Description

Pleas download “T3_Data.Rdata” from Canvas for this tutorial.

The data for this tutorial describe a field experiment, conducted by an online retailer. The study focuses on the effect of coupons as a promotion tool. The company recruits 20,000 consumers in the study, and assign the coupons based on three characteristics that are calculated from their CRM system: the recency, frequency and average monetary values of consumers’ historical purchases. Each variable is categorized into two levels. For example, for “recency”, if consumers make a purchase more recently, they are tagged with “Recent” and otherwise, with “Overdue”.

Consumers in the treatment group receive coupons, and those in the control not. Then, the online retailer track the subsequent purchases of the consumers (“order_size”), the main outcome variable for the study. You are given a sample (500 consumers) of the full data, and asked to quantify the effectiveness of coupons.

# Load and scan the data.  
load("T3_Data.Rdata")
head(coupon)
## # A tibble: 6 x 6
##   customer recency frequency monetary  used_coupon order_size
##   <chr>    <fct>   <fct>     <fct>           <int>      <dbl>
## 1 15329    Overdue Frequent  Low value           0          0
## 2 11263    Recent  Frequent  Low value           0          2
## 3 06049    Recent  Infreqent Low value           0          0
## 4 15866    Recent  Infreqent Low value           0          0
## 5 09007    Recent  Infreqent Low value           0          0
## 6 03518    Recent  Frequent  Low value           0          0

Matching

Note: the following analysis is more of a show-and-tell purpose. In practice, you can make the code much more efficient. Or you may use read-made packages such as Matching or MatchIt. Here, we will follow the procedure discussed in class step by step. Also, for statistical inference, you may need subsampling, as boostrapping may not work (due to the deterministic nature of sample pruning). We will not have the procedure in this notebook. For more information, check the standard packages.

Step 1 - Define and calculate the “closeness” of consumers

In the data, all three variables of \(X_i\) are discrete (binary). Therefore, we use a standard measure called “Jaccard distance” to measure the differences. Notice that the smaller the measure, the more similar two consumers.

distance <- dist(data.matrix(coupon[,2:4])-1, # coerce into a binary matrix
                 method = "binary") # choose binary or the Jaccard measure
# coerce the distance matrix into a normal matrix for later use
distance <- as.matrix(distance)
distance[1:10,1:10] # just to check the first 10 rows and columns
##      1   2 3 4 5   6   7   8   9  10
## 1  0.0 0.5 1 1 1 0.5 0.0 0.5 0.0 0.0
## 2  0.5 0.0 1 1 1 0.0 0.5 1.0 0.5 0.5
## 3  1.0 1.0 0 0 0 1.0 1.0 1.0 1.0 1.0
## 4  1.0 1.0 0 0 0 1.0 1.0 1.0 1.0 1.0
## 5  1.0 1.0 0 0 0 1.0 1.0 1.0 1.0 1.0
## 6  0.5 0.0 1 1 1 0.0 0.5 1.0 0.5 0.5
## 7  0.0 0.5 1 1 1 0.5 0.0 0.5 0.0 0.0
## 8  0.5 1.0 1 1 1 1.0 0.5 0.0 0.5 0.5
## 9  0.0 0.5 1 1 1 0.5 0.0 0.5 0.0 0.0
## 10 0.0 0.5 1 1 1 0.5 0.0 0.5 0.0 0.0

Step 2 - find the “closest” consumers

Given the distance matrix, we next find the closest consumers for each consumer in the data. Here, we use sampling with replacement, meaning a consumer may be matched multiple times to other consumers. This is generally preferred for samller data.

# initialize some dimensions
N <- dim(coupon)[1]
N.1 <- sum(coupon$used_coupon)

# the index of treated and control units
idx.1 <- which(coupon$used_coupon==1)
idx.0 <- which(coupon$used_coupon==0)

# we create an empty list to store results
best_matches <- vector(mode = "list", N)
for (i in 1:N) { # separate the treated and the control
  if (coupon$used_coupon[i]==1) { # for the treated
    dist_i <- distance[i,idx.0] # get the distances to all the controls
    best_i <- idx.0[which(dist_i==min(dist_i))] # select controls with smallest distance
  } else if (coupon$used_coupon[i]==0) { # for the control 
    dist_i <- distance[i,idx.1] # get the distances to all the treated
    best_i <- idx.1[which(dist_i==min(dist_i))] # select treated with smallest distance
  }
  best_matches[[i]] <- best_i # store results
}

Step 3 - Get the treatment effects

Given the matched samples for each consumer, we first us the average of the matched samples to obtain the potential outcomes.

