Goals:

  • Handcode offline policy learning with binary treatment

  • Use the policytree package


401(k) data set again

We again use the data of 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 data set 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 few controls ensure that the programs run not as long as with data sets that you hope to have for your applications.

if (!require("rpart")) install.packages("rpart", dependencies = TRUE); library(rpart)
if (!require("rpart.plot")) install.packages("rpart.plot", dependencies = TRUE); library(rpart.plot)
if (!require("glmnet")) install.packages("glmnet", dependencies = TRUE); library(glmnet)
if (!require("hdm")) install.packages("hdm", dependencies = TRUE); library(hdm)
if (!require("tidyverse")) install.packages("tidyverse", dependencies = TRUE); library(tidyverse)
if (!require("policytree")) install.packages("policytree", dependencies = TRUE); library(policytree)
if (!require("DiagrammeR")) install.packages("DiagrammeR", dependencies = TRUE); library(DiagrammeR)
if (!require("causalDML")) {
  if (!require("devtools")) install.packages("devtools", dependencies = TRUE); library(devtools)
  install_github(repo="MCKnaus/causalDML") 
}; library(causalDML)

set.seed(1234) # for replicability

# Get data
data(pension)
# Treatment
W = pension$p401
# Outcome
Y = pension$net_tfa
# Y[W==1] = Y[W==1] - 5000 # optional to see more action
# Create main effects matrix
X = model.matrix(~ 0 + age + db + educ + fsize + hown + inc + male + marr + pira + twoearn, data = pension)
X2 = model.matrix(~ 0 + (age + db + educ + fsize + hown + inc + male + marr + pira + twoearn)^2, data = pension)
# Define labels to be used in plot later
w_label = c("No 401(k)","401(k)")



Double ML for AIPW with causalDML package

We create the pseudo outcome \[\tilde{Y}_{ATE} = \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}}\]

by running the DML_aipw function.

# 5-fold cross-fitting with causalDML package
aipw = DML_aipw(Y,W,X)

# If you have more time, tune the forest
# forest = create_method("forest_grf",args=list(tune.parameters = "all"))
# aipw = DML_aipw(Y,W,X,ml_w=list(forest),ml_y=list(forest),cf=5)
summary(aipw$ATE)
          ATE      SE      t         p    
1 - 0 11288.4  1166.9 9.6736 < 2.2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1



Policy learning as classification problem

Lasso

In the lecture slides we derived that policy learning with a binary treatment can be operationalized as weighted classification problem: \[\hat{\pi} = argmax_{\pi \in \Pi} \left\{ \frac{1}{N} \sum_{i=1}^N \underbrace{|\tilde{Y}_{i,ATE}|}_{\text{weight}}~ \underbrace{sign(\tilde{Y}_{i,ATE})}_{\text{to be classified}} ~ \overbrace{(2 \pi(X_i) - 1)}^{\text{function to be learned}}] \right\}\]

where the pseudo-outcome \(\tilde{Y}_{ATE}\) is required to define the sign and the weight. It can be retrieved from aipw$ATE$delta.

One possibility to implement policy learning is to use Lasso for Logistic regression. We apply a design matrix with first order interactions to account for potential non-linearities of the effects:

pseudo_outcome = aipw$ATE$delta
sign = sign(pseudo_outcome)
cvfit = cv.glmnet(X2, sign, family = "binomial", type.measure = "class", weights = abs(pseudo_outcome))
plot(cvfit)

Now use the predict function to get the estimated optimal assignment:

pi_lasso = as.numeric(predict(cvfit,newx=X2, type = "class", s = "lambda.min"))
table(pi_lasso)
pi_lasso
  -1    1 
  89 9826 

Only very few observations are assigned to the control condition. Let’s see how we can describe them in the spirit of a CLAN analysis:

CLAN_lasso = cbind(colMeans(X[pi_lasso == -1,]),colMeans(X[pi_lasso == 1,]))
colnames(CLAN_lasso) = c("No 401(k)","401(k)")
round(CLAN_lasso,2)
        No 401(k)   401(k)
age         44.39    41.03
db           0.00     0.27
educ        15.52    13.19
fsize        3.04     2.86
hown         0.76     0.63
inc     121736.06 36434.93
male         0.20     0.21
marr         0.97     0.60
pira         1.00     0.24
twoearn      0.57     0.38

