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
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)

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

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
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.

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.

## 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
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.

## 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=