get_potential_outcomes <- function (x) {
  return(mean(coupon$order_size[x]))
}
potential_purchase <- sapply(best_matches,get_potential_outcomes,simplify = T)

Next, we can calculate the ATT (average treatment effects on the treated) and the ATC (average treatment effects on the control)

ATT_matching <- mean(coupon$order_size[idx.1])-
  mean(potential_purchase[idx.1])
ATC_matching <- -mean(coupon$order_size[idx.0])+
  mean(potential_purchase[idx.0])
#ATE is the weighted average of ATT and ATC
ATE_matching <- N.1/N*ATT_matching +
  (1-N.1/N)*ATC_matching

# print out the results
print(list(ATE = ATE_matching,
           ATT = ATT_matching,
           ATC = ATC_matching))
## $ATE
## [1] 10.10295
## 
## $ATT
## [1] 14.9714
## 
## $ATC
## [1] 9.048706

Weighting

As in the tutorial on classical matching, all the selection (of treatment assignment) is on three variables: recency, frequency, and monetary. Given the data, there are two main parts to estimating treatment effects using weighted regression. The first part involves obtaining estimates of customers’ propensities to use the coupon. For this tutorial, we will use logistic regression to obtain these propensity scores. The second part involves performing the weighted regression, using weights that are based on the propensity scores estimated in Part 1.

Part 1: Estimating the propensity to use the coupon

There are three variables that we can use to estimate the propensity to use the coupon: recency, frequency, and monetary. These variables collectively satisfy the back-door criterion for blocking associations between coupon use and order size. That is, we can condition on these variables to block all back-door paths between used_coupon and total_order.

To estimate the propensities, we set up a logistic regression. Because our objective is to estimate customers’ propensities to use the coupon, we make used_coupon the dependent variable in the regression. For the model spec, we will account for all only the main effects. You may try alternative specs such as with all 2- and 3-way interactions.

propensity_fit <- 
    glm(used_coupon ~ recency + frequency + monetary, data = coupon,
        family = binomial)
summary(propensity_fit)
## 
## Call:
## glm(formula = used_coupon ~ recency + frequency + monetary, family = binomial, 
##     data = coupon)
## 
## Deviance Residuals: 
##     Min       1Q   Median       3Q      Max  
## -1.7623  -0.6016  -0.3076  -0.2008   2.7978  
## 
## Coefficients:
##                    Estimate Std. Error z value Pr(>|z|)    
## (Intercept)         -3.8937     0.4007  -9.718  < 2e-16 ***
## recencyOverdue       0.8662     0.2671   3.243  0.00118 ** 
## frequencyFrequent    2.2761     0.3971   5.731 9.98e-09 ***
## monetaryHigh value   2.9326     0.4238   6.920 4.53e-12 ***
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## (Dispersion parameter for binomial family taken to be 1)
## 
##     Null deviance: 468.35  on 499  degrees of freedom
## Residual deviance: 366.11  on 496  degrees of freedom
## AIC: 374.11
## 
## Number of Fisher Scoring iterations: 6

Based on the caliberated model, we the obtain the propensity scores or the likelihood of being assigned coupons.

p <- predict(propensity_fit, type = 'response')
# visualize the propensity scores by groups
par(mfrow=c(1,2))
hist(p[idx.0])
hist(p[idx.1])

With the propensity score, we run weighted OLS to obtain the ATE, ATT and ATC.For ATE, we weight the treatment group and control group by \(\dfrac{1}{e}\) and \(\dfrac{1}{1-e}\), respectively. For ATT, we weight the control group by \(\dfrac{e}{1-e}\) and for ATC, the treatment group by \(\dfrac{1-e}{e}\).

w_ate <- p
w_ate[idx.1] <- 1/p[idx.1] 
w_ate[idx.0] <- 1/(1-p[idx.0])

w_att <- rep(1,N) 
w_att[idx.0] <- p[idx.0]/(1-p[idx.0])

w_atc <- rep(1,N)
w_atc[idx.1] <- (1-p[idx.1])/p[idx.1]

Run a weighted OLS to obtain the ATE, ATT and ATC:

ATE_weighting <- lm(order_size ~ used_coupon + recency + frequency + monetary, 
                            data = coupon, weights = w_ate)