It seems that mostly very high income earners are not selected.


Classification tree

An alternative is to use classification trees to solve the weighted classification problem:

df = data.frame(sign = sign,pseudo_outcome = pseudo_outcome,X)
tree = rpart(sign ~ X, weights = abs(pseudo_outcome), method = "class")
# print(tree)
rpart.plot(tree)

Also only very few assigned to “No 401(k)”.

# Output takes values 1 and 2, therefore recode to -1/1
pi_tree = 2 * (as.numeric(predict(tree,type = "class")) - 1.5)
table(pi_tree)
pi_tree
  -1    1 
  65 9850 

Run a CLAN analysis as above:

CLAN_tree = cbind(colMeans(X[pi_tree == -1,]),colMeans(X[pi_tree == 1,]))
colnames(CLAN_tree) = c("No 401(k)","401(k)")
round(CLAN_tree,2)
        No 401(k)   401(k)
age         45.38    41.03
db           0.00     0.27
educ        16.02    13.19
fsize        2.95     2.87
hown         0.97     0.63
inc     138411.00 36532.74
male         0.12     0.21
marr         0.97     0.60
pira         0.72     0.24
twoearn      0.68     0.38

Now let’s check to what extend Lasso and Tree classifications agree.

table(pi_lasso,pi_tree)
        pi_tree
pi_lasso   -1    1
      -1   42   47
      1    23 9803



Policy learning with policytree package

The policytree package does not explicitly solve the weighted classification problem, but searches the optimal tree over all possible splits for a given depth (not greedy). It requires the \(\hat{\Gamma}\) matrix \[ \hat{\Gamma} = \begin{bmatrix} \hat{\Gamma}_{1,0} & \hat{\Gamma}_{1,1} \\ \vdots &\vdots \\ \hat{\Gamma}_{N,0} & \hat{\Gamma}_{N,1} \end{bmatrix} \]

that is stored in aipw$APO$gamma.

Depth 1 tree

First we specify a depth 1 tree:

depth1 = policy_tree(X,aipw$APO$gamma,1)
plot(depth1,w_label)

The tree says that only very high earners should not be part of the 401(k) plan.

If we check the GATEs like in the ANB_401k_GATE notebook, we see where this decision comes from:

inc = X[,6]
sr_inc = spline_cate(aipw$ATE$delta,inc)
plot(sr_inc,z_label = "Income")

The effect is estimated to become negative for high-earners. However, I would not take this too serious as there are basically no observations in the high earnings regions:

hist(inc)

However, for the sake of illustration we can see where the decision of the policy tree comes from.



Depth 2 tree

This is how the depth 2 tree looks like:

depth2 = policy_tree(X,aipw$APO$gamma,2)
plot(depth2,w_label)



Depth 3 tree

For the depth 3 tree, we tell the function policy_tree to not check every splitting point (split.step = 1000), but to only evaluate every 1000th value of a variable. This speeds up the calculation, otherwise it takes much longer to calculate the tree:

depth3 = policy_tree(X,aipw$APO$gamma,3,split.step = 1000)
Warnung: A depth 3 or deeper policy_tree is only feasible for 'small' n and p. To fit deeper trees, consider using the hybrid greedy approach available in the function `hybrid_policy_tree`. Note that this still requires an (n, p) configuration which is feasible for a depth k=2 policy_tree, see the documentation for details.
plot(depth3,w_label)

I would not take these results too serious as already the depth 1 tree could be overfitting. Instead, see this as illustration of the implementation.

Potential extension

For the sake of the arguments one could subtract hypothetical costs of, e.g. $5000 from the treated and rerun the analysis. This would lead to more people being assigned to “No 401(k)” because the costs are larger than the benefits. To this end uncomment line 71 and rerun the analysis.


