We continue analyzing the lalonde data obtained from the MatchIt package. We estimate the propensity scores using the selected logstic regression model in R Example 5

library("MatchIt")
data("lalonde")

model <- glm(treat ~ re74 + race + married + I(re74^2) + re74:race, data = lalonde, family = "binomial")
eps <- predict(model, type = "response")
lps <- predict(model)

Assess initial imbalance

m.out0 <- matchit(treat ~ age + educ + race + married + 
                   nodegree + re74 + re75, data = lalonde,
                 method = NULL, distance = "glm")
## distance here refer to a method to estimate the propensity score
## No matching is performed at this stage
summary(m.out0)

Call:
matchit(formula = treat ~ age + educ + race + married + nodegree + 
    re74 + re75, data = lalonde, method = NULL, distance = "glm")

Summary of Balance for All Data:
           Means Treated Means Control Std. Mean Diff. Var. Ratio eCDF Mean eCDF Max
distance          0.5774        0.1822          1.7941     0.9211    0.3774   0.6444
age              25.8162       28.0303         -0.3094     0.4400    0.0813   0.1577
educ             10.3459       10.2354          0.0550     0.4959    0.0347   0.1114
raceblack         0.8432        0.2028          1.7615          .    0.6404   0.6404
racehispan        0.0595        0.1422         -0.3498          .    0.0827   0.0827
racewhite         0.0973        0.6550         -1.8819          .    0.5577   0.5577
married           0.1892        0.5128         -0.8263          .    0.3236   0.3236
nodegree          0.7081        0.5967          0.2450          .    0.1114   0.1114
re74           2095.5737     5619.2365         -0.7211     0.5181    0.2248   0.4470
re75           1532.0553     2466.4844         -0.2903     0.9563    0.1342   0.2876

Sample Sizes:
          Control Treated
All           429     185
Matched       429     185
Unmatched       0       0
Discarded       0       0
## Love plot before matching
plot(summary(m.out0), abs = F)

## Default thresholds: solid line 0.1, dashed line 0.05

Drop control and treated units that are out of the estimated propenstiy score range

library(ggplot2)
temp.data <- data.frame(lps = lps, treated = as.factor(lalonde$treat))
ggplot(temp.data, aes(x = lps, fill = treated, color = treated)) + 
  geom_histogram(alpha = 0.5, position = "identity") + 
  xlab("Linearized propensity score") 


idx.treated <- which((lalonde$treat == 1) & (lps > max(lps[lalonde$treat == 0])))
idx.control <- which((lalonde$treat == 0) & (lps < min(lps[lalonde$treat == 1])))
idx <- c(idx.treated, idx.control)  ## dropped two treated units and 77 control units
lalonde <- lalonde[-idx, ]
lps <- lps[-idx]

From the histogram, we see a potential issue here, which is that there are not enough controls that can be potentially matched with the treated units for units whose lps > 0.

Matching

Greedy algorithm, covariate balancing is not satisfying

## Greedy algorithm
m.out1 <- matchit(treat ~ age + educ + race + married + 
                   nodegree + re74 + re75, data = lalonde,
                  estimand = "ATT", 
                 method = "nearest", distance = lps)
plot(summary(m.out1), abs = F)

We change to optimal matching, and covariate balancing is still not satisfying

## Optimal matching algorithm
## install additional package
##install.packages("optmatch") and choose the binary version
library("optmatch")

Attaching package: ‘optmatch’

The following object is masked from ‘package:survival’:

    strata
m.out2 <- matchit(treat ~ age + educ + race + married + 
                   nodegree + re74 + re75, data = lalonde,
                  estimand = "ATT", 
                 method = "optimal", distance = lps)
plot(summary(m.out2), abs = F)

You see that even the linearized propensity score are not matched well, which indicates that some treated units are not able to be well matched (as there are not enough controls with lps > 0).

Three strategies to improve balancing:

## Strategy I: require exact match for race, as race seems to be the most unbalanced covariate and is discrete
m.out3 <- matchit(treat ~ age + educ + race + married + 
                   nodegree + re74 + re75, data = lalonde,
                  estimand = "ATT", exact = "race",
                 method = "optimal", distance = lps)
Warning: Fewer control units than treated units in some `exact` strata; not all treated units will get a match.
summary(m.out3)

Call:
matchit(formula = treat ~ age + educ + race + married + nodegree + 
    re74 + re75, data = lalonde, method = "optimal", distance = lps, 
    estimand = "ATT", exact = "race")

Summary of Balance for All Data:
           Means Treated Means Control Std. Mean Diff. Var. Ratio eCDF Mean eCDF Max
distance          0.2259       -1.8038          1.9434     0.4496    0.3409   0.6040
age              25.8197       26.4091         -0.0819     0.4847    0.0685   0.1514
educ             10.3279       10.1193          0.1041     0.4802    0.0372   0.1027
raceblack         0.8415        0.2472          1.6276          .    0.5944   0.5944
racehispan        0.0601        0.1733         -0.4762          .    0.1132   0.1132
racewhite         0.0984        0.5795         -1.6158          .    0.4812   0.4812
married           0.1858        0.4205         -0.6033          .    0.2347   0.2347
nodegree          0.7104        0.6335          0.1694          .    0.0769   0.0769
re74           1785.3081     3243.4437         -0.3770     0.7722    0.1575   0.3977
re75           1448.6596     1860.5826         -0.1318     1.3614    0.0915   0.2458

Summary of Balance for Matched Data:
           Means Treated Means Control Std. Mean Diff. Var. Ratio eCDF Mean eCDF Max
