Setting the stage

Managing expectations

This notebook illustrates the theoretical derivations of the paper “Treatment Effect Estimators as Weighted Outcomes”. We keep everything as simple as possible meaning that

  • we use the cleaned and readily available 401(k) data of the hdm package, which includes a treatment and an instrument

  • we use the regression_forest() of the grf to estimate nuisance parameters because this is the only ML method with a build-in function to extract smoother weights

  • we hand-code two-fold cross-validation with regression_forest() and reuse the same nuisance parameters for different estimators

  • we do no tune the hyperparamters and stick to the default setting

  • we only consider causal/instrumental forest effect estimates for one unit and not for all 9915

  • we stick as close as possible to the paper notation

However, the code provides the basis to extend the analysis in different directions. To this end, click on the “Code” button at the top right and “Download Rmd”.

This notebooks is only for illustration. The https://github.com/MCKnaus/OutcomeWeights R package implements everything in a more user friendly way.

Load packages and data

First, load the relevant packages

if (!require("cobalt")) install.packages("cobalt", dependencies = TRUE); library(cobalt)
if (!require("grf")) install.packages("grf", dependencies = TRUE); library(grf)
if (!require("hdm")) install.packages("hdm", dependencies = TRUE); library(hdm)
if (!require("gridExtra")) install.packages("gridExtra", dependencies = TRUE); library(gridExtra)
if (!require("tidyverse")) install.packages("tidyverse", dependencies = TRUE); library(tidyverse)
if (!require("AER")) install.packages("AER", dependencies = TRUE); library(AER)

and the data

data(pension) # Find variable description if you type ?pension in console
# Treatment
D = pension$p401
# Instrument
Z = pension$e401
# Outcome
Y = pension$net_tfa
# Controls
X = model.matrix(~ 0 + age + db + educ + fsize + hown + inc + male + marr + pira + twoearn, data = pension)
colnames(X) = c("Age","Benefit pension","Education","Family size","Home owner","Income","Male","Married","IRA","Two earners")

Define useful quantities and set the seed:

# Helpful variables
N = length(Y)
ones = matrix(1,N,1)

# Choose unit for which causal/instrumental forest weights should be calculated
unit = 1

# Define number of folds for cross-fitting
nfolds = 2

set.seed(1234)

One function to calculate them all

