We use the Lalonde data that we encountered in HW2 and will encounter again in HW4. Here we focus on the observational data of the job training program. The job training program took place in 1976, and we are interested in its impact on 1978 earnings.
Initial assessment
We obtain the data from a software called MatchIt. This is a subset of the data that you will deal with in HW4.
library("MatchIt")
There were 16 warnings (use warnings() to see them)
data("lalonde")
lalonde
- Check initial covariate balancing
model <- glm(treat ~ . , data = lalonde[, -9], family = "binomial")
x <- model.matrix(model)[, -1]
n <- table(lalonde$treat)
z <- lalonde$treat
data_stat <- data.frame(t(apply(x, 2, function(x) c(mean(x[z==0]), sd(x[z==0]), mean(x[z==1]), sd(x[z==1])))))
colnames(data_stat) <- c("Mean control", "S.D. control", "Mean treated", "S.D. treated")
data_stat$t_stat <- (data_stat[, 3] - data_stat[, 1])/sqrt(data_stat[, 2]^2/n[1] + data_stat[, 4]^2/n[2])
signif(data_stat, 2)
- Visualize covariates balancing
We use t statistics here as the mean differences for different variables do not have comparable scales
library("ggplot2")
t.stat <- (data_stat[, 3] - data_stat[, 1])/sqrt(data_stat[, 2]^2/n[1] + data_stat[, 4]^2/n[2])
temp <- data.frame(x = colnames(x), y = t.stat)
ggplot(temp, aes(x, y)) + geom_point() + geom_hline(yintercept = 0) +
geom_hline(yintercept = -1.96, color = "red")+
geom_hline(yintercept = 1.96, color = "red") +
xlab("") + ylab("t statistics") + theme_classic() +
theme(axis.text.x = element_text(angle = 45, vjust = 0.5, hjust=1))
T statistics show that the mean differences of many variables are significantly non-zero.
Stratification based on the estimated propensity score
- Estimate propensity score
model <- glm(treat ~ . , data = lalonde[, -9], family = "binomial")
summary(model)
Call:
glm(formula = treat ~ ., family = "binomial", data = lalonde[,
-9])
Deviance Residuals:
Min 1Q Median 3Q Max
-1.7645 -0.4736 -0.2862 0.7508 2.7169
Coefficients:
Estimate Std. Error z value Pr(>|z|)
(Intercept) -1.663e+00 9.709e-01 -1.713 0.08668 .
age 1.578e-02 1.358e-02 1.162 0.24521
educ 1.613e-01 6.513e-02 2.477 0.01325 *
racehispan -2.082e+00 3.672e-01 -5.669 1.44e-08 ***
racewhite -3.065e+00 2.865e-01 -10.699 < 2e-16 ***
married -8.321e-01 2.903e-01 -2.866 0.00415 **
nodegree 7.073e-01 3.377e-01 2.095 0.03620 *
re74 -7.178e-05 2.875e-05 -2.497 0.01253 *
re75 5.345e-05 4.635e-05 1.153 0.24884
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
(Dispersion parameter for binomial family taken to be 1)
Null deviance: 751.49 on 613 degrees of freedom
Residual deviance: 487.84 on 605 degrees of freedom
AIC: 505.84
Number of Fisher Scoring iterations: 5
- Check overlapping of the estimated propensity score
library(ggplot2)
pscore <- model$fitted.values
temp.data <- data.frame(eps = pscore, treated = as.factor(lalonde$treat))
ggplot(temp.data,
aes(x = eps, fill = treated, color = treated)) +
geom_histogram(alpha = 0.5, position = "identity") +
xlab("Estimated propensity score")
Overlap is extremely poor. Many control units have low propensity score.
- Trimming to improve overlapping
rm.idx <- which(pscore < 0.1 | pscore > 0.9)
idx.treated <- which((lalonde$treat == 1) & (pscore > max(pscore[lalonde$treat == 0])))
idx.control <- which((lalonde$treat == 0) & (pscore < min(pscore[lalonde$treat == 1])))
rm.idx <- union(rm.idx, c(idx.treated, idx.control))
lalonde <- lalonde[-rm.idx, ]
pscore <- pscore[-rm.idx]
lps <- predict(model)[-rm.idx]
x <- x[-rm.idx, ]
lalonde
Almost half of the units get trimmed out
Stratify the units into K = 5 equal strata and check covariates balancing
NeymanSRE <- function(W, Y, strata.labels) {
n <- length(W)
groups <- unique(strata.labels)
ests <- sapply(groups, function(gg) {
wt <- sum(strata.labels == gg)/n
est <- mean(Y[strata.labels == gg & W == 1]) - mean(Y[strata.labels == gg & W == 0])
est.var <- var(Y[strata.labels == gg & W == 1])/sum(strata.labels == gg & W == 1) +
var(Y[strata.labels == gg & W == 0])/sum(strata.labels == gg & W == 0)
return(c(wt, est, est.var))
})
# print(ests)
neyman.est <- sum(ests[1, ] * ests[2, ])
neyman.var <- sum(ests[1, ]^2 * ests[3, ])
return(c(est = neyman.est, se = sqrt(neyman.var),
tstat = neyman.est/sqrt(neyman.var)))
}
nn <- 5
q.pscore <- quantile(pscore , (1:( nn -1)) / nn)
ps.strata <- cut(pscore, breaks = c(0 , q.pscore ,1), labels = 1:nn)
balance_check <- apply(x, 2, function(v) NeymanSRE(lalonde$treat, v, ps.strata))
temp <- data.frame(x = colnames(x), y = balance_check[3, ])
ggplot(temp, aes(x, y)) + geom_point() + geom_hline(yintercept = 0) +
geom_hline(yintercept = -1.96, color = "red")+
geom_hline(yintercept = 1.96, color = "red") +
xlab("") + ylab("t statistics") + theme_classic() +
theme(axis.text.x = element_text(angle = 45, vjust = 0.5, hjust=1))
Covariates get much better balanced.
- We also perform sequencing splitting to find the stratas
## First, create a data frame to store the current grouping information
temp <- data.frame(e = lps, treat = lalonde$treat, b = 1)
t.max <- 1.96
# check whether t. stat is above t.max for first iteration
t.stat <- t.test(x = temp$e[temp$treat == 1], y = temp$e[temp$treat == 0], var.equal=T)$statistic
condition = t.stat > t.max
# minimum n.t or n.c in each block
size <- 3
size.new <- 20
# continue until all t statistics are below t.max
set.seed(0)
while(condition)
{
# calculate size in each group
# we want to not split a block if it is too small
b <- max(temp$b)
ignore <- sapply(1:b, function(j) {
n.t <- sum(temp$treat == 1 & temp$b == j)
n.c <- sum(temp$treat == 0 & temp$b == j)
return(n.t < size | n.c < size | (n.t + n.c < size.new * 2))
})
# split unbalanced blocks into more blocks
split <- which((abs(t.stat) > t.max) & (!ignore))
if(length(split) == 0)
break
## we need to keep a current copy of the block information and which block to ignore as block assignments are going to change later
b.current <- temp$b
for(j in split)
{
cutoff <- median(temp$e[b.current == j])
## We split units into two new blocks
## extract the index of units belonging to each new stratum
idx.s <- which(b.current == j & temp$e < cutoff)
idx.l <- which(b.current == j & temp$e > cutoff)
## randomly put half of the ties into one category
idx.e <- which(temp$e == cutoff & b.current == j)
n.tie <- length(idx.e)
if (n.tie >= 1) {
if (n.tie > 1) {
idx.e <- sample(idx.e)
idx.s <- c(idx.s, idx.e[1:round(n.tie/2)])
}
idx.l <- c(idx.l, idx.e[(round(n.tie/2)+ 1):n.tie])
}
## we split only when new stratum has at least size number of control/treated units
if (sum(temp$treat[idx.s]==1) > size && sum(temp$treat[idx.s]==0) > size &&
sum(temp$treat[idx.l]==1) > size && sum(temp$treat[idx.l]==0) > size) {
# anything above the current will have to be moved up 1
temp$b[b.current > j] <- temp$b[b.current > j] + 1
## the upper new stratum will also have the block idx added by 1
temp$b[idx.l] <- temp$b[idx.l] + 1
}
## We don't do anything if we do not want to split
}
# calculate t statistic for each block
b <- max(temp$b)
t.stat <- sapply(1:b, function(j) {
t.test(x = temp$e[temp$treat == 1 & temp$b == j],
y = temp$e[temp$treat == 0 & temp$b == j], var.equal=T)$statistic
})
## Update condition
# check whether ANY blocks are above t.max
# AND are not too small
condition <- any(abs(t.stat) > t.max)
}
lalonde$blocks <- temp$b
print("number of individuals per strata")
[1] "number of individuals per strata"
table(lalonde[, c("treat", "blocks")])
blocks
treat 1 2 3 4
0 67 28 14 57
1 16 13 28 110
## check the range of estimated propensity scores
lps_blocks <- sapply(1:max(lalonde$blocks),
function(j) range(temp$e[temp$b == j]))
eps_blocks <- exp(lps_blocks)/(1 + exp(lps_blocks))
colnames(eps_blocks) <- paste("strata", 1:4)
rownames(eps_blocks) <- c("min eps", "max eps")
eps_blocks
strata 1 strata 2 strata 3 strata 4
min eps 0.1002783 0.2225951 0.4509483 0.6052111
max eps 0.2161957 0.4487064 0.6051661 0.7891728
- Check covariates balancing again
balance_check <- apply(x, 2, function(v) NeymanSRE(lalonde$treat, v, lalonde$blocks))
temp <- data.frame(x = colnames(x), y = balance_check[3, ])
ggplot(temp, aes(x, y)) + geom_point() + geom_hline(yintercept = 0) +
geom_hline(yintercept = -1.96, color = "red")+
geom_hline(yintercept = 1.96, color = "red") +
xlab("") + ylab("t statistics") + theme_classic() +
theme(axis.text.x = element_text(angle = 45, vjust = 0.5, hjust=1))
We have better covariate balancing even with fewer blocks.
- Next, we treat the data as from a stratified randomized experiment and use Neyman’s estimator
## CI from Neyman
result <- NeymanSRE(lalonde$treat, lalonde$re78, lalonde$blocks)
result <- c(result[1:2], c(result[1] - 1.96 * result[2], result[1] + 1.96 * result[2]))
names(result) <- c("est", "sd", "CI_lower", "CI_upper")
result
est sd CI_lower CI_upper
941.2842 886.9070 -797.0535 2679.6219
LS0tCnRpdGxlOiAnUiBFeGFtcGxlIDc6IHByb3BlbnNpdHkgc2NvcmUgc3RyYXRpZmljYXRpb24gd2l0aCBsYWxvbmRlIGRhdGEnCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCldlIHVzZSB0aGUgTGFsb25kZSBkYXRhIHRoYXQgd2UgZW5jb3VudGVyZWQgaW4gSFcyIGFuZCB3aWxsIGVuY291bnRlciBhZ2FpbiBpbiBIVzQuIEhlcmUgd2UgZm9jdXMgb24gdGhlIG9ic2VydmF0aW9uYWwgZGF0YSBvZiB0aGUgam9iIHRyYWluaW5nIHByb2dyYW0uIFRoZSBqb2IgdHJhaW5pbmcgcHJvZ3JhbSB0b29rIHBsYWNlIGluIDE5NzYsIGFuZCB3ZSBhcmUgaW50ZXJlc3RlZCBpbiBpdHMgaW1wYWN0IG9uIDE5NzggZWFybmluZ3MuCgoKIyBJbml0aWFsIGFzc2Vzc21lbnQKCldlIG9idGFpbiB0aGUgZGF0YSBmcm9tIGEgc29mdHdhcmUgY2FsbGVkIE1hdGNoSXQuIFRoaXMgaXMgYSBzdWJzZXQgb2YgdGhlIGRhdGEgdGhhdCB5b3Ugd2lsbCBkZWFsIHdpdGggaW4gSFc0LgoKLSBSZWFkIGRhdGEKCmBgYHtyfQpsaWJyYXJ5KCJNYXRjaEl0IikKZGF0YSgibGFsb25kZSIpCmxhbG9uZGUKYGBgCgotIENoZWNrIGluaXRpYWwgY292YXJpYXRlIGJhbGFuY2luZyAgCmBgYHtyfQptb2RlbCA8LSBnbG0odHJlYXQgfiAuICwgZGF0YSA9IGxhbG9uZGVbLCAtOV0sIGZhbWlseSA9ICJiaW5vbWlhbCIpCnggPC0gbW9kZWwubWF0cml4KG1vZGVsKVssIC0xXQpuIDwtIHRhYmxlKGxhbG9uZGUkdHJlYXQpCnogPC0gbGFsb25kZSR0cmVhdApkYXRhX3N0YXQgPC0gZGF0YS5mcmFtZSh0KGFwcGx5KHgsIDIsIGZ1bmN0aW9uKHgpIGMobWVhbih4W3o9PTBdKSwgc2QoeFt6PT0wXSksIG1lYW4oeFt6PT0xXSksIHNkKHhbej09MV0pKSkpKQpjb2xuYW1lcyhkYXRhX3N0YXQpIDwtIGMoIk1lYW4gY29udHJvbCIsICJTLkQuIGNvbnRyb2wiLCAiTWVhbiB0cmVhdGVkIiwgIlMuRC4gdHJlYXRlZCIpCmRhdGFfc3RhdCR0X3N0YXQgPC0gKGRhdGFfc3RhdFssIDNdIC0gZGF0YV9zdGF0WywgMV0pL3NxcnQoZGF0YV9zdGF0WywgMl1eMi9uWzFdICsgZGF0YV9zdGF0WywgNF1eMi9uWzJdKQpzaWduaWYoZGF0YV9zdGF0LCAyKQpgYGAKCi0gVmlzdWFsaXplIGNvdmFyaWF0ZXMgYmFsYW5jaW5nCgpXZSB1c2UgdCBzdGF0aXN0aWNzIGhlcmUgYXMgdGhlIG1lYW4gZGlmZmVyZW5jZXMgZm9yIGRpZmZlcmVudCB2YXJpYWJsZXMgZG8gbm90IGhhdmUgY29tcGFyYWJsZSBzY2FsZXMKCmBgYHtyfQpsaWJyYXJ5KCJnZ3Bsb3QyIikKdC5zdGF0IDwtIChkYXRhX3N0YXRbLCAzXSAtIGRhdGFfc3RhdFssIDFdKS9zcXJ0KGRhdGFfc3RhdFssIDJdXjIvblsxXSArIGRhdGFfc3RhdFssIDRdXjIvblsyXSkKdGVtcCA8LSBkYXRhLmZyYW1lKHggPSBjb2xuYW1lcyh4KSwgeSA9IHQuc3RhdCkKZ2dwbG90KHRlbXAsIGFlcyh4LCB5KSkgKyBnZW9tX3BvaW50KCkgKyBnZW9tX2hsaW5lKHlpbnRlcmNlcHQgPSAwKSArCiAgZ2VvbV9obGluZSh5aW50ZXJjZXB0ID0gLTEuOTYsIGNvbG9yID0gInJlZCIpKyAKICBnZW9tX2hsaW5lKHlpbnRlcmNlcHQgPSAxLjk2LCBjb2xvciA9ICJyZWQiKSArCiAgeGxhYigiIikgKyB5bGFiKCJ0IHN0YXRpc3RpY3MiKSArIHRoZW1lX2NsYXNzaWMoKSArIAogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gNDUsIHZqdXN0ID0gMC41LCBoanVzdD0xKSkgCmBgYAoKVCBzdGF0aXN0aWNzIHNob3cgdGhhdCB0aGUgbWVhbiBkaWZmZXJlbmNlcyBvZiBtYW55IHZhcmlhYmxlcyBhcmUgc2lnbmlmaWNhbnRseSBub24temVyby4KCgojIFN0cmF0aWZpY2F0aW9uIGJhc2VkIG9uIHRoZSBlc3RpbWF0ZWQgcHJvcGVuc2l0eSBzY29yZQoKLSBFc3RpbWF0ZSBwcm9wZW5zaXR5IHNjb3JlCgpgYGB7cn0KbW9kZWwgPC0gZ2xtKHRyZWF0IH4gLiAsIGRhdGEgPSBsYWxvbmRlWywgLTldLCBmYW1pbHkgPSAiYmlub21pYWwiKQpzdW1tYXJ5KG1vZGVsKQpgYGAKCgotIENoZWNrIG92ZXJsYXBwaW5nIG9mIHRoZSBlc3RpbWF0ZWQgcHJvcGVuc2l0eSBzY29yZQoKYGBge3J9CmxpYnJhcnkoZ2dwbG90MikKcHNjb3JlIDwtIG1vZGVsJGZpdHRlZC52YWx1ZXMKdGVtcC5kYXRhIDwtIGRhdGEuZnJhbWUoZXBzID0gcHNjb3JlLCB0cmVhdGVkID0gYXMuZmFjdG9yKGxhbG9uZGUkdHJlYXQpKQpnZ3Bsb3QodGVtcC5kYXRhLCAKICAgICAgIGFlcyh4ID0gZXBzLCBmaWxsID0gdHJlYXRlZCwgY29sb3IgPSB0cmVhdGVkKSkgKyAKICBnZW9tX2hpc3RvZ3JhbShhbHBoYSA9IDAuNSwgcG9zaXRpb24gPSAiaWRlbnRpdHkiKSArIAogIHhsYWIoIkVzdGltYXRlZCBwcm9wZW5zaXR5IHNjb3JlIikgCmBgYApPdmVybGFwIGlzIGV4dHJlbWVseSBwb29yLiBNYW55IGNvbnRyb2wgdW5pdHMgaGF2ZSBsb3cgcHJvcGVuc2l0eSBzY29yZS4gCgoKLSBUcmltbWluZyB0byBpbXByb3ZlIG92ZXJsYXBwaW5nCmBgYHtyfQpybS5pZHggPC0gd2hpY2gocHNjb3JlIDwgMC4xIHwgcHNjb3JlID4gMC45KQppZHgudHJlYXRlZCA8LSB3aGljaCgobGFsb25kZSR0cmVhdCA9PSAxKSAmIChwc2NvcmUgPiBtYXgocHNjb3JlW2xhbG9uZGUkdHJlYXQgPT0gMF0pKSkKaWR4LmNvbnRyb2wgPC0gd2hpY2goKGxhbG9uZGUkdHJlYXQgPT0gMCkgJiAocHNjb3JlIDwgbWluKHBzY29yZVtsYWxvbmRlJHRyZWF0ID09IDFdKSkpCnJtLmlkeCA8LSB1bmlvbihybS5pZHgsIGMoaWR4LnRyZWF0ZWQsIGlkeC5jb250cm9sKSkKCmxhbG9uZGUgPC0gbGFsb25kZVstcm0uaWR4LCBdCnBzY29yZSA8LSBwc2NvcmVbLXJtLmlkeF0KbHBzIDwtIHByZWRpY3QobW9kZWwpWy1ybS5pZHhdCnggPC0geFstcm0uaWR4LCBdCgpsYWxvbmRlCmBgYAoKQWxtb3N0IGhhbGYgb2YgdGhlIHVuaXRzIGdldCB0cmltbWVkIG91dAoKLSBTdHJhdGlmaWNhdGlvbgoKU3RyYXRpZnkgdGhlIHVuaXRzIGludG8gSyA9IDUgZXF1YWwgc3RyYXRhIGFuZCBjaGVjayBjb3ZhcmlhdGVzIGJhbGFuY2luZwoKYGBge3J9Ck5leW1hblNSRSA8LSBmdW5jdGlvbihXLCBZLCBzdHJhdGEubGFiZWxzKSB7CiAgbiA8LSBsZW5ndGgoVykKICBncm91cHMgPC0gdW5pcXVlKHN0cmF0YS5sYWJlbHMpCiAgZXN0cyA8LSBzYXBwbHkoZ3JvdXBzLCBmdW5jdGlvbihnZykgewogICB3dCA8LSBzdW0oc3RyYXRhLmxhYmVscyA9PSBnZykvbgogICBlc3QgPC0gbWVhbihZW3N0cmF0YS5sYWJlbHMgPT0gZ2cgJiBXID09IDFdKSAtIG1lYW4oWVtzdHJhdGEubGFiZWxzID09IGdnICYgVyA9PSAwXSkKICAgZXN0LnZhciA8LSB2YXIoWVtzdHJhdGEubGFiZWxzID09IGdnICYgVyA9PSAxXSkvc3VtKHN0cmF0YS5sYWJlbHMgPT0gZ2cgJiBXID09IDEpICsgCiAgICAgdmFyKFlbc3RyYXRhLmxhYmVscyA9PSBnZyAmIFcgPT0gMF0pL3N1bShzdHJhdGEubGFiZWxzID09IGdnICYgVyA9PSAwKQogICByZXR1cm4oYyh3dCwgZXN0LCBlc3QudmFyKSkKIH0pCiMgcHJpbnQoZXN0cykKIG5leW1hbi5lc3QgPC0gc3VtKGVzdHNbMSwgXSAqIGVzdHNbMiwgXSkKIG5leW1hbi52YXIgPC0gc3VtKGVzdHNbMSwgXV4yICogZXN0c1szLCBdKQogcmV0dXJuKGMoZXN0ID0gbmV5bWFuLmVzdCwgc2UgPSBzcXJ0KG5leW1hbi52YXIpLCAKICAgICAgICAgIHRzdGF0ID0gbmV5bWFuLmVzdC9zcXJ0KG5leW1hbi52YXIpKSkKfQoKbm4gPC0gNQpxLnBzY29yZSA8LSBxdWFudGlsZShwc2NvcmUgLCAoMTooIG5uIC0xKSkgLyBubikKcHMuc3RyYXRhIDwtIGN1dChwc2NvcmUsIGJyZWFrcyA9IGMoMCAsIHEucHNjb3JlICwxKSwgbGFiZWxzID0gMTpubikKYmFsYW5jZV9jaGVjayA8LSBhcHBseSh4LCAyLCBmdW5jdGlvbih2KSBOZXltYW5TUkUobGFsb25kZSR0cmVhdCwgdiwgcHMuc3RyYXRhKSkgCgoKdGVtcCA8LSBkYXRhLmZyYW1lKHggPSBjb2xuYW1lcyh4KSwgeSA9IGJhbGFuY2VfY2hlY2tbMywgXSkKZ2dwbG90KHRlbXAsIGFlcyh4LCB5KSkgKyBnZW9tX3BvaW50KCkgKyBnZW9tX2hsaW5lKHlpbnRlcmNlcHQgPSAwKSArCiAgZ2VvbV9obGluZSh5aW50ZXJjZXB0ID0gLTEuOTYsIGNvbG9yID0gInJlZCIpKyAKICBnZW9tX2hsaW5lKHlpbnRlcmNlcHQgPSAxLjk2LCBjb2xvciA9ICJyZWQiKSArCiAgeGxhYigiIikgKyB5bGFiKCJ0IHN0YXRpc3RpY3MiKSArIHRoZW1lX2NsYXNzaWMoKSArIAogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gNDUsIHZqdXN0ID0gMC41LCBoanVzdD0xKSkgCmBgYAoKQ292YXJpYXRlcyBnZXQgbXVjaCBiZXR0ZXIgYmFsYW5jZWQuCgotIFdlIGFsc28gcGVyZm9ybSBzZXF1ZW5jaW5nIHNwbGl0dGluZyB0byBmaW5kIHRoZSBzdHJhdGFzCgpgYGB7cn0KIyMgRmlyc3QsIGNyZWF0ZSBhIGRhdGEgZnJhbWUgdG8gc3RvcmUgdGhlIGN1cnJlbnQgZ3JvdXBpbmcgaW5mb3JtYXRpb24KdGVtcCA8LSBkYXRhLmZyYW1lKGUgPSBscHMsIHRyZWF0ID0gbGFsb25kZSR0cmVhdCwgYiA9IDEpCgp0Lm1heCA8LSAgMS45NgojIGNoZWNrIHdoZXRoZXIgdC4gc3RhdCBpcyBhYm92ZSB0Lm1heCBmb3IgZmlyc3QgaXRlcmF0aW9uCnQuc3RhdCA8LSB0LnRlc3QoeCA9IHRlbXAkZVt0ZW1wJHRyZWF0ID09IDFdLCB5ID0gIHRlbXAkZVt0ZW1wJHRyZWF0ID09IDBdLCB2YXIuZXF1YWw9VCkkc3RhdGlzdGljCmNvbmRpdGlvbiA9IHQuc3RhdCA+IHQubWF4CiMgbWluaW11bSBuLnQgb3Igbi5jIGluIGVhY2ggYmxvY2sKc2l6ZSA8LSAzCnNpemUubmV3IDwtIDIwCgojIGNvbnRpbnVlIHVudGlsIGFsbCB0IHN0YXRpc3RpY3MgYXJlIGJlbG93IHQubWF4CnNldC5zZWVkKDApCndoaWxlKGNvbmRpdGlvbikKewogICMgY2FsY3VsYXRlIHNpemUgaW4gZWFjaCBncm91cAogICMgd2Ugd2FudCB0byBub3Qgc3BsaXQgYSBibG9jayBpZiBpdCBpcyB0b28gc21hbGwKICBiIDwtIG1heCh0ZW1wJGIpCiAgaWdub3JlIDwtIHNhcHBseSgxOmIsIGZ1bmN0aW9uKGopIHsKICAgICBuLnQgPC0gc3VtKHRlbXAkdHJlYXQgPT0gMSAmIHRlbXAkYiA9PSBqKQogICAgIG4uYyA8LSBzdW0odGVtcCR0cmVhdCA9PSAwICYgdGVtcCRiID09IGopCiAgICAgcmV0dXJuKG4udCA8IHNpemUgfCBuLmMgPCBzaXplIHwgKG4udCArIG4uYyA8IHNpemUubmV3ICogMikpCiAgfSkKICAKICAKICAjIHNwbGl0IHVuYmFsYW5jZWQgYmxvY2tzIGludG8gbW9yZSBibG9ja3MKICBzcGxpdCA8LSB3aGljaCgoYWJzKHQuc3RhdCkgPiB0Lm1heCkgJiAoIWlnbm9yZSkpCiAgCiAgaWYobGVuZ3RoKHNwbGl0KSA9PSAwKQogICAgYnJlYWsKCiAgCiAgIyMgd2UgbmVlZCB0byBrZWVwIGEgY3VycmVudCBjb3B5IG9mIHRoZSBibG9jayBpbmZvcm1hdGlvbiBhbmQgd2hpY2ggYmxvY2sgdG8gaWdub3JlIGFzIGJsb2NrIGFzc2lnbm1lbnRzIGFyZSBnb2luZyB0byBjaGFuZ2UgbGF0ZXIKICBiLmN1cnJlbnQgPC0gdGVtcCRiCiAgCiAgZm9yKGogaW4gc3BsaXQpCiAgewogICAgCiAgICBjdXRvZmYgPC0gbWVkaWFuKHRlbXAkZVtiLmN1cnJlbnQgPT0gal0pCiAgICAjIyBXZSBzcGxpdCB1bml0cyBpbnRvIHR3byBuZXcgYmxvY2tzCiAgICAjIyBleHRyYWN0IHRoZSBpbmRleCBvZiB1bml0cyBiZWxvbmdpbmcgdG8gZWFjaCBuZXcgc3RyYXR1bQogICAgaWR4LnMgPC0gd2hpY2goYi5jdXJyZW50ID09IGogJiB0ZW1wJGUgPCBjdXRvZmYpCiAgICBpZHgubCA8LSB3aGljaChiLmN1cnJlbnQgPT0gaiAmIHRlbXAkZSA+IGN1dG9mZikKICAgICMjIHJhbmRvbWx5IHB1dCBoYWxmIG9mIHRoZSB0aWVzIGludG8gb25lIGNhdGVnb3J5CiAgICBpZHguZSA8LSB3aGljaCh0ZW1wJGUgPT0gY3V0b2ZmICYgYi5jdXJyZW50ID09IGopCiAgICBuLnRpZSA8LSBsZW5ndGgoaWR4LmUpCiAgICBpZiAobi50aWUgPj0gMSkgewogICAgICBpZiAobi50aWUgPiAxKSB7CiAgICAgICAgaWR4LmUgPC0gc2FtcGxlKGlkeC5lKQogICAgICAgIGlkeC5zIDwtIGMoaWR4LnMsIGlkeC5lWzE6cm91bmQobi50aWUvMildKQogICAgICB9CiAgICAgIGlkeC5sIDwtIGMoaWR4LmwsIGlkeC5lWyhyb3VuZChuLnRpZS8yKSsgMSk6bi50aWVdKQogICAgfQogICAgICAKICAgICMjIHdlIHNwbGl0IG9ubHkgd2hlbiBuZXcgc3RyYXR1bSBoYXMgYXQgbGVhc3Qgc2l6ZSBudW1iZXIgb2YgY29udHJvbC90cmVhdGVkIHVuaXRzCiAgICBpZiAoc3VtKHRlbXAkdHJlYXRbaWR4LnNdPT0xKSA+IHNpemUgJiYgc3VtKHRlbXAkdHJlYXRbaWR4LnNdPT0wKSA+IHNpemUgJiYgCiAgICAgICAgc3VtKHRlbXAkdHJlYXRbaWR4LmxdPT0xKSA+IHNpemUgJiYgc3VtKHRlbXAkdHJlYXRbaWR4LmxdPT0wKSA+IHNpemUpIHsKICAgICAgIyBhbnl0aGluZyBhYm92ZSB0aGUgY3VycmVudCB3aWxsIGhhdmUgdG8gYmUgbW92ZWQgdXAgMQogICAgICB0ZW1wJGJbYi5jdXJyZW50ID4gal0gPC0gdGVtcCRiW2IuY3VycmVudCA+IGpdICsgMQogICAgICAjIyB0aGUgdXBwZXIgbmV3IHN0cmF0dW0gd2lsbCBhbHNvIGhhdmUgdGhlIGJsb2NrIGlkeCBhZGRlZCBieSAxCiAgICAgIHRlbXAkYltpZHgubF0gPC0gdGVtcCRiW2lkeC5sXSArIDEKICAgIH0KICAgICMjIFdlIGRvbid0IGRvIGFueXRoaW5nIGlmIHdlIGRvIG5vdCB3YW50IHRvIHNwbGl0CiAgfQogIAogICAjIGNhbGN1bGF0ZSB0IHN0YXRpc3RpYyBmb3IgZWFjaCBibG9jawogIGIgPC0gbWF4KHRlbXAkYikKICB0LnN0YXQgPC0gc2FwcGx5KDE6YiwgZnVuY3Rpb24oaikgewogICAgdC50ZXN0KHggPSB0ZW1wJGVbdGVtcCR0cmVhdCA9PSAxICYgdGVtcCRiID09IGpdLCAKICAgICAgICAgICAgICAgICAgICAgICAgeSA9IHRlbXAkZVt0ZW1wJHRyZWF0ID09IDAgJiB0ZW1wJGIgPT0gal0sIHZhci5lcXVhbD1UKSRzdGF0aXN0aWMKICB9KQogIAogICMjIFVwZGF0ZSBjb25kaXRpb24KICAjIGNoZWNrIHdoZXRoZXIgQU5ZIGJsb2NrcyBhcmUgYWJvdmUgdC5tYXgKICAjIEFORCBhcmUgbm90IHRvbyBzbWFsbAogIGNvbmRpdGlvbiA8LSBhbnkoYWJzKHQuc3RhdCkgPiB0Lm1heCkKfQoKbGFsb25kZSRibG9ja3MgPC0gdGVtcCRiCnByaW50KCJudW1iZXIgb2YgaW5kaXZpZHVhbHMgcGVyIHN0cmF0YSIpCnRhYmxlKGxhbG9uZGVbLCBjKCJ0cmVhdCIsICJibG9ja3MiKV0pCgojIyBjaGVjayB0aGUgcmFuZ2Ugb2YgZXN0aW1hdGVkIHByb3BlbnNpdHkgc2NvcmVzCmxwc19ibG9ja3MgPC0gc2FwcGx5KDE6bWF4KGxhbG9uZGUkYmxvY2tzKSwgCiAgICAgICAgICAgICAgICAgICAgIGZ1bmN0aW9uKGopIHJhbmdlKHRlbXAkZVt0ZW1wJGIgPT0gal0pKQplcHNfYmxvY2tzIDwtIGV4cChscHNfYmxvY2tzKS8oMSArIGV4cChscHNfYmxvY2tzKSkKY29sbmFtZXMoZXBzX2Jsb2NrcykgPC0gcGFzdGUoInN0cmF0YSIsIDE6NCkKcm93bmFtZXMoZXBzX2Jsb2NrcykgPC0gYygibWluIGVwcyIsICJtYXggZXBzIikKZXBzX2Jsb2NrcwpgYGAKCi0gQ2hlY2sgY292YXJpYXRlcyBiYWxhbmNpbmcgYWdhaW4KCmBgYHtyfQpiYWxhbmNlX2NoZWNrIDwtIGFwcGx5KHgsIDIsIGZ1bmN0aW9uKHYpIE5leW1hblNSRShsYWxvbmRlJHRyZWF0LCB2LCBsYWxvbmRlJGJsb2NrcykpIAoKCnRlbXAgPC0gZGF0YS5mcmFtZSh4ID0gY29sbmFtZXMoeCksIHkgPSBiYWxhbmNlX2NoZWNrWzMsIF0pCmdncGxvdCh0ZW1wLCBhZXMoeCwgeSkpICsgZ2VvbV9wb2ludCgpICsgZ2VvbV9obGluZSh5aW50ZXJjZXB0ID0gMCkgKwogIGdlb21faGxpbmUoeWludGVyY2VwdCA9IC0xLjk2LCBjb2xvciA9ICJyZWQiKSsgCiAgZ2VvbV9obGluZSh5aW50ZXJjZXB0ID0gMS45NiwgY29sb3IgPSAicmVkIikgKwogIHhsYWIoIiIpICsgeWxhYigidCBzdGF0aXN0aWNzIikgKyB0aGVtZV9jbGFzc2ljKCkgKyAKICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDQ1LCB2anVzdCA9IDAuNSwgaGp1c3Q9MSkpIApgYGAKV2UgaGF2ZSBiZXR0ZXIgY292YXJpYXRlIGJhbGFuY2luZyBldmVuIHdpdGggZmV3ZXIgYmxvY2tzLgoKLSBOZXh0LCB3ZSB0cmVhdCB0aGUgZGF0YSBhcyBmcm9tIGEgc3RyYXRpZmllZCByYW5kb21pemVkIGV4cGVyaW1lbnQgYW5kIHVzZSBOZXltYW4ncyBlc3RpbWF0b3IKCmBgYHtyfQojIyBDSSBmcm9tIE5leW1hbgpyZXN1bHQgPC0gTmV5bWFuU1JFKGxhbG9uZGUkdHJlYXQsIGxhbG9uZGUkcmU3OCwgbGFsb25kZSRibG9ja3MpCnJlc3VsdCA8LSBjKHJlc3VsdFsxOjJdLCBjKHJlc3VsdFsxXSAtIDEuOTYgKiByZXN1bHRbMl0sIHJlc3VsdFsxXSArIDEuOTYgKiByZXN1bHRbMl0pKQpuYW1lcyhyZXN1bHQpIDwtIGMoImVzdCIsICJzZCIsICJDSV9sb3dlciIsICJDSV91cHBlciIpCnJlc3VsdApgYGAKCgo=