Copied and modified from https://rpubs.com/yongks/instacart8

1 Introduction

Instacart is an app for on-demand grocery shopping with same-day delivery service. Instacart uses a crowdsourced marketplace model, akin to that of Uber or Lyft.

The Instacart shopping process is as follows. First, an app user places their grocery order through the app. Then, a locally crowdsourced “shopper” is notified of the order, goes to a nearby store, buys the groceries, and delivers them to the user.

There are three ways that Instacart generates revenue: delivery fees, membership fees, and mark-ups on in-store prices.

1.1 Research Goal & Objective

The main objective of the competition is to predict what will the user will buy in the next order, given all data of prior orders.

2 Market Basket Analysis

Market Basket Analysis (MBA) is a process that looks for relationships among entities and objects that frequently appear together, such as the collection of items in a shopper’s cart. For the purposes of customer centricity, market basket analysis examines collections of items to identify affinities that are relevant within the different contexts of the customer touch points. Some examples include:

Product placement—Identifying products that may often be purchased together and arranging the placement of those close by to encourage the purchaser to buy both items. That placement can be physical, such as in the arrangement of products on shelves in a brick and mortar location, or virtual, such as in a print catalog or on an e-commerce site.
Point-of-Sale—Companies may use the affinity grouping of multiple products as an indication that customers may be predisposed to buying certain sets of products at the same time. This enables the presentation of items for cross-selling, or may suggest that customers may be willing to buy more items when certain products are bundled together.
Customer retention—When customers contact a business to sever a relationship, a company representative may use market basket analysis to determine the right incentives to offer in order to retain the customer’s business.

MBA is one of the key techniques used by the large retailers that uncovers associations between items by looking for combinations of items that occur together frequently in transactions. In other words, it allows the retailers to identify relationships between the items that people buy.

Association Rules is widely used to analyze retail basket or transaction data, is intended to identify strong rules discovered in transaction data using some measures of interestingness, based on the concept of strong rules.

3 Terminology of Association Rules

Assume there are 100 transactions on a retail shop. * 10 out of them bought milk, 8 bought butter and 6 bought both of them (milk & butter). * For example, our interesting is how it like if someone bought milk also bought butter: + bought milk => bought butter

First, we need to know the terminology that used in MBA.

Itemset : set of items that customer bought in all transactions.
Support : proportion of transaction that contain an itemsets of interest. \[Supp(X \Rightarrow Y) = \frac{frq(| X \cup Y |)}{N}\] For example, our interest is product Milk & Butter \[ \begin{aligned} Supp(Milk \Rightarrow Butter) &= P(Milk, Butter) \\ &= \frac{frq(Milk, Butter)}{N}\\ &= \frac{6}{100}\\ &= 0.06\\ \end{aligned} \]

The minimum support of the rule is defined as the minimum number of transactions that include both the antecedent and consequent parts in order to qualify to be part of frequent item set. The default minimum support would be 10% of the total number of transactions taken for analysis.
Confidence : conditional probability that if a customer purchases X, they will purchases Y. It determines the operational usefulness of a rule. Transactions with confidence with more than 50% will be selected. Higher the confidence , stronger the rule is. \[Conf(X, Y) = \frac{Supp(X,Y)}{P(Y)}\] Confidence for Milk & Butter is, where \[P(Butter) = \frac{frq(Butter)}{N} = \frac{8}{100} = 0.08\] Then, \[ \begin{aligned} Conf(Milk \Rightarrow Butter) &= \frac{Supp(Milk \Rightarrow Butter)}{P(Butter)}\\ &= \frac{0.06}{0.08}\\ &= 0.75 \end{aligned} \]
The minimum confidence of the rule is defined as the minimum number of transaction that has consequent will also have antecedent. The default minimum confidence would be 50%.
Lift : ratio of support of X occuring together with Y divided by the probability that X and Y occur if they are independet. \[ \begin{aligned} Lift(X,Y) &= \frac{Supp(X,Y)}{P(X,Y)},& P(X,Y) = P(X)P(Y)\\ &= \frac{Supp(X,Y)}{P(X)P(Y)}&\\ &= \frac{Supp(X,Y)}{P(Y)}\frac{1}{P(X)}\\ &= Conf(X,Y)\frac{1}{P(X)}\\ &= \frac{Conf(X,Y)}{P(X)} \end{aligned} \] Now $Lift(Milk, Butter) = ?$ \[P(Milk) = \frac{frq(Milk)}{N} = \frac{10}{100} = 0.01\] So, \[ \begin{aligned} Lift(Milk, Butter) &= \frac{Conf(Milk, BUtter)}{P(Milk)}\\ &= \frac{0.75}{0.10}\\ &= 7.5 \end{aligned} \]

Note: this example is extremely small. In practice, a rule needs a support of hundreds transactions before it can be considered statistically significant, and datasets often contain thousands or millions of transactions.

Ok, enough for the theory, let’s get to the code.

4 Dataset Preparation

4.1 Data Source

Last year, Instacart released a public dataset, “The Instacart Online Grocery Shopping Dataset 2017”. The dataset contains over 3 million anonymized grocery orders from more than 200,000 Instacart users. This analysis will make use of this datasets.

Data source can be downloaded here: https://www.kaggle.com/c/instacart-market-basket-analysis/data

4.2 R Libraries Used

Here are the R libraries used in this analysis.

rr library(knitr) # web widget library(tidyverse) # data manipulation library(data.table) # fast file reading library(caret) # rocr analysis library(ROCR) # rocr analysis library(kableExtra) # nice table html formating library(gridExtra) # arranging ggplot in grid

4.3 Import Datasets

rr # setwd(‘./data’) aisles <- fread(‘data/aisles.csv’, stringsAsFactors = TRUE) departments <- fread(‘data/departments.csv’, stringsAsFactors = TRUE) products <- fread(‘data/products.csv’, stringsAsFactors = TRUE) orders <- fread(‘data/orders.csv’, stringsAsFactors = TRUE) order_products_train <- fread(’data/order_products__train.csv’) order_products_prior <- fread(’data/order_products__prior.csv’)

4.4 Data Dictionary

The dataset for this competition is a relational set of files describing customers’ orders over time. They are anonymized and contains a sample of over 3 million grocery orders from more than 200,000 Instacart users. For each user, Instacart provided between 4 and 100 of their orders, with the sequence of products purchased in each order, the week and hour of day the order was placed, and a relative measure of time between orders.

Total six datasets were imported. Follwing section will explore each datasets in further detail. These datasets were sourced from an existing Kaggle competition.

orders (3.4m rows, 206k users):

order_id: order identifier
user_id: customer identifier
eval_set: which evaluation set this order belongs in (see SET described below)
order_number: the order sequence number for this user (1 = first, n = nth)
order_dow: the day of the week the order was placed on
order_hour_of_day: the hour of the day the order was placed on
days_since_prior: days since the last order, capped at 30 (with NAs for order_number = 1)

products (50k rows):

product_id: product identifier
product_name: name of the product
aisle_id: foreign key
department_id: foreign key

aisles (134 rows):

aisle_id: aisle identifier
aisle: the name of the aisle

deptartments (21 rows):

department_id: department identifier
department: the name of the department

order_products__SET (30m+ rows):

order_id: foreign key
product_id: foreign key
add_to_cart_order: order in which each product was added to cart
reordered: 1 if this product has been ordered by this user in the past, 0 otherwise

where SET is one of the four following evaluation sets (eval_set in orders):

"prior": orders prior to that users most recent order (~3.2m orders)
"train": training data supplied to participants (~131k orders)
"test": test data reserved for machine learning competitions (~75k orders)

4.5 Understanding Datasets

4.5.1 Aisles

There are 134 aisles in this dataset. Here are few sample names of the ailes.

rr paste(sort(head(aisles$aisle)), collapse=‘,’)

4.5.2 Departments

There are 21 departments in this dataset.Names of all deparments are listed below in aphabetically ordered.

rr paste(sort(departments$department), collapse = ‘,’)

4.5.3 Products

There are 49,688 products in the catalogue within 134 aisles and 21 departments.

Sample products are as below.

rr products %>% head %>% kable() %>% kable_styling(bootstrap_options = c(, ))

4.5.4 Departments And Its Relevant Products

Products dataframe is related to Deparments.

We shall see sample of 3 products for few deparments.

rr departments %>% left_join(products) %>% select(department, product_name) %>% group_by(department) %>% sample_n(3) %>% summarise(three_examples_product = paste(product_name, collapse = ’ / ’)) %>% sample_n(5) %>% kable() %>% kable_styling(bootstrap_options = c(, ))

4.5.5 Aisles And Its Relevant Products

Products dataframe is also related to aisles. Each aisle relates to multiple products. By joining both aisles and products dataframe, we have an idea what type of prodcuts for each ailes.

Example below shows 3 samples products of for few aisles.

rr aisles %>% left_join(products) %>% select(aisle, product_name) %>%
group_by(aisle) %>% sample_n(3) %>% summarise(three_examples_product = paste(product_name, collapse = ’ || ’)) %>% sample_n(5) %>% kable() %>% kable_styling(bootstrap_options = c(, ))

4.5.6 Orders

There are over 3 millions observations in orders dataset. Each row represent an unique order.

4.5.6.1 Train Eval_Set

Let’s analyse the construct of one user. For example, user_id 1 had made 10 prior orders (order number from 1 to 10), last order is a train (eval_set). Note that the first order (order_number 1) does not have value for day_since_prior_order, as it is the first order without prior records.

This also means <user_id, product_id> made up the key for prediction.

rr orders %>% filter(user_id == 1) %>% kable() %>% kable_styling(bootstrap_options = c(, ))

4.5.6.2 Test Eval_Set

Let’s analyse another construct of orders. User_id 3 had made 12 orders before the final order labeled as test (eval_set) order. From the data we know that order_number is being recycled for each user.

Instacart did not provide us the basket content for test order. This is in fact the target for prediction.

rr orders %>% filter(user_id == 3) %>% kable() %>% kable_styling(bootstrap_options = c(, ))

4.5.7 Order_Product

Each order contain multiple products purchased by user. Instacart had cleanly categorized the orders into ‘train’ and ‘prior’ in SINGLE order dataset.

However, the detail of each orders are splitted into two datsets:
- order_product_train: contain only detail product items of last order
- order_product_prior: contain detail product items of all prior orders

4.5.8 Order_Product_Train

order_product_train/prior dataframe tells us which products were purchased at each order; for both train and prior order.

For example, we know user_id 1 in the LAST ORDER (order_id 1187899) purchased 10 unique products by quering order_product_train with the relevant order_id.

rr order_products_train %>% filter (order_id == 1187899) %>% kable() %>% kable_styling(bootstrap_options = c(, ))

4.5.9 Order_Product_Train_Prior

Similary, detail items for a PRIOR ORDER (example order_id: 2550362) can be retireved by quering different dataset order_product_prior.

rr order_products_prior %>% filter(order_id == 2550362) %>% kable() %>% kable_styling(bootstrap_options = c(, ))

4.5.10 Users

Ther is no dedicated dataframe for users. However, we can derive number of unique users from order dataframe. By grouping the user_id and eval_set column, we found that there are 75,000 test users, 131,209 train users.

rr orders %>% filter(eval_set %in% c(‘train’, ‘test’) ) %>% count(eval_set) %>% mutate(percentage = n/sum(n)) %>% kable() %>% kable_styling(bootstrap_options = c(, ))

5 Exploratory Data Analysis

In this section, we shall try to understand the buying behaviour by asking some interesting quesitons.

What usually does people buy, and which one they usually reorder
When do they buy (day and time)? Is there a buying trend and does it influence what they buy ?

To reduce our coding steps, we construct a reusable dataframe combining all details from orders and its products. This dataframe will contain rows for prior orders and products only (excluding last order which is labeled as train).

rr users_orders_products_ <- orders %>% inner_join(order_products_prior) %>% # inner_join with prior table will filter out train orders left_join(products) %>% left_join(aisles) %>% left_join(departments) %>% arrange(user_id, order_number) %>% select(user_id, order_id, order_number, order_dow, order_hour_of_day, days_since_prior_order, product_id, product_name, reordered, add_to_cart_order, department_id, aisle_id, department, aisle)

5.1 Orders

5.1.1 How Many Orders ?

Most users made few orders. The number of orders a users made decrease significally along the order numbers. Maximum orders any users had made is 99.

rr tmp <- users_orders_products_ %>% group_by(user_id) %>% summarize(n_orders = max(order_number))

tmp %>% ggplot(aes(x = as.factor(n_orders))) + geom_bar() + labs(y = ‘Count of Users’, x = ‘Number of Orders Made By Users’) + theme( axis.text.x = element_text (size = 6.0, angle = (90), hjust = 1, vjust = 0.5) )

5.1.2 How Soon Until Next Order ?

It is very obvious that most users made their orders weekly (every 7 days) and monthly (every 30 days). See the peak of day 7 and day 30 in the chart below.

rr tmp <- users_orders_products_ %>% filter(order_number > 1) %>% # days_since_prior is NA for first order, need to filter out group_by(order_id) %>% summarize(n_orders = max(days_since_prior_order))

tmp %>% ggplot(aes(x = as.factor(n_orders))) + geom_bar() + labs(y = ‘Count of Orders’, x = ‘Days Since Prior For Each Order’)

5.2 Orders_Products

5.2.1 Most Popular Products Sold

We know that banana are the most popular products. The number of orders varies greatly for different products. Illustration below uses shows sample of only 30 top products. Notice however the varience is not obvious outside top 10 products.

rr tmp <- order_products_train %>% left_join(products) %>% group_by(product_name) %>% summarize(count = n()) %>% top_n(n = 30, wt = count) %>%
mutate(percentage = count/sum(count))

p1 <- tmp %>% ggplot(aes(x = reorder(product_name, count), y = percentage)) +
geom_col() + labs(title = ‘Products Top 30’, y = ‘Percentage of Orders’) + theme ( axis.text.x=element_text(angle=90, hjust=1, vjust=0.5), axis.title.x = element_blank())

p2 <- tmp %>% ggplot(aes(x = ’‘, y = percentage)) + labs(title = ’Products Top 30’, y = ‘percentage.of.orders’, x = ‘Products’) + geom_boxplot()

grid.arrange(p1, p2, ncol = 2)

5.2.2 Most Popular Department Sold

Certain departmens are clearly more popular, like produce and dairy eggs. Both deparments combined contributed to more than 40% of total orders.

rr tmp <- users_orders_products_ %>% group_by(department) %>% summarize(count = n()) %>% mutate(percentage = count/sum(count))

p1 <- tmp %>% ggplot (aes(x = reorder(department, count), y = percentage)) +
geom_col() + labs(title = ‘Departments’, y = ‘Percentage of Orders’) + theme ( axis.text.x = element_text(angle = 90, hjust = 1, vjust = 0.5), axis.title.x = element_blank())

p2 <- tmp %>% ggplot(aes(x = ’‘, y = percentage )) + labs(title = ’Departments’, y = ‘percentage.of.orders’, x = ‘Departments’) + geom_boxplot()

grid.arrange(p1, p2, ncol = 2)

5.2.3 Most Popular Aisles Sold

We looked into the buying trend of product by aisles and notice that certain aisle like vegetables and fruits contributes to almost 30% of total orders. Chart below shows top 30 aisles.

rr tmp <- users_orders_products_ %>% group_by(aisle) %>% summarize(count = n()) %>% top_n(n = 30, wt = count) %>%
mutate(percentage = count/sum(count))

p1 <- tmp %>% ggplot(aes(x = reorder(aisle, count), y = percentage)) +
geom_col() + labs(title = ‘Aisles Top 30’, x = ‘Aisles’, y = ‘Percentage of Orders’) + theme(axis.text.x=element_text(angle = 90, hjust = 1, vjust = 0.5), axis.title.x = element_blank())

p2 <- tmp %>% ggplot(aes(x = ’‘, y = percentage )) + geom_boxplot() + labs(title = ’Aisles Top 30’, y = ‘percentage.of.orders’, x = ‘Aisles’)

grid.arrange(p1, p2, ncol = 2)

5.2.4 Products Ordered Day Pattern

We can see that both Day 0 and Day 1 stands out to be the most busy shopping day for instacart. This means that day of order made may influence the basket size.

rr users_orders_products_ %>% group_by(order_dow) %>% summarize(count = n()) %>% mutate(percentage = count/sum(count)) %>% ggplot(aes(x = as.factor(order_dow), y = percentage, fill = as.factor(order_dow))) + geom_col() + labs(title = ‘Daily Orders’, y = ‘Percentage of Orders’)

When we zoom into daily orders, we notice that top ten products contributes between 7% to 8% of daily orders. It is interesting to see that Limes are part of top ten for Day 0 and Day 6, but not other days. Whereas Organic Whole Milk doesn’t make it to top ten for Day 0. Organic Respberries does not make it to top 10 of Day 6. This means that there is a chance of predictability based on the day order is made.

rr users_orders_products_%>% group_by(order_dow, product_name) %>% summarize(n = n()) %>% mutate(percentage = n/sum(n)) %>% top_n(10, wt = n) %>% ggplot(aes(x = as.factor(order_dow), y = percentage, fill = product_name)) + geom_col() + labs(y = ‘Proprtion of Orders In A Day’, title = ‘Daily Top 10 Products Ordered’) + theme(legend.position = , legend.direction = )

5.2.5 Products Ordered Hour Pattern

Morning to afternoon are the peak shopping hours for instacart customers. The hour order made influences basket size.

rr users_orders_products_ %>% group_by(order_hour_of_day) %>% summarize(count = n()) %>% mutate(percentage = count/sum(count)) %>% ggplot(aes(x = as.factor(order_hour_of_day), y = percentage)) + geom_col() + labs(y = ‘Percentage of Orders’, title = ‘Hourly Orders’)

In the grocery, there are close to 50,000 products. When we zoom into hourly purchases, we noticed that top 10 products managed to score betwen 6% to 8% of hourly sales. Every hour has slightly diffrent combination of top 10 products (combination out of 12 products). That means certain products are predictable for ordering irregardless of the hour of order.

It is interesting to know that, similar to daily top 10 products, the Organic Wholemilk and Limes is missing as top 10 from some hours.

rr users_orders_products_ %>% group_by(order_hour_of_day, product_name) %>% summarize(n = n()) %>% mutate(percentage = n/sum(n)) %>% top_n(10, wt = n) %>% ggplot (aes(x = as.factor(order_hour_of_day), y = percentage, fill = product_name)) + geom_col() + labs(y = ‘Proprtion of Orders In A Hour’, title = ‘Hourly Top 10 Products Ordered’) + theme(legend.position = , legend.direction = )

5.3 Basket Analysis

5.3.1 Basket Size Distribution

Number of items in all orders range from 1 to 145. The histogram below is highly skewed towards small basket size. Majority of users purchased 5 items in their orders.

rr tmp <- users_orders_products_ %>% group_by(order_id) %>% summarize(basket_size = n(), reordered_items = sum(reordered)) %>% group_by(basket_size) %>% summarize(n = n(), avg_reordered_items = mean(reordered_items)) %>% arrange(basket_size)

tmp %>% ggplot(aes(x = as.factor(basket_size))) + geom_col(aes(y = n)) + labs(y = ‘Order Count’, x = ‘Number of Items in Basket’, title = ‘Basket Size Distribution’) + theme(axis.text.x = element_text(size = 6.0, angle = 90, hjust = 1, vjust = 0.5))

5.4 Re-Ordered Analysis

Analyzing the re-ordered products is the most important part of the EDA. This is becasue insights from this analysis can help to develop intuition for furhter feature engineering that will make the prediction more meaningful.

5.4.1 Average Re-ordered Items In Basket Distribution

rr tmp %>% ggplot(aes(x = as.factor(basket_size))) + geom_point(aes(y = avg_reordered_items), color = ‘red’) + labs(y = ‘Avg Number of Re-Ordered Items’, x = ‘Number of Items in Basket’, title = ‘Reorder Rate by Basket Size’) + theme(axis.text.x = element_text(size = 6.0, angle = 90, hjust = 1, vjust = 0.5)) + geom_abline(intercept = 0, slope = 1, color = ‘blue’)

5.4.2 Product Reorder Ratio

One of the tricker things to predict in the Instacart dataset is the incidence of orders without reordered products. Plotting the proportion of this incidence across the training sample (a snapshot of 131K+ users) provides some inspiration.

5.4.3 How Many Products Were Reordered

Among all product purchases, 41% of products are reordered. The reordered rate is particularly high on top 10 products. As shown in chart below, top ten popular products has reordered rate is around 70% to 85%; higher than the overall ratio of 41%.

rr ## overall all products reordered rate tmp1 <- users_orders_products_ %>% filter(order_number > 1) %>% # exclude first order, which will never have reordered count(reordered) %>% mutate(ratio = n/sum(n))

p1 <- tmp1 %>% ggplot(aes(x = ’‘, y = ratio, fill = as.factor(reordered))) + geom_col(width = 1) + labs(y = ’Product Reordered Ratio’) + coord_polar(theta = ‘y’, start = 0) + scale_fill_brewer(palette = 2) + theme(axis.title.y = element_blank())

5.5 top10 products and its reordered rate

tmp2 <- users_orders_products_ %>% count(product_id) %>% # filter only top 10 products for reorder analysis top_n(n = 10) %>% left_join(users_orders_products_) %>% # now find out their reordered rate group_by(product_id, product_name) %>% summarize(reordered_rate = sum(reordered, na.rm = TRUE)/n()) %>% select(product_id, product_name, reordered_rate) %>% arrange(desc(reordered_rate))

p2 <- tmp2 %>% ggplot(aes(x = reorder(product_name, reordered_rate), y = reordered_rate)) + labs(title = ‘Top 10 Products Sold and Their Reordering Rate’) + geom_col() + scale_y_continuous(limits = c(0, 1), breaks = seq(0, 1, by = 0.1)) + coord_flip()

grid.arrange(p1, p2, ncol = 2)

5.5.1 Reordering vs Days Since Prior Order

We understand from order analysis earlier that most users place their orders every 7 and 30 days. However, from reorder ration perspective, day 7 and day 30 has high contrast whereby day 7 orders has high reorder ratio and day 30 has lowest reordering ratio.

rr tmp <- users_orders_products_ %>% filter(order_number > 1) %>% group_by(days_since_prior_order, order_id) %>% summarize(contain_reordered = max(reordered)) %>% summarize(reordered_orders = sum(contain_reordered), n = n() + 1) %>% mutate(non_reorder_ratio = 1 - (reordered_orders/n))

tmp %>% ggplot(aes(x = days_since_prior_order, y = non_reorder_ratio)) + geom_point() + geom_line() + labs(title = ‘Orders NOT Containing Reordered Products over Days since Prior Order’)

5.5.2 Reordering vs Hour Of Order

rr tmp <- users_orders_products_ %>% filter(order_number > 1) %>% group_by(order_hour_of_day, order_id) %>% summarize(contain_reordered = max(reordered)) %>% summarize(reordered_orders = sum(contain_reordered), n = n()) %>% mutate(non_reorder_ratio = 1 - (reordered_orders/n))

tmp %>% ggplot(aes(x = order_hour_of_day, y = non_reorder_ratio)) + geom_point() + geom_line() + labs(title = ‘Non Reorder Ratio over Time of Order Placed’)

5.5.3 Reordering vs Day Of Order

rr tmp <- users_orders_products_ %>% filter(order_number > 1) %>% group_by(order_dow, order_id) %>% summarize(contain_reordered = max(reordered)) %>% summarize(reordered_orders = sum(contain_reordered), n = n() + 1) %>% mutate(non_reorder_ratio = 1 - (reordered_orders/n))

tmp %>% ggplot(aes(x = order_dow, y = non_reorder_ratio)) + geom_point() + geom_line() + labs(title = ‘Non Reorder Ratio over Day of Purchase’)

5.5.4 Reordering vs Day Of Order

Intuitively, we can think of the more regular a buyer is, the person tend to repeat ordering the same products.

rr tmp <- users_orders_products_ %>% filter(order_number > 1) %>% group_by(user_id, order_id) %>% summarize(contain_reordered = max(reordered)) %>% summarize(reordered_orders = sum(contain_reordered), total_orders_per_user = n()) %>% group_by(total_orders_per_user) %>% summarize(reorders = sum(reordered_orders), total = sum(total_orders_per_user)) %>% mutate(non_ratio = 1 - (reorders/total))