Proposition 1 in the paper shows that the outcome weights vector can be obtained in the general form \[\boldsymbol{\omega'} = (\boldsymbol{\tilde{Z}'\tilde{D}})^{-1} \boldsymbol{\tilde{Z}'T}\]

where \(\boldsymbol{\tilde{Z}}\), \(\boldsymbol{\tilde{D}}\) and \(\boldsymbol{T}\) are pseudo-instrument, pseudo-treatment and the transformation matrix, respectively.

This motivates the definition of the weight_maker(Dtilde,Ztilde,T_mat) function taking the three generic inputs and producing the outcome weights vector:

weight_maker = function(Dtilde,Ztilde,T_mat) {
  omega = (t(Ztilde) %*% Dtilde)^(-1) %*% t(Ztilde) %*% T_mat
  return(omega)
}

In the following, we just need to define the three components for the respective estimators and plug them into this generic function to obtain the outcome weights.

Estimate all nuisance parameters and get outcome smoother matrices

Equation (8) in the paper shows which nuisance parameters are required for the estimators under consideration. Here, we estimate them all using honest random forest and 2-fold cross-fitting. Additionally, we extract the relevant smoother matrices \(\boldsymbol{S}\), \(\boldsymbol{S^d_0}\), \(\boldsymbol{S^d_1}\), \(\boldsymbol{S^z_0}\), and \(\boldsymbol{S^z_1}\).

# Get fold number
fold = sample(1:nfolds,N,replace=T)

# Initialize nuisance parameters
Yhat = Yhatd0 = Yhatd1 = Yhatz0 = Yhatz1 = 
  Dhat = Dhatz0 = Dhatz1 = Zhat = rep(NA,N)

# Initialize smoother matrices
S = Sd0 = Sd1 = Sz0 = Sz1 = matrix(0,N,N)

for (i in 1:nfolds){
  # Calculate nuisance parameters and relevant smoother matrices
  rf_Yhat = regression_forest(X[fold != i,],Y[fold != i])
  Yhat[fold == i] = predict(rf_Yhat, X[fold == i,])$predictions
  S[fold == i, fold != i] = as.matrix(get_forest_weights(rf_Yhat, X[fold == i,]))

  rf_Yhatd0 = regression_forest(X[fold != i & D==0,],Y[fold != i & D==0])
  Yhatd0[fold == i] = predict(rf_Yhatd0, X[fold == i,])$predictions
  Sd0[fold == i, fold != i  & D==0] = as.matrix(get_forest_weights(rf_Yhatd0, X[fold == i,]))

  rf_Yhatd1 = regression_forest(X[fold != i & D==1,],Y[fold != i & D==1])
  Yhatd1[fold == i] = predict(rf_Yhatd1, X[fold == i,])$predictions
  Sd1[fold == i, fold != i  & D==1] = as.matrix(get_forest_weights(rf_Yhatd1, X[fold == i,]))

  rf_Yhatz0 = regression_forest(X[fold != i & Z==0,],Y[fold != i & Z==0])
  Yhatz0[fold == i] = predict(rf_Yhatz0, X[fold == i,])$predictions
  Sz0[fold == i, fold != i  & Z==0] = as.matrix(get_forest_weights(rf_Yhatz0, X[fold == i,]))
  
  rf_Yhatz1 = regression_forest(X[fold != i & Z==1,],Y[fold != i & Z==1])
  Yhatz1[fold == i] = predict(rf_Yhatz1, X[fold == i,])$predictions
  Sz1[fold == i, fold != i  & Z==1] = as.matrix(get_forest_weights(rf_Yhatz1, X[fold == i,]))
  
  rf_Dhat = regression_forest(X[fold != i,],D[fold != i])
  Dhat[fold == i] = predict(rf_Dhat, X[fold == i,])$predictions
  
  rf_Dhatz0 = regression_forest(X[fold != i & Z==0,],D[fold != i & Z==0])
  Dhatz0[fold == i] = predict(rf_Dhatz0, X[fold == i,])$predictions
  
  rf_Dhatz1 = regression_forest(X[fold != i & Z==1,],D[fold != i & Z==1])
  Dhatz1[fold == i] = predict(rf_Dhatz1, X[fold == i,])$predictions
  
  rf_Zhat = regression_forest(X[fold != i,],Z[fold != i])
  Zhat[fold == i] = predict(rf_Zhat, X[fold == i,])$predictions
}

For those not familiar with smoothers, lets observe that they produce exactly the same predictions as the original predict() functions:

cat("Smoother matrices replicate predicted nuisance parameter?",
 all(
  all.equal(as.numeric(S %*% Y), Yhat) == TRUE,
  all.equal(as.numeric(Sd0 %*% Y), Yhatd0) == TRUE,
  all.equal(as.numeric(Sd1 %*% Y), Yhatd1) == TRUE,
  all.equal(as.numeric(Sz0 %*% Y), Yhatz0) == TRUE,
  all.equal(as.numeric(Sz1 %*% Y), Yhatz1) == TRUE)
)
Smoother matrices replicate predicted nuisance parameter? TRUE

Also observe that random forest is an affine smoother because all rows add up exactly to one:

cat("Affine smoother matrices?",
all(
  all.equal(as.numeric(ones),as.numeric(rowSums(S))) == TRUE,
  all.equal(as.numeric(ones),as.numeric(rowSums(Sd0))) == TRUE,
  all.equal(as.numeric(ones),as.numeric(rowSums(Sd1))) == TRUE,
  all.equal(as.numeric(ones),as.numeric(rowSums(Sz0))) == TRUE,
  all.equal(as.numeric(ones),as.numeric(rowSums(Sz1))) == TRUE)
)
Affine smoother matrices? TRUE

Finally, define the different IPW weights for later use:

lambda1 = D / Dhat
lambda0 = (1-D) / (1-Dhat)
lambdaz1 = Z / Zhat
lambdaz0 = (1-Z) / (1-Zhat)

Outcome weights of DML and GRF

Instrumental forest

To be replicated

Here, we want to replicate the CLATE estimate for unit 1. To this end, we first run instrumental_forest() with the pre-defined nuisance parameters:

# Run IF with the pre-specified nuisance parameters
ivf = instrumental_forest(X,Y,D,Z,Y.hat=Yhat,W.hat=Dhat,Z.hat=Zhat)
# Get CLATEs 
clates_if = predict(ivf)$predictions

The estimated CLATE for unit 1 is then 5858.0128285, which becomes the number to be replicated:

to_be_rep_if = clates_if[unit]
to_be_rep_if
[1] 5858.013

Nearly replication using weights

According to the main text of the paper, we need the following components \[\boldsymbol{\hat{R}} = \boldsymbol{Z} - \boldsymbol{\hat{Z}}, \quad \boldsymbol{\hat{V}} = \boldsymbol{D} - \boldsymbol{\hat{D}}, \quad \boldsymbol{\hat{U}} = \boldsymbol{Y} - \boldsymbol{\hat{Y}}, \quad \alpha^{if}(\boldsymbol{x})\] that are defined in the following

Uhat = Y - Yhat
Vhat = D - Dhat
Rhat = Z - Zhat
alpha_if = get_forest_weights(ivf)[unit,]

Now define the pseudo-variables and the transformation matrix:

Ztilde_if = Rhat * alpha_if
Dtilde_if = Vhat
Ytilde_if = Uhat
T_if = diag(N) - S

As a sanity check observe how the transformation matrix replicates the pseudo-outcome:

cat("TY replicates pseudo-outcome?",
  all.equal(as.numeric( T_if %*% Y ), Uhat))
TY replicates pseudo-outcome? TRUE

Now we pass the required components to the weight_maker() function

omega_if = weight_maker(Dtilde_if, Ztilde_if, T_if)

This estimates an effect of 5858.0128285, which is very close but not identical to the number to be replicated:

all.equal(as.numeric( omega_if %*% Y ), to_be_rep_if)
[1] "Mean relative difference: 0.01158283"

Exact replication

As noted in Appendix A.3.1, the grf package applies an additional constant which requires to adjust the pseudo-instrument:

# Create weighted residual maker matrix
M1_inv = solve(t(ones) %*% diag(alpha_if) %*% ones)
P1 = (ones %*% M1_inv) %*% (t(ones) %*% diag(alpha_if))
M1 = diag(N) - P1
# Get modified pseudo-instrument
Ztilde_if = (M1 %*% Rhat) * alpha_if

Plugging this new pseudo-instrument into the weight_maker() function creates outcome weights that now perfectly replicate the package output:

# Get if outcome weights
omega_if = weight_maker(Dtilde_if, Ztilde_if, T_if) 
cat("ω'Y replicates package output?",all.equal(as.numeric( omega_if %*% Y ), to_be_rep_if))
ω'Y replicates package output? TRUE

Partially linear IV regression

To obtain the standard partially linear IV regression, we first solve the canonical moment condition to see which value should be replicated:

to_be_rep_plriv = mean(Rhat * Uhat) / mean(Rhat * Vhat)
to_be_rep_plriv
[1] 12559.55

Compared to IF, we only need to pass a different pseudo-instrument to the weight maker function to replicate this number:

# Modified pseudo-instrument
Ztilde_plriv = Rhat * ones
# Get outcome weights
omega_plriv = weight_maker(Dtilde_if, Ztilde_plriv, T_if) 
cat("ω'Y replicates moment based implentation?",all.equal(as.numeric( omega_plriv %*% Y ), to_be_rep_plriv))
ω'Y replicates moment based implentation? TRUE

Causal forest

To be replicated

Here, we want to replicate the CATE estimate for unit 1. To this end, we first run the causal_forest() with the pre-defined nuisance parameters:

cf = causal_forest(X,Y,D,Y.hat=Yhat,W.hat=Dhat)
cates_cf = predict(cf)$predictions

The estimated CATE for unit 1 is then 6038.6909875, which becomes the number to be replicated:

to_be_rep_cf = cates_cf[unit]
to_be_rep_cf
[1] 6038.691

Exact replication

Causal forest works equivalently to instrumental forest but requires weight \(\alpha^{cf}(\boldsymbol{x})\) to enter the pseudo-instrument:

alpha_cf = get_forest_weights(cf)[unit,]
# Create weighted residual maker matrix (slow and complicated but stick to paper notation)
M1_inv = solve(t(ones) %*% diag(alpha_cf) %*% ones)
P1 = (ones %*% M1_inv) %*% (t(ones) %*% diag(alpha_cf))
M1 = diag(N) - P1
# Get pseudo-instrument
Ztilde_cf = (M1 %*% Vhat) * alpha_cf

Plugging this new into the weight_maker() function pseudo-instrument again perfectly replicates the package output:

# Get if outcome weights
omega_cf = weight_maker(Dtilde_if, Ztilde_cf, T_if) 
cat("ω'Y replicates package output?",
    all.equal(as.numeric( omega_cf %*% Y ), to_be_rep_cf))
ω'Y replicates package output? TRUE

Partially linear regression

To obtain the standard partially linear regression, we first solve the canonical moment condition to see which value should be replicated:

to_be_rep_plr = mean(Vhat * Uhat) / mean(Vhat * Vhat)
to_be_rep_plr
[1] 13520.61

Compared to CF, we only need to pass a different pseudo-instrument to the weight_maker() function to replicate this number:

# Modified pseudo-instrument
Ztilde_plr = Vhat * ones
# Get outcome weights
omega_plr = weight_maker(Dtilde_if, Ztilde_plr, T_if) 
cat("ω'Y replicates moment based implementation?",
    all.equal(as.numeric( omega_plr %*% Y ), to_be_rep_plr))
ω'Y replicates moment based implementation? TRUE

Augmented inverse probability weighting

The AIPW uses a large pseudo-outcome and takes the mean of it:

Ytilde_aipw = Yhatd1 - Yhatd0 + lambda1 * (Y - Yhatd1) - lambda0 * (Y- Yhatd0)
to_be_rep_aipw = mean(Ytilde_aipw)
to_be_rep_aipw
[1] 11490.05

To replicate this number with outcome weights, we need to implement the transformation matrix

# Taipw = Sd1 - Sd0 + diag(lambda1) %*% (diag(N) - Sd1) - diag(lambda0) %*% (diag(N) - Sd0) # slow
T_aipw = Sd1 - Sd0 + lambda1 * (diag(N) - Sd1) - lambda0 * (diag(N) - Sd0)

and plug it into the weight maker to replicate the number:

omega_aipw = weight_maker(ones, ones, T_aipw) 
cat("ω'Y replicates standard implementation?",
    all.equal(as.numeric( omega_aipw %*% Y ), to_be_rep_aipw))
ω'Y replicates standard implementation? TRUE

Wald AIPW

The moment based representation is the ratio of to average treatment effects estiamted with AIPW:

Dtilde_ivaipw = Dhatz1 - Dhatz0 + Z / Zhat * (D - Dhatz1) - (1 - Z) / (1 - Zhat) * (D - Dhatz0)

Ytilde_ivaipw = Yhatz1 - Yhatz0 + Z / Zhat * (Y - Yhatz1) - (1 - Z) / (1 - Zhat) * (Y - Yhatz0)

ITT_y = mean(Ytilde_ivaipw)
ITT_d = mean(Dtilde_ivaipw)

to_be_rep_waipw = ITT_y / ITT_d
to_be_rep_waipw
[1] 11275.52

Again the transformation matrix is the involved part but we also have a non-one pseudo_treatment:

# T_waipw = Sz1 - Sz0 + diag(lambdaz1) %*% (diag(n) - Sz1) - diag(lambdaz0) %*% (diag(n) - Sz0)
T_waipw = Sz1 - Sz0 + lambdaz1 * (diag(N) - Sz1) - lambdaz0 * (diag(N) - Sz0)

Dtilde_waipw = ones * ITT_d

omega_waipw = weight_maker(Dtilde_waipw, ones, T_waipw)
cat("ω'Y replicates standard implementation?",
    all.equal(as.numeric( omega_waipw %*% Y ), to_be_rep_waipw))
ω'Y replicates standard implementation? TRUE

Outcome weights of special cases

TSLS

We can similarly extract the outcome weights of TSLS to replicate the standard implementation of the AER package:

tsls = ivreg(Y ~ D + X  | X + Z)
summary(tsls)

Call:
ivreg(formula = Y ~ D + X | X + Z)

Residuals:
    Min      1Q  Median      3Q     Max 
-507731  -16906   -2147   10266 1431531 

Coefficients:
                   Estimate Std. Error t value Pr(>|t|)    
(Intercept)      -3.239e+04  4.411e+03  -7.344 2.24e-13 ***
D                 8.483e+03  1.799e+03   4.716 2.43e-06 ***
XAge              6.248e+02  5.993e+01  10.425  < 2e-16 ***
XBenefit pension -4.514e+03  1.344e+03  -3.360 0.000783 ***
XEducation       -6.253e+02  2.282e+02  -2.740 0.006152 ** 
XFamily size     -1.067e+03  4.552e+02  -2.343 0.019150 *  
XHome owner       1.063e+03  1.323e+03   0.804 0.421557    
XIncome           9.283e-01  3.063e-02  30.309  < 2e-16 ***
XMale            -1.028e+03  1.513e+03  -0.679 0.496987    
XMarried          6.988e+02  1.814e+03   0.385 0.700108    
XIRA              2.912e+04  1.467e+03  19.853  < 2e-16 ***
XTwo earners     -1.933e+04  1.575e+03 -12.274  < 2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 55600 on 9903 degrees of freedom
Multiple R-Squared: 0.2348, Adjusted R-squared: 0.234 
Wald test:   272 on 11 and 9903 DF,  p-value: < 2.2e-16 
to_be_rep_tsls = tsls$coefficient[2]

We now use residuals produced by the residual maker matrix as pseudo-instrument and -treatment, and the residual maker matrix as transformation matrix:

# Get residuals
Ztilde_tsls = lm(Z ~ X)$residuals
Dtilde_tsls = lm(D ~ X)$residuals

# Get projection matrix
Xcons = model.matrix(~ X)
PX = Xcons %*% solve(crossprod(Xcons)) %*% t(Xcons)
# Get residual maker matrix
MX = diag(N) - PX

# Create TSLS
omega_tsls = weight_maker(Dtilde_tsls, Ztilde_tsls, MX) 

cat("ω'Y replicates standard implementation?",
    all.equal(as.numeric( omega_tsls %*% Y ), as.numeric(to_be_rep_tsls)))
ω'Y replicates standard implementation? TRUE

Wald estimator

The Wald estimator is replicated using the residual maker matrix of a constant:

# Get residuals
Ztilde_wald = lm(Z ~ 1)$residuals
Dtilde_wald = lm(D ~ 1)$residuals

# Get standard implementation
wald = ivreg(Y ~ D | Z)
to_be_rep_wald = wald$coefficient[2]

# Get projection and residual maker matrix of ones
P1 = ones %*% solve(crossprod(ones)) %*% t(ones)
M1 = diag(N) - P1

# Create TSLS
omega_wald = weight_maker(Dtilde_wald, Ztilde_wald, M1) 

cat("ω'Y replicates standard implementation?",
    all.equal(as.numeric( omega_wald %*% Y ), as.numeric(to_be_rep_wald)))
ω'Y replicates standard implementation? TRUE

OLS

To replicate OLS, we can just recycle the linear treatment residuals from TSLS

ols = lm(Y ~ D + X)
to_be_rep_ols = ols$coefficient[2]

# Create OLS weights
omega_ols = weight_maker(Dtilde_tsls, Dtilde_tsls, MX) 

cat("ω'Y replicates standard implementation?",
    all.equal(as.numeric( omega_ols %*% Y ), as.numeric(to_be_rep_ols)))
ω'Y replicates standard implementation? TRUE

Difference in means

Finally, the difference in means estimator is recovered by recycling the Wald residuals:

dim = lm(Y ~ D)
to_be_rep_dim = dim$coefficient[2]

# Create DiM weights
omega_dim = weight_maker(Dtilde_wald, Dtilde_wald, M1) 

cat("ω'Y replicates standard implementation?",
    all.equal(as.numeric( omega_dim %*% Y ), as.numeric(to_be_rep_dim)))
ω'Y replicates standard implementation? TRUE
LS0tDQp0aXRsZTogIlRyZWF0bWVudCBFZmZlY3QgRXN0aW1hdG9ycyBhcyBXZWlnaHRlZCBPdXRjb21lcyINCnN1YnRpdGxlOiAiVGhlb3J5IGluIGFjdGlvbiINCmF1dGhvcjogIk1pY2hhZWwgQy4gS25hdXMiDQpkYXRlOiAiYHIgZm9ybWF0KFN5cy50aW1lKCksICclbS8leScpYCINCm91dHB1dDogDQogIGh0bWxfbm90ZWJvb2s6DQogICAgdG9jOiB0cnVlDQogICAgdG9jX2Zsb2F0OiB0cnVlDQogICAgY29kZV9mb2xkaW5nOiBzaG93DQotLS0NCg0KDQojIFNldHRpbmcgdGhlIHN0YWdlDQoNCiMjIE1hbmFnaW5nIGV4cGVjdGF0aW9ucw0KDQpUaGlzIG5vdGVib29rIGlsbHVzdHJhdGVzIHRoZSB0aGVvcmV0aWNhbCBkZXJpdmF0aW9ucyBvZiB0aGUgcGFwZXIgIlRyZWF0bWVudCBFZmZlY3QgRXN0aW1hdG9ycyBhcyBXZWlnaHRlZCBPdXRjb21lcyIuIFdlIGtlZXAgZXZlcnl0aGluZyBhcyBzaW1wbGUgYXMgcG9zc2libGUgbWVhbmluZyB0aGF0DQoNCi0gd2UgdXNlIHRoZSBjbGVhbmVkIGFuZCByZWFkaWx5IGF2YWlsYWJsZSA0MDEoaykgZGF0YSBvZiB0aGUgYGhkbWAgcGFja2FnZSwgd2hpY2ggaW5jbHVkZXMgYSB0cmVhdG1lbnQgYW5kIGFuIGluc3RydW1lbnQNCg0KLSB3ZSB1c2UgdGhlIGByZWdyZXNzaW9uX2ZvcmVzdCgpYCBvZiB0aGUgYGdyZmAgdG8gZXN0aW1hdGUgbnVpc2FuY2UgcGFyYW1ldGVycyBiZWNhdXNlIHRoaXMgaXMgdGhlIG9ubHkgTUwgbWV0aG9kIHdpdGggYSBidWlsZC1pbiBmdW5jdGlvbiB0byBleHRyYWN0IHNtb290aGVyIHdlaWdodHMNCg0KLSB3ZSBoYW5kLWNvZGUgdHdvLWZvbGQgY3Jvc3MtdmFsaWRhdGlvbiB3aXRoIGByZWdyZXNzaW9uX2ZvcmVzdCgpYCBhbmQgcmV1c2UgdGhlIHNhbWUgbnVpc2FuY2UgcGFyYW1ldGVycyBmb3IgZGlmZmVyZW50IGVzdGltYXRvcnMNCg0KLSB3ZSBkbyBubyB0dW5lIHRoZSBoeXBlcnBhcmFtdGVycyBhbmQgc3RpY2sgdG8gdGhlIGRlZmF1bHQgc2V0dGluZw0KDQotIHdlIG9ubHkgY29uc2lkZXIgY2F1c2FsL2luc3RydW1lbnRhbCBmb3Jlc3QgZWZmZWN0IGVzdGltYXRlcyBmb3Igb25lIHVuaXQgYW5kIG5vdCBmb3IgYWxsIDk5MTUNCg0KLSB3ZSBzdGljayBhcyBjbG9zZSBhcyBwb3NzaWJsZSB0byB0aGUgcGFwZXIgbm90YXRpb24NCg0KSG93ZXZlciwgdGhlIGNvZGUgcHJvdmlkZXMgdGhlIGJhc2lzIHRvIGV4dGVuZCB0aGUgYW5hbHlzaXMgaW4gZGlmZmVyZW50IGRpcmVjdGlvbnMuIFRvIHRoaXMgZW5kLCBjbGljayBvbiB0aGUgIkNvZGUiIGJ1dHRvbiBhdCB0aGUgdG9wIHJpZ2h0IGFuZCAiRG93bmxvYWQgUm1kIi4NCg0KVGhpcyBub3RlYm9va3MgaXMgb25seSBmb3IgaWxsdXN0cmF0aW9uLiBUaGUgW2h0dHBzOi8vZ2l0aHViLmNvbS9NQ0tuYXVzL091dGNvbWVXZWlnaHRzXShPdXRjb21lV2VpZ2h0cykgUiBwYWNrYWdlIGltcGxlbWVudHMgZXZlcnl0aGluZyBpbiBhIG1vcmUgdXNlciBmcmllbmRseSB3YXkuDQoNCiMjIExvYWQgcGFja2FnZXMgYW5kIGRhdGENCg0KRmlyc3QsIGxvYWQgdGhlIHJlbGV2YW50IHBhY2thZ2VzDQoNCmBgYHtyLCB3YXJuaW5nID0gRiwgbWVzc2FnZSA9IEZ9DQppZiAoIXJlcXVpcmUoImNvYmFsdCIpKSBpbnN0YWxsLnBhY2thZ2VzKCJjb2JhbHQiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeShjb2JhbHQpDQppZiAoIXJlcXVpcmUoImdyZiIpKSBpbnN0YWxsLnBhY2thZ2VzKCJncmYiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeShncmYpDQppZiAoIXJlcXVpcmUoImhkbSIpKSBpbnN0YWxsLnBhY2thZ2VzKCJoZG0iLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeShoZG0pDQppZiAoIXJlcXVpcmUoImdyaWRFeHRyYSIpKSBpbnN0YWxsLnBhY2thZ2VzKCJncmlkRXh0cmEiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeShncmlkRXh0cmEpDQppZiAoIXJlcXVpcmUoInRpZHl2ZXJzZSIpKSBpbnN0YWxsLnBhY2thZ2VzKCJ0aWR5dmVyc2UiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeSh0aWR5dmVyc2UpDQppZiAoIXJlcXVpcmUoIkFFUiIpKSBpbnN0YWxsLnBhY2thZ2VzKCJBRVIiLCBkZXBlbmRlbmNpZXMgPSBUUlVFKTsgbGlicmFyeShBRVIpDQpgYGANCg0KYW5kIHRoZSBkYXRhDQoNCmBgYHtyfQ0KZGF0YShwZW5zaW9uKSAjIEZpbmQgdmFyaWFibGUgZGVzY3JpcHRpb24gaWYgeW91IHR5cGUgP3BlbnNpb24gaW4gY29uc29sZQ0KIyBUcmVhdG1lbnQNCkQgPSBwZW5zaW9uJHA0MDENCiMgSW5zdHJ1bWVudA0KWiA9IHBlbnNpb24kZTQwMQ0KIyBPdXRjb21lDQpZID0gcGVuc2lvbiRuZXRfdGZhDQojIENvbnRyb2xzDQpYID0gbW9kZWwubWF0cml4KH4gMCArIGFnZSArIGRiICsgZWR1YyArIGZzaXplICsgaG93biArIGluYyArIG1hbGUgKyBtYXJyICsgcGlyYSArIHR3b2Vhcm4sIGRhdGEgPSBwZW5zaW9uKQ0KY29sbmFtZXMoWCkgPSBjKCJBZ2UiLCJCZW5lZml0IHBlbnNpb24iLCJFZHVjYXRpb24iLCJGYW1pbHkgc2l6ZSIsIkhvbWUgb3duZXIiLCJJbmNvbWUiLCJNYWxlIiwiTWFycmllZCIsIklSQSIsIlR3byBlYXJuZXJzIikNCmBgYA0KDQpEZWZpbmUgdXNlZnVsIHF1YW50aXRpZXMgYW5kIHNldCB0aGUgc2VlZDoNCg0KYGBge3J9DQojIEhlbHBmdWwgdmFyaWFibGVzDQpOID0gbGVuZ3RoKFkpDQpvbmVzID0gbWF0cml4KDEsTiwxKQ0KDQojIENob29zZSB1bml0IGZvciB3aGljaCBjYXVzYWwvaW5zdHJ1bWVudGFsIGZvcmVzdCB3ZWlnaHRzIHNob3VsZCBiZSBjYWxjdWxhdGVkDQp1bml0ID0gMQ0KDQojIERlZmluZSBudW1iZXIgb2YgZm9sZHMgZm9yIGNyb3NzLWZpdHRpbmcNCm5mb2xkcyA9IDINCg0Kc2V0LnNlZWQoMTIzNCkNCmBgYA0KDQojIyBPbmUgZnVuY3Rpb24gdG8gY2FsY3VsYXRlIHRoZW0gYWxsDQoNClByb3Bvc2l0aW9uIDEgaW4gdGhlIHBhcGVyIHNob3dzIHRoYXQgdGhlIG91dGNvbWUgd2VpZ2h0cyB2ZWN0b3IgY2FuIGJlIG9idGFpbmVkIGluIHRoZSBnZW5lcmFsIGZvcm0NCiQkXGJvbGRzeW1ib2x7XG9tZWdhJ30gPSAoXGJvbGRzeW1ib2x7XHRpbGRle1p9J1x0aWxkZXtEfX0pXnstMX0gXGJvbGRzeW1ib2x7XHRpbGRle1p9J1R9JCQNCg0Kd2hlcmUgJFxib2xkc3ltYm9se1x0aWxkZXtafX0kLCAkXGJvbGRzeW1ib2x7XHRpbGRle0R9fSQgYW5kICRcYm9sZHN5bWJvbHtUfSQgYXJlIHBzZXVkby1pbnN0cnVtZW50LCBwc2V1ZG8tdHJlYXRtZW50IGFuZCB0aGUgdHJhbnNmb3JtYXRpb24gbWF0cml4LCByZXNwZWN0aXZlbHkuIA0KDQpUaGlzIG1vdGl2YXRlcyB0aGUgZGVmaW5pdGlvbiBvZiB0aGUgYHdlaWdodF9tYWtlcihEdGlsZGUsWnRpbGRlLFRfbWF0KWAgZnVuY3Rpb24gdGFraW5nIHRoZSB0aHJlZSBnZW5lcmljIGlucHV0cyBhbmQgcHJvZHVjaW5nIHRoZSBvdXRjb21lIHdlaWdodHMgdmVjdG9yOg0KDQpgYGB7cn0NCndlaWdodF9tYWtlciA9IGZ1bmN0aW9uKER0aWxkZSxadGlsZGUsVF9tYXQpIHsNCiAgb21lZ2EgPSAodChadGlsZGUpICUqJSBEdGlsZGUpXigtMSkgJSolIHQoWnRpbGRlKSAlKiUgVF9tYXQNCiAgcmV0dXJuKG9tZWdhKQ0KfQ0KYGBgDQoNCkluIHRoZSBmb2xsb3dpbmcsIHdlIGp1c3QgbmVlZCB0byBkZWZpbmUgdGhlIHRocmVlIGNvbXBvbmVudHMgZm9yIHRoZSByZXNwZWN0aXZlIGVzdGltYXRvcnMgYW5kIHBsdWcgdGhlbSBpbnRvIHRoaXMgZ2VuZXJpYyBmdW5jdGlvbiB0byBvYnRhaW4gdGhlIG91dGNvbWUgd2VpZ2h0cy4NCg0KDQojIyBFc3RpbWF0ZSBhbGwgbnVpc2FuY2UgcGFyYW1ldGVycyBhbmQgZ2V0IG91dGNvbWUgc21vb3RoZXIgbWF0cmljZXMNCg0KRXF1YXRpb24gKDgpIGluIHRoZSBwYXBlciBzaG93cyB3aGljaCBudWlzYW5jZSBwYXJhbWV0ZXJzIGFyZSByZXF1aXJlZCBmb3IgdGhlIGVzdGltYXRvcnMgdW5kZXIgY29uc2lkZXJhdGlvbi4gSGVyZSwgd2UgZXN0aW1hdGUgdGhlbSBhbGwgdXNpbmcgaG9uZXN0IHJhbmRvbSBmb3Jlc3QgYW5kIDItZm9sZCBjcm9zcy1maXR0aW5nLiBBZGRpdGlvbmFsbHksIHdlIGV4dHJhY3QgdGhlIHJlbGV2YW50IHNtb290aGVyIG1hdHJpY2VzICRcYm9sZHN5bWJvbHtTfSQsICRcYm9sZHN5bWJvbHtTXmRfMH0kLCAkXGJvbGRzeW1ib2x7U15kXzF9JCwgJFxib2xkc3ltYm9se1Neel8wfSQsIGFuZCAkXGJvbGRzeW1ib2x7U156XzF9JC4NCg0KYGBge3J9DQojIEdldCBmb2xkIG51bWJlcg0KZm9sZCA9IHNhbXBsZSgxOm5mb2xkcyxOLHJlcGxhY2U9VCkNCg0KIyBJbml0aWFsaXplIG51aXNhbmNlIHBhcmFtZXRlcnMNClloYXQgPSBZaGF0ZDAgPSBZaGF0ZDEgPSBZaGF0ejAgPSBZaGF0ejEgPSANCiAgRGhhdCA9IERoYXR6MCA9IERoYXR6MSA9IFpoYXQgPSByZXAoTkEsTikNCg0KIyBJbml0aWFsaXplIHNtb290aGVyIG1hdHJpY2VzDQpTID0gU2QwID0gU2QxID0gU3owID0gU3oxID0gbWF0cml4KDAsTixOKQ0KDQpmb3IgKGkgaW4gMTpuZm9sZHMpew0KICAjIENhbGN1bGF0ZSBudWlzYW5jZSBwYXJhbWV0ZXJzIGFuZCByZWxldmFudCBzbW9vdGhlciBtYXRyaWNlcw0KICByZl9ZaGF0ID0gcmVncmVzc2lvbl9mb3Jlc3QoWFtmb2xkICE9IGksXSxZW2ZvbGQgIT0gaV0pDQogIFloYXRbZm9sZCA9PSBpXSA9IHByZWRpY3QocmZfWWhhdCwgWFtmb2xkID09IGksXSkkcHJlZGljdGlvbnMNCiAgU1tmb2xkID09IGksIGZvbGQgIT0gaV0gPSBhcy5tYXRyaXgoZ2V0X2ZvcmVzdF93ZWlnaHRzKHJmX1loYXQsIFhbZm9sZCA9PSBpLF0pKQ0KDQogIHJmX1loYXRkMCA9IHJlZ3Jlc3Npb25fZm9yZXN0KFhbZm9sZCAhPSBpICYgRD09MCxdLFlbZm9sZCAhPSBpICYgRD09MF0pDQogIFloYXRkMFtmb2xkID09IGldID0gcHJlZGljdChyZl9ZaGF0ZDAsIFhbZm9sZCA9PSBpLF0pJHByZWRpY3Rpb25zDQogIFNkMFtmb2xkID09IGksIGZvbGQgIT0gaSAgJiBEPT0wXSA9IGFzLm1hdHJpeChnZXRfZm9yZXN0X3dlaWdodHMocmZfWWhhdGQwLCBYW2ZvbGQgPT0gaSxdKSkNCg0KICByZl9ZaGF0ZDEgPSByZWdyZXNzaW9uX2ZvcmVzdChYW2ZvbGQgIT0gaSAmIEQ9PTEsXSxZW2ZvbGQgIT0gaSAmIEQ9PTFdKQ0KICBZaGF0ZDFbZm9sZCA9PSBpXSA9IHByZWRpY3QocmZfWWhhdGQxLCBYW2ZvbGQgPT0gaSxdKSRwcmVkaWN0aW9ucw0KICBTZDFbZm9sZCA9PSBpLCBmb2xkICE9IGkgICYgRD09MV0gPSBhcy5tYXRyaXgoZ2V0X2ZvcmVzdF93ZWlnaHRzKHJmX1loYXRkMSwgWFtmb2xkID09IGksXSkpDQoNCiAgcmZfWWhhdHowID0gcmVncmVzc2lvbl9mb3Jlc3QoWFtmb2xkICE9IGkgJiBaPT0wLF0sWVtmb2xkICE9IGkgJiBaPT0wXSkNCiAgWWhhdHowW2ZvbGQgPT0gaV0gPSBwcmVkaWN0KHJmX1loYXR6MCwgWFtmb2xkID09IGksXSkkcHJlZGljdGlvbnMNCiAgU3owW2ZvbGQgPT0gaSwgZm9sZCAhPSBpICAmIFo9PTBdID0gYXMubWF0cml4KGdldF9mb3Jlc3Rfd2VpZ2h0cyhyZl9ZaGF0ejAsIFhbZm9sZCA9PSBpLF0pKQ0KICANCiAgcmZfWWhhdHoxID0gcmVncmVzc2lvbl9mb3Jlc3QoWFtmb2xkICE9IGkgJiBaPT0xLF0sWVtmb2xkICE9IGkgJiBaPT0xXSkNCiAgWWhhdHoxW2ZvbGQgPT0gaV0gPSBwcmVkaWN0KHJmX1loYXR6MSwgWFtmb2xkID09IGksXSkkcHJlZGljdGlvbnMNCiAgU3oxW2ZvbGQgPT0gaSwgZm9sZCAhPSBpICAmIFo9PTFdID0gYXMubWF0cml4KGdldF9mb3Jlc3Rfd2VpZ2h0cyhyZl9ZaGF0ejEsIFhbZm9sZCA9PSBpLF0pKQ0KICANCiAgcmZfRGhhdCA9IHJlZ3Jlc3Npb25fZm9yZXN0KFhbZm9sZCAhPSBpLF0sRFtmb2xkICE9IGldKQ0KICBEaGF0W2ZvbGQgPT0gaV0gPSBwcmVkaWN0KHJmX0RoYXQsIFhbZm9sZCA9PSBpLF0pJHByZWRpY3Rpb25zDQogIA0KICByZl9EaGF0ejAgPSByZWdyZXNzaW9uX2ZvcmVzdChYW2ZvbGQgIT0gaSAmIFo9PTAsXSxEW2ZvbGQgIT0gaSAmIFo9PTBdKQ0KICBEaGF0ejBbZm9sZCA9PSBpXSA9IHByZWRpY3QocmZfRGhhdHowLCBYW2ZvbGQgPT0gaSxdKSRwcmVkaWN0aW9ucw0KICANCiAgcmZfRGhhdHoxID0gcmVncmVzc2lvbl9mb3Jlc3QoWFtmb2xkICE9IGkgJiBaPT0xLF0sRFtmb2xkICE9IGkgJiBaPT0xXSkNCiAgRGhhdHoxW2ZvbGQgPT0gaV0gPSBwcmVkaWN0KHJmX0RoYXR6MSwgWFtmb2xkID09IGksXSkkcHJlZGljdGlvbnMNCiAgDQogIHJmX1poYXQgPSByZWdyZXNzaW9uX2ZvcmVzdChYW2ZvbGQgIT0gaSxdLFpbZm9sZCAhPSBpXSkNCiAgWmhhdFtmb2xkID09IGldID0gcHJlZGljdChyZl9aaGF0LCBYW2ZvbGQgPT0gaSxdKSRwcmVkaWN0aW9ucw0KfQ0KYGBgDQoNCkZvciB0aG9zZSBub3QgZmFtaWxpYXIgd2l0aCBzbW9vdGhlcnMsIGxldHMgb2JzZXJ2ZSB0aGF0IHRoZXkgcHJvZHVjZSBleGFjdGx5IHRoZSBzYW1lIHByZWRpY3Rpb25zIGFzIHRoZSBvcmlnaW5hbCBgcHJlZGljdCgpYCBmdW5jdGlvbnM6DQpgYGB7cn0NCmNhdCgiU21vb3RoZXIgbWF0cmljZXMgcmVwbGljYXRlIHByZWRpY3RlZCBudWlzYW5jZSBwYXJhbWV0ZXI/IiwNCiBhbGwoDQogIGFsbC5lcXVhbChhcy5udW1lcmljKFMgJSolIFkpLCBZaGF0KSA9PSBUUlVFLA0KICBhbGwuZXF1YWwoYXMubnVtZXJpYyhTZDAgJSolIFkpLCBZaGF0ZDApID09IFRSVUUsDQogIGFsbC5lcXVhbChhcy5udW1lcmljKFNkMSAlKiUgWSksIFloYXRkMSkgPT0gVFJVRSwNCiAgYWxsLmVxdWFsKGFzLm51bWVyaWMoU3owICUqJSBZKSwgWWhhdHowKSA9PSBUUlVFLA0KICBhbGwuZXF1YWwoYXMubnVtZXJpYyhTejEgJSolIFkpLCBZaGF0ejEpID09IFRSVUUpDQopDQpgYGANCg0KQWxzbyBvYnNlcnZlIHRoYXQgcmFuZG9tIGZvcmVzdCBpcyBhbiBhZmZpbmUgc21vb3RoZXIgYmVjYXVzZSBhbGwgcm93cyBhZGQgdXAgZXhhY3RseSB0byBvbmU6DQpgYGB7cn0NCmNhdCgiQWZmaW5lIHNtb290aGVyIG1hdHJpY2VzPyIsDQphbGwoDQogIGFsbC5lcXVhbChhcy5udW1lcmljKG9uZXMpLGFzLm51bWVyaWMocm93U3VtcyhTKSkpID09IFRSVUUsDQogIGFsbC5lcXVhbChhcy5udW1lcmljKG9uZXMpLGFzLm51bWVyaWMocm93U3VtcyhTZDApKSkgPT0gVFJVRSwNCiAgYWxsLmVxdWFsKGFzLm51bWVyaWMob25lcyksYXMubnVtZXJpYyhyb3dTdW1zKFNkMSkpKSA9PSBUUlVFLA0KICBhbGwuZXF1YWwoYXMubnVtZXJpYyhvbmVzKSxhcy5udW1lcmljKHJvd1N1bXMoU3owKSkpID09IFRSVUUsDQogIGFsbC5lcXVhbChhcy5udW1lcmljKG9uZXMpLGFzLm51bWVyaWMocm93U3VtcyhTejEpKSkgPT0gVFJVRSkNCikNCmBgYA0KDQpGaW5hbGx5LCBkZWZpbmUgdGhlIGRpZmZlcmVudCBJUFcgd2VpZ2h0cyBmb3IgbGF0ZXIgdXNlOg0KYGBge3J9DQpsYW1iZGExID0gRCAvIERoYXQNCmxhbWJkYTAgPSAoMS1EKSAvICgxLURoYXQpDQpsYW1iZGF6MSA9IFogLyBaaGF0DQpsYW1iZGF6MCA9ICgxLVopIC8gKDEtWmhhdCkNCmBgYA0KDQoNCiMgT3V0Y29tZSB3ZWlnaHRzIG9mIERNTCBhbmQgR1JGDQoNCiMjIEluc3RydW1lbnRhbCBmb3Jlc3QNCg0KIyMjIFRvIGJlIHJlcGxpY2F0ZWQNCg0KSGVyZSwgd2Ugd2FudCB0byByZXBsaWNhdGUgdGhlIENMQVRFIGVzdGltYXRlIGZvciB1bml0IGByIHVuaXRgLiBUbyB0aGlzIGVuZCwgd2UgZmlyc3QgcnVuIGBpbnN0cnVtZW50YWxfZm9yZXN0KClgIHdpdGggdGhlIHByZS1kZWZpbmVkIG51aXNhbmNlIHBhcmFtZXRlcnM6DQpgYGB7cn0NCiMgUnVuIElGIHdpdGggdGhlIHByZS1zcGVjaWZpZWQgbnVpc2FuY2UgcGFyYW1ldGVycw0KaXZmID0gaW5zdHJ1bWVudGFsX2ZvcmVzdChYLFksRCxaLFkuaGF0PVloYXQsVy5oYXQ9RGhhdCxaLmhhdD1aaGF0KQ0KIyBHZXQgQ0xBVEVzIA0KY2xhdGVzX2lmID0gcHJlZGljdChpdmYpJHByZWRpY3Rpb25zDQpgYGANCg0KVGhlIGVzdGltYXRlZCBDTEFURSBmb3IgdW5pdCBgciB1bml0YCBpcyB0aGVuIGByIGNsYXRlc19pZlt1bml0XSBgLCB3aGljaCBiZWNvbWVzIHRoZSBudW1iZXIgdG8gYmUgcmVwbGljYXRlZDoNCmBgYHtyfQ0KdG9fYmVfcmVwX2lmID0gY2xhdGVzX2lmW3VuaXRdDQp0b19iZV9yZXBfaWYNCmBgYA0KDQojIyMgTmVhcmx5IHJlcGxpY2F0aW9uIHVzaW5nIHdlaWdodHMNCg0KQWNjb3JkaW5nIHRvIHRoZSBtYWluIHRleHQgb2YgdGhlIHBhcGVyLCB3ZSBuZWVkIHRoZSBmb2xsb3dpbmcgY29tcG9uZW50cyANCiQkXGJvbGRzeW1ib2x7XGhhdHtSfX0gPSBcYm9sZHN5bWJvbHtafSAtIFxib2xkc3ltYm9se1xoYXR7Wn19LCBccXVhZCBcYm9sZHN5bWJvbHtcaGF0e1Z9fSA9IFxib2xkc3ltYm9se0R9IC0gXGJvbGRzeW1ib2x7XGhhdHtEfX0sIFxxdWFkIFxib2xkc3ltYm9se1xoYXR7VX19ID0gXGJvbGRzeW1ib2x7WX0gLSBcYm9sZHN5bWJvbHtcaGF0e1l9fSwgXHF1YWQgXGFscGhhXntpZn0oXGJvbGRzeW1ib2x7eH0pJCQNCnRoYXQgYXJlIGRlZmluZWQgaW4gdGhlIGZvbGxvd2luZw0KYGBge3J9DQpVaGF0ID0gWSAtIFloYXQNClZoYXQgPSBEIC0gRGhhdA0KUmhhdCA9IFogLSBaaGF0DQphbHBoYV9pZiA9IGdldF9mb3Jlc3Rfd2VpZ2h0cyhpdmYpW3VuaXQsXQ0KYGBgDQoNCk5vdyBkZWZpbmUgdGhlIHBzZXVkby12YXJpYWJsZXMgYW5kIHRoZSB0cmFuc2Zvcm1hdGlvbiBtYXRyaXg6DQpgYGB7cn0NClp0aWxkZV9pZiA9IFJoYXQgKiBhbHBoYV9pZg0KRHRpbGRlX2lmID0gVmhhdA0KWXRpbGRlX2lmID0gVWhhdA0KVF9pZiA9IGRpYWcoTikgLSBTDQpgYGANCg0KQXMgYSBzYW5pdHkgY2hlY2sgb2JzZXJ2ZSBob3cgdGhlIHRyYW5zZm9ybWF0aW9uIG1hdHJpeCByZXBsaWNhdGVzIHRoZSBwc2V1ZG8tb3V0Y29tZToNCmBgYHtyfQ0KY2F0KCJUWSByZXBsaWNhdGVzIHBzZXVkby1vdXRjb21lPyIsDQogIGFsbC5lcXVhbChhcy5udW1lcmljKCBUX2lmICUqJSBZICksIFVoYXQpKQ0KYGBgDQoNCk5vdyB3ZSBwYXNzIHRoZSByZXF1aXJlZCBjb21wb25lbnRzIHRvIHRoZSBgd2VpZ2h0X21ha2VyKClgIGZ1bmN0aW9uDQpgYGB7cn0NCm9tZWdhX2lmID0gd2VpZ2h0X21ha2VyKER0aWxkZV9pZiwgWnRpbGRlX2lmLCBUX2lmKQ0KYGBgDQoNClRoaXMgZXN0aW1hdGVzIGFuIGVmZmVjdCBvZiBgciBvbWVnYV9pZiAlKiUgWWAsIHdoaWNoIGlzIHZlcnkgY2xvc2UgYnV0IG5vdCBpZGVudGljYWwgdG8gdGhlIG51bWJlciB0byBiZSByZXBsaWNhdGVkOg0KYGBge3J9DQphbGwuZXF1YWwoYXMubnVtZXJpYyggb21lZ2FfaWYgJSolIFkgKSwgdG9fYmVfcmVwX2lmKQ0KYGBgDQoNCiMjIyBFeGFjdCByZXBsaWNhdGlvbg0KDQpBcyBub3RlZCBpbiBBcHBlbmRpeCBBLjMuMSwgdGhlIGdyZiBwYWNrYWdlIGFwcGxpZXMgYW4gYWRkaXRpb25hbCBjb25zdGFudCB3aGljaCByZXF1aXJlcyB0byBhZGp1c3QgdGhlIHBzZXVkby1pbnN0cnVtZW50Og0KYGBge3J9DQojIENyZWF0ZSB3ZWlnaHRlZCByZXNpZHVhbCBtYWtlciBtYXRyaXgNCk0xX2ludiA9IHNvbHZlKHQob25lcykgJSolIGRpYWcoYWxwaGFfaWYpICUqJSBvbmVzKQ0KUDEgPSAob25lcyAlKiUgTTFfaW52KSAlKiUgKHQob25lcykgJSolIGRpYWcoYWxwaGFfaWYpKQ0KTTEgPSBkaWFnKE4pIC0gUDENCiMgR2V0IG1vZGlmaWVkIHBzZXVkby1pbnN0cnVtZW50DQpadGlsZGVfaWYgPSAoTTEgJSolIFJoYXQpICogYWxwaGFfaWYNCmBgYA0KDQpQbHVnZ2luZyB0aGlzIG5ldyBwc2V1ZG8taW5zdHJ1bWVudCBpbnRvIHRoZSBgd2VpZ2h0X21ha2VyKClgIGZ1bmN0aW9uIGNyZWF0ZXMgb3V0Y29tZSB3ZWlnaHRzIHRoYXQgbm93IHBlcmZlY3RseSByZXBsaWNhdGUgdGhlIHBhY2thZ2Ugb3V0cHV0Og0KYGBge3J9DQojIEdldCBpZiBvdXRjb21lIHdlaWdodHMNCm9tZWdhX2lmID0gd2VpZ2h0X21ha2VyKER0aWxkZV9pZiwgWnRpbGRlX2lmLCBUX2lmKSANCmNhdCgiz4knWSByZXBsaWNhdGVzIHBhY2thZ2Ugb3V0cHV0PyIsYWxsLmVxdWFsKGFzLm51bWVyaWMoIG9tZWdhX2lmICUqJSBZICksIHRvX2JlX3JlcF9pZikpDQpgYGANCg0KIyMgUGFydGlhbGx5IGxpbmVhciBJViByZWdyZXNzaW9uDQoNClRvIG9idGFpbiB0aGUgc3RhbmRhcmQgcGFydGlhbGx5IGxpbmVhciBJViByZWdyZXNzaW9uLCB3ZSBmaXJzdCBzb2x2ZSB0aGUgY2Fub25pY2FsIG1vbWVudCBjb25kaXRpb24gdG8gc2VlIHdoaWNoIHZhbHVlIHNob3VsZCBiZSByZXBsaWNhdGVkOg0KYGBge3J9DQp0b19iZV9yZXBfcGxyaXYgPSBtZWFuKFJoYXQgKiBVaGF0KSAvIG1lYW4oUmhhdCAqIFZoYXQpDQp0b19iZV9yZXBfcGxyaXYNCmBgYA0KDQpDb21wYXJlZCB0byBJRiwgd2Ugb25seSBuZWVkIHRvIHBhc3MgYSBkaWZmZXJlbnQgcHNldWRvLWluc3RydW1lbnQgdG8gdGhlIHdlaWdodCBtYWtlciBmdW5jdGlvbiB0byByZXBsaWNhdGUgdGhpcyBudW1iZXI6DQpgYGB7cn0NCiMgTW9kaWZpZWQgcHNldWRvLWluc3RydW1lbnQNClp0aWxkZV9wbHJpdiA9IFJoYXQgKiBvbmVzDQojIEdldCBvdXRjb21lIHdlaWdodHMNCm9tZWdhX3Bscml2ID0gd2VpZ2h0X21ha2VyKER0aWxkZV9pZiwgWnRpbGRlX3Bscml2LCBUX2lmKSANCmNhdCgiz4knWSByZXBsaWNhdGVzIG1vbWVudCBiYXNlZCBpbXBsZW50YXRpb24/IixhbGwuZXF1YWwoYXMubnVtZXJpYyggb21lZ2FfcGxyaXYgJSolIFkgKSwgdG9fYmVfcmVwX3Bscml2KSkNCmBgYA0KDQoNCiMjIENhdXNhbCBmb3Jlc3QNCg0KIyMjIFRvIGJlIHJlcGxpY2F0ZWQNCg0KSGVyZSwgd2Ugd2FudCB0byByZXBsaWNhdGUgdGhlIENBVEUgZXN0aW1hdGUgZm9yIHVuaXQgYHIgdW5pdGAuIFRvIHRoaXMgZW5kLCB3ZSBmaXJzdCBydW4gdGhlIGBjYXVzYWxfZm9yZXN0KClgIHdpdGggdGhlIHByZS1kZWZpbmVkIG51aXNhbmNlIHBhcmFtZXRlcnM6DQpgYGB7cn0NCmNmID0gY2F1c2FsX2ZvcmVzdChYLFksRCxZLmhhdD1ZaGF0LFcuaGF0PURoYXQpDQpjYXRlc19jZiA9IHByZWRpY3QoY2YpJHByZWRpY3Rpb25zDQpgYGANCg0KVGhlIGVzdGltYXRlZCBDQVRFIGZvciB1bml0IGByIHVuaXRgIGlzIHRoZW4gYHIgY2F0ZXNfY2ZbdW5pdF0gYCwgd2hpY2ggYmVjb21lcyB0aGUgbnVtYmVyIHRvIGJlIHJlcGxpY2F0ZWQ6DQpgYGB7cn0NCnRvX2JlX3JlcF9jZiA9IGNhdGVzX2NmW3VuaXRdDQp0b19iZV9yZXBfY2YNCmBgYA0KDQojIyMgRXhhY3QgcmVwbGljYXRpb24NCg0KQ2F1c2FsIGZvcmVzdCB3b3JrcyBlcXVpdmFsZW50bHkgdG8gaW5zdHJ1bWVudGFsIGZvcmVzdCBidXQgcmVxdWlyZXMgd2VpZ2h0ICRcYWxwaGFee2NmfShcYm9sZHN5bWJvbHt4fSkkIHRvIGVudGVyIHRoZSBwc2V1ZG8taW5zdHJ1bWVudDoNCmBgYHtyfQ0KYWxwaGFfY2YgPSBnZXRfZm9yZXN0X3dlaWdodHMoY2YpW3VuaXQsXQ0KTTFfaW52ID0gc29sdmUodChvbmVzKSAlKiUgZGlhZyhhbHBoYV9jZikgJSolIG9uZXMpDQpQMSA9IChvbmVzICUqJSBNMV9pbnYpICUqJSAodChvbmVzKSAlKiUgZGlhZyhhbHBoYV9jZikpDQpNMSA9IGRpYWcoTikgLSBQMQ0KIyBHZXQgcHNldWRvLWluc3RydW1lbnQNClp0aWxkZV9jZiA9IChNMSAlKiUgVmhhdCkgKiBhbHBoYV9jZg0KYGBgDQoNClBsdWdnaW5nIHRoaXMgbmV3IGludG8gdGhlIGB3ZWlnaHRfbWFrZXIoKWAgZnVuY3Rpb24gcHNldWRvLWluc3RydW1lbnQgYWdhaW4gcGVyZmVjdGx5IHJlcGxpY2F0ZXMgdGhlIHBhY2thZ2Ugb3V0cHV0Og0KYGBge3J9DQojIEdldCBpZiBvdXRjb21lIHdlaWdodHMNCm9tZWdhX2NmID0gd2VpZ2h0X21ha2VyKER0aWxkZV9pZiwgWnRpbGRlX2NmLCBUX2lmKSANCmNhdCgiz4knWSByZXBsaWNhdGVzIHBhY2thZ2Ugb3V0cHV0PyIsDQogICAgYWxsLmVxdWFsKGFzLm51bWVyaWMoIG9tZWdhX2NmICUqJSBZICksIHRvX2JlX3JlcF9jZikpDQpgYGANCg0KIyMgUGFydGlhbGx5IGxpbmVhciByZWdyZXNzaW9uDQoNClRvIG9idGFpbiB0aGUgc3RhbmRhcmQgcGFydGlhbGx5IGxpbmVhciByZWdyZXNzaW9uLCB3ZSBmaXJzdCBzb2x2ZSB0aGUgY2Fub25pY2FsIG1vbWVudCBjb25kaXRpb24gdG8gc2VlIHdoaWNoIHZhbHVlIHNob3VsZCBiZSByZXBsaWNhdGVkOg0KYGBge3J9DQp0b19iZV9yZXBfcGxyID0gbWVhbihWaGF0ICogVWhhdCkgLyBtZWFuKFZoYXQgKiBWaGF0KQ0KdG9fYmVfcmVwX3Bscg0KYGBgDQoNCkNvbXBhcmVkIHRvIENGLCB3ZSBvbmx5IG5lZWQgdG8gcGFzcyBhIGRpZmZlcmVudCBwc2V1ZG8taW5zdHJ1bWVudCB0byB0aGUgYHdlaWdodF9tYWtlcigpYCBmdW5jdGlvbiB0byByZXBsaWNhdGUgdGhpcyBudW1iZXI6DQpgYGB7cn0NCiMgTW9kaWZpZWQgcHNldWRvLWluc3RydW1lbnQNClp0aWxkZV9wbHIgPSBWaGF0ICogb25lcw0KIyBHZXQgb3V0Y29tZSB3ZWlnaHRzDQpvbWVnYV9wbHIgPSB3ZWlnaHRfbWFrZXIoRHRpbGRlX2lmLCBadGlsZGVfcGxyLCBUX2lmKSANCmNhdCgiz4knWSByZXBsaWNhdGVzIG1vbWVudCBiYXNlZCBpbXBsZW1lbnRhdGlvbj8iLA0KICAgIGFsbC5lcXVhbChhcy5udW1lcmljKCBvbWVnYV9wbHIgJSolIFkgKSwgdG9fYmVfcmVwX3BscikpDQpgYGANCg0KIyMgQXVnbWVudGVkIGludmVyc2UgcHJvYmFiaWxpdHkgd2VpZ2h0aW5nDQoNClRoZSBBSVBXIHVzZXMgYSBsYXJnZSBwc2V1ZG8tb3V0Y29tZSBhbmQgdGFrZXMgdGhlIG1lYW4gb2YgaXQ6DQpgYGB7cn0NCll0aWxkZV9haXB3ID0gWWhhdGQxIC0gWWhhdGQwICsgbGFtYmRhMSAqIChZIC0gWWhhdGQxKSAtIGxhbWJkYTAgKiAoWS0gWWhhdGQwKQ0KdG9fYmVfcmVwX2FpcHcgPSBtZWFuKFl0aWxkZV9haXB3KQ0KdG9fYmVfcmVwX2FpcHcNCmBgYA0KDQpUbyByZXBsaWNhdGUgdGhpcyBudW1iZXIgd2l0aCBvdXRjb21lIHdlaWdodHMsIHdlIG5lZWQgdG8gaW1wbGVtZW50IHRoZSB0cmFuc2Zvcm1hdGlvbiBtYXRyaXgNCmBgYHtyfQ0KIyBUYWlwdyA9IFNkMSAtIFNkMCArIGRpYWcobGFtYmRhMSkgJSolIChkaWFnKE4pIC0gU2QxKSAtIGRpYWcobGFtYmRhMCkgJSolIChkaWFnKE4pIC0gU2QwKSAjIHNsb3cNClRfYWlwdyA9IFNkMSAtIFNkMCArIGxhbWJkYTEgKiAoZGlhZyhOKSAtIFNkMSkgLSBsYW1iZGEwICogKGRpYWcoTikgLSBTZDApDQpgYGANCg0KYW5kIHBsdWcgaXQgaW50byB0aGUgd2VpZ2h0IG1ha2VyIHRvIHJlcGxpY2F0ZSB0aGUgbnVtYmVyOg0KYGBge3J9DQpvbWVnYV9haXB3ID0gd2VpZ2h0X21ha2VyKG9uZXMsIG9uZXMsIFRfYWlwdykgDQpjYXQoIs+JJ1kgcmVwbGljYXRlcyBzdGFuZGFyZCBpbXBsZW1lbnRhdGlvbj8iLA0KICAgIGFsbC5lcXVhbChhcy5udW1lcmljKCBvbWVnYV9haXB3ICUqJSBZICksIHRvX2JlX3JlcF9haXB3KSkNCmBgYA0KDQojIyBXYWxkIEFJUFcNCg0KVGhlIG1vbWVudCBiYXNlZCByZXByZXNlbnRhdGlvbiBpcyB0aGUgcmF0aW8gb2YgdG8gYXZlcmFnZSB0cmVhdG1lbnQgZWZmZWN0cyBlc3RpYW10ZWQgd2l0aCBBSVBXOg0KYGBge3J9DQpEdGlsZGVfaXZhaXB3ID0gRGhhdHoxIC0gRGhhdHowICsgWiAvIFpoYXQgKiAoRCAtIERoYXR6MSkgLSAoMSAtIFopIC8gKDEgLSBaaGF0KSAqIChEIC0gRGhhdHowKQ0KDQpZdGlsZGVfaXZhaXB3ID0gWWhhdHoxIC0gWWhhdHowICsgWiAvIFpoYXQgKiAoWSAtIFloYXR6MSkgLSAoMSAtIFopIC8gKDEgLSBaaGF0KSAqIChZIC0gWWhhdHowKQ0KDQpJVFRfeSA9IG1lYW4oWXRpbGRlX2l2YWlwdykNCklUVF9kID0gbWVhbihEdGlsZGVfaXZhaXB3KQ0KDQp0b19iZV9yZXBfd2FpcHcgPSBJVFRfeSAvIElUVF9kDQp0b19iZV9yZXBfd2FpcHcNCmBgYA0KDQpBZ2FpbiB0aGUgdHJhbnNmb3JtYXRpb24gbWF0cml4IGlzIHRoZSBpbnZvbHZlZCBwYXJ0IGJ1dCB3ZSBhbHNvIGhhdmUgYSBub24tb25lIHBzZXVkb190cmVhdG1lbnQ6DQpgYGB7cn0NCiMgVF93YWlwdyA9IFN6MSAtIFN6MCArIGRpYWcobGFtYmRhejEpICUqJSAoZGlhZyhuKSAtIFN6MSkgLSBkaWFnKGxhbWJkYXowKSAlKiUgKGRpYWcobikgLSBTejApDQpUX3dhaXB3ID0gU3oxIC0gU3owICsgbGFtYmRhejEgKiAoZGlhZyhOKSAtIFN6MSkgLSBsYW1iZGF6MCAqIChkaWFnKE4pIC0gU3owKQ0KDQpEdGlsZGVfd2FpcHcgPSBvbmVzICogSVRUX2QNCg0Kb21lZ2Ffd2FpcHcgPSB3ZWlnaHRfbWFrZXIoRHRpbGRlX3dhaXB3LCBvbmVzLCBUX3dhaXB3KQ0KY2F0KCLPiSdZIHJlcGxpY2F0ZXMgc3RhbmRhcmQgaW1wbGVtZW50YXRpb24/IiwNCiAgICBhbGwuZXF1YWwoYXMubnVtZXJpYyggb21lZ2Ffd2FpcHcgJSolIFkgKSwgdG9fYmVfcmVwX3dhaXB3KSkNCmBgYA0KDQoNCiMgT3V0Y29tZSB3ZWlnaHRzIG9mIHNwZWNpYWwgY2FzZXMNCg0KIyMgVFNMUw0KDQpXZSBjYW4gc2ltaWxhcmx5IGV4dHJhY3QgdGhlIG91dGNvbWUgd2VpZ2h0cyBvZiBUU0xTIHRvIHJlcGxpY2F0ZSB0aGUgc3RhbmRhcmQgaW1wbGVtZW50YXRpb24gb2YgdGhlIGBBRVJgIHBhY2thZ2U6DQoNCmBgYHtyfQ0KdHNscyA9IGl2cmVnKFkgfiBEICsgWCAgfCBYICsgWikNCnN1bW1hcnkodHNscykNCnRvX2JlX3JlcF90c2xzID0gdHNscyRjb2VmZmljaWVudFsyXQ0KYGBgDQoNCldlIG5vdyB1c2UgcmVzaWR1YWxzIHByb2R1Y2VkIGJ5IHRoZSByZXNpZHVhbCBtYWtlciBtYXRyaXggYXMgcHNldWRvLWluc3RydW1lbnQgYW5kIC10cmVhdG1lbnQsIGFuZCB0aGUgcmVzaWR1YWwgbWFrZXIgbWF0cml4IGFzIHRyYW5zZm9ybWF0aW9uIG1hdHJpeDoNCg0KYGBge3J9DQojIEdldCByZXNpZHVhbHMNClp0aWxkZV90c2xzID0gbG0oWiB+IFgpJHJlc2lkdWFscw0KRHRpbGRlX3RzbHMgPSBsbShEIH4gWCkkcmVzaWR1YWxzDQoNCiMgR2V0IHByb2plY3Rpb24gbWF0cml4DQpYY29ucyA9IG1vZGVsLm1hdHJpeCh+IFgpDQpQWCA9IFhjb25zICUqJSBzb2x2ZShjcm9zc3Byb2QoWGNvbnMpKSAlKiUgdChYY29ucykNCiMgR2V0IHJlc2lkdWFsIG1ha2VyIG1hdHJpeA0KTVggPSBkaWFnKE4pIC0gUFgNCg0KIyBDcmVhdGUgVFNMUw0Kb21lZ2FfdHNscyA9IHdlaWdodF9tYWtlcihEdGlsZGVfdHNscywgWnRpbGRlX3RzbHMsIE1YKSANCg0KY2F0KCLPiSdZIHJlcGxpY2F0ZXMgc3RhbmRhcmQgaW1wbGVtZW50YXRpb24/IiwNCiAgICBhbGwuZXF1YWwoYXMubnVtZXJpYyggb21lZ2FfdHNscyAlKiUgWSApLCBhcy5udW1lcmljKHRvX2JlX3JlcF90c2xzKSkpDQoNCmBgYA0KDQojIyBXYWxkIGVzdGltYXRvcg0KDQpUaGUgV2FsZCBlc3RpbWF0b3IgaXMgcmVwbGljYXRlZCB1c2luZyB0aGUgcmVzaWR1YWwgbWFrZXIgbWF0cml4IG9mIGEgY29uc3RhbnQ6DQoNCmBgYHtyfQ0KIyBHZXQgcmVzaWR1YWxzDQpadGlsZGVfd2FsZCA9IGxtKFogfiAxKSRyZXNpZHVhbHMNCkR0aWxkZV93YWxkID0gbG0oRCB+IDEpJHJlc2lkdWFscw0KDQojIEdldCBzdGFuZGFyZCBpbXBsZW1lbnRhdGlvbg0Kd2FsZCA9IGl2cmVnKFkgfiBEIHwgWikNCnRvX2JlX3JlcF93YWxkID0gd2FsZCRjb2VmZmljaWVudFsyXQ0KDQojIEdldCBwcm9qZWN0aW9uIGFuZCByZXNpZHVhbCBtYWtlciBtYXRyaXggb2Ygb25lcw0KUDEgPSBvbmVzICUqJSBzb2x2ZShjcm9zc3Byb2Qob25lcykpICUqJSB0KG9uZXMpDQpNMSA9IGRpYWcoTikgLSBQMQ0KDQojIENyZWF0ZSBUU0xTDQpvbWVnYV93YWxkID0gd2VpZ2h0X21ha2VyKER0aWxkZV93YWxkLCBadGlsZGVfd2FsZCwgTTEpIA0KDQpjYXQoIs+JJ1kgcmVwbGljYXRlcyBzdGFuZGFyZCBpbXBsZW1lbnRhdGlvbj8iLA0KICAgIGFsbC5lcXVhbChhcy5udW1lcmljKCBvbWVnYV93YWxkICUqJSBZICksIGFzLm51bWVyaWModG9fYmVfcmVwX3dhbGQpKSkNCmBgYA0KDQoNCiMjIE9MUw0KDQpUbyByZXBsaWNhdGUgT0xTLCB3ZSBjYW4ganVzdCByZWN5Y2xlIHRoZSBsaW5lYXIgdHJlYXRtZW50IHJlc2lkdWFscyBmcm9tIFRTTFMNCg0KYGBge3J9DQpvbHMgPSBsbShZIH4gRCArIFgpDQp0b19iZV9yZXBfb2xzID0gb2xzJGNvZWZmaWNpZW50WzJdDQoNCiMgQ3JlYXRlIE9MUyB3ZWlnaHRzDQpvbWVnYV9vbHMgPSB3ZWlnaHRfbWFrZXIoRHRpbGRlX3RzbHMsIER0aWxkZV90c2xzLCBNWCkgDQoNCmNhdCgiz4knWSByZXBsaWNhdGVzIHN0YW5kYXJkIGltcGxlbWVudGF0aW9uPyIsDQogICAgYWxsLmVxdWFsKGFzLm51bWVyaWMoIG9tZWdhX29scyAlKiUgWSApLCBhcy5udW1lcmljKHRvX2JlX3JlcF9vbHMpKSkNCmBgYA0KDQojIyBEaWZmZXJlbmNlIGluIG1lYW5zDQoNCkZpbmFsbHksIHRoZSBkaWZmZXJlbmNlIGluIG1lYW5zIGVzdGltYXRvciBpcyByZWNvdmVyZWQgYnkgcmVjeWNsaW5nIHRoZSBXYWxkIHJlc2lkdWFsczoNCg0KYGBge3J9DQpkaW0gPSBsbShZIH4gRCkNCnRvX2JlX3JlcF9kaW0gPSBkaW0kY29lZmZpY2llbnRbMl0NCg0KIyBDcmVhdGUgRGlNIHdlaWdodHMNCm9tZWdhX2RpbSA9IHdlaWdodF9tYWtlcihEdGlsZGVfd2FsZCwgRHRpbGRlX3dhbGQsIE0xKSANCg0KY2F0KCLPiSdZIHJlcGxpY2F0ZXMgc3RhbmRhcmQgaW1wbGVtZW50YXRpb24/IiwNCiAgICBhbGwuZXF1YWwoYXMubnVtZXJpYyggb21lZ2FfZGltICUqJSBZICksIGFzLm51bWVyaWModG9fYmVfcmVwX2RpbSkpKQ0KYGBgDQoNCg0KDQoNCg0K