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