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!

Celebrate pan-Asian cuisines in these lessons! Image by Jen Looper

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.

Binary vs. multiclass problems for classification algorithms to handle. Infographic by Jen Looper

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

  1. 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.

  1. 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.

Artwork by @allison_horst

# 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.

  1. 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
  1. 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("")

  1. 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("")

  1. 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("")

  1. 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("")

  1. 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("")

  1. 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 ⚖️

Artwork by @allison_horst

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:

  • adding observations to the minority class: Over-sampling e.g using a SMOTE algorithm

  • removing observations from majority class: Under-sampling

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?

Post-lecture quiz

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 ♥️

Artwork by @allison_horst

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==