Introduction to classification: Clean, prep, and visualize your
data
In these four lessons, you will explore a fundamental focus of
classic machine learning - classification. We will walk through
using various classification algorithms with a dataset about all the
brilliant cuisines of Asia and India. Hope you’re hungry!
Classification is a form of supervised
learning that bears a lot in common with regression techniques. In
classification, you train a model to predict which category
an item belongs to. If machine learning is all about predicting values
or names to things by using datasets, then classification generally
falls into two groups: binary classification and multiclass
classification.
Remember:
Linear regression helped you predict
relationships between variables and make accurate predictions on where a
new datapoint would fall in relationship to that line. So, you could
predict a numeric values such as what price a pumpkin would be in
September vs. December, for example.
Logistic regression helped you discover “binary
categories”: at this price point, is this pumpkin orange or
not-orange?
Classification uses various algorithms to determine other ways of
determining a data point’s label or class. Let’s work with this cuisine
data to see whether, by observing a group of ingredients, we can
determine its cuisine of origin.
Introduction
Classification is one of the fundamental activities of the machine
learning researcher and data scientist. From basic classification of a
binary value (“is this email spam or not?”), to complex image
classification and segmentation using computer vision, it’s always
useful to be able to sort data into classes and ask questions of it.
To state the process in a more scientific way, your classification
method creates a predictive model that enables you to map the
relationship between input variables to output variables.
Before starting the process of cleaning our data, visualizing it, and
prepping it for our ML tasks, let’s learn a bit about the various ways
machine learning can be leveraged to classify data.
Derived from statistics,
classification using classic machine learning uses features, such as
smoker
, weight
, and age
to
determine likelihood of developing X disease. As a supervised
learning technique similar to the regression exercises you performed
earlier, your data is labeled and the ML algorithms use those labels to
classify and predict classes (or ‘features’) of a dataset and assign
them to a group or outcome.
✅ Take a moment to imagine a dataset about cuisines. What would a
multiclass model be able to answer? What would a binary model be able to
answer? What if you wanted to determine whether a given cuisine was
likely to use fenugreek? What if you wanted to see if, given a present
of a grocery bag full of star anise, artichokes, cauliflower, and
horseradish, you could create a typical Indian dish?
Hello ‘classifier’
The question we want to ask of this cuisine dataset is actually a
multiclass question, as we have several potential
national cuisines to work with. Given a batch of ingredients, which of
these many classes will the data fit?
Tidymodels offers several different algorithms to use to classify
data, depending on the kind of problem you want to solve. In the next
two lessons, you’ll learn about several of these algorithms.
Prerequisite
For this lesson, we’ll require the following packages to clean, prep
and visualize our data:
You can have them installed as:
install.packages(c("tidyverse", "tidymodels", "DataExplorer", "here"))
Alternately, the script below checks whether you have the packages
required to complete this module and installs them for you in case they
are missing.
suppressWarnings(if (!require("pacman"))install.packages("pacman"))
pacman::p_load(tidyverse, tidymodels, DataExplorer, themis, here)
We’ll later load these awesome packages and make them available in
our current R session. (This is for mere illustration,
pacman::p_load()
already did that for you)
Exercise - clean and balance your data
The first task at hand, before starting this project, is to clean and
balance your data to get better results
Let’s meet the data!🕵️
# Import data
df <- read_csv(file = "https://raw.githubusercontent.com/microsoft/ML-For-Beginners/main/4-Classification/data/cuisines.csv")
## New names:
## Rows: 2448 Columns: 385
## -- Column specification
## -------------------------------------------------------- Delimiter: "," chr
## (1): cuisine dbl (384): ...1, almond, angelica, anise, anise_seed, apple,
## apple_brandy, a...
## i Use `spec()` to retrieve the full column specification for this data. i
## Specify the column types or set `show_col_types = FALSE` to quiet this message.
## * `` -> `...1`
# View the first 5 rows
df %>%
slice_head(n = 5)
Interesting! From the looks of it, the first column is a kind of
id
column. Let’s get a little more information about the
data.
# Basic information about the data
df %>%
introduce()
# Visualize basic information above
df %>%
plot_intro(ggtheme = theme_light())
From the output, we can immediately see that we have
2448
rows and 385
columns and 0
missing values. We also have 1 discrete column, cuisine.
Exercise - learning about cuisines
- Now the work starts to become more interesting. Let’s discover the
distribution of data, per cuisine.
# Count observations per cuisine
df %>%
count(cuisine) %>%
arrange(n)
# Plot the distribution
theme_set(theme_light())
df %>%
count(cuisine) %>%
ggplot(mapping = aes(x = n, y = reorder(cuisine, -n))) +
geom_col(fill = "midnightblue", alpha = 0.7) +
ylab("cuisine")
There are a finite number of cuisines, but the distribution of data
is uneven. You can fix that! Before doing so, explore a little more.
- Next, let’s assign each cuisine into it’s individual tibble and find
out how much data is available (rows, columns) per cuisine.
A tibble, or tbl_df, is a modern reimagining of the data.frame,
keeping what time has proven to be effective, and throwing out what is
not.
# Create individual tibbles for the cuisines
thai_df <- df %>%
filter(cuisine == "thai")
japanese_df <- df %>%
filter(cuisine == "japanese")
chinese_df <- df %>%
filter(cuisine == "chinese")
indian_df <- df %>%
filter(cuisine == "indian")
korean_df <- df %>%
filter(cuisine == "korean")
# Find out how much data is available per cuisine
cat(" thai df:", dim(thai_df), "\n",
"japanese df:", dim(japanese_df), "\n",
"chinese_df:", dim(chinese_df), "\n",
"indian_df:", dim(indian_df), "\n",
"korean_df:", dim(korean_df))
## thai df: 289 385
## japanese df: 320 385
## chinese_df: 442 385
## indian_df: 598 385
## korean_df: 799 385
Perfect!😋
Exercise - Discovering top ingredients by cuisine using
dplyr
Now you can dig deeper into the data and learn what are the typical
ingredients per cuisine. You should clean out recurrent data that
creates confusion between cuisines, so let’s learn about this
problem.
- Create a function
create_ingredient()
in R that returns
an ingredient dataframe. This function will start by dropping an
unhelpful column and sort through ingredients by their count.
The basic structure of a function in R is:
myFunction <- function(arglist){
...
return
(value)
}
A tidy introduction to R functions can be found here.
Let’s get right into it! We’ll make use of dplyr verbs which we have been
learning in our previous lessons. As a recap:
dplyr::select()
: help you pick which
columns to keep or exclude.
dplyr::pivot_longer()
: helps you to “lengthen” data,
increasing the number of rows and decreasing the number of
columns.
dplyr::group_by()
and
dplyr::summarise()
: helps you to find find summary
statistics for different groups, and put them in a nice table.
dplyr::filter()
: creates a subset of the data only
containing rows that satisfy your conditions.
dplyr::mutate()
: helps you to create or modify
columns.
Check out this art-filled
learnr tutorial by Allison Horst, that introduces some useful data
wrangling functions in dplyr (part of the Tidyverse)
# Creates a functions that returns the top ingredients by class
create_ingredient <- function(df){
# Drop the id column which is the first colum
ingredient_df = df %>% select(-1) %>%
# Transpose data to a long format
pivot_longer(!cuisine, names_to = "ingredients", values_to = "count") %>%
# Find the top most ingredients for a particular cuisine
group_by(ingredients) %>%
summarise(n_instances = sum(count)) %>%
filter(n_instances != 0) %>%
# Arrange by descending order
arrange(desc(n_instances)) %>%
mutate(ingredients = factor(ingredients) %>% fct_inorder())
return(ingredient_df)
} # End of function
- Now we can use the function to get an idea of top ten most popular
ingredient by cuisine. Let’s take it out for a spin with
thai_df
# Call create_ingredient and display popular ingredients
thai_ingredient_df <- create_ingredient(df = thai_df)
thai_ingredient_df %>%
slice_head(n = 10)
In the previous section, we used geom_col()
, let’s see
how you can use geom_bar
too, to create bar charts. Use
?geom_bar
for further reading.
# Make a bar chart for popular thai cuisines
thai_ingredient_df %>%
slice_head(n = 10) %>%
ggplot(aes(x = n_instances, y = ingredients)) +
geom_bar(stat = "identity", width = 0.5, fill = "steelblue") +
xlab("") + ylab("")
- Let’s do the same for the Japanese data
# Get popular ingredients for Japanese cuisines and make bar chart
create_ingredient(df = japanese_df) %>%
slice_head(n = 10) %>%
ggplot(aes(x = n_instances, y = ingredients)) +
geom_bar(stat = "identity", width = 0.5, fill = "darkorange", alpha = 0.8) +
xlab("") + ylab("")
- What about the Chinese cuisines?
# Get popular ingredients for Chinese cuisines and make bar chart
create_ingredient(df = chinese_df) %>%
slice_head(n = 10) %>%
ggplot(aes(x = n_instances, y = ingredients)) +
geom_bar(stat = "identity", width = 0.5, fill = "cyan4", alpha = 0.8) +
xlab("") + ylab("")
- Let’s take a look at the Indian cuisines 🌶️.
# Get popular ingredients for Indian cuisines and make bar chart
create_ingredient(df = indian_df) %>%
slice_head(n = 10) %>%
ggplot(aes(x = n_instances, y = ingredients)) +
geom_bar(stat = "identity", width = 0.5, fill = "#041E42FF", alpha = 0.8) +
xlab("") + ylab("")
- Finally, plot the Korean ingredients.
# Get popular ingredients for Korean cuisines and make bar chart
create_ingredient(df = korean_df) %>%
slice_head(n = 10) %>%
ggplot(aes(x = n_instances, y = ingredients)) +
geom_bar(stat = "identity", width = 0.5, fill = "#852419FF", alpha = 0.8) +
xlab("") + ylab("")
- From the data visualizations, we can now drop the most common
ingredients that create confusion between distinct cuisines, using
dplyr::select()
.
Everyone loves rice, garlic and ginger!
# Drop rice, garlic and ginger from our original data set
df_select <- df %>%
select(-c(1, rice, garlic, ginger))
# Display new data set
df_select %>%
slice_head(n = 5)
Preprocessing data using recipes 👩🍳👨🍳 - Dealing with imbalanced data
⚖️
Given that this lesson is about cuisines, we have to put
recipes
into context .
Tidymodels provides yet another neat package: recipes
- a
package for preprocessing data.
Now we are on the same page 😅.
Let’s take a look at the distribution of our cuisines again.
# Distribution of cuisines
old_label_count <- df_select %>%
count(cuisine) %>%
arrange(desc(n))
old_label_count
As you can see, there is quite an unequal distribution in the number
of cuisines. Korean cuisines are almost 3 times Thai cuisines.
Imbalanced data often has negative effects on the model performance.
Think about a binary classification. If most of your data is one class,
a ML model is going to predict that class more frequently, just because
there is more data for it. Balancing the data takes any skewed data and
helps remove this imbalance. Many models perform best when the number of
observations is equal and, thus, tend to struggle with unbalanced
data.
There are majorly two ways of dealing with imbalanced data sets:
Let’s now demonstrate how to deal with imbalanced data sets using a
recipe
. A recipe can be thought of as a blueprint that
describes what steps should be applied to a data set in order to get it
ready for data analysis.
# Load themis package for dealing with imbalanced data
library(themis)
# Create a recipe for preprocessing data
cuisines_recipe <- recipe(cuisine ~ ., data = df_select) %>%
step_smote(cuisine)
cuisines_recipe
##
## -- Recipe ----------------------------------------------------------------------
##
## -- Inputs
## Number of variables by role
## outcome: 1
## predictor: 380
##
## -- Operations
## * SMOTE based on: cuisine
Let’s break down our preprocessing steps.
The call to recipe()
with a formula tells the recipe
the roles of the variables using df_select
data as
the reference. For instance the cuisine
column has been
assigned an outcome
role while the rest of the columns have
been assigned a predictor
role.
step_smote(cuisine)
creates a specification of a recipe step that synthetically
generates new examples of the minority class using nearest neighbors of
these cases.
Now, if we wanted to see the preprocessed data, we’d have to prep()
and bake()
our recipe.
prep()
: estimates the required parameters from a
training set that can be later applied to other data sets.
bake()
: takes a prepped recipe and applies the
operations to any data set.
# Prep and bake the recipe
preprocessed_df <- cuisines_recipe %>%
prep() %>%
bake(new_data = NULL) %>%
relocate(cuisine)
# Display data
preprocessed_df %>%
slice_head(n = 5)
# Quick summary stats
preprocessed_df %>%
introduce()
Let’s now check the distribution of our cuisines and compare them
with the imbalanced data.
# Distribution of cuisines
new_label_count <- preprocessed_df %>%
count(cuisine) %>%
arrange(desc(n))
list(new_label_count = new_label_count,
old_label_count = old_label_count)
## $new_label_count
## # A tibble: 5 x 2
## cuisine n
## <fct> <int>
## 1 chinese 799
## 2 indian 799
## 3 japanese 799
## 4 korean 799
## 5 thai 799
##
## $old_label_count
## # A tibble: 5 x 2
## cuisine n
## <chr> <int>
## 1 korean 799
## 2 indian 598
## 3 chinese 442
## 4 japanese 320
## 5 thai 289
Yum! The data is nice and clean, balanced, and very delicious 😋!
Normally, a recipe is usually used as a preprocessor for modelling
where it defines what steps should be applied to a data set in order to
get it ready for modelling. In that case, a workflow()
is
typically used (as we have already seen in our previous lessons) instead
of manually estimating a recipe
As such, you don’t typically need to
prep()
and
bake()
recipes when you use tidymodels,
but they are helpful functions to have in your toolkit for confirming
that recipes are doing what you expect like in our case.
When you bake()
a prepped recipe with
new_data = NULL
, you get the data that you
provided when defining the recipe back, but having undergone the
preprocessing steps.
Let’s now save a copy of this data for use in future lessons:
# Save preprocessed data
write_csv(preprocessed_df, "../../../data/cleaned_cuisines_R.csv")
This fresh CSV can now be found in the root data folder.
🚀Challenge
This curriculum contains several interesting datasets. Dig through
the data
folders and see if any contain datasets that would
be appropriate for binary or multi-class classification? What questions
would you ask of this dataset?
Review & Self Study
THANK YOU TO:
Allison Horst
for creating the amazing illustrations that make R more welcoming and
engaging. Find more illustrations at her gallery.
Cassie Breviu and Jen Looper for creating the
original Python version of this module ♥️
LS0tDQp0aXRsZTogJ0J1aWxkIGEgY2xhc3NpZmljYXRpb24gbW9kZWw6IERlbGljaW91cyBBc2lhbiBhbmQgSW5kaWFuIEN1aXNpbmVzJw0Kb3V0cHV0Og0KICBodG1sX2RvY3VtZW50Og0KICAgIGRmX3ByaW50OiBwYWdlZA0KICAgIHRoZW1lOiBmbGF0bHkNCiAgICBoaWdobGlnaHQ6IGJyZWV6ZWRhcmsNCiAgICB0b2M6IHllcw0KICAgIHRvY19mbG9hdDogeWVzDQogICAgY29kZV9kb3dubG9hZDogeWVzDQotLS0NCg0KIyMgSW50cm9kdWN0aW9uIHRvIGNsYXNzaWZpY2F0aW9uOiBDbGVhbiwgcHJlcCwgYW5kIHZpc3VhbGl6ZSB5b3VyIGRhdGENCg0KSW4gdGhlc2UgZm91ciBsZXNzb25zLCB5b3Ugd2lsbCBleHBsb3JlIGEgZnVuZGFtZW50YWwgZm9jdXMgb2YgY2xhc3NpYyBtYWNoaW5lIGxlYXJuaW5nIC0gKmNsYXNzaWZpY2F0aW9uKi4gV2Ugd2lsbCB3YWxrIHRocm91Z2ggdXNpbmcgdmFyaW91cyBjbGFzc2lmaWNhdGlvbiBhbGdvcml0aG1zIHdpdGggYSBkYXRhc2V0IGFib3V0IGFsbCB0aGUgYnJpbGxpYW50IGN1aXNpbmVzIG9mIEFzaWEgYW5kIEluZGlhLiBIb3BlIHlvdSdyZSBodW5ncnkhDQoNCiFbQ2VsZWJyYXRlIHBhbi1Bc2lhbiBjdWlzaW5lcyBpbiB0aGVzZSBsZXNzb25zISBJbWFnZSBieSBKZW4gTG9vcGVyXSguLi8uLi9pbWFnZXMvcGluY2gucG5nKQ0KDQpDbGFzc2lmaWNhdGlvbiBpcyBhIGZvcm0gb2YgW3N1cGVydmlzZWQgbGVhcm5pbmddKGh0dHBzOi8vd2lraXBlZGlhLm9yZy93aWtpL1N1cGVydmlzZWRfbGVhcm5pbmcpIHRoYXQgYmVhcnMgYSBsb3QgaW4gY29tbW9uIHdpdGggcmVncmVzc2lvbiB0ZWNobmlxdWVzLiBJbiBjbGFzc2lmaWNhdGlvbiwgeW91IHRyYWluIGEgbW9kZWwgdG8gcHJlZGljdCB3aGljaCBgY2F0ZWdvcnlgIGFuIGl0ZW0gYmVsb25ncyB0by4gSWYgbWFjaGluZSBsZWFybmluZyBpcyBhbGwgYWJvdXQgcHJlZGljdGluZyB2YWx1ZXMgb3IgbmFtZXMgdG8gdGhpbmdzIGJ5IHVzaW5nIGRhdGFzZXRzLCB0aGVuIGNsYXNzaWZpY2F0aW9uIGdlbmVyYWxseSBmYWxscyBpbnRvIHR3byBncm91cHM6ICpiaW5hcnkgY2xhc3NpZmljYXRpb24qIGFuZCAqbXVsdGljbGFzcyBjbGFzc2lmaWNhdGlvbiouDQoNClJlbWVtYmVyOg0KDQotICAgKipMaW5lYXIgcmVncmVzc2lvbioqIGhlbHBlZCB5b3UgcHJlZGljdCByZWxhdGlvbnNoaXBzIGJldHdlZW4gdmFyaWFibGVzIGFuZCBtYWtlIGFjY3VyYXRlIHByZWRpY3Rpb25zIG9uIHdoZXJlIGEgbmV3IGRhdGFwb2ludCB3b3VsZCBmYWxsIGluIHJlbGF0aW9uc2hpcCB0byB0aGF0IGxpbmUuIFNvLCB5b3UgY291bGQgcHJlZGljdCBhIG51bWVyaWMgdmFsdWVzIHN1Y2ggYXMgKndoYXQgcHJpY2UgYSBwdW1wa2luIHdvdWxkIGJlIGluIFNlcHRlbWJlciB2cy4gRGVjZW1iZXIqLCBmb3IgZXhhbXBsZS4NCg0KLSAgICoqTG9naXN0aWMgcmVncmVzc2lvbioqIGhlbHBlZCB5b3UgZGlzY292ZXIgImJpbmFyeSBjYXRlZ29yaWVzIjogYXQgdGhpcyBwcmljZSBwb2ludCwgKmlzIHRoaXMgcHVtcGtpbiBvcmFuZ2Ugb3Igbm90LW9yYW5nZSo/DQoNCkNsYXNzaWZpY2F0aW9uIHVzZXMgdmFyaW91cyBhbGdvcml0aG1zIHRvIGRldGVybWluZSBvdGhlciB3YXlzIG9mIGRldGVybWluaW5nIGEgZGF0YSBwb2ludCdzIGxhYmVsIG9yIGNsYXNzLiBMZXQncyB3b3JrIHdpdGggdGhpcyBjdWlzaW5lIGRhdGEgdG8gc2VlIHdoZXRoZXIsIGJ5IG9ic2VydmluZyBhIGdyb3VwIG9mIGluZ3JlZGllbnRzLCB3ZSBjYW4gZGV0ZXJtaW5lIGl0cyBjdWlzaW5lIG9mIG9yaWdpbi4NCg0KIyMjIFsqKlByZS1sZWN0dXJlIHF1aXoqKl0oaHR0cHM6Ly9ncmF5LXNhbmQtMDdhMTBmNDAzLjEuYXp1cmVzdGF0aWNhcHBzLm5ldC9xdWl6LzE5LykNCg0KIyMjICoqSW50cm9kdWN0aW9uKioNCg0KQ2xhc3NpZmljYXRpb24gaXMgb25lIG9mIHRoZSBmdW5kYW1lbnRhbCBhY3Rpdml0aWVzIG9mIHRoZSBtYWNoaW5lIGxlYXJuaW5nIHJlc2VhcmNoZXIgYW5kIGRhdGEgc2NpZW50aXN0LiBGcm9tIGJhc2ljIGNsYXNzaWZpY2F0aW9uIG9mIGEgYmluYXJ5IHZhbHVlICgiaXMgdGhpcyBlbWFpbCBzcGFtIG9yIG5vdD8iKSwgdG8gY29tcGxleCBpbWFnZSBjbGFzc2lmaWNhdGlvbiBhbmQgc2VnbWVudGF0aW9uIHVzaW5nIGNvbXB1dGVyIHZpc2lvbiwgaXQncyBhbHdheXMgdXNlZnVsIHRvIGJlIGFibGUgdG8gc29ydCBkYXRhIGludG8gY2xhc3NlcyBhbmQgYXNrIHF1ZXN0aW9ucyBvZiBpdC4NCg0KVG8gc3RhdGUgdGhlIHByb2Nlc3MgaW4gYSBtb3JlIHNjaWVudGlmaWMgd2F5LCB5b3VyIGNsYXNzaWZpY2F0aW9uIG1ldGhvZCBjcmVhdGVzIGEgcHJlZGljdGl2ZSBtb2RlbCB0aGF0IGVuYWJsZXMgeW91IHRvIG1hcCB0aGUgcmVsYXRpb25zaGlwIGJldHdlZW4gaW5wdXQgdmFyaWFibGVzIHRvIG91dHB1dCB2YXJpYWJsZXMuDQoNCiFbQmluYXJ5IHZzLiBtdWx0aWNsYXNzIHByb2JsZW1zIGZvciBjbGFzc2lmaWNhdGlvbiBhbGdvcml0aG1zIHRvIGhhbmRsZS4gSW5mb2dyYXBoaWMgYnkgSmVuIExvb3Blcl0oLi4vLi4vaW1hZ2VzL2JpbmFyeS1tdWx0aWNsYXNzLnBuZyl7d2lkdGg9IjUwMCJ9DQoNCkJlZm9yZSBzdGFydGluZyB0aGUgcHJvY2VzcyBvZiBjbGVhbmluZyBvdXIgZGF0YSwgdmlzdWFsaXppbmcgaXQsIGFuZCBwcmVwcGluZyBpdCBmb3Igb3VyIE1MIHRhc2tzLCBsZXQncyBsZWFybiBhIGJpdCBhYm91dCB0aGUgdmFyaW91cyB3YXlzIG1hY2hpbmUgbGVhcm5pbmcgY2FuIGJlIGxldmVyYWdlZCB0byBjbGFzc2lmeSBkYXRhLg0KDQpEZXJpdmVkIGZyb20gW3N0YXRpc3RpY3NdKGh0dHBzOi8vd2lraXBlZGlhLm9yZy93aWtpL1N0YXRpc3RpY2FsX2NsYXNzaWZpY2F0aW9uKSwgY2xhc3NpZmljYXRpb24gdXNpbmcgY2xhc3NpYyBtYWNoaW5lIGxlYXJuaW5nIHVzZXMgZmVhdHVyZXMsIHN1Y2ggYXMgYHNtb2tlcmAsIGB3ZWlnaHRgLCBhbmQgYGFnZWAgdG8gZGV0ZXJtaW5lICpsaWtlbGlob29kIG9mIGRldmVsb3BpbmcgWCBkaXNlYXNlKi4gQXMgYSBzdXBlcnZpc2VkIGxlYXJuaW5nIHRlY2huaXF1ZSBzaW1pbGFyIHRvIHRoZSByZWdyZXNzaW9uIGV4ZXJjaXNlcyB5b3UgcGVyZm9ybWVkIGVhcmxpZXIsIHlvdXIgZGF0YSBpcyBsYWJlbGVkIGFuZCB0aGUgTUwgYWxnb3JpdGhtcyB1c2UgdGhvc2UgbGFiZWxzIHRvIGNsYXNzaWZ5IGFuZCBwcmVkaWN0IGNsYXNzZXMgKG9yICdmZWF0dXJlcycpIG9mIGEgZGF0YXNldCBhbmQgYXNzaWduIHRoZW0gdG8gYSBncm91cCBvciBvdXRjb21lLg0KDQrinIUgVGFrZSBhIG1vbWVudCB0byBpbWFnaW5lIGEgZGF0YXNldCBhYm91dCBjdWlzaW5lcy4gV2hhdCB3b3VsZCBhIG11bHRpY2xhc3MgbW9kZWwgYmUgYWJsZSB0byBhbnN3ZXI/IFdoYXQgd291bGQgYSBiaW5hcnkgbW9kZWwgYmUgYWJsZSB0byBhbnN3ZXI/IFdoYXQgaWYgeW91IHdhbnRlZCB0byBkZXRlcm1pbmUgd2hldGhlciBhIGdpdmVuIGN1aXNpbmUgd2FzIGxpa2VseSB0byB1c2UgZmVudWdyZWVrPyBXaGF0IGlmIHlvdSB3YW50ZWQgdG8gc2VlIGlmLCBnaXZlbiBhIHByZXNlbnQgb2YgYSBncm9jZXJ5IGJhZyBmdWxsIG9mIHN0YXIgYW5pc2UsIGFydGljaG9rZXMsIGNhdWxpZmxvd2VyLCBhbmQgaG9yc2VyYWRpc2gsIHlvdSBjb3VsZCBjcmVhdGUgYSB0eXBpY2FsIEluZGlhbiBkaXNoPw0KDQojIyMgKipIZWxsbyAnY2xhc3NpZmllcicqKg0KDQpUaGUgcXVlc3Rpb24gd2Ugd2FudCB0byBhc2sgb2YgdGhpcyBjdWlzaW5lIGRhdGFzZXQgaXMgYWN0dWFsbHkgYSAqKm11bHRpY2xhc3MgcXVlc3Rpb24qKiwgYXMgd2UgaGF2ZSBzZXZlcmFsIHBvdGVudGlhbCBuYXRpb25hbCBjdWlzaW5lcyB0byB3b3JrIHdpdGguIEdpdmVuIGEgYmF0Y2ggb2YgaW5ncmVkaWVudHMsIHdoaWNoIG9mIHRoZXNlIG1hbnkgY2xhc3NlcyB3aWxsIHRoZSBkYXRhIGZpdD8NCg0KVGlkeW1vZGVscyBvZmZlcnMgc2V2ZXJhbCBkaWZmZXJlbnQgYWxnb3JpdGhtcyB0byB1c2UgdG8gY2xhc3NpZnkgZGF0YSwgZGVwZW5kaW5nIG9uIHRoZSBraW5kIG9mIHByb2JsZW0geW91IHdhbnQgdG8gc29sdmUuIEluIHRoZSBuZXh0IHR3byBsZXNzb25zLCB5b3UnbGwgbGVhcm4gYWJvdXQgc2V2ZXJhbCBvZiB0aGVzZSBhbGdvcml0aG1zLg0KDQojIyMjICoqUHJlcmVxdWlzaXRlKioNCg0KRm9yIHRoaXMgbGVzc29uLCB3ZSdsbCByZXF1aXJlIHRoZSBmb2xsb3dpbmcgcGFja2FnZXMgdG8gY2xlYW4sIHByZXAgYW5kIHZpc3VhbGl6ZSBvdXIgZGF0YToNCg0KLSAgIGB0aWR5dmVyc2VgOiBUaGUgW3RpZHl2ZXJzZV0oaHR0cHM6Ly93d3cudGlkeXZlcnNlLm9yZy8pIGlzIGEgW2NvbGxlY3Rpb24gb2YgUiBwYWNrYWdlc10oaHR0cHM6Ly93d3cudGlkeXZlcnNlLm9yZy9wYWNrYWdlcykgZGVzaWduZWQgdG8gbWFrZXMgZGF0YSBzY2llbmNlIGZhc3RlciwgZWFzaWVyIGFuZCBtb3JlIGZ1biENCg0KLSAgIGB0aWR5bW9kZWxzYDogVGhlIFt0aWR5bW9kZWxzXShodHRwczovL3d3dy50aWR5bW9kZWxzLm9yZy8pIGZyYW1ld29yayBpcyBhIFtjb2xsZWN0aW9uIG9mIHBhY2thZ2VzXShodHRwczovL3d3dy50aWR5bW9kZWxzLm9yZy9wYWNrYWdlcy8pIGZvciBtb2RlbGluZyBhbmQgbWFjaGluZSBsZWFybmluZy4NCg0KLSAgIGBEYXRhRXhwbG9yZXJgOiBUaGUgW0RhdGFFeHBsb3JlciBwYWNrYWdlXShodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvRGF0YUV4cGxvcmVyL3ZpZ25ldHRlcy9kYXRhZXhwbG9yZXItaW50cm8uaHRtbCkgaXMgbWVhbnQgdG8gc2ltcGxpZnkgYW5kIGF1dG9tYXRlIEVEQSBwcm9jZXNzIGFuZCByZXBvcnQgZ2VuZXJhdGlvbi4NCg0KLSAgIGB0aGVtaXNgOiBUaGUgW3RoZW1pcyBwYWNrYWdlXShodHRwczovL3RoZW1pcy50aWR5bW9kZWxzLm9yZy8pIHByb3ZpZGVzIEV4dHJhIFJlY2lwZXMgU3RlcHMgZm9yIERlYWxpbmcgd2l0aCBVbmJhbGFuY2VkIERhdGEuDQoNCllvdSBjYW4gaGF2ZSB0aGVtIGluc3RhbGxlZCBhczoNCg0KYGluc3RhbGwucGFja2FnZXMoYygidGlkeXZlcnNlIiwgInRpZHltb2RlbHMiLCAiRGF0YUV4cGxvcmVyIiwgImhlcmUiKSlgDQoNCkFsdGVybmF0ZWx5LCB0aGUgc2NyaXB0IGJlbG93IGNoZWNrcyB3aGV0aGVyIHlvdSBoYXZlIHRoZSBwYWNrYWdlcyByZXF1aXJlZCB0byBjb21wbGV0ZSB0aGlzIG1vZHVsZSBhbmQgaW5zdGFsbHMgdGhlbSBmb3IgeW91IGluIGNhc2UgdGhleSBhcmUgbWlzc2luZy4NCg0KYGBge3IsIG1lc3NhZ2U9Riwgd2FybmluZz1GfQ0Kc3VwcHJlc3NXYXJuaW5ncyhpZiAoIXJlcXVpcmUoInBhY21hbiIpKWluc3RhbGwucGFja2FnZXMoInBhY21hbiIpKQ0KDQpwYWNtYW46OnBfbG9hZCh0aWR5dmVyc2UsIHRpZHltb2RlbHMsIERhdGFFeHBsb3JlciwgdGhlbWlzLCBoZXJlKQ0KYGBgDQoNCldlJ2xsIGxhdGVyIGxvYWQgdGhlc2UgYXdlc29tZSBwYWNrYWdlcyBhbmQgbWFrZSB0aGVtIGF2YWlsYWJsZSBpbiBvdXIgY3VycmVudCBSIHNlc3Npb24uIChUaGlzIGlzIGZvciBtZXJlIGlsbHVzdHJhdGlvbiwgYHBhY21hbjo6cF9sb2FkKClgIGFscmVhZHkgZGlkIHRoYXQgZm9yIHlvdSkNCg0KIyMgRXhlcmNpc2UgLSBjbGVhbiBhbmQgYmFsYW5jZSB5b3VyIGRhdGENCg0KVGhlIGZpcnN0IHRhc2sgYXQgaGFuZCwgYmVmb3JlIHN0YXJ0aW5nIHRoaXMgcHJvamVjdCwgaXMgdG8gY2xlYW4gYW5kICoqYmFsYW5jZSoqIHlvdXIgZGF0YSB0byBnZXQgYmV0dGVyIHJlc3VsdHMNCg0KTGV0J3MgbWVldCB0aGUgZGF0YSHwn5W177iPDQoNCmBgYHtyIGltcG9ydF9kYXRhfQ0KIyBJbXBvcnQgZGF0YQ0KZGYgPC0gcmVhZF9jc3YoZmlsZSA9ICJodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vbWljcm9zb2Z0L01MLUZvci1CZWdpbm5lcnMvbWFpbi80LUNsYXNzaWZpY2F0aW9uL2RhdGEvY3Vpc2luZXMuY3N2IikNCg0KIyBWaWV3IHRoZSBmaXJzdCA1IHJvd3MNCmRmICU+JSANCiAgc2xpY2VfaGVhZChuID0gNSkNCg0KYGBgDQoNCkludGVyZXN0aW5nISBGcm9tIHRoZSBsb29rcyBvZiBpdCwgdGhlIGZpcnN0IGNvbHVtbiBpcyBhIGtpbmQgb2YgYGlkYCBjb2x1bW4uIExldCdzIGdldCBhIGxpdHRsZSBtb3JlIGluZm9ybWF0aW9uIGFib3V0IHRoZSBkYXRhLg0KDQpgYGB7ciBpbmZvfQ0KIyBCYXNpYyBpbmZvcm1hdGlvbiBhYm91dCB0aGUgZGF0YQ0KZGYgJT4lDQogIGludHJvZHVjZSgpDQoNCiMgVmlzdWFsaXplIGJhc2ljIGluZm9ybWF0aW9uIGFib3ZlDQpkZiAlPiUgDQogIHBsb3RfaW50cm8oZ2d0aGVtZSA9IHRoZW1lX2xpZ2h0KCkpDQpgYGANCg0KRnJvbSB0aGUgb3V0cHV0LCB3ZSBjYW4gaW1tZWRpYXRlbHkgc2VlIHRoYXQgd2UgaGF2ZSBgMjQ0OGAgcm93cyBhbmQgYDM4NWAgY29sdW1ucyBhbmQgYDBgIG1pc3NpbmcgdmFsdWVzLiBXZSBhbHNvIGhhdmUgMSBkaXNjcmV0ZSBjb2x1bW4sICpjdWlzaW5lKi4NCg0KIyMgRXhlcmNpc2UgLSBsZWFybmluZyBhYm91dCBjdWlzaW5lcw0KDQoxLiAgTm93IHRoZSB3b3JrIHN0YXJ0cyB0byBiZWNvbWUgbW9yZSBpbnRlcmVzdGluZy4gTGV0J3MgZGlzY292ZXIgdGhlIGRpc3RyaWJ1dGlvbiBvZiBkYXRhLCBwZXIgY3Vpc2luZS4NCg0KYGBge3IgZmlsdGVyX2N1aXNpbmV9DQojIENvdW50IG9ic2VydmF0aW9ucyBwZXIgY3Vpc2luZQ0KZGYgJT4lIA0KICBjb3VudChjdWlzaW5lKSAlPiUgDQogIGFycmFuZ2UobikNCg0KIyBQbG90IHRoZSBkaXN0cmlidXRpb24NCnRoZW1lX3NldCh0aGVtZV9saWdodCgpKQ0KZGYgJT4lIA0KICBjb3VudChjdWlzaW5lKSAlPiUgDQogIGdncGxvdChtYXBwaW5nID0gYWVzKHggPSBuLCB5ID0gcmVvcmRlcihjdWlzaW5lLCAtbikpKSArDQogIGdlb21fY29sKGZpbGwgPSAibWlkbmlnaHRibHVlIiwgYWxwaGEgPSAwLjcpICsNCiAgeWxhYigiY3Vpc2luZSIpDQpgYGANCg0KVGhlcmUgYXJlIGEgZmluaXRlIG51bWJlciBvZiBjdWlzaW5lcywgYnV0IHRoZSBkaXN0cmlidXRpb24gb2YgZGF0YSBpcyB1bmV2ZW4uIFlvdSBjYW4gZml4IHRoYXQhIEJlZm9yZSBkb2luZyBzbywgZXhwbG9yZSBhIGxpdHRsZSBtb3JlLg0KDQoyLiAgTmV4dCwgbGV0J3MgYXNzaWduIGVhY2ggY3Vpc2luZSBpbnRvIGl0J3MgaW5kaXZpZHVhbCB0aWJibGUgYW5kIGZpbmQgb3V0IGhvdyBtdWNoIGRhdGEgaXMgYXZhaWxhYmxlIChyb3dzLCBjb2x1bW5zKSBwZXIgY3Vpc2luZS4NCg0KPiBBIHRpYmJsZSwgb3IgdGJsX2RmLCBpcyBhIG1vZGVybiByZWltYWdpbmluZyBvZiB0aGUgZGF0YS5mcmFtZSwga2VlcGluZyB3aGF0IHRpbWUgaGFzIHByb3ZlbiB0byBiZSBlZmZlY3RpdmUsIGFuZCB0aHJvd2luZyBvdXQgd2hhdCBpcyBub3QuDQoNCiFbQXJ0d29yayBieSBcQGFsbGlzb25faG9yc3RdKC4uLy4uL2ltYWdlcy9kcGx5cl9maWx0ZXIuanBnKQ0KDQpgYGB7ciBjdWlzaW5lX2RmfQ0KIyBDcmVhdGUgaW5kaXZpZHVhbCB0aWJibGVzIGZvciB0aGUgY3Vpc2luZXMNCnRoYWlfZGYgPC0gZGYgJT4lIA0KICBmaWx0ZXIoY3Vpc2luZSA9PSAidGhhaSIpDQpqYXBhbmVzZV9kZiA8LSBkZiAlPiUgDQogIGZpbHRlcihjdWlzaW5lID09ICJqYXBhbmVzZSIpDQpjaGluZXNlX2RmIDwtIGRmICU+JSANCiAgZmlsdGVyKGN1aXNpbmUgPT0gImNoaW5lc2UiKQ0KaW5kaWFuX2RmIDwtIGRmICU+JSANCiAgZmlsdGVyKGN1aXNpbmUgPT0gImluZGlhbiIpDQprb3JlYW5fZGYgPC0gZGYgJT4lIA0KICBmaWx0ZXIoY3Vpc2luZSA9PSAia29yZWFuIikNCg0KDQojIEZpbmQgb3V0IGhvdyBtdWNoIGRhdGEgaXMgYXZhaWxhYmxlIHBlciBjdWlzaW5lDQpjYXQoIiB0aGFpIGRmOiIsIGRpbSh0aGFpX2RmKSwgIlxuIiwNCiAgICAiamFwYW5lc2UgZGY6IiwgZGltKGphcGFuZXNlX2RmKSwgIlxuIiwNCiAgICAiY2hpbmVzZV9kZjoiLCBkaW0oY2hpbmVzZV9kZiksICJcbiIsDQogICAgImluZGlhbl9kZjoiLCBkaW0oaW5kaWFuX2RmKSwgIlxuIiwNCiAgICAia29yZWFuX2RmOiIsIGRpbShrb3JlYW5fZGYpKQ0KYGBgDQoNClBlcmZlY3Qh8J+Yiw0KDQojIyAqKkV4ZXJjaXNlIC0gRGlzY292ZXJpbmcgdG9wIGluZ3JlZGllbnRzIGJ5IGN1aXNpbmUgdXNpbmcgZHBseXIqKg0KDQpOb3cgeW91IGNhbiBkaWcgZGVlcGVyIGludG8gdGhlIGRhdGEgYW5kIGxlYXJuIHdoYXQgYXJlIHRoZSB0eXBpY2FsIGluZ3JlZGllbnRzIHBlciBjdWlzaW5lLiBZb3Ugc2hvdWxkIGNsZWFuIG91dCByZWN1cnJlbnQgZGF0YSB0aGF0IGNyZWF0ZXMgY29uZnVzaW9uIGJldHdlZW4gY3Vpc2luZXMsIHNvIGxldCdzIGxlYXJuIGFib3V0IHRoaXMgcHJvYmxlbS4NCg0KMS4gIENyZWF0ZSBhIGZ1bmN0aW9uIGBjcmVhdGVfaW5ncmVkaWVudCgpYCBpbiBSIHRoYXQgcmV0dXJucyBhbiBpbmdyZWRpZW50IGRhdGFmcmFtZS4gVGhpcyBmdW5jdGlvbiB3aWxsIHN0YXJ0IGJ5IGRyb3BwaW5nIGFuIHVuaGVscGZ1bCBjb2x1bW4gYW5kIHNvcnQgdGhyb3VnaCBpbmdyZWRpZW50cyBieSB0aGVpciBjb3VudC4NCg0KVGhlIGJhc2ljIHN0cnVjdHVyZSBvZiBhIGZ1bmN0aW9uIGluIFIgaXM6DQoNCmBteUZ1bmN0aW9uIDwtIGZ1bmN0aW9uKGFyZ2xpc3Qpe2ANCg0KKipgLi4uYCoqDQoNCioqYHJldHVybmAqKmAodmFsdWUpYA0KDQpgfWANCg0KQSB0aWR5IGludHJvZHVjdGlvbiB0byBSIGZ1bmN0aW9ucyBjYW4gYmUgZm91bmQgW2hlcmVdKGh0dHBzOi8vc2tpcm1lci5naXRodWIuaW8vcHJlc2VudGF0aW9ucy9mdW5jdGlvbnNfd2l0aF9yLmh0bWwjMSkuDQoNCkxldCdzIGdldCByaWdodCBpbnRvIGl0ISBXZSdsbCBtYWtlIHVzZSBvZiBbZHBseXIgdmVyYnNdKGh0dHBzOi8vZHBseXIudGlkeXZlcnNlLm9yZy8pIHdoaWNoIHdlIGhhdmUgYmVlbiBsZWFybmluZyBpbiBvdXIgcHJldmlvdXMgbGVzc29ucy4gQXMgYSByZWNhcDoNCg0KLSAgIGBkcGx5cjo6c2VsZWN0KClgOiBoZWxwIHlvdSBwaWNrIHdoaWNoICoqY29sdW1ucyoqIHRvIGtlZXAgb3IgZXhjbHVkZS4NCg0KLSAgIGBkcGx5cjo6cGl2b3RfbG9uZ2VyKClgOiBoZWxwcyB5b3UgdG8gImxlbmd0aGVuIiBkYXRhLCBpbmNyZWFzaW5nIHRoZSBudW1iZXIgb2Ygcm93cyBhbmQgZGVjcmVhc2luZyB0aGUgbnVtYmVyIG9mIGNvbHVtbnMuDQoNCi0gICBgZHBseXI6Omdyb3VwX2J5KClgIGFuZCBgZHBseXI6OnN1bW1hcmlzZSgpYDogaGVscHMgeW91IHRvIGZpbmQgZmluZCBzdW1tYXJ5IHN0YXRpc3RpY3MgZm9yIGRpZmZlcmVudCBncm91cHMsIGFuZCBwdXQgdGhlbSBpbiBhIG5pY2UgdGFibGUuDQoNCi0gICBgZHBseXI6OmZpbHRlcigpYDogY3JlYXRlcyBhIHN1YnNldCBvZiB0aGUgZGF0YSBvbmx5IGNvbnRhaW5pbmcgcm93cyB0aGF0IHNhdGlzZnkgeW91ciBjb25kaXRpb25zLg0KDQotICAgYGRwbHlyOjptdXRhdGUoKWA6IGhlbHBzIHlvdSB0byBjcmVhdGUgb3IgbW9kaWZ5IGNvbHVtbnMuDQoNCkNoZWNrIG91dCB0aGlzIFsqYXJ0Ki1maWxsZWQgbGVhcm5yIHR1dG9yaWFsXShodHRwczovL2FsbGlzb25ob3JzdC5zaGlueWFwcHMuaW8vZHBseXItbGVhcm5yLyNzZWN0aW9uLXdlbGNvbWUpIGJ5IEFsbGlzb24gSG9yc3QsIHRoYXQgaW50cm9kdWNlcyBzb21lIHVzZWZ1bCBkYXRhIHdyYW5nbGluZyBmdW5jdGlvbnMgaW4gZHBseXIgKihwYXJ0IG9mIHRoZSBUaWR5dmVyc2UpKg0KDQpgYGB7ciBjcmVhdGVfaW5ncmVkaWVudH0NCiMgQ3JlYXRlcyBhIGZ1bmN0aW9ucyB0aGF0IHJldHVybnMgdGhlIHRvcCBpbmdyZWRpZW50cyBieSBjbGFzcw0KDQpjcmVhdGVfaW5ncmVkaWVudCA8LSBmdW5jdGlvbihkZil7DQogIA0KICAjIERyb3AgdGhlIGlkIGNvbHVtbiB3aGljaCBpcyB0aGUgZmlyc3QgY29sdW0NCiAgaW5ncmVkaWVudF9kZiA9IGRmICU+JSBzZWxlY3QoLTEpICU+JSANCiAgIyBUcmFuc3Bvc2UgZGF0YSB0byBhIGxvbmcgZm9ybWF0DQogICAgcGl2b3RfbG9uZ2VyKCFjdWlzaW5lLCBuYW1lc190byA9ICJpbmdyZWRpZW50cyIsIHZhbHVlc190byA9ICJjb3VudCIpICU+JSANCiAgIyBGaW5kIHRoZSB0b3AgbW9zdCBpbmdyZWRpZW50cyBmb3IgYSBwYXJ0aWN1bGFyIGN1aXNpbmUNCiAgICBncm91cF9ieShpbmdyZWRpZW50cykgJT4lIA0KICAgIHN1bW1hcmlzZShuX2luc3RhbmNlcyA9IHN1bShjb3VudCkpICU+JSANCiAgICBmaWx0ZXIobl9pbnN0YW5jZXMgIT0gMCkgJT4lIA0KICAjIEFycmFuZ2UgYnkgZGVzY2VuZGluZyBvcmRlcg0KICAgIGFycmFuZ2UoZGVzYyhuX2luc3RhbmNlcykpICU+JSANCiAgICBtdXRhdGUoaW5ncmVkaWVudHMgPSBmYWN0b3IoaW5ncmVkaWVudHMpICU+JSBmY3RfaW5vcmRlcigpKQ0KICANCiAgDQogIHJldHVybihpbmdyZWRpZW50X2RmKQ0KfSAjIEVuZCBvZiBmdW5jdGlvbg0KDQpgYGANCg0KMi4gIE5vdyB3ZSBjYW4gdXNlIHRoZSBmdW5jdGlvbiB0byBnZXQgYW4gaWRlYSBvZiB0b3AgdGVuIG1vc3QgcG9wdWxhciBpbmdyZWRpZW50IGJ5IGN1aXNpbmUuIExldCdzIHRha2UgaXQgb3V0IGZvciBhIHNwaW4gd2l0aCBgdGhhaV9kZmANCg0KYGBge3IgdGhhaV9pbmdyZWRpZW50X2RmfQ0KIyBDYWxsIGNyZWF0ZV9pbmdyZWRpZW50IGFuZCBkaXNwbGF5IHBvcHVsYXIgaW5ncmVkaWVudHMNCnRoYWlfaW5ncmVkaWVudF9kZiA8LSBjcmVhdGVfaW5ncmVkaWVudChkZiA9IHRoYWlfZGYpDQoNCnRoYWlfaW5ncmVkaWVudF9kZiAlPiUgDQogIHNsaWNlX2hlYWQobiA9IDEwKQ0KDQpgYGANCg0KSW4gdGhlIHByZXZpb3VzIHNlY3Rpb24sIHdlIHVzZWQgYGdlb21fY29sKClgLCBsZXQncyBzZWUgaG93IHlvdSBjYW4gdXNlIGBnZW9tX2JhcmAgdG9vLCB0byBjcmVhdGUgYmFyIGNoYXJ0cy4gVXNlIGA/Z2VvbV9iYXJgIGZvciBmdXJ0aGVyIHJlYWRpbmcuDQoNCmBgYHtyIHRoYWlfY2hhcnR9DQojIE1ha2UgYSBiYXIgY2hhcnQgZm9yIHBvcHVsYXIgdGhhaSBjdWlzaW5lcw0KdGhhaV9pbmdyZWRpZW50X2RmICU+JSANCiAgc2xpY2VfaGVhZChuID0gMTApICU+JSANCiAgZ2dwbG90KGFlcyh4ID0gbl9pbnN0YW5jZXMsIHkgPSBpbmdyZWRpZW50cykpICsNCiAgZ2VvbV9iYXIoc3RhdCA9ICJpZGVudGl0eSIsIHdpZHRoID0gMC41LCBmaWxsID0gInN0ZWVsYmx1ZSIpICsNCiAgeGxhYigiIikgKyB5bGFiKCIiKQ0KDQpgYGANCg0KMy4gIExldCdzIGRvIHRoZSBzYW1lIGZvciB0aGUgSmFwYW5lc2UgZGF0YQ0KDQpgYGB7ciBqYXBhbmVzZV9pbmdyZWRpZW50X2RmfQ0KIyBHZXQgcG9wdWxhciBpbmdyZWRpZW50cyBmb3IgSmFwYW5lc2UgY3Vpc2luZXMgYW5kIG1ha2UgYmFyIGNoYXJ0DQpjcmVhdGVfaW5ncmVkaWVudChkZiA9IGphcGFuZXNlX2RmKSAlPiUgDQogIHNsaWNlX2hlYWQobiA9IDEwKSAlPiUNCiAgZ2dwbG90KGFlcyh4ID0gbl9pbnN0YW5jZXMsIHkgPSBpbmdyZWRpZW50cykpICsNCiAgZ2VvbV9iYXIoc3RhdCA9ICJpZGVudGl0eSIsIHdpZHRoID0gMC41LCBmaWxsID0gImRhcmtvcmFuZ2UiLCBhbHBoYSA9IDAuOCkgKw0KICB4bGFiKCIiKSArIHlsYWIoIiIpDQoNCg0KDQpgYGANCg0KNC4gIFdoYXQgYWJvdXQgdGhlIENoaW5lc2UgY3Vpc2luZXM/DQoNCmBgYHtyIGNoaW5lc2VfaW5ncmVkaWVudF9kZn0NCiMgR2V0IHBvcHVsYXIgaW5ncmVkaWVudHMgZm9yIENoaW5lc2UgY3Vpc2luZXMgYW5kIG1ha2UgYmFyIGNoYXJ0DQpjcmVhdGVfaW5ncmVkaWVudChkZiA9IGNoaW5lc2VfZGYpICU+JSANCiAgc2xpY2VfaGVhZChuID0gMTApICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSBuX2luc3RhbmNlcywgeSA9IGluZ3JlZGllbnRzKSkgKw0KICBnZW9tX2JhcihzdGF0ID0gImlkZW50aXR5Iiwgd2lkdGggPSAwLjUsIGZpbGwgPSAiY3lhbjQiLCBhbHBoYSA9IDAuOCkgKw0KICB4bGFiKCIiKSArIHlsYWIoIiIpDQoNCg0KYGBgDQoNCjUuICBMZXQncyB0YWtlIGEgbG9vayBhdCB0aGUgSW5kaWFuIGN1aXNpbmVzIPCfjLbvuI8uDQoNCmBgYHtyIGluZGlhbl9pbmdyZWRpZW50X2RmIH0NCiMgR2V0IHBvcHVsYXIgaW5ncmVkaWVudHMgZm9yIEluZGlhbiBjdWlzaW5lcyBhbmQgbWFrZSBiYXIgY2hhcnQNCmNyZWF0ZV9pbmdyZWRpZW50KGRmID0gaW5kaWFuX2RmKSAlPiUgDQogIHNsaWNlX2hlYWQobiA9IDEwKSAlPiUNCiAgZ2dwbG90KGFlcyh4ID0gbl9pbnN0YW5jZXMsIHkgPSBpbmdyZWRpZW50cykpICsNCiAgZ2VvbV9iYXIoc3RhdCA9ICJpZGVudGl0eSIsIHdpZHRoID0gMC41LCBmaWxsID0gIiMwNDFFNDJGRiIsIGFscGhhID0gMC44KSArDQogIHhsYWIoIiIpICsgeWxhYigiIikNCmBgYA0KDQo2LiAgRmluYWxseSwgcGxvdCB0aGUgS29yZWFuIGluZ3JlZGllbnRzLg0KDQpgYGB7ciBrb3JlYW5faW5ncmVkaWVudF9kZiB9DQojIEdldCBwb3B1bGFyIGluZ3JlZGllbnRzIGZvciBLb3JlYW4gY3Vpc2luZXMgYW5kIG1ha2UgYmFyIGNoYXJ0DQpjcmVhdGVfaW5ncmVkaWVudChkZiA9IGtvcmVhbl9kZikgJT4lIA0KICBzbGljZV9oZWFkKG4gPSAxMCkgJT4lDQogIGdncGxvdChhZXMoeCA9IG5faW5zdGFuY2VzLCB5ID0gaW5ncmVkaWVudHMpKSArDQogIGdlb21fYmFyKHN0YXQgPSAiaWRlbnRpdHkiLCB3aWR0aCA9IDAuNSwgZmlsbCA9ICIjODUyNDE5RkYiLCBhbHBoYSA9IDAuOCkgKw0KICB4bGFiKCIiKSArIHlsYWIoIiIpDQpgYGANCg0KNy4gIEZyb20gdGhlIGRhdGEgdmlzdWFsaXphdGlvbnMsIHdlIGNhbiBub3cgZHJvcCB0aGUgbW9zdCBjb21tb24gaW5ncmVkaWVudHMgdGhhdCBjcmVhdGUgY29uZnVzaW9uIGJldHdlZW4gZGlzdGluY3QgY3Vpc2luZXMsIHVzaW5nIGBkcGx5cjo6c2VsZWN0KClgLg0KDQpFdmVyeW9uZSBsb3ZlcyByaWNlLCBnYXJsaWMgYW5kIGdpbmdlciENCg0KYGBge3IgZGZfc2VsZWN0fQ0KIyBEcm9wIHJpY2UsIGdhcmxpYyBhbmQgZ2luZ2VyIGZyb20gb3VyIG9yaWdpbmFsIGRhdGEgc2V0DQpkZl9zZWxlY3QgPC0gZGYgJT4lIA0KICBzZWxlY3QoLWMoMSwgcmljZSwgZ2FybGljLCBnaW5nZXIpKQ0KDQojIERpc3BsYXkgbmV3IGRhdGEgc2V0DQpkZl9zZWxlY3QgJT4lIA0KICBzbGljZV9oZWFkKG4gPSA1KQ0KDQpgYGANCg0KIyMgUHJlcHJvY2Vzc2luZyBkYXRhIHVzaW5nIHJlY2lwZXMg8J+RqeKAjfCfjbPwn5Go4oCN8J+NsyAtIERlYWxpbmcgd2l0aCBpbWJhbGFuY2VkIGRhdGEg4pqW77iPDQoNCiFbQXJ0d29yayBieSBcQGFsbGlzb25faG9yc3RdKC4uLy4uL2ltYWdlcy9yZWNpcGVzLnBuZykNCg0KR2l2ZW4gdGhhdCB0aGlzIGxlc3NvbiBpcyBhYm91dCBjdWlzaW5lcywgd2UgaGF2ZSB0byBwdXQgYHJlY2lwZXNgIGludG8gY29udGV4dCAuDQoNClRpZHltb2RlbHMgcHJvdmlkZXMgeWV0IGFub3RoZXIgbmVhdCBwYWNrYWdlOiBgcmVjaXBlc2AtIGEgcGFja2FnZSBmb3IgcHJlcHJvY2Vzc2luZyBkYXRhLg0KDQpOb3cgd2UgYXJlIG9uIHRoZSBzYW1lIHBhZ2Ug8J+YhS4NCg0KTGV0J3MgdGFrZSBhIGxvb2sgYXQgdGhlIGRpc3RyaWJ1dGlvbiBvZiBvdXIgY3Vpc2luZXMgYWdhaW4uDQoNCmBgYHtyIGRmX3NlbGVjdF9ufQ0KIyBEaXN0cmlidXRpb24gb2YgY3Vpc2luZXMNCm9sZF9sYWJlbF9jb3VudCA8LSBkZl9zZWxlY3QgJT4lIA0KICBjb3VudChjdWlzaW5lKSAlPiUgDQogIGFycmFuZ2UoZGVzYyhuKSkNCg0Kb2xkX2xhYmVsX2NvdW50DQpgYGANCg0KQXMgeW91IGNhbiBzZWUsIHRoZXJlIGlzIHF1aXRlIGFuIHVuZXF1YWwgZGlzdHJpYnV0aW9uIGluIHRoZSBudW1iZXIgb2YgY3Vpc2luZXMuIEtvcmVhbiBjdWlzaW5lcyBhcmUgYWxtb3N0IDMgdGltZXMgVGhhaSBjdWlzaW5lcy4gSW1iYWxhbmNlZCBkYXRhIG9mdGVuIGhhcyBuZWdhdGl2ZSBlZmZlY3RzIG9uIHRoZSBtb2RlbCBwZXJmb3JtYW5jZS4gVGhpbmsgYWJvdXQgYSBiaW5hcnkgY2xhc3NpZmljYXRpb24uIElmIG1vc3Qgb2YgeW91ciBkYXRhIGlzIG9uZSBjbGFzcywgYSBNTCBtb2RlbCBpcyBnb2luZyB0byBwcmVkaWN0IHRoYXQgY2xhc3MgbW9yZSBmcmVxdWVudGx5LCBqdXN0IGJlY2F1c2UgdGhlcmUgaXMgbW9yZSBkYXRhIGZvciBpdC4gQmFsYW5jaW5nIHRoZSBkYXRhIHRha2VzIGFueSBza2V3ZWQgZGF0YSBhbmQgaGVscHMgcmVtb3ZlIHRoaXMgaW1iYWxhbmNlLiBNYW55IG1vZGVscyBwZXJmb3JtIGJlc3Qgd2hlbiB0aGUgbnVtYmVyIG9mIG9ic2VydmF0aW9ucyBpcyBlcXVhbCBhbmQsIHRodXMsIHRlbmQgdG8gc3RydWdnbGUgd2l0aCB1bmJhbGFuY2VkIGRhdGEuDQoNClRoZXJlIGFyZSBtYWpvcmx5IHR3byB3YXlzIG9mIGRlYWxpbmcgd2l0aCBpbWJhbGFuY2VkIGRhdGEgc2V0czoNCg0KLSAgIGFkZGluZyBvYnNlcnZhdGlvbnMgdG8gdGhlIG1pbm9yaXR5IGNsYXNzOiBgT3Zlci1zYW1wbGluZ2AgZS5nIHVzaW5nIGEgU01PVEUgYWxnb3JpdGhtDQoNCi0gICByZW1vdmluZyBvYnNlcnZhdGlvbnMgZnJvbSBtYWpvcml0eSBjbGFzczogYFVuZGVyLXNhbXBsaW5nYA0KDQpMZXQncyBub3cgZGVtb25zdHJhdGUgaG93IHRvIGRlYWwgd2l0aCBpbWJhbGFuY2VkIGRhdGEgc2V0cyB1c2luZyBhIGByZWNpcGVgLiBBIHJlY2lwZSBjYW4gYmUgdGhvdWdodCBvZiBhcyBhIGJsdWVwcmludCB0aGF0IGRlc2NyaWJlcyB3aGF0IHN0ZXBzIHNob3VsZCBiZSBhcHBsaWVkIHRvIGEgZGF0YSBzZXQgaW4gb3JkZXIgdG8gZ2V0IGl0IHJlYWR5IGZvciBkYXRhIGFuYWx5c2lzLg0KDQpgYGB7ciByZWNpcGV9DQojIExvYWQgdGhlbWlzIHBhY2thZ2UgZm9yIGRlYWxpbmcgd2l0aCBpbWJhbGFuY2VkIGRhdGENCmxpYnJhcnkodGhlbWlzKQ0KDQojIENyZWF0ZSBhIHJlY2lwZSBmb3IgcHJlcHJvY2Vzc2luZyBkYXRhDQpjdWlzaW5lc19yZWNpcGUgPC0gcmVjaXBlKGN1aXNpbmUgfiAuLCBkYXRhID0gZGZfc2VsZWN0KSAlPiUgDQogIHN0ZXBfc21vdGUoY3Vpc2luZSkNCg0KY3Vpc2luZXNfcmVjaXBlDQpgYGANCg0KTGV0J3MgYnJlYWsgZG93biBvdXIgcHJlcHJvY2Vzc2luZyBzdGVwcy4NCg0KLSAgIFRoZSBjYWxsIHRvIGByZWNpcGUoKWAgd2l0aCBhIGZvcm11bGEgdGVsbHMgdGhlIHJlY2lwZSB0aGUgKnJvbGVzKiBvZiB0aGUgdmFyaWFibGVzIHVzaW5nIGBkZl9zZWxlY3RgIGRhdGEgYXMgdGhlIHJlZmVyZW5jZS4gRm9yIGluc3RhbmNlIHRoZSBgY3Vpc2luZWAgY29sdW1uIGhhcyBiZWVuIGFzc2lnbmVkIGFuIGBvdXRjb21lYCByb2xlIHdoaWxlIHRoZSByZXN0IG9mIHRoZSBjb2x1bW5zIGhhdmUgYmVlbiBhc3NpZ25lZCBhIGBwcmVkaWN0b3JgIHJvbGUuDQoNCi0gICBbYHN0ZXBfc21vdGUoY3Vpc2luZSlgXShodHRwczovL3RoZW1pcy50aWR5bW9kZWxzLm9yZy9yZWZlcmVuY2Uvc3RlcF9zbW90ZS5odG1sKSBjcmVhdGVzIGEgKnNwZWNpZmljYXRpb24qIG9mIGEgcmVjaXBlIHN0ZXAgdGhhdCBzeW50aGV0aWNhbGx5IGdlbmVyYXRlcyBuZXcgZXhhbXBsZXMgb2YgdGhlIG1pbm9yaXR5IGNsYXNzIHVzaW5nIG5lYXJlc3QgbmVpZ2hib3JzIG9mIHRoZXNlIGNhc2VzLg0KDQpOb3csIGlmIHdlIHdhbnRlZCB0byBzZWUgdGhlIHByZXByb2Nlc3NlZCBkYXRhLCB3ZSdkIGhhdmUgdG8gWyoqYHByZXAoKWAqKl0oaHR0cHM6Ly9yZWNpcGVzLnRpZHltb2RlbHMub3JnL3JlZmVyZW5jZS9wcmVwLmh0bWwpIGFuZCBbKipgYmFrZSgpYCoqXShodHRwczovL3JlY2lwZXMudGlkeW1vZGVscy5vcmcvcmVmZXJlbmNlL2Jha2UuaHRtbCkgb3VyIHJlY2lwZS4NCg0KYHByZXAoKWA6IGVzdGltYXRlcyB0aGUgcmVxdWlyZWQgcGFyYW1ldGVycyBmcm9tIGEgdHJhaW5pbmcgc2V0IHRoYXQgY2FuIGJlIGxhdGVyIGFwcGxpZWQgdG8gb3RoZXIgZGF0YSBzZXRzLg0KDQpgYmFrZSgpYDogdGFrZXMgYSBwcmVwcGVkIHJlY2lwZSBhbmQgYXBwbGllcyB0aGUgb3BlcmF0aW9ucyB0byBhbnkgZGF0YSBzZXQuDQoNCmBgYHtyIHByZXBfYmFrZX0NCiMgUHJlcCBhbmQgYmFrZSB0aGUgcmVjaXBlDQpwcmVwcm9jZXNzZWRfZGYgPC0gY3Vpc2luZXNfcmVjaXBlICU+JSANCiAgcHJlcCgpICU+JSANCiAgYmFrZShuZXdfZGF0YSA9IE5VTEwpICU+JSANCiAgcmVsb2NhdGUoY3Vpc2luZSkNCg0KIyBEaXNwbGF5IGRhdGENCnByZXByb2Nlc3NlZF9kZiAlPiUgDQogIHNsaWNlX2hlYWQobiA9IDUpDQoNCiMgUXVpY2sgc3VtbWFyeSBzdGF0cw0KcHJlcHJvY2Vzc2VkX2RmICU+JSANCiAgaW50cm9kdWNlKCkNCg0KYGBgDQoNCkxldCdzIG5vdyBjaGVjayB0aGUgZGlzdHJpYnV0aW9uIG9mIG91ciBjdWlzaW5lcyBhbmQgY29tcGFyZSB0aGVtIHdpdGggdGhlIGltYmFsYW5jZWQgZGF0YS4NCg0KYGBge3IgcHJlcF9jdWlzaW5lc30NCiMgRGlzdHJpYnV0aW9uIG9mIGN1aXNpbmVzDQpuZXdfbGFiZWxfY291bnQgPC0gcHJlcHJvY2Vzc2VkX2RmICU+JSANCiAgY291bnQoY3Vpc2luZSkgJT4lIA0KICBhcnJhbmdlKGRlc2MobikpDQoNCmxpc3QobmV3X2xhYmVsX2NvdW50ID0gbmV3X2xhYmVsX2NvdW50LA0KICAgICBvbGRfbGFiZWxfY291bnQgPSBvbGRfbGFiZWxfY291bnQpDQoNCmBgYA0KDQpZdW0hIFRoZSBkYXRhIGlzIG5pY2UgYW5kIGNsZWFuLCBiYWxhbmNlZCwgYW5kIHZlcnkgZGVsaWNpb3VzIPCfmIshDQoNCj4gTm9ybWFsbHksIGEgcmVjaXBlIGlzIHVzdWFsbHkgdXNlZCBhcyBhIHByZXByb2Nlc3NvciBmb3IgbW9kZWxsaW5nIHdoZXJlIGl0IGRlZmluZXMgd2hhdCBzdGVwcyBzaG91bGQgYmUgYXBwbGllZCB0byBhIGRhdGEgc2V0IGluIG9yZGVyIHRvIGdldCBpdCByZWFkeSBmb3IgbW9kZWxsaW5nLiBJbiB0aGF0IGNhc2UsIGEgYHdvcmtmbG93KClgIGlzIHR5cGljYWxseSB1c2VkIChhcyB3ZSBoYXZlIGFscmVhZHkgc2VlbiBpbiBvdXIgcHJldmlvdXMgbGVzc29ucykgaW5zdGVhZCBvZiBtYW51YWxseSBlc3RpbWF0aW5nIGEgcmVjaXBlDQo+DQo+IEFzIHN1Y2gsIHlvdSBkb24ndCB0eXBpY2FsbHkgbmVlZCB0byAqKmBwcmVwKClgKiogYW5kICoqYGJha2UoKWAqKiByZWNpcGVzIHdoZW4geW91IHVzZSB0aWR5bW9kZWxzLCBidXQgdGhleSBhcmUgaGVscGZ1bCBmdW5jdGlvbnMgdG8gaGF2ZSBpbiB5b3VyIHRvb2xraXQgZm9yIGNvbmZpcm1pbmcgdGhhdCByZWNpcGVzIGFyZSBkb2luZyB3aGF0IHlvdSBleHBlY3QgbGlrZSBpbiBvdXIgY2FzZS4NCj4NCj4gV2hlbiB5b3UgKipgYmFrZSgpYCoqIGEgcHJlcHBlZCByZWNpcGUgd2l0aCAqKmBuZXdfZGF0YSA9IE5VTExgKiosIHlvdSBnZXQgdGhlIGRhdGEgdGhhdCB5b3UgcHJvdmlkZWQgd2hlbiBkZWZpbmluZyB0aGUgcmVjaXBlIGJhY2ssIGJ1dCBoYXZpbmcgdW5kZXJnb25lIHRoZSBwcmVwcm9jZXNzaW5nIHN0ZXBzLg0KDQpMZXQncyBub3cgc2F2ZSBhIGNvcHkgb2YgdGhpcyBkYXRhIGZvciB1c2UgaW4gZnV0dXJlIGxlc3NvbnM6DQoNCmBgYHtyIHNhdmVfcHJlcHJvY19kYXRhfQ0KIyBTYXZlIHByZXByb2Nlc3NlZCBkYXRhDQp3cml0ZV9jc3YocHJlcHJvY2Vzc2VkX2RmLCAiLi4vLi4vLi4vZGF0YS9jbGVhbmVkX2N1aXNpbmVzX1IuY3N2IikNCg0KYGBgDQoNClRoaXMgZnJlc2ggQ1NWIGNhbiBub3cgYmUgZm91bmQgaW4gdGhlIHJvb3QgZGF0YSBmb2xkZXIuDQoNCioq8J+agENoYWxsZW5nZSoqDQoNClRoaXMgY3VycmljdWx1bSBjb250YWlucyBzZXZlcmFsIGludGVyZXN0aW5nIGRhdGFzZXRzLiBEaWcgdGhyb3VnaCB0aGUgYGRhdGFgIGZvbGRlcnMgYW5kIHNlZSBpZiBhbnkgY29udGFpbiBkYXRhc2V0cyB0aGF0IHdvdWxkIGJlIGFwcHJvcHJpYXRlIGZvciBiaW5hcnkgb3IgbXVsdGktY2xhc3MgY2xhc3NpZmljYXRpb24/IFdoYXQgcXVlc3Rpb25zIHdvdWxkIHlvdSBhc2sgb2YgdGhpcyBkYXRhc2V0Pw0KDQojIyBbKipQb3N0LWxlY3R1cmUgcXVpeioqXShodHRwczovL2dyYXktc2FuZC0wN2ExMGY0MDMuMS5henVyZXN0YXRpY2FwcHMubmV0L3F1aXovMjAvKQ0KDQojIyAqKlJldmlldyAmIFNlbGYgU3R1ZHkqKg0KDQotICAgQ2hlY2sgb3V0IFtwYWNrYWdlIHRoZW1pc10oaHR0cHM6Ly9naXRodWIuY29tL3RpZHltb2RlbHMvdGhlbWlzKS4gV2hhdCBvdGhlciB0ZWNobmlxdWVzIGNvdWxkIHdlIHVzZSB0byBkZWFsIHdpdGggaW1iYWxhbmNlZCBkYXRhPw0KDQotICAgVGlkeSBtb2RlbHMgW3JlZmVyZW5jZSB3ZWJzaXRlXShodHRwczovL3d3dy50aWR5bW9kZWxzLm9yZy9zdGFydC8pLg0KDQotICAgSC4gV2lja2hhbSBhbmQgRy4gR3JvbGVtdW5kLCBbKlIgZm9yIERhdGEgU2NpZW5jZTogVmlzdWFsaXplLCBNb2RlbCwgVHJhbnNmb3JtLCBUaWR5LCBhbmQgSW1wb3J0IERhdGEqXShodHRwczovL3I0ZHMuaGFkLmNvLm56LykuDQoNCiMjIyMgVEhBTksgWU9VIFRPOg0KDQpbYEFsbGlzb24gSG9yc3RgXShodHRwczovL3R3aXR0ZXIuY29tL2FsbGlzb25faG9yc3QvKSBmb3IgY3JlYXRpbmcgdGhlIGFtYXppbmcgaWxsdXN0cmF0aW9ucyB0aGF0IG1ha2UgUiBtb3JlIHdlbGNvbWluZyBhbmQgZW5nYWdpbmcuIEZpbmQgbW9yZSBpbGx1c3RyYXRpb25zIGF0IGhlciBbZ2FsbGVyeV0oaHR0cHM6Ly93d3cuZ29vZ2xlLmNvbS91cmw/cT1odHRwczovL2dpdGh1Yi5jb20vYWxsaXNvbmhvcnN0L3N0YXRzLWlsbHVzdHJhdGlvbnMmc2E9RCZzb3VyY2U9ZWRpdG9ycyZ1c3Q9MTYyNjM4MDc3MjUzMDAwMCZ1c2c9QU92VmF3M3pjZnlDaXpGUVpwa1NMenhpaVFFTSkuDQoNCltDYXNzaWUgQnJldml1XShodHRwczovL3d3dy50d2l0dGVyLmNvbS9jYXNzaWV2aWV3KSBhbmQgW0plbiBMb29wZXJdKGh0dHBzOi8vd3d3LnR3aXR0ZXIuY29tL2plbmxvb3BlcikgZm9yIGNyZWF0aW5nIHRoZSBvcmlnaW5hbCBQeXRob24gdmVyc2lvbiBvZiB0aGlzIG1vZHVsZSDimaXvuI8NCg0KIVtBcnR3b3JrIGJ5IFxAYWxsaXNvbl9ob3JzdF0oLi4vLi4vaW1hZ2VzL3JfbGVhcm5lcnNfc20uanBlZykNCg==