Goals:

  • Handcode Double ML for ATE using AIPW

  • Implement it using the causalDML package


Introducing the data

The Application Notebook builds on the dataset that is kindly provided in the hdm package. The data was used in Chernozhukov and Hansen (2004). Their paper investigates the effect of participation in the employer-sponsored 401(k) retirement savings plan (p401) on net assets (net_tfa). Since then the data was used to showcase many new methods. It is not the most comprehensive dataset with basically ten covariates/regressors/predictors:

  • age: age

  • db: defined benefit pension

  • educ: education (in years)

  • fsize: family size

  • hown: home owner

  • inc: income (in US $)

  • male: male

  • marr: married

  • pira: participation in individual retirement account (IRA)

  • twoearn: two earners

However, it is publicly available and the relatively few covariates ensure that the programs do not run too long.

# To install the causalDML package uncomment the following two lines
# library(devtools)
# install_github(repo="MCKnaus/causalDML")

# Load the packages required for later
library(hdm)
library(tidyverse)
library(causalDML)
library(grf)
library(lmtest)
library(sandwich)


set.seed(1234) # for replicability
options(scipen = 10) # Switch off scientific notation

data(pension)
# Outcome
Y = pension$net_tfa
# Treatment
W = pension$p401
# Create main effects matrix
X = model.matrix(~ 0 + age + db + educ + fsize + hown + inc + male + marr + pira + twoearn, data = pension)


We want to estimate the effect of 401(k) participation on net assets. Today without imposing effect heterogeneity.



AIPW Double ML

Hand-coded

To implement the AIPW we estimate the nuisance parameters \(e(X)=E[W|X]\), \(m(0,X)=E[Y|W=0,X]\) and \(m(1,X)=E[Y|W=1,X]\) using random forest and plug the predictions into the pseudo outcome: \[ \begin{align} \tilde{Y}_{\gamma_0} & = \underbrace{\hat{m}(0,X)}_{\text{outcome predictions}} + \underbrace{\frac{(1-W) (Y - \hat{m}(0,X))}{1-\hat{e}(X)}}_{\text{weighted residuals}} \\ \tilde{Y}_{\gamma_1} & = \underbrace{\hat{m}(1,X)}_{\text{outcome predictions}} + \underbrace{\frac{W (Y - \hat{m}(1,X))}{\hat{e}(X)}}_{\text{weighted residuals}} \\ \tilde{Y}_{ATE} & = \tilde{Y}_{\gamma_1} - \tilde{Y}_{\gamma_0} \\ &= \underbrace{\hat{m}(1,X) - \hat{m}(0,X)}_{\text{outcome predictions}} + \underbrace{\frac{W (Y - \hat{m}(1,X))}{\hat{e}(X)} - \frac{(1-W) (Y - \hat{m}(0,X))}{1-\hat{e}(X)}}_{\text{weighted residuals}} \end{align} \]

The theoretical results require that we predict the nuisance parameters out-of-sample. The easiest way to do this is two-fold cross-fitting:

  • Split the sample in two random subsamples, S1 and S2

  • Form prediction models in S1, use it to predict in S2

  • Form prediction models in S2, use it to predict in S1

# 2-fold cross-fitting
n = length(Y)
m0hat = m1hat = ehat = rep(NA,n)
# Draw random indices for sample 1
index_s1 = sample(1:n,n/2)
# Create S1
x1 = X[index_s1,]
w1 = W[index_s1]
y1 = Y[index_s1]
# Create sample 2 with those not in S1
x2 = X[-index_s1,]
w2 = W[-index_s1]
y2 = Y[-index_s1]
# Model in S1, predict in S2
rf = regression_forest(x1,w1)
ehat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x1[w1==0,],y1[w1==0])
m0hat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x1[w1==1,],y1[w1==1])
m1hat[-index_s1] = predict(rf,newdata=x2)$predictions
# Model in S2, predict in S1
rf = regression_forest(x2,w2)
ehat[index_s1] = predict(rf,newdata=x1)$predictions
rf = regression_forest(x2[w2==0,],y2[w2==0])
m0hat[index_s1] = predict(rf,newdata=x1)$predictions
rf = regression_forest(x2[w2==1,],y2[w2==1])
m1hat[index_s1] = predict(rf,newdata=x1)$predictions
  • Create the pseudo-outcomes for APOs