tmp %>% ggplot(aes(x = total_orders_per_user, y = non_ratio)) + geom_point() + geom_line() + labs(title = ‘Non Reorder Ratio over Day of Purchase’)

6 Predictive Analysis

6.1 Type of Prediction

The objective is to predict what product will the customer purchase in the next basket. It require probability estimation of each product that bad been purchased before, that to be purchased before.This is a classification problem, as well as a regression of probability of repurchases.

For this analysis, we shall use two Naive models (handcrafted baseline) and one Machine Learning Logistic regression will be used for Machine Learning approach for its speed and simplicity; to demonstrate the feasibility to producing a better outcome then baseline.

6.1.1 Train/Test Dataset Splitting

Instacart did not provide us test order detail, therefore we shall use the train users for both trainng and testing. We achieve this by splitting the train users and its related orders and products into train dataset and train dataset, at 70%/30% split (by number of users). That means our train/test dataset will contain approximately 91846 / 39,363 users.

For this analysis, we will not be submitting to Kaggle.

rr # update this variable for changing split ratio train_proportion <- 0.7

7 build list of all users ID

tmp <- orders %>% filter(eval_set == ‘train’) %>% distinct(user_id)

8 70/30 split

set.seed(12345) train.rows <- sample(1:nrow(tmp), train_proportion * nrow(tmp)) train.users <- tmp[train.rows, ] # select training rows, list of train users test.users <- tmp[-train.rows, ] # select testing rows, list of test users

cat(Rows in Training Users: , length(train.users), \nTotal Rows in Testing Users: , length(test.users), \nTrain/Test Split % : , 100length(train.users)/(length(test.users)+length(train.users)), / , 100length(test.users)/(length(test.users)+length(train.users)))

8.0.1 Training Data Construct

The data frame used for training should contain the below columns and features:

key

This is unique pair of user_id and product_id from orders
The keys should be constructed from all user_id-product_id pair that includes all prior and test/train rows