distance         -0.0701       -0.1097          0.0379     1.0038    0.0095   0.0948
age              26.0086       26.2931         -0.0395     0.4074    0.0929   0.2241
educ             10.4741       10.0431          0.2152     0.3270    0.0517   0.1466
raceblack         0.7500        0.7500          0.0000          .    0.0000   0.0000
racehispan        0.0948        0.0948          0.0000          .    0.0000   0.0000
racewhite         0.1552        0.1552          0.0000          .    0.0000   0.0000
married           0.2328        0.2931         -0.1552          .    0.0603   0.0603
nodegree          0.7069        0.6466          0.1330          .    0.0603   0.0603
re74           2261.7502     2786.3308         -0.1356     0.6877    0.0323   0.1293
re75           2073.3520     1608.2498          0.1488     1.4552    0.0724   0.1552
           Std. Pair Dist.
distance            0.0442
age                 1.1684
educ                1.3341
raceblack           0.0000
racehispan          0.0000
racewhite           0.0000
married             0.1995
nodegree            0.7792
re74                0.5037
re75                0.5826

Sample Sizes:
          Control Treated
All           352     183
Matched       116     116
Unmatched     236      67
Discarded       0       0
plot(summary(m.out3), abs = F)

Strategy II: we can to improve balancing by discard units if the distance between pairs are two large

head(m.out2$match.matrix)
     [,1]     
NSW1 "PSID271"
NSW2 "PSID185"
NSW3 "PSID388"
NSW4 "PSID386"
NSW5 "PSID372"
NSW6 "PSID370"
names(lps) <- rownames(lalonde)
dists <- lps[rownames(m.out2$match.matrix)] - lps[m.out2$match.matrix[,1]]
hist(dists, main = "Histogram of distances between matched pairs")

## We see that some distances are large.

## We set a threshold 1 to make a balance between removing poor matches and retain most of the treated units
ID.treated.notmatched <- names(dists[abs(dists) > 1])
lalonde.new <- lalonde[!(rownames(lalonde) %in% ID.treated.notmatched),]
lps.new <- lps[!(rownames(lalonde) %in% ID.treated.notmatched)]

m.out4 <- matchit(treat ~ age + educ + race + married + 
                   nodegree + re74 + re75, data = lalonde.new,
                  estimand = "ATT", 
                 method = "optimal", distance = lps.new)
plot(summary(m.out4), abs = F)

summary(m.out4)

Call:
matchit(formula = treat ~ age + educ + race + married + nodegree + 
    re74 + re75, data = lalonde.new, method = "optimal", distance = lps.new, 
    estimand = "ATT")

Summary of Balance for All Data:
           Means Treated Means Control Std. Mean Diff. Var. Ratio eCDF Mean eCDF Max
distance          0.0178       -1.8038          1.4298     0.6690    0.3048   0.5148
age              25.6727       26.4091         -0.1050     0.4602    0.0689   0.1483
educ             10.2909       10.1193          0.0871     0.4641    0.0379   0.1011
raceblack         0.7364        0.2472          1.1103          .    0.4892   0.4892
racehispan        0.1000        0.1733         -0.2443          .    0.0733   0.0733
racewhite         0.1636        0.5795         -1.1242          .    0.4159   0.4159
married           0.1545        0.4205         -0.7356          .    0.2659   0.2659
nodegree          0.7182        0.6335          0.1882          .    0.0847   0.0847
re74           1209.8659     3243.4437         -0.5896     0.6141    0.2191   0.4818
re75           1187.4235     1860.5826         -0.2158     1.3561    0.1407   0.3301

Summary of Balance for Matched Data:
           Means Treated Means Control Std. Mean Diff. Var. Ratio eCDF Mean eCDF Max
distance          0.0178       -0.0923          0.0865     1.0704    0.0261   0.2727
age              25.6727       25.7273         -0.0078     0.4029    0.0914   0.2273
educ             10.2909        9.9455          0.1754     0.3844    0.0478   0.1182
raceblack         0.7364        0.7364          0.0000          .    0.0000   0.0000
racehispan        0.1000        0.0818          0.0606          .    0.0182   0.0182
racewhite         0.1636        0.1818         -0.0491          .    0.0182   0.0182
married           0.1545        0.2455         -0.2515          .    0.0909   0.0909
nodegree          0.7182        0.6545          0.1415          .    0.0636   0.0636
re74           1209.8659     2086.6191         -0.2542     0.6268    0.0901   0.2818
re75           1187.4235     1222.3671         -0.0112     1.3399    0.0224   0.1091
           Std. Pair Dist.
distance            0.0870
age                 1.3358
educ                1.3203
raceblack           0.0000
racehispan          0.0606
racewhite           0.0491
married             0.3018
nodegree            0.9093
re74                0.5885
re75                0.5532

Sample Sizes:
          Control Treated
All           352     110
Matched       110     110
Unmatched     242       0
Discarded       0       0

Covariate balancing improves. However, notice that because we have removed more than 1/3 of of the treated units, the treated population may have changed dramastically. The ATT we estimate here can be biased for the ATT of the original population.

Strategy III: In the software tutorial, it uses another method called “optimal full matching” and reaches extremely good balancing. It assigns every treated and control unit in the sample to one subclass each (Hansen 2004; Stuart and Green 2008). Each subclass contains one treated unit and one or more control units or one control units and one or more treated units. Here it performs better than optimal matching, as full matching allows one control be matched with many treated units.

We can also use matching with replacement here, which does a similar job.

## We match each treated with 2 controls to increase stability (as some controls may be used multiple times)
m.out5 <- matchit(treat ~ age + educ + race + married + 
                   nodegree + re74 + re75, data = lalonde,
                  estimand = "ATT", replace= T, ratio = 2,
                 method = "nearest", distance = lps)
plot(summary(m.out5), abs = F)

Actually, for matching with replacement you can change the propensity score estimation method to the simple logistic regression using all covariates as linear terms, and you will see an even better covariate balancing result.

m.out6 <- matchit(treat ~ age + educ + race + married + 
                   nodegree + re74 + re75, data = lalonde,
                  estimand = "ATT", replace= T, ratio = 2,
                 method = "nearest", distance = "glm") 
plot(summary(m.out6), abs = F)

estimate the ATT

We can continue with either m.out3 or m.out6.

m.data <- match.data(m.out3)
head(m.data)

## Neyman's approach, treating the data as from a pairwise randomized experiment
tau_hat_vec <- sapply(levels(m.data$subclass), function(sc) {
  treated <- m.data$re78[m.data$subclass == sc & m.data$treat == 1]
  control <- m.data$re78[m.data$subclass == sc & m.data$treat == 0]
  return(treated - control)
})

tau_hat <- mean(tau_hat_vec, na.rm = T)
sd_tau_hat <- sd(tau_hat_vec)/sqrt(length(tau_hat_vec))
print(c(tau_hat, sd_tau_hat))
[1] 1461.558 1055.290
  
## 95% CI
print(c(tau_hat- 1.96 * sd_tau_hat, tau_hat + 1.96 * sd_tau_hat))
[1] -606.8106 3529.9267

Neyman’s approach with regression adjustment of the bias

## First run a linear regression on the control (remember to remove the treatment assignment variable!)

fit0 <- lm(re78 ~ age + educ + race + married + nodegree + 
             re74 + re75, data = m.data[m.data$treat == 0, ])

m.data$predicted_y0 <- predict(fit0, m.data)

## Neyman's approach with regression adjustment
tau_hat_vec_adjusted <- sapply(levels(m.data$subclass), function(sc) {
  treated <- m.data$re78[m.data$subclass == sc & m.data$treat == 1]
  control <- m.data$re78[m.data$subclass == sc & m.data$treat == 0]
  
  bias <- m.data$predicted_y0[m.data$subclass == sc & m.data$treat == 1] - 
    m.data$predicted_y0[m.data$subclass == sc & m.data$treat == 0]
  control.adjusted <- control + bias
    
  return(treated - control.adjusted)
})

tau_hat_adjusted <- mean(tau_hat_vec_adjusted)
sd_tau_hat_adjusted <- sd(tau_hat_vec_adjusted)/sqrt(length(tau_hat_vec_adjusted))
print(c(tau_hat_adjusted, sd_tau_hat_adjusted))
  
## 95% CI
print(c(tau_hat_adjusted- 1.96 * sd_tau_hat_adjusted, tau_hat_adjusted + 1.96 * sd_tau_hat_adjusted))

Run outcome regression directly:

fit <- lm(re78 ~ treat + age + educ + race + married + nodegree + 
             re74 + re75, data = m.data, weights = m.data$weights)
summary(fit)

Results are similar to the regression adjustment of bias.

m.data <- match.data(m.out6)
head(m.out6$match.matrix)

## Neyman's approach 
tau_hat_vec <- sapply(rownames(m.out6$match.matrix), function(ID) {
  treated <- m.data[ID,]$re78
  control <- m.data[m.out6$match.matrix[ID,1],]$re78
  return(treated - control)
})


tau_hat <- mean(tau_hat_vec, na.rm = T)

sd_tau_hat <- sd(tau_hat_vec)/sqrt(length(tau_hat_vec))
print(c(tau_hat, sd_tau_hat))
  
## 95% CI
print(c(tau_hat- 1.96 * sd_tau_hat, tau_hat + 1.96 * sd_tau_hat))

Neyman’s approach with regression adjustment of the bias

## First run a linear regression on the control (remember to remove the treatment assignment variable!)

fit0 <- lm(re78 ~ age + educ + race + married + nodegree + 
             re74 + re75, data = m.data[m.data$treat == 0, ])

m.data$predicted_y0 <- predict(fit0, m.data)

## Neyman's approach with regression adjustment
tau_hat_vec_adjusted <- sapply(rownames(m.out6$match.matrix), function(ID) {
  treated <- m.data[ID,]$re78
  control <- m.data[m.out6$match.matrix[ID,1],]$re78
  
  bias <- m.data[ID,]$predicted_y0 - 
    m.data[m.out6$match.matrix[ID,1],]$predicted_y0
  control.adjusted <- control + bias
    
  return(treated - control.adjusted)
})

tau_hat_adjusted <- mean(tau_hat_vec_adjusted)
sd_tau_hat_adjusted <- sd(tau_hat_vec_adjusted)/sqrt(length(tau_hat_vec_adjusted))
print(c(tau_hat_adjusted, sd_tau_hat_adjusted))
  
## 95% CI
print(c(tau_hat_adjusted- 1.96 * sd_tau_hat_adjusted, tau_hat_adjusted + 1.96 * sd_tau_hat_adjusted))

Results are different because:

LS0tCnRpdGxlOiAiRXhhbXBsZSA2OiBtYXRjaGluZyB1c2luZyBNYXRjaEl0IgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgpXZSBjb250aW51ZSBhbmFseXppbmcgdGhlIGxhbG9uZGUgZGF0YSBvYnRhaW5lZCBmcm9tIHRoZSBNYXRjaEl0IHBhY2thZ2UuIFdlIGVzdGltYXRlIHRoZSBwcm9wZW5zaXR5IHNjb3JlcyB1c2luZyB0aGUgc2VsZWN0ZWQgbG9nc3RpYyByZWdyZXNzaW9uIG1vZGVsIGluIFIgRXhhbXBsZSA1ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIAoKYGBge3J9CmxpYnJhcnkoIk1hdGNoSXQiKQpkYXRhKCJsYWxvbmRlIikKCm1vZGVsIDwtIGdsbSh0cmVhdCB+IHJlNzQgKyByYWNlICsgbWFycmllZCArIEkocmU3NF4yKSArIHJlNzQ6cmFjZSwgZGF0YSA9IGxhbG9uZGUsIGZhbWlseSA9ICJiaW5vbWlhbCIpCmVwcyA8LSBwcmVkaWN0KG1vZGVsLCB0eXBlID0gInJlc3BvbnNlIikKbHBzIDwtIHByZWRpY3QobW9kZWwpCmBgYAoKIyMgQXNzZXNzIGluaXRpYWwgaW1iYWxhbmNlCgpgYGB7cn0KbS5vdXQwIDwtIG1hdGNoaXQodHJlYXQgfiBhZ2UgKyBlZHVjICsgcmFjZSArIG1hcnJpZWQgKyAKICAgICAgICAgICAgICAgICAgIG5vZGVncmVlICsgcmU3NCArIHJlNzUsIGRhdGEgPSBsYWxvbmRlLAogICAgICAgICAgICAgICAgIG1ldGhvZCA9IE5VTEwsIGRpc3RhbmNlID0gImdsbSIpCiMjIGRpc3RhbmNlIGhlcmUgcmVmZXIgdG8gYSBtZXRob2QgdG8gZXN0aW1hdGUgdGhlIHByb3BlbnNpdHkgc2NvcmUKIyMgTm8gbWF0Y2hpbmcgaXMgcGVyZm9ybWVkIGF0IHRoaXMgc3RhZ2UKc3VtbWFyeShtLm91dDApCmBgYAoKYGBge3J9CiMjIExvdmUgcGxvdCBiZWZvcmUgbWF0Y2hpbmcKcGxvdChzdW1tYXJ5KG0ub3V0MCksIGFicyA9IEYpCiMjIERlZmF1bHQgdGhyZXNob2xkczogc29saWQgbGluZSAwLjEsIGRhc2hlZCBsaW5lIDAuMDUKYGBgCgoKCgojIyBEcm9wIGNvbnRyb2wgYW5kIHRyZWF0ZWQgdW5pdHMgdGhhdCBhcmUgb3V0IG9mIHRoZSBlc3RpbWF0ZWQgcHJvcGVuc3RpeSBzY29yZSByYW5nZQpgYGB7cn0KbGlicmFyeShnZ3Bsb3QyKQp0ZW1wLmRhdGEgPC0gZGF0YS5mcmFtZShscHMgPSBscHMsIHRyZWF0ZWQgPSBhcy5mYWN0b3IobGFsb25kZSR0cmVhdCkpCmdncGxvdCh0ZW1wLmRhdGEsIGFlcyh4ID0gbHBzLCBmaWxsID0gdHJlYXRlZCwgY29sb3IgPSB0cmVhdGVkKSkgKyAKICBnZW9tX2hpc3RvZ3JhbShhbHBoYSA9IDAuNSwgcG9zaXRpb24gPSAiaWRlbnRpdHkiKSArIAogIHhsYWIoIkxpbmVhcml6ZWQgcHJvcGVuc2l0eSBzY29yZSIpIAoKaWR4LnRyZWF0ZWQgPC0gd2hpY2goKGxhbG9uZGUkdHJlYXQgPT0gMSkgJiAobHBzID4gbWF4KGxwc1tsYWxvbmRlJHRyZWF0ID09IDBdKSkpCmlkeC5jb250cm9sIDwtIHdoaWNoKChsYWxvbmRlJHRyZWF0ID09IDApICYgKGxwcyA8IG1pbihscHNbbGFsb25kZSR0cmVhdCA9PSAxXSkpKQppZHggPC0gYyhpZHgudHJlYXRlZCwgaWR4LmNvbnRyb2wpICAjIyBkcm9wcGVkIHR3byB0cmVhdGVkIHVuaXRzIGFuZCA3NyBjb250cm9sIHVuaXRzCmxhbG9uZGUgPC0gbGFsb25kZVstaWR4LCBdCmxwcyA8LSBscHNbLWlkeF0KYGBgCkZyb20gdGhlIGhpc3RvZ3JhbSwgd2Ugc2VlIGEgcG90ZW50aWFsIGlzc3VlIGhlcmUsIHdoaWNoIGlzIHRoYXQgdGhlcmUgYXJlIG5vdCBlbm91Z2ggY29udHJvbHMgdGhhdCBjYW4gYmUgcG90ZW50aWFsbHkgbWF0Y2hlZCB3aXRoIHRoZSB0cmVhdGVkIHVuaXRzIGZvciB1bml0cyB3aG9zZSBscHMgPiAwLiAKCiMjIE1hdGNoaW5nCgpHcmVlZHkgYWxnb3JpdGhtLCBjb3ZhcmlhdGUgYmFsYW5jaW5nIGlzIG5vdCBzYXRpc2Z5aW5nIApgYGB7cn0KIyMgR3JlZWR5IGFsZ29yaXRobQptLm91dDEgPC0gbWF0Y2hpdCh0cmVhdCB+IGFnZSArIGVkdWMgKyByYWNlICsgbWFycmllZCArIAogICAgICAgICAgICAgICAgICAgbm9kZWdyZWUgKyByZTc0ICsgcmU3NSwgZGF0YSA9IGxhbG9uZGUsCiAgICAgICAgICAgICAgICAgIGVzdGltYW5kID0gIkFUVCIsIAogICAgICAgICAgICAgICAgIG1ldGhvZCA9ICJuZWFyZXN0IiwgZGlzdGFuY2UgPSBscHMpCnBsb3Qoc3VtbWFyeShtLm91dDEpLCBhYnMgPSBGKQpgYGAKCgpXZSBjaGFuZ2UgdG8gb3B0aW1hbCBtYXRjaGluZywgYW5kIGNvdmFyaWF0ZSBiYWxhbmNpbmcgaXMgc3RpbGwgbm90IHNhdGlzZnlpbmcgCmBgYHtyfQojIyBPcHRpbWFsIG1hdGNoaW5nIGFsZ29yaXRobQojIyBpbnN0YWxsIGFkZGl0aW9uYWwgcGFja2FnZQojI2luc3RhbGwucGFja2FnZXMoIm9wdG1hdGNoIikgYW5kIGNob29zZSB0aGUgYmluYXJ5IHZlcnNpb24KbGlicmFyeSgib3B0bWF0Y2giKQptLm91dDIgPC0gbWF0Y2hpdCh0cmVhdCB+IGFnZSArIGVkdWMgKyByYWNlICsgbWFycmllZCArIAogICAgICAgICAgICAgICAgICAgbm9kZWdyZWUgKyByZTc0ICsgcmU3NSwgZGF0YSA9IGxhbG9uZGUsCiAgICAgICAgICAgICAgICAgIGVzdGltYW5kID0gIkFUVCIsIAogICAgICAgICAgICAgICAgIG1ldGhvZCA9ICJvcHRpbWFsIiwgZGlzdGFuY2UgPSBscHMpCnBsb3Qoc3VtbWFyeShtLm91dDIpLCBhYnMgPSBGKQpgYGAKCllvdSBzZWUgdGhhdCBldmVuIHRoZSBsaW5lYXJpemVkIHByb3BlbnNpdHkgc2NvcmUgYXJlIG5vdCBtYXRjaGVkIHdlbGwsIHdoaWNoIGluZGljYXRlcyB0aGF0IHNvbWUgdHJlYXRlZCB1bml0cyBhcmUgbm90IGFibGUgdG8gYmUgd2VsbCBtYXRjaGVkIChhcyB0aGVyZSBhcmUgbm90IGVub3VnaCBjb250cm9scyB3aXRoIGxwcyA+IDApLiAKClRocmVlIHN0cmF0ZWdpZXMgdG8gaW1wcm92ZSBiYWxhbmNpbmc6CgpgYGB7cn0KIyMgU3RyYXRlZ3kgSTogcmVxdWlyZSBleGFjdCBtYXRjaCBmb3IgcmFjZSwgYXMgcmFjZSBzZWVtcyB0byBiZSB0aGUgbW9zdCB1bmJhbGFuY2VkIGNvdmFyaWF0ZSBhbmQgaXMgZGlzY3JldGUKbS5vdXQzIDwtIG1hdGNoaXQodHJlYXQgfiBhZ2UgKyBlZHVjICsgcmFjZSArIG1hcnJpZWQgKyAKICAgICAgICAgICAgICAgICAgIG5vZGVncmVlICsgcmU3NCArIHJlNzUsIGRhdGEgPSBsYWxvbmRlLAogICAgICAgICAgICAgICAgICBlc3RpbWFuZCA9ICJBVFQiLCBleGFjdCA9ICJyYWNlIiwKICAgICAgICAgICAgICAgICBtZXRob2QgPSAib3B0aW1hbCIsIGRpc3RhbmNlID0gbHBzKQpzdW1tYXJ5KG0ub3V0MykKcGxvdChzdW1tYXJ5KG0ub3V0MyksIGFicyA9IEYpCmBgYAoKClN0cmF0ZWd5IElJOiB3ZSBjYW4gdG8gaW1wcm92ZSBiYWxhbmNpbmcgYnkgZGlzY2FyZCB1bml0cyBpZiB0aGUgZGlzdGFuY2UgYmV0d2VlbiBwYWlycyBhcmUgdHdvIGxhcmdlCmBgYHtyfQpoZWFkKG0ub3V0MiRtYXRjaC5tYXRyaXgpCm5hbWVzKGxwcykgPC0gcm93bmFtZXMobGFsb25kZSkKZGlzdHMgPC0gbHBzW3Jvd25hbWVzKG0ub3V0MiRtYXRjaC5tYXRyaXgpXSAtIGxwc1ttLm91dDIkbWF0Y2gubWF0cml4WywxXV0KaGlzdChkaXN0cywgbWFpbiA9ICJIaXN0b2dyYW0gb2YgZGlzdGFuY2VzIGJldHdlZW4gbWF0Y2hlZCBwYWlycyIpCiMjIFdlIHNlZSB0aGF0IHNvbWUgZGlzdGFuY2VzIGFyZSBsYXJnZS4KCiMjIFdlIHNldCBhIHRocmVzaG9sZCAxIHRvIG1ha2UgYSBiYWxhbmNlIGJldHdlZW4gcmVtb3ZpbmcgcG9vciBtYXRjaGVzIGFuZCByZXRhaW4gbW9zdCBvZiB0aGUgdHJlYXRlZCB1bml0cwpJRC50cmVhdGVkLm5vdG1hdGNoZWQgPC0gbmFtZXMoZGlzdHNbYWJzKGRpc3RzKSA+IDFdKQpsYWxvbmRlLm5ldyA8LSBsYWxvbmRlWyEocm93bmFtZXMobGFsb25kZSkgJWluJSBJRC50cmVhdGVkLm5vdG1hdGNoZWQpLF0KbHBzLm5ldyA8LSBscHNbIShyb3duYW1lcyhsYWxvbmRlKSAlaW4lIElELnRyZWF0ZWQubm90bWF0Y2hlZCldCgptLm91dDQgPC0gbWF0Y2hpdCh0cmVhdCB+IGFnZSArIGVkdWMgKyByYWNlICsgbWFycmllZCArIAogICAgICAgICAgICAgICAgICAgbm9kZWdyZWUgKyByZTc0ICsgcmU3NSwgZGF0YSA9IGxhbG9uZGUubmV3LAogICAgICAgICAgICAgICAgICBlc3RpbWFuZCA9ICJBVFQiLCAKICAgICAgICAgICAgICAgICBtZXRob2QgPSAib3B0aW1hbCIsIGRpc3RhbmNlID0gbHBzLm5ldykKcGxvdChzdW1tYXJ5KG0ub3V0NCksIGFicyA9IEYpCnN1bW1hcnkobS5vdXQ0KQpgYGAKQ292YXJpYXRlIGJhbGFuY2luZyBpbXByb3Zlcy4gSG93ZXZlciwgbm90aWNlIHRoYXQgYmVjYXVzZSB3ZSBoYXZlIHJlbW92ZWQgbW9yZSB0aGFuIDEvMyBvZiBvZiB0aGUgdHJlYXRlZCB1bml0cywgdGhlIHRyZWF0ZWQgcG9wdWxhdGlvbiBtYXkgaGF2ZSBjaGFuZ2VkIGRyYW1hc3RpY2FsbHkuIFRoZSBBVFQgd2UgZXN0aW1hdGUgaGVyZSBjYW4gYmUgYmlhc2VkIGZvciB0aGUgQVRUIG9mIHRoZSBvcmlnaW5hbCBwb3B1bGF0aW9uLgoKU3RyYXRlZ3kgSUlJOiBJbiB0aGUgc29mdHdhcmUgdHV0b3JpYWwsIGl0IHVzZXMgYW5vdGhlciBtZXRob2QgY2FsbGVkICJvcHRpbWFsIGZ1bGwgbWF0Y2hpbmciIGFuZCByZWFjaGVzIGV4dHJlbWVseSBnb29kIGJhbGFuY2luZy4gSXQgYXNzaWducyBldmVyeSB0cmVhdGVkIGFuZCBjb250cm9sIHVuaXQgaW4gdGhlIHNhbXBsZSB0byBvbmUgc3ViY2xhc3MgZWFjaCAoSGFuc2VuIDIwMDQ7IFN0dWFydCBhbmQgR3JlZW4gMjAwOCkuIEVhY2ggc3ViY2xhc3MgY29udGFpbnMgb25lIHRyZWF0ZWQgdW5pdCBhbmQgb25lIG9yIG1vcmUgY29udHJvbCB1bml0cyBvciBvbmUgY29udHJvbCB1bml0cyBhbmQgb25lIG9yIG1vcmUgdHJlYXRlZCB1bml0cy4gSGVyZSBpdCBwZXJmb3JtcyBiZXR0ZXIgdGhhbiBvcHRpbWFsIG1hdGNoaW5nLCBhcyBmdWxsIG1hdGNoaW5nIGFsbG93cyBvbmUgY29udHJvbCBiZSBtYXRjaGVkIHdpdGggbWFueSB0cmVhdGVkIHVuaXRzLiAKCldlIGNhbiBhbHNvIHVzZSBtYXRjaGluZyB3aXRoIHJlcGxhY2VtZW50IGhlcmUsIHdoaWNoIGRvZXMgYSBzaW1pbGFyIGpvYi4KCmBgYHtyfQojIyBXZSBtYXRjaCBlYWNoIHRyZWF0ZWQgd2l0aCAyIGNvbnRyb2xzIHRvIGluY3JlYXNlIHN0YWJpbGl0eSAoYXMgc29tZSBjb250cm9scyBtYXkgYmUgdXNlZCBtdWx0aXBsZSB0aW1lcykKbS5vdXQ1IDwtIG1hdGNoaXQodHJlYXQgfiBhZ2UgKyBlZHVjICsgcmFjZSArIG1hcnJpZWQgKyAKICAgICAgICAgICAgICAgICAgIG5vZGVncmVlICsgcmU3NCArIHJlNzUsIGRhdGEgPSBsYWxvbmRlLAogICAgICAgICAgICAgICAgICBlc3RpbWFuZCA9ICJBVFQiLCByZXBsYWNlPSBULCByYXRpbyA9IDIsCiAgICAgICAgICAgICAgICAgbWV0aG9kID0gIm5lYXJlc3QiLCBkaXN0YW5jZSA9IGxwcykKcGxvdChzdW1tYXJ5KG0ub3V0NSksIGFicyA9IEYpCmBgYAoKCkFjdHVhbGx5LCBmb3IgbWF0Y2hpbmcgd2l0aCByZXBsYWNlbWVudCB5b3UgY2FuIGNoYW5nZSB0aGUgcHJvcGVuc2l0eSBzY29yZSBlc3RpbWF0aW9uIG1ldGhvZCB0byB0aGUgc2ltcGxlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gdXNpbmcgYWxsIGNvdmFyaWF0ZXMgYXMgbGluZWFyIHRlcm1zLCBhbmQgeW91IHdpbGwgc2VlIGFuIGV2ZW4gYmV0dGVyIGNvdmFyaWF0ZSBiYWxhbmNpbmcgcmVzdWx0LiAKCmBgYHtyfQptLm91dDYgPC0gbWF0Y2hpdCh0cmVhdCB+IGFnZSArIGVkdWMgKyByYWNlICsgbWFycmllZCArIAogICAgICAgICAgICAgICAgICAgbm9kZWdyZWUgKyByZTc0ICsgcmU3NSwgZGF0YSA9IGxhbG9uZGUsCiAgICAgICAgICAgICAgICAgIGVzdGltYW5kID0gIkFUVCIsIHJlcGxhY2U9IFQsIHJhdGlvID0gMiwKICAgICAgICAgICAgICAgICBtZXRob2QgPSAibmVhcmVzdCIsIGRpc3RhbmNlID0gImdsbSIpIApwbG90KHN1bW1hcnkobS5vdXQ2KSwgYWJzID0gRikKYGBgCgoKIyMgZXN0aW1hdGUgdGhlIEFUVAoKV2UgY2FuIGNvbnRpbnVlIHdpdGggZWl0aGVyIG0ub3V0MyBvciBtLm91dDYuIAoKLSBJZiB3ZSBjb250aW51ZSB3aXRoIG0ub3V0MzoKCmBgYHtyfQptLmRhdGEgPC0gbWF0Y2guZGF0YShtLm91dDMpCmhlYWQobS5kYXRhKQoKIyMgTmV5bWFuJ3MgYXBwcm9hY2gsIHRyZWF0aW5nIHRoZSBkYXRhIGFzIGZyb20gYSBwYWlyd2lzZSByYW5kb21pemVkIGV4cGVyaW1lbnQKdGF1X2hhdF92ZWMgPC0gc2FwcGx5KGxldmVscyhtLmRhdGEkc3ViY2xhc3MpLCBmdW5jdGlvbihzYykgewogIHRyZWF0ZWQgPC0gbS5kYXRhJHJlNzhbbS5kYXRhJHN1YmNsYXNzID09IHNjICYgbS5kYXRhJHRyZWF0ID09IDFdCiAgY29udHJvbCA8LSBtLmRhdGEkcmU3OFttLmRhdGEkc3ViY2xhc3MgPT0gc2MgJiBtLmRhdGEkdHJlYXQgPT0gMF0KICByZXR1cm4odHJlYXRlZCAtIGNvbnRyb2wpCn0pCgp0YXVfaGF0IDwtIG1lYW4odGF1X2hhdF92ZWMsIG5hLnJtID0gVCkKc2RfdGF1X2hhdCA8LSBzZCh0YXVfaGF0X3ZlYykvc3FydChsZW5ndGgodGF1X2hhdF92ZWMpKQpwcmludChjKHRhdV9oYXQsIHNkX3RhdV9oYXQpKQogIAojIyA5NSUgQ0kKcHJpbnQoYyh0YXVfaGF0LSAxLjk2ICogc2RfdGF1X2hhdCwgdGF1X2hhdCArIDEuOTYgKiBzZF90YXVfaGF0KSkKYGBgCgpOZXltYW4ncyBhcHByb2FjaCB3aXRoIHJlZ3Jlc3Npb24gYWRqdXN0bWVudCBvZiB0aGUgYmlhcwoKYGBge3J9CiMjIEZpcnN0IHJ1biBhIGxpbmVhciByZWdyZXNzaW9uIG9uIHRoZSBjb250cm9sIChyZW1lbWJlciB0byByZW1vdmUgdGhlIHRyZWF0bWVudCBhc3NpZ25tZW50IHZhcmlhYmxlISkKCmZpdDAgPC0gbG0ocmU3OCB+IGFnZSArIGVkdWMgKyByYWNlICsgbWFycmllZCArIG5vZGVncmVlICsgCiAgICAgICAgICAgICByZTc0ICsgcmU3NSwgZGF0YSA9IG0uZGF0YVttLmRhdGEkdHJlYXQgPT0gMCwgXSkKCm0uZGF0YSRwcmVkaWN0ZWRfeTAgPC0gcHJlZGljdChmaXQwLCBtLmRhdGEpCgojIyBOZXltYW4ncyBhcHByb2FjaCB3aXRoIHJlZ3Jlc3Npb24gYWRqdXN0bWVudAp0YXVfaGF0X3ZlY19hZGp1c3RlZCA8LSBzYXBwbHkobGV2ZWxzKG0uZGF0YSRzdWJjbGFzcyksIGZ1bmN0aW9uKHNjKSB7CiAgdHJlYXRlZCA8LSBtLmRhdGEkcmU3OFttLmRhdGEkc3ViY2xhc3MgPT0gc2MgJiBtLmRhdGEkdHJlYXQgPT0gMV0KICBjb250cm9sIDwtIG0uZGF0YSRyZTc4W20uZGF0YSRzdWJjbGFzcyA9PSBzYyAmIG0uZGF0YSR0cmVhdCA9PSAwXQogIAogIGJpYXMgPC0gbS5kYXRhJHByZWRpY3RlZF95MFttLmRhdGEkc3ViY2xhc3MgPT0gc2MgJiBtLmRhdGEkdHJlYXQgPT0gMV0gLSAKICAgIG0uZGF0YSRwcmVkaWN0ZWRfeTBbbS5kYXRhJHN1YmNsYXNzID09IHNjICYgbS5kYXRhJHRyZWF0ID09IDBdCiAgY29udHJvbC5hZGp1c3RlZCA8LSBjb250cm9sICsgYmlhcwogICAgCiAgcmV0dXJuKHRyZWF0ZWQgLSBjb250cm9sLmFkanVzdGVkKQp9KQoKdGF1X2hhdF9hZGp1c3RlZCA8LSBtZWFuKHRhdV9oYXRfdmVjX2FkanVzdGVkKQpzZF90YXVfaGF0X2FkanVzdGVkIDwtIHNkKHRhdV9oYXRfdmVjX2FkanVzdGVkKS9zcXJ0KGxlbmd0aCh0YXVfaGF0X3ZlY19hZGp1c3RlZCkpCnByaW50KGModGF1X2hhdF9hZGp1c3RlZCwgc2RfdGF1X2hhdF9hZGp1c3RlZCkpCiAgCiMjIDk1JSBDSQpwcmludChjKHRhdV9oYXRfYWRqdXN0ZWQtIDEuOTYgKiBzZF90YXVfaGF0X2FkanVzdGVkLCB0YXVfaGF0X2FkanVzdGVkICsgMS45NiAqIHNkX3RhdV9oYXRfYWRqdXN0ZWQpKQpgYGAKClJ1biBvdXRjb21lIHJlZ3Jlc3Npb24gZGlyZWN0bHk6CmBgYHtyfQpmaXQgPC0gbG0ocmU3OCB+IHRyZWF0ICsgYWdlICsgZWR1YyArIHJhY2UgKyBtYXJyaWVkICsgbm9kZWdyZWUgKyAKICAgICAgICAgICAgIHJlNzQgKyByZTc1LCBkYXRhID0gbS5kYXRhLCB3ZWlnaHRzID0gbS5kYXRhJHdlaWdodHMpCnN1bW1hcnkoZml0KQpgYGAKUmVzdWx0cyBhcmUgc2ltaWxhciB0byB0aGUgcmVncmVzc2lvbiBhZGp1c3RtZW50IG9mIGJpYXMuCgotIElmIHdlIGNvbnRpbnVlIHdpdGggbS5kYXRhNgpgYGB7cn0KbS5kYXRhIDwtIG1hdGNoLmRhdGEobS5vdXQ2KQpoZWFkKG0ub3V0NiRtYXRjaC5tYXRyaXgpCgojIyBOZXltYW4ncyBhcHByb2FjaCAKdGF1X2hhdF92ZWMgPC0gc2FwcGx5KHJvd25hbWVzKG0ub3V0NiRtYXRjaC5tYXRyaXgpLCBmdW5jdGlvbihJRCkgewogIHRyZWF0ZWQgPC0gbS5kYXRhW0lELF0kcmU3OAogIGNvbnRyb2wgPC0gbS5kYXRhW20ub3V0NiRtYXRjaC5tYXRyaXhbSUQsMV0sXSRyZTc4CiAgcmV0dXJuKHRyZWF0ZWQgLSBjb250cm9sKQp9KQoKCnRhdV9oYXQgPC0gbWVhbih0YXVfaGF0X3ZlYywgbmEucm0gPSBUKQoKc2RfdGF1X2hhdCA8LSBzZCh0YXVfaGF0X3ZlYykvc3FydChsZW5ndGgodGF1X2hhdF92ZWMpKQpwcmludChjKHRhdV9oYXQsIHNkX3RhdV9oYXQpKQogIAojIyA5NSUgQ0kKcHJpbnQoYyh0YXVfaGF0LSAxLjk2ICogc2RfdGF1X2hhdCwgdGF1X2hhdCArIDEuOTYgKiBzZF90YXVfaGF0KSkKYGBgCgpOZXltYW4ncyBhcHByb2FjaCB3aXRoIHJlZ3Jlc3Npb24gYWRqdXN0bWVudCBvZiB0aGUgYmlhcwoKYGBge3J9CiMjIEZpcnN0IHJ1biBhIGxpbmVhciByZWdyZXNzaW9uIG9uIHRoZSBjb250cm9sIChyZW1lbWJlciB0byByZW1vdmUgdGhlIHRyZWF0bWVudCBhc3NpZ25tZW50IHZhcmlhYmxlISkKCmZpdDAgPC0gbG0ocmU3OCB+IGFnZSArIGVkdWMgKyByYWNlICsgbWFycmllZCArIG5vZGVncmVlICsgCiAgICAgICAgICAgICByZTc0ICsgcmU3NSwgZGF0YSA9IG0uZGF0YVttLmRhdGEkdHJlYXQgPT0gMCwgXSkKCm0uZGF0YSRwcmVkaWN0ZWRfeTAgPC0gcHJlZGljdChmaXQwLCBtLmRhdGEpCgojIyBOZXltYW4ncyBhcHByb2FjaCB3aXRoIHJlZ3Jlc3Npb24gYWRqdXN0bWVudAp0YXVfaGF0X3ZlY19hZGp1c3RlZCA8LSBzYXBwbHkocm93bmFtZXMobS5vdXQ2JG1hdGNoLm1hdHJpeCksIGZ1bmN0aW9uKElEKSB7CiAgdHJlYXRlZCA8LSBtLmRhdGFbSUQsXSRyZTc4CiAgY29udHJvbCA8LSBtLmRhdGFbbS5vdXQ2JG1hdGNoLm1hdHJpeFtJRCwxXSxdJHJlNzgKICAKICBiaWFzIDwtIG0uZGF0YVtJRCxdJHByZWRpY3RlZF95MCAtIAogICAgbS5kYXRhW20ub3V0NiRtYXRjaC5tYXRyaXhbSUQsMV0sXSRwcmVkaWN0ZWRfeTAKICBjb250cm9sLmFkanVzdGVkIDwtIGNvbnRyb2wgKyBiaWFzCiAgICAKICByZXR1cm4odHJlYXRlZCAtIGNvbnRyb2wuYWRqdXN0ZWQpCn0pCgp0YXVfaGF0X2FkanVzdGVkIDwtIG1lYW4odGF1X2hhdF92ZWNfYWRqdXN0ZWQpCnNkX3RhdV9oYXRfYWRqdXN0ZWQgPC0gc2QodGF1X2hhdF92ZWNfYWRqdXN0ZWQpL3NxcnQobGVuZ3RoKHRhdV9oYXRfdmVjX2FkanVzdGVkKSkKcHJpbnQoYyh0YXVfaGF0X2FkanVzdGVkLCBzZF90YXVfaGF0X2FkanVzdGVkKSkKICAKIyMgOTUlIENJCnByaW50KGModGF1X2hhdF9hZGp1c3RlZC0gMS45NiAqIHNkX3RhdV9oYXRfYWRqdXN0ZWQsIHRhdV9oYXRfYWRqdXN0ZWQgKyAxLjk2ICogc2RfdGF1X2hhdF9hZGp1c3RlZCkpCmBgYAoKUmVzdWx0cyBhcmUgZGlmZmVyZW50IGJlY2F1c2U6CgotIG0ub3V0MyBvbmx5IGVzdGltYXRlIHRoZSBBVFQgb2YgYSBzdWJzZXQgb2YgdHJlYXRlZCB1bml0cwotIG0ub3V0NiBtYXkgaGlnaGx5IGRlcGVuZCBvbiB0aGUgb3V0Y29tZSBvZiBhIGZldyBjb250cm9scwoKCgoK