\[ \begin{align} \tilde{Y}_{\gamma_0} & = \hat{m}(0,X) + \frac{(1-W) (Y - \hat{m}(0,X))}{1-\hat{e}(X)} \\ \tilde{Y}_{\gamma_1} & = \hat{m}(1,X) + \frac{W (Y - \hat{m}(1,X))}{\hat{e}(X)} \end{align} \]

Y_t_0 = m0hat + (1-W)*(Y-m0hat)/(1-ehat)
Y_t_1 = m1hat + W*(Y-m1hat)/ehat
  • Use the APO pseudo-outcomes in a simple OLS with only a constant to get the APO estimates and inference (this is equivalent to running a t-test on the mean of the pseudo-outcome)
summary(lm(Y_t_0 ~ 1))

Call:
lm(formula = Y_t_0 ~ 1)

Residuals:
    Min      1Q  Median      3Q     Max 
-800176  -15814  -13718   -2679 2706849 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  14152.5      793.7   17.83   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 79040 on 9914 degrees of freedom
mean(Y_t_0)
[1] 14152.48
summary(lm(Y_t_1 ~ 1))

Call:
lm(formula = Y_t_1 ~ 1)

Residuals:
     Min       1Q   Median       3Q      Max 
-1508685   -21560   -13401     5176  3302290 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  25638.2      956.1   26.82   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 95200 on 9914 degrees of freedom
mean(Y_t_1)
[1] 25638.21
  • Create the pseudo-outcome for ATE and use it in a simple OLS with only a constant to get the ATE point estimate and inference:

\[ \begin{align} \tilde{Y}_{ATE} & = \tilde{Y}_{\gamma_1} - \tilde{Y}_{\gamma_0} \end{align} \]

Y_ate = Y_t_1 - Y_t_0

summary(lm(Y_ate ~ 1))

Call:
lm(formula = Y_ate ~ 1)

Residuals:
     Min       1Q   Median       3Q      Max 
-2635515   -13172    -2157    12260  3290639 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)    11486       1160   9.899   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 115500 on 9914 degrees of freedom

I think this is really neat. We need to be careful in constructing the pseudo-outcomes. However, at the end it boils down to run the simplest OLS you can think of and can use the familiar standard errors to test against the null hypothesis of a zero effect.



Double ML for AIPW with causalDML package

2-fold cross-fitting is easy to implement but especially in small sample sizes, using only 50% of the data to estimate the nuisance parameters might lead to unstable predictions.

Thus, we use the DML_aipw function of the causalDML package to run 5-fold cross-fitting. This package requires to create the methods that we use because it allows for ensemble methods (for a more detailed intro see the GitHub page). For now, we focus again on honest random forest.

With 5-fold cross-fitting, we split the sample in 5 folds and use 4 folds (80% of the data) to predict the left out fold (20% of the data). We iterate such that every fold is left out once.

# 5-fold cross-fitting with causalDML package
# Create learner
forest = create_method("forest_grf",args=list(tune.parameters = "all"))
# Run and 
aipw = DML_aipw(Y,W,X,ml_w=list(forest),ml_y=list(forest),cf=5)

Let’s first have a look at the estimated average potential outcomes:

summary(aipw$APO)
       APO       SE
0 14165.56 799.3773
1 25820.97 972.8471
plot(aipw$APO)

The average treatment effect is then just the difference between the two potential outcomes:

summary(aipw$ATE)
          ATE      SE      t         p    
1 - 0 11655.4  1175.5 9.9154 < 2.2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Finally, we can use the same nuisance parameters to estimate the ATT:

APO_att = APO_dml_atet(Y,aipw$APO$m_mat,aipw$APO$w_mat,aipw$APO$e_mat,aipw$APO$cf_mat)
ATT = ATE_dml(APO_att)
summary(ATT)
         ATET      SE      t         p    
