Effect homogeneity
DGP
Consider the following DGP with homogeneous effects and a binary
treatment:
\(p=5\) independent covariates
\(X_1,...,X_k,...,X_{5}\) drawn from a
uniform distribution: \(X_k \sim
uniform(-\pi,\pi)\)
The treatment model is \(W \sim
Bernoulli(\underbrace{\Phi(sin(X_1))}_{e(X)})\), where \(\Phi(\cdot)\) is the standard normal
cumulative density function
The outcome model is \(Y =
\underbrace{0.1}_{\tau} W + \underbrace{sin(X_1)}_{m(X)}+
\varepsilon\), with \(\varepsilon \sim
N(0,1)\)
This means that we are in a highly nonlinear setting, but only one
variable (\(X_1\)) is relevant and the
others are just noise. The treatment model produces in expectation a
balanced treatment share with 50% controls and 50% treated.
if (!require("grf")) install.packages("grf", dependencies = TRUE); library(grf)
if (!require("tidyverse")) install.packages("tidyverse", dependencies = TRUE); library(tidyverse)
if (!require("patchwork")) install.packages("patchwork", dependencies = TRUE); library(patchwork)
if (!require("causalDML")) {
if (!require("devtools")) install.packages("devtools", dependencies = TRUE); library(devtools)
install_github(repo="MCKnaus/causalDML")
}; library(causalDML)
set.seed(1234)
# Set parameters
n = 200
p = 10
theta = 0.1
# Define and plot functions
x = matrix(runif(n*p,-pi,pi),ncol=p)
e = function(x){pnorm(sin(x))}
m0 = function(x){sin(x)}
m1 = function(x){m0(x) + theta}
tau = function(x){m1(x) - m0(x)}
w = rbinom(n,1,e(x[,1]))
y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)
g1 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=e,size=1) + ylab("e") + xlab("X1")
g2 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,aes(colour="Y1")) +
stat_function(fun=m0,size=1,aes(colour="Y0")) + ylab("Y") + xlab("X1")
g3 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab(expression(tau)) + xlab("X1")
g1 / g2 / g3
Hand-coded AIPW w/o cross-fitting
We draw a sample of \(N=200\) and
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
without honesty (sample size too small for honesty) and plug the
predictions into 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}}\]
# No cross-fitting
# Predict propensity score
rf = regression_forest(x,w,honesty=F)
ehat = predict(rf,newdata=x)$predictions
# Model control outcome using only control and predict for all
rf = regression_forest(x[w==0,],y[w==0],honesty=F)
m0hat = predict(rf,newdata=x)$predictions
# Model control outcome using only control and predict for all
rf = regression_forest(x[w==1,],y[w==1],honesty=F)
m1hat = predict(rf,newdata=x)$predictions
# Generate pseudo-outcome
pseudo_y = m1hat - m0hat +
w*(y-m1hat) / ehat - (1-w)*(y-m0hat) / (1-ehat)
Take the mean of the pseudo-outcome and run a t-test
mean(pseudo_y)
[1] 0.1179403
t.test(pseudo_y)
One Sample t-test
data: pseudo_y
t = 1.3308, df = 199, p-value = 0.1848
alternative hypothesis: true mean is not equal to 0
95 percent confidence interval:
-0.05681688 0.29269743
sample estimates:
mean of x
0.1179403
or run just an OLS regression with only a constant for point
estimation and inference in one step.
summary(lm(pseudo_y~1))
Call:
lm(formula = pseudo_y ~ 1)
Residuals:
Min 1Q Median 3Q Max
-4.1751 -0.8027 -0.0574 0.8494 3.3141
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 0.11794 0.08862 1.331 0.185
Residual standard error: 1.253 on 199 degrees of freedom
Hand-coded AIPW with 2-fold cross-fitting
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
Plug the prediction in the pseudo-outcome and proceed as
above
# 2-fold cross-fitting
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,honesty=F)
ehat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x1[w1==0,],y1[w1==0],honesty=F)
m0hat[-index_s1] = predict(rf,newdata=x2)$predictions
rf = regression_forest(x1[w1==1,],y1[w1==1],honesty=F)
m1hat[-index_s1] = predict(rf,newdata=x2)$predictions
# Model in S2, predict in S1
rf = regression_forest(x2,w2,honesty=F)
ehat[index_s1] = predict(rf,newdata=x1)$predictions
rf = regression_forest(x2[w2==0,],y2[w2==0],honesty=F)
m0hat[index_s1] = predict(rf,newdata=x1)$predictions
rf = regression_forest(x2[w2==1,],y2[w2==1],honesty=F)
m1hat[index_s1] = predict(rf,newdata=x1)$predictions
# Generate pseudo-outcome and take and test mean
pseudo_y = m1hat - m0hat +
w*(y-m1hat) / ehat - (1-w)*(y-m0hat) / (1-ehat)
summary(lm(pseudo_y ~ 1))
Call:
lm(formula = pseudo_y ~ 1)
Residuals:
Min 1Q Median 3Q Max
-28.3108 -0.6695 0.2376 1.4207 9.9140
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 0.01853 0.22297 0.083 0.934
Residual standard error: 3.153 on 199 degrees of freedom
AIPW with 5-fold cross-fitting
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 now, we focus on the 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(honesty=F))
# Run and
aipw = DML_aipw(y,w,x,ml_w=list(forest),ml_y=list(forest),cf=5)
summary(aipw$APO)
APO SE
0 0.01579749 0.1498814
1 0.13913183 0.1668602
We observe two things:
The estimator with 5-fold cross-fitting comes closest to the true
value
However, without cross-fitting is also close, but with a much
much smaller standard error.
Let’s see whether the former is only by chance or systematic, and
especially whether the latter is too good to be true.
Simulation study homogeneous effect setting
We run a simulation study drawing \(M=1,000\) samples from the DGP described
above and estimate the effect with three different estimators:
Partially linear model estimated with 5-fold
cross-fitting
AIPW without cross-fitting
AIPW with 5-fold cross-fitting
Additionally to bias, variance and MSE, we also check the quality of
the standard errors via the coverage rate. The coverage rate checks how
often the true value is included in the confidence intervals (see ring
toss analogy as an intuitive refresher).
We would like to have nominal coverage, i.e. for a 95% confidence
level it should happen in 95% of the replications, for a 90% confidence
level in 90% of the replications, …
# set number of replications
n_rep = 1000 # Decrease for faster computation
# initialize storage for results
coverage = results = matrix(NA,n_rep,3)
colnames(coverage) = colnames(results) = c("PL cf5","AIPW no","AIPW cf5")
# start the simulation
for (i in 1:n_rep) {
x = matrix(runif(n*p,-pi,pi),ncol=p)
w = rbinom(n,1,e(x[,1]))
y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)
# partially linear model
pl = DML_partial_linear(y,w,x,ml_w=list(forest),ml_y=list(forest),cf=5)
results[i,1] = pl$result[1]
coverage[i,1] = (pl$result[1] - 1.96*pl$result[2] < theta & pl$result[1] + 1.96*pl$result[2] > theta)
# No cross-fitting
rf = regression_forest(x,w,honesty=F)
ehat = predict(rf,newdata=x)$predictions
rf = regression_forest(x[w==0,],y[w==0],honesty=F)
m0hat = predict(rf,newdata=x)$predictions
rf = regression_forest(x[w==1,],y[w==1],honesty=F)
m1hat = predict(rf,newdata=x)$predictions
pseudo_y = m1hat - m0hat +
w*(y-m1hat) / ehat - (1-w)*(y-m0hat) / (1-ehat)
results[i,2] = mean(pseudo_y)
tt = t.test(pseudo_y)
coverage[i,2] = (tt$conf.int[1] < theta & tt$conf.int[2] > theta)
# 5-fold cross-fitting with causalDML package reusing the folds and pscores of PL
aipw = DML_aipw(y,w,x,ml_y=list(forest),cf=5,
e_mat = cbind(1-pl$e_hat,pl$e_hat),cf_mat = pl$cf_mat)
results[i,3] = aipw$ATE$results[1]
coverage[i,3] = (aipw$ATE$results[1] - 1.96*aipw$ATE$results[2] < theta & aipw$ATE$results[1] + 1.96*aipw$ATE$results[2] > theta)
}
We plot the estimator distributions and note that the estimator
without cross-fitting seems to be biased:
as.data.frame(results) %>% pivot_longer(cols=everything(),names_to = "Estimator",values_to = "coef") %>%
ggplot(aes(x = coef, fill = Estimator)) + geom_density(alpha=0.5) + theme_bw() + geom_vline(xintercept=theta)
This is confirmed by the decomposition of the MSE (see formula in SNB_Partially_linear
notebook):
data.frame(method = colnames(results),
bias2 = colMeans(results-theta)^2,
var = colMeans(sweep(results,2,colMeans(results))^2)) %>%
pivot_longer(-method,names_to = "Component",values_to = "MSE") %>%
ggplot(aes(fill=factor(Component,levels=c("var","bias2")), y=MSE, x=method)) +
geom_bar(position="stack", stat="identity") + scale_fill_discrete(name = "Component")
Notably the variance of the partially linear estimator is smaller
compared to cross-fitted AIPW, while both are basically unbiased. This
makes sense because we looked at the case with actual effect
homogeneity, where the partially linear estimator is an efficient
estimator in case of homoscedastic errors, which we impose.
Finally, let’s check the coverage rate:
data.frame(method = colnames(results),
coverage = colMeans(coverage)) %>%
ggplot(aes(y=coverage, x=method)) + geom_hline(yintercept=0.95,linetype="dashed") +
geom_point(size=5,shape=4) + scale_fill_discrete(name = "Component") + ylim(c(0,1)) +
geom_hline(yintercept=c(0,1))
Without cross-fitting, the coverage rate of AIPW is only 50%, which
reflects the bias and that the estimated standard errors are too small.
The other two slightly undercover, but especially cross-fitted AIPW
works well in terms of inference.
Effect heterogeneity with balanced treatment shares
DGP
Now we introduce heterogeneous treatment effects leaving the rest
unchanged:
\(p=10\) independent covariates
\(X_1,...,X_k,...,X_{10}\) drawn from a
uniform distribution: \(X_k \sim
uniform(-\pi,\pi)\)
The treatment model is \(W \sim
Bernoulli(\underbrace{\Phi(sin(X_1))}_{e(X)})\), where \(\Phi(\cdot)\) is the standard normal
cumulative density function
The outcome model of the treated is \(Y(1) = \underbrace{sin(X_1)}_{m_1(X)}+
\varepsilon\), with \(\varepsilon \sim
N(0,1)\)
The outcome model of the controls is \(Y(0) = \underbrace{cos(X_1+1/2\pi)}_{m_0(X)}+
\varepsilon\), with \(\varepsilon \sim
N(0,1)\)
This means that the ATE is equal to zero (\(\tau_{ATE}=0\)) but we have tremendous
effect heterogeneity:
x = matrix(runif(n*p,-pi,pi),ncol=p)
e = function(x){pnorm(sin(x))}
m1 = function(x){sin(x)}
m0 = function(x){cos(x+1/2*pi)}
tau = function(x){m1(x) - m0(x)}
w = rbinom(n,1,e(x[,1]))
y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)
g1 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=e,size=1) + ylab("e") + xlab("X1")
g2 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,aes(colour="Y1")) +
stat_function(fun=m0,size=1,aes(colour="Y0")) + ylab("Y") + xlab("X1")
g3 = data.frame(x = c(-pi, pi)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab(expression(tau)) + xlab("X1")
g1 / g2 / g3
Simulation study heterogeneous effect setting
We run a simulation study drawing \(M=1,000\) samples from the DGP described
above and estimate the effect with three different estimators:
Partially linear model estimated with 5-fold
cross-fitting
AIPW without cross-fitting
AIPW with 5-fold cross-fitting
# initialize storage for results
coverage_het = results_het = matrix(NA,n_rep,3)
colnames(coverage_het) = colnames(results_het) = c("PL cf5","AIPW no","AIPW cf5")
# start the simulation
for (i in 1:n_rep) {
x = matrix(runif(n*p,-pi,pi),ncol=p)
w = rbinom(n,1,e(x[,1]))
y = w*m1(x[,1]) + (1-w)*m0(x[,1]) + rnorm(n,0,1)
# partially linear model
pl = DML_partial_linear(y,w,x,ml_w=list(forest),ml_y=list(forest),cf=5)
results_het[i,1] = pl$result[1]
coverage_het[i,1] = (pl$result[1] - 1.96*pl$result[2] < 0 & pl$result[1] + 1.96*pl$result[2] > 0)
# No cross-fitting
rf = regression_forest(x,w,honesty=F)
ehat = predict(rf,newdata=x)$predictions
rf = regression_forest(x[w==0,],y[w==0],honesty=F)
m0hat = predict(rf,newdata=x)$predictions
rf = regression_forest(x[w==1,],y[w==1],honesty=F)
m1hat = predict(rf,newdata=x)$predictions
pseudo_y = m1hat - m0hat +
w*(y-m1hat) / ehat - (1-w)*(y-m0hat) / (1-ehat)
results_het[i,2] = mean(pseudo_y)
tt = t.test(pseudo_y)
coverage_het[i,2] = (tt$conf.int[1] < 0 & tt$conf.int[2] > 0)
aipw = DML_aipw(y,w,x,ml_y=list(forest),cf=5,
e_mat = cbind(1-pl$e_hat,pl$e_hat),cf_mat = pl$cf_mat)
results_het[i,3] = aipw$ATE$results[1]
coverage_het[i,3] = (aipw$ATE$results[1] - 1.96*aipw$ATE$results[2] < 0 & aipw$ATE$results[1] + 1.96*aipw$ATE$results[2] > 0)
}
We plot the estimator distributions and note that basically all
estimators are unbiased:
as.data.frame(results_het) %>% pivot_longer(cols=everything(),names_to = "Estimator",values_to = "coef") %>%
ggplot(aes(x = coef, fill = Estimator)) + geom_density(alpha=0.5) + theme_bw() + geom_vline(xintercept=0)
This is confirmed by the decomposition of the MSE:
data.frame(method = colnames(results_het),
bias2 = colMeans(results_het-0)^2,
var = colMeans(sweep(results_het,2,colMeans(results_het))^2)) %>%
pivot_longer(-method,names_to = "Component",values_to = "MSE") %>%
ggplot(aes(fill=factor(Component,levels=c("var","bias2")), y=MSE, x=method)) +
geom_bar(position="stack", stat="identity") + scale_fill_discrete(name = "Component")
Notably the partially linear estimator is unbiased although it
assumes effect heterogeneity. However, it shows a higher variance than
the AIPW estimator. This is not unexpected because AIPW is an efficient
estimator in the heterogeneous effects setting. But cross-fitting seems
to be harmful as we have no bias and lower variance without all this
additional effort.
BUT, let’s check the coverage rate:
data.frame(method = colnames(results_het),
coverage = colMeans(coverage_het)) %>%
ggplot(aes(y=coverage, x=method)) + geom_hline(yintercept=0.95,linetype="dashed") +
geom_point(size=5,shape=4) + scale_fill_discrete(name = "Component") + ylim(c(0,1)) +
geom_hline(yintercept=c(0,1))
Cross-fitted AIPW shows nearly perfect coverage, while the standard
errors without cross-fitting are much too small.
\(\Rightarrow\) Cross-fitting is not
necessarily required to remove bias in the point estimates due to
overfitting, but to remove downward bias in the standard errors. The
true ATE is zero in our case, but we would find significant effects in
about 20% of the cases instead of the 5% that we allow to happen given
our confidence level.
LS0tDQp0aXRsZTogIkNhdXNhbCBNTDogQUlQVyBEb3VibGUgTUwgKEFURSkiDQpzdWJ0aXRsZTogIlNpbXVsYXRpb24gbm90ZWJvb2siDQphdXRob3I6ICJNaWNoYWVsIEtuYXVzIg0KZGF0ZTogImByIGZvcm1hdChTeXMudGltZSgpLCAnJW0vJXknKWAiDQpvdXRwdXQ6IA0KICBodG1sX25vdGVib29rOg0KICAgIHRvYzogdHJ1ZQ0KICAgIHRvY19mbG9hdDogdHJ1ZQ0KICAgIGNvZGVfZm9sZGluZzogc2hvdw0KLS0tDQoNCg0KR29hbHM6DQoNCi0gSGFuZGNvZGUgQUlQVyBEb3VibGUgTUwgZm9yIEFURQ0KDQotIENvbXBhcmUgcGFydGlhbGx5IGxpbmVhciBhbmQgQUlQVyBEb3VibGUgTUwgZm9yIEFURQ0KDQotIFNlZSBob3cgcGFydGlhbGx5IGxpbmVhciBtb2RlbCBjYW4gZ28gd3JvbmcgaWYgZWZmZWN0cyBhcmUgYWN0dWFsbHkgaGV0ZXJvZ2VuZW91cw0KDQo8YnI+DQoNCg0KIyBFZmZlY3QgaG9tb2dlbmVpdHkNCg0KIyMgREdQDQoNCkNvbnNpZGVyIHRoZSBmb2xsb3dpbmcgREdQIHdpdGggaG9tb2dlbmVvdXMgZWZmZWN0cyBhbmQgYSBiaW5hcnkgdHJlYXRtZW50Og0KDQotICRwPTUkIGluZGVwZW5kZW50IGNvdmFyaWF0ZXMgJFhfMSwuLi4sWF9rLC4uLixYX3s1fSQgZHJhd24gZnJvbSBhIHVuaWZvcm0gZGlzdHJpYnV0aW9uOiAkWF9rIFxzaW0gdW5pZm9ybSgtXHBpLFxwaSkkDQoNCi0gVGhlIHRyZWF0bWVudCBtb2RlbCBpcyAkVyBcc2ltIEJlcm5vdWxsaShcdW5kZXJicmFjZXtcUGhpKHNpbihYXzEpKX1fe2UoWCl9KSQsIHdoZXJlICRcUGhpKFxjZG90KSQgaXMgdGhlIHN0YW5kYXJkIG5vcm1hbCBjdW11bGF0aXZlIGRlbnNpdHkgZnVuY3Rpb24NCg0KLSBUaGUgb3V0Y29tZSBtb2RlbCBpcyAkWSA9IFx1bmRlcmJyYWNlezAuMX1fe1x0YXV9IFcgKyBcdW5kZXJicmFjZXtzaW4oWF8xKX1fe20oWCl9KyBcdmFyZXBzaWxvbiQsIHdpdGggJFx2YXJlcHNpbG9uIFxzaW0gTigwLDEpJA0KDQpUaGlzIG1lYW5zIHRoYXQgd2UgYXJlIGluIGEgaGlnaGx5IG5vbmxpbmVhciBzZXR0aW5nLCBidXQgb25seSBvbmUgdmFyaWFibGUgKCRYXzEkKSBpcyByZWxldmFudCBhbmQgdGhlIG90aGVycyBhcmUganVzdCBub2lzZS4gVGhlIHRyZWF0bWVudCBtb2RlbCBwcm9kdWNlcyBpbiBleHBlY3RhdGlvbiBhIGJhbGFuY2VkIHRyZWF0bWVudCBzaGFyZSB3aXRoIDUwJSBjb250cm9scyBhbmQgNTAlIHRyZWF0ZWQuDQoNCg0KYGBge3IsIHdhcm5pbmcgPSBGLCBtZXNzYWdlID0gRn0NCmlmICghcmVxdWlyZSgiZ3JmIikpIGluc3RhbGwucGFja2FnZXMoImdyZiIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KGdyZikNCmlmICghcmVxdWlyZSgidGlkeXZlcnNlIikpIGluc3RhbGwucGFja2FnZXMoInRpZHl2ZXJzZSIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KHRpZHl2ZXJzZSkNCmlmICghcmVxdWlyZSgicGF0Y2h3b3JrIikpIGluc3RhbGwucGFja2FnZXMoInBhdGNod29yayIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KHBhdGNod29yaykNCmlmICghcmVxdWlyZSgiY2F1c2FsRE1MIikpIHsNCiAgaWYgKCFyZXF1aXJlKCJkZXZ0b29scyIpKSBpbnN0YWxsLnBhY2thZ2VzKCJkZXZ0b29scyIsIGRlcGVuZGVuY2llcyA9IFRSVUUpOyBsaWJyYXJ5KGRldnRvb2xzKQ0KICBpbnN0YWxsX2dpdGh1YihyZXBvPSJNQ0tuYXVzL2NhdXNhbERNTCIpIA0KfTsgbGlicmFyeShjYXVzYWxETUwpDQoNCnNldC5zZWVkKDEyMzQpDQoNCiMgU2V0IHBhcmFtZXRlcnMNCm4gPSAyMDANCnAgPSAxMA0KdGhldGEgPSAwLjENCg0KIyBEZWZpbmUgYW5kIHBsb3QgZnVuY3Rpb25zDQp4ID0gbWF0cml4KHJ1bmlmKG4qcCwtcGkscGkpLG5jb2w9cCkNCmUgPSBmdW5jdGlvbih4KXtwbm9ybShzaW4oeCkpfQ0KbTAgPSBmdW5jdGlvbih4KXtzaW4oeCl9DQptMSA9IGZ1bmN0aW9uKHgpe20wKHgpICsgdGhldGF9DQp0YXUgPSBmdW5jdGlvbih4KXttMSh4KSAtIG0wKHgpfQ0KdyA9IHJiaW5vbShuLDEsZSh4WywxXSkpDQp5ID0gdyptMSh4WywxXSkgKyAoMS13KSptMCh4WywxXSkgKyBybm9ybShuLDAsMSkNCg0KZzEgPSBkYXRhLmZyYW1lKHggPSBjKC1waSwgcGkpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1lLHNpemU9MSkgKyB5bGFiKCJlIikgKyB4bGFiKCJYMSIpDQpnMiA9IGRhdGEuZnJhbWUoeCA9IGMoLXBpLCBwaSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPW0xLHNpemU9MSxhZXMoY29sb3VyPSJZMSIpKSArIA0KICBzdGF0X2Z1bmN0aW9uKGZ1bj1tMCxzaXplPTEsYWVzKGNvbG91cj0iWTAiKSkgKyB5bGFiKCJZIikgKyB4bGFiKCJYMSIpDQpnMyA9IGRhdGEuZnJhbWUoeCA9IGMoLXBpLCBwaSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPXRhdSxzaXplPTEpICsgeWxhYihleHByZXNzaW9uKHRhdSkpICsgeGxhYigiWDEiKQ0KZzEgLyBnMiAvIGczDQpgYGANCg0KPGJyPiANCg0KIyMgSGFuZC1jb2RlZCBBSVBXIHcvbyBjcm9zcy1maXR0aW5nDQoNCldlIGRyYXcgYSBzYW1wbGUgb2YgJE49MjAwJCBhbmQgZXN0aW1hdGUgdGhlIG51aXNhbmNlIHBhcmFtZXRlcnMgJGUoWCk9RVtXfFhdJCwgJG0oMCxYKT1FW1l8Vz0wLFhdJCBhbmQgJG0oMSxYKT1FW1l8Vz0xLFhdJCB1c2luZyByYW5kb20gZm9yZXN0IHdpdGhvdXQgaG9uZXN0eSAoc2FtcGxlIHNpemUgdG9vIHNtYWxsIGZvciBob25lc3R5KSBhbmQgcGx1ZyB0aGUgcHJlZGljdGlvbnMgaW50byB0aGUgcHNldWRvIG91dGNvbWU6DQokJFx0aWxkZXtZfV97QVRFfSA9IFx1bmRlcmJyYWNle1xoYXR7bX0oMSxYKSAtIFxoYXR7bX0oMCxYKX1fe1x0ZXh0e291dGNvbWUgcHJlZGljdGlvbnN9fSArIFx1bmRlcmJyYWNle1xmcmFje1cgKFkgLSBcaGF0e219KDEsWCkpfXtcaGF0e2V9KFgpfSAtIFxmcmFjeygxLVcpIChZIC0gXGhhdHttfSgwLFgpKX17MS1caGF0e2V9KFgpfX1fe1x0ZXh0e3dlaWdodGVkIHJlc2lkdWFsc319JCQNCg0KYGBge3J9DQojIE5vIGNyb3NzLWZpdHRpbmcNCiMgUHJlZGljdCBwcm9wZW5zaXR5IHNjb3JlDQpyZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHgsdyxob25lc3R5PUYpDQplaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQojIE1vZGVsIGNvbnRyb2wgb3V0Y29tZSB1c2luZyBvbmx5IGNvbnRyb2wgYW5kIHByZWRpY3QgZm9yIGFsbA0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4W3c9PTAsXSx5W3c9PTBdLGhvbmVzdHk9RikNCm0waGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQojIE1vZGVsIGNvbnRyb2wgb3V0Y29tZSB1c2luZyBvbmx5IGNvbnRyb2wgYW5kIHByZWRpY3QgZm9yIGFsbA0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4W3c9PTEsXSx5W3c9PTFdLGhvbmVzdHk9RikNCm0xaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQojIEdlbmVyYXRlIHBzZXVkby1vdXRjb21lDQpwc2V1ZG9feSA9ICBtMWhhdCAtIG0waGF0ICsNCiAgICAgICAgICAgIHcqKHktbTFoYXQpIC8gZWhhdCAtICgxLXcpKih5LW0waGF0KSAvICgxLWVoYXQpDQpgYGANCg0KVGFrZSB0aGUgbWVhbiBvZiB0aGUgcHNldWRvLW91dGNvbWUgYW5kIHJ1biBhIHQtdGVzdA0KDQpgYGB7cn0NCm1lYW4ocHNldWRvX3kpDQp0LnRlc3QocHNldWRvX3kpDQpgYGANCg0Kb3IgcnVuIGp1c3QgYW4gT0xTIHJlZ3Jlc3Npb24gd2l0aCBvbmx5IGEgY29uc3RhbnQgZm9yIHBvaW50IGVzdGltYXRpb24gYW5kIGluZmVyZW5jZSBpbiBvbmUgc3RlcC4NCg0KYGBge3J9DQpzdW1tYXJ5KGxtKHBzZXVkb195fjEpKQ0KYGBgDQoNCg0KPGJyPg0KDQojIyBIYW5kLWNvZGVkIEFJUFcgd2l0aCAyLWZvbGQgY3Jvc3MtZml0dGluZw0KDQpUaGUgdGhlb3JldGljYWwgcmVzdWx0cyByZXF1aXJlIHRoYXQgd2UgcHJlZGljdCB0aGUgbnVpc2FuY2UgcGFyYW1ldGVycyBvdXQtb2Ytc2FtcGxlLiBUaGUgZWFzaWVzdCB3YXkgdG8gZG8gdGhpcyBpcyB0d28tZm9sZCBjcm9zcy1maXR0aW5nOg0KDQotIFNwbGl0IHRoZSBzYW1wbGUgaW4gdHdvIHJhbmRvbSBzdWJzYW1wbGVzLCBTMSBhbmQgUzINCg0KLSBGb3JtIHByZWRpY3Rpb24gbW9kZWxzIGluIFMxLCB1c2UgaXQgdG8gcHJlZGljdCBpbiBTMg0KDQotIEZvcm0gcHJlZGljdGlvbiBtb2RlbHMgaW4gUzIsIHVzZSBpdCB0byBwcmVkaWN0IGluIFMxDQoNCi0gUGx1ZyB0aGUgcHJlZGljdGlvbiBpbiB0aGUgcHNldWRvLW91dGNvbWUgYW5kIHByb2NlZWQgYXMgYWJvdmUNCg0KDQpgYGB7cn0NCiMgMi1mb2xkIGNyb3NzLWZpdHRpbmcNCm0waGF0ID0gbTFoYXQgPSBlaGF0ID0gcmVwKE5BLG4pDQojIERyYXcgcmFuZG9tIGluZGljZXMgZm9yIHNhbXBsZSAxDQppbmRleF9zMSA9IHNhbXBsZSgxOm4sbi8yKQ0KIyBDcmVhdGUgUzENCngxID0geFtpbmRleF9zMSxdDQp3MSA9IHdbaW5kZXhfczFdDQp5MSA9IHlbaW5kZXhfczFdDQojIENyZWF0ZSBzYW1wbGUgMiB3aXRoIHRob3NlIG5vdCBpbiBTMQ0KeDIgPSB4Wy1pbmRleF9zMSxdDQp3MiA9IHdbLWluZGV4X3MxXQ0KeTIgPSB5Wy1pbmRleF9zMV0NCiMgTW9kZWwgaW4gUzEsIHByZWRpY3QgaW4gUzINCnJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeDEsdzEsaG9uZXN0eT1GKQ0KZWhhdFstaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgyKSRwcmVkaWN0aW9ucw0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4MVt3MT09MCxdLHkxW3cxPT0wXSxob25lc3R5PUYpDQptMGhhdFstaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgyKSRwcmVkaWN0aW9ucw0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4MVt3MT09MSxdLHkxW3cxPT0xXSxob25lc3R5PUYpDQptMWhhdFstaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgyKSRwcmVkaWN0aW9ucw0KIyBNb2RlbCBpbiBTMiwgcHJlZGljdCBpbiBTMQ0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4Mix3Mixob25lc3R5PUYpDQplaGF0W2luZGV4X3MxXSA9IHByZWRpY3QocmYsbmV3ZGF0YT14MSkkcHJlZGljdGlvbnMNCnJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeDJbdzI9PTAsXSx5Mlt3Mj09MF0saG9uZXN0eT1GKQ0KbTBoYXRbaW5kZXhfczFdID0gcHJlZGljdChyZixuZXdkYXRhPXgxKSRwcmVkaWN0aW9ucw0KcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4Mlt3Mj09MSxdLHkyW3cyPT0xXSxob25lc3R5PUYpDQptMWhhdFtpbmRleF9zMV0gPSBwcmVkaWN0KHJmLG5ld2RhdGE9eDEpJHByZWRpY3Rpb25zDQojIEdlbmVyYXRlIHBzZXVkby1vdXRjb21lIGFuZCB0YWtlIGFuZCB0ZXN0IG1lYW4NCnBzZXVkb195ID0gIG0xaGF0IC0gbTBoYXQgKw0KICB3Kih5LW0xaGF0KSAvIGVoYXQgLSAoMS13KSooeS1tMGhhdCkgLyAoMS1laGF0KQ0Kc3VtbWFyeShsbShwc2V1ZG9feSB+IDEpKQ0KYGBgDQoNCjxicj4NCg0KDQojIyBBSVBXIHdpdGggNS1mb2xkIGNyb3NzLWZpdHRpbmcNCg0KMi1mb2xkIGNyb3NzLWZpdHRpbmcgaXMgZWFzeSB0byBpbXBsZW1lbnQgYnV0IGVzcGVjaWFsbHkgaW4gc21hbGwgc2FtcGxlIHNpemVzIHVzaW5nIG9ubHkgNTAlIG9mIHRoZSBkYXRhIHRvIGVzdGltYXRlIHRoZSBudWlzYW5jZSBwYXJhbWV0ZXJzIG1pZ2h0IGxlYWQgdG8gdW5zdGFibGUgcHJlZGljdGlvbnMuDQoNClRodXMsIHdlIHVzZSB0aGUgYERNTF9haXB3YCBmdW5jdGlvbiBvZiB0aGUgYGNhdXNhbERNTGAgcGFja2FnZSB0byBydW4gNS1mb2xkIGNyb3NzLWZpdHRpbmcuIFRoaXMgcGFja2FnZSByZXF1aXJlcyB0byBjcmVhdGUgdGhlIG1ldGhvZHMgdGhhdCB3ZSB1c2UgYmVjYXVzZSBpdCBhbGxvd3MgZm9yIGVuc2VtYmxlIG1ldGhvZHMuIEZvciBub3csIHdlIGZvY3VzIG9uIHRoZSBob25lc3QgcmFuZG9tIGZvcmVzdC4NCg0KV2l0aCA1LWZvbGQgY3Jvc3MtZml0dGluZywgd2Ugc3BsaXQgdGhlIHNhbXBsZSBpbiA1IGZvbGRzIGFuZCB1c2UgNCBmb2xkcyAoODAlIG9mIHRoZSBkYXRhKSB0byBwcmVkaWN0IHRoZSBsZWZ0IG91dCBmb2xkICgyMCUgb2YgdGhlIGRhdGEpLiBXZSBpdGVyYXRlIHN1Y2ggdGhhdCBldmVyeSBmb2xkIGlzIGxlZnQgb3V0IG9uY2UuDQoNCg0KYGBge3J9DQojIDUtZm9sZCBjcm9zcy1maXR0aW5nIHdpdGggY2F1c2FsRE1MIHBhY2thZ2UNCiMgQ3JlYXRlIGxlYXJuZXINCmZvcmVzdCA9IGNyZWF0ZV9tZXRob2QoImZvcmVzdF9ncmYiLGFyZ3M9bGlzdChob25lc3R5PUYpKQ0KIyBSdW4gYW5kIA0KYWlwdyA9IERNTF9haXB3KHksdyx4LG1sX3c9bGlzdChmb3Jlc3QpLG1sX3k9bGlzdChmb3Jlc3QpLGNmPTUpDQpzdW1tYXJ5KGFpcHckQVBPKQ0KcGxvdChhaXB3JEFQTykNCnN1bW1hcnkoYWlwdyRBVEUpDQpgYGANCg0KV2Ugb2JzZXJ2ZSB0d28gdGhpbmdzOg0KDQotIFRoZSBlc3RpbWF0b3Igd2l0aCA1LWZvbGQgY3Jvc3MtZml0dGluZyBjb21lcyBjbG9zZXN0IHRvIHRoZSB0cnVlIHZhbHVlDQoNCi0gSG93ZXZlciwgd2l0aG91dCBjcm9zcy1maXR0aW5nIGlzIGFsc28gY2xvc2UsIGJ1dCB3aXRoIGEgbXVjaCBtdWNoIHNtYWxsZXIgc3RhbmRhcmQgZXJyb3IuDQoNCkxldCdzIHNlZSB3aGV0aGVyIHRoZSBmb3JtZXIgaXMgb25seSBieSBjaGFuY2Ugb3Igc3lzdGVtYXRpYywgYW5kIGVzcGVjaWFsbHkgd2hldGhlciB0aGUgbGF0dGVyIGlzIHRvbyBnb29kIHRvIGJlIHRydWUuDQoNCjxicj4NCg0KDQojIyBTaW11bGF0aW9uIHN0dWR5IGhvbW9nZW5lb3VzIGVmZmVjdCBzZXR0aW5nDQoNCldlIHJ1biBhIHNpbXVsYXRpb24gc3R1ZHkgZHJhd2luZyAkTT0xLDAwMCQgc2FtcGxlcyBmcm9tIHRoZSBER1AgZGVzY3JpYmVkIGFib3ZlIGFuZCBlc3RpbWF0ZSB0aGUgZWZmZWN0IHdpdGggdGhyZWUgZGlmZmVyZW50IGVzdGltYXRvcnM6DQoNCi0gUGFydGlhbGx5IGxpbmVhciBtb2RlbCBlc3RpbWF0ZWQgd2l0aCA1LWZvbGQgY3Jvc3MtZml0dGluZw0KDQotIEFJUFcgd2l0aG91dCBjcm9zcy1maXR0aW5nDQoNCi0gQUlQVyB3aXRoIDUtZm9sZCBjcm9zcy1maXR0aW5nDQoNCkFkZGl0aW9uYWxseSB0byBiaWFzLCB2YXJpYW5jZSBhbmQgTVNFLCB3ZSBhbHNvIGNoZWNrIHRoZSBxdWFsaXR5IG9mIHRoZSBzdGFuZGFyZCBlcnJvcnMgdmlhIHRoZSBjb3ZlcmFnZSByYXRlLiBUaGUgY292ZXJhZ2UgcmF0ZSBjaGVja3MgaG93IG9mdGVuIHRoZSB0cnVlIHZhbHVlIGlzIGluY2x1ZGVkIGluIHRoZSBjb25maWRlbmNlIGludGVydmFscyAoc2VlIFtyaW5nIHRvc3MgYW5hbG9neV0oaHR0cHM6Ly9tZWRpdW0uY29tL0BFcGlFbGxpZS9oYXZpbmctY29uZmlkZW5jZS1pbi1jb25maWRlbmNlLWludGVydmFscy04Zjg4MTcxMmQ4MzcpIGFzIGFuIGludHVpdGl2ZSByZWZyZXNoZXIpLiANCg0KV2Ugd291bGQgbGlrZSB0byBoYXZlIG5vbWluYWwgY292ZXJhZ2UsIGkuZS4gZm9yIGEgOTUlIGNvbmZpZGVuY2UgbGV2ZWwgaXQgc2hvdWxkIGhhcHBlbiBpbiA5NSUgb2YgdGhlIHJlcGxpY2F0aW9ucywgZm9yIGEgOTAlIGNvbmZpZGVuY2UgbGV2ZWwgaW4gOTAlIG9mIHRoZSByZXBsaWNhdGlvbnMsIC4uLg0KDQoNCmBgYHtyfQ0KIyBzZXQgbnVtYmVyIG9mIHJlcGxpY2F0aW9ucw0Kbl9yZXAgPSAxMDAwICMgRGVjcmVhc2UgZm9yIGZhc3RlciBjb21wdXRhdGlvbg0KIyBpbml0aWFsaXplIHN0b3JhZ2UgZm9yIHJlc3VsdHMNCmNvdmVyYWdlID0gcmVzdWx0cyA9IG1hdHJpeChOQSxuX3JlcCwzKQ0KY29sbmFtZXMoY292ZXJhZ2UpID0gY29sbmFtZXMocmVzdWx0cykgPSBjKCJQTCBjZjUiLCJBSVBXIG5vIiwiQUlQVyBjZjUiKQ0KDQojIHN0YXJ0IHRoZSBzaW11bGF0aW9uDQpmb3IgKGkgaW4gMTpuX3JlcCkgew0KICB4ID0gbWF0cml4KHJ1bmlmKG4qcCwtcGkscGkpLG5jb2w9cCkNCiAgdyA9IHJiaW5vbShuLDEsZSh4WywxXSkpDQogIHkgPSB3Km0xKHhbLDFdKSArICgxLXcpKm0wKHhbLDFdKSArIHJub3JtKG4sMCwxKQ0KICANCiAgIyBwYXJ0aWFsbHkgbGluZWFyIG1vZGVsDQogIHBsID0gRE1MX3BhcnRpYWxfbGluZWFyKHksdyx4LG1sX3c9bGlzdChmb3Jlc3QpLG1sX3k9bGlzdChmb3Jlc3QpLGNmPTUpDQogIHJlc3VsdHNbaSwxXSA9IHBsJHJlc3VsdFsxXQ0KICBjb3ZlcmFnZVtpLDFdID0gKHBsJHJlc3VsdFsxXSAtIDEuOTYqcGwkcmVzdWx0WzJdIDwgdGhldGEgJiBwbCRyZXN1bHRbMV0gKyAxLjk2KnBsJHJlc3VsdFsyXSA+IHRoZXRhKQ0KICANCiAgIyBObyBjcm9zcy1maXR0aW5nDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeCx3LGhvbmVzdHk9RikNCiAgZWhhdCA9IHByZWRpY3QocmYsbmV3ZGF0YT14KSRwcmVkaWN0aW9ucw0KICByZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHhbdz09MCxdLHlbdz09MF0saG9uZXN0eT1GKQ0KICBtMGhhdCA9IHByZWRpY3QocmYsbmV3ZGF0YT14KSRwcmVkaWN0aW9ucw0KICByZiA9IHJlZ3Jlc3Npb25fZm9yZXN0KHhbdz09MSxdLHlbdz09MV0saG9uZXN0eT1GKQ0KICBtMWhhdCA9IHByZWRpY3QocmYsbmV3ZGF0YT14KSRwcmVkaWN0aW9ucw0KICBwc2V1ZG9feSA9ICBtMWhhdCAtIG0waGF0ICsNCiAgICB3Kih5LW0xaGF0KSAvIGVoYXQgLSAoMS13KSooeS1tMGhhdCkgLyAoMS1laGF0KQ0KICByZXN1bHRzW2ksMl0gPSBtZWFuKHBzZXVkb195KQ0KICB0dCA9IHQudGVzdChwc2V1ZG9feSkNCiAgY292ZXJhZ2VbaSwyXSA9ICh0dCRjb25mLmludFsxXSAgPCB0aGV0YSAmIHR0JGNvbmYuaW50WzJdID4gdGhldGEpDQoNCiAgIyA1LWZvbGQgY3Jvc3MtZml0dGluZyB3aXRoIGNhdXNhbERNTCBwYWNrYWdlIHJldXNpbmcgdGhlIGZvbGRzIGFuZCBwc2NvcmVzIG9mIFBMDQogIGFpcHcgPSBETUxfYWlwdyh5LHcseCxtbF95PWxpc3QoZm9yZXN0KSxjZj01LA0KICAgICAgICAgICAgICAgICAgZV9tYXQgPSBjYmluZCgxLXBsJGVfaGF0LHBsJGVfaGF0KSxjZl9tYXQgPSBwbCRjZl9tYXQpDQogIHJlc3VsdHNbaSwzXSA9IGFpcHckQVRFJHJlc3VsdHNbMV0NCiAgY292ZXJhZ2VbaSwzXSA9IChhaXB3JEFURSRyZXN1bHRzWzFdIC0gMS45NiphaXB3JEFURSRyZXN1bHRzWzJdIDwgdGhldGEgJiBhaXB3JEFURSRyZXN1bHRzWzFdICsgMS45NiphaXB3JEFURSRyZXN1bHRzWzJdID4gdGhldGEpDQp9DQpgYGANCg0KV2UgcGxvdCB0aGUgZXN0aW1hdG9yIGRpc3RyaWJ1dGlvbnMgYW5kIG5vdGUgdGhhdCB0aGUgZXN0aW1hdG9yIHdpdGhvdXQgY3Jvc3MtZml0dGluZyBzZWVtcyB0byBiZSBiaWFzZWQ6DQoNCg0KYGBge3J9DQphcy5kYXRhLmZyYW1lKHJlc3VsdHMpICU+JSBwaXZvdF9sb25nZXIoY29scz1ldmVyeXRoaW5nKCksbmFtZXNfdG8gPSAiRXN0aW1hdG9yIix2YWx1ZXNfdG8gPSAiY29lZiIpICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSBjb2VmLCBmaWxsID0gRXN0aW1hdG9yKSkgKyBnZW9tX2RlbnNpdHkoYWxwaGE9MC41KSArIHRoZW1lX2J3KCkgKyBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQ9dGhldGEpDQpgYGANCg0KVGhpcyBpcyBjb25maXJtZWQgYnkgdGhlIGRlY29tcG9zaXRpb24gb2YgdGhlIE1TRSAoc2VlIGZvcm11bGEgaW4gW1NOQl9QYXJ0aWFsbHlfbGluZWFyXShodHRwczovL21ja25hdXMuZ2l0aHViLmlvL2Fzc2V0cy9ub3RlYm9va3MvU05CL1NOQl9QYXJ0aWFsbHlfbGluZWFyLm5iLmh0bWwpIG5vdGVib29rKToNCg0KYGBge3J9DQpkYXRhLmZyYW1lKG1ldGhvZCA9IGNvbG5hbWVzKHJlc3VsdHMpLA0KICAgICAgICAgICBiaWFzMiA9IGNvbE1lYW5zKHJlc3VsdHMtdGhldGEpXjIsDQogICAgICAgICAgIHZhciA9IGNvbE1lYW5zKHN3ZWVwKHJlc3VsdHMsMixjb2xNZWFucyhyZXN1bHRzKSleMikpICU+JSANCiAgcGl2b3RfbG9uZ2VyKC1tZXRob2QsbmFtZXNfdG8gPSAiQ29tcG9uZW50Iix2YWx1ZXNfdG8gPSAiTVNFIikgJT4lDQogIGdncGxvdChhZXMoZmlsbD1mYWN0b3IoQ29tcG9uZW50LGxldmVscz1jKCJ2YXIiLCJiaWFzMiIpKSwgeT1NU0UsIHg9bWV0aG9kKSkgKyANCiAgZ2VvbV9iYXIocG9zaXRpb249InN0YWNrIiwgc3RhdD0iaWRlbnRpdHkiKSArIHNjYWxlX2ZpbGxfZGlzY3JldGUobmFtZSA9ICJDb21wb25lbnQiKQ0KYGBgDQoNCk5vdGFibHkgdGhlIHZhcmlhbmNlIG9mIHRoZSBwYXJ0aWFsbHkgbGluZWFyIGVzdGltYXRvciBpcyBzbWFsbGVyIGNvbXBhcmVkIHRvIGNyb3NzLWZpdHRlZCBBSVBXLCB3aGlsZSBib3RoIGFyZSBiYXNpY2FsbHkgdW5iaWFzZWQuIFRoaXMgbWFrZXMgc2Vuc2UgYmVjYXVzZSB3ZSBsb29rZWQgYXQgdGhlIGNhc2Ugd2l0aCBhY3R1YWwgZWZmZWN0IGhvbW9nZW5laXR5LCB3aGVyZSB0aGUgcGFydGlhbGx5IGxpbmVhciBlc3RpbWF0b3IgaXMgYW4gZWZmaWNpZW50IGVzdGltYXRvciBpbiBjYXNlIG9mIGhvbW9zY2VkYXN0aWMgZXJyb3JzLCB3aGljaCB3ZSBpbXBvc2UuDQoNCkZpbmFsbHksIGxldCdzIGNoZWNrIHRoZSBjb3ZlcmFnZSByYXRlOg0KDQpgYGB7cn0NCmRhdGEuZnJhbWUobWV0aG9kID0gY29sbmFtZXMocmVzdWx0cyksDQogICAgICAgICAgIGNvdmVyYWdlID0gY29sTWVhbnMoY292ZXJhZ2UpKSAlPiUgDQogIGdncGxvdChhZXMoeT1jb3ZlcmFnZSwgeD1tZXRob2QpKSArIGdlb21faGxpbmUoeWludGVyY2VwdD0wLjk1LGxpbmV0eXBlPSJkYXNoZWQiKSArIA0KICBnZW9tX3BvaW50KHNpemU9NSxzaGFwZT00KSArIHNjYWxlX2ZpbGxfZGlzY3JldGUobmFtZSA9ICJDb21wb25lbnQiKSArIHlsaW0oYygwLDEpKSArDQogIGdlb21faGxpbmUoeWludGVyY2VwdD1jKDAsMSkpDQpgYGANCg0KV2l0aG91dCBjcm9zcy1maXR0aW5nLCB0aGUgY292ZXJhZ2UgcmF0ZSBvZiBBSVBXIGlzIG9ubHkgNTAlLCB3aGljaCByZWZsZWN0cyB0aGUgYmlhcyBhbmQgdGhhdCB0aGUgZXN0aW1hdGVkIHN0YW5kYXJkIGVycm9ycyBhcmUgdG9vIHNtYWxsLiBUaGUgb3RoZXIgdHdvIHNsaWdodGx5IHVuZGVyY292ZXIsIGJ1dCBlc3BlY2lhbGx5IGNyb3NzLWZpdHRlZCBBSVBXIHdvcmtzIHdlbGwgaW4gdGVybXMgb2YgaW5mZXJlbmNlLg0KDQoNCjxicj4NCjxicj4NCg0KDQoNCiMgRWZmZWN0IGhldGVyb2dlbmVpdHkgd2l0aCBiYWxhbmNlZCB0cmVhdG1lbnQgc2hhcmVzDQoNCiMjIERHUA0KDQpOb3cgd2UgaW50cm9kdWNlIGhldGVyb2dlbmVvdXMgdHJlYXRtZW50IGVmZmVjdHMgbGVhdmluZyB0aGUgcmVzdCB1bmNoYW5nZWQ6DQoNCi0gJHA9MTAkIGluZGVwZW5kZW50IGNvdmFyaWF0ZXMgJFhfMSwuLi4sWF9rLC4uLixYX3sxMH0kIGRyYXduIGZyb20gYSB1bmlmb3JtIGRpc3RyaWJ1dGlvbjogJFhfayBcc2ltIHVuaWZvcm0oLVxwaSxccGkpJA0KDQotIFRoZSB0cmVhdG1lbnQgbW9kZWwgaXMgJFcgXHNpbSBCZXJub3VsbGkoXHVuZGVyYnJhY2V7XFBoaShzaW4oWF8xKSl9X3tlKFgpfSkkLCB3aGVyZSAkXFBoaShcY2RvdCkkIGlzIHRoZSBzdGFuZGFyZCBub3JtYWwgY3VtdWxhdGl2ZSBkZW5zaXR5IGZ1bmN0aW9uDQoNCi0gVGhlIG91dGNvbWUgbW9kZWwgb2YgdGhlIHRyZWF0ZWQgaXMgJFkoMSkgPSBcdW5kZXJicmFjZXtzaW4oWF8xKX1fe21fMShYKX0rIFx2YXJlcHNpbG9uJCwgd2l0aCAkXHZhcmVwc2lsb24gXHNpbSBOKDAsMSkkDQoNCi0gVGhlIG91dGNvbWUgbW9kZWwgb2YgdGhlIGNvbnRyb2xzIGlzICRZKDApID0gXHVuZGVyYnJhY2V7Y29zKFhfMSsxLzJccGkpfV97bV8wKFgpfSsgXHZhcmVwc2lsb24kLCB3aXRoICRcdmFyZXBzaWxvbiBcc2ltIE4oMCwxKSQNCg0KVGhpcyBtZWFucyB0aGF0IHRoZSBBVEUgaXMgZXF1YWwgdG8gemVybyAoJFx0YXVfe0FURX09MCQpIGJ1dCB3ZSBoYXZlIHRyZW1lbmRvdXMgZWZmZWN0IGhldGVyb2dlbmVpdHk6IA0KDQoNCmBgYHtyfQ0KeCA9IG1hdHJpeChydW5pZihuKnAsLXBpLHBpKSxuY29sPXApDQplID0gZnVuY3Rpb24oeCl7cG5vcm0oc2luKHgpKX0NCm0xID0gZnVuY3Rpb24oeCl7c2luKHgpfQ0KbTAgPSBmdW5jdGlvbih4KXtjb3MoeCsxLzIqcGkpfQ0KdGF1ID0gZnVuY3Rpb24oeCl7bTEoeCkgLSBtMCh4KX0NCncgPSByYmlub20obiwxLGUoeFssMV0pKQ0KeSA9IHcqbTEoeFssMV0pICsgKDEtdykqbTAoeFssMV0pICsgcm5vcm0obiwwLDEpDQoNCmcxID0gZGF0YS5mcmFtZSh4ID0gYygtcGksIHBpKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49ZSxzaXplPTEpICsgeWxhYigiZSIpICsgeGxhYigiWDEiKQ0KZzIgPSBkYXRhLmZyYW1lKHggPSBjKC1waSwgcGkpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1tMSxzaXplPTEsYWVzKGNvbG91cj0iWTEiKSkgKyANCiAgc3RhdF9mdW5jdGlvbihmdW49bTAsc2l6ZT0xLGFlcyhjb2xvdXI9IlkwIikpICsgeWxhYigiWSIpICsgeGxhYigiWDEiKQ0KZzMgPSBkYXRhLmZyYW1lKHggPSBjKC1waSwgcGkpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj10YXUsc2l6ZT0xKSArIHlsYWIoZXhwcmVzc2lvbih0YXUpKSArIHhsYWIoIlgxIikNCmcxIC8gZzIgLyBnMw0KYGBgDQoNCjxicj4NCg0KDQojIyBTaW11bGF0aW9uIHN0dWR5IGhldGVyb2dlbmVvdXMgZWZmZWN0IHNldHRpbmcNCg0KV2UgcnVuIGEgc2ltdWxhdGlvbiBzdHVkeSBkcmF3aW5nICRNPTEsMDAwJCBzYW1wbGVzIGZyb20gdGhlIERHUCBkZXNjcmliZWQgYWJvdmUgYW5kIGVzdGltYXRlIHRoZSBlZmZlY3Qgd2l0aCB0aHJlZSBkaWZmZXJlbnQgZXN0aW1hdG9yczoNCg0KLSBQYXJ0aWFsbHkgbGluZWFyIG1vZGVsIGVzdGltYXRlZCB3aXRoIDUtZm9sZCBjcm9zcy1maXR0aW5nDQoNCi0gQUlQVyB3aXRob3V0IGNyb3NzLWZpdHRpbmcNCg0KLSBBSVBXIHdpdGggNS1mb2xkIGNyb3NzLWZpdHRpbmcNCg0KDQpgYGB7cn0NCiMgaW5pdGlhbGl6ZSBzdG9yYWdlIGZvciByZXN1bHRzDQpjb3ZlcmFnZV9oZXQgPSByZXN1bHRzX2hldCA9IG1hdHJpeChOQSxuX3JlcCwzKQ0KY29sbmFtZXMoY292ZXJhZ2VfaGV0KSA9IGNvbG5hbWVzKHJlc3VsdHNfaGV0KSA9IGMoIlBMIGNmNSIsIkFJUFcgbm8iLCJBSVBXIGNmNSIpDQoNCiMgc3RhcnQgdGhlIHNpbXVsYXRpb24NCmZvciAoaSBpbiAxOm5fcmVwKSB7DQogIHggPSBtYXRyaXgocnVuaWYobipwLC1waSxwaSksbmNvbD1wKQ0KICB3ID0gcmJpbm9tKG4sMSxlKHhbLDFdKSkNCiAgeSA9IHcqbTEoeFssMV0pICsgKDEtdykqbTAoeFssMV0pICsgcm5vcm0obiwwLDEpDQogIA0KICAjIHBhcnRpYWxseSBsaW5lYXIgbW9kZWwNCiAgcGwgPSBETUxfcGFydGlhbF9saW5lYXIoeSx3LHgsbWxfdz1saXN0KGZvcmVzdCksbWxfeT1saXN0KGZvcmVzdCksY2Y9NSkNCiAgcmVzdWx0c19oZXRbaSwxXSA9IHBsJHJlc3VsdFsxXQ0KICBjb3ZlcmFnZV9oZXRbaSwxXSA9IChwbCRyZXN1bHRbMV0gLSAxLjk2KnBsJHJlc3VsdFsyXSA8IDAgJiBwbCRyZXN1bHRbMV0gKyAxLjk2KnBsJHJlc3VsdFsyXSA+IDApDQogIA0KICAjIE5vIGNyb3NzLWZpdHRpbmcNCiAgcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4LHcsaG9uZXN0eT1GKQ0KICBlaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeFt3PT0wLF0seVt3PT0wXSxob25lc3R5PUYpDQogIG0waGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeFt3PT0xLF0seVt3PT0xXSxob25lc3R5PUYpDQogIG0xaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHBzZXVkb195ID0gIG0xaGF0IC0gbTBoYXQgKw0KICAgIHcqKHktbTFoYXQpIC8gZWhhdCAtICgxLXcpKih5LW0waGF0KSAvICgxLWVoYXQpDQogIHJlc3VsdHNfaGV0W2ksMl0gPSBtZWFuKHBzZXVkb195KQ0KICB0dCA9IHQudGVzdChwc2V1ZG9feSkNCiAgY292ZXJhZ2VfaGV0W2ksMl0gPSAodHQkY29uZi5pbnRbMV0gIDwgMCAmIHR0JGNvbmYuaW50WzJdID4gMCkNCiAgDQogIGFpcHcgPSBETUxfYWlwdyh5LHcseCxtbF95PWxpc3QoZm9yZXN0KSxjZj01LA0KICAgICAgICAgICAgICAgICAgZV9tYXQgPSBjYmluZCgxLXBsJGVfaGF0LHBsJGVfaGF0KSxjZl9tYXQgPSBwbCRjZl9tYXQpDQogIHJlc3VsdHNfaGV0W2ksM10gPSBhaXB3JEFURSRyZXN1bHRzWzFdDQogIGNvdmVyYWdlX2hldFtpLDNdID0gKGFpcHckQVRFJHJlc3VsdHNbMV0gLSAxLjk2KmFpcHckQVRFJHJlc3VsdHNbMl0gPCAwICYgYWlwdyRBVEUkcmVzdWx0c1sxXSArIDEuOTYqYWlwdyRBVEUkcmVzdWx0c1syXSA+IDApDQp9DQpgYGANCg0KV2UgcGxvdCB0aGUgZXN0aW1hdG9yIGRpc3RyaWJ1dGlvbnMgYW5kIG5vdGUgdGhhdCBiYXNpY2FsbHkgYWxsIGVzdGltYXRvcnMgYXJlIHVuYmlhc2VkOg0KDQoNCmBgYHtyfQ0KYXMuZGF0YS5mcmFtZShyZXN1bHRzX2hldCkgJT4lIHBpdm90X2xvbmdlcihjb2xzPWV2ZXJ5dGhpbmcoKSxuYW1lc190byA9ICJFc3RpbWF0b3IiLHZhbHVlc190byA9ICJjb2VmIikgJT4lDQogIGdncGxvdChhZXMoeCA9IGNvZWYsIGZpbGwgPSBFc3RpbWF0b3IpKSArIGdlb21fZGVuc2l0eShhbHBoYT0wLjUpICsgdGhlbWVfYncoKSArIGdlb21fdmxpbmUoeGludGVyY2VwdD0wKQ0KYGBgDQoNClRoaXMgaXMgY29uZmlybWVkIGJ5IHRoZSBkZWNvbXBvc2l0aW9uIG9mIHRoZSBNU0U6DQoNCmBgYHtyfQ0KZGF0YS5mcmFtZShtZXRob2QgPSBjb2xuYW1lcyhyZXN1bHRzX2hldCksDQogICAgICAgICAgIGJpYXMyID0gY29sTWVhbnMocmVzdWx0c19oZXQtMCleMiwNCiAgICAgICAgICAgdmFyID0gY29sTWVhbnMoc3dlZXAocmVzdWx0c19oZXQsMixjb2xNZWFucyhyZXN1bHRzX2hldCkpXjIpKSAlPiUgDQogIHBpdm90X2xvbmdlcigtbWV0aG9kLG5hbWVzX3RvID0gIkNvbXBvbmVudCIsdmFsdWVzX3RvID0gIk1TRSIpICU+JQ0KICBnZ3Bsb3QoYWVzKGZpbGw9ZmFjdG9yKENvbXBvbmVudCxsZXZlbHM9YygidmFyIiwiYmlhczIiKSksIHk9TVNFLCB4PW1ldGhvZCkpICsgDQogIGdlb21fYmFyKHBvc2l0aW9uPSJzdGFjayIsIHN0YXQ9ImlkZW50aXR5IikgKyBzY2FsZV9maWxsX2Rpc2NyZXRlKG5hbWUgPSAiQ29tcG9uZW50IikNCmBgYA0KDQpOb3RhYmx5IHRoZSBwYXJ0aWFsbHkgbGluZWFyIGVzdGltYXRvciBpcyB1bmJpYXNlZCBhbHRob3VnaCBpdCBhc3N1bWVzIGVmZmVjdCBoZXRlcm9nZW5laXR5LiBIb3dldmVyLCBpdCBzaG93cyBhIGhpZ2hlciB2YXJpYW5jZSB0aGFuIHRoZSBBSVBXIGVzdGltYXRvci4gVGhpcyBpcyBub3QgdW5leHBlY3RlZCBiZWNhdXNlIEFJUFcgaXMgYW4gZWZmaWNpZW50IGVzdGltYXRvciBpbiB0aGUgaGV0ZXJvZ2VuZW91cyBlZmZlY3RzIHNldHRpbmcuIEJ1dCBjcm9zcy1maXR0aW5nIHNlZW1zIHRvIGJlIGhhcm1mdWwgYXMgd2UgaGF2ZSBubyBiaWFzIGFuZCBsb3dlciB2YXJpYW5jZSB3aXRob3V0IGFsbCB0aGlzIGFkZGl0aW9uYWwgZWZmb3J0Lg0KDQpCVVQsIGxldCdzIGNoZWNrIHRoZSBjb3ZlcmFnZSByYXRlOg0KDQpgYGB7cn0NCmRhdGEuZnJhbWUobWV0aG9kID0gY29sbmFtZXMocmVzdWx0c19oZXQpLA0KICAgICAgICAgICBjb3ZlcmFnZSA9IGNvbE1lYW5zKGNvdmVyYWdlX2hldCkpICU+JSANCiAgZ2dwbG90KGFlcyh5PWNvdmVyYWdlLCB4PW1ldGhvZCkpICsgZ2VvbV9obGluZSh5aW50ZXJjZXB0PTAuOTUsbGluZXR5cGU9ImRhc2hlZCIpICsgDQogIGdlb21fcG9pbnQoc2l6ZT01LHNoYXBlPTQpICsgc2NhbGVfZmlsbF9kaXNjcmV0ZShuYW1lID0gIkNvbXBvbmVudCIpICsgeWxpbShjKDAsMSkpICsNCiAgZ2VvbV9obGluZSh5aW50ZXJjZXB0PWMoMCwxKSkNCmBgYA0KDQpDcm9zcy1maXR0ZWQgQUlQVyBzaG93cyBuZWFybHkgcGVyZmVjdCBjb3ZlcmFnZSwgd2hpbGUgdGhlIHN0YW5kYXJkIGVycm9ycyB3aXRob3V0IGNyb3NzLWZpdHRpbmcgYXJlIG11Y2ggdG9vIHNtYWxsLg0KDQokXFJpZ2h0YXJyb3ckIENyb3NzLWZpdHRpbmcgaXMgbm90IG5lY2Vzc2FyaWx5IHJlcXVpcmVkIHRvIHJlbW92ZSBiaWFzIGluIHRoZSBwb2ludCBlc3RpbWF0ZXMgZHVlIHRvIG92ZXJmaXR0aW5nLCBidXQgdG8gcmVtb3ZlIGRvd253YXJkIGJpYXMgaW4gdGhlIHN0YW5kYXJkIGVycm9ycy4gVGhlIHRydWUgQVRFIGlzIHplcm8gaW4gb3VyIGNhc2UsIGJ1dCB3ZSB3b3VsZCBmaW5kIHNpZ25pZmljYW50IGVmZmVjdHMgaW4gYWJvdXQgMjAlIG9mIHRoZSBjYXNlcyBpbnN0ZWFkIG9mIHRoZSA1JSB0aGF0IHdlIGFsbG93IHRvIGhhcHBlbiBnaXZlbiBvdXIgY29uZmlkZW5jZSBsZXZlbC4gDQoNCjxicj4NCjxicj4NCg0KDQoNCiMgRWZmZWN0IGhldGVyb2dlbmVpdHkgd2l0aCB1bmJhbGFuY2VkIHRyZWF0bWVudCBzaGFyZXMNCg0KIyMgREdQDQoNCk5vdyB3ZSBpbnRyb2R1Y2UgdW5iYWxhbmNlZCB0cmVhdG1lbnQgc2hhcmVzIGxlYXZpbmcgdGhlIHJlc3QgdW5jaGFuZ2VkOg0KDQotICRwPTEwJCBpbmRlcGVuZGVudCBjb3ZhcmlhdGVzICRYXzEsLi4uLFhfaywuLi4sWF97MTB9JCBkcmF3biBmcm9tIGEgdW5pZm9ybSBkaXN0cmlidXRpb246ICRYX2sgXHNpbSB1bmlmb3JtKC1ccGksXHBpKSQNCg0KLSBUaGUgdHJlYXRtZW50IG1vZGVsIGlzICRXIFxzaW0gQmVybm91bGxpKFx1bmRlcmJyYWNle1xQaGkoc2luKFhfMS0wLjUpKX1fe2UoWCl9KSQsIHdoZXJlICRcUGhpKFxjZG90KSQgaXMgdGhlIHN0YW5kYXJkIG5vcm1hbCBjdW11bGF0aXZlIGRlbnNpdHkgZnVuY3Rpb24NCg0KLSBUaGUgb3V0Y29tZSBtb2RlbCBvZiB0aGUgdHJlYXRlZCBpcyAkWSgxKSA9IFx1bmRlcmJyYWNle3NpbihYXzEpfV97bV8xKFgpfSsgXHZhcmVwc2lsb24kLCB3aXRoICRcdmFyZXBzaWxvbiBcc2ltIE4oMCwxKSQNCg0KLSBUaGUgb3V0Y29tZSBtb2RlbCBvZiB0aGUgY29udHJvbHMgaXMgJFkoMCkgPSBcdW5kZXJicmFjZXtjb3MoWF8xKzEvMlxwaSl9X3ttXzAoWCl9KyBcdmFyZXBzaWxvbiQsIHdpdGggJFx2YXJlcHNpbG9uIFxzaW0gTigwLDEpJA0KDQpXZSBub3cgZXhwZWN0IHJvdWdobHkgMS8zIHRyZWF0ZWQgYW5kIGluY3JlYXNlIHRoZSBzYW1wbGUgc2l6ZSB0byAzMDAgc3VjaCB0aGF0IGF0IGxlYXN0IDEwMCBvYnNlcnZhdGlvbnMgYXJlIGluIGVhY2ggdHJlYXRtZW50IGFybToNCg0KDQpgYGB7cn0NCm4gPSAzMDANCg0KeCA9IG1hdHJpeChydW5pZihuKnAsLXBpLHBpKSxuY29sPXApDQplID0gZnVuY3Rpb24oeCl7cG5vcm0oc2luKHgpLTAuNSl9DQptMSA9IGZ1bmN0aW9uKHgpe3Npbih4KX0NCm0wID0gZnVuY3Rpb24oeCl7Y29zKHgrMS8yKnBpKX0NCnRhdSA9IGZ1bmN0aW9uKHgpe20xKHgpIC0gbTAoeCl9DQp3ID0gcmJpbm9tKG4sMSxlKHhbLDFdKSkNCnkgPSB3Km0xKHhbLDFdKSArICgxLXcpKm0wKHhbLDFdKSArIHJub3JtKG4sMCwxKQ0KDQpnMSA9IGRhdGEuZnJhbWUoeCA9IGMoLXBpLCBwaSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPWUsc2l6ZT0xKSArIHlsYWIoImUiKSArIHhsYWIoIlgxIikNCmcyID0gZGF0YS5mcmFtZSh4ID0gYygtcGksIHBpKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49bTEsc2l6ZT0xLGFlcyhjb2xvdXI9IlkxIikpICsgDQogIHN0YXRfZnVuY3Rpb24oZnVuPW0wLHNpemU9MSxhZXMoY29sb3VyPSJZMCIpKSArIHlsYWIoIlkiKSArIHhsYWIoIlgxIikNCmczID0gZGF0YS5mcmFtZSh4ID0gYygtcGksIHBpKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49dGF1LHNpemU9MSkgKyB5bGFiKGV4cHJlc3Npb24odGF1KSkgKyB4bGFiKCJYMSIpDQpnMSAvIGcyIC8gZzMNCmBgYA0KDQo8YnI+DQoNCg0KIyMjIFNpbXVsYXRpb24gc3R1ZHkgdW5iYWxhbmNlZCB0cmVhdG1lbnQgc2hhcmVzDQoNCldlIHJ1biBhIHNpbXVsYXRpb24gc3R1ZHkgZHJhd2luZyAkTT0xLDAwMCQgc2FtcGxlcyBmcm9tIHRoZSBER1AgZGVzY3JpYmVkIGFib3ZlIGFuZCBlc3RpbWF0ZSB0aGUgZWZmZWN0IHdpdGggdGhyZWUgZGlmZmVyZW50IGVzdGltYXRvcnM6DQoNCi0gUGFydGlhbGx5IGxpbmVhciBtb2RlbCBlc3RpbWF0ZWQgd2l0aCA1LWZvbGQgY3Jvc3MtZml0dGluZw0KDQotIEFJUFcgd2l0aG91dCBjcm9zcy1maXR0aW5nDQoNCi0gQUlQVyB3aXRoIDUtZm9sZCBjcm9zcy1maXR0aW5nDQoNCg0KYGBge3J9DQojIGluaXRpYWxpemUgc3RvcmFnZSBmb3IgcmVzdWx0cw0KY292ZXJhZ2VfdW5iYWwgPSByZXN1bHRzX3VuYmFsID0gbWF0cml4KE5BLG5fcmVwLDMpDQpjb2xuYW1lcyhjb3ZlcmFnZV91bmJhbCkgPSBjb2xuYW1lcyhyZXN1bHRzX3VuYmFsKSA9IGMoIlBMIGNmNSIsIkFJUFcgbm8iLCJBSVBXIGNmNSIpDQoNCiMgc3RhcnQgc2ltdWxhdGlvbg0KZm9yIChpIGluIDE6bl9yZXApIHsNCiAgeCA9IG1hdHJpeChydW5pZihuKnAsLXBpLHBpKSxuY29sPXApDQogIHcgPSByYmlub20obiwxLGUoeFssMV0pKQ0KICB5ID0gdyptMSh4WywxXSkgKyAoMS13KSptMCh4WywxXSkgKyBybm9ybShuLDAsMSkNCiAgDQogICMgcGFydGlhbGx5IGxpbmVhciBtb2RlbA0KICBwbCA9IERNTF9wYXJ0aWFsX2xpbmVhcih5LHcseCxtbF93PWxpc3QoZm9yZXN0KSxtbF95PWxpc3QoZm9yZXN0KSxjZj01KQ0KICByZXN1bHRzX3VuYmFsW2ksMV0gPSBwbCRyZXN1bHRbMV0NCiAgY292ZXJhZ2VfdW5iYWxbaSwxXSA9IChwbCRyZXN1bHRbMV0gLSAxLjk2KnBsJHJlc3VsdFsyXSA8IDAgJiBwbCRyZXN1bHRbMV0gKyAxLjk2KnBsJHJlc3VsdFsyXSA+IDApDQogIA0KICAjIE5vIGNyb3NzLWZpdHRpbmcNCiAgcmYgPSByZWdyZXNzaW9uX2ZvcmVzdCh4LHcsaG9uZXN0eT1GKQ0KICBlaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeFt3PT0wLF0seVt3PT0wXSxob25lc3R5PUYpDQogIG0waGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHJmID0gcmVncmVzc2lvbl9mb3Jlc3QoeFt3PT0xLF0seVt3PT0xXSxob25lc3R5PUYpDQogIG0xaGF0ID0gcHJlZGljdChyZixuZXdkYXRhPXgpJHByZWRpY3Rpb25zDQogIHBzZXVkb195ID0gIG0xaGF0IC0gbTBoYXQgKw0KICAgIHcqKHktbTFoYXQpIC8gZWhhdCAtICgxLXcpKih5LW0waGF0KSAvICgxLWVoYXQpDQogIHJlc3VsdHNfdW5iYWxbaSwyXSA9IG1lYW4ocHNldWRvX3kpDQogIHR0ID0gdC50ZXN0KHBzZXVkb195KQ0KICBjb3ZlcmFnZV91bmJhbFtpLDJdID0gKHR0JGNvbmYuaW50WzFdICA8IDAgJiB0dCRjb25mLmludFsyXSA+IDApDQogIA0KICAjIDUtZm9sZCBjcm9zcy1maXR0aW5nIHdpdGggY2F1c2FsRE1MIHBhY2thZ2UgcmV1c2luZyB0aGUgZm9sZHMgYW5kIHBzY29yZXMgb2YgUEwNCiAgYWlwdyA9IERNTF9haXB3KHksdyx4LG1sX3k9bGlzdChmb3Jlc3QpLGNmPTUsDQogICAgICAgICAgICAgICAgICBlX21hdCA9IGNiaW5kKDEtcGwkZV9oYXQscGwkZV9oYXQpLGNmX21hdCA9IHBsJGNmX21hdCkNCiAgcmVzdWx0c191bmJhbFtpLDNdID0gYWlwdyRBVEUkcmVzdWx0c1sxXQ0KICBjb3ZlcmFnZV91bmJhbFtpLDNdID0gKGFpcHckQVRFJHJlc3VsdHNbMV0gLSAxLjk2KmFpcHckQVRFJHJlc3VsdHNbMl0gPCAwICYgYWlwdyRBVEUkcmVzdWx0c1sxXSArIDEuOTYqYWlwdyRBVEUkcmVzdWx0c1syXSA+IDApDQp9DQpgYGANCg0KV2UgcGxvdCB0aGUgZXN0aW1hdG9yIGRpc3RyaWJ1dGlvbnM6DQoNCmBgYHtyLCB3YXJuaW5nID0gRiwgbWVzc2FnZSA9IEZ9DQphcy5kYXRhLmZyYW1lKHJlc3VsdHNfdW5iYWwpICU+JSBwaXZvdF9sb25nZXIoY29scz1ldmVyeXRoaW5nKCksbmFtZXNfdG8gPSAiRXN0aW1hdG9yIix2YWx1ZXNfdG8gPSAiY29lZiIpICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSBjb2VmLCBmaWxsID0gRXN0aW1hdG9yKSkgKyBnZW9tX2RlbnNpdHkoYWxwaGE9MC41KSArIHRoZW1lX2J3KCkgKyBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQ9MCkNCmBgYA0KDQpCT09NISEhIE1heWJlIHlvdSB0aG91Z2h0IHRoYXQgdGhlIGVmZmVjdCBob21vZ2VuZWl0eSBhc3N1bXB0aW9uIGltcG9zZWQgYnkgdGhlIHBhcnRpYWxseSBsaW5lYXIgbW9kZWwgd2FzIGhhcm1sZXNzIGdpdmVuIHRoYXQgaXQgd29ya2VkIG5pY2VseSBhYm92ZSwgYnV0IHRoZSA1MC01MCB0cmVhdG1lbnQgc2hhcmUgaXMganVzdCBuaWNlIGluIHRoaXMgcmVnYXJkIChzZWUgW1PFgm9jennFhHNraSAoMjAyMCldKGh0dHBzOi8vZG9pLm9yZy8xMC4xMTYyL3Jlc3RfYV8wMDk1MykgZm9yIGEgbmljZSBkaXNjdXNzaW9uIGluIGNhc2Ugb2YgT0xTKS4gSW4gdGhlIHByZXNlbmNlIG9mIGhldGVyb2dlbmVvdXMgZWZmZWN0cywgZXN0aW1hdG9ycyBhc3N1bWluZyBlZmZlY3QgaG9tb2dlbmVpdHkgZXN0aW1hdGUgc29tZSBjYXVzYWwgZWZmZWN0LCBidXQgbm90IG5lY2Vzc2FyaWx5IHRoZSBBVEUuIFRoZSBlc3RpbWF0b3IgZGlzdHJpYnV0aW9uIGNlbnRlcnMgbmljZWx5IGFyb3VuZCAwLjUsIHdoaWxlIHdlIGtub3cgaXQgc2hvdWxkIGNlbnRlciBhcm91bmQgemVyby4NCg0KVGhpcyBpcyBjb25maXJtZWQgYnkgdGhlIGRlY29tcG9zaXRpb24gb2YgdGhlIE1TRSBzaG93aW5nIGEgaHVnZSBiaWFzOg0KYGBge3J9DQpkYXRhLmZyYW1lKG1ldGhvZCA9IGNvbG5hbWVzKHJlc3VsdHNfdW5iYWwpLA0KICAgICAgICAgICBiaWFzMiA9IGNvbE1lYW5zKHJlc3VsdHNfdW5iYWwtMCxuYS5ybT1UKV4yLA0KICAgICAgICAgICB2YXIgPSBjb2xNZWFucyhzd2VlcChyZXN1bHRzX3VuYmFsLDIsY29sTWVhbnMocmVzdWx0c191bmJhbCxuYS5ybT1UKSleMixuYS5ybT1UKSkgJT4lIA0KICBwaXZvdF9sb25nZXIoLW1ldGhvZCxuYW1lc190byA9ICJDb21wb25lbnQiLHZhbHVlc190byA9ICJNU0UiKSAlPiUNCiAgZ2dwbG90KGFlcyhmaWxsPWZhY3RvcihDb21wb25lbnQsbGV2ZWxzPWMoInZhciIsImJpYXMyIikpLCB5PU1TRSwgeD1tZXRob2QpKSArIA0KICBnZW9tX2Jhcihwb3NpdGlvbj0ic3RhY2siLCBzdGF0PSJpZGVudGl0eSIpICsgc2NhbGVfZmlsbF9kaXNjcmV0ZShuYW1lID0gIkNvbXBvbmVudCIpDQpgYGANCg0KVGhpcyBraWxscyBvZiBjb3Vyc2UgYWxzbyB0aGUgY292ZXJhZ2UgcmF0ZToNCg0KYGBge3J9DQpkYXRhLmZyYW1lKG1ldGhvZCA9IGNvbG5hbWVzKHJlc3VsdHNfdW5iYWwpLA0KICAgICAgICAgICBjb3ZlcmFnZSA9IGNvbE1lYW5zKGNvdmVyYWdlX3VuYmFsLG5hLnJtPVQpKSAlPiUgDQogIGdncGxvdChhZXMoeT1jb3ZlcmFnZSwgeD1tZXRob2QpKSArIGdlb21faGxpbmUoeWludGVyY2VwdD0wLjk1LGxpbmV0eXBlPSJkYXNoZWQiKSArIA0KICBnZW9tX3BvaW50KHNpemU9NSxzaGFwZT00KSArIHNjYWxlX2ZpbGxfZGlzY3JldGUobmFtZSA9ICJDb21wb25lbnQiKSArIHlsaW0oYygwLDEpKSArDQogIGdlb21faGxpbmUoeWludGVyY2VwdD1jKDAsMSkpDQpgYGANCg0KJFxSaWdodGFycm93JCBXZSB3b3VsZCByZWplY3QgdGhlIE51bGwgb2YgJFx0YXVfe0FURX09MCQsIHdoaWNoIGlzIHRydWUgaW4gb3VyIHNldHRpbmcsIGluIDgwJSBvZiB0aGUgY2FzZXMgaWYgd2UgaW1wb3NlZCB0aGUgYXNzdW1wdGlvbiBvZiBlZmZlY3QgaG9tb2dlbmVpdHkuDQoNCjxicj4NCjxicj4NCg0KDQoNCiMgVGFrZS1hd2F5DQogDQogLSBXZSBjYW4gcHJvZ3JhbSBhIGNyb3NzLWZpdCBEb3VibGUgTUwgQUlQVyBlc3RpbWF0b3Igd2l0aCBmZXcgbGluZXMgb2YgY29kZQ0KIA0KIC0gQ3Jvc3MtZml0dGluZyBtYWtlcyBhIGRpZmZlcmVuY2UsIGVzcGVjaWFsbHkgd2hlbiBpdCBjb21lcyB0byBpbmZlcmVuY2UNCiANCiAtIEVzdGltYXRvcnMgYXNzdW1pbmcgZWZmZWN0IGhvbW9nZW5laXR5IGNhbiBkcmFtYXRpY2FsbHkgYnJlYWsgZG93biBpbiB0aGUgcHJlc2VuY2Ugb2YgaGV0ZXJvZ2VuZWl0eQ0KIA0KPGJyPg0KPGJyPg0KIA0KIA0KIyBTdWdnZXN0aW9ucyB0byBwbGF5IHdpdGggdGhlIHRveSBtb2RlbA0KDQpUaGUgd2hvbGUgdGhpbmcgcmFuIHNldmVyYWwgaG91cnMgb24gbXkgbGFwdG9wLCBzbyB5b3Ugc2hvdWxkIGRlY3JlYXNlICpuX3JlcCogZm9yIHRoZSBmaXJzdCBwbGF5IGFuZCB0aGVuIHJ1biBpdCBvdmVyIG5pZ2h0IHdpdGggbW9yZS4NCg0KU29tZSBzdWdnZXN0aW9uczoNCiANCi0gTGV0IHRoZSB0cmVhdG1lbnQgc2hhcmVzIGdvIGUuZy4gZnJvbSAxMCUgdG8gOTAlIGluIDEwJSBzdGVwcyBhbmQgd2F0Y2ggaG93IHlvdSBjYW4gYmFzaWNhbGx5IGdldCBldmVyeSBlZmZlY3QgeW91IGxpa2Ugd2l0aCB0aGUgcGFydGlhbGx5IGxpbmVhciBtb2RlbA0KIA0KLSBNb2RpZnkgREdQIChpbmNyZWFzZSB0aGV0YSwgY29ycmVsYXRpb24gb2YgY292YXJpYXRlcywgY29lZmZpY2llbnRzLCBub2lzZSB0ZXJtLCAuLi4pDQoNCi0gSW5jcmVhc2UgdGhlIG51bWJlciBvZiBvYnNlcnZhdGlvbnMNCg0KLSBJbmNyZWFzZSBjcm9zcy1maXR0aW5nIGZvbGRzIHRvIDEwIGFuZC9vciAyMA0KDQog