LS0tDQp0aXRsZTogIkNhdXNhbCBNTDogT2ZmbGluZSBwb2xpY3kgbGVhcm5pbmciDQpzdWJ0aXRsZTogIkFwcGxpY2F0aW9uIG5vdGVib29rIg0KYXV0aG9yOiAiTWljaGFlbCBLbmF1cyINCmRhdGU6ICJgciBmb3JtYXQoU3lzLnRpbWUoKSwgJyVtLyV5JylgIg0Kb3V0cHV0OiANCiAgaHRtbF9ub3RlYm9vazoNCiAgICB0b2M6IHRydWUNCiAgICB0b2NfZmxvYXQ6IHRydWUNCiAgICBjb2RlX2ZvbGRpbmc6IHNob3cNCi0tLQ0KDQoNCjxicj4NCg0KR29hbHM6DQoNCi0gSGFuZGNvZGUgb2ZmbGluZSBwb2xpY3kgbGVhcm5pbmcgd2l0aCBiaW5hcnkgdHJlYXRtZW50DQoNCi0gVXNlIHRoZSBgcG9saWN5dHJlZWAgcGFja2FnZQ0KDQo8YnI+DQoNCiMgNDAxKGspIGRhdGEgc2V0IGFnYWluDQoNCldlIGFnYWluIHVzZSB0aGUgZGF0YSBvZiB0aGUgYGhkbWAgcGFja2FnZS4gVGhlIGRhdGEgd2FzIHVzZWQgaW4gW0NoZXJub3podWtvdiBhbmQgSGFuc2VuICgyMDA0KV0oaHR0cHM6Ly9kaXJlY3QubWl0LmVkdS9yZXN0L2FydGljbGUvODYvMy83MzUvNTc1ODYvVGhlLUVmZmVjdHMtb2YtNDAxLUstUGFydGljaXBhdGlvbi1vbi10aGUtV2VhbHRoKS4gVGhlaXIgcGFwZXIgaW52ZXN0aWdhdGVzIHRoZSBlZmZlY3Qgb2YgcGFydGljaXBhdGlvbiBpbiB0aGUgZW1wbG95ZXItc3BvbnNvcmVkIDQwMShrKSByZXRpcmVtZW50IHNhdmluZ3MgcGxhbiAoKnA0MDEqKSBvbiBuZXQgYXNzZXRzICgqbmV0X3RmYSopLiBTaW5jZSB0aGVuLCB0aGUgZGF0YSB3YXMgdXNlZCB0byBzaG93Y2FzZSBtYW55IG5ldyBtZXRob2RzLiBJdCBpcyBub3QgdGhlIG1vc3QgY29tcHJlaGVuc2l2ZSBkYXRhIHNldCB3aXRoIGJhc2ljYWxseSB0ZW4gY292YXJpYXRlcy9yZWdyZXNzb3JzL3ByZWRpY3RvcnM6DQoNCi0gKmFnZSo6IGFnZQ0KDQotICpkYio6IGRlZmluZWQgYmVuZWZpdCBwZW5zaW9uDQoNCi0gKmVkdWMqOiBlZHVjYXRpb24gKGluIHllYXJzKQ0KDQotICpmc2l6ZSo6IGZhbWlseSBzaXplDQoNCi0gKmhvd24qOiBob21lIG93bmVyDQoNCi0gKmluYyo6IGluY29tZSAoaW4gVVMgJCkNCg0KLSAqbWFsZSo6IG1hbGUNCg0KLSAqbWFycio6IG1hcnJpZWQNCg0KLSAqcGlyYSo6IHBhcnRpY2lwYXRpb24gaW4gaW5kaXZpZHVhbCByZXRpcmVtZW50IGFjY291bnQgKElSQSkNCg0KLSAqdHdvZWFybio6IHR3byBlYXJuZXJzDQoNCkhvd2V2ZXIsIGl0IGlzIHB1YmxpY2x5IGF2YWlsYWJsZSBhbmQgdGhlIGZldyBjb250cm9scyBlbnN1cmUgdGhhdCB0aGUgcHJvZ3JhbXMgcnVuIG5vdCBhcyBsb25nIGFzIHdpdGggZGF0YSBzZXRzIHRoYXQgeW91IGhvcGUgdG8gaGF2ZSBmb3IgeW91ciBhcHBsaWNhdGlvbnMuDQoNCmBgYHtyLCB3YXJuaW5nPUYsbWVzc2FnZT1GfQ0KaWYgKCFyZXF1aXJlKCJycGFydCIpKSBpbnN0YWxsLnBhY2thZ2VzKCJycGFydCIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KHJwYXJ0KQ0KaWYgKCFyZXF1aXJlKCJycGFydC5wbG90IikpIGluc3RhbGwucGFja2FnZXMoInJwYXJ0LnBsb3QiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeShycGFydC5wbG90KQ0KaWYgKCFyZXF1aXJlKCJnbG1uZXQiKSkgaW5zdGFsbC5wYWNrYWdlcygiZ2xtbmV0IiwgZGVwZW5kZW5jaWVzID0gVFJVRSk7IGxpYnJhcnkoZ2xtbmV0KQ0KaWYgKCFyZXF1aXJlKCJoZG0iKSkgaW5zdGFsbC5wYWNrYWdlcygiaGRtIiwgZGVwZW5kZW5jaWVzID0gVFJVRSk7IGxpYnJhcnkoaGRtKQ0KaWYgKCFyZXF1aXJlKCJ0aWR5dmVyc2UiKSkgaW5zdGFsbC5wYWNrYWdlcygidGlkeXZlcnNlIiwgZGVwZW5kZW5jaWVzID0gVFJVRSk7IGxpYnJhcnkodGlkeXZlcnNlKQ0KaWYgKCFyZXF1aXJlKCJwb2xpY3l0cmVlIikpIGluc3RhbGwucGFja2FnZXMoInBvbGljeXRyZWUiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeShwb2xpY3l0cmVlKQ0KaWYgKCFyZXF1aXJlKCJEaWFncmFtbWVSIikpIGluc3RhbGwucGFja2FnZXMoIkRpYWdyYW1tZVIiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeShEaWFncmFtbWVSKQ0KaWYgKCFyZXF1aXJlKCJjYXVzYWxETUwiKSkgew0KICBpZiAoIXJlcXVpcmUoImRldnRvb2xzIikpIGluc3RhbGwucGFja2FnZXMoImRldnRvb2xzIiwgZGVwZW5kZW5jaWVzID0gVFJVRSk7IGxpYnJhcnkoZGV2dG9vbHMpDQogIGluc3RhbGxfZ2l0aHViKHJlcG89Ik1DS25hdXMvY2F1c2FsRE1MIikgDQp9OyBsaWJyYXJ5KGNhdXNhbERNTCkNCg0Kc2V0LnNlZWQoMTIzNCkgIyBmb3IgcmVwbGljYWJpbGl0eQ0KDQojIEdldCBkYXRhDQpkYXRhKHBlbnNpb24pDQojIFRyZWF0bWVudA0KVyA9IHBlbnNpb24kcDQwMQ0KIyBPdXRjb21lDQpZID0gcGVuc2lvbiRuZXRfdGZhDQojIFlbVz09MV0gPSBZW1c9PTFdIC0gNTAwMCAjIG9wdGlvbmFsIHRvIHNlZSBtb3JlIGFjdGlvbg0KIyBDcmVhdGUgbWFpbiBlZmZlY3RzIG1hdHJpeA0KWCA9IG1vZGVsLm1hdHJpeCh+IDAgKyBhZ2UgKyBkYiArIGVkdWMgKyBmc2l6ZSArIGhvd24gKyBpbmMgKyBtYWxlICsgbWFyciArIHBpcmEgKyB0d29lYXJuLCBkYXRhID0gcGVuc2lvbikNClgyID0gbW9kZWwubWF0cml4KH4gMCArIChhZ2UgKyBkYiArIGVkdWMgKyBmc2l6ZSArIGhvd24gKyBpbmMgKyBtYWxlICsgbWFyciArIHBpcmEgKyB0d29lYXJuKV4yLCBkYXRhID0gcGVuc2lvbikNCiMgRGVmaW5lIGxhYmVscyB0byBiZSB1c2VkIGluIHBsb3QgbGF0ZXINCndfbGFiZWwgPSBjKCJObyA0MDEoaykiLCI0MDEoaykiKQ0KYGBgDQoNCjxicj4NCjxicj4NCg0KIyBEb3VibGUgTUwgZm9yIEFJUFcgd2l0aCBgY2F1c2FsRE1MYCBwYWNrYWdlDQoNCldlIGNyZWF0ZSB0aGUgcHNldWRvIG91dGNvbWUNCiQkXHRpbGRle1l9X3tBVEV9ID0gXHVuZGVyYnJhY2V7XGhhdHttfSgxLFgpIC0gXGhhdHttfSgwLFgpfV97XHRleHR7b3V0Y29tZSBwcmVkaWN0aW9uc319ICsgXHVuZGVyYnJhY2V7XGZyYWN7VyAoWSAtIFxoYXR7bX0oMSxYKSl9e1xoYXR7ZX0oWCl9IC0gXGZyYWN7KDEtVykgKFkgLSBcaGF0e219KDAsWCkpfXsxLVxoYXR7ZX0oWCl9fV97XHRleHR7d2VpZ2h0ZWQgcmVzaWR1YWxzfX0kJA0KDQpieSBydW5uaW5nIHRoZSBgRE1MX2FpcHdgIGZ1bmN0aW9uLg0KDQpgYGB7cn0NCiMgNS1mb2xkIGNyb3NzLWZpdHRpbmcgd2l0aCBjYXVzYWxETUwgcGFja2FnZQ0KYWlwdyA9IERNTF9haXB3KFksVyxYKQ0KDQojIElmIHlvdSBoYXZlIG1vcmUgdGltZSwgdHVuZSB0aGUgZm9yZXN0DQojIGZvcmVzdCA9IGNyZWF0ZV9tZXRob2QoImZvcmVzdF9ncmYiLGFyZ3M9bGlzdCh0dW5lLnBhcmFtZXRlcnMgPSAiYWxsIikpDQojIGFpcHcgPSBETUxfYWlwdyhZLFcsWCxtbF93PWxpc3QoZm9yZXN0KSxtbF95PWxpc3QoZm9yZXN0KSxjZj01KQ0Kc3VtbWFyeShhaXB3JEFURSkNCmBgYA0KDQo8YnI+DQo8YnI+DQoNCg0KIyBQb2xpY3kgbGVhcm5pbmcgYXMgY2xhc3NpZmljYXRpb24gcHJvYmxlbQ0KDQojIyBMYXNzbw0KDQpJbiB0aGUgbGVjdHVyZSBzbGlkZXMgd2UgZGVyaXZlZCB0aGF0IHBvbGljeSBsZWFybmluZyB3aXRoIGEgYmluYXJ5IHRyZWF0bWVudCBjYW4gYmUgb3BlcmF0aW9uYWxpemVkIGFzIHdlaWdodGVkIGNsYXNzaWZpY2F0aW9uIHByb2JsZW06DQokJFxoYXR7XHBpfSA9IGFyZ21heF97XHBpIFxpbiBcUGl9IFxsZWZ0XHsgXGZyYWN7MX17Tn0gXHN1bV97aT0xfV5OICBcdW5kZXJicmFjZXt8XHRpbGRle1l9X3tpLEFURX18fV97XHRleHR7d2VpZ2h0fX1+IA0KXHVuZGVyYnJhY2V7c2lnbihcdGlsZGV7WX1fe2ksQVRFfSl9X3tcdGV4dHt0byBiZSBjbGFzc2lmaWVkfX0gfiBcb3ZlcmJyYWNleygyIFxwaShYX2kpIC0gMSl9XntcdGV4dHtmdW5jdGlvbiB0byBiZSBsZWFybmVkfX1dIFxyaWdodFx9JCQNCg0Kd2hlcmUgdGhlIHBzZXVkby1vdXRjb21lICRcdGlsZGV7WX1fe0FURX0kIGlzIHJlcXVpcmVkIHRvIGRlZmluZSB0aGUgc2lnbiBhbmQgdGhlIHdlaWdodC4gSXQgY2FuIGJlIHJldHJpZXZlZCBmcm9tIGBhaXB3JEFURSRkZWx0YWAuDQoNCk9uZSBwb3NzaWJpbGl0eSB0byBpbXBsZW1lbnQgcG9saWN5IGxlYXJuaW5nIGlzIHRvIHVzZSBMYXNzbyBmb3IgTG9naXN0aWMgcmVncmVzc2lvbi4gV2UgYXBwbHkgYSBkZXNpZ24gbWF0cml4IHdpdGggZmlyc3Qgb3JkZXIgaW50ZXJhY3Rpb25zIHRvIGFjY291bnQgZm9yIHBvdGVudGlhbCBub24tbGluZWFyaXRpZXMgb2YgdGhlIGVmZmVjdHM6DQoNCmBgYHtyfQ0KcHNldWRvX291dGNvbWUgPSBhaXB3JEFURSRkZWx0YQ0Kc2lnbiA9IHNpZ24ocHNldWRvX291dGNvbWUpDQpjdmZpdCA9IGN2LmdsbW5ldChYMiwgc2lnbiwgZmFtaWx5ID0gImJpbm9taWFsIiwgdHlwZS5tZWFzdXJlID0gImNsYXNzIiwgd2VpZ2h0cyA9IGFicyhwc2V1ZG9fb3V0Y29tZSkpDQpwbG90KGN2Zml0KQ0KYGBgDQoNCk5vdyB1c2UgdGhlIGBwcmVkaWN0YCBmdW5jdGlvbiB0byBnZXQgdGhlIGVzdGltYXRlZCBvcHRpbWFsIGFzc2lnbm1lbnQ6DQoNCmBgYHtyfQ0KcGlfbGFzc28gPSBhcy5udW1lcmljKHByZWRpY3QoY3ZmaXQsbmV3eD1YMiwgdHlwZSA9ICJjbGFzcyIsIHMgPSAibGFtYmRhLm1pbiIpKQ0KdGFibGUocGlfbGFzc28pDQpgYGANCg0KT25seSB2ZXJ5IGZldyBvYnNlcnZhdGlvbnMgYXJlIGFzc2lnbmVkIHRvIHRoZSBjb250cm9sIGNvbmRpdGlvbi4gTGV0J3Mgc2VlIGhvdyB3ZSBjYW4gZGVzY3JpYmUgdGhlbSBpbiB0aGUgc3Bpcml0IG9mIGEgQ0xBTiBhbmFseXNpczoNCg0KYGBge3J9DQpDTEFOX2xhc3NvID0gY2JpbmQoY29sTWVhbnMoWFtwaV9sYXNzbyA9PSAtMSxdKSxjb2xNZWFucyhYW3BpX2xhc3NvID09IDEsXSkpDQpjb2xuYW1lcyhDTEFOX2xhc3NvKSA9IGMoIk5vIDQwMShrKSIsIjQwMShrKSIpDQpyb3VuZChDTEFOX2xhc3NvLDIpDQpgYGANCg0KSXQgc2VlbXMgdGhhdCBtb3N0bHkgdmVyeSBoaWdoIGluY29tZSBlYXJuZXJzIGFyZSBub3Qgc2VsZWN0ZWQuDQoNCjxicj4NCg0KIyMgQ2xhc3NpZmljYXRpb24gdHJlZQ0KDQpBbiBhbHRlcm5hdGl2ZSBpcyB0byB1c2UgY2xhc3NpZmljYXRpb24gdHJlZXMgdG8gc29sdmUgdGhlIHdlaWdodGVkIGNsYXNzaWZpY2F0aW9uIHByb2JsZW06DQoNCmBgYHtyfQ0KZGYgPSBkYXRhLmZyYW1lKHNpZ24gPSBzaWduLHBzZXVkb19vdXRjb21lID0gcHNldWRvX291dGNvbWUsWCkNCnRyZWUgPSBycGFydChzaWduIH4gWCwgd2VpZ2h0cyA9IGFicyhwc2V1ZG9fb3V0Y29tZSksIG1ldGhvZCA9ICJjbGFzcyIpDQojIHByaW50KHRyZWUpDQpycGFydC5wbG90KHRyZWUpDQpgYGANCg0KQWxzbyBvbmx5IHZlcnkgZmV3IGFzc2lnbmVkIHRvICJObyA0MDEoaykiLg0KDQpgYGB7cn0NCiMgT3V0cHV0IHRha2VzIHZhbHVlcyAxIGFuZCAyLCB0aGVyZWZvcmUgcmVjb2RlIHRvIC0xLzENCnBpX3RyZWUgPSAyICogKGFzLm51bWVyaWMocHJlZGljdCh0cmVlLHR5cGUgPSAiY2xhc3MiKSkgLSAxLjUpDQp0YWJsZShwaV90cmVlKQ0KYGBgDQoNClJ1biBhIENMQU4gYW5hbHlzaXMgYXMgYWJvdmU6DQoNCmBgYHtyfQ0KQ0xBTl90cmVlID0gY2JpbmQoY29sTWVhbnMoWFtwaV90cmVlID09IC0xLF0pLGNvbE1lYW5zKFhbcGlfdHJlZSA9PSAxLF0pKQ0KY29sbmFtZXMoQ0xBTl90cmVlKSA9IGMoIk5vIDQwMShrKSIsIjQwMShrKSIpDQpyb3VuZChDTEFOX3RyZWUsMikNCmBgYA0KDQpOb3cgbGV0J3MgY2hlY2sgdG8gd2hhdCBleHRlbmQgTGFzc28gYW5kIFRyZWUgY2xhc3NpZmljYXRpb25zIGFncmVlLg0KDQpgYGB7cn0NCnRhYmxlKHBpX2xhc3NvLHBpX3RyZWUpDQpgYGANCjxicj4NCjxicj4NCg0KDQojIFBvbGljeSBsZWFybmluZyB3aXRoIGBwb2xpY3l0cmVlYCBwYWNrYWdlDQoNClRoZSBgcG9saWN5dHJlZWAgcGFja2FnZSBkb2VzIG5vdCBleHBsaWNpdGx5IHNvbHZlIHRoZSB3ZWlnaHRlZCBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtLCBidXQgc2VhcmNoZXMgdGhlIG9wdGltYWwgdHJlZSBvdmVyIGFsbCBwb3NzaWJsZSBzcGxpdHMgZm9yIGEgZ2l2ZW4gZGVwdGggKG5vdCBncmVlZHkpLiBJdCByZXF1aXJlcyB0aGUgJFxoYXR7XEdhbW1hfSQgbWF0cml4DQokJA0KXGhhdHtcR2FtbWF9ID0gDQpcYmVnaW57Ym1hdHJpeH0NClxoYXR7XEdhbW1hfV97MSwwfSAmIFxoYXR7XEdhbW1hfV97MSwxfSBcXA0KXHZkb3RzICZcdmRvdHMgXFwNClxoYXR7XEdhbW1hfV97TiwwfSAmIFxoYXR7XEdhbW1hfV97TiwxfQ0KXGVuZHtibWF0cml4fQ0KJCQNCg0KdGhhdCBpcyBzdG9yZWQgaW4gYGFpcHckQVBPJGdhbW1hYC4NCg0KIyMgRGVwdGggMSB0cmVlDQoNCkZpcnN0IHdlIHNwZWNpZnkgYSBkZXB0aCAxIHRyZWU6DQoNCg0KYGBge3IsIHdhcm5pbmcgPSBGLCBtZXNzYWdlID0gRn0NCmRlcHRoMSA9IHBvbGljeV90cmVlKFgsYWlwdyRBUE8kZ2FtbWEsMSkNCnBsb3QoZGVwdGgxLHdfbGFiZWwpDQpgYGANCg0KVGhlIHRyZWUgc2F5cyB0aGF0IG9ubHkgdmVyeSBoaWdoIGVhcm5lcnMgc2hvdWxkIG5vdCBiZSBwYXJ0IG9mIHRoZSA0MDEoaykgcGxhbi4NCg0KSWYgd2UgY2hlY2sgdGhlIEdBVEVzIGxpa2UgaW4gdGhlICpBTkJfNDAxa19HQVRFKiBub3RlYm9vaywgd2Ugc2VlIHdoZXJlIHRoaXMgZGVjaXNpb24gY29tZXMgZnJvbToNCmBgYHtyLCByZXN1bHRzPSdoaWRlJ30NCmluYyA9IFhbLDZdDQpzcl9pbmMgPSBzcGxpbmVfY2F0ZShhaXB3JEFURSRkZWx0YSxpbmMpDQpgYGANCg0KYGBge3J9DQpwbG90KHNyX2luYyx6X2xhYmVsID0gIkluY29tZSIpDQpgYGANCg0KVGhlIGVmZmVjdCBpcyBlc3RpbWF0ZWQgdG8gYmVjb21lIG5lZ2F0aXZlIGZvciBoaWdoLWVhcm5lcnMuIEhvd2V2ZXIsIEkgd291bGQgbm90IHRha2UgdGhpcyB0b28gc2VyaW91cyBhcyB0aGVyZSBhcmUgYmFzaWNhbGx5IG5vIG9ic2VydmF0aW9ucyBpbiB0aGUgaGlnaCBlYXJuaW5ncyByZWdpb25zOg0KDQpgYGB7cn0NCmhpc3QoaW5jKQ0KYGBgDQoNCkhvd2V2ZXIsIGZvciB0aGUgc2FrZSBvZiBpbGx1c3RyYXRpb24gd2UgY2FuIHNlZSB3aGVyZSB0aGUgZGVjaXNpb24gb2YgdGhlIHBvbGljeSB0cmVlIGNvbWVzIGZyb20uDQoNCjxicj4NCjxicj4NCg0KIyMjIERlcHRoIDIgdHJlZQ0KDQpUaGlzIGlzIGhvdyB0aGUgZGVwdGggMiB0cmVlIGxvb2tzIGxpa2U6DQoNCmBgYHtyfQ0KZGVwdGgyID0gcG9saWN5X3RyZWUoWCxhaXB3JEFQTyRnYW1tYSwyKQ0KcGxvdChkZXB0aDIsd19sYWJlbCkNCmBgYA0KDQo8YnI+DQo8YnI+DQoNCiMjIyBEZXB0aCAzIHRyZWUNCg0KRm9yIHRoZSBkZXB0aCAzIHRyZWUsIHdlIHRlbGwgdGhlIGZ1bmN0aW9uIGBwb2xpY3lfdHJlZWAgdG8gbm90IGNoZWNrIGV2ZXJ5IHNwbGl0dGluZyBwb2ludCAoYHNwbGl0LnN0ZXAgPSAxMDAwYCksIGJ1dCB0byBvbmx5IGV2YWx1YXRlIGV2ZXJ5IDEwMDB0aCB2YWx1ZSBvZiBhIHZhcmlhYmxlLiBUaGlzIHNwZWVkcyB1cCB0aGUgY2FsY3VsYXRpb24sIG90aGVyd2lzZSBpdCB0YWtlcyBtdWNoIGxvbmdlciB0byBjYWxjdWxhdGUgdGhlIHRyZWU6DQoNCmBgYHtyLCB3YXJuaW5ncz1GfQ0KZGVwdGgzID0gcG9saWN5X3RyZWUoWCxhaXB3JEFQTyRnYW1tYSwzLHNwbGl0LnN0ZXAgPSAxMDAwKQ0KcGxvdChkZXB0aDMsd19sYWJlbCkNCmBgYA0KDQpJIHdvdWxkIG5vdCB0YWtlIHRoZXNlIHJlc3VsdHMgdG9vIHNlcmlvdXMgYXMgYWxyZWFkeSB0aGUgZGVwdGggMSB0cmVlIGNvdWxkIGJlIG92ZXJmaXR0aW5nLiBJbnN0ZWFkLCBzZWUgdGhpcyBhcyBpbGx1c3RyYXRpb24gb2YgdGhlIGltcGxlbWVudGF0aW9uLg0KDQojIyMgUG90ZW50aWFsIGV4dGVuc2lvbg0KDQpGb3IgdGhlIHNha2Ugb2YgdGhlIGFyZ3VtZW50cyBvbmUgY291bGQgc3VidHJhY3QgaHlwb3RoZXRpY2FsIGNvc3RzIG9mLCBlLmcuICQ1MDAwIGZyb20gdGhlIHRyZWF0ZWQgYW5kIHJlcnVuIHRoZSBhbmFseXNpcy4gVGhpcyB3b3VsZCBsZWFkIHRvIG1vcmUgcGVvcGxlIGJlaW5nIGFzc2lnbmVkIHRvICJObyA0MDEoaykiIGJlY2F1c2UgdGhlIGNvc3RzIGFyZSBsYXJnZXIgdGhhbiB0aGUgYmVuZWZpdHMuIFRvIHRoaXMgZW5kIHVuY29tbWVudCBsaW5lIDcxIGFuZCByZXJ1biB0aGUgYW5hbHlzaXMuDQoNCjxicj4NCg0KDQo=