summary(ATE_weighting)
## 
## Call:
## lm(formula = order_size ~ used_coupon + recency + frequency + 
##     monetary, data = coupon, weights = w_ate)
## 
## Weighted Residuals:
##      Min       1Q   Median       3Q      Max 
## -31.5180  -0.4619   1.1624   1.5266  23.6292 
## 
## Coefficients:
##                    Estimate Std. Error t value Pr(>|t|)    
## (Intercept)         -1.5113     0.3006  -5.028 6.94e-07 ***
## used_coupon         10.9644     0.3145  34.866  < 2e-16 ***
## recencyOverdue       0.3760     0.3268   1.151     0.25    
## frequencyFrequent    1.9332     0.3236   5.974 4.42e-09 ***
## monetaryHigh value   8.6786     0.4576  18.963  < 2e-16 ***
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 4.725 on 495 degrees of freedom
## Multiple R-squared:  0.7758, Adjusted R-squared:  0.774 
## F-statistic: 428.1 on 4 and 495 DF,  p-value: < 2.2e-16
ATT_weighting <- lm(order_size ~ used_coupon + recency + frequency + monetary, 
                            data = coupon, weights = w_att)
summary(ATT_weighting)
## 
## Call:
## lm(formula = order_size ~ used_coupon + recency + frequency + 
##     monetary, data = coupon, weights = w_att)
## 
## Weighted Residuals:
##      Min       1Q   Median       3Q      Max 
## -13.5545   0.3120   0.6046   1.0227  12.4464 
## 
## Coefficients:
##                    Estimate Std. Error t value Pr(>|t|)    
## (Intercept)         -4.2365     0.5981  -7.083 4.88e-12 ***
## used_coupon         14.6882     0.3694  39.762  < 2e-16 ***
## recencyOverdue       1.8419     0.3773   4.882 1.42e-06 ***
## frequencyFrequent    1.9403     0.5074   3.824 0.000148 ***
## monetaryHigh value   9.3197     0.4625  20.149  < 2e-16 ***
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 2.457 on 495 degrees of freedom
## Multiple R-squared:  0.8091, Adjusted R-squared:  0.8075 
## F-statistic: 524.5 on 4 and 495 DF,  p-value: < 2.2e-16
ATC_weighting <- lm(order_size ~ used_coupon + recency + frequency + monetary, 
                            data = coupon, weights = w_atc)
summary(ATC_weighting)
## 
## Call:
## lm(formula = order_size ~ used_coupon + recency + frequency + 
##     monetary, data = coupon, weights = w_atc)
## 
## Weighted Residuals:
##     Min      1Q  Median      3Q     Max 
## -28.123  -1.024   1.037   1.054  22.245 
## 
## Coefficients:
##                    Estimate Std. Error t value Pr(>|t|)    
## (Intercept)        -1.05423    0.25457  -4.141 4.06e-05 ***
## used_coupon        10.06795    0.28220  35.677  < 2e-16 ***
## recencyOverdue      0.01749    0.29837   0.059    0.953    
## frequencyFrequent   2.07857    0.29035   7.159 2.96e-12 ***
## monetaryHigh value  8.46985    0.49125  17.241  < 2e-16 ***
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 3.794 on 495 degrees of freedom
## Multiple R-squared:  0.778,  Adjusted R-squared:  0.7762 
## F-statistic: 433.6 on 4 and 495 DF,  p-value: < 2.2e-16

Summary

In general, you will see differences in the estimates produced by different methods. This is called a “method bias”. Conventionally, people run various analyses to show the robustness of the estimates.

LS0tDQp0aXRsZTogJ1R1dG9yaWFsIDM6IE1hdGNoaW5nIGFuZCBXZWlnaHRpbmcgRXN0aW1hdG9ycycNCm91dHB1dDoNCiAgaHRtbF9kb2N1bWVudDoNCiAgICBkZl9wcmludDogdGliYmxlDQogICAgY29kZV9kb3dubG9hZDogeWVzDQogICAgdGhlbWU6IGNlcnVsZWFuDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZmxvYXQ6IHllcw0KICAgIG51bWJlcl9zZWN0aW9uczogbm8NCiAgcGRmX2RvY3VtZW50Og0KICAgIHRvYzogeWVzDQotLS0NCg0KIyMjICoqRGVzY3JpcHRpb24qKg0KUGxlYXMgZG93bmxvYWQgIlQzX0RhdGEuUmRhdGEiIGZyb20gQ2FudmFzIGZvciB0aGlzIHR1dG9yaWFsLiANCg0KVGhlIGRhdGEgZm9yIHRoaXMgdHV0b3JpYWwgZGVzY3JpYmUgYSBmaWVsZCBleHBlcmltZW50LCBjb25kdWN0ZWQgYnkgYW4gb25saW5lIHJldGFpbGVyLiBUaGUgc3R1ZHkgZm9jdXNlcyBvbiB0aGUgZWZmZWN0IG9mIGNvdXBvbnMgYXMgYSBwcm9tb3Rpb24gdG9vbC4gVGhlIGNvbXBhbnkgcmVjcnVpdHMgMjAsMDAwIGNvbnN1bWVycyBpbiB0aGUgc3R1ZHksIGFuZCBhc3NpZ24gdGhlIGNvdXBvbnMgYmFzZWQgb24gdGhyZWUgY2hhcmFjdGVyaXN0aWNzIHRoYXQgYXJlIGNhbGN1bGF0ZWQgZnJvbSB0aGVpciBDUk0gc3lzdGVtOiB0aGUgcmVjZW5jeSwgZnJlcXVlbmN5IGFuZCBhdmVyYWdlIG1vbmV0YXJ5IHZhbHVlcyBvZiBjb25zdW1lcnMnIGhpc3RvcmljYWwgcHVyY2hhc2VzLiBFYWNoIHZhcmlhYmxlIGlzIGNhdGVnb3JpemVkIGludG8gdHdvIGxldmVscy4gRm9yIGV4YW1wbGUsIGZvciAicmVjZW5jeSIsIGlmIGNvbnN1bWVycyBtYWtlIGEgcHVyY2hhc2UgbW9yZSByZWNlbnRseSwgdGhleSBhcmUgdGFnZ2VkIHdpdGggIlJlY2VudCIgYW5kIG90aGVyd2lzZSwgd2l0aCAiT3ZlcmR1ZSIuIA0KDQpDb25zdW1lcnMgaW4gdGhlIHRyZWF0bWVudCBncm91cCByZWNlaXZlIGNvdXBvbnMsIGFuZCB0aG9zZSBpbiB0aGUgY29udHJvbCBub3QuIFRoZW4sIHRoZSBvbmxpbmUgcmV0YWlsZXIgdHJhY2sgdGhlIHN1YnNlcXVlbnQgcHVyY2hhc2VzIG9mIHRoZSBjb25zdW1lcnMgKCJvcmRlcl9zaXplIiksIHRoZSBtYWluIG91dGNvbWUgdmFyaWFibGUgZm9yIHRoZSBzdHVkeS4gWW91IGFyZSBnaXZlbiBhIHNhbXBsZSAoNTAwIGNvbnN1bWVycykgb2YgdGhlIGZ1bGwgZGF0YSwgYW5kIGFza2VkIHRvIHF1YW50aWZ5IHRoZSBlZmZlY3RpdmVuZXNzIG9mIGNvdXBvbnMuICAgDQoNCmBgYHtyfQ0KIyBMb2FkIGFuZCBzY2FuIHRoZSBkYXRhLiAgDQpsb2FkKCJUM19EYXRhLlJkYXRhIikNCmhlYWQoY291cG9uKQ0KYGBgDQojIyMgKipNYXRjaGluZyoqDQoNCk5vdGU6IHRoZSBmb2xsb3dpbmcgYW5hbHlzaXMgaXMgbW9yZSBvZiBhIHNob3ctYW5kLXRlbGwgcHVycG9zZS4gSW4gcHJhY3RpY2UsIHlvdSBjYW4gbWFrZSB0aGUgY29kZSBtdWNoIG1vcmUgZWZmaWNpZW50LiBPciB5b3UgbWF5IHVzZSByZWFkLW1hZGUgcGFja2FnZXMgc3VjaCBhcyBNYXRjaGluZyBvciBNYXRjaEl0LiBIZXJlLCB3ZSB3aWxsIGZvbGxvdyB0aGUgcHJvY2VkdXJlIGRpc2N1c3NlZCBpbiBjbGFzcyBzdGVwIGJ5IHN0ZXAuIEFsc28sIGZvciBzdGF0aXN0aWNhbCBpbmZlcmVuY2UsIHlvdSBtYXkgbmVlZCBzdWJzYW1wbGluZywgYXMgYm9vc3RyYXBwaW5nIG1heSBub3Qgd29yayAoZHVlIHRvIHRoZSBkZXRlcm1pbmlzdGljIG5hdHVyZSBvZiBzYW1wbGUgcHJ1bmluZykuIFdlIHdpbGwgbm90IGhhdmUgdGhlIHByb2NlZHVyZSBpbiB0aGlzIG5vdGVib29rLiBGb3IgbW9yZSBpbmZvcm1hdGlvbiwgY2hlY2sgdGhlIHN0YW5kYXJkIHBhY2thZ2VzLiANCg0KIyMjIyBTdGVwIDEgLSBEZWZpbmUgYW5kIGNhbGN1bGF0ZSB0aGUgImNsb3NlbmVzcyIgb2YgY29uc3VtZXJzDQpJbiB0aGUgZGF0YSwgYWxsIHRocmVlIHZhcmlhYmxlcyBvZiAkWF9pJCBhcmUgZGlzY3JldGUgKGJpbmFyeSkuIFRoZXJlZm9yZSwgd2UgdXNlIGEgc3RhbmRhcmQgbWVhc3VyZSBjYWxsZWQgIkphY2NhcmQgZGlzdGFuY2UiIHRvIG1lYXN1cmUgdGhlIGRpZmZlcmVuY2VzLiBOb3RpY2UgdGhhdCB0aGUgc21hbGxlciB0aGUgbWVhc3VyZSwgdGhlIG1vcmUgc2ltaWxhciB0d28gY29uc3VtZXJzLiANCg0KYGBge3J9DQpkaXN0YW5jZSA8LSBkaXN0KGRhdGEubWF0cml4KGNvdXBvblssMjo0XSktMSwgIyBjb2VyY2UgaW50byBhIGJpbmFyeSBtYXRyaXgNCiAgICAgICAgICAgICAgICAgbWV0aG9kID0gImJpbmFyeSIpICMgY2hvb3NlIGJpbmFyeSBvciB0aGUgSmFjY2FyZCBtZWFzdXJlDQojIGNvZXJjZSB0aGUgZGlzdGFuY2UgbWF0cml4IGludG8gYSBub3JtYWwgbWF0cml4IGZvciBsYXRlciB1c2UNCmRpc3RhbmNlIDwtIGFzLm1hdHJpeChkaXN0YW5jZSkNCmRpc3RhbmNlWzE6MTAsMToxMF0gIyBqdXN0IHRvIGNoZWNrIHRoZSBmaXJzdCAxMCByb3dzIGFuZCBjb2x1bW5zDQpgYGANCg0KIyMjIyBTdGVwIDIgLSBmaW5kIHRoZSAiY2xvc2VzdCIgY29uc3VtZXJzDQpHaXZlbiB0aGUgZGlzdGFuY2UgbWF0cml4LCB3ZSBuZXh0IGZpbmQgdGhlIGNsb3Nlc3QgY29uc3VtZXJzIGZvciBlYWNoIGNvbnN1bWVyIGluIHRoZSBkYXRhLiBIZXJlLCB3ZSB1c2Ugc2FtcGxpbmcgd2l0aCByZXBsYWNlbWVudCwgbWVhbmluZyBhIGNvbnN1bWVyIG1heSBiZSBtYXRjaGVkIG11bHRpcGxlIHRpbWVzIHRvIG90aGVyIGNvbnN1bWVycy4gVGhpcyBpcyBnZW5lcmFsbHkgcHJlZmVycmVkIGZvciBzYW1sbGVyIGRhdGEuIA0KYGBge3J9DQojIGluaXRpYWxpemUgc29tZSBkaW1lbnNpb25zDQpOIDwtIGRpbShjb3Vwb24pWzFdDQpOLjEgPC0gc3VtKGNvdXBvbiR1c2VkX2NvdXBvbikNCg0KIyB0aGUgaW5kZXggb2YgdHJlYXRlZCBhbmQgY29udHJvbCB1bml0cw0KaWR4LjEgPC0gd2hpY2goY291cG9uJHVzZWRfY291cG9uPT0xKQ0KaWR4LjAgPC0gd2hpY2goY291cG9uJHVzZWRfY291cG9uPT0wKQ0KDQojIHdlIGNyZWF0ZSBhbiBlbXB0eSBsaXN0IHRvIHN0b3JlIHJlc3VsdHMNCmJlc3RfbWF0Y2hlcyA8LSB2ZWN0b3IobW9kZSA9ICJsaXN0IiwgTikNCmZvciAoaSBpbiAxOk4pIHsgIyBzZXBhcmF0ZSB0aGUgdHJlYXRlZCBhbmQgdGhlIGNvbnRyb2wNCiAgaWYgKGNvdXBvbiR1c2VkX2NvdXBvbltpXT09MSkgeyAjIGZvciB0aGUgdHJlYXRlZA0KICAgIGRpc3RfaSA8LSBkaXN0YW5jZVtpLGlkeC4wXSAjIGdldCB0aGUgZGlzdGFuY2VzIHRvIGFsbCB0aGUgY29udHJvbHMNCiAgICBiZXN0X2kgPC0gaWR4LjBbd2hpY2goZGlzdF9pPT1taW4oZGlzdF9pKSldICMgc2VsZWN0IGNvbnRyb2xzIHdpdGggc21hbGxlc3QgZGlzdGFuY2UNCiAgfSBlbHNlIGlmIChjb3Vwb24kdXNlZF9jb3Vwb25baV09PTApIHsgIyBmb3IgdGhlIGNvbnRyb2wgDQogICAgZGlzdF9pIDwtIGRpc3RhbmNlW2ksaWR4LjFdICMgZ2V0IHRoZSBkaXN0YW5jZXMgdG8gYWxsIHRoZSB0cmVhdGVkDQogICAgYmVzdF9pIDwtIGlkeC4xW3doaWNoKGRpc3RfaT09bWluKGRpc3RfaSkpXSAjIHNlbGVjdCB0cmVhdGVkIHdpdGggc21hbGxlc3QgZGlzdGFuY2UNCiAgfQ0KICBiZXN0X21hdGNoZXNbW2ldXSA8LSBiZXN0X2kgIyBzdG9yZSByZXN1bHRzDQp9DQpgYGANCiMjIyMgU3RlcCAzIC0gR2V0IHRoZSB0cmVhdG1lbnQgZWZmZWN0cw0KR2l2ZW4gdGhlIG1hdGNoZWQgc2FtcGxlcyBmb3IgZWFjaCBjb25zdW1lciwgd2UgZmlyc3QgdXMgdGhlIGF2ZXJhZ2Ugb2YgdGhlIG1hdGNoZWQgc2FtcGxlcyB0byBvYnRhaW4gdGhlIHBvdGVudGlhbCBvdXRjb21lcy4gDQpgYGB7cn0NCmdldF9wb3RlbnRpYWxfb3V0Y29tZXMgPC0gZnVuY3Rpb24gKHgpIHsNCiAgcmV0dXJuKG1lYW4oY291cG9uJG9yZGVyX3NpemVbeF0pKQ0KfQ0KcG90ZW50aWFsX3B1cmNoYXNlIDwtIHNhcHBseShiZXN0X21hdGNoZXMsZ2V0X3BvdGVudGlhbF9vdXRjb21lcyxzaW1wbGlmeSA9IFQpDQpgYGANCk5leHQsIHdlIGNhbiBjYWxjdWxhdGUgdGhlIEFUVCAoYXZlcmFnZSB0cmVhdG1lbnQgZWZmZWN0cyBvbiB0aGUgdHJlYXRlZCkgYW5kIHRoZSBBVEMgKGF2ZXJhZ2UgdHJlYXRtZW50IGVmZmVjdHMgb24gdGhlIGNvbnRyb2wpDQpgYGB7cn0NCkFUVF9tYXRjaGluZyA8LSBtZWFuKGNvdXBvbiRvcmRlcl9zaXplW2lkeC4xXSktDQogIG1lYW4ocG90ZW50aWFsX3B1cmNoYXNlW2lkeC4xXSkNCkFUQ19tYXRjaGluZyA8LSAtbWVhbihjb3Vwb24kb3JkZXJfc2l6ZVtpZHguMF0pKw0KICBtZWFuKHBvdGVudGlhbF9wdXJjaGFzZVtpZHguMF0pDQojQVRFIGlzIHRoZSB3ZWlnaHRlZCBhdmVyYWdlIG9mIEFUVCBhbmQgQVRDDQpBVEVfbWF0Y2hpbmcgPC0gTi4xL04qQVRUX21hdGNoaW5nICsNCiAgKDEtTi4xL04pKkFUQ19tYXRjaGluZw0KDQojIHByaW50IG91dCB0aGUgcmVzdWx0cw0KcHJpbnQobGlzdChBVEUgPSBBVEVfbWF0Y2hpbmcsDQogICAgICAgICAgIEFUVCA9IEFUVF9tYXRjaGluZywNCiAgICAgICAgICAgQVRDID0gQVRDX21hdGNoaW5nKSkNCmBgYA0KIyMjICoqV2VpZ2h0aW5nKioNCkFzIGluIHRoZSB0dXRvcmlhbCBvbiBjbGFzc2ljYWwgbWF0Y2hpbmcsIGFsbCB0aGUgc2VsZWN0aW9uIChvZiB0cmVhdG1lbnQgYXNzaWdubWVudCkgaXMgb24gdGhyZWUgdmFyaWFibGVzOiByZWNlbmN5LCBmcmVxdWVuY3ksIGFuZCBtb25ldGFyeS4gR2l2ZW4gdGhlIGRhdGEsIHRoZXJlIGFyZSB0d28gbWFpbiBwYXJ0cyB0byBlc3RpbWF0aW5nIHRyZWF0bWVudCBlZmZlY3RzIHVzaW5nIHdlaWdodGVkIHJlZ3Jlc3Npb24uIFRoZSBmaXJzdCBwYXJ0IGludm9sdmVzIG9idGFpbmluZyBlc3RpbWF0ZXMgb2YgY3VzdG9tZXJz4oCZIHByb3BlbnNpdGllcyB0byB1c2UgdGhlIGNvdXBvbi4gRm9yIHRoaXMgdHV0b3JpYWwsIHdlIHdpbGwgdXNlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gdG8gb2J0YWluIHRoZXNlIHByb3BlbnNpdHkgc2NvcmVzLiBUaGUgc2Vjb25kIHBhcnQgaW52b2x2ZXMgcGVyZm9ybWluZyB0aGUgd2VpZ2h0ZWQgcmVncmVzc2lvbiwgdXNpbmcgd2VpZ2h0cyB0aGF0IGFyZSBiYXNlZCBvbiB0aGUgcHJvcGVuc2l0eSBzY29yZXMgZXN0aW1hdGVkIGluIFBhcnQgMS4NCg0KIyMjIyBQYXJ0IDE6IEVzdGltYXRpbmcgdGhlIHByb3BlbnNpdHkgdG8gdXNlIHRoZSBjb3Vwb24NClRoZXJlIGFyZSB0aHJlZSB2YXJpYWJsZXMgdGhhdCB3ZSBjYW4gdXNlIHRvIGVzdGltYXRlIHRoZSBwcm9wZW5zaXR5IHRvIHVzZSB0aGUgY291cG9uOiByZWNlbmN5LCBmcmVxdWVuY3ksIGFuZCBtb25ldGFyeS4gVGhlc2UgdmFyaWFibGVzIGNvbGxlY3RpdmVseSBzYXRpc2Z5IHRoZSBiYWNrLWRvb3IgY3JpdGVyaW9uIGZvciBibG9ja2luZyBhc3NvY2lhdGlvbnMgYmV0d2VlbiBjb3Vwb24gdXNlIGFuZCBvcmRlciBzaXplLiBUaGF0IGlzLCB3ZSBjYW4gY29uZGl0aW9uIG9uIHRoZXNlIHZhcmlhYmxlcyB0byBibG9jayBhbGwgYmFjay1kb29yIHBhdGhzIGJldHdlZW4gdXNlZF9jb3Vwb24gYW5kIHRvdGFsX29yZGVyLiANCg0KVG8gZXN0aW1hdGUgdGhlIHByb3BlbnNpdGllcywgd2Ugc2V0IHVwIGEgbG9naXN0aWMgcmVncmVzc2lvbi4gQmVjYXVzZSBvdXIgb2JqZWN0aXZlIGlzIHRvIGVzdGltYXRlIGN1c3RvbWVyc+KAmSBwcm9wZW5zaXRpZXMgdG8gdXNlIHRoZSBjb3Vwb24sIHdlIG1ha2UgdXNlZF9jb3Vwb24gdGhlIGRlcGVuZGVudCB2YXJpYWJsZSBpbiB0aGUgcmVncmVzc2lvbi4gRm9yIHRoZSBtb2RlbCBzcGVjLCB3ZSB3aWxsIGFjY291bnQgZm9yIGFsbCBvbmx5IHRoZSBtYWluIGVmZmVjdHMuIFlvdSBtYXkgdHJ5IGFsdGVybmF0aXZlIHNwZWNzIHN1Y2ggYXMgd2l0aCBhbGwgMi0gYW5kIDMtd2F5IGludGVyYWN0aW9ucy4gDQpgYGB7cn0NCnByb3BlbnNpdHlfZml0IDwtIA0KICAgIGdsbSh1c2VkX2NvdXBvbiB+IHJlY2VuY3kgKyBmcmVxdWVuY3kgKyBtb25ldGFyeSwgZGF0YSA9IGNvdXBvbiwNCiAgICAgICAgZmFtaWx5ID0gYmlub21pYWwpDQpzdW1tYXJ5KHByb3BlbnNpdHlfZml0KQ0KYGBgDQpCYXNlZCBvbiB0aGUgY2FsaWJlcmF0ZWQgbW9kZWwsIHdlIHRoZSBvYnRhaW4gdGhlIHByb3BlbnNpdHkgc2NvcmVzIG9yIHRoZSBsaWtlbGlob29kIG9mIGJlaW5nIGFzc2lnbmVkIGNvdXBvbnMuIA0KYGBge3J9DQpwIDwtIHByZWRpY3QocHJvcGVuc2l0eV9maXQsIHR5cGUgPSAncmVzcG9uc2UnKQ0KIyB2aXN1YWxpemUgdGhlIHByb3BlbnNpdHkgc2NvcmVzIGJ5IGdyb3Vwcw0KcGFyKG1mcm93PWMoMSwyKSkNCmhpc3QocFtpZHguMF0pDQpoaXN0KHBbaWR4LjFdKQ0KYGBgDQpXaXRoIHRoZSBwcm9wZW5zaXR5IHNjb3JlLCB3ZSBydW4gd2VpZ2h0ZWQgT0xTIHRvIG9idGFpbiB0aGUgQVRFLCBBVFQgYW5kIEFUQy5Gb3IgQVRFLCB3ZSB3ZWlnaHQgdGhlIHRyZWF0bWVudCBncm91cCBhbmQgY29udHJvbCBncm91cCBieSAkXGRmcmFjezF9e2V9JCBhbmQgJFxkZnJhY3sxfXsxLWV9JCwgcmVzcGVjdGl2ZWx5LiBGb3IgQVRULCB3ZSB3ZWlnaHQgdGhlIGNvbnRyb2wgZ3JvdXAgYnkgJFxkZnJhY3tlfXsxLWV9JCBhbmQgZm9yIEFUQywgdGhlIHRyZWF0bWVudCBncm91cCBieSAkXGRmcmFjezEtZX17ZX0kLg0KYGBge3J9DQp3X2F0ZSA8LSBwDQp3X2F0ZVtpZHguMV0gPC0gMS9wW2lkeC4xXSANCndfYXRlW2lkeC4wXSA8LSAxLygxLXBbaWR4LjBdKQ0KDQp3X2F0dCA8LSByZXAoMSxOKSANCndfYXR0W2lkeC4wXSA8LSBwW2lkeC4wXS8oMS1wW2lkeC4wXSkNCg0Kd19hdGMgPC0gcmVwKDEsTikNCndfYXRjW2lkeC4xXSA8LSAoMS1wW2lkeC4xXSkvcFtpZHguMV0NCmBgYA0KUnVuIGEgd2VpZ2h0ZWQgT0xTIHRvIG9idGFpbiB0aGUgQVRFLCBBVFQgYW5kIEFUQzoNCmBgYHtyfQ0KQVRFX3dlaWdodGluZyA8LSBsbShvcmRlcl9zaXplIH4gdXNlZF9jb3Vwb24gKyByZWNlbmN5ICsgZnJlcXVlbmN5ICsgbW9uZXRhcnksIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRhdGEgPSBjb3Vwb24sIHdlaWdodHMgPSB3X2F0ZSkNCnN1bW1hcnkoQVRFX3dlaWdodGluZykNCmBgYA0KYGBge3J9DQpBVFRfd2VpZ2h0aW5nIDwtIGxtKG9yZGVyX3NpemUgfiB1c2VkX2NvdXBvbiArIHJlY2VuY3kgKyBmcmVxdWVuY3kgKyBtb25ldGFyeSwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgZGF0YSA9IGNvdXBvbiwgd2VpZ2h0cyA9IHdfYXR0KQ0Kc3VtbWFyeShBVFRfd2VpZ2h0aW5nKQ0KYGBgDQpgYGB7cn0NCkFUQ193ZWlnaHRpbmcgPC0gbG0ob3JkZXJfc2l6ZSB+IHVzZWRfY291cG9uICsgcmVjZW5jeSArIGZyZXF1ZW5jeSArIG1vbmV0YXJ5LCANCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBkYXRhID0gY291cG9uLCB3ZWlnaHRzID0gd19hdGMpDQpzdW1tYXJ5KEFUQ193ZWlnaHRpbmcpDQpgYGANCiMjIyAqKlN1bW1hcnkqKg0KSW4gZ2VuZXJhbCwgeW91IHdpbGwgc2VlIGRpZmZlcmVuY2VzIGluIHRoZSBlc3RpbWF0ZXMgcHJvZHVjZWQgYnkgZGlmZmVyZW50IG1ldGhvZHMuIFRoaXMgaXMgY2FsbGVkIGEgIm1ldGhvZCBiaWFzIi4gQ29udmVudGlvbmFsbHksIHBlb3BsZSBydW4gdmFyaW91cyBhbmFseXNlcyB0byBzaG93IHRoZSByb2J1c3RuZXNzIG9mIHRoZSBlc3RpbWF0ZXMuIA0K