`actual

This is the response variable with value of 1 or 0 for each unique key
The value is 1 when the product is purchased in the last order (train or test set of orders)
The value is 0 when the product is not purchased in the train or test set, but was bought in prior set

other features

From exploratory discovery, features that could contribute to the prediction should be populated into the construct. Feature engineering will happen in the later stage.

Let’s proceed to create the basic training construct. This won’t be used for prediction until feature engineering is completed in later stage.

rr # list of products in the final order, this make up the label construct1 <- orders %>%
filter(user_id %in% train.users & eval_set == ‘train’) %>% left_join(order_products_train) %>% distinct(user_id, product_id) %>% mutate(actual = 1) #training label

9 list of products each users had bought before in prior orders

construct2 <- orders %>%
filter(user_id %in% train.users & eval_set == ‘prior’) %>% left_join(order_products_prior) %>% distinct(user_id, product_id)

10 Training Construct

train.construct <- left_join(construct2, construct1) %>% mutate(key = paste(user_id, product_id, sep = -)) %>% # key select(key, user_id, product_id, actual) %>% arrange(user_id, product_id) %>% replace_na(list(actual = 0)) # proudcts not in last order, but exist in prior order # drop_na # remove proudcts not in historical but appear in last order

rm(list = c(‘construct1’, ‘construct2’)) head(train.construct, 50)

10.0.1 Testing Data Construct

Similar approach to training data construct, here we frame the testing data for evaluate our model built with training data.

# list of products in the final order, this make up the label
construct1 <- orders %>%    
  filter(user_id %in% test.users & eval_set == 'train') %>% 
  left_join(order_products_train) %>%
  distinct(user_id, product_id) %>%
  mutate(actual = 1)  #training label

# list of products each users had bought before in prior orders
construct2 <- orders %>%   
  filter(user_id %in% test.users & eval_set == 'prior') %>% 
  left_join(order_products_prior) %>%
  distinct(user_id, product_id)

# Training Construct
test.construct <- construct2 %>% 
  left_join(construct1) %>%
  mutate(key = paste(user_id, product_id, sep = "-")) %>%  # key
  select(key, user_id, product_id, actual) %>%
  arrange(user_id, product_id) %>%
  replace_na(list(actual = 0)) # proudcts not in last order, but exist in prior order
#  drop_na # remove proudcts not in historical but appear in last order

rm(list = c('construct1', 'construct2'))
head(test.construct, 50)

10.1 Model Evaluation & Optimization

Instacart has close to 50k products in their catalogue. As the maximum number of items ordered by a user is just a fraction of the 50k available product. This means by simply predicting nothing is purchased in the next basket, we would yeild close to 100% accuracy.

Due to the highly imbalance dataset, Instacart require F1 Score as the competition scoring, instead of accuracy.

To evaluate the performance of the model, we had created a custom function to build a confusion matrix and derive other binary classification metrics.

rr ## Custom Function For Binary Class Performance Evaluation binclass_eval = function (actual, predict) { cm = table(as.integer(actual), as.integer(predict), dnn=c(‘Actual’,‘Predicted’)) ac = (cm[‘1’,‘1’]+cm[‘0’,‘0’])/(cm[‘0’,‘1’] + cm[‘1’,‘0’] + cm[‘1’,‘1’] + cm[‘0’,‘0’]) pr = cm[‘1’,‘1’]/(cm[‘0’,‘1’] + cm[‘1’,‘1’]) rc = cm[‘1’,‘1’]/(cm[‘1’,‘0’] + cm[‘1’,‘1’]) fs = 2* pr*rc/(pr+rc) list(cm=cm, recall=rc, precision=pr, fscore=fs, accuracy=ac) }

If the prediction is based on probability, we shall build a function to discover cutoff that optimize various performance metrics.

rr ### Cutoff Threshold Optimization optimize_cutoff = function (actual, probability) { rocr.pred = prediction(predictions = probability, labels = actual) rocr.metrics = data.frame( cutoff = rocr.pred@cutoffs[[1]], accuracy = (rocr.pred@tp[[1]] + rocr.pred@tn[[1]]) / (rocr.pred@tp[[1]] + rocr.pred@tn[[1]] + rocr.pred@fp[[1]] + rocr.pred@fn[[1]]), tpr = rocr.pred@tp[[1]] / (rocr.pred@tp[[1]] + rocr.pred@fn[[1]]), fpr = rocr.pred@fp[[1]] / (rocr.pred@fp[[1]] + rocr.pred@tn[[1]]), ppv = rocr.pred@tp[[1]] / (rocr.pred@tp[[1]] + rocr.pred@fp[[1]]) ) rocr.metrics$fscore = 2 * (rocr.metrics$tpr * rocr.metrics$ppv) / (rocr.metrics$tpr + rocr.metrics$ppv) rocr.metrics$tpr_fpr = rocr.metrics$tpr / rocr.metrics$fpr

## Discovery the optimal threshold for various metrics rocr.best = rbind( best.accuracy = c(max = max(rocr.metrics$accuracy, na.rm = TRUE), cutoff=rocr.metrics$cutoff[which.max(rocr.metrics$accuracy)]), best.ppv = c(max = max(rocr.metrics$ppv, na.rm = TRUE), cutoff = rocr.metrics$cutoff[which.max(rocr.metrics$ppv)]), best.recall = c(max = max(rocr.metrics$tpr, na.rm = TRUE), cutoff = rocr.metrics$cutoff[which.max(rocr.metrics$tpr)]), best.fscore = c(max = max(rocr.metrics$fscore, na.rm = TRUE), cutoff = rocr.metrics$cutoff[which.max(rocr.metrics$fscore)]), best.tpr_fpr = c(max = max(rocr.metrics$tpr_fpr, na.rm = TRUE), cutoff = rocr.metrics$cutoff[which.max(rocr.metrics$tpr_fpr)]) )

list(metrics = rocr.metrics, best = rocr.best) }

10.2 Model 1 : Naive Prediction

10.2.1 Build The Model

With intension to make this a baseline model, We simply predict the basket based on user last order.

rr m1.train.data = users_orders_products_ %>% filter(user_id %in% train.users) %>% group_by(user_id) %>% top_n(n=1, wt=order_number) %>% #last order has the higher order_number select(user_id, product_id) %>% mutate (predicted=1) %>% #predict based on last ordered, therefore 1 full_join(train.construct) %>% # join with train construct for items not predicted but in final order select(user_id, product_id, actual, predicted) %>% replace_na(list(predicted = 0))

head(m1.train.data,25)

10.2.2 Confusion Matrix

rr m1.eval = binclass_eval(m1.train.data$actual, m1.train.data$predicted) m1.eval$cm

10.2.3 Model Performance

The result shows only 0.3460833 F1 Score.

rr cat(: , m1.eval$accuracy, \\nPrecision: \, m1.eval$precision, \nRecall: , m1.eval$recall, \\nFScore: \, m1.eval$fscore)

10.3 Model 2 : Smarter Naive Prediction (Baseline)

In this model, we predict products in the basket by estimating their frequency of repurchased. This way we get a ratio to indicate probability of re-purchases. We use ROCR package to estimate the best cutoff point (at which above this cutoff we shall predict for re-order) that give us the optimum F1 score.

10.3.1 Build The Model

rr ## Build Model m2.train.data = users_orders_products_ %>% filter(user_id %in% train.users) %>% group_by(user_id) %>% mutate(total_orders = max(order_number)) %>% # total number of orders made previously ungroup %>% select(user_id, order_id, product_id, total_orders) %>% group_by(user_id, product_id) %>% summarize(predicted=n()/max(total_orders)) %>% select(user_id, product_id, predicted) %>% full_join(train.construct) %>% # join with train construct for items not predicted but in final order select(user_id, product_id, actual, predicted) %>% replace_na(list(predicted = 0))

head(m2.train.data,20)

10.3.2 Optimize Cutoff

We see that in order to maximize F1 Score, we need to set the cutoff threshold to 0.3368, which is the next step.

rr ### Threshold Optimization m2.rocr = optimize_cutoff(actual = m2.train.data$actual, probability = m2.train.data$predicted) kable(m2.rocr$best) %>% kable_styling(bootstrap_options = c())

10.3.3 Confusion Matrix

Let’s set the cutoff to 0.3367347 as discovered in previous step.

rr m2.eval = binclass_eval(m2.train.data$actual, m2.train.data$predicted>0.3367347) m2.eval$cm

10.3.4 Model Performance

We are getting slightly better F1 Score (0.3753544) compare to previous naive model. We shall use this as the BASELINE.

rr cat(: , m2.eval$accuracy, \\nPrecision: \, m2.eval$precision, \nRecall: , m2.eval$recall, \\nFScore: \, m2.eval$fscore)

10.4 Machine Learning Framing

We construct all the products that users had purchased in the last 3 orders, then use machine learning classification to predict will each of the product be purchased again. We shall use decision tree and logistic regression for this prediction.

10.4.1 Feature Engineering

10.4.1.1 Order Features

These are original features provided by Instacart. Although there are no other features engineered specifically to describe Order, thse features are being used to generate other features in the following sections.

orders
- order_dow
- order_hour_of_day
- days_since_prior_order
- reordered

10.4.1.2 User Features

We create five features which is unique to each individual user. These are the features that desribe the user.

users
- u_n_orders: Number of Orders Per User
- u_avg_priors: Average waiting days between orders per User
- u_avg_hod: Average Order Placing Hour Per User
- u_avg_dow: Average Order Placing Day Per User
- u_avg_order_size: Average Size of Basket (items in order) Per User

#### user features
users_ = users_orders_products_ %>%
  group_by(user_id,order_id) %>%
    mutate(u_o_size = ifelse(row_number()==1, max(add_to_cart_order),0) ) %>%
  group_by(user_id) %>%
    summarize(
      u_n_orders = max(order_number),
      u_avg_priors = mean(days_since_prior_order,na.rm=TRUE),
      u_avg_hod = mean(order_hour_of_day),
      u_avg_dow = mean(order_dow),
      u_avg_order_size = sum(u_o_size)/max(order_number)
    ) %>% 
  arrange(user_id)

head(users_)

10.4.1.3 Product Features

We create two product specific features.

products

avg_product_order_dow: Average of product order_dow
avg_product_order_hod: Average of product order_hour_of_day

products_ = users_orders_products_ %>%
  group_by(product_id) %>%
  summarize( 
    p_avg_dow = mean(order_dow),
    p_avg_hod = mean(order_hour_of_day)
  ) %>% arrange(product_id)

head(products_)

10.4.1.4 User-Product Features

We shall introduce product related features that are user-product specifc

up_n_reordered : how many times a user reorderedthis product
up_avg_priors : Average number of days in between before a user purchase this product
up_avg_hod : Average hour a user purchase this product
up_avg_dow : Average day of week a user purchase this product
up_avg_rank : Average add to cart number a user select this product

rr ### user_products features user_products_ = users_orders_products_ %>% group_by(user_id, product_id) %>% summarize( up_n_reordered = n()-1, # minus off first order, which is not reorder up_avg_priors = mean(days_since_prior_order,na.rm=TRUE), up_avg_hod = mean(order_hour_of_day), up_avg_dow = mean(order_dow), up_avg_rank = mean(add_to_cart_order) ) %>% ungroup %>% left_join(users_) %>% # to retrieve u_n_orders mutate(up_reorder_rate = up_n_reordered/(u_n_orders-1)) %>% replace_na(list(up_avg_priors = 0)) %>% # fix up arrange(user_id,product_id)

head(user_products_,20)

10.4.2 Construct Training Data

We shall combined training construct table with the new engineered features to form the training data. Categorical data which are merely names or identification will be removed since they should not contribute to prediction.

After this step, the trianing data is ready for machine learning algorithm of choice.

m3.train.data = users_orders_products_ %>%
  filter(user_id %in% train.users) %>%
  left_join(user_products_) %>% 
  left_join(products_) %>%
  #left_join(users_)  #user_products_ already contain user specific features
  full_join(train.construct, by=c('user_id','product_id')) %>%
  arrange(user_id, product_id) %>%
  select(-c('key','user_id','order_id', 'product_id', 'product_name', 'department_id', 'aisle_id', 'department','aisle', 'days_since_prior_order')) 

glimpse(m3.train.data)

10.4.3 Construct Testing Data

m3.test.data = users_orders_products_ %>%
  filter(user_id %in% test.users) %>%
  left_join(user_products_) %>% 
  left_join(products_) %>%
  #left_join(users_)  #user_products_ already contain user specific features
  full_join(test.construct, by=c('user_id','product_id')) %>%
  arrange(user_id, product_id) %>%
  select(-c('key','user_id','order_id', 'product_id', 'product_name', 'department_id', 'aisle_id', 'department','aisle', 'days_since_prior_order')) 

glimpse(m3.test.data)

10.5 Model 3 : Logistic Regression

10.5.1 Model Trainng

rr m3.fit = glm(actual ~ ., family = binomial, data = m3.train.data)

10.5.2 Training Data Performance

10.5.2.1 Prediction

rr m3.predict = predict(m3.fit, type = ‘response’, newdata = m3.train.data)

10.5.2.2 Optimize Cutoff

rr ### Threshold Optimization m3.rocr = optimize_cutoff(actual = m3.train.data$actual, probability = m3.predict) kable(m3.rocr$best) %>% kable_styling(bootstrap_options = c())

10.5.2.3 Confusion Matrix

rr m3.eval = binclass_eval(m3.train.data$actual, m3.predict>0.2233115) m3.eval$cm

10.5.2.4 Model Evaluation

Logistic regression produce F1 Score of 0.5388937 with training data, a much better compared to Model 1 and Model 2. We shall proceed test the model on unknown data, the test data.

rr cat(: , m3.eval$accuracy, \\nPrecision: \, m3.eval$precision, \nRecall: , m3.eval$recall, \\nFScore: \, m3.eval$fscore)

rocr.pred = prediction(m3.predict, m3.train.data$actual)
rocr.perf = performance(rocr.pred, measure = "tpr", x.measure = "fpr")
rocr.auc = as.numeric(performance(rocr.pred, "auc")@y.values)
plot(rocr.perf,
    lwd = 3, colorize = TRUE,
    print.cutoffs.at = seq(0, 1, by = 0.1),
    text.adj = c(-0.2, 1.7),
    main = 'ROC Curve')
mtext(paste('auc : ', round(rocr.auc, 5)))
abline(0, 1, col = "red", lty = 2)

10.5.3 Test Data Performance

10.5.3.1 Prediction

rr m3.predict.test = predict(m3.fit, type = ‘response’, newdata = m3.test.data)

10.5.3.2 Optimize Cutoff

rr ### Threshold Optimization m3.rocr.test = optimize_cutoff(actual = m3.test.data$actual, probability = m3.predict.test) kable(m3.rocr.test$best) %>% kable_styling(bootstrap_options = c())

10.5.3.3 Confusion Matrix

rr m3.eval.test = binclass_eval(m3.test.data$actual, m3.predict.test>0.2233115) m3.eval.test$cm

10.5.3.4 Model Evaluation

Logistic regression produce F1 Score of 0.5388937 with training data, a much better compared to Model 1 and Model 2. We shall proceed test the model on unknown data, the test data.

We acheived F1 Score of 0.5405588, slightly higher than training data.

rr cat(: , m3.eval.test$accuracy, \\nPrecision: \, m3.eval.test$precision, \nRecall: , m3.eval.test$recall, \\nFScore: \, m3.eval.test$fscore)

rr rm(list=c(‘m3.fit’,‘m3.predict’, ‘m3.rocr’))

10.5.3.5 ROC

rr rocr.pred = prediction(predictions = m3.predict.test, labels = m3.test.data$actual) rocr.perf = performance(rocr.pred, measure = , x.measure = ) rocr.auc = as.numeric(performance(rocr.pred, )@y.values) rocr.auc

rr plot(rocr.perf, lwd = 3, colorize = TRUE, print.cutoffs.at = seq(0, 1, by = 0.1), text.adj = c(-0.2, 1.7), main = ‘ROC Curve’) mtext(paste(‘auc :’, round(rocr.auc, 5))) abline(0, 1, col = , lty = 2)

11 Analysis & Recommendations

Technical Challenges

Machine speed and memory. The GLM

LS0tDQp0aXRsZTogICJJbnN0YWNhcnQgTWFya2V0IEJhc2tldCBBbmFseXNpcyINCmF1dGhvcjogIkJ5IEFlcCBIaWRheWF0dWxvaCINCmRhdGU6ICAgIjIwMTkgSnVuIDciDQpvdXRwdXQ6IA0KICBodG1sX25vdGVib29rOg0KICAgIG51bWJlcl9zZWN0aW9uczogeWVzDQogICAgdGhlbWU6IHNwYWNlbGFiDQogICAgZGZfcHJpbnQ6IHBhZ2VkDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6IDQNCiAgICB0b2NfZmxvYXQ6IHRydWUNCi0tLQ0KDQo8c3R5bGUgdHlwZT0idGV4dC9jc3MiPg0KDQpib2R5eyAvKiBOb3JtYWwgICovDQogICAgICBmb250LXNpemU6IDEycHg7DQogIH0NCnRkIHsgIC8qIFRhYmxlICAqLw0KICBmb250LXNpemU6IDEycHg7DQp9DQpoMS50aXRsZSB7DQogIGZvbnQtc2l6ZTogMzhweDsNCiAgY29sb3I6IGxpZ2h0Ymx1ZTsNCiAgZm9udC13ZWlnaHQ6IGJvbGQ7DQp9DQpoMSB7IC8qIEhlYWRlciAxICovDQogIGZvbnQtc2l6ZTogMjRweDsNCiAgY29sb3I6IERhcmtCbHVlOw0KfQ0KaDIgeyAvKiBIZWFkZXIgMiAqLw0KICBmb250LXNpemU6IDIwcHg7DQogIGNvbG9yOiBEYXJrQmx1ZTsNCn0NCmgzIHsgLyogSGVhZGVyIDMgKi8NCiAgZm9udC1zaXplOiAxNnB4Ow0KIyAgZm9udC1mYW1pbHk6ICJUaW1lcyBOZXcgUm9tYW4iLCBUaW1lcywgc2VyaWY7DQogIGNvbG9yOiBEYXJrQmx1ZTsNCn0NCmg0IHsgLyogSGVhZGVyIDQgKi8NCiAgZm9udC1zaXplOiAxNHB4Ow0KICBjb2xvcjogRGFya0JsdWU7DQp9DQpjb2RlLnJ7IC8qIENvZGUgYmxvY2sgKi8NCiAgICBmb250LXNpemU6IDEycHg7DQp9DQpwcmUgeyAvKiBDb2RlIGJsb2NrIC0gZGV0ZXJtaW5lcyBjb2RlIHNwYWNpbmcgYmV0d2VlbiBsaW5lcyAqLw0KICAgIGZvbnQtc2l6ZTogMTJweDsNCn0NCjwvc3R5bGU+DQoNCg0KYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9DQoja25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFKQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG89VFJVRSwgZmlnLmhlaWdodD0zLjUsIGZpZy53aWR0aD05LjIsIHJlc3VsdHM9J2hvbGQnLCB3YXJuaW5nPUZBTFNFLCBmaWcuc2hvdz0naG9sZCcsIG1lc3NhZ2U9RkFMU0UpIA0Kb3B0aW9ucyhzY2lwZW4gPSA5OSkNCmBgYA0KDQpDb3BpZWQgYW5kIG1vZGlmaWVkIGZyb20gPGh0dHBzOi8vcnB1YnMuY29tL3lvbmdrcy9pbnN0YWNhcnQ4Pg0KDQojIEludHJvZHVjdGlvbg0KDQpJbnN0YWNhcnQgaXMgYW4gYXBwIGZvciBvbi1kZW1hbmQgZ3JvY2VyeSBzaG9wcGluZyB3aXRoIHNhbWUtZGF5IGRlbGl2ZXJ5IHNlcnZpY2UuICBJbnN0YWNhcnQgdXNlcyBhIGNyb3dkc291cmNlZCBtYXJrZXRwbGFjZSBtb2RlbCwgYWtpbiB0byB0aGF0IG9mIFViZXIgb3IgTHlmdC4gDQogDQpUaGUgSW5zdGFjYXJ0IHNob3BwaW5nIHByb2Nlc3MgaXMgYXMgZm9sbG93cy4gIEZpcnN0LCBhbiBhcHAgdXNlciBwbGFjZXMgdGhlaXIgZ3JvY2VyeSBvcmRlciB0aHJvdWdoIHRoZSBhcHAuICBUaGVuLCBhIGxvY2FsbHkgY3Jvd2Rzb3VyY2VkICJzaG9wcGVyIiBpcyBub3RpZmllZCBvZiB0aGUgb3JkZXIsIGdvZXMgdG8gYSBuZWFyYnkgc3RvcmUsIGJ1eXMgdGhlIGdyb2NlcmllcywgYW5kIGRlbGl2ZXJzIHRoZW0gdG8gdGhlIHVzZXIuICAgDQogDQpUaGVyZSBhcmUgdGhyZWUgd2F5cyB0aGF0IEluc3RhY2FydCBnZW5lcmF0ZXMgcmV2ZW51ZTogZGVsaXZlcnkgZmVlcywgbWVtYmVyc2hpcCBmZWVzLCBhbmQgbWFyay11cHMgb24gaW4tc3RvcmUgcHJpY2VzLg0KDQojIyBSZXNlYXJjaCBHb2FsICYgT2JqZWN0aXZlDQoNClRoZSBtYWluIG9iamVjdGl2ZSBvZiB0aGUgY29tcGV0aXRpb24gaXMgdG8gcHJlZGljdCB3aGF0IHdpbGwgdGhlIHVzZXIgd2lsbCBidXkgaW4gdGhlIG5leHQgb3JkZXIsIGdpdmVuIGFsbCBkYXRhIG9mIHByaW9yIG9yZGVycy4gDQoNCiMgTWFya2V0IEJhc2tldCBBbmFseXNpcw0KDQpNYXJrZXQgQmFza2V0IEFuYWx5c2lzIChNQkEpIGlzIGEgcHJvY2VzcyB0aGF0IGxvb2tzIGZvciByZWxhdGlvbnNoaXBzIGFtb25nIGVudGl0aWVzIGFuZCBvYmplY3RzIHRoYXQgZnJlcXVlbnRseSBhcHBlYXIgdG9nZXRoZXIsIHN1Y2ggYXMgdGhlIGNvbGxlY3Rpb24gb2YgaXRlbXMgaW4gYSBzaG9wcGVy4oCZcyBjYXJ0LiBGb3IgdGhlIHB1cnBvc2VzIG9mIGN1c3RvbWVyIGNlbnRyaWNpdHksIG1hcmtldCBiYXNrZXQgYW5hbHlzaXMgZXhhbWluZXMgY29sbGVjdGlvbnMgb2YgaXRlbXMgdG8gaWRlbnRpZnkgYWZmaW5pdGllcyB0aGF0IGFyZSByZWxldmFudCB3aXRoaW4gdGhlIGRpZmZlcmVudCBjb250ZXh0cyBvZiB0aGUgY3VzdG9tZXIgdG91Y2ggcG9pbnRzLiBTb21lIGV4YW1wbGVzIGluY2x1ZGU6DQoNCiogUHJvZHVjdCBwbGFjZW1lbnTigJRJZGVudGlmeWluZyBwcm9kdWN0cyB0aGF0IG1heSBvZnRlbiBiZSBwdXJjaGFzZWQgdG9nZXRoZXIgYW5kIGFycmFuZ2luZyB0aGUgcGxhY2VtZW50IG9mIHRob3NlIGNsb3NlIGJ5IHRvIGVuY291cmFnZSB0aGUgcHVyY2hhc2VyIHRvIGJ1eSBib3RoIGl0ZW1zLiBUaGF0IHBsYWNlbWVudCBjYW4gYmUgcGh5c2ljYWwsIHN1Y2ggYXMgaW4gdGhlIGFycmFuZ2VtZW50IG9mIHByb2R1Y3RzIG9uIHNoZWx2ZXMgaW4gYSBicmljayBhbmQgbW9ydGFyIGxvY2F0aW9uLCBvciB2aXJ0dWFsLCBzdWNoIGFzIGluIGEgcHJpbnQgY2F0YWxvZyBvciBvbiBhbiBlLWNvbW1lcmNlIHNpdGUuDQoNCiogUG9pbnQtb2YtU2FsZeKAlENvbXBhbmllcyBtYXkgdXNlIHRoZSBhZmZpbml0eSBncm91cGluZyBvZiBtdWx0aXBsZSBwcm9kdWN0cyBhcyBhbiBpbmRpY2F0aW9uIHRoYXQgY3VzdG9tZXJzIG1heSBiZSBwcmVkaXNwb3NlZCB0byBidXlpbmcgY2VydGFpbiBzZXRzIG9mIHByb2R1Y3RzIGF0IHRoZSBzYW1lIHRpbWUuIFRoaXMgZW5hYmxlcyB0aGUgcHJlc2VudGF0aW9uIG9mIGl0ZW1zIGZvciBjcm9zcy1zZWxsaW5nLCBvciBtYXkgc3VnZ2VzdCB0aGF0IGN1c3RvbWVycyBtYXkgYmUgd2lsbGluZyB0byBidXkgbW9yZSBpdGVtcyB3aGVuIGNlcnRhaW4gcHJvZHVjdHMgYXJlIGJ1bmRsZWQgdG9nZXRoZXIuDQoNCiogQ3VzdG9tZXIgcmV0ZW50aW9u4oCUV2hlbiBjdXN0b21lcnMgY29udGFjdCBhIGJ1c2luZXNzIHRvIHNldmVyIGEgcmVsYXRpb25zaGlwLCBhIGNvbXBhbnkgcmVwcmVzZW50YXRpdmUgbWF5IHVzZSBtYXJrZXQgYmFza2V0IGFuYWx5c2lzIHRvIGRldGVybWluZSB0aGUgcmlnaHQgaW5jZW50aXZlcyB0byBvZmZlciBpbiBvcmRlciB0byByZXRhaW4gdGhlIGN1c3RvbWVy4oCZcyBidXNpbmVzcy4NCg0KTUJBIGlzIG9uZSBvZiB0aGUga2V5IHRlY2huaXF1ZXMgdXNlZCBieSB0aGUgbGFyZ2UgcmV0YWlsZXJzIHRoYXQgdW5jb3ZlcnMgYXNzb2NpYXRpb25zIGJldHdlZW4gaXRlbXMgYnkgbG9va2luZyBmb3IgY29tYmluYXRpb25zIG9mIGl0ZW1zIHRoYXQgb2NjdXIgdG9nZXRoZXIgZnJlcXVlbnRseSBpbiB0cmFuc2FjdGlvbnMuIEluIG90aGVyIHdvcmRzLCBpdCBhbGxvd3MgdGhlIHJldGFpbGVycyB0byBpZGVudGlmeSByZWxhdGlvbnNoaXBzIGJldHdlZW4gdGhlIGl0ZW1zIHRoYXQgcGVvcGxlIGJ1eS4NCg0KQXNzb2NpYXRpb24gUnVsZXMgaXMgd2lkZWx5IHVzZWQgdG8gYW5hbHl6ZSByZXRhaWwgYmFza2V0IG9yIHRyYW5zYWN0aW9uIGRhdGEsIGlzIGludGVuZGVkIHRvIGlkZW50aWZ5IHN0cm9uZyBydWxlcyBkaXNjb3ZlcmVkIGluIHRyYW5zYWN0aW9uIGRhdGEgdXNpbmcgc29tZSBtZWFzdXJlcyBvZiBpbnRlcmVzdGluZ25lc3MsIGJhc2VkIG9uIHRoZSBjb25jZXB0IG9mIHN0cm9uZyBydWxlcy4NCg0KIyBUZXJtaW5vbG9neSBvZiBBc3NvY2lhdGlvbiBSdWxlcw0KDQpBc3N1bWUgdGhlcmUgYXJlIDEwMCB0cmFuc2FjdGlvbnMgb24gYSByZXRhaWwgc2hvcC4NCiogMTAgb3V0IG9mIHRoZW0gYm91Z2h0IG1pbGssIDggYm91Z2h0IGJ1dHRlciBhbmQgNiBib3VnaHQgYm90aCBvZiB0aGVtIChtaWxrICYgYnV0dGVyKS4gDQoqIEZvciBleGFtcGxlLCBvdXIgaW50ZXJlc3RpbmcgaXMgaG93IGl0IGxpa2UgaWYgc29tZW9uZSBib3VnaHQgbWlsayBhbHNvIGJvdWdodCBidXR0ZXI6DQogICAgKyBib3VnaHQgbWlsayA9PiBib3VnaHQgYnV0dGVyDQoNCkZpcnN0LCB3ZSBuZWVkIHRvIGtub3cgdGhlIHRlcm1pbm9sb2d5IHRoYXQgdXNlZCBpbiBNQkEuDQoNCiAgKiAgKipJdGVtc2V0KiogOiBzZXQgb2YgaXRlbXMgdGhhdCBjdXN0b21lciBib3VnaHQgaW4gYWxsIHRyYW5zYWN0aW9ucy4NCiAgKiAgKipTdXBwb3J0KiogOiBwcm9wb3J0aW9uIG9mIHRyYW5zYWN0aW9uIHRoYXQgY29udGFpbiBhbiBpdGVtc2V0cyBvZiBpbnRlcmVzdC4NCiAgICAgICQkU3VwcChYIFxSaWdodGFycm93IFkpID0gXGZyYWN7ZnJxKHwgWCBcY3VwIFkgfCl9e059JCQNCiAgICAgIEZvciBleGFtcGxlLCBvdXIgaW50ZXJlc3QgaXMgcHJvZHVjdCBNaWxrICYgQnV0dGVyDQogICAgICAkJA0KICAgICAgXGJlZ2lue2FsaWduZWR9DQogICAgICBTdXBwKE1pbGsgXFJpZ2h0YXJyb3cgQnV0dGVyKSAmPSBQKE1pbGssIEJ1dHRlcikgXFwNCiAgICAgICY9IFxmcmFje2ZycShNaWxrLCBCdXR0ZXIpfXtOfVxcDQogICAgICAmPSBcZnJhY3s2fXsxMDB9XFwNCiAgICAgICY9IDAuMDZcXA0KICAgICAgXGVuZHthbGlnbmVkfQ0KICAgICAgJCQNCiAgICAgIA0KICAgICAgVGhlIG1pbmltdW0gc3VwcG9ydCBvZiB0aGUgcnVsZSBpcyBkZWZpbmVkIGFzIHRoZSBtaW5pbXVtIG51bWJlciBvZiB0cmFuc2FjdGlvbnMgdGhhdCBpbmNsdWRlIGJvdGggdGhlIGFudGVjZWRlbnQgYW5kIGNvbnNlcXVlbnQgcGFydHMgaW4gb3JkZXIgdG8gcXVhbGlmeSB0byBiZSBwYXJ0IG9mIGZyZXF1ZW50IGl0ZW0gc2V0LiBUaGUgZGVmYXVsdCBtaW5pbXVtIHN1cHBvcnQgd291bGQgYmUgMTAlIG9mIHRoZSB0b3RhbCBudW1iZXIgb2YgdHJhbnNhY3Rpb25zIHRha2VuIGZvciBhbmFseXNpcy4NCiAgICAgIA0KICAqICoqQ29uZmlkZW5jZSoqIDogY29uZGl0aW9uYWwgcHJvYmFiaWxpdHkgdGhhdCBpZiBhIGN1c3RvbWVyIHB1cmNoYXNlcyBYLCB0aGV5IHdpbGwgcHVyY2hhc2VzIFkuIEl0IGRldGVybWluZXMgdGhlIG9wZXJhdGlvbmFsIHVzZWZ1bG5lc3Mgb2YgYSBydWxlLiBUcmFuc2FjdGlvbnMgd2l0aCBjb25maWRlbmNlIHdpdGggbW9yZSB0aGFuIDUwJSB3aWxsIGJlIHNlbGVjdGVkLiBIaWdoZXIgdGhlIGNvbmZpZGVuY2UgLCBzdHJvbmdlciB0aGUgcnVsZSBpcy4NCiAgICAkJENvbmYoWCwgWSkgPSBcZnJhY3tTdXBwKFgsWSl9e1AoWSl9JCQNCiAgICBDb25maWRlbmNlIGZvciBNaWxrICYgQnV0dGVyIGlzLA0KICAgIHdoZXJlICQkUChCdXR0ZXIpID0gXGZyYWN7ZnJxKEJ1dHRlcil9e059ID0gXGZyYWN7OH17MTAwfSA9IDAuMDgkJCANCiAgICBUaGVuLA0KICAgICQkDQogICAgXGJlZ2lue2FsaWduZWR9DQogICAgQ29uZihNaWxrIFxSaWdodGFycm93IEJ1dHRlcikgJj0gXGZyYWN7U3VwcChNaWxrIFxSaWdodGFycm93IEJ1dHRlcil9e1AoQnV0dGVyKX1cXA0KICAgICY9IFxmcmFjezAuMDZ9ezAuMDh9XFwNCiAgICAmPSAwLjc1DQogICAgXGVuZHthbGlnbmVkfQ0KICAgICQkDQogICAgDQogICAgVGhlIG1pbmltdW0gY29uZmlkZW5jZSBvZiB0aGUgcnVsZSBpcyBkZWZpbmVkIGFzIHRoZSBtaW5pbXVtIG51bWJlciBvZiB0cmFuc2FjdGlvbiB0aGF0IGhhcyBjb25zZXF1ZW50IHdpbGwgYWxzbyBoYXZlIGFudGVjZWRlbnQuIFRoZSBkZWZhdWx0IG1pbmltdW0gY29uZmlkZW5jZSB3b3VsZCBiZSA1MCUuDQogICogKipMaWZ0KiogOiByYXRpbyBvZiBzdXBwb3J0IG9mIFggb2NjdXJpbmcgdG9nZXRoZXIgd2l0aCBZIGRpdmlkZWQgYnkgdGhlIHByb2JhYmlsaXR5IHRoYXQgWCBhbmQgWSBvY2N1ciBpZiB0aGV5IGFyZSBpbmRlcGVuZGV0Lg0KICAkJA0KICBcYmVnaW57YWxpZ25lZH0NCiAgTGlmdChYLFkpICY9IFxmcmFje1N1cHAoWCxZKX17UChYLFkpfSwmIFAoWCxZKSA9IFAoWClQKFkpXFwNCiAgJj0gXGZyYWN7U3VwcChYLFkpfXtQKFgpUChZKX0mXFwgDQogICY9IFxmcmFje1N1cHAoWCxZKX17UChZKX1cZnJhY3sxfXtQKFgpfVxcDQogICY9IENvbmYoWCxZKVxmcmFjezF9e1AoWCl9XFwNCiAgJj0gXGZyYWN7Q29uZihYLFkpfXtQKFgpfQ0KICBcZW5ke2FsaWduZWR9DQogICQkDQogIE5vdyAkTGlmdChNaWxrLCBCdXR0ZXIpID0gPyQNCiAgJCRQKE1pbGspID0gXGZyYWN7ZnJxKE1pbGspfXtOfSA9IFxmcmFjezEwfXsxMDB9ID0gMC4wMSQkDQogIFNvLA0KICAkJA0KICBcYmVnaW57YWxpZ25lZH0NCiAgTGlmdChNaWxrLCBCdXR0ZXIpICY9IFxmcmFje0NvbmYoTWlsaywgQlV0dGVyKX17UChNaWxrKX1cXA0KICAmPSBcZnJhY3swLjc1fXswLjEwfVxcDQogICY9IDcuNQ0KICBcZW5ke2FsaWduZWR9DQogICQkDQoNCk5vdGU6IHRoaXMgZXhhbXBsZSBpcyBleHRyZW1lbHkgc21hbGwuIEluIHByYWN0aWNlLCBhIHJ1bGUgbmVlZHMgYSBzdXBwb3J0IG9mIGh1bmRyZWRzIHRyYW5zYWN0aW9ucyBiZWZvcmUgaXQgY2FuIGJlIGNvbnNpZGVyZWQgc3RhdGlzdGljYWxseSBzaWduaWZpY2FudCwgYW5kIGRhdGFzZXRzIG9mdGVuIGNvbnRhaW4gdGhvdXNhbmRzIG9yIG1pbGxpb25zIG9mIHRyYW5zYWN0aW9ucy4NCg0KT2ssIGVub3VnaCBmb3IgdGhlIHRoZW9yeSwgbGV0J3MgZ2V0IHRvIHRoZSBjb2RlLiANCg0KIyBEYXRhc2V0IFByZXBhcmF0aW9uDQoNCiMjIERhdGEgU291cmNlDQoNCkxhc3QgeWVhciwgSW5zdGFjYXJ0IHJlbGVhc2VkIGEgcHVibGljIGRhdGFzZXQsICoqIlRoZSBJbnN0YWNhcnQgT25saW5lIEdyb2NlcnkgU2hvcHBpbmcgRGF0YXNldCAyMDE3IioqLiBUaGUgZGF0YXNldCBjb250YWlucyBvdmVyIDMgbWlsbGlvbiBhbm9ueW1pemVkIGdyb2Nlcnkgb3JkZXJzIGZyb20gbW9yZSB0aGFuIDIwMCwwMDAgSW5zdGFjYXJ0IHVzZXJzLiBUaGlzIGFuYWx5c2lzIHdpbGwgbWFrZSB1c2Ugb2YgdGhpcyBkYXRhc2V0cy4gIA0KDQpEYXRhIHNvdXJjZSBjYW4gYmUgZG93bmxvYWRlZCBoZXJlOiBodHRwczovL3d3dy5rYWdnbGUuY29tL2MvaW5zdGFjYXJ0LW1hcmtldC1iYXNrZXQtYW5hbHlzaXMvZGF0YQ0KDQojIyBSIExpYnJhcmllcyBVc2VkDQoNCkhlcmUgYXJlIHRoZSBSIGxpYnJhcmllcyB1c2VkIGluIHRoaXMgYW5hbHlzaXMuIA0KDQpgYGB7ciwgbWVzc2FnZT1GQUxTRX0NCmxpYnJhcnkoa25pdHIpICAgICAgIyB3ZWIgd2lkZ2V0DQpsaWJyYXJ5KHRpZHl2ZXJzZSkgICMgZGF0YSBtYW5pcHVsYXRpb24NCmxpYnJhcnkoZGF0YS50YWJsZSkgIyBmYXN0IGZpbGUgcmVhZGluZw0KbGlicmFyeShjYXJldCkgICAgICAjIHJvY3IgYW5hbHlzaXMNCmxpYnJhcnkoUk9DUikgICAgICAgIyByb2NyIGFuYWx5c2lzDQpsaWJyYXJ5KGthYmxlRXh0cmEpICMgbmljZSB0YWJsZSBodG1sIGZvcm1hdGluZyANCmxpYnJhcnkoZ3JpZEV4dHJhKSAgIyBhcnJhbmdpbmcgZ2dwbG90IGluIGdyaWQNCmBgYA0KDQojIyBJbXBvcnQgRGF0YXNldHMNCg0KYGBge3IsIHJlc3VsdHM9J2hpZGUnLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQ0KIyBzZXR3ZCgnLi9kYXRhJykNCmFpc2xlcyAgICAgIDwtICBmcmVhZCgnZGF0YS9haXNsZXMuY3N2JywgICAgICBzdHJpbmdzQXNGYWN0b3JzID0gVFJVRSkNCmRlcGFydG1lbnRzIDwtICBmcmVhZCgnZGF0YS9kZXBhcnRtZW50cy5jc3YnLCBzdHJpbmdzQXNGYWN0b3JzID0gVFJVRSkNCnByb2R1Y3RzICAgIDwtICBmcmVhZCgnZGF0YS9wcm9kdWN0cy5jc3YnLCAgICBzdHJpbmdzQXNGYWN0b3JzID0gVFJVRSkNCm9yZGVycyAgICAgIDwtICBmcmVhZCgnZGF0YS9vcmRlcnMuY3N2JywgICAgICBzdHJpbmdzQXNGYWN0b3JzID0gVFJVRSkNCm9yZGVyX3Byb2R1Y3RzX3RyYWluICA8LSAgZnJlYWQoJ2RhdGEvb3JkZXJfcHJvZHVjdHNfX3RyYWluLmNzdicpDQpvcmRlcl9wcm9kdWN0c19wcmlvciAgPC0gIGZyZWFkKCdkYXRhL29yZGVyX3Byb2R1Y3RzX19wcmlvci5jc3YnKQ0KYGBgDQoNCmBgYHtyIGVjaG89RkFMU0UsIG1lc3NhZ2U9RkFMU0UsIGV2YWw9RkFMU0V9DQojIGxvYWQgcHJlcGFyZWQgY3N2IGZvciBmYXN0ZXIgcHJvY2Vzc2luZw0KDQojIGNvbnN0cnVjdA0KdHJhaW4uY29uc3RydWN0ID0gZnJlYWQoJ2RhdGFzL3RyYWluLmNvbnN0cnVjdC5jc3YnKQ0KdGVzdC5jb25zdHJ1Y3QgPSBmcmVhZCgnZGF0YS90ZXN0LmNvbnN0cnVjdC5jc3YnKQ0KDQojIGZlYXR1cmVzDQp1c2Vyc19vcmRlcnNfcHJvZHVjdHNfID0gZnJlYWQoJy4vZGF0YXNldHMvdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXy5jc3YnKQ0KdXNlcnNfID0gZnJlYWQoJy4vZGF0YXNldHMvdXNlcnNfLmNzdicpDQpwcm9kdWN0c189IGZyZWFkKCcuL2RhdGFzZXRzL3Byb2R1Y3RzLmNzdicpDQp1c2VyX3Byb2R1Y3RzXyA9IGZyZWFkKCcuL2RhdGFzZXRzL3VzZXJfcHJvZHVjdHNfLmNzdicpDQptMy50cmFpbi5kYXRhID0gZnJlYWQoJy4vZGF0YXNldHMvbTMudHJhaW4uZGF0YS5jc3YnKQ0KbTMudGVzdC5kYXRhID0gZnJlYWQoJy4vZGF0YXNldHMvbTMudGVzdC5kYXRhLmNzdicpDQpgYGANCg0KIyMgRGF0YSBEaWN0aW9uYXJ5DQoNClRoZSBkYXRhc2V0IGZvciB0aGlzIGNvbXBldGl0aW9uIGlzIGEgcmVsYXRpb25hbCBzZXQgb2YgZmlsZXMgZGVzY3JpYmluZyBjdXN0b21lcnMnIG9yZGVycyBvdmVyIHRpbWUuIFRoZXkgYXJlIGFub255bWl6ZWQgYW5kIGNvbnRhaW5zIGEgc2FtcGxlIG9mIG92ZXIgKiozIG1pbGxpb24gZ3JvY2VyeSBvcmRlcnMqKiBmcm9tIG1vcmUgdGhhbiAqKjIwMCwwMDAgSW5zdGFjYXJ0IHVzZXJzKiouIEZvciBlYWNoIHVzZXIsIEluc3RhY2FydCBwcm92aWRlZCAqKmJldHdlZW4gNCBhbmQgMTAwKiogb2YgdGhlaXIgb3JkZXJzLCB3aXRoIHRoZSBzZXF1ZW5jZSBvZiBwcm9kdWN0cyBwdXJjaGFzZWQgaW4gZWFjaCBvcmRlciwgdGhlICoqd2VlayBhbmQgaG91ciBvZiBkYXkqKiB0aGUgb3JkZXIgd2FzIHBsYWNlZCwgYW5kIGEgKipyZWxhdGl2ZSBtZWFzdXJlIG9mIHRpbWUgYmV0d2VlbiBvcmRlcnMqKi4NCg0KVG90YWwgc2l4IGRhdGFzZXRzIHdlcmUgaW1wb3J0ZWQuIEZvbGx3aW5nIHNlY3Rpb24gd2lsbCBleHBsb3JlIGVhY2ggZGF0YXNldHMgaW4gZnVydGhlciBkZXRhaWwuIFRoZXNlIGRhdGFzZXRzIHdlcmUgc291cmNlZCBmcm9tIGFuIGV4aXN0aW5nIEthZ2dsZSBjb21wZXRpdGlvbi4NCg0KYG9yZGVyc2AgKDMuNG0gcm93cywgMjA2ayB1c2Vycyk6ICANCg0KKiBgb3JkZXJfaWRgOiBvcmRlciBpZGVudGlmaWVyICANCiogYHVzZXJfaWRgOiBjdXN0b21lciBpZGVudGlmaWVyICANCiogYGV2YWxfc2V0YDogd2hpY2ggZXZhbHVhdGlvbiBzZXQgdGhpcyBvcmRlciBiZWxvbmdzIGluIChzZWUgYFNFVGAgZGVzY3JpYmVkIGJlbG93KSAgDQoqIGBvcmRlcl9udW1iZXJgOiB0aGUgb3JkZXIgc2VxdWVuY2UgbnVtYmVyIGZvciB0aGlzIHVzZXIgKDEgPSBmaXJzdCwgbiA9IG50aCkgIA0KKiBgb3JkZXJfZG93YDogdGhlIGRheSBvZiB0aGUgd2VlayB0aGUgb3JkZXIgd2FzIHBsYWNlZCBvbiAgDQoqIGBvcmRlcl9ob3VyX29mX2RheWA6IHRoZSBob3VyIG9mIHRoZSBkYXkgdGhlIG9yZGVyIHdhcyBwbGFjZWQgb24gIA0KKiBgZGF5c19zaW5jZV9wcmlvcmA6IGRheXMgc2luY2UgdGhlIGxhc3Qgb3JkZXIsIGNhcHBlZCBhdCAzMCAod2l0aCBOQXMgZm9yIGBvcmRlcl9udW1iZXJgID0gMSkgIA0KDQpgcHJvZHVjdHNgICg1MGsgcm93cyk6ICANCg0KKiBgcHJvZHVjdF9pZGA6IHByb2R1Y3QgaWRlbnRpZmllciAgDQoqIGBwcm9kdWN0X25hbWVgOiBuYW1lIG9mIHRoZSBwcm9kdWN0ICANCiogYGFpc2xlX2lkYDogZm9yZWlnbiBrZXkgIA0KKiBgZGVwYXJ0bWVudF9pZGA6IGZvcmVpZ24ga2V5ICANCg0KYGFpc2xlc2AgKDEzNCByb3dzKTogIA0KDQoqIGBhaXNsZV9pZGA6IGFpc2xlIGlkZW50aWZpZXIgIA0KKiBgYWlzbGVgOiB0aGUgbmFtZSBvZiB0aGUgYWlzbGUgIA0KDQpgZGVwdGFydG1lbnRzYCAoMjEgcm93cyk6ICANCg0KKiBgZGVwYXJ0bWVudF9pZGA6IGRlcGFydG1lbnQgaWRlbnRpZmllciAgDQoqIGBkZXBhcnRtZW50YDogdGhlIG5hbWUgb2YgdGhlIGRlcGFydG1lbnQgIA0KDQpgb3JkZXJfcHJvZHVjdHNfX1NFVGAgKDMwbSsgcm93cyk6ICANCg0KKiBgb3JkZXJfaWRgOiBmb3JlaWduIGtleSAgDQoqIGBwcm9kdWN0X2lkYDogZm9yZWlnbiBrZXkgIA0KKiBgYWRkX3RvX2NhcnRfb3JkZXJgOiBvcmRlciBpbiB3aGljaCBlYWNoIHByb2R1Y3Qgd2FzIGFkZGVkIHRvIGNhcnQgIA0KKiBgcmVvcmRlcmVkYDogMSBpZiB0aGlzIHByb2R1Y3QgaGFzIGJlZW4gb3JkZXJlZCBieSB0aGlzIHVzZXIgaW4gdGhlIHBhc3QsIDAgb3RoZXJ3aXNlICANCg0Kd2hlcmUgYFNFVGAgaXMgb25lIG9mIHRoZSBmb3VyIGZvbGxvd2luZyBldmFsdWF0aW9uIHNldHMgKGBldmFsX3NldGAgaW4gYG9yZGVyc2ApOiAgDQoNCiogYCJwcmlvciJgOiBvcmRlcnMgcHJpb3IgdG8gdGhhdCB1c2VycyBtb3N0IHJlY2VudCBvcmRlciAofjMuMm0gb3JkZXJzKSAgDQoqIGAidHJhaW4iYDogdHJhaW5pbmcgZGF0YSBzdXBwbGllZCB0byBwYXJ0aWNpcGFudHMgKH4xMzFrIG9yZGVycykgIA0KKiBgInRlc3QiYDogdGVzdCBkYXRhIHJlc2VydmVkIGZvciBtYWNoaW5lIGxlYXJuaW5nIGNvbXBldGl0aW9ucyAofjc1ayBvcmRlcnMpICANCg0KIyMgVW5kZXJzdGFuZGluZyBEYXRhc2V0cw0KDQojIyMgQWlzbGVzDQoNClRoZXJlIGFyZSAqKjEzNCBhaXNsZXMqKiBpbiB0aGlzIGRhdGFzZXQuIEhlcmUgYXJlIGZldyBzYW1wbGUgbmFtZXMgb2YgdGhlIGFpbGVzLiAgDQoNCmBgYHtyLCByZXN1bHRzPSdob2xkJ30NCnBhc3RlKHNvcnQoaGVhZChhaXNsZXMkYWlzbGUpKSwgY29sbGFwc2U9JywgJykNCmBgYA0KDQojIyMgRGVwYXJ0bWVudHMNCg0KVGhlcmUgYXJlICoqMjEgZGVwYXJ0bWVudHMqKiBpbiB0aGlzIGRhdGFzZXQuTmFtZXMgb2YgYWxsIGRlcGFybWVudHMgYXJlIGxpc3RlZCBiZWxvdyBpbiBhcGhhYmV0aWNhbGx5IG9yZGVyZWQuDQoNCmBgYHtyLCByZXN1bHRzPSdob2xkJ30NCnBhc3RlKHNvcnQoZGVwYXJ0bWVudHMkZGVwYXJ0bWVudCksIGNvbGxhcHNlID0gJywgJykNCmBgYA0KDQojIyMgUHJvZHVjdHMNCg0KVGhlcmUgYXJlICoqNDksNjg4IHByb2R1Y3RzKiogaW4gdGhlIGNhdGFsb2d1ZSB3aXRoaW4gKioxMzQgYWlzbGVzIGFuZCAyMSBkZXBhcnRtZW50cyoqLiAgDQoNClNhbXBsZSBwcm9kdWN0cyBhcmUgYXMgYmVsb3cuDQoNCmBgYHtyLCByZXN1bHRzPSdob2xkJ30NCnByb2R1Y3RzICU+JSANCiAgaGVhZCAlPiUgDQogIGthYmxlKCkgJT4lIA0KICBrYWJsZV9zdHlsaW5nKGJvb3RzdHJhcF9vcHRpb25zID0gYygic3RyaXBlZCIsICJob3ZlciIpKQ0KYGBgDQoNCiMjIyBEZXBhcnRtZW50cyBBbmQgSXRzIFJlbGV2YW50IFByb2R1Y3RzDQoNClByb2R1Y3RzIGRhdGFmcmFtZSBpcyByZWxhdGVkIHRvIERlcGFybWVudHMuICANCg0KV2Ugc2hhbGwgc2VlIHNhbXBsZSBvZiAzIHByb2R1Y3RzIGZvciBmZXcgZGVwYXJtZW50cy4NCg0KYGBge3IsIHJlc3VsdHM9J2hvbGQnLCBtZXNzYWdlPUZBTFNFfQ0KZGVwYXJ0bWVudHMgJT4lIA0KICBsZWZ0X2pvaW4ocHJvZHVjdHMpICU+JSANCiAgc2VsZWN0KGRlcGFydG1lbnQsIHByb2R1Y3RfbmFtZSkgJT4lDQogIGdyb3VwX2J5KGRlcGFydG1lbnQpICU+JQ0KICBzYW1wbGVfbigzKSAlPiUNCiAgc3VtbWFyaXNlKHRocmVlX2V4YW1wbGVzX3Byb2R1Y3QgPSBwYXN0ZShwcm9kdWN0X25hbWUsIGNvbGxhcHNlID0gJyAvICcpKSAlPiUgDQogIHNhbXBsZV9uKDUpICU+JSANCiAga2FibGUoKSAlPiUgDQogIGthYmxlX3N0eWxpbmcoYm9vdHN0cmFwX29wdGlvbnMgPSBjKCJzdHJpcGVkIiwgImhvdmVyIikpDQpgYGANCg0KIyMjIEFpc2xlcyBBbmQgSXRzIFJlbGV2YW50IFByb2R1Y3RzDQoNClByb2R1Y3RzIGRhdGFmcmFtZSBpcyBhbHNvIHJlbGF0ZWQgdG8gYWlzbGVzLiBFYWNoIGFpc2xlIHJlbGF0ZXMgdG8gbXVsdGlwbGUgcHJvZHVjdHMuIEJ5IGpvaW5pbmcgYm90aCBhaXNsZXMgYW5kIHByb2R1Y3RzIGRhdGFmcmFtZSwgd2UgaGF2ZSBhbiBpZGVhIHdoYXQgdHlwZSBvZiBwcm9kY3V0cyBmb3IgZWFjaCBhaWxlcy4gIA0KDQpFeGFtcGxlIGJlbG93IHNob3dzIDMgc2FtcGxlcyBwcm9kdWN0cyBvZiBmb3IgZmV3IGFpc2xlcy4NCg0KYGBge3IsIHJlc3VsdHM9J2hvbGQnLCBtZXNzYWdlPUZBTFNFfQ0KYWlzbGVzICU+JSANCiAgbGVmdF9qb2luKHByb2R1Y3RzKSAlPiUNCiAgc2VsZWN0KGFpc2xlLCBwcm9kdWN0X25hbWUpICU+JSAgDQogIGdyb3VwX2J5KGFpc2xlKSAlPiUNCiAgc2FtcGxlX24oMykgJT4lIA0KICBzdW1tYXJpc2UodGhyZWVfZXhhbXBsZXNfcHJvZHVjdCA9IHBhc3RlKHByb2R1Y3RfbmFtZSwgY29sbGFwc2UgPSAnIHx8ICcpKSAlPiUgDQogIHNhbXBsZV9uKDUpICU+JSANCiAga2FibGUoKSAlPiUgDQogIGthYmxlX3N0eWxpbmcoYm9vdHN0cmFwX29wdGlvbnMgPSBjKCJzdHJpcGVkIiwgImhvdmVyIikpDQpgYGANCg0KIyMjIE9yZGVycw0KDQpUaGVyZSBhcmUgb3ZlciAqKjMgbWlsbGlvbnMqKiBvYnNlcnZhdGlvbnMgaW4gb3JkZXJzIGRhdGFzZXQuIEVhY2ggcm93IHJlcHJlc2VudCBhbiAqKnVuaXF1ZSBvcmRlcioqLiANCg0KIyMjIyBUcmFpbiBFdmFsX1NldA0KDQpMZXQncyBhbmFseXNlIHRoZSBjb25zdHJ1Y3Qgb2Ygb25lIHVzZXIuIEZvciBleGFtcGxlLCAqKnVzZXJfaWQgMSoqIGhhZCBtYWRlICoqMTAgcHJpb3Igb3JkZXJzKiogKG9yZGVyIG51bWJlciBmcm9tIDEgdG8gMTApLCBsYXN0IG9yZGVyIGlzIGEgKip0cmFpbioqIChldmFsX3NldCkuIE5vdGUgdGhhdCB0aGUgZmlyc3Qgb3JkZXIgKG9yZGVyX251bWJlciAxKSBkb2VzIG5vdCBoYXZlIHZhbHVlIGZvciBkYXlfc2luY2VfcHJpb3Jfb3JkZXIsIGFzIGl0IGlzIHRoZSBmaXJzdCBvcmRlciB3aXRob3V0IHByaW9yIHJlY29yZHMuICANCg0KVGhpcyBhbHNvIG1lYW5zICoqYDx1c2VyX2lkLCBwcm9kdWN0X2lkPmAqKiBtYWRlIHVwIHRoZSAqKmtleSoqIGZvciBwcmVkaWN0aW9uLiAgDQoNCmBgYHtyfQ0Kb3JkZXJzICU+JSANCiAgZmlsdGVyKHVzZXJfaWQgPT0gMSkgJT4lIA0KICBrYWJsZSgpICU+JQ0KICBrYWJsZV9zdHlsaW5nKGJvb3RzdHJhcF9vcHRpb25zID0gYygic3RyaXBlZCIsICJob3ZlciIpKQ0KYGBgDQojIyMjIFRlc3QgRXZhbF9TZXQNCg0KTGV0J3MgYW5hbHlzZSBhbm90aGVyIGNvbnN0cnVjdCBvZiBvcmRlcnMuICoqVXNlcl9pZCAzKiogaGFkIG1hZGUgKioxMiBvcmRlcnMqKiBiZWZvcmUgdGhlIGZpbmFsIG9yZGVyIGxhYmVsZWQgYXMgKip0ZXN0KiogKGV2YWxfc2V0KSBvcmRlci4gRnJvbSB0aGUgZGF0YSB3ZSBrbm93IHRoYXQgb3JkZXJfbnVtYmVyIGlzIGJlaW5nIHJlY3ljbGVkIGZvciBlYWNoIHVzZXIuICANCg0KKipJbnN0YWNhcnQgZGlkIG5vdCBwcm92aWRlIHVzIHRoZSBiYXNrZXQgY29udGVudCBmb3IgdGVzdCBvcmRlcioqLiBUaGlzIGlzIGluIGZhY3QgdGhlICoqdGFyZ2V0IGZvciBwcmVkaWN0aW9uKiouIA0KDQpgYGB7cn0NCm9yZGVycyAlPiUgDQogIGZpbHRlcih1c2VyX2lkID09IDMpICU+JSANCiAga2FibGUoKSAlPiUNCiAga2FibGVfc3R5bGluZyhib290c3RyYXBfb3B0aW9ucyA9IGMoInN0cmlwZWQiLCAiaG92ZXIiKSkNCmBgYA0KDQojIyMgT3JkZXJfUHJvZHVjdA0KDQpFYWNoIG9yZGVyIGNvbnRhaW4gbXVsdGlwbGUgcHJvZHVjdHMgcHVyY2hhc2VkIGJ5IHVzZXIuIEluc3RhY2FydCBoYWQgY2xlYW5seSBjYXRlZ29yaXplZCB0aGUgb3JkZXJzIGludG8gJ3RyYWluJyBhbmQgJ3ByaW9yJyBpbiAqKlNJTkdMRSoqIG9yZGVyIGRhdGFzZXQuDQoNCkhvd2V2ZXIsIHRoZSBkZXRhaWwgb2YgZWFjaCBvcmRlcnMgYXJlIHNwbGl0dGVkIGludG8gdHdvIGRhdHNldHM6ICANCi0gKipgb3JkZXJfcHJvZHVjdF90cmFpbmAqKjogY29udGFpbiBvbmx5IGRldGFpbCBwcm9kdWN0IGl0ZW1zIG9mIGxhc3Qgb3JkZXIgIA0KLSAqKmBvcmRlcl9wcm9kdWN0X3ByaW9yYCoqOiBjb250YWluIGRldGFpbCBwcm9kdWN0IGl0ZW1zIG9mIGFsbCBwcmlvciBvcmRlcnMgIA0KDQojIyMgT3JkZXJfUHJvZHVjdF9UcmFpbg0KDQoqKm9yZGVyX3Byb2R1Y3RfdHJhaW4vcHJpb3IqKiBkYXRhZnJhbWUgdGVsbHMgdXMgd2hpY2ggcHJvZHVjdHMgd2VyZSBwdXJjaGFzZWQgYXQgZWFjaCBvcmRlcjsgZm9yIGJvdGggKip0cmFpbioqIGFuZCAqKnByaW9yKiogb3JkZXIuICANCg0KRm9yIGV4YW1wbGUsIHdlIGtub3cgKip1c2VyX2lkIDEqKiBpbiB0aGUgKipMQVNUIE9SREVSKiogKG9yZGVyX2lkIDExODc4OTkpIHB1cmNoYXNlZCAqKjEwIHVuaXF1ZSBwcm9kdWN0cyoqIGJ5ICoqcXVlcmluZyBvcmRlcl9wcm9kdWN0X3RyYWluKiogd2l0aCB0aGUgcmVsZXZhbnQgb3JkZXJfaWQuICANCg0KYGBge3J9DQpvcmRlcl9wcm9kdWN0c190cmFpbiAlPiUgDQogIGZpbHRlciAob3JkZXJfaWQgPT0gMTE4Nzg5OSkgJT4lIA0KICBrYWJsZSgpICU+JSANCiAga2FibGVfc3R5bGluZyhib290c3RyYXBfb3B0aW9ucyA9IGMoInN0cmlwZWQiLCAiaG92ZXIiKSkNCmBgYA0KDQojIyMgT3JkZXJfUHJvZHVjdF9UcmFpbl9Qcmlvcg0KDQpTaW1pbGFyeSwgZGV0YWlsIGl0ZW1zIGZvciBhICoqUFJJT1IgT1JERVIqKiAoZXhhbXBsZSBvcmRlcl9pZDogMjU1MDM2MikgY2FuIGJlIHJldGlyZXZlZCBieSBxdWVyaW5nIGRpZmZlcmVudCBkYXRhc2V0IG9yZGVyX3Byb2R1Y3RfcHJpb3IuDQoNCmBgYHtyfQ0Kb3JkZXJfcHJvZHVjdHNfcHJpb3IgJT4lIA0KICBmaWx0ZXIob3JkZXJfaWQgPT0gMjU1MDM2MikgJT4lIA0KICBrYWJsZSgpICU+JSANCiAga2FibGVfc3R5bGluZyhib290c3RyYXBfb3B0aW9ucyA9IGMoInN0cmlwZWQiLCAiaG92ZXIiKSkNCmBgYA0KDQojIyMgVXNlcnMNCg0KVGhlciBpcyBubyBkZWRpY2F0ZWQgZGF0YWZyYW1lIGZvciB1c2Vycy4gSG93ZXZlciwgd2UgY2FuIGRlcml2ZSBudW1iZXIgb2YgdW5pcXVlIHVzZXJzIGZyb20gKipvcmRlcioqIGRhdGFmcmFtZS4gQnkgZ3JvdXBpbmcgdGhlIHVzZXJfaWQgYW5kIGV2YWxfc2V0IGNvbHVtbiwgd2UgZm91bmQgdGhhdCB0aGVyZSBhcmUgKio3NSwwMDAgdGVzdCoqIHVzZXJzLCAqKjEzMSwyMDkgdHJhaW4qKiB1c2Vycy4gIA0KDQpgYGB7cn0NCm9yZGVycyAlPiUgDQogIGZpbHRlcihldmFsX3NldCAlaW4lIGMoJ3RyYWluJywgJ3Rlc3QnKSApICU+JQ0KICBjb3VudChldmFsX3NldCkgJT4lDQogIG11dGF0ZShwZXJjZW50YWdlID0gbi9zdW0obikpICU+JQ0KICBrYWJsZSgpICU+JSANCiAga2FibGVfc3R5bGluZyhib290c3RyYXBfb3B0aW9ucyA9IGMoInN0cmlwZWQiLCAiaG92ZXIiKSkNCmBgYA0KDQoNCiMgRXhwbG9yYXRvcnkgRGF0YSBBbmFseXNpcw0KDQpJbiB0aGlzIHNlY3Rpb24sIHdlIHNoYWxsIHRyeSB0byB1bmRlcnN0YW5kIHRoZSBidXlpbmcgYmVoYXZpb3VyIGJ5IGFza2luZyBzb21lIGludGVyZXN0aW5nIHF1ZXNpdG9ucy4gIA0KDQotIFdoYXQgdXN1YWxseSBkb2VzIHBlb3BsZSBidXksIGFuZCB3aGljaCBvbmUgdGhleSB1c3VhbGx5IHJlb3JkZXINCi0gV2hlbiBkbyB0aGV5IGJ1eSAoZGF5IGFuZCB0aW1lKT8gSXMgdGhlcmUgYSBidXlpbmcgdHJlbmQgYW5kIGRvZXMgaXQgaW5mbHVlbmNlIHdoYXQgdGhleSBidXkgPyAgDQoNClRvIHJlZHVjZSBvdXIgY29kaW5nIHN0ZXBzLCB3ZSBjb25zdHJ1Y3QgYSByZXVzYWJsZSBkYXRhZnJhbWUgY29tYmluaW5nIGFsbCBkZXRhaWxzIGZyb20gb3JkZXJzIGFuZCBpdHMgcHJvZHVjdHMuIFRoaXMgZGF0YWZyYW1lIHdpbGwgY29udGFpbiByb3dzIGZvciAqKnByaW9yIG9yZGVycyBhbmQgcHJvZHVjdHMgb25seSoqIChleGNsdWRpbmcgbGFzdCBvcmRlciB3aGljaCBpcyBsYWJlbGVkIGFzIGB0cmFpbmApLiANCg0KYGBge3J9DQp1c2Vyc19vcmRlcnNfcHJvZHVjdHNfIDwtIG9yZGVycyAlPiUNCiAgaW5uZXJfam9pbihvcmRlcl9wcm9kdWN0c19wcmlvcikgJT4lICAjIGlubmVyX2pvaW4gd2l0aCBwcmlvciB0YWJsZSB3aWxsIGZpbHRlciBvdXQgdHJhaW4gb3JkZXJzDQogIGxlZnRfam9pbihwcm9kdWN0cykgJT4lDQogIGxlZnRfam9pbihhaXNsZXMpICU+JQ0KICBsZWZ0X2pvaW4oZGVwYXJ0bWVudHMpICU+JQ0KICBhcnJhbmdlKHVzZXJfaWQsIG9yZGVyX251bWJlcikgJT4lDQogIHNlbGVjdCh1c2VyX2lkLCBvcmRlcl9pZCwgb3JkZXJfbnVtYmVyLCBvcmRlcl9kb3csIG9yZGVyX2hvdXJfb2ZfZGF5LCBkYXlzX3NpbmNlX3ByaW9yX29yZGVyLCBwcm9kdWN0X2lkLCBwcm9kdWN0X25hbWUsIHJlb3JkZXJlZCwgYWRkX3RvX2NhcnRfb3JkZXIsIGRlcGFydG1lbnRfaWQsIGFpc2xlX2lkLCBkZXBhcnRtZW50LCBhaXNsZSkNCmBgYA0KDQoNCiMjIE9yZGVycw0KDQojIyMgSG93IE1hbnkgT3JkZXJzID8NCg0KTW9zdCB1c2VycyBtYWRlIGZldyBvcmRlcnMuIFRoZSBudW1iZXIgb2Ygb3JkZXJzIGEgdXNlcnMgbWFkZSBkZWNyZWFzZSBzaWduaWZpY2FsbHkgYWxvbmcgdGhlIG9yZGVyIG51bWJlcnMuIE1heGltdW0gb3JkZXJzIGFueSB1c2VycyBoYWQgbWFkZSBpcyA5OS4NCg0KYGBge3IgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0yLjV9DQp0bXAgPC0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUgDQogIGdyb3VwX2J5KHVzZXJfaWQpICU+JSANCiAgc3VtbWFyaXplKG5fb3JkZXJzID0gbWF4KG9yZGVyX251bWJlcikpDQoNCnRtcCAlPiUgDQogIGdncGxvdChhZXMoeCA9IGFzLmZhY3RvcihuX29yZGVycykpKSArIA0KICBnZW9tX2JhcigpICsNCiAgbGFicyh5ID0gJ0NvdW50IG9mIFVzZXJzJywNCiAgICAgICB4ID0gJ051bWJlciBvZiBPcmRlcnMgTWFkZSBCeSBVc2VycycpICsNCiAgdGhlbWUoDQogICAgICBheGlzLnRleHQueCAgPSBlbGVtZW50X3RleHQgKHNpemUgPSA2LjAsIGFuZ2xlID0gKDkwKSwgaGp1c3QgPSAxLCB2anVzdCA9IDAuNSkNCiAgICApDQpgYGANCiMjIyBIb3cgU29vbiBVbnRpbCBOZXh0IE9yZGVyID8NCg0KSXQgaXMgdmVyeSBvYnZpb3VzIHRoYXQgbW9zdCB1c2VycyBtYWRlIHRoZWlyIG9yZGVycyAqKndlZWtseSAoZXZlcnkgNyBkYXlzKSBhbmQgbW9udGhseSAoZXZlcnkgMzAgZGF5cykqKi4gU2VlIHRoZSBwZWFrIG9mIGRheSA3IGFuZCBkYXkgMzAgaW4gdGhlIGNoYXJ0IGJlbG93LiANCg0KYGBge3IgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0yLjV9DQp0bXAgIDwtICB1c2Vyc19vcmRlcnNfcHJvZHVjdHNfICU+JSANCiAgZmlsdGVyKG9yZGVyX251bWJlciA+IDEpICU+JSAjIGRheXNfc2luY2VfcHJpb3IgaXMgTkEgZm9yIGZpcnN0IG9yZGVyLCBuZWVkIHRvIGZpbHRlciBvdXQNCiAgZ3JvdXBfYnkob3JkZXJfaWQpICU+JSANCiAgICBzdW1tYXJpemUobl9vcmRlcnMgPSBtYXgoZGF5c19zaW5jZV9wcmlvcl9vcmRlcikpDQoNCnRtcCAlPiUgDQogIGdncGxvdChhZXMoeCA9IGFzLmZhY3RvcihuX29yZGVycykpKSArIA0KICBnZW9tX2JhcigpICsgDQogIGxhYnMoeSA9ICdDb3VudCBvZiBPcmRlcnMnLCANCiAgICAgICB4ID0gJ0RheXMgU2luY2UgUHJpb3IgRm9yIEVhY2ggT3JkZXInKQ0KYGBgDQoNCiMjIE9yZGVyc19Qcm9kdWN0cw0KDQojIyMgTW9zdCBQb3B1bGFyIFByb2R1Y3RzIFNvbGQNCg0KV2Uga25vdyB0aGF0ICoqYmFuYW5hKiogYXJlIHRoZSBtb3N0IHBvcHVsYXIgcHJvZHVjdHMuIFRoZSBudW1iZXIgb2Ygb3JkZXJzIHZhcmllcyBncmVhdGx5IGZvciBkaWZmZXJlbnQgcHJvZHVjdHMuIElsbHVzdHJhdGlvbiBiZWxvdyB1c2VzIHNob3dzIHNhbXBsZSBvZiBvbmx5ICoqMzAgdG9wIHByb2R1Y3RzKiouICBOb3RpY2UgaG93ZXZlciB0aGUgdmFyaWVuY2UgaXMgbm90IG9idmlvdXMgb3V0c2lkZSB0b3AgMTAgcHJvZHVjdHMuDQoNCmBgYHtyLCBmaWcud2lkdGg9OS41LCBmaWcuaGVpZ2h0PTMuNX0NCnRtcCA8LSBvcmRlcl9wcm9kdWN0c190cmFpbiAlPiUNCiAgbGVmdF9qb2luKHByb2R1Y3RzKSAlPiUNCiAgZ3JvdXBfYnkocHJvZHVjdF9uYW1lKSAlPiUNCiAgc3VtbWFyaXplKGNvdW50ID0gbigpKSAlPiUNCiAgdG9wX24obiA9IDMwLCB3dCA9IGNvdW50KSAlPiUgIA0KICBtdXRhdGUocGVyY2VudGFnZSA9IGNvdW50L3N1bShjb3VudCkpDQoNCnAxIDwtIHRtcCAlPiUgDQogIGdncGxvdChhZXMoeCA9IHJlb3JkZXIocHJvZHVjdF9uYW1lLCBjb3VudCksIHkgPSBwZXJjZW50YWdlKSkgKyAgDQogIGdlb21fY29sKCkgKyANCiAgbGFicyh0aXRsZSA9ICdQcm9kdWN0cyBUb3AgMzAnLA0KICAgICAgIHkgPSAnUGVyY2VudGFnZSBvZiBPcmRlcnMnKSArDQogIHRoZW1lICgNCiAgICBheGlzLnRleHQueD1lbGVtZW50X3RleHQoYW5nbGU9OTAsIGhqdXN0PTEsIHZqdXN0PTAuNSksDQogICAgYXhpcy50aXRsZS54ID0gZWxlbWVudF9ibGFuaygpKSANCg0KcDIgPC0gdG1wICU+JSANCiAgZ2dwbG90KGFlcyh4ID0gJycsIHkgPSBwZXJjZW50YWdlKSkgKyANCiAgbGFicyh0aXRsZSA9ICdQcm9kdWN0cyBUb3AgMzAnLA0KICAgICAgIHkgPSAncGVyY2VudGFnZS5vZi5vcmRlcnMnLA0KICAgICAgIHggPSAnUHJvZHVjdHMnKSArIA0KICBnZW9tX2JveHBsb3QoKQ0KDQpncmlkLmFycmFuZ2UocDEsIHAyLCBuY29sID0gMikNCmBgYA0KYGBge3IgZWNobz1GQUxTRX0NCnJtKGxpc3QgPSBjKCd0bXAnLCdwMScsJ3AyJykpDQpgYGANCg0KIyMjIE1vc3QgUG9wdWxhciBEZXBhcnRtZW50IFNvbGQNCg0KQ2VydGFpbiBkZXBhcnRtZW5zIGFyZSBjbGVhcmx5IG1vcmUgcG9wdWxhciwgbGlrZSAqKnByb2R1Y2UgYW5kIGRhaXJ5IGVnZ3MqKi4gQm90aCBkZXBhcm1lbnRzIGNvbWJpbmVkIGNvbnRyaWJ1dGVkIHRvICoqbW9yZSB0aGFuIDQwJSoqIG9mIHRvdGFsIG9yZGVycy4NCg0KYGBge3IsIGZpZy53aWR0aD05LjUsIGZpZy5oZWlnaHQ9My41fQ0KdG1wIDwtIHVzZXJzX29yZGVyc19wcm9kdWN0c18gJT4lDQogIGdyb3VwX2J5KGRlcGFydG1lbnQpICU+JQ0KICBzdW1tYXJpemUoY291bnQgPSBuKCkpICU+JQ0KICBtdXRhdGUocGVyY2VudGFnZSA9IGNvdW50L3N1bShjb3VudCkpDQoNCnAxIDwtIHRtcCAlPiUgDQogIGdncGxvdCAoYWVzKHggPSByZW9yZGVyKGRlcGFydG1lbnQsIGNvdW50KSwgeSA9IHBlcmNlbnRhZ2UpKSArICANCiAgZ2VvbV9jb2woKSArIA0KICBsYWJzKHRpdGxlID0gJ0RlcGFydG1lbnRzJywgeSA9ICdQZXJjZW50YWdlIG9mIE9yZGVycycpICsNCiAgdGhlbWUgKA0KICAgIGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIGhqdXN0ID0gMSwgdmp1c3QgPSAwLjUpLA0KICAgIGF4aXMudGl0bGUueCA9IGVsZW1lbnRfYmxhbmsoKSkgDQoNCnAyIDwtIHRtcCAlPiUgDQogIGdncGxvdChhZXMoeCA9ICcnLCB5ID0gcGVyY2VudGFnZSApKSArIA0KICBsYWJzKHRpdGxlID0gJ0RlcGFydG1lbnRzJywNCiAgICAgICB5ID0gJ3BlcmNlbnRhZ2Uub2Yub3JkZXJzJywNCiAgICAgICB4ID0gJ0RlcGFydG1lbnRzJykgKyANCiAgZ2VvbV9ib3hwbG90KCkNCg0KZ3JpZC5hcnJhbmdlKHAxLCBwMiwgbmNvbCA9IDIpDQpgYGANCg0KYGBge3IgZWNobz1GQUxTRX0NCnJtKGxpc3QgPSBjKCd0bXAnLCAncDEnLCAncDInKSkNCmBgYA0KDQojIyMgTW9zdCBQb3B1bGFyIEFpc2xlcyBTb2xkDQoNCldlIGxvb2tlZCBpbnRvIHRoZSBidXlpbmcgdHJlbmQgb2YgcHJvZHVjdCBieSBhaXNsZXMgYW5kIG5vdGljZSB0aGF0IGNlcnRhaW4gYWlzbGUgbGlrZSAqKnZlZ2V0YWJsZXMgYW5kIGZydWl0cyoqIGNvbnRyaWJ1dGVzIHRvICoqYWxtb3N0IDMwJSoqIG9mIHRvdGFsIG9yZGVycy4gQ2hhcnQgYmVsb3cgc2hvd3MgdG9wIDMwIGFpc2xlcy4NCg0KYGBge3IsIGZpZy53aWR0aD05LjUsIGZpZy5oZWlnaHQ9My41fQ0KdG1wIDwtIHVzZXJzX29yZGVyc19wcm9kdWN0c18gJT4lDQogIGdyb3VwX2J5KGFpc2xlKSAlPiUNCiAgc3VtbWFyaXplKGNvdW50ID0gbigpKSAlPiUNCiAgdG9wX24obiA9IDMwLCB3dCA9IGNvdW50KSAlPiUgIA0KICBtdXRhdGUocGVyY2VudGFnZSA9IGNvdW50L3N1bShjb3VudCkpDQoNCnAxIDwtIHRtcCAlPiUgDQogIGdncGxvdChhZXMoeCA9IHJlb3JkZXIoYWlzbGUsIGNvdW50KSwgeSA9IHBlcmNlbnRhZ2UpKSArICANCiAgZ2VvbV9jb2woKSArIA0KICBsYWJzKHRpdGxlID0gJ0Fpc2xlcyBUb3AgMzAnLA0KICAgICAgIHggPSAnQWlzbGVzJywNCiAgICAgICB5ID0gJ1BlcmNlbnRhZ2Ugb2YgT3JkZXJzJykgKw0KICB0aGVtZShheGlzLnRleHQueD1lbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgaGp1c3QgPSAxLCB2anVzdCA9IDAuNSksDQogICAgICAgIGF4aXMudGl0bGUueCA9IGVsZW1lbnRfYmxhbmsoKSkNCg0KcDIgPC0gdG1wICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSAnJywgeSA9IHBlcmNlbnRhZ2UgKSkgKyANCiAgZ2VvbV9ib3hwbG90KCkgKw0KICBsYWJzKHRpdGxlID0gJ0Fpc2xlcyBUb3AgMzAnLA0KICAgICAgIHkgPSAncGVyY2VudGFnZS5vZi5vcmRlcnMnLA0KICAgICAgIHggPSAnQWlzbGVzJykNCg0KZ3JpZC5hcnJhbmdlKHAxLCBwMiwgbmNvbCA9IDIpDQpgYGANCg0KYGBge3IgZWNobz1GQUxTRX0NCnJtKGxpc3QgPSBjKCd0bXAnLCAncDEnLCAncDInKSkNCmBgYA0KDQojIyMgUHJvZHVjdHMgT3JkZXJlZCBEYXkgUGF0dGVybg0KDQpXZSBjYW4gc2VlIHRoYXQgYm90aCAqKkRheSAwIGFuZCBEYXkgMSoqIHN0YW5kcyBvdXQgdG8gYmUgdGhlIG1vc3QgYnVzeSBzaG9wcGluZyBkYXkgZm9yIGluc3RhY2FydC4gVGhpcyBtZWFucyB0aGF0IGRheSBvZiBvcmRlciBtYWRlIG1heSBpbmZsdWVuY2UgdGhlIGJhc2tldCBzaXplLg0KDQpgYGB7ciwgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0zLjB9DQp1c2Vyc19vcmRlcnNfcHJvZHVjdHNfICU+JQ0KICBncm91cF9ieShvcmRlcl9kb3cpICU+JQ0KICBzdW1tYXJpemUoY291bnQgPSBuKCkpICU+JQ0KICBtdXRhdGUocGVyY2VudGFnZSA9IGNvdW50L3N1bShjb3VudCkpICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSBhcy5mYWN0b3Iob3JkZXJfZG93KSwgeSA9IHBlcmNlbnRhZ2UsIGZpbGwgPSBhcy5mYWN0b3Iob3JkZXJfZG93KSkpICsgDQogIGdlb21fY29sKCkgKyANCiAgbGFicyh0aXRsZSA9ICdEYWlseSBPcmRlcnMnLCB5ID0gJ1BlcmNlbnRhZ2Ugb2YgT3JkZXJzJykgDQpgYGANCg0KV2hlbiB3ZSB6b29tIGludG8gZGFpbHkgb3JkZXJzLCB3ZSBub3RpY2UgdGhhdCB0b3AgdGVuIHByb2R1Y3RzIGNvbnRyaWJ1dGVzIGJldHdlZW4gNyUgdG8gOCUgb2YgZGFpbHkgb3JkZXJzLiBJdCBpcyBpbnRlcmVzdGluZyB0byBzZWUgdGhhdCBMaW1lcyBhcmUgcGFydCBvZiB0b3AgdGVuIGZvciBEYXkgMCBhbmQgRGF5IDYsIGJ1dCBub3Qgb3RoZXIgZGF5cy4gV2hlcmVhcyBPcmdhbmljIFdob2xlIE1pbGsgZG9lc24ndCBtYWtlIGl0IHRvIHRvcCB0ZW4gZm9yIERheSAwLiBPcmdhbmljIFJlc3BiZXJyaWVzIGRvZXMgbm90IG1ha2UgaXQgdG8gdG9wIDEwIG9mIERheSA2LiBUaGlzIG1lYW5zIHRoYXQgdGhlcmUgaXMgYSBjaGFuY2Ugb2YgcHJlZGljdGFiaWxpdHkgYmFzZWQgb24gdGhlIGRheSBvcmRlciBpcyBtYWRlLiANCg0KYGBge3IsIGZpZy53aWR0aD05LjMsIGZpZy5oZWlnaHQ9NC41fQ0KdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyU+JQ0KICBncm91cF9ieShvcmRlcl9kb3csIHByb2R1Y3RfbmFtZSkgJT4lDQogIHN1bW1hcml6ZShuID0gbigpKSAlPiUNCiAgbXV0YXRlKHBlcmNlbnRhZ2UgPSBuL3N1bShuKSkgJT4lDQogIHRvcF9uKDEwLCB3dCA9IG4pICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSBhcy5mYWN0b3Iob3JkZXJfZG93KSwgeSA9IHBlcmNlbnRhZ2UsIGZpbGwgPSBwcm9kdWN0X25hbWUpKSArIA0KICBnZW9tX2NvbCgpICsgDQogIGxhYnMoeSA9ICdQcm9wcnRpb24gb2YgT3JkZXJzIEluIEEgRGF5JywNCiAgICAgICB0aXRsZSA9ICdEYWlseSBUb3AgMTAgUHJvZHVjdHMgT3JkZXJlZCcpICsNCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gImJvdHRvbSIsIGxlZ2VuZC5kaXJlY3Rpb24gPSAiaG9yaXpvbnRhbCIpDQpgYGANCg0KIyMjIFByb2R1Y3RzIE9yZGVyZWQgSG91ciBQYXR0ZXJuDQoNCk1vcm5pbmcgdG8gYWZ0ZXJub29uIGFyZSB0aGUgcGVhayBzaG9wcGluZyBob3VycyBmb3IgaW5zdGFjYXJ0IGN1c3RvbWVycy4gVGhlIGhvdXIgb3JkZXIgbWFkZSBpbmZsdWVuY2VzIGJhc2tldCBzaXplLg0KDQpgYGB7ciwgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0zLjB9DQp1c2Vyc19vcmRlcnNfcHJvZHVjdHNfICU+JQ0KICBncm91cF9ieShvcmRlcl9ob3VyX29mX2RheSkgJT4lDQogIHN1bW1hcml6ZShjb3VudCA9IG4oKSkgJT4lDQogIG11dGF0ZShwZXJjZW50YWdlID0gY291bnQvc3VtKGNvdW50KSkgJT4lDQogIGdncGxvdChhZXMoeCA9IGFzLmZhY3RvcihvcmRlcl9ob3VyX29mX2RheSksIHkgPSBwZXJjZW50YWdlKSkgKyANCiAgZ2VvbV9jb2woKSArIA0KICBsYWJzKHkgPSAnUGVyY2VudGFnZSBvZiBPcmRlcnMnLA0KICAgICAgIHRpdGxlID0gJ0hvdXJseSBPcmRlcnMnKQ0KYGBgDQoNCkluIHRoZSBncm9jZXJ5LCB0aGVyZSBhcmUgY2xvc2UgdG8gNTAsMDAwIHByb2R1Y3RzLiBXaGVuIHdlIHpvb20gaW50byBob3VybHkgcHVyY2hhc2VzLCB3ZSBub3RpY2VkIHRoYXQgdG9wIDEwIHByb2R1Y3RzIG1hbmFnZWQgdG8gc2NvcmUgYmV0d2VuIDYlIHRvIDglIG9mIGhvdXJseSBzYWxlcy4gRXZlcnkgaG91ciBoYXMgc2xpZ2h0bHkgZGlmZnJlbnQgY29tYmluYXRpb24gb2YgdG9wIDEwIHByb2R1Y3RzIChjb21iaW5hdGlvbiBvdXQgb2YgMTIgcHJvZHVjdHMpLiBUaGF0IG1lYW5zIGNlcnRhaW4gcHJvZHVjdHMgYXJlIHByZWRpY3RhYmxlIGZvciBvcmRlcmluZyBpcnJlZ2FyZGxlc3Mgb2YgdGhlIGhvdXIgb2Ygb3JkZXIuICANCg0KSXQgaXMgaW50ZXJlc3RpbmcgdG8ga25vdyB0aGF0LCBzaW1pbGFyIHRvIGRhaWx5IHRvcCAxMCBwcm9kdWN0cywgdGhlIE9yZ2FuaWMgV2hvbGVtaWxrIGFuZCBMaW1lcyBpcyBtaXNzaW5nIGFzIHRvcCAxMCBmcm9tIHNvbWUgaG91cnMuICANCg0KYGBge3IsIGZpZy53aWR0aD05LjMsIGZpZy5oZWlnaHQ9NX0NCnVzZXJzX29yZGVyc19wcm9kdWN0c18gJT4lDQogIGdyb3VwX2J5KG9yZGVyX2hvdXJfb2ZfZGF5LCBwcm9kdWN0X25hbWUpICU+JQ0KICBzdW1tYXJpemUobiA9IG4oKSkgJT4lDQogIG11dGF0ZShwZXJjZW50YWdlID0gbi9zdW0obikpICU+JQ0KICB0b3BfbigxMCwgd3QgPSBuKSAlPiUNCiAgZ2dwbG90IChhZXMoeCA9IGFzLmZhY3RvcihvcmRlcl9ob3VyX29mX2RheSksIHkgPSBwZXJjZW50YWdlLCBmaWxsID0gcHJvZHVjdF9uYW1lKSkgKyANCiAgZ2VvbV9jb2woKSArIA0KICBsYWJzKHkgPSAnUHJvcHJ0aW9uIG9mIE9yZGVycyBJbiBBIEhvdXInLA0KICAgICAgIHRpdGxlID0gJ0hvdXJseSBUb3AgMTAgUHJvZHVjdHMgT3JkZXJlZCcpICsNCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gImJvdHRvbSIsIGxlZ2VuZC5kaXJlY3Rpb24gPSAiaG9yaXpvbnRhbCIpDQpgYGANCg0KDQojIyBCYXNrZXQgQW5hbHlzaXMNCg0KIyMjIEJhc2tldCBTaXplIERpc3RyaWJ1dGlvbg0KDQpOdW1iZXIgb2YgaXRlbXMgaW4gYWxsIG9yZGVycyByYW5nZSBmcm9tIDEgdG8gMTQ1LiBUaGUgaGlzdG9ncmFtIGJlbG93IGlzIGhpZ2hseSAqKnNrZXdlZCB0b3dhcmRzIHNtYWxsIGJhc2tldCBzaXplKiouIE1ham9yaXR5IG9mIHVzZXJzIHB1cmNoYXNlZCA1IGl0ZW1zIGluIHRoZWlyIG9yZGVycy4NCg0KYGBge3IgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0zfQ0KdG1wIDwtIHVzZXJzX29yZGVyc19wcm9kdWN0c18gJT4lDQogIGdyb3VwX2J5KG9yZGVyX2lkKSAgJT4lDQogIHN1bW1hcml6ZShiYXNrZXRfc2l6ZSA9IG4oKSwgDQogICAgICAgICAgICByZW9yZGVyZWRfaXRlbXMgPSBzdW0ocmVvcmRlcmVkKSkgJT4lDQogIGdyb3VwX2J5KGJhc2tldF9zaXplKSAlPiUNCiAgc3VtbWFyaXplKG4gPSBuKCksIGF2Z19yZW9yZGVyZWRfaXRlbXMgPSBtZWFuKHJlb3JkZXJlZF9pdGVtcykpICU+JQ0KICBhcnJhbmdlKGJhc2tldF9zaXplKQ0KICANCnRtcCAlPiUgDQogIGdncGxvdChhZXMoeCA9IGFzLmZhY3RvcihiYXNrZXRfc2l6ZSkpKSArDQogIGdlb21fY29sKGFlcyh5ID0gbikpICsNCiAgbGFicyh5ID0gJ09yZGVyIENvdW50JywNCiAgICAgICB4ID0gJ051bWJlciBvZiBJdGVtcyBpbiBCYXNrZXQnLA0KICAgICAgIHRpdGxlID0gJ0Jhc2tldCBTaXplIERpc3RyaWJ1dGlvbicpICsNCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoc2l6ZSA9IDYuMCwgYW5nbGUgPSA5MCwgaGp1c3QgPSAxLCB2anVzdCA9IDAuNSkpDQpgYGANCg0KDQojIyBSZS1PcmRlcmVkIEFuYWx5c2lzDQoNCkFuYWx5emluZyB0aGUgcmUtb3JkZXJlZCBwcm9kdWN0cyBpcyB0aGUgbW9zdCBpbXBvcnRhbnQgcGFydCBvZiB0aGUgRURBLiBUaGlzIGlzIGJlY2FzdWUgaW5zaWdodHMgZnJvbSB0aGlzIGFuYWx5c2lzIGNhbiBoZWxwIHRvIGRldmVsb3AgaW50dWl0aW9uIGZvciBmdXJodGVyIGZlYXR1cmUgZW5naW5lZXJpbmcgdGhhdCB3aWxsIG1ha2UgdGhlIHByZWRpY3Rpb24gbW9yZSBtZWFuaW5nZnVsLg0KDQojIyMgQXZlcmFnZSBSZS1vcmRlcmVkIEl0ZW1zIEluIEJhc2tldCBEaXN0cmlidXRpb24NCg0KYGBge3IgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0zfQ0KdG1wICU+JSANCiAgZ2dwbG90KGFlcyh4ID0gYXMuZmFjdG9yKGJhc2tldF9zaXplKSkpICsgDQogIGdlb21fcG9pbnQoYWVzKHkgPSBhdmdfcmVvcmRlcmVkX2l0ZW1zKSwgY29sb3IgPSAncmVkJykgKw0KICBsYWJzKHkgPSAnQXZnIE51bWJlciBvZiBSZS1PcmRlcmVkIEl0ZW1zJywNCiAgICAgICB4ID0gJ051bWJlciBvZiBJdGVtcyBpbiBCYXNrZXQnLA0KICAgICAgIHRpdGxlID0gJ1Jlb3JkZXIgUmF0ZSBieSBCYXNrZXQgU2l6ZScpICsNCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoc2l6ZSA9IDYuMCwgYW5nbGUgPSA5MCwgaGp1c3QgPSAxLCB2anVzdCA9IDAuNSkpICsNCiAgZ2VvbV9hYmxpbmUoaW50ZXJjZXB0ID0gMCwgc2xvcGUgPSAxLCBjb2xvciA9ICdibHVlJykNCmBgYA0KDQojIyMgUHJvZHVjdCBSZW9yZGVyIFJhdGlvDQoNCk9uZSBvZiB0aGUgdHJpY2tlciB0aGluZ3MgdG8gcHJlZGljdCBpbiB0aGUgSW5zdGFjYXJ0IGRhdGFzZXQgaXMgdGhlIGluY2lkZW5jZSBvZiBvcmRlcnMgd2l0aG91dCByZW9yZGVyZWQgcHJvZHVjdHMuIFBsb3R0aW5nIHRoZSBwcm9wb3J0aW9uIG9mIHRoaXMgaW5jaWRlbmNlIGFjcm9zcyB0aGUgdHJhaW5pbmcgc2FtcGxlIChhIHNuYXBzaG90IG9mIDEzMUsrIHVzZXJzKSBwcm92aWRlcyBzb21lIGluc3BpcmF0aW9uLg0KDQojIyMgSG93IE1hbnkgUHJvZHVjdHMgV2VyZSBSZW9yZGVyZWQNCg0KQW1vbmcgYWxsIHByb2R1Y3QgcHVyY2hhc2VzLCA0MSUgb2YgcHJvZHVjdHMgYXJlIHJlb3JkZXJlZC4gIFRoZSByZW9yZGVyZWQgcmF0ZSBpcyBwYXJ0aWN1bGFybHkgaGlnaCBvbiB0b3AgMTAgcHJvZHVjdHMuIEFzIHNob3duIGluIGNoYXJ0IGJlbG93LCB0b3AgdGVuIHBvcHVsYXIgcHJvZHVjdHMgaGFzIHJlb3JkZXJlZCByYXRlIGlzIGFyb3VuZCA3MCUgdG8gODUlOyBoaWdoZXIgdGhhbiB0aGUgb3ZlcmFsbCByYXRpbyBvZiA0MSUuIA0KDQpgYGB7ciwgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0zLCBtZXNzYWdlPUZBTFNFfQ0KIyMgb3ZlcmFsbCBhbGwgcHJvZHVjdHMgcmVvcmRlcmVkIHJhdGUNCnRtcDEgPC0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUNCiAgZmlsdGVyKG9yZGVyX251bWJlciA+IDEpICU+JSAjIGV4Y2x1ZGUgZmlyc3Qgb3JkZXIsIHdoaWNoIHdpbGwgbmV2ZXIgaGF2ZSByZW9yZGVyZWQNCiAgY291bnQocmVvcmRlcmVkKSAlPiUNCiAgbXV0YXRlKHJhdGlvID0gbi9zdW0obikpDQogIA0KcDEgPC0gdG1wMSAlPiUgDQogIGdncGxvdChhZXMoeCA9ICcnLCB5ID0gcmF0aW8sIGZpbGwgPSBhcy5mYWN0b3IocmVvcmRlcmVkKSkpICsgDQogIGdlb21fY29sKHdpZHRoID0gMSkgKyANCiAgbGFicyh5ID0gJ1Byb2R1Y3QgUmVvcmRlcmVkIFJhdGlvJykgKw0KICBjb29yZF9wb2xhcih0aGV0YSA9ICd5Jywgc3RhcnQgPSAwKSArIA0KICBzY2FsZV9maWxsX2JyZXdlcihwYWxldHRlID0gIkRhcmsyIikgKw0KICB0aGVtZShheGlzLnRpdGxlLnkgPSBlbGVtZW50X2JsYW5rKCkpDQoNCiMjIHRvcDEwIHByb2R1Y3RzIGFuZCBpdHMgcmVvcmRlcmVkIHJhdGUNCnRtcDIgPC0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUNCiAgY291bnQocHJvZHVjdF9pZCkgJT4lICMgZmlsdGVyIG9ubHkgdG9wIDEwIHByb2R1Y3RzIGZvciByZW9yZGVyIGFuYWx5c2lzDQogIHRvcF9uKG4gPSAxMCkgJT4lDQogIGxlZnRfam9pbih1c2Vyc19vcmRlcnNfcHJvZHVjdHNfKSAlPiUgICMgbm93IGZpbmQgb3V0IHRoZWlyIHJlb3JkZXJlZCByYXRlDQogIGdyb3VwX2J5KHByb2R1Y3RfaWQsIHByb2R1Y3RfbmFtZSkgJT4lDQogIHN1bW1hcml6ZShyZW9yZGVyZWRfcmF0ZSA9IHN1bShyZW9yZGVyZWQsIG5hLnJtID0gVFJVRSkvbigpKSAlPiUgDQogIHNlbGVjdChwcm9kdWN0X2lkLCBwcm9kdWN0X25hbWUsIHJlb3JkZXJlZF9yYXRlKSAlPiUNCiAgYXJyYW5nZShkZXNjKHJlb3JkZXJlZF9yYXRlKSkNCg0KcDIgPC0gdG1wMiAlPiUgDQogIGdncGxvdChhZXMoeCA9IHJlb3JkZXIocHJvZHVjdF9uYW1lLCByZW9yZGVyZWRfcmF0ZSksIHkgPSByZW9yZGVyZWRfcmF0ZSkpICsgDQogIGxhYnModGl0bGUgPSAnVG9wIDEwIFByb2R1Y3RzIFNvbGQgYW5kIFRoZWlyIFJlb3JkZXJpbmcgUmF0ZScpICsNCiAgZ2VvbV9jb2woKSArIA0KICBzY2FsZV95X2NvbnRpbnVvdXMobGltaXRzID0gYygwLCAxKSwgYnJlYWtzID0gc2VxKDAsIDEsIGJ5ID0gMC4xKSkgKyANCiAgY29vcmRfZmxpcCgpDQoNCmdyaWQuYXJyYW5nZShwMSwgcDIsIG5jb2wgPSAyKQ0KYGBgDQoNCmBgYHtyIGVjaG89RkFMU0V9DQpybShsaXN0ID0gYygndG1wMScsICd0bXAyJywgJ3AxJywgJ3AyJykpDQpgYGANCg0KIyMjIFJlb3JkZXJpbmcgdnMgRGF5cyBTaW5jZSBQcmlvciBPcmRlcg0KDQpXZSB1bmRlcnN0YW5kIGZyb20gb3JkZXIgYW5hbHlzaXMgZWFybGllciB0aGF0IG1vc3QgdXNlcnMgcGxhY2UgdGhlaXIgb3JkZXJzIGV2ZXJ5IDcgYW5kIDMwIGRheXMuIEhvd2V2ZXIsIGZyb20gcmVvcmRlciByYXRpb24gcGVyc3BlY3RpdmUsIGRheSA3IGFuZCBkYXkgMzAgaGFzIGhpZ2ggY29udHJhc3Qgd2hlcmVieSBkYXkgNyBvcmRlcnMgaGFzIGhpZ2ggcmVvcmRlciByYXRpbyBhbmQgZGF5IDMwIGhhcyBsb3dlc3QgcmVvcmRlcmluZyByYXRpby4NCg0KYGBge3IgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0yLjV9DQp0bXAgPC0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUNCiAgZmlsdGVyKG9yZGVyX251bWJlciA+IDEpICU+JQ0KICBncm91cF9ieShkYXlzX3NpbmNlX3ByaW9yX29yZGVyLCBvcmRlcl9pZCkgJT4lDQogIHN1bW1hcml6ZShjb250YWluX3Jlb3JkZXJlZCA9IG1heChyZW9yZGVyZWQpKSAlPiUNCiAgc3VtbWFyaXplKHJlb3JkZXJlZF9vcmRlcnMgPSBzdW0oY29udGFpbl9yZW9yZGVyZWQpLA0KICAgICAgICAgICAgbiA9IG4oKSArIDEpICU+JQ0KICBtdXRhdGUobm9uX3Jlb3JkZXJfcmF0aW8gPSAxIC0gKHJlb3JkZXJlZF9vcmRlcnMvbikpDQoNCnRtcCAlPiUgDQogIGdncGxvdChhZXMoeCA9IGRheXNfc2luY2VfcHJpb3Jfb3JkZXIsIHkgPSBub25fcmVvcmRlcl9yYXRpbykpICsgDQogIGdlb21fcG9pbnQoKSArIA0KICBnZW9tX2xpbmUoKSArDQogIGxhYnModGl0bGUgPSAnT3JkZXJzIE5PVCBDb250YWluaW5nIFJlb3JkZXJlZCBQcm9kdWN0cyBvdmVyIERheXMgc2luY2UgUHJpb3IgT3JkZXInKQ0KYGBgDQoNCiMjIyBSZW9yZGVyaW5nIHZzIEhvdXIgT2YgT3JkZXINCg0KDQpgYGB7ciBmaWcud2lkdGg9OS4zLCBmaWcuaGVpZ2h0PTIuNX0NCnRtcCA8LSB1c2Vyc19vcmRlcnNfcHJvZHVjdHNfICU+JQ0KICBmaWx0ZXIob3JkZXJfbnVtYmVyID4gMSkgJT4lDQogIGdyb3VwX2J5KG9yZGVyX2hvdXJfb2ZfZGF5LCBvcmRlcl9pZCkgJT4lDQogIHN1bW1hcml6ZShjb250YWluX3Jlb3JkZXJlZCA9IG1heChyZW9yZGVyZWQpKSAlPiUNCiAgc3VtbWFyaXplKHJlb3JkZXJlZF9vcmRlcnMgPSBzdW0oY29udGFpbl9yZW9yZGVyZWQpLA0KICAgICAgICAgICAgbiA9IG4oKSkgJT4lDQogIG11dGF0ZShub25fcmVvcmRlcl9yYXRpbyA9IDEgLSAocmVvcmRlcmVkX29yZGVycy9uKSkNCg0KdG1wICU+JSANCiAgZ2dwbG90KGFlcyh4ID0gb3JkZXJfaG91cl9vZl9kYXksIHkgPSBub25fcmVvcmRlcl9yYXRpbykpICsgDQogIGdlb21fcG9pbnQoKSArIA0KICBnZW9tX2xpbmUoKSArDQogIGxhYnModGl0bGUgPSAnTm9uIFJlb3JkZXIgUmF0aW8gb3ZlciBUaW1lIG9mIE9yZGVyIFBsYWNlZCcpDQpgYGANCg0KIyMjIFJlb3JkZXJpbmcgdnMgRGF5IE9mIE9yZGVyDQoNCg0KYGBge3IgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0yLjV9DQp0bXAgPC0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUNCiAgZmlsdGVyKG9yZGVyX251bWJlciA+IDEpICU+JQ0KICBncm91cF9ieShvcmRlcl9kb3csIG9yZGVyX2lkKSAlPiUNCiAgc3VtbWFyaXplKGNvbnRhaW5fcmVvcmRlcmVkID0gbWF4KHJlb3JkZXJlZCkpICU+JQ0KICBzdW1tYXJpemUocmVvcmRlcmVkX29yZGVycyA9IHN1bShjb250YWluX3Jlb3JkZXJlZCksDQogICAgICAgICAgICBuID0gbigpICsgMSkgJT4lDQogIG11dGF0ZShub25fcmVvcmRlcl9yYXRpbyA9IDEgLSAocmVvcmRlcmVkX29yZGVycy9uKSkNCg0KdG1wICU+JSANCiAgZ2dwbG90KGFlcyh4ID0gb3JkZXJfZG93LCB5ID0gbm9uX3Jlb3JkZXJfcmF0aW8pKSArIA0KICBnZW9tX3BvaW50KCkgKyANCiAgZ2VvbV9saW5lKCkgKw0KICBsYWJzKHRpdGxlID0gJ05vbiBSZW9yZGVyIFJhdGlvIG92ZXIgRGF5IG9mIFB1cmNoYXNlJykNCmBgYA0KDQojIyMgUmVvcmRlcmluZyB2cyBEYXkgT2YgT3JkZXINCg0KSW50dWl0aXZlbHksIHdlIGNhbiB0aGluayBvZiB0aGUgbW9yZSByZWd1bGFyIGEgYnV5ZXIgaXMsICB0aGUgcGVyc29uIHRlbmQgdG8gcmVwZWF0IG9yZGVyaW5nIHRoZSBzYW1lIHByb2R1Y3RzLiANCg0KYGBge3IgZmlnLndpZHRoPTkuMywgZmlnLmhlaWdodD0yLjV9DQp0bXAgPC0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUNCiAgZmlsdGVyKG9yZGVyX251bWJlciA+IDEpICU+JQ0KICBncm91cF9ieSh1c2VyX2lkLCBvcmRlcl9pZCkgJT4lDQogIHN1bW1hcml6ZShjb250YWluX3Jlb3JkZXJlZCA9IG1heChyZW9yZGVyZWQpKSAlPiUNCiAgc3VtbWFyaXplKHJlb3JkZXJlZF9vcmRlcnMgPSBzdW0oY29udGFpbl9yZW9yZGVyZWQpLA0KICAgICAgICAgICAgdG90YWxfb3JkZXJzX3Blcl91c2VyID0gbigpKSAlPiUNCiAgZ3JvdXBfYnkodG90YWxfb3JkZXJzX3Blcl91c2VyKSAlPiUNCiAgc3VtbWFyaXplKHJlb3JkZXJzID0gc3VtKHJlb3JkZXJlZF9vcmRlcnMpLA0KICAgICAgICAgICAgdG90YWwgPSBzdW0odG90YWxfb3JkZXJzX3Blcl91c2VyKSkgJT4lDQogIG11dGF0ZShub25fcmF0aW8gPSAxIC0gKHJlb3JkZXJzL3RvdGFsKSkNCiAgDQp0bXAgJT4lIA0KICBnZ3Bsb3QoYWVzKHggPSB0b3RhbF9vcmRlcnNfcGVyX3VzZXIsIHkgPSBub25fcmF0aW8pKSArIA0KICBnZW9tX3BvaW50KCkgKyANCiAgZ2VvbV9saW5lKCkgKw0KICBsYWJzKHRpdGxlID0gJ05vbiBSZW9yZGVyIFJhdGlvIG92ZXIgRGF5IG9mIFB1cmNoYXNlJykNCmBgYA0KDQoNCiMgUHJlZGljdGl2ZSBBbmFseXNpcw0KDQojIyBUeXBlIG9mIFByZWRpY3Rpb24NCg0KVGhlIG9iamVjdGl2ZSBpcyB0byBwcmVkaWN0IHdoYXQgcHJvZHVjdCB3aWxsIHRoZSBjdXN0b21lciBwdXJjaGFzZSBpbiB0aGUgbmV4dCBiYXNrZXQuIEl0IHJlcXVpcmUgcHJvYmFiaWxpdHkgZXN0aW1hdGlvbiBvZiBlYWNoIHByb2R1Y3QgdGhhdCBiYWQgYmVlbiBwdXJjaGFzZWQgYmVmb3JlLCB0aGF0IHRvIGJlIHB1cmNoYXNlZCBiZWZvcmUuKipUaGlzIGlzIGEgY2xhc3NpZmljYXRpb24gcHJvYmxlbSoqLCBhcyB3ZWxsIGFzICoqYSByZWdyZXNzaW9uIG9mIHByb2JhYmlsaXR5Kiogb2YgcmVwdXJjaGFzZXMuIA0KDQpGb3IgdGhpcyBhbmFseXNpcywgd2Ugc2hhbGwgdXNlIHR3byBOYWl2ZSBtb2RlbHMgKGhhbmRjcmFmdGVkIGJhc2VsaW5lKSBhbmQgb25lIE1hY2hpbmUgTGVhcm5pbmcgTG9naXN0aWMgcmVncmVzc2lvbiB3aWxsIGJlIHVzZWQgZm9yIE1hY2hpbmUgTGVhcm5pbmcgYXBwcm9hY2ggZm9yIGl0cyBzcGVlZCBhbmQgc2ltcGxpY2l0eTsgdG8gZGVtb25zdHJhdGUgdGhlIGZlYXNpYmlsaXR5IHRvIHByb2R1Y2luZyBhIGJldHRlciBvdXRjb21lIHRoZW4gYmFzZWxpbmUuDQoNCiMjIyBUcmFpbi9UZXN0IERhdGFzZXQgU3BsaXR0aW5nDQoNCkluc3RhY2FydCBkaWQgbm90IHByb3ZpZGUgdXMgKip0ZXN0IG9yZGVyIGRldGFpbCoqLCB0aGVyZWZvcmUgd2Ugc2hhbGwgdXNlIHRoZSAqKnRyYWluKiogdXNlcnMgZm9yIGJvdGggdHJhaW5uZyBhbmQgdGVzdGluZy4gV2UgYWNoaWV2ZSB0aGlzIGJ5IHNwbGl0dGluZyB0aGUgKip0cmFpbioqIHVzZXJzIGFuZCBpdHMgcmVsYXRlZCBvcmRlcnMgYW5kIHByb2R1Y3RzIGludG8gdHJhaW4gZGF0YXNldCBhbmQgdHJhaW4gZGF0YXNldCwgYXQgNzAlLzMwJSBzcGxpdCAoYnkgbnVtYmVyIG9mIHVzZXJzKS4gVGhhdCBtZWFucyBvdXIgdHJhaW4vdGVzdCBkYXRhc2V0IHdpbGwgY29udGFpbiBhcHByb3hpbWF0ZWx5IDkxODQ2IC8gMzksMzYzIHVzZXJzLg0KDQpGb3IgdGhpcyBhbmFseXNpcywgd2Ugd2lsbCBub3QgYmUgc3VibWl0dGluZyB0byBLYWdnbGUuIA0KDQpgYGB7ciByZXN1bHRzPSdob2xkJ30NCiMgdXBkYXRlIHRoaXMgdmFyaWFibGUgZm9yIGNoYW5naW5nIHNwbGl0IHJhdGlvDQp0cmFpbl9wcm9wb3J0aW9uIDwtIDAuNw0KDQojIGJ1aWxkIGxpc3Qgb2YgYWxsIHVzZXJzIElEDQp0bXAgPC0gb3JkZXJzICU+JSANCiAgZmlsdGVyKGV2YWxfc2V0ID09ICd0cmFpbicpICU+JSANCiAgZGlzdGluY3QodXNlcl9pZCkNCg0KIyA3MC8zMCBzcGxpdA0Kc2V0LnNlZWQoMTIzNDUpDQp0cmFpbi5yb3dzIDwtIHNhbXBsZSgxOm5yb3codG1wKSwgdHJhaW5fcHJvcG9ydGlvbiAqIG5yb3codG1wKSkNCnRyYWluLnVzZXJzIDwtIHRtcFt0cmFpbi5yb3dzLCBdICAjIHNlbGVjdCB0cmFpbmluZyByb3dzLCBsaXN0IG9mIHRyYWluIHVzZXJzDQp0ZXN0LnVzZXJzIDwtIHRtcFstdHJhaW4ucm93cywgXSAjIHNlbGVjdCB0ZXN0aW5nIHJvd3MsIGxpc3Qgb2YgdGVzdCB1c2Vycw0KDQpjYXQoIlRvdGFsIFJvd3MgaW4gVHJhaW5pbmcgVXNlcnM6ICIsIGxlbmd0aCh0cmFpbi51c2VycyksDQogICAgIlxuVG90YWwgUm93cyBpbiBUZXN0aW5nIFVzZXJzOiAiLCBsZW5ndGgodGVzdC51c2VycyksDQogICAgIlxuVHJhaW4vVGVzdCBTcGxpdCAlIDogIiwgMTAwKmxlbmd0aCh0cmFpbi51c2VycykvKGxlbmd0aCh0ZXN0LnVzZXJzKStsZW5ndGgodHJhaW4udXNlcnMpKSwNCiAgICAiIC8gIiwgMTAwKmxlbmd0aCh0ZXN0LnVzZXJzKS8obGVuZ3RoKHRlc3QudXNlcnMpK2xlbmd0aCh0cmFpbi51c2VycykpKQ0KYGBgDQoNCmBgYHtyIGVjaG89RkFMU0V9DQpybShsaXN0ID0gYygndG1wJywgJ3RyYWluLnJvd3MnKSkgIyBtZW1vcnkgY2xlYW51cA0KYGBgDQoNCiMjIyBUcmFpbmluZyBEYXRhIENvbnN0cnVjdA0KDQpUaGUgZGF0YSBmcmFtZSB1c2VkIGZvciB0cmFpbmluZyBzaG91bGQgY29udGFpbiB0aGUgYmVsb3cgY29sdW1ucyBhbmQgZmVhdHVyZXM6ICANCg0KKipga2V5YCoqICANCg0KLSBUaGlzIGlzIHVuaXF1ZSBwYWlyIG9mIHVzZXJfaWQgYW5kIHByb2R1Y3RfaWQgZnJvbSBvcmRlcnMgIA0KLSBUaGUga2V5cyBzaG91bGQgYmUgY29uc3RydWN0ZWQgZnJvbSBhbGwgYHVzZXJfaWQtcHJvZHVjdF9pZGAgcGFpciB0aGF0IGluY2x1ZGVzIGFsbCBwcmlvciBhbmQgdGVzdC90cmFpbiByb3dzICANCg0KKipgYWN0dWFsKiogIA0KDQotIFRoaXMgaXMgdGhlIHJlc3BvbnNlIHZhcmlhYmxlIHdpdGggdmFsdWUgb2YgMSBvciAwIGZvciBlYWNoIHVuaXF1ZSBrZXkgIA0KLSBUaGUgdmFsdWUgaXMgMSB3aGVuIHRoZSBwcm9kdWN0IGlzIHB1cmNoYXNlZCBpbiB0aGUgbGFzdCBvcmRlciAodHJhaW4gb3IgdGVzdCBzZXQgb2Ygb3JkZXJzKSAgDQotIFRoZSB2YWx1ZSBpcyAwIHdoZW4gdGhlIHByb2R1Y3QgaXMgbm90IHB1cmNoYXNlZCBpbiB0aGUgdHJhaW4gb3IgdGVzdCBzZXQsIGJ1dCB3YXMgYm91Z2h0IGluIHByaW9yIHNldA0KDQoqKmBvdGhlciBmZWF0dXJlc2AqKiAgDQoNCkZyb20gZXhwbG9yYXRvcnkgZGlzY292ZXJ5LCBmZWF0dXJlcyB0aGF0IGNvdWxkIGNvbnRyaWJ1dGUgdG8gdGhlIHByZWRpY3Rpb24gc2hvdWxkIGJlIHBvcHVsYXRlZCBpbnRvIHRoZSBjb25zdHJ1Y3QuIEZlYXR1cmUgZW5naW5lZXJpbmcgd2lsbCBoYXBwZW4gaW4gdGhlIGxhdGVyIHN0YWdlLg0KDQpMZXQncyBwcm9jZWVkIHRvIGNyZWF0ZSB0aGUgYmFzaWMgKip0cmFpbmluZyBjb25zdHJ1Y3QqKi4gVGhpcyB3b24ndCBiZSB1c2VkIGZvciBwcmVkaWN0aW9uIHVudGlsIGZlYXR1cmUgZW5naW5lZXJpbmcgaXMgY29tcGxldGVkIGluIGxhdGVyIHN0YWdlLg0KDQpgYGB7cn0NCiMgbGlzdCBvZiBwcm9kdWN0cyBpbiB0aGUgZmluYWwgb3JkZXIsIHRoaXMgbWFrZSB1cCB0aGUgbGFiZWwNCmNvbnN0cnVjdDEgPC0gb3JkZXJzICU+JSAgICANCiAgZmlsdGVyKHVzZXJfaWQgJWluJSB0cmFpbi51c2VycyAmIGV2YWxfc2V0ID09ICd0cmFpbicpICU+JSANCiAgbGVmdF9qb2luKG9yZGVyX3Byb2R1Y3RzX3RyYWluKSAlPiUNCiAgZGlzdGluY3QodXNlcl9pZCwgcHJvZHVjdF9pZCkgJT4lDQogIG11dGF0ZShhY3R1YWwgPSAxKSAgI3RyYWluaW5nIGxhYmVsDQoNCiMgbGlzdCBvZiBwcm9kdWN0cyBlYWNoIHVzZXJzIGhhZCBib3VnaHQgYmVmb3JlIGluIHByaW9yIG9yZGVycw0KY29uc3RydWN0MiA8LSBvcmRlcnMgJT4lICAgDQogIGZpbHRlcih1c2VyX2lkICVpbiUgdHJhaW4udXNlcnMgJiBldmFsX3NldCA9PSAncHJpb3InKSAlPiUgDQogIGxlZnRfam9pbihvcmRlcl9wcm9kdWN0c19wcmlvcikgJT4lDQogIGRpc3RpbmN0KHVzZXJfaWQsIHByb2R1Y3RfaWQpDQoNCiMgVHJhaW5pbmcgQ29uc3RydWN0DQp0cmFpbi5jb25zdHJ1Y3QgPC0gbGVmdF9qb2luKGNvbnN0cnVjdDIsIGNvbnN0cnVjdDEpICU+JQ0KICBtdXRhdGUoa2V5ID0gcGFzdGUodXNlcl9pZCwgcHJvZHVjdF9pZCwgc2VwID0gIi0iKSkgJT4lICAjIGtleQ0KICBzZWxlY3Qoa2V5LCB1c2VyX2lkLCBwcm9kdWN0X2lkLCBhY3R1YWwpICU+JQ0KICBhcnJhbmdlKHVzZXJfaWQsIHByb2R1Y3RfaWQpICU+JQ0KICByZXBsYWNlX25hKGxpc3QoYWN0dWFsID0gMCkpICMgcHJvdWRjdHMgbm90IGluIGxhc3Qgb3JkZXIsIGJ1dCBleGlzdCBpbiBwcmlvciBvcmRlcg0KIyAgZHJvcF9uYSAjIHJlbW92ZSBwcm91ZGN0cyBub3QgaW4gaGlzdG9yaWNhbCBidXQgYXBwZWFyIGluIGxhc3Qgb3JkZXINCg0Kcm0obGlzdCA9IGMoJ2NvbnN0cnVjdDEnLCAnY29uc3RydWN0MicpKQ0KaGVhZCh0cmFpbi5jb25zdHJ1Y3QsIDUwKQ0KYGBgDQoNCiMjIyBUZXN0aW5nIERhdGEgQ29uc3RydWN0DQoNClNpbWlsYXIgYXBwcm9hY2ggdG8gdHJhaW5pbmcgZGF0YSBjb25zdHJ1Y3QsIGhlcmUgd2UgZnJhbWUgdGhlIHRlc3RpbmcgZGF0YSBmb3IgZXZhbHVhdGUgb3VyIG1vZGVsIGJ1aWx0IHdpdGggdHJhaW5pbmcgZGF0YS4NCg0KYGBge3IgZXZhbD1GQUxTRX0NCiMgbGlzdCBvZiBwcm9kdWN0cyBpbiB0aGUgZmluYWwgb3JkZXIsIHRoaXMgbWFrZSB1cCB0aGUgbGFiZWwNCmNvbnN0cnVjdDEgPC0gb3JkZXJzICU+JSAgICANCiAgZmlsdGVyKHVzZXJfaWQgJWluJSB0ZXN0LnVzZXJzICYgZXZhbF9zZXQgPT0gJ3RyYWluJykgJT4lIA0KICBsZWZ0X2pvaW4ob3JkZXJfcHJvZHVjdHNfdHJhaW4pICU+JQ0KICBkaXN0aW5jdCh1c2VyX2lkLCBwcm9kdWN0X2lkKSAlPiUNCiAgbXV0YXRlKGFjdHVhbCA9IDEpICAjdHJhaW5pbmcgbGFiZWwNCg0KIyBsaXN0IG9mIHByb2R1Y3RzIGVhY2ggdXNlcnMgaGFkIGJvdWdodCBiZWZvcmUgaW4gcHJpb3Igb3JkZXJzDQpjb25zdHJ1Y3QyIDwtIG9yZGVycyAlPiUgICANCiAgZmlsdGVyKHVzZXJfaWQgJWluJSB0ZXN0LnVzZXJzICYgZXZhbF9zZXQgPT0gJ3ByaW9yJykgJT4lIA0KICBsZWZ0X2pvaW4ob3JkZXJfcHJvZHVjdHNfcHJpb3IpICU+JQ0KICBkaXN0aW5jdCh1c2VyX2lkLCBwcm9kdWN0X2lkKQ0KDQojIFRyYWluaW5nIENvbnN0cnVjdA0KdGVzdC5jb25zdHJ1Y3QgPC0gY29uc3RydWN0MiAlPiUgDQogIGxlZnRfam9pbihjb25zdHJ1Y3QxKSAlPiUNCiAgbXV0YXRlKGtleSA9IHBhc3RlKHVzZXJfaWQsIHByb2R1Y3RfaWQsIHNlcCA9ICItIikpICU+JSAgIyBrZXkNCiAgc2VsZWN0KGtleSwgdXNlcl9pZCwgcHJvZHVjdF9pZCwgYWN0dWFsKSAlPiUNCiAgYXJyYW5nZSh1c2VyX2lkLCBwcm9kdWN0X2lkKSAlPiUNCiAgcmVwbGFjZV9uYShsaXN0KGFjdHVhbCA9IDApKSAjIHByb3VkY3RzIG5vdCBpbiBsYXN0IG9yZGVyLCBidXQgZXhpc3QgaW4gcHJpb3Igb3JkZXINCiMgIGRyb3BfbmEgIyByZW1vdmUgcHJvdWRjdHMgbm90IGluIGhpc3RvcmljYWwgYnV0IGFwcGVhciBpbiBsYXN0IG9yZGVyDQoNCnJtKGxpc3QgPSBjKCdjb25zdHJ1Y3QxJywgJ2NvbnN0cnVjdDInKSkNCmhlYWQodGVzdC5jb25zdHJ1Y3QsIDUwKQ0KYGBgDQoNCiMjIE1vZGVsIEV2YWx1YXRpb24gJiBPcHRpbWl6YXRpb24NCg0KSW5zdGFjYXJ0IGhhcyBjbG9zZSB0byA1MGsgcHJvZHVjdHMgaW4gdGhlaXIgY2F0YWxvZ3VlLiBBcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgaXRlbXMgb3JkZXJlZCBieSBhIHVzZXIgaXMganVzdCBhIGZyYWN0aW9uIG9mIHRoZSA1MGsgYXZhaWxhYmxlIHByb2R1Y3QuIFRoaXMgbWVhbnMgYnkgc2ltcGx5IHByZWRpY3Rpbmcgbm90aGluZyBpcyBwdXJjaGFzZWQgaW4gdGhlIG5leHQgYmFza2V0LCB3ZSB3b3VsZCB5ZWlsZCAqKmNsb3NlIHRvIDEwMCUgYWNjdXJhY3kqKi4gIA0KDQpEdWUgdG8gdGhlICoqaGlnaGx5IGltYmFsYW5jZSoqIGRhdGFzZXQsIEluc3RhY2FydCByZXF1aXJlICoqRjEgU2NvcmUqKiBhcyB0aGUgY29tcGV0aXRpb24gc2NvcmluZywgaW5zdGVhZCBvZiBhY2N1cmFjeS4gIA0KDQpUbyBldmFsdWF0ZSB0aGUgcGVyZm9ybWFuY2Ugb2YgdGhlIG1vZGVsLCB3ZSBoYWQgY3JlYXRlZCBhIGN1c3RvbSBmdW5jdGlvbiB0byBidWlsZCBhICoqY29uZnVzaW9uIG1hdHJpeCBhbmQgZGVyaXZlIG90aGVyIGJpbmFyeSBjbGFzc2lmaWNhdGlvbiBtZXRyaWNzKiouIA0KDQpgYGB7cn0NCiMjIEN1c3RvbSBGdW5jdGlvbiBGb3IgQmluYXJ5IENsYXNzIFBlcmZvcm1hbmNlIEV2YWx1YXRpb24NCmJpbmNsYXNzX2V2YWwgPSBmdW5jdGlvbiAoYWN0dWFsLCBwcmVkaWN0KSB7DQogIGNtID0gdGFibGUoYXMuaW50ZWdlcihhY3R1YWwpLCBhcy5pbnRlZ2VyKHByZWRpY3QpLCBkbm49YygnQWN0dWFsJywnUHJlZGljdGVkJykpDQogIGFjID0gKGNtWycxJywnMSddK2NtWycwJywnMCddKS8oY21bJzAnLCcxJ10gKyBjbVsnMScsJzAnXSArIGNtWycxJywnMSddICsgY21bJzAnLCcwJ10pDQogIHByID0gY21bJzEnLCcxJ10vKGNtWycwJywnMSddICsgY21bJzEnLCcxJ10pDQogIHJjID0gY21bJzEnLCcxJ10vKGNtWycxJywnMCddICsgY21bJzEnLCcxJ10pDQogIGZzID0gMiogcHIqcmMvKHByK3JjKQ0KICBsaXN0KGNtPWNtLCByZWNhbGw9cmMsIHByZWNpc2lvbj1wciwgZnNjb3JlPWZzLCBhY2N1cmFjeT1hYykNCn0NCmBgYA0KDQpJZiB0aGUgcHJlZGljdGlvbiBpcyBiYXNlZCBvbiBwcm9iYWJpbGl0eSwgd2Ugc2hhbGwgYnVpbGQgYSBmdW5jdGlvbiB0byBkaXNjb3ZlciAqKmN1dG9mZiB0aGF0IG9wdGltaXplIHZhcmlvdXMgcGVyZm9ybWFuY2UgbWV0cmljcyoqLiANCg0KYGBge3J9DQojIyMgQ3V0b2ZmIFRocmVzaG9sZCBPcHRpbWl6YXRpb24NCm9wdGltaXplX2N1dG9mZiA9IGZ1bmN0aW9uIChhY3R1YWwsIHByb2JhYmlsaXR5KSB7DQogIHJvY3IucHJlZCA9IHByZWRpY3Rpb24ocHJlZGljdGlvbnMgPSBwcm9iYWJpbGl0eSwgbGFiZWxzID0gYWN0dWFsKQ0KICByb2NyLm1ldHJpY3MgPSBkYXRhLmZyYW1lKA0KICAgICAgY3V0b2ZmICAgPSByb2NyLnByZWRAY3V0b2Zmc1tbMV1dLA0KICAgICAgYWNjdXJhY3kgPSAocm9jci5wcmVkQHRwW1sxXV0gKyByb2NyLnByZWRAdG5bWzFdXSkgLyANCiAgICAgICAgICAgICAgICAgICAocm9jci5wcmVkQHRwW1sxXV0gKyByb2NyLnByZWRAdG5bWzFdXSArIHJvY3IucHJlZEBmcFtbMV1dICsgcm9jci5wcmVkQGZuW1sxXV0pLA0KICAgICAgdHByID0gcm9jci5wcmVkQHRwW1sxXV0gLyAocm9jci5wcmVkQHRwW1sxXV0gKyByb2NyLnByZWRAZm5bWzFdXSksDQogICAgICBmcHIgPSByb2NyLnByZWRAZnBbWzFdXSAvIChyb2NyLnByZWRAZnBbWzFdXSArIHJvY3IucHJlZEB0bltbMV1dKSwNCiAgICAgIHBwdiA9IHJvY3IucHJlZEB0cFtbMV1dIC8gKHJvY3IucHJlZEB0cFtbMV1dICsgcm9jci5wcmVkQGZwW1sxXV0pDQogICkNCiAgcm9jci5tZXRyaWNzJGZzY29yZSA9IDIgKiAocm9jci5tZXRyaWNzJHRwciAqIHJvY3IubWV0cmljcyRwcHYpIC8gKHJvY3IubWV0cmljcyR0cHIgKyByb2NyLm1ldHJpY3MkcHB2KQ0KICByb2NyLm1ldHJpY3MkdHByX2ZwciA9IHJvY3IubWV0cmljcyR0cHIgLyByb2NyLm1ldHJpY3MkZnByDQogIA0KICAjIyBEaXNjb3ZlcnkgdGhlIG9wdGltYWwgdGhyZXNob2xkIGZvciB2YXJpb3VzIG1ldHJpY3MNCiAgcm9jci5iZXN0ID0gcmJpbmQoDQogICAgYmVzdC5hY2N1cmFjeSA9IGMobWF4ID0gbWF4KHJvY3IubWV0cmljcyRhY2N1cmFjeSwgbmEucm0gPSBUUlVFKSwgY3V0b2ZmPXJvY3IubWV0cmljcyRjdXRvZmZbd2hpY2gubWF4KHJvY3IubWV0cmljcyRhY2N1cmFjeSldKSwNCiAgICBiZXN0LnBwdiA9IGMobWF4ID0gbWF4KHJvY3IubWV0cmljcyRwcHYsIG5hLnJtID0gVFJVRSksIGN1dG9mZiA9IHJvY3IubWV0cmljcyRjdXRvZmZbd2hpY2gubWF4KHJvY3IubWV0cmljcyRwcHYpXSksDQogICAgYmVzdC5yZWNhbGwgPSBjKG1heCA9IG1heChyb2NyLm1ldHJpY3MkdHByLCBuYS5ybSA9IFRSVUUpLCBjdXRvZmYgPSByb2NyLm1ldHJpY3MkY3V0b2ZmW3doaWNoLm1heChyb2NyLm1ldHJpY3MkdHByKV0pLA0KICAgIGJlc3QuZnNjb3JlID0gYyhtYXggPSBtYXgocm9jci5tZXRyaWNzJGZzY29yZSwgbmEucm0gPSBUUlVFKSwgY3V0b2ZmID0gcm9jci5tZXRyaWNzJGN1dG9mZlt3aGljaC5tYXgocm9jci5tZXRyaWNzJGZzY29yZSldKSwNCiAgICBiZXN0LnRwcl9mcHIgPSBjKG1heCA9IG1heChyb2NyLm1ldHJpY3MkdHByX2ZwciwgbmEucm0gPSBUUlVFKSwgY3V0b2ZmID0gcm9jci5tZXRyaWNzJGN1dG9mZlt3aGljaC5tYXgocm9jci5tZXRyaWNzJHRwcl9mcHIpXSkNCiAgKQ0KICANCiAgbGlzdChtZXRyaWNzID0gcm9jci5tZXRyaWNzLCBiZXN0ID0gcm9jci5iZXN0KQ0KfQ0KYGBgDQoNCg0KIyMgTW9kZWwgMSA6IE5haXZlIFByZWRpY3Rpb24NCg0KIyMjIEJ1aWxkIFRoZSBNb2RlbA0KDQpXaXRoIGludGVuc2lvbiB0byBtYWtlIHRoaXMgYSBiYXNlbGluZSBtb2RlbCwgV2Ugc2ltcGx5IHByZWRpY3QgdGhlIGJhc2tldCBiYXNlZCBvbiB1c2VyIGxhc3Qgb3JkZXIuIA0KDQpgYGB7cn0NCm0xLnRyYWluLmRhdGEgPSB1c2Vyc19vcmRlcnNfcHJvZHVjdHNfICU+JQ0KICBmaWx0ZXIodXNlcl9pZCAlaW4lIHRyYWluLnVzZXJzKSAlPiUNCiAgZ3JvdXBfYnkodXNlcl9pZCkgJT4lDQogIHRvcF9uKG49MSwgd3Q9b3JkZXJfbnVtYmVyKSAgJT4lICNsYXN0IG9yZGVyIGhhcyB0aGUgaGlnaGVyIG9yZGVyX251bWJlcg0KICBzZWxlY3QodXNlcl9pZCwgcHJvZHVjdF9pZCkgJT4lIA0KICBtdXRhdGUgKHByZWRpY3RlZD0xKSAgJT4lICAgICAgICAjcHJlZGljdCBiYXNlZCBvbiBsYXN0IG9yZGVyZWQsIHRoZXJlZm9yZSAxDQogIGZ1bGxfam9pbih0cmFpbi5jb25zdHJ1Y3QpICU+JSAgIyBqb2luIHdpdGggdHJhaW4gY29uc3RydWN0IGZvciBpdGVtcyBub3QgcHJlZGljdGVkIGJ1dCBpbiBmaW5hbCBvcmRlcg0KICBzZWxlY3QodXNlcl9pZCwgcHJvZHVjdF9pZCwgYWN0dWFsLCBwcmVkaWN0ZWQpICU+JQ0KICByZXBsYWNlX25hKGxpc3QocHJlZGljdGVkID0gMCkpDQoNCmhlYWQobTEudHJhaW4uZGF0YSwyNSkNCmBgYA0KDQojIyMgQ29uZnVzaW9uIE1hdHJpeA0KDQpgYGB7ciBtb2RlbDEtZXZhbH0NCm0xLmV2YWwgPSBiaW5jbGFzc19ldmFsKG0xLnRyYWluLmRhdGEkYWN0dWFsLCBtMS50cmFpbi5kYXRhJHByZWRpY3RlZCkNCm0xLmV2YWwkY20NCmBgYA0KDQojIyMgTW9kZWwgUGVyZm9ybWFuY2UNCg0KVGhlIHJlc3VsdCBzaG93cyBvbmx5ICoqMC4zNDYwODMzIEYxIFNjb3JlKiouDQoNCmBgYHtyfQ0KY2F0KCJBY2N1cmFjeTogICIsIG0xLmV2YWwkYWNjdXJhY3ksDQogICAgIlxuUHJlY2lzaW9uOiAiLCBtMS5ldmFsJHByZWNpc2lvbiwNCiAgICAiXG5SZWNhbGw6ICAgICIsIG0xLmV2YWwkcmVjYWxsLA0KICAgICJcbkZTY29yZTogICAgIiwgbTEuZXZhbCRmc2NvcmUpDQpgYGANCg0KYGBge3IgZWNobz1GQUxTRX0NCnJtKGxpc3Q9YygnbTEudHJhaW4uZGF0YScpKQ0KYGBgDQoNCiMjIE1vZGVsIDIgOiBTbWFydGVyIE5haXZlIFByZWRpY3Rpb24gKEJhc2VsaW5lKQ0KDQpJbiB0aGlzIG1vZGVsLCB3ZSBwcmVkaWN0IHByb2R1Y3RzIGluIHRoZSBiYXNrZXQgYnkgZXN0aW1hdGluZyB0aGVpciBmcmVxdWVuY3kgb2YgcmVwdXJjaGFzZWQuIFRoaXMgd2F5IHdlIGdldCBhIHJhdGlvIHRvIGluZGljYXRlIHByb2JhYmlsaXR5IG9mIHJlLXB1cmNoYXNlcy4gV2UgdXNlIFJPQ1IgcGFja2FnZSB0byBlc3RpbWF0ZSB0aGUgYmVzdCBjdXRvZmYgcG9pbnQgKGF0IHdoaWNoIGFib3ZlIHRoaXMgY3V0b2ZmIHdlIHNoYWxsIHByZWRpY3QgZm9yIHJlLW9yZGVyKSB0aGF0IGdpdmUgdXMgdGhlICoqb3B0aW11bSBGMSBzY29yZSoqLiANCg0KIyMjIEJ1aWxkIFRoZSBNb2RlbA0KDQpgYGB7ciBtb2RlbDItYnVpbGRpbmcsIG1lc3NhZ2U9RkFMU0V9DQojIyBCdWlsZCBNb2RlbA0KbTIudHJhaW4uZGF0YSA9IHVzZXJzX29yZGVyc19wcm9kdWN0c18gJT4lDQogIGZpbHRlcih1c2VyX2lkICVpbiUgdHJhaW4udXNlcnMpICU+JQ0KICBncm91cF9ieSh1c2VyX2lkKSAlPiUNCiAgICBtdXRhdGUodG90YWxfb3JkZXJzID0gbWF4KG9yZGVyX251bWJlcikpICU+JSAgIyB0b3RhbCBudW1iZXIgb2Ygb3JkZXJzIG1hZGUgcHJldmlvdXNseQ0KICB1bmdyb3VwICU+JSANCiAgc2VsZWN0KHVzZXJfaWQsIG9yZGVyX2lkLCBwcm9kdWN0X2lkLCB0b3RhbF9vcmRlcnMpICU+JQ0KICBncm91cF9ieSh1c2VyX2lkLCBwcm9kdWN0X2lkKSAlPiUNCiAgICBzdW1tYXJpemUocHJlZGljdGVkPW4oKS9tYXgodG90YWxfb3JkZXJzKSkgJT4lDQogIHNlbGVjdCh1c2VyX2lkLCBwcm9kdWN0X2lkLCBwcmVkaWN0ZWQpICU+JQ0KICBmdWxsX2pvaW4odHJhaW4uY29uc3RydWN0KSAlPiUgICMgam9pbiB3aXRoIHRyYWluIGNvbnN0cnVjdCBmb3IgaXRlbXMgbm90IHByZWRpY3RlZCBidXQgaW4gZmluYWwgb3JkZXINCiAgc2VsZWN0KHVzZXJfaWQsIHByb2R1Y3RfaWQsIGFjdHVhbCwgcHJlZGljdGVkKSAlPiUNCiAgcmVwbGFjZV9uYShsaXN0KHByZWRpY3RlZCA9IDApKQ0KDQpoZWFkKG0yLnRyYWluLmRhdGEsMjApDQpgYGANCg0KIyMjIE9wdGltaXplIEN1dG9mZg0KDQpXZSBzZWUgdGhhdCBpbiBvcmRlciB0byBtYXhpbWl6ZSAqKkYxIFNjb3JlKiosIHdlIG5lZWQgdG8gc2V0IHRoZSBjdXRvZmYgdGhyZXNob2xkIHRvIDAuMzM2OCwgd2hpY2ggaXMgdGhlIG5leHQgc3RlcC4NCg0KYGBge3IgbW9kZWwyLW9wdGltaXplfQ0KIyMjIFRocmVzaG9sZCBPcHRpbWl6YXRpb24NCm0yLnJvY3IgPSBvcHRpbWl6ZV9jdXRvZmYoYWN0dWFsID0gbTIudHJhaW4uZGF0YSRhY3R1YWwsIHByb2JhYmlsaXR5ID0gbTIudHJhaW4uZGF0YSRwcmVkaWN0ZWQpDQprYWJsZShtMi5yb2NyJGJlc3QpICU+JSBrYWJsZV9zdHlsaW5nKGJvb3RzdHJhcF9vcHRpb25zID0gYygic3RyaXBlZCIpKQ0KYGBgDQoNCiMjIyBDb25mdXNpb24gTWF0cml4DQoNCkxldCdzIHNldCB0aGUgKipjdXRvZmYgdG8gMC4zMzY3MzQ3KiogYXMgZGlzY292ZXJlZCBpbiBwcmV2aW91cyBzdGVwLg0KDQpgYGB7ciBtb2RlbDItZXZhbH0NCm0yLmV2YWwgPSBiaW5jbGFzc19ldmFsKG0yLnRyYWluLmRhdGEkYWN0dWFsLCBtMi50cmFpbi5kYXRhJHByZWRpY3RlZD4wLjMzNjczNDcpDQptMi5ldmFsJGNtDQpgYGANCg0KIyMjIE1vZGVsIFBlcmZvcm1hbmNlDQoNCldlIGFyZSBnZXR0aW5nIHNsaWdodGx5ICoqYmV0dGVyIEYxIFNjb3JlICgwLjM3NTM1NDQpKiogY29tcGFyZSB0byBwcmV2aW91cyBuYWl2ZSBtb2RlbC4gV2Ugc2hhbGwgdXNlIHRoaXMgYXMgdGhlICoqQkFTRUxJTkUqKi4NCg0KYGBge3J9DQpjYXQoIkFjY3VyYWN5OiAgIiwgbTIuZXZhbCRhY2N1cmFjeSwNCiAgICAiXG5QcmVjaXNpb246ICIsIG0yLmV2YWwkcHJlY2lzaW9uLA0KICAgICJcblJlY2FsbDogICAgIiwgbTIuZXZhbCRyZWNhbGwsDQogICAgIlxuRlNjb3JlOiAgICAiLCBtMi5ldmFsJGZzY29yZSkNCmBgYA0KDQpgYGB7ciBlY2hvPUZBTFNFfQ0Kcm0obGlzdD1jKCdtMi50cmFpbi5kYXRhJywnbTIucm9jcicpKQ0KYGBgDQoNCiMjIE1hY2hpbmUgTGVhcm5pbmcgRnJhbWluZw0KDQpXZSBjb25zdHJ1Y3QgYWxsIHRoZSBwcm9kdWN0cyB0aGF0IHVzZXJzIGhhZCBwdXJjaGFzZWQgaW4gdGhlIGxhc3QgMyBvcmRlcnMsIHRoZW4gdXNlIG1hY2hpbmUgbGVhcm5pbmcgY2xhc3NpZmljYXRpb24gdG8gcHJlZGljdCB3aWxsIGVhY2ggb2YgdGhlIHByb2R1Y3QgYmUgcHVyY2hhc2VkIGFnYWluLiBXZSBzaGFsbCB1c2UgKipkZWNpc2lvbiB0cmVlIGFuZCBsb2dpc3RpYyByZWdyZXNzaW9uKiogZm9yIHRoaXMgcHJlZGljdGlvbi4NCg0KIyMjIEZlYXR1cmUgRW5naW5lZXJpbmcNCg0KIyMjIyBPcmRlciBGZWF0dXJlcw0KDQpUaGVzZSBhcmUgb3JpZ2luYWwgZmVhdHVyZXMgcHJvdmlkZWQgYnkgSW5zdGFjYXJ0LiBBbHRob3VnaCB0aGVyZSBhcmUgbm8gb3RoZXIgZmVhdHVyZXMgZW5naW5lZXJlZCBzcGVjaWZpY2FsbHkgdG8gZGVzY3JpYmUgT3JkZXIsIHRoc2UgZmVhdHVyZXMgYXJlIGJlaW5nIHVzZWQgdG8gZ2VuZXJhdGUgb3RoZXIgZmVhdHVyZXMgaW4gdGhlIGZvbGxvd2luZyBzZWN0aW9ucy4NCg0KKipgb3JkZXJzYCoqICANCi0gYG9yZGVyX2Rvd2AgIA0KLSBgb3JkZXJfaG91cl9vZl9kYXlgICANCi0gYGRheXNfc2luY2VfcHJpb3Jfb3JkZXJgICANCi0gYHJlb3JkZXJlZGAgIA0KDQojIyMjIFVzZXIgRmVhdHVyZXMNCg0KV2UgY3JlYXRlIGZpdmUgZmVhdHVyZXMgd2hpY2ggaXMgdW5pcXVlIHRvIGVhY2ggaW5kaXZpZHVhbCB1c2VyLiBUaGVzZSBhcmUgdGhlIGZlYXR1cmVzIHRoYXQgZGVzcmliZSB0aGUgdXNlci4NCg0KKipgdXNlcnNgKiogIA0KLSBgdV9uX29yZGVyc2A6IE51bWJlciBvZiBPcmRlcnMgUGVyIFVzZXIgIA0KLSBgdV9hdmdfcHJpb3JzYDogQXZlcmFnZSB3YWl0aW5nIGRheXMgYmV0d2VlbiBvcmRlcnMgcGVyIFVzZXIgIA0KLSBgdV9hdmdfaG9kYDogQXZlcmFnZSBPcmRlciBQbGFjaW5nIEhvdXIgUGVyIFVzZXIgIA0KLSBgdV9hdmdfZG93YDogQXZlcmFnZSBPcmRlciBQbGFjaW5nIERheSBQZXIgVXNlciAgDQotIGB1X2F2Z19vcmRlcl9zaXplYDogQXZlcmFnZSBTaXplIG9mIEJhc2tldCAoaXRlbXMgaW4gb3JkZXIpIFBlciBVc2VyICANCg0KYGBge3IgZXZhbD1GQUxTRSwgbWVzc2FnZT1GQUxTRX0NCiMjIyMgdXNlciBmZWF0dXJlcw0KdXNlcnNfID0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUNCiAgZ3JvdXBfYnkodXNlcl9pZCxvcmRlcl9pZCkgJT4lDQogICAgbXV0YXRlKHVfb19zaXplID0gaWZlbHNlKHJvd19udW1iZXIoKT09MSwgbWF4KGFkZF90b19jYXJ0X29yZGVyKSwwKSApICU+JQ0KICBncm91cF9ieSh1c2VyX2lkKSAlPiUNCiAgICBzdW1tYXJpemUoDQogICAgICB1X25fb3JkZXJzID0gbWF4KG9yZGVyX251bWJlciksDQogICAgICB1X2F2Z19wcmlvcnMgPSBtZWFuKGRheXNfc2luY2VfcHJpb3Jfb3JkZXIsbmEucm09VFJVRSksDQogICAgICB1X2F2Z19ob2QgPSBtZWFuKG9yZGVyX2hvdXJfb2ZfZGF5KSwNCiAgICAgIHVfYXZnX2RvdyA9IG1lYW4ob3JkZXJfZG93KSwNCiAgICAgIHVfYXZnX29yZGVyX3NpemUgPSBzdW0odV9vX3NpemUpL21heChvcmRlcl9udW1iZXIpDQogICAgKSAlPiUgDQogIGFycmFuZ2UodXNlcl9pZCkNCg0KaGVhZCh1c2Vyc18pDQpgYGANCg0KIyMjIyBQcm9kdWN0IEZlYXR1cmVzDQoNCldlIGNyZWF0ZSB0d28gcHJvZHVjdCBzcGVjaWZpYyBmZWF0dXJlcy4NCg0KKipgcHJvZHVjdHNgKiogIA0KDQotIGBhdmdfcHJvZHVjdF9vcmRlcl9kb3dgOiBBdmVyYWdlIG9mIHByb2R1Y3Qgb3JkZXJfZG93DQotIGBhdmdfcHJvZHVjdF9vcmRlcl9ob2RgOiBBdmVyYWdlIG9mIHByb2R1Y3Qgb3JkZXJfaG91cl9vZl9kYXkgIA0KDQpgYGB7ciBldmFsPUZBTFNFLCBtZXNzYWdlPUZBTFNFfQ0KcHJvZHVjdHNfID0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUNCiAgZ3JvdXBfYnkocHJvZHVjdF9pZCkgJT4lDQogIHN1bW1hcml6ZSggDQogICAgcF9hdmdfZG93ID0gbWVhbihvcmRlcl9kb3cpLA0KICAgIHBfYXZnX2hvZCA9IG1lYW4ob3JkZXJfaG91cl9vZl9kYXkpDQogICkgJT4lIGFycmFuZ2UocHJvZHVjdF9pZCkNCg0KaGVhZChwcm9kdWN0c18pDQpgYGANCg0KIyMjIyBVc2VyLVByb2R1Y3QgRmVhdHVyZXMNCg0KV2Ugc2hhbGwgaW50cm9kdWNlIHByb2R1Y3QgcmVsYXRlZCBmZWF0dXJlcyB0aGF0IGFyZSB1c2VyLXByb2R1Y3Qgc3BlY2lmYw0KDQotIGB1cF9uX3Jlb3JkZXJlZGAgOiBob3cgbWFueSB0aW1lcyBhIHVzZXIgcmVvcmRlcmVkdGhpcyBwcm9kdWN0ICANCi0gYHVwX2F2Z19wcmlvcnNgIDogQXZlcmFnZSBudW1iZXIgb2YgZGF5cyBpbiBiZXR3ZWVuIGJlZm9yZSBhIHVzZXIgcHVyY2hhc2UgdGhpcyBwcm9kdWN0ICANCi0gYHVwX2F2Z19ob2RgIDogQXZlcmFnZSBob3VyIGEgdXNlciBwdXJjaGFzZSB0aGlzIHByb2R1Y3QgIA0KLSBgdXBfYXZnX2Rvd2AgOiBBdmVyYWdlIGRheSBvZiB3ZWVrIGEgdXNlciBwdXJjaGFzZSB0aGlzIHByb2R1Y3QgIA0KLSBgdXBfYXZnX3JhbmtgIDogQXZlcmFnZSBhZGQgdG8gY2FydCBudW1iZXIgYSB1c2VyIHNlbGVjdCB0aGlzIHByb2R1Y3QgIA0KDQpgYGB7cn0NCiMjIyB1c2VyX3Byb2R1Y3RzIGZlYXR1cmVzDQp1c2VyX3Byb2R1Y3RzXyA9IHVzZXJzX29yZGVyc19wcm9kdWN0c18gJT4lDQogIGdyb3VwX2J5KHVzZXJfaWQsIHByb2R1Y3RfaWQpICU+JQ0KICAgIHN1bW1hcml6ZSgNCiAgICAgIHVwX25fcmVvcmRlcmVkID0gbigpLTEsICMgbWludXMgb2ZmIGZpcnN0IG9yZGVyLCB3aGljaCBpcyBub3QgcmVvcmRlcg0KICAgICAgdXBfYXZnX3ByaW9ycyA9IG1lYW4oZGF5c19zaW5jZV9wcmlvcl9vcmRlcixuYS5ybT1UUlVFKSwNCiAgICAgIHVwX2F2Z19ob2QgPSBtZWFuKG9yZGVyX2hvdXJfb2ZfZGF5KSwNCiAgICAgIHVwX2F2Z19kb3cgPSBtZWFuKG9yZGVyX2RvdyksDQogICAgICB1cF9hdmdfcmFuayA9IG1lYW4oYWRkX3RvX2NhcnRfb3JkZXIpDQogICAgKSAlPiUNCiAgdW5ncm91cCAlPiUNCiAgbGVmdF9qb2luKHVzZXJzXykgJT4lICMgdG8gcmV0cmlldmUgdV9uX29yZGVycw0KICBtdXRhdGUodXBfcmVvcmRlcl9yYXRlID0gdXBfbl9yZW9yZGVyZWQvKHVfbl9vcmRlcnMtMSkpICU+JQ0KICByZXBsYWNlX25hKGxpc3QodXBfYXZnX3ByaW9ycyA9IDApKSAlPiUgIyBmaXggdXAgDQogIGFycmFuZ2UodXNlcl9pZCxwcm9kdWN0X2lkKQ0KDQpoZWFkKHVzZXJfcHJvZHVjdHNfLDIwKQ0KYGBgDQoNCiMjIyBDb25zdHJ1Y3QgVHJhaW5pbmcgRGF0YQ0KDQpXZSBzaGFsbCBjb21iaW5lZCB0cmFpbmluZyBjb25zdHJ1Y3QgdGFibGUgd2l0aCB0aGUgbmV3IGVuZ2luZWVyZWQgZmVhdHVyZXMgdG8gZm9ybSB0aGUgdHJhaW5pbmcgZGF0YS4gQ2F0ZWdvcmljYWwgZGF0YSB3aGljaCBhcmUgbWVyZWx5IG5hbWVzIG9yIGlkZW50aWZpY2F0aW9uIHdpbGwgYmUgcmVtb3ZlZCBzaW5jZSB0aGV5IHNob3VsZCBub3QgY29udHJpYnV0ZSB0byBwcmVkaWN0aW9uLg0KDQpBZnRlciB0aGlzIHN0ZXAsIHRoZSB0cmlhbmluZyBkYXRhIGlzIHJlYWR5IGZvciBtYWNoaW5lIGxlYXJuaW5nIGFsZ29yaXRobSBvZiBjaG9pY2UuDQoNCmBgYHtyIGV2YWw9RkFMU0V9DQptMy50cmFpbi5kYXRhID0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUNCiAgZmlsdGVyKHVzZXJfaWQgJWluJSB0cmFpbi51c2VycykgJT4lDQogIGxlZnRfam9pbih1c2VyX3Byb2R1Y3RzXykgJT4lIA0KICBsZWZ0X2pvaW4ocHJvZHVjdHNfKSAlPiUNCiAgI2xlZnRfam9pbih1c2Vyc18pICAjdXNlcl9wcm9kdWN0c18gYWxyZWFkeSBjb250YWluIHVzZXIgc3BlY2lmaWMgZmVhdHVyZXMNCiAgZnVsbF9qb2luKHRyYWluLmNvbnN0cnVjdCwgYnk9YygndXNlcl9pZCcsJ3Byb2R1Y3RfaWQnKSkgJT4lDQogIGFycmFuZ2UodXNlcl9pZCwgcHJvZHVjdF9pZCkgJT4lDQogIHNlbGVjdCgtYygna2V5JywndXNlcl9pZCcsJ29yZGVyX2lkJywgJ3Byb2R1Y3RfaWQnLCAncHJvZHVjdF9uYW1lJywgJ2RlcGFydG1lbnRfaWQnLCAnYWlzbGVfaWQnLCAnZGVwYXJ0bWVudCcsJ2Fpc2xlJywgJ2RheXNfc2luY2VfcHJpb3Jfb3JkZXInKSkgDQoNCmdsaW1wc2UobTMudHJhaW4uZGF0YSkNCmBgYA0KDQojIyMgQ29uc3RydWN0IFRlc3RpbmcgRGF0YQ0KDQpgYGB7ciBldmFsPUZBTFNFfQ0KbTMudGVzdC5kYXRhID0gdXNlcnNfb3JkZXJzX3Byb2R1Y3RzXyAlPiUNCiAgZmlsdGVyKHVzZXJfaWQgJWluJSB0ZXN0LnVzZXJzKSAlPiUNCiAgbGVmdF9qb2luKHVzZXJfcHJvZHVjdHNfKSAlPiUgDQogIGxlZnRfam9pbihwcm9kdWN0c18pICU+JQ0KICAjbGVmdF9qb2luKHVzZXJzXykgICN1c2VyX3Byb2R1Y3RzXyBhbHJlYWR5IGNvbnRhaW4gdXNlciBzcGVjaWZpYyBmZWF0dXJlcw0KICBmdWxsX2pvaW4odGVzdC5jb25zdHJ1Y3QsIGJ5PWMoJ3VzZXJfaWQnLCdwcm9kdWN0X2lkJykpICU+JQ0KICBhcnJhbmdlKHVzZXJfaWQsIHByb2R1Y3RfaWQpICU+JQ0KICBzZWxlY3QoLWMoJ2tleScsJ3VzZXJfaWQnLCdvcmRlcl9pZCcsICdwcm9kdWN0X2lkJywgJ3Byb2R1Y3RfbmFtZScsICdkZXBhcnRtZW50X2lkJywgJ2Fpc2xlX2lkJywgJ2RlcGFydG1lbnQnLCdhaXNsZScsICdkYXlzX3NpbmNlX3ByaW9yX29yZGVyJykpIA0KDQpnbGltcHNlKG0zLnRlc3QuZGF0YSkNCmBgYA0KDQpgYGB7ciBlY2hvPUZBTFNFfQ0KIyBjbGVhbnVwIHRvIGZyZWUgbWVtb3J5DQpybShsaXN0PWMoJ3VzZXJzXycsJ3Byb2R1Y3RzJywncHJvZHVjdHNfJywnb3JkZXJfcHJvZHVjdHNfdHJhaW4nLCdvcmRlcl9wcm9kdWN0c19wcmlvcicsJ3VzZXJfcHJvZHVjdHNfJywndXNlcnNfb3JkZXJzX3Byb2R1Y3RzXycpKQ0KYGBgDQoNCg0KIyMgTW9kZWwgMyA6IExvZ2lzdGljIFJlZ3Jlc3Npb24NCg0KIyMjIE1vZGVsIFRyYWlubmcNCg0KYGBge3IgbW9kZWwzLWJ1aWxkaW5nfQ0KbTMuZml0ID0gZ2xtKGFjdHVhbCB+IC4sIGZhbWlseSA9IGJpbm9taWFsLCBkYXRhID0gbTMudHJhaW4uZGF0YSkNCmBgYA0KDQojIyMgVHJhaW5pbmcgRGF0YSBQZXJmb3JtYW5jZQ0KDQojIyMjIFByZWRpY3Rpb24NCg0KYGBge3J9DQptMy5wcmVkaWN0ID0gcHJlZGljdChtMy5maXQsIHR5cGUgPSAncmVzcG9uc2UnLCBuZXdkYXRhID0gbTMudHJhaW4uZGF0YSkNCmBgYA0KDQojIyMjIE9wdGltaXplIEN1dG9mZg0KDQpgYGB7ciBtb2RlbDMtb3B0aW1pemV9DQojIyMgVGhyZXNob2xkIE9wdGltaXphdGlvbg0KbTMucm9jciA9IG9wdGltaXplX2N1dG9mZihhY3R1YWwgPSBtMy50cmFpbi5kYXRhJGFjdHVhbCwgcHJvYmFiaWxpdHkgPSBtMy5wcmVkaWN0KQ0Ka2FibGUobTMucm9jciRiZXN0KSAlPiUga2FibGVfc3R5bGluZyhib290c3RyYXBfb3B0aW9ucyA9IGMoInN0cmlwZWQiKSkNCmBgYA0KDQojIyMjIENvbmZ1c2lvbiBNYXRyaXgNCg0KYGBge3IgbW9kZWwzLWV2YWx9DQptMy5ldmFsID0gYmluY2xhc3NfZXZhbChtMy50cmFpbi5kYXRhJGFjdHVhbCwgbTMucHJlZGljdD4wLjIyMzMxMTUpDQptMy5ldmFsJGNtDQpgYGANCg0KIyMjIyBNb2RlbCBFdmFsdWF0aW9uDQoNCkxvZ2lzdGljIHJlZ3Jlc3Npb24gcHJvZHVjZSBGMSBTY29yZSBvZiAwLjUzODg5Mzcgd2l0aCB0cmFpbmluZyBkYXRhLCBhIG11Y2ggYmV0dGVyIGNvbXBhcmVkIHRvIE1vZGVsIDEgYW5kIE1vZGVsIDIuIFdlIHNoYWxsIHByb2NlZWQgdGVzdCB0aGUgbW9kZWwgb24gdW5rbm93biBkYXRhLCB0aGUgdGVzdCBkYXRhLg0KDQpgYGB7cn0NCmNhdCgiQWNjdXJhY3k6ICAiLCAgIG0zLmV2YWwkYWNjdXJhY3ksDQogICAgIlxuUHJlY2lzaW9uOiAiLCBtMy5ldmFsJHByZWNpc2lvbiwNCiAgICAiXG5SZWNhbGw6ICAgICIsIG0zLmV2YWwkcmVjYWxsLA0KICAgICJcbkZTY29yZTogICAgIiwgbTMuZXZhbCRmc2NvcmUpDQpgYGANCg0KYGBge3IsIGV2YWw9RkFMU0V9DQpyb2NyLnByZWQgPSBwcmVkaWN0aW9uKG0zLnByZWRpY3QsIG0zLnRyYWluLmRhdGEkYWN0dWFsKQ0Kcm9jci5wZXJmID0gcGVyZm9ybWFuY2Uocm9jci5wcmVkLCBtZWFzdXJlID0gInRwciIsIHgubWVhc3VyZSA9ICJmcHIiKQ0Kcm9jci5hdWMgPSBhcy5udW1lcmljKHBlcmZvcm1hbmNlKHJvY3IucHJlZCwgImF1YyIpQHkudmFsdWVzKQ0KcGxvdChyb2NyLnBlcmYsDQogICAgbHdkID0gMywgY29sb3JpemUgPSBUUlVFLA0KICAgIHByaW50LmN1dG9mZnMuYXQgPSBzZXEoMCwgMSwgYnkgPSAwLjEpLA0KICAgIHRleHQuYWRqID0gYygtMC4yLCAxLjcpLA0KICAgIG1haW4gPSAnUk9DIEN1cnZlJykNCm10ZXh0KHBhc3RlKCdhdWMgOiAnLCByb3VuZChyb2NyLmF1YywgNSkpKQ0KYWJsaW5lKDAsIDEsIGNvbCA9ICJyZWQiLCBsdHkgPSAyKQ0KYGBgDQoNCmBgYHtyIG1vZGVsMy1jbGVhbnVwLCBlY2hvPUZBTFNFfQ0Kcm0obGlzdD1jKCdtMy5wcmVkaWN0JywgJ20zLnJvY3InKSkNCmBgYA0KDQojIyMgVGVzdCBEYXRhIFBlcmZvcm1hbmNlDQoNCiMjIyMgUHJlZGljdGlvbg0KDQpgYGB7cn0NCm0zLnByZWRpY3QudGVzdCA9IHByZWRpY3QobTMuZml0LCB0eXBlID0gJ3Jlc3BvbnNlJywgbmV3ZGF0YSA9IG0zLnRlc3QuZGF0YSkNCmBgYA0KDQojIyMjIE9wdGltaXplIEN1dG9mZg0KDQpgYGB7ciBtb2RlbDMtb3B0aW1pemUyfQ0KIyMjIFRocmVzaG9sZCBPcHRpbWl6YXRpb24NCm0zLnJvY3IudGVzdCA9IG9wdGltaXplX2N1dG9mZihhY3R1YWwgPSBtMy50ZXN0LmRhdGEkYWN0dWFsLCBwcm9iYWJpbGl0eSA9IG0zLnByZWRpY3QudGVzdCkNCmthYmxlKG0zLnJvY3IudGVzdCRiZXN0KSAlPiUga2FibGVfc3R5bGluZyhib290c3RyYXBfb3B0aW9ucyA9IGMoInN0cmlwZWQiKSkNCmBgYA0KDQojIyMjIENvbmZ1c2lvbiBNYXRyaXgNCg0KYGBge3IgbW9kZWwzLWV2YWwyfQ0KbTMuZXZhbC50ZXN0ID0gYmluY2xhc3NfZXZhbChtMy50ZXN0LmRhdGEkYWN0dWFsLCBtMy5wcmVkaWN0LnRlc3Q+MC4yMjMzMTE1KQ0KbTMuZXZhbC50ZXN0JGNtDQpgYGANCg0KIyMjIyBNb2RlbCBFdmFsdWF0aW9uDQoNCkxvZ2lzdGljIHJlZ3Jlc3Npb24gcHJvZHVjZSBGMSBTY29yZSBvZiAwLjUzODg5Mzcgd2l0aCB0cmFpbmluZyBkYXRhLCBhIG11Y2ggYmV0dGVyIGNvbXBhcmVkIHRvIE1vZGVsIDEgYW5kIE1vZGVsIDIuIFdlIHNoYWxsIHByb2NlZWQgdGVzdCB0aGUgbW9kZWwgb24gdW5rbm93biBkYXRhLCB0aGUgdGVzdCBkYXRhLg0KDQpXZSBhY2hlaXZlZCBGMSBTY29yZSBvZiAqKjAuNTQwNTU4OCoqLCBzbGlnaHRseSBoaWdoZXIgdGhhbiB0cmFpbmluZyBkYXRhLg0KDQpgYGB7cn0NCmNhdCgiQWNjdXJhY3k6ICAiLCAgIG0zLmV2YWwudGVzdCRhY2N1cmFjeSwNCiAgICAiXG5QcmVjaXNpb246ICIsIG0zLmV2YWwudGVzdCRwcmVjaXNpb24sDQogICAgIlxuUmVjYWxsOiAgICAiLCBtMy5ldmFsLnRlc3QkcmVjYWxsLA0KICAgICJcbkZTY29yZTogICAgIiwgbTMuZXZhbC50ZXN0JGZzY29yZSkNCmBgYA0KDQpgYGB7cn0NCnJtKGxpc3Q9YygnbTMuZml0JywnbTMucHJlZGljdCcsICdtMy5yb2NyJykpDQpgYGANCg0KDQojIyMjIFJPQw0KDQpgYGB7cn0NCnJvY3IucHJlZCA9IHByZWRpY3Rpb24ocHJlZGljdGlvbnMgPSBtMy5wcmVkaWN0LnRlc3QsIGxhYmVscyA9IG0zLnRlc3QuZGF0YSRhY3R1YWwpDQpyb2NyLnBlcmYgPSBwZXJmb3JtYW5jZShyb2NyLnByZWQsIG1lYXN1cmUgPSAidHByIiwgeC5tZWFzdXJlID0gImZwciIpDQpyb2NyLmF1YyA9IGFzLm51bWVyaWMocGVyZm9ybWFuY2Uocm9jci5wcmVkLCAiYXVjIilAeS52YWx1ZXMpDQpyb2NyLmF1Yw0KYGBgDQoNCmBgYHtyfQ0KcGxvdChyb2NyLnBlcmYsDQogICAgIGx3ZCA9IDMsIGNvbG9yaXplID0gVFJVRSwNCiAgICAgcHJpbnQuY3V0b2Zmcy5hdCA9IHNlcSgwLCAxLCBieSA9IDAuMSksDQogICAgIHRleHQuYWRqID0gYygtMC4yLCAxLjcpLA0KICAgICBtYWluID0gJ1JPQyBDdXJ2ZScpDQptdGV4dChwYXN0ZSgnYXVjIDogJywgcm91bmQocm9jci5hdWMsIDUpKSkNCmFibGluZSgwLCAxLCBjb2wgPSAicmVkIiwgbHR5ID0gMikNCmBgYA0KDQojIEFuYWx5c2lzICYgUmVjb21tZW5kYXRpb25zDQoNClRlY2huaWNhbCBDaGFsbGVuZ2VzDQoNCi0gTWFjaGluZSBzcGVlZCBhbmQgbWVtb3J5LiBUaGUgR0xNDQo=

Instacart Market Basket Analysis

By Aep Hidayatuloh

2019 Jun 7

1 Introduction

1.1 Research Goal & Objective

2 Market Basket Analysis

3 Terminology of Association Rules

4 Dataset Preparation

4.1 Data Source

4.2 R Libraries Used

4.3 Import Datasets

4.4 Data Dictionary

4.5 Understanding Datasets

4.5.1 Aisles

4.5.2 Departments

4.5.3 Products

4.5.4 Departments And Its Relevant Products

4.5.5 Aisles And Its Relevant Products

4.5.6 Orders

4.5.6.1 Train Eval_Set

4.5.6.2 Test Eval_Set

4.5.7 Order_Product

4.5.8 Order_Product_Train

4.5.9 Order_Product_Train_Prior

4.5.10 Users

5 Exploratory Data Analysis

5.1 Orders

5.1.1 How Many Orders ?

5.1.2 How Soon Until Next Order ?

5.2 Orders_Products

5.2.1 Most Popular Products Sold

5.2.2 Most Popular Department Sold

5.2.3 Most Popular Aisles Sold

5.2.4 Products Ordered Day Pattern

5.2.5 Products Ordered Hour Pattern

5.3 Basket Analysis

5.3.1 Basket Size Distribution

5.4 Re-Ordered Analysis

5.4.1 Average Re-ordered Items In Basket Distribution

5.4.2 Product Reorder Ratio

5.4.3 How Many Products Were Reordered

5.5 top10 products and its reordered rate

5.5.1 Reordering vs Days Since Prior Order

5.5.2 Reordering vs Hour Of Order

5.5.3 Reordering vs Day Of Order

5.5.4 Reordering vs Day Of Order

6 Predictive Analysis

6.1 Type of Prediction

6.1.1 Train/Test Dataset Splitting

7 build list of all users ID

8 70/30 split

8.0.1 Training Data Construct

9 list of products each users had bought before in prior orders

10 Training Construct

10.0.1 Testing Data Construct

10.1 Model Evaluation & Optimization

10.2 Model 1 : Naive Prediction

10.2.1 Build The Model

10.2.2 Confusion Matrix

10.2.3 Model Performance

10.3 Model 2 : Smarter Naive Prediction (Baseline)

10.3.1 Build The Model

10.3.2 Optimize Cutoff

10.3.3 Confusion Matrix

10.3.4 Model Performance

10.4 Machine Learning Framing

10.4.1 Feature Engineering

10.4.1.1 Order Features

10.4.1.2 User Features

10.4.1.3 Product Features

10.4.1.4 User-Product Features

10.4.2 Construct Training Data

10.4.3 Construct Testing Data

10.5 Model 3 : Logistic Regression

10.5.1 Model Trainng

10.5.2 Training Data Performance

10.5.2.1 Prediction

10.5.2.2 Optimize Cutoff

10.5.2.3 Confusion Matrix

10.5.2.4 Model Evaluation