1 - 0 14867.9  1903.7 7.8099 6.302e-15 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

We find that the ATT is roughly $3000 higher than the ATE:

# Collect the results
Effect = c(aipw$ATE$result[1],ATT$results[1])
se = c(aipw$ATE$result[2],ATT$results[2])
data.frame(Effect,se,
                Target = c("ATE","ATT"),
                cil = Effect - 1.96*se,
                ciu = Effect + 1.96*se)  %>% 
  ggplot(aes(x=Target,y=Effect,ymin=cil,ymax=ciu)) + geom_point(size=2.5) + geom_errorbar(width=0.15)  +
  geom_hline(yintercept=0) + xlab("Target parameter")

If you want to understand whether ATE and ATT are statistically significant, check out application notebook ANB_Generic_DML.



LS0tDQp0aXRsZTogIkNhdXNhbCBNTDogRG91YmxlIE1MIGZvciBhdmVyYWdlIHRyZWF0bWVudCBlZmZlY3RzIg0Kc3VidGl0bGU6ICJBcHBsaWNhdGlvbiBub3RlYm9vayINCmF1dGhvcjogIk1pY2hhZWwgS25hdXMiDQpkYXRlOiAiYHIgZm9ybWF0KFN5cy50aW1lKCksICclbS8leScpYCINCm91dHB1dDogDQogIGh0bWxfbm90ZWJvb2s6DQogICAgdG9jOiB0cnVlDQogICAgdG9jX2Zsb2F0OiB0cnVlDQogICAgY29kZV9mb2xkaW5nOiBzaG93DQotLS0NCg0KDQpHb2FsczoNCg0KLSBIYW5kY29kZSBEb3VibGUgTUwgZm9yIEFURSB1c2luZyBBSVBXDQoNCi0gSW1wbGVtZW50IGl0IHVzaW5nIHRoZSBgY2F1c2FsRE1MYCBwYWNrYWdlDQoNCjxicj4NCg0KIyBJbnRyb2R1Y2luZyB0aGUgZGF0YQ0KDQpUaGUgQXBwbGljYXRpb24gTm90ZWJvb2sgYnVpbGRzIG9uIHRoZSBkYXRhc2V0IHRoYXQgaXMga2luZGx5IHByb3ZpZGVkIGluIHRoZSBgaGRtYCBwYWNrYWdlLiBUaGUgZGF0YSB3YXMgdXNlZCBpbiBbQ2hlcm5vemh1a292IGFuZCBIYW5zZW4gKDIwMDQpXShodHRwczovL2RpcmVjdC5taXQuZWR1L3Jlc3QvYXJ0aWNsZS84Ni8zLzczNS81NzU4Ni9UaGUtRWZmZWN0cy1vZi00MDEtSy1QYXJ0aWNpcGF0aW9uLW9uLXRoZS1XZWFsdGgpLiBUaGVpciBwYXBlciBpbnZlc3RpZ2F0ZXMgdGhlIGVmZmVjdCBvZiBwYXJ0aWNpcGF0aW9uIGluIHRoZSBlbXBsb3llci1zcG9uc29yZWQgNDAxKGspIHJldGlyZW1lbnQgc2F2aW5ncyBwbGFuIChgcDQwMWApIG9uIG5ldCBhc3NldHMgKGBuZXRfdGZhYCkuIFNpbmNlIHRoZW4gdGhlIGRhdGEgd2FzIHVzZWQgdG8gc2hvd2Nhc2UgbWFueSBuZXcgbWV0aG9kcy4gSXQgaXMgbm90IHRoZSBtb3N0IGNvbXByZWhlbnNpdmUgZGF0YXNldCB3aXRoIGJhc2ljYWxseSB0ZW4gY292YXJpYXRlcy9yZWdyZXNzb3JzL3ByZWRpY3RvcnM6DQoNCi0gKmFnZSo6IGFnZQ0KDQotICpkYio6IGRlZmluZWQgYmVuZWZpdCBwZW5zaW9uDQoNCi0gKmVkdWMqOiBlZHVjYXRpb24gKGluIHllYXJzKQ0KDQotICpmc2l6ZSo6IGZhbWlseSBzaXplDQoNCi0gKmhvd24qOiBob21lIG93bmVyDQoNCi0gKmluYyo6IGluY29tZSAoaW4gVVMgJCkNCg0KLSAqbWFsZSo6IG1hbGUNCg0KLSAqbWFycio6IG1hcnJpZWQNCg0KLSAqcGlyYSo6IHBhcnRpY2lwYXRpb24gaW4gaW5kaXZpZHVhbCByZXRpcmVtZW50IGFjY291bnQgKElSQSkNCg0KLSAqdHdvZWFybio6IHR3byBlYXJuZXJzDQoNCkhvd2V2ZXIsIGl0IGlzIHB1YmxpY2x5IGF2YWlsYWJsZSBhbmQgdGhlIHJlbGF0aXZlbHkgZmV3IGNvdmFyaWF0ZXMgZW5zdXJlIHRoYXQgdGhlIHByb2dyYW1zIGRvIG5vdCBydW4gdG9vIGxvbmcuDQoNCmBgYHtyLCB3YXJuaW5nID0gRiwgbWVzc2FnZSA9IEZ9DQojIFRvIGluc3RhbGwgdGhlIGNhdXNhbERNTCBwYWNrYWdlIHVuY29tbWVudCB0aGUgZm9sbG93aW5nIHR3byBsaW5lcw0KIyBsaWJyYXJ5KGRldnRvb2xzKQ0KIyBpbnN0YWxsX2dpdGh1YihyZXBvPSJNQ0tuYXVzL2NhdXNhbERNTCIpDQoNCiMgTG9hZCB0aGUgcGFja2FnZXMgcmVxdWlyZWQgZm9yIGxhdGVyDQpsaWJyYXJ5KGhkbSkNCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeShjYXVzYWxETUwpDQpsaWJyYXJ5KGdyZikNCmxpYnJhcnkobG10ZXN0KQ0KbGlicmFyeShzYW5kd2ljaCkNCg0KDQpzZXQuc2VlZCgxMjM0KSAjIGZvciByZXBsaWNhYmlsaXR5DQpvcHRpb25zKHNjaXBlbiA9IDEwKSAjIFN3aXRjaCBvZmYgc2NpZW50aWZpYyBub3RhdGlvbg0KDQpkYXRhKHBlbnNpb24pDQojIE91dGNvbWUNClkgPSBwZW5zaW9uJG5ldF90ZmENCiMgVHJlYXRtZW50DQpXID0gcGVuc2lvbiRwNDAxDQojIENyZWF0ZSBtYWluIGVmZmVjdHMgbWF0cml4DQpYID0gbW9kZWwubWF0cml4KH4gMCArIGFnZSArIGRiICsgZWR1YyArIGZzaXplICsgaG93biArIGluYyArIG1hbGUgKyBtYXJyICsgcGlyYSArIHR3b2Vhcm4sIGRhdGEgPSBwZW5zaW9uKQ0KYGBgDQoNCjxicj4NCg0KV2Ugd2FudCB0byBlc3RpbWF0ZSB0aGUgZWZmZWN0IG9mIDQwMShrKSBwYXJ0aWNpcGF0aW9uIG9uIG5ldCBhc3NldHMuIFRvZGF5ICoqd2l0aG91dCBpbXBvc2luZyBlZmZlY3QgaGV0ZXJvZ2VuZWl0eSoqLg0KDQo8YnI+DQo8YnI+DQoNCiMgQUlQVyBEb3VibGUgTUwNCg0KIyMgSGFuZC1jb2RlZA0KDQpUbyBpbXBsZW1lbnQgdGhlIEFJUFcgd2UgZXN0aW1hdGUgdGhlIG51aXNhbmNlIHBhcmFtZXRlcnMgJGUoWCk9RVtXfFhdJCwgJG0oMCxYKT1FW1l8Vz0wLFhdJCBhbmQgJG0oMSxYKT1FW1l8Vz0xLFhdJCB1c2luZyByYW5kb20gZm9yZXN0IGFuZCBwbHVnIHRoZSBwcmVkaWN0aW9ucyBpbnRvIHRoZSBwc2V1ZG8gb3V0Y29tZToNCiQkDQpcYmVnaW57YWxpZ259DQpcdGlsZGV7WX1fe1xnYW1tYV8wfSAmID0gXHVuZGVyYnJhY2V7XGhhdHttfSgwLFgpfV97XHRleHR7b3V0Y29tZSBwcmVkaWN0aW9uc319ICsgXHVuZGVyYnJhY2V7XGZyYWN7KDEtVykgKFkgLSBcaGF0e219KDAsWCkpfXsxLVxoYXR7ZX0oWCl9fV97XHRleHR7d2VpZ2h0ZWQgcmVzaWR1YWxzfX0gXFwNClx0aWxkZXtZfV97XGdhbW1hXzF9ICYgPSBcdW5kZXJicmFjZXtcaGF0e219KDEsWCl9X3tcdGV4dHtvdXRjb21lIHByZWRpY3Rpb25zfX0gKyBcdW5kZXJicmFjZXtcZnJhY3tXIChZIC0gXGhhdHttfSgxLFgpKX17XGhhdHtlfShYKX19X3tcdGV4dHt3ZWlnaHRlZCByZXNpZHVhbHN9fSBcXA0KXHRpbGRle1l9X3tBVEV9ICYgPSBcdGlsZGV7WX1fe1xnYW1tYV8xfSAtIFx0aWxkZXtZfV97XGdhbW1hXzB9IFxcIA0KJj0gXHVuZGVyYnJhY2V7XGhhdHttfSgxLFgpIC0gXGhhdHttfSgwLFgpfV97XHRleHR7b3V0Y29tZSBwcmVkaWN0aW9uc319ICsgXHVuZGVyYnJhY2V7XGZyYWN7VyAoWSAtIFxoYXR7bX0oMSxYKSl9e1xoYXR7ZX0oWCl9IC0gXGZyYWN7KDEtVykgKFkgLSBcaGF0e219KDAsWCkpfXsxLVxoYXR7ZX0oWCl9fV97XHRleHR7d2VpZ2h0ZWQgcmVzaWR1YWxzfX0NClxlbmR7YWxpZ259DQokJA0KDQpUaGUgdGhlb3JldGljYWwgcmVzdWx0cyByZXF1aXJlIHRoYXQgd2UgcHJlZGljdCB0aGUgbnVpc2FuY2UgcGFyYW1ldGVycyBvdXQtb2Ytc2FtcGxlLiBUaGUgZWFzaWVzdCB3YXkgdG8gZG8gdGhpcyBpcyB0d28tZm9sZCBjcm9zcy1maXR0aW5nOg0KDQotIFNwbGl0IHRoZSBzYW1wbGUgaW4gdHdvIHJhbmRvbSBzdWJzYW1wbGVzLCBTMSBhbmQgUzINCg0KLSBGb3JtIHByZWRpY3Rpb24gbW9kZWxzIGluIFMxLCB1c2UgaXQgdG8gcHJlZGljdCBpbiBTMg0KDQotIEZvcm0gcHJlZGljdGlvbiBtb2RlbHMgaW4gUzIsIHVzZSBpdCB0byBwcmVkaWN0IGluIFMxDQoNCg0KYGBge3J9DQojIDItZm9sZCBjcm9zcy1maXR0aW5nDQpuID0gbGVuZ3RoKFkpDQptMGhhdCA9IG0xaGF0ID0gZWhhdCA9IHJlcChOQSxuKQ0KIyBEcmF3IHJhbmRvbSBpbmRpY2VzIGZvciBzYW1wbGUgMQ0KaW5kZXhfczEgPSBzYW1wbGUoMTpuLG4vMikNCiMgQ3JlYXRlIFMxDQp4MSA9IFhbaW5kZXhfczEsXQ0KdzEgPSBXW2luZGV4X3MxXQ0KeTEgPSBZW2luZGV4X3MxXQ0KIyBDcmVhdGUgc2FtcGxlIDIgd2l0aCB0aG9zZSBub3QgaW4gUzENCngyID0gWFstaW5kZXhfczEsXQ0KdzIgPSBXWy1pbmRleF9zMV0NCnkyID0gWVstaW5kZXhfczFdDQojIE1vZGVsIGluIFMxLCBwcmVkaWN0IGluIFMyDQpyZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgxLHcxKQ0KZWhhdFstaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgyKSRwcmVkaWN0aW9ucw0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4MVt3MT09MCxdLHkxW3cxPT0wXSkNCm0waGF0Wy1pbmRleF9zMV0gPSBwcmVkaWN0KHJmLG5ld2RhdGE9eDIpJHByZWRpY3Rpb25zDQpyZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgxW3cxPT0xLF0seTFbdzE9PTFdKQ0KbTFoYXRbLWluZGV4X3MxXSA9IHByZWRpY3QocmYsbmV3ZGF0YT14MikkcHJlZGljdGlvbnMNCiMgTW9kZWwgaW4gUzIsIHByZWRpY3QgaW4gUzENCnJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeDIsdzIpDQplaGF0W2luZGV4X3MxXSA9IHByZWRpY3QocmYsbmV3ZGF0YT14MSkkcHJlZGljdGlvbnMNCnJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeDJbdzI9PTAsXSx5Mlt3Mj09MF0pDQptMGhhdFtpbmRleF9zMV0gPSBwcmVkaWN0KHJmLG5ld2RhdGE9eDEpJHByZWRpY3Rpb25zDQpyZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgyW3cyPT0xLF0seTJbdzI9PTFdKQ0KbTFoYXRbaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgxKSRwcmVkaWN0aW9ucw0KYGBgDQoNCi0gQ3JlYXRlIHRoZSBwc2V1ZG8tb3V0Y29tZXMgZm9yIEFQT3MNCg0KJCQNClxiZWdpbnthbGlnbn0NClx0aWxkZXtZfV97XGdhbW1hXzB9ICYgPSBcaGF0e219KDAsWCkgKyBcZnJhY3soMS1XKSAoWSAtIFxoYXR7bX0oMCxYKSl9ezEtXGhhdHtlfShYKX0gXFwNClx0aWxkZXtZfV97XGdhbW1hXzF9ICYgPSBcaGF0e219KDEsWCkgKyBcZnJhY3tXIChZIC0gXGhhdHttfSgxLFgpKX17XGhhdHtlfShYKX0NClxlbmR7YWxpZ259DQokJA0KDQpgYGB7cn0NCllfdF8wID0gbTBoYXQgKyAoMS1XKSooWS1tMGhhdCkvKDEtZWhhdCkNCllfdF8xID0gbTFoYXQgKyBXKihZLW0xaGF0KS9laGF0DQpgYGANCg0KLSBVc2UgdGhlIEFQTyBwc2V1ZG8tb3V0Y29tZXMgaW4gYSBzaW1wbGUgT0xTIHdpdGggb25seSBhIGNvbnN0YW50IHRvIGdldCB0aGUgQVBPIGVzdGltYXRlcyBhbmQgaW5mZXJlbmNlICh0aGlzIGlzIGVxdWl2YWxlbnQgdG8gcnVubmluZyBhIHQtdGVzdCBvbiB0aGUgbWVhbiBvZiB0aGUgcHNldWRvLW91dGNvbWUpDQoNCmBgYHtyfQ0Kc3VtbWFyeShsbShZX3RfMCB+IDEpKQ0KbWVhbihZX3RfMCkNCnN1bW1hcnkobG0oWV90XzEgfiAxKSkNCm1lYW4oWV90XzEpDQpgYGANCg0KLSBDcmVhdGUgdGhlIHBzZXVkby1vdXRjb21lIGZvciBBVEUgYW5kIHVzZSBpdCBpbiBhIHNpbXBsZSBPTFMgd2l0aCBvbmx5IGEgY29uc3RhbnQgdG8gZ2V0IHRoZSBBVEUgcG9pbnQgZXN0aW1hdGUgYW5kIGluZmVyZW5jZToNCg0KJCQNClxiZWdpbnthbGlnbn0NClx0aWxkZXtZfV97QVRFfSAmID0gXHRpbGRle1l9X3tcZ2FtbWFfMX0gLSBcdGlsZGV7WX1fe1xnYW1tYV8wfQ0KXGVuZHthbGlnbn0NCiQkDQoNCmBgYHtyfQ0KWV9hdGUgPSBZX3RfMSAtIFlfdF8wDQoNCnN1bW1hcnkobG0oWV9hdGUgfiAxKSkNCmBgYA0KDQpJIHRoaW5rIHRoaXMgaXMgcmVhbGx5IG5lYXQuIFdlIG5lZWQgdG8gYmUgY2FyZWZ1bCBpbiBjb25zdHJ1Y3RpbmcgdGhlIHBzZXVkby1vdXRjb21lcy4gSG93ZXZlciwgYXQgdGhlIGVuZCBpdCBib2lscyBkb3duIHRvIHJ1biB0aGUgc2ltcGxlc3QgT0xTIHlvdSBjYW4gdGhpbmsgb2YgYW5kIGNhbiB1c2UgdGhlIGZhbWlsaWFyIHN0YW5kYXJkIGVycm9ycyB0byB0ZXN0IGFnYWluc3QgdGhlIG51bGwgaHlwb3RoZXNpcyBvZiBhIHplcm8gZWZmZWN0Lg0KDQo8YnI+DQo8YnI+DQoNCg0KIyBEb3VibGUgTUwgZm9yIEFJUFcgd2l0aCBgY2F1c2FsRE1MYCBwYWNrYWdlDQoNCjItZm9sZCBjcm9zcy1maXR0aW5nIGlzIGVhc3kgdG8gaW1wbGVtZW50IGJ1dCBlc3BlY2lhbGx5IGluIHNtYWxsIHNhbXBsZSBzaXplcywgdXNpbmcgb25seSA1MCUgb2YgdGhlIGRhdGEgdG8gZXN0aW1hdGUgdGhlIG51aXNhbmNlIHBhcmFtZXRlcnMgbWlnaHQgbGVhZCB0byB1bnN0YWJsZSBwcmVkaWN0aW9ucy4NCg0KVGh1cywgd2UgdXNlIHRoZSBgRE1MX2FpcHdgIGZ1bmN0aW9uIG9mIHRoZSBgY2F1c2FsRE1MYCBwYWNrYWdlIHRvIHJ1biA1LWZvbGQgY3Jvc3MtZml0dGluZy4gIFRoaXMgcGFja2FnZSByZXF1aXJlcyB0byBjcmVhdGUgdGhlIG1ldGhvZHMgdGhhdCB3ZSB1c2UgYmVjYXVzZSBpdCBhbGxvd3MgZm9yIGVuc2VtYmxlIG1ldGhvZHMgKGZvciBhIG1vcmUgZGV0YWlsZWQgaW50cm8gc2VlIHRoZSBbR2l0SHViIHBhZ2VdKGh0dHBzOi8vZ2l0aHViLmNvbS9NQ0tuYXVzL2NhdXNhbERNTCkpLiBGb3Igbm93LCB3ZSBmb2N1cyBhZ2FpbiBvbiBob25lc3QgcmFuZG9tIGZvcmVzdC4NCg0KV2l0aCA1LWZvbGQgY3Jvc3MtZml0dGluZywgd2Ugc3BsaXQgdGhlIHNhbXBsZSBpbiA1IGZvbGRzIGFuZCB1c2UgNCBmb2xkcyAoODAlIG9mIHRoZSBkYXRhKSB0byBwcmVkaWN0IHRoZSBsZWZ0IG91dCBmb2xkICgyMCUgb2YgdGhlIGRhdGEpLiBXZSBpdGVyYXRlIHN1Y2ggdGhhdCBldmVyeSBmb2xkIGlzIGxlZnQgb3V0IG9uY2UuDQoNCmBgYHtyfQ0KIyA1LWZvbGQgY3Jvc3MtZml0dGluZyB3aXRoIGNhdXNhbERNTCBwYWNrYWdlDQojIENyZWF0ZSBsZWFybmVyDQpmb3Jlc3QgPSBjcmVhdGVfbWV0aG9kKCJmb3Jlc3RfZ3JmIixhcmdzPWxpc3QodHVuZS5wYXJhbWV0ZXJzID0gImFsbCIpKQ0KIyBSdW4gYW5kIA0KYWlwdyA9IERNTF9haXB3KFksVyxYLG1sX3c9bGlzdChmb3Jlc3QpLG1sX3k9bGlzdChmb3Jlc3QpLGNmPTUpDQpgYGANCg0KTGV0J3MgZmlyc3QgaGF2ZSBhIGxvb2sgYXQgdGhlIGVzdGltYXRlZCBhdmVyYWdlIHBvdGVudGlhbCBvdXRjb21lczoNCg0KYGBge3J9DQpzdW1tYXJ5KGFpcHckQVBPKQ0KcGxvdChhaXB3JEFQTykNCmBgYA0KDQpUaGUgYXZlcmFnZSB0cmVhdG1lbnQgZWZmZWN0IGlzIHRoZW4ganVzdCB0aGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSB0d28gcG90ZW50aWFsIG91dGNvbWVzOg0KDQpgYGB7cn0NCnN1bW1hcnkoYWlwdyRBVEUpDQpgYGANCg0KRmluYWxseSwgd2UgY2FuIHVzZSB0aGUgc2FtZSBudWlzYW5jZSBwYXJhbWV0ZXJzIHRvIGVzdGltYXRlIHRoZSBBVFQ6DQoNCmBgYHtyfQ0KQVBPX2F0dCA9IEFQT19kbWxfYXRldChZLGFpcHckQVBPJG1fbWF0LGFpcHckQVBPJHdfbWF0LGFpcHckQVBPJGVfbWF0LGFpcHckQVBPJGNmX21hdCkNCkFUVCA9IEFURV9kbWwoQVBPX2F0dCkNCnN1bW1hcnkoQVRUKQ0KYGBgDQoNCldlIGZpbmQgdGhhdCB0aGUgQVRUIGlzIHJvdWdobHkgJDMwMDAgaGlnaGVyIHRoYW4gdGhlIEFURToNCg0KYGBge3J9DQojIENvbGxlY3QgdGhlIHJlc3VsdHMNCkVmZmVjdCA9IGMoYWlwdyRBVEUkcmVzdWx0WzFdLEFUVCRyZXN1bHRzWzFdKQ0Kc2UgPSBjKGFpcHckQVRFJHJlc3VsdFsyXSxBVFQkcmVzdWx0c1syXSkNCmRhdGEuZnJhbWUoRWZmZWN0LHNlLA0KICAgICAgICAgICAgICAgIFRhcmdldCA9IGMoIkFURSIsIkFUVCIpLA0KICAgICAgICAgICAgICAgIGNpbCA9IEVmZmVjdCAtIDEuOTYqc2UsDQogICAgICAgICAgICAgICAgY2l1ID0gRWZmZWN0ICsgMS45NipzZSkgICU+JSANCiAgZ2dwbG90KGFlcyh4PVRhcmdldCx5PUVmZmVjdCx5bWluPWNpbCx5bWF4PWNpdSkpICsgZ2VvbV9wb2ludChzaXplPTIuNSkgKyBnZW9tX2Vycm9yYmFyKHdpZHRoPTAuMTUpICArDQogIGdlb21faGxpbmUoeWludGVyY2VwdD0wKSArIHhsYWIoIlRhcmdldCBwYXJhbWV0ZXIiKQ0KYGBgDQoNCklmIHlvdSB3YW50IHRvIHVuZGVyc3RhbmQgd2hldGhlciBBVEUgYW5kIEFUVCBhcmUgc3RhdGlzdGljYWxseSBzaWduaWZpY2FudCwgY2hlY2sgb3V0IGFwcGxpY2F0aW9uIG5vdGVib29rICpBTkJfR2VuZXJpY19ETUwqLg0KDQo8YnI+DQo8YnI+