Introduction
For this assignment, we will be building different types of
bootstrapped confidence intervals to estimate the mean of a lognormal
distribution. Specifically, we will use four different types: normal,
percentile, bias-corrected and accelerated (BCa), and studentized
(asymptotic) at confidence level of 95%. For all of them, we will first
build them manually and then build them using the boot() and boot.ci()
functions from the boot package.
To compute these confidence intervals, we will need data. The data we
will be using consists of soil lead (Pb) concentrations (mg/kg) from 55
urban garden sites. In order to estimate the mean of a lognormal, we
will assume this data follows a lognormal distribution.
lead <- c(0.85, 1.23, 0.92, 3.45, 2.11, 1.56, 4.89, 2.34, 1.78, 6.72, 0.95, 1.34, 8.91, 2.67, 1.89, 5.43, 1.12, 3.78, 2.45, 7.65, 1.05, 1.45, 12.34, 2.89, 2.01, 4.56, 1.23, 4.32, 2.67, 9.87, 0.99, 1.56, 15.23, 3.12, 2.34, 3.89, 1.34, 5.67, 2.89, 11.45, 1.12, 1.67, 18.90, 3.45, 2.56, 3.45, 1.45, 6.78, 3.12, 14.56, 1.23, 1.78, 22.34, 3.78, 2.78)
Part A
For Part A, we will be constructing a normal (or standard)
bootstrapped confidence interval. For this interval, we will assume that
our bootstrap sampling distribution will follow a normal
distribution.
Manual Construction
of the Confidence Interval
First, we will manually build the confidence interval.
## Manually Building a 95% Normal Bootstrap Confidence Interval
set.seed(1) # controls randomness of sampling
# Manual Bootstrap
B <- 5000
n <- length(lead)
boot_means <- numeric(B) # Empty Vector to Store Bootstrap Sample Means
# Loop to Create Samples and Calculate Sample Means
for(b in 1:B) {
boot_sample <- sample(lead, n, replace=TRUE) # Generating bootstrap sample
boot_means[b] <- mean(boot_sample) # Calculate Bootstrap Sample Means
}
mean.samp <- mean(lead) # mean from the original sample
boot.se <- sd(boot_means) # standard error of bootstrap
z <- qnorm(0.975) # critical value for confidence interval
moe = z*boot.se # margin of error for confidence interval
# The Confidence Interval
ci_normal_manual <- c(LCL = mean.samp - moe, UCL = mean.samp + moe)
ci_normal_manual
LCL UCL
3.173717 5.621919
Our resuling confidence interval is (3.1737, 5.6219).
Constructing the
Confidence Interval with the boot Package
Next, we will use the boot() and boot.ci() functions from the
boot package to build the confidence interval.
## Calculating Bootstrap Confidence Interval Via Boot Package
set.seed(1) # still controls randomness of sampling
# creates statistic function
mean_stat <- function(data, indices) {
sample_data<- data[indices]
return(mean(sample_data))
}
# Boot function generating bootstrap sampling distribution of the mean
boot.means <- boot(lead, mean_stat, R = 5000) # generating 5000 samples
# 95% Confidence Interval for Bootstrap Sample Mean
ci_boot_normal1 <- boot.ci(boot.means, type = "norm")
ci_boot_normal1
BOOTSTRAP CONFIDENCE INTERVAL CALCULATIONS
Based on 5000 bootstrap replicates
CALL :
boot.ci(boot.out = boot.means, type = "norm")
Intervals :
Level Normal
95% ( 3.165, 5.655 )
Calculations and Intervals on Original Scale
Histogram of the
Sampling Distribution
And finally, we will plot the actual sampling distribution
itself.
# plot histogram of sampling distribution of means
hist(boot.means$t, prob = TRUE, col = "lightblue", main = "Bootstrap Sampling Distribution of Sample Means", xlab = "Sample Mean")
# Add Gaussian Density Curve of Sampling Distribution
lines(density(boot.means$t, kernel = "gaussian"), col = "red", lwd = 2)
There does appear to be some positive skew. However the skew looks a bit
exaggerated due to the graph not being centered. Other than that,
nothing looks out of the ordinary. The density curve definitely takes
shape of a bell curve thanks to the 5000 sample means we have.
TO RECAP
Our manually constructed normal bootstrap confidence interval is
(3.1737, 5.6219), and the interval constructed via the boot package is
(3.165, 5.655). I expected the intervals to differ slightly because the
sample mean differs from the bootstrap mean.
Part B
For this part, we will construct a percentile bootstrap confidence
interval. These are the simplest confidence intervals, as they are built
by directly taking the corresponding quantiles of the empirical
distribution of bootstrap sampling distribution. This method works well
when the bootstrap distribution is approximately symmetric and the
estimator has a low amount of bias.
Manually Building the
Confidence Interval
First, We will manually build this confidence interval. We will use
the same sampling distribution from earlier. Since the sampling
distribution looks roughly symmetric and we are building a 95%
confidence interval, we will calculate the 2.5% and 97.5% percentiles
and use those values as the lower and upper limits of this confidence
interval.
boot.mean.values <- boot.means$t
alpha <- 0.05 # 1 - alpha = level of confidence
# The COnfidence Interval
ci_percentile_manual <- quantile(boot.mean.values, probs=c(alpha/2, 1-alpha/2))
ci_percentile_manual
2.5% 97.5%
3.245577 5.729459
Our resulting confidence interval is (3.2456, 5.7295).
Constructing the
Interval via boot Package
Then, we will construct our confidence interval via the functions
from the boot package.
## Generate 95% Bootstrap Percentile Confidence Interval of Sample Mean
set.seed(1) # still controls randomness of sampling
# creates statistic function
mean_stat <- function(data, indices) {
sample_data<- data[indices]
return(mean(sample_data))
}
# Boot function generating bootstrap sampling distribution of the mean
boot.means <- boot(lead, mean_stat, R = 5000) # generating 5000 samples
# 95% Confidence Interval for Bootstrap Sample Mean
# Percentile CI
ci_boot_percent <- boot.ci(boot.means, type="perc")
ci_boot_percent
BOOTSTRAP CONFIDENCE INTERVAL CALCULATIONS
Based on 5000 bootstrap replicates
CALL :
boot.ci(boot.out = boot.means, type = "perc")
Intervals :
Level Percentile
95% ( 3.243, 5.730 )
Calculations and Intervals on Original Scale
The Resulting Confidence Interval is (3.2430, 5.7300).
TO RECAP
The manually constructed percentile confidence interval is (3.2456,
5.7295), and the percentile confidence interval constructed via the boot
package is (3.2530, 5.7300).
Part C
For this part, we will build the Bias-Corrected and Accelerated (BCa)
Bootstrap Confidence Interval. This method is essentially an enhanced
version of the percentile method: it provides adjusted quantiles by
adjusting for bias and skewness in the sampling distribution. This
occurs with two adjustment parameters: the bias correction factor, \(z_0\), which measures median bias by
comparing the bootstrap samples to the original sample, and the
acceleration factor, \(a\), which
measures how the standard error changes.
To construct this interval, we need to rely on a specific type of
resampling method called a jackknife. This is a resampling method in
which you take n subsamples of your original sample, leaving one
observation out of each of them and then calculating any statistic(s) of
interest. Then, we get \(z_0\) by
getting the proportion of observations in our bootstrap sample that is
smaller than our statistic, and then we get \(a\) by seeing how far the confidence
interval moves based on the bias adjustment.
## Manually Building A 95% BCa Confidence Interval
# Creates function
ci_bca <- function(data, B, alpha, original_estimate){
n = length(data)
boot_means <- numeric(B)
# Bootstrapping and Finding the Likelihood Estimators for Mean and Variance
for (i in 1:B) {
boot_sample = sample(data, size = n, replace= TRUE)
mean.lognorm[i] = sum(log(boot_sample))/n
var.lognorm[i] = sum((log(boot_sample) - mean.lognorm[i])^2)/n
bootstrap_means[i] = exp(mean.lognorm[i] +
(var.lognorm[i]/2))
# bias correction factor below
## can use normal if statement syntax, just incorporate the [i] to indicate that the statement is evaluating element by element
if (bootstrap_ex_estimates[i] < original_estimate ){
}
} # END BOOTSTRAP LOOP
#### START CORRECTION CALCULATION
prop_less = prop_less/b
z0 = qnorm(prop_less)
# now have bias correction
#### END BIAS CORRECTION CALCULATION
#### START ACCELERATION CALCULATION
# good practice to use different "counting variable than was earlier used in function, I'll use j instead of i
jack_vals = numeric(n)
for (j in 1:n){ # START JACK LOOP
jack_sample = data[-j]
mu_jack = sum(log(jack_sample)) / (n-1)
# the jackknife estimate is computed by leaving OUT the ith observation
theta_squared_jack = sum((log(jack_sample)-mu_jack)^2) / (n-1)
jack_vals[j] = exp(mu_jack + (theta_squared_jack/2))
} # END JACK LOOP
theta_jack_mean = mean(jack_vals)
# we want the difference between the total average and each jackknife estimate that left one out
numerator = sum((theta_jack_mean - jack_vals)^3)
denominator = sum((theta_jack_mean - jack_vals)^2)
a_hat = numerator/ (6 * denominator^(3/2))
#### END ACCELERATION CALCULATION
### FINAL OUTPUT/INTERVAL
z_score1 = qnorm(alpha/2)
z_score2 = qnorm(1-alpha/2)
alpha1 = pnorm(z0 + (z0 + z_score1)/(1-a_hat*(z0 + z_score1)))
alpha2 = pnorm(z0 + (z0 + z_score2)/(1-a_hat*(z0 + z_score2)))
lower = quantile(bootstrap_ex_estimates, alpha1)
upper = quantile(bootstrap_ex_estimates, alpha2)
results = rbind(lower,upper)
rownames(results) = c("Lower Estimate", "Higher Estimate")
colnames(results) = "BCA"
return(results)
}
Using the
boot Package
set.seed(1)
mean_stat <- function(data, indices) {
sample_data <- data[indices]
return(mean(data[indices]))
}
boot.means<- boot(lead, mean_stat, R=5000)
ci_bc_acc <- boot.ci(boot.means, type="bca")
ci_bc_acc
BOOTSTRAP CONFIDENCE INTERVAL CALCULATIONS
Based on 5000 bootstrap replicates
CALL :
boot.ci(boot.out = boot.means, type = "bca")
Intervals :
Level BCa
95% ( 3.391, 5.991 )
Calculations and Intervals on Original Scale
The resulting confidence interval is (3.391, 5.991).
TO RECAP
The manually constructed Bias-Corrected and Accelerated interval is
(,) and the confidence interval constructed via the boot package is
(3.391, 5.991)
Part D
For Part D, we will be constructing a studentized (asymptotic)
bootstrap confidence interval. This method accounts for variability
across bootstrap samples.
## Using the boot Package
set.seed(1)
mean_stat <- function(data, indices) {
sample_data <- data[indices]
return(mean(data[indices]))
}
#boot_result <- boot(lead, mean_stat, R=5000)
#boot.ci(boot_result, type="stud")
LS0tDQp0aXRsZTogIlNUQSA1MDYgSG9tZXdvcmsgNzogQm9vdHN0cmFwIENvbmZpZGVuY2UgSW50ZXJ2YWxzIg0KYXV0aG9yOiAiSWFuIFZhbldyaWdodCINCmRhdGU6ICIwMy8zMC8yMDI2Ig0KbGFuZzogZW4NCm91dHB1dDoNCiAgaHRtbF9kb2N1bWVudDogDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6IDQNCiAgICB0b2NfZmxvYXQ6IHllcw0KICAgIG51bWJlcl9zZWN0aW9uczogeWVzDQogICAgdG9jX2NvbGxhcHNlZDogeWVzDQogICAgY29kZV9mb2xkaW5nOiBzaG93DQogICAgY29kZV9kb3dubG9hZDogeWVzDQogICAgc21vb3RoX3Njcm9sbDogeWVzDQogICAgI2hpZ2hsaWdodDogemVuYnVybg0KICAgICN0aGVtZTogY2VydWxlYW4NCiAgcGRmX2RvY3VtZW50OiANCiAgICBrZWVwLXRleDogdHJ1ZQ0KICAgIHRvYzogeWVzDQogICAgdG9jX2RlcHRoOiA0DQogICAgZmlnX2NhcHRpb246IHllcw0KICAgIG51bWJlcl9zZWN0aW9uczogeWVzDQogICAgZmlnX3dpZHRoOiAzDQogICAgZmlnX2hlaWdodDogMw0KICB3b3JkX2RvY3VtZW50OiANCiAgICB0b2M6IHllcw0KICAgIHRvY19kZXB0aDogNA0KICAgIGZpZ19jYXB0aW9uOiB5ZXMNCiAgICBrZWVwX21kOiB5ZXMNCmVkaXRvcl9vcHRpb25zOiANCiAgY2h1bmtfb3V0cHV0X3R5cGU6IGlubGluZQ0KLS0tDQoNCmBgYHtjc3MsIGVjaG8gPSBGQUxTRX0NCiNUT0M6OmJlZm9yZSB7DQogIGNvbnRlbnQ6ICJUYWJsZSBvZiBDb250ZW50cyI7DQogIGZvbnQtd2VpZ2h0OiBib2xkOw0KICBmb250LXNpemU6IDEuMmVtOw0KICBkaXNwbGF5OiBibG9jazsNCiAgY29sb3I6IG5hdnk7DQogIG1hcmdpbi1ib3R0b206IDEwcHg7DQp9DQoNCg0KZGl2I1RPQyBsaSB7ICAgICAvKiB0YWJsZSBvZiBjb250ZW50ICAqLw0KICAgIGxpc3Qtc3R5bGU6dXBwZXItcm9tYW47DQogICAgYmFja2dyb3VuZC1pbWFnZTpub25lOw0KICAgIGJhY2tncm91bmQtcmVwZWF0Om5vbmU7DQogICAgYmFja2dyb3VuZC1wb3NpdGlvbjowOw0KfQ0KDQpoMS50aXRsZSB7ICAgIC8qIGxldmVsIDEgaGVhZGVyIG9mIHRpdGxlICAqLw0KICBmb250LXNpemU6IDIycHg7DQogIGZvbnQtd2VpZ2h0OiBib2xkOw0KICBjb2xvcjogRGFya1JlZDsNCiAgdGV4dC1hbGlnbjogY2VudGVyOw0KICBmb250LWZhbWlseTogIkdpbGwgU2FucyIsIHNhbnMtc2VyaWY7DQp9DQoNCmg0LmF1dGhvciB7IC8qIEhlYWRlciA0IC0gYW5kIHRoZSBhdXRob3IgYW5kIGRhdGEgaGVhZGVycyB1c2UgdGhpcyB0b28gICovDQogIGZvbnQtc2l6ZTogMTVweDsNCiAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogIGZvbnQtZmFtaWx5OiBzeXN0ZW0tdWk7DQogIGNvbG9yOiBuYXZ5Ow0KICB0ZXh0LWFsaWduOiBjZW50ZXI7DQp9DQoNCmg0LmRhdGUgeyAvKiBIZWFkZXIgNCAtIGFuZCB0aGUgYXV0aG9yIGFuZCBkYXRhIGhlYWRlcnMgdXNlIHRoaXMgdG9vICAqLw0KICBmb250LXNpemU6IDE4cHg7DQogIGZvbnQtd2VpZ2h0OiBib2xkOw0KICBmb250LWZhbWlseTogIkdpbGwgU2FucyIsIHNhbnMtc2VyaWY7DQogIGNvbG9yOiBEYXJrQmx1ZTsNCiAgdGV4dC1hbGlnbjogY2VudGVyOw0KfQ0KDQpoMSB7IC8qIEhlYWRlciAxIC0gYW5kIHRoZSBhdXRob3IgYW5kIGRhdGEgaGVhZGVycyB1c2UgdGhpcyB0b28gICovDQogICAgZm9udC1zaXplOiAyMHB4Ow0KICAgIGZvbnQtd2VpZ2h0OiBib2xkOw0KICAgIGZvbnQtZmFtaWx5OiAiVGltZXMgTmV3IFJvbWFuIiwgVGltZXMsIHNlcmlmOw0KICAgIGNvbG9yOiBkYXJrcmVkOw0KICAgIHRleHQtYWxpZ246IGNlbnRlcjsNCn0NCg0KaDIgeyAvKiBIZWFkZXIgMiAtIGFuZCB0aGUgYXV0aG9yIGFuZCBkYXRhIGhlYWRlcnMgdXNlIHRoaXMgdG9vICAqLw0KICAgIGZvbnQtc2l6ZTogMThweDsNCiAgICBmb250LXdlaWdodDogYm9sZDsNCiAgICBmb250LWZhbWlseTogIlRpbWVzIE5ldyBSb21hbiIsIFRpbWVzLCBzZXJpZjsNCiAgICBjb2xvcjogbmF2eTsNCiAgICB0ZXh0LWFsaWduOiBsZWZ0Ow0KfQ0KDQpoMyB7IC8qIEhlYWRlciAzIC0gYW5kIHRoZSBhdXRob3IgYW5kIGRhdGEgaGVhZGVycyB1c2UgdGhpcyB0b28gICovDQogICAgZm9udC1zaXplOiAxOHB4Ow0KICAgIGZvbnQtd2VpZ2h0OiBib2xkOw0KICAgIGZvbnQtZmFtaWx5OiAiVGltZXMgTmV3IFJvbWFuIiwgVGltZXMsIHNlcmlmOw0KICAgIGNvbG9yOiBuYXZ5Ow0KICAgIHRleHQtYWxpZ246IGxlZnQ7DQp9DQoNCmg0IHsgLyogSGVhZGVyIDQgLSBhbmQgdGhlIGF1dGhvciBhbmQgZGF0YSBoZWFkZXJzIHVzZSB0aGlzIHRvbyAgKi8NCiAgICBmb250LXNpemU6IDE2cHg7DQogIGZvbnQtd2VpZ2h0OiBib2xkOw0KICAgIGZvbnQtZmFtaWx5OiAiVGltZXMgTmV3IFJvbWFuIiwgVGltZXMsIHNlcmlmOw0KICAgIGNvbG9yOiBkYXJrcmVkOw0KICAgIHRleHQtYWxpZ246IGxlZnQ7DQp9DQoNCi8qIEFkZCBkb3RzIGFmdGVyIG51bWJlcmVkIGhlYWRlcnMgKi8NCi5oZWFkZXItc2VjdGlvbi1udW1iZXI6OmFmdGVyIHsNCiAgY29udGVudDogIi4iOw0KDQpib2R5IHtiYWNrZ3JvdW5kLWNvbG9yOiAjZmZmZmZmOw0KICAgICAgY29sb3I6ICMwMDAwMDA7DQogICAgICBmb250LWZhbWlseTogQXJpYWwsIHNhbnMtc2VyaWY7DQogICAgICBmb250LXNpemU6IDFyZW07DQogICAgICBsaW5lLWhlaWdodDogMS42Ow0KICAgICAgfQ0KDQouaGlnaGxpZ2h0bWUgeyBiYWNrZ3JvdW5kLWNvbG9yOnllbGxvdzsgfQ0KDQpwIHsgYmFja2dyb3VuZC1jb2xvcjp3aGl0ZTsgfQ0KDQp9DQoNCg0KDQoNCg0KDQpgYGANCg0KYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9DQojIGNvZGUgY2h1bmsgc3BlY2lmaWVzIHdoZXRoZXIgdGhlIFIgY29kZSwgd2FybmluZ3MsIGFuZCBvdXRwdXQgDQojIHdpbGwgYmUgaW5jbHVkZWQgaW4gdGhlIG91dHB1dCBmaWxlcy4NCmlmICghcmVxdWlyZSgia25pdHIiKSkgew0KICAgaW5zdGFsbC5wYWNrYWdlcygia25pdHIiKQ0KICAgbGlicmFyeShrbml0cikNCn0NCmlmICghcmVxdWlyZSgicGFuZGVyIikpIHsNCiAgIGluc3RhbGwucGFja2FnZXMoInBhbmRlciIpDQogICBsaWJyYXJ5KHBhbmRlcikNCn0NCmlmICghcmVxdWlyZSgiZ2dwbG90MiIpKSB7DQogIGluc3RhbGwucGFja2FnZXMoImdncGxvdDIiKQ0KICBsaWJyYXJ5KGdncGxvdDIpDQp9DQppZiAoIXJlcXVpcmUoInRpZHl2ZXJzZSIpKSB7DQogIGluc3RhbGwucGFja2FnZXMoInRpZHl2ZXJzZSIpDQogIGxpYnJhcnkodGlkeXZlcnNlKQ0KfQ0KDQppZiAoIXJlcXVpcmUoInBsb3RseSIpKSB7DQogIGluc3RhbGwucGFja2FnZXMoInBsb3RseSIpDQogIGxpYnJhcnkocGxvdGx5KQ0KfQ0KaWYgKCFyZXF1aXJlKCJmaXRkaXN0cnBsdXMiKSkgew0KICBpbnN0YWxsLnBhY2thZ2VzKCJmaXRkaXN0cnBsdXMiKQ0KICBsaWJyYXJ5KGZpdGRpc3RycGx1cykNCn0NCmlmICghcmVxdWlyZSgiYm9vdCIpKSB7DQogIGluc3RhbGwucGFja2FnZXMoImJvb3QiKQ0KICBsaWJyYXJ5KGJvb3QpDQp9DQojIyAgR2xvYmFsIG9wdGlvbnMgZm9yIGFsbCBjb2RlIGNodW5rcw0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFLCAgICAgICAjIGluY2x1ZGUgY29kZSBjaHVuayBpbiB0aGUgb3V0cHV0IGZpbGUNCiAgICAgICAgICAgICAgICAgICAgICB3YXJuaW5nID0gRkFMU0UsICAgIyBzb21ldGltZXMsIHlvdSBjb2RlIG1heSBwcm9kdWNlIHdhcm5pbmcgbWVzc2FnZXMsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgeW91IGNhbiBjaG9vc2UgdG8gaW5jbHVkZSB0aGUgd2FybmluZyBtZXNzYWdlcyBpbg0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIHRoZSBvdXRwdXQgZmlsZS4gDQogICAgICAgICAgICAgICAgICAgICAgcmVzdWx0cyA9IFRSVUUsICAgICMgeW91IGNhbiBhbHNvIGRlY2lkZSB3aGV0aGVyIHRvIGluY2x1ZGUgdGhlIG91dHB1dA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIGluIHRoZSBvdXRwdXQgZmlsZS4NCiAgICAgICAgICAgICAgICAgICAgICBtZXNzYWdlID0gRkFMU0UsDQogICAgICAgICAgICAgICAgICAgICAgY29tbWVudCA9IE5BDQogICAgICAgICAgICAgICAgICAgICAgKSAgDQojIyAgb3B0aW9ucyBmb3IgYWx0ZXJuYXRpdmUgdGV4dCBhbmQgY2FwdGlvbiBvZiBmaWd1cmVzDQprbml0cjo6a25pdF9ob29rcyRzZXQocGxvdCA9IGZ1bmN0aW9uKHgsb3B0aW9ucykgew0KICAgICAgYmFzZSA9IGtuaXRyOjpvcHRzX2tuaXQkZ2V0KCdiYXNlLnVybCcpDQogICAgICBpZiAoaXMubnVsbChiYXNlKSkgYmFzZSA9ICcnDQogICAgICBhbHQgPSBpZmVsc2UgKGlzLm51bGwob3B0aW9ucyRhbHQpLCIiLG9wdGlvbnMkYWx0KQ0KICAgICAgY2FwID0gaWZlbHNlIChpcy5udWxsKG9wdGlvbnMkY2FwdGlvbiksIiIsb3B0aW9ucyRjYXB0aW9uKQ0KICAgICAgaWYgKGFsdCAhPSAiIil7DQogICAgICAgIHNwcmludGYoJyFbJXNdKCVzJXMgIiVzIiknLCBjYXAsIGJhc2UsIHgsIGFsdCkNCiAgICAgIH0gZWxzZSB7DQogICAgICAgIHNwcmludGYoJyFbJXNdKCVzJXMpJywgY2FwLCBiYXNlLCB4KSAgDQogICAgICAgIH0NCiAgfSkNCmBgYA0KDQpcDQoNCiMgSW50cm9kdWN0aW9uDQpGb3IgdGhpcyBhc3NpZ25tZW50LCB3ZSB3aWxsIGJlIGJ1aWxkaW5nIGRpZmZlcmVudCB0eXBlcyBvZiBib290c3RyYXBwZWQgY29uZmlkZW5jZSBpbnRlcnZhbHMgdG8gZXN0aW1hdGUgdGhlIG1lYW4gb2YgYSBsb2dub3JtYWwgZGlzdHJpYnV0aW9uLiBTcGVjaWZpY2FsbHksIHdlIHdpbGwgdXNlIGZvdXIgZGlmZmVyZW50IHR5cGVzOiBub3JtYWwsIHBlcmNlbnRpbGUsIGJpYXMtY29ycmVjdGVkIGFuZCBhY2NlbGVyYXRlZCAoQkNhKSwgYW5kIHN0dWRlbnRpemVkIChhc3ltcHRvdGljKSBhdCBjb25maWRlbmNlIGxldmVsIG9mIDk1JS4gRm9yIGFsbCBvZiB0aGVtLCB3ZSB3aWxsIGZpcnN0IGJ1aWxkIHRoZW0gbWFudWFsbHkgYW5kIHRoZW4gYnVpbGQgdGhlbSB1c2luZyB0aGUgYm9vdCgpIGFuZCBib290LmNpKCkgZnVuY3Rpb25zIGZyb20gdGhlIGBib290YCBwYWNrYWdlLg0KDQpUbyBjb21wdXRlIHRoZXNlIGNvbmZpZGVuY2UgaW50ZXJ2YWxzLCB3ZSB3aWxsIG5lZWQgZGF0YS4gVGhlIGRhdGEgd2Ugd2lsbCBiZSB1c2luZyBjb25zaXN0cyBvZiBzb2lsIGxlYWQgKFBiKSBjb25jZW50cmF0aW9ucyAobWcva2cpIGZyb20gNTUgdXJiYW4gZ2FyZGVuIHNpdGVzLiBJbiBvcmRlciB0byBlc3RpbWF0ZSB0aGUgbWVhbiBvZiBhIGxvZ25vcm1hbCwgd2Ugd2lsbCBhc3N1bWUgdGhpcyBkYXRhIGZvbGxvd3MgYSBsb2dub3JtYWwgZGlzdHJpYnV0aW9uLg0KYGBge3J9DQpsZWFkIDwtIGMoMC44NSwgMS4yMywgMC45MiwgMy40NSwgMi4xMSwgMS41NiwgNC44OSwgMi4zNCwgMS43OCwgNi43MiwgMC45NSwgMS4zNCwgOC45MSwgMi42NywgMS44OSwgNS40MywgMS4xMiwgMy43OCwgMi40NSwgNy42NSwgMS4wNSwgMS40NSwgMTIuMzQsIDIuODksIDIuMDEsIDQuNTYsIDEuMjMsIDQuMzIsIDIuNjcsIDkuODcsIDAuOTksIDEuNTYsIDE1LjIzLCAzLjEyLCAyLjM0LCAzLjg5LCAxLjM0LCA1LjY3LCAyLjg5LCAxMS40NSwgMS4xMiwgMS42NywgMTguOTAsIDMuNDUsIDIuNTYsIDMuNDUsIDEuNDUsIDYuNzgsIDMuMTIsIDE0LjU2LCAxLjIzLCAxLjc4LCAyMi4zNCwgMy43OCwgMi43OCkNCmBgYA0KIyBQYXJ0IEENCkZvciBQYXJ0IEEsIHdlIHdpbGwgYmUgY29uc3RydWN0aW5nIGEgbm9ybWFsIChvciBzdGFuZGFyZCkgYm9vdHN0cmFwcGVkIGNvbmZpZGVuY2UgaW50ZXJ2YWwuIEZvciB0aGlzIGludGVydmFsLCB3ZSB3aWxsIGFzc3VtZSB0aGF0IG91ciBib290c3RyYXAgc2FtcGxpbmcgZGlzdHJpYnV0aW9uIHdpbGwgZm9sbG93IGEgbm9ybWFsIGRpc3RyaWJ1dGlvbi4NCg0KIyMgTWFudWFsIENvbnN0cnVjdGlvbiBvZiB0aGUgQ29uZmlkZW5jZSBJbnRlcnZhbA0KRmlyc3QsIHdlIHdpbGwgbWFudWFsbHkgYnVpbGQgdGhlIGNvbmZpZGVuY2UgaW50ZXJ2YWwuDQpgYGB7cn0NCiMjIE1hbnVhbGx5IEJ1aWxkaW5nIGEgOTUlIE5vcm1hbCBCb290c3RyYXAgQ29uZmlkZW5jZSBJbnRlcnZhbA0KDQpzZXQuc2VlZCgxKSAjIGNvbnRyb2xzIHJhbmRvbW5lc3Mgb2Ygc2FtcGxpbmcNCg0KIyBNYW51YWwgQm9vdHN0cmFwDQpCIDwtIDUwMDANCm4gPC0gbGVuZ3RoKGxlYWQpDQpib290X21lYW5zIDwtIG51bWVyaWMoQikgIyBFbXB0eSBWZWN0b3IgdG8gU3RvcmUgQm9vdHN0cmFwIFNhbXBsZSBNZWFucw0KDQojIExvb3AgdG8gQ3JlYXRlIFNhbXBsZXMgYW5kIENhbGN1bGF0ZSBTYW1wbGUgTWVhbnMNCmZvcihiIGluIDE6Qikgew0KICBib290X3NhbXBsZSA8LSBzYW1wbGUobGVhZCwgbiwgcmVwbGFjZT1UUlVFKSAgIyBHZW5lcmF0aW5nIGJvb3RzdHJhcCBzYW1wbGUNCiAgYm9vdF9tZWFuc1tiXSA8LSBtZWFuKGJvb3Rfc2FtcGxlKSAjIENhbGN1bGF0ZSBCb290c3RyYXAgU2FtcGxlIE1lYW5zDQp9DQoNCg0KbWVhbi5zYW1wIDwtIG1lYW4obGVhZCkgIyBtZWFuIGZyb20gdGhlIG9yaWdpbmFsIHNhbXBsZQ0KYm9vdC5zZSA8LSBzZChib290X21lYW5zKSAjIHN0YW5kYXJkIGVycm9yIG9mIGJvb3RzdHJhcCANCnogPC0gcW5vcm0oMC45NzUpICMgY3JpdGljYWwgdmFsdWUgZm9yIGNvbmZpZGVuY2UgaW50ZXJ2YWwNCm1vZSA9IHoqYm9vdC5zZSAjIG1hcmdpbiBvZiBlcnJvciBmb3IgY29uZmlkZW5jZSBpbnRlcnZhbA0KDQojIFRoZSBDb25maWRlbmNlIEludGVydmFsIA0KY2lfbm9ybWFsX21hbnVhbCA8LSBjKExDTCA9IG1lYW4uc2FtcCAtIG1vZSwgVUNMID0gbWVhbi5zYW1wICsgbW9lKQ0KY2lfbm9ybWFsX21hbnVhbA0KYGBgDQpPdXIgcmVzdWxpbmcgY29uZmlkZW5jZSBpbnRlcnZhbCBpcyAoMy4xNzM3LCA1LjYyMTkpLiANCg0KIyMgQ29uc3RydWN0aW5nIHRoZSBDb25maWRlbmNlIEludGVydmFsIHdpdGggdGhlIGBib290YCBQYWNrYWdlDQpOZXh0LCB3ZSB3aWxsIHVzZSB0aGUgYm9vdCgpIGFuZCBib290LmNpKCkgZnVuY3Rpb25zIGZyb20gdGhlIGBib290YCBwYWNrYWdlIHRvIGJ1aWxkIHRoZSBjb25maWRlbmNlIGludGVydmFsLg0KYGBge3J9DQojIyBDYWxjdWxhdGluZyBCb290c3RyYXAgQ29uZmlkZW5jZSBJbnRlcnZhbCBWaWEgQm9vdCBQYWNrYWdlDQoNCnNldC5zZWVkKDEpICMgc3RpbGwgY29udHJvbHMgcmFuZG9tbmVzcyBvZiBzYW1wbGluZw0KDQojIGNyZWF0ZXMgc3RhdGlzdGljIGZ1bmN0aW9uIA0KbWVhbl9zdGF0IDwtIGZ1bmN0aW9uKGRhdGEsIGluZGljZXMpIHsNCiAgc2FtcGxlX2RhdGE8LSBkYXRhW2luZGljZXNdDQogIHJldHVybihtZWFuKHNhbXBsZV9kYXRhKSkNCn0NCg0KIyBCb290IGZ1bmN0aW9uIGdlbmVyYXRpbmcgYm9vdHN0cmFwIHNhbXBsaW5nIGRpc3RyaWJ1dGlvbiBvZiB0aGUgbWVhbg0KYm9vdC5tZWFucyA8LSBib290KGxlYWQsIG1lYW5fc3RhdCwgUiA9IDUwMDApICMgZ2VuZXJhdGluZyA1MDAwIHNhbXBsZXMNCiMgOTUlIENvbmZpZGVuY2UgSW50ZXJ2YWwgZm9yIEJvb3RzdHJhcCBTYW1wbGUgTWVhbg0KY2lfYm9vdF9ub3JtYWwxIDwtIGJvb3QuY2koYm9vdC5tZWFucywgdHlwZSA9ICJub3JtIikNCmNpX2Jvb3Rfbm9ybWFsMQ0KYGBgDQojIyBIaXN0b2dyYW0gb2YgdGhlIFNhbXBsaW5nIERpc3RyaWJ1dGlvbg0KQW5kIGZpbmFsbHksIHdlIHdpbGwgcGxvdCB0aGUgYWN0dWFsIHNhbXBsaW5nIGRpc3RyaWJ1dGlvbiBpdHNlbGYuDQpgYGB7cn0NCiMgcGxvdCBoaXN0b2dyYW0gb2Ygc2FtcGxpbmcgZGlzdHJpYnV0aW9uIG9mIG1lYW5zDQpoaXN0KGJvb3QubWVhbnMkdCwgcHJvYiA9IFRSVUUsIGNvbCA9ICJsaWdodGJsdWUiLCBtYWluID0gIkJvb3RzdHJhcCBTYW1wbGluZyBEaXN0cmlidXRpb24gb2YgU2FtcGxlIE1lYW5zIiwgeGxhYiA9ICJTYW1wbGUgTWVhbiIpIA0KDQojIEFkZCBHYXVzc2lhbiBEZW5zaXR5IEN1cnZlIG9mIFNhbXBsaW5nIERpc3RyaWJ1dGlvbg0KbGluZXMoZGVuc2l0eShib290Lm1lYW5zJHQsIGtlcm5lbCA9ICJnYXVzc2lhbiIpLCBjb2wgPSAicmVkIiwgbHdkID0gMikNCmBgYA0KVGhlcmUgZG9lcyBhcHBlYXIgdG8gYmUgc29tZSBwb3NpdGl2ZSBza2V3LiBIb3dldmVyIHRoZSBza2V3IGxvb2tzIGEgYml0IGV4YWdnZXJhdGVkIGR1ZSB0byB0aGUgZ3JhcGggbm90IGJlaW5nIGNlbnRlcmVkLiBPdGhlciB0aGFuIHRoYXQsIG5vdGhpbmcgbG9va3Mgb3V0IG9mIHRoZSBvcmRpbmFyeS4gVGhlIGRlbnNpdHkgY3VydmUgZGVmaW5pdGVseSB0YWtlcyBzaGFwZSBvZiBhIGJlbGwgY3VydmUgdGhhbmtzIHRvIHRoZSA1MDAwIHNhbXBsZSBtZWFucyB3ZSBoYXZlLiANCg0KIyMgVE8gUkVDQVAgDQpPdXIgbWFudWFsbHkgY29uc3RydWN0ZWQgbm9ybWFsIGJvb3RzdHJhcCBjb25maWRlbmNlIGludGVydmFsIGlzICgzLjE3MzcsIDUuNjIxOSksIGFuZCB0aGUgaW50ZXJ2YWwgY29uc3RydWN0ZWQgdmlhIHRoZSBib290IHBhY2thZ2UgaXMgKDMuMTY1LCA1LjY1NSkuIEkgZXhwZWN0ZWQgdGhlIGludGVydmFscyB0byBkaWZmZXIgc2xpZ2h0bHkgYmVjYXVzZSB0aGUgc2FtcGxlIG1lYW4gZGlmZmVycyBmcm9tIHRoZSBib290c3RyYXAgbWVhbi4NCg0KIyBQYXJ0IEINCkZvciB0aGlzIHBhcnQsIHdlIHdpbGwgY29uc3RydWN0IGEgcGVyY2VudGlsZSBib290c3RyYXAgY29uZmlkZW5jZSBpbnRlcnZhbC4gVGhlc2UgYXJlIHRoZSBzaW1wbGVzdCBjb25maWRlbmNlIGludGVydmFscywgYXMgdGhleSBhcmUgYnVpbHQgYnkgZGlyZWN0bHkgdGFraW5nIHRoZSBjb3JyZXNwb25kaW5nIHF1YW50aWxlcyBvZiB0aGUgZW1waXJpY2FsIGRpc3RyaWJ1dGlvbiBvZiBib290c3RyYXAgc2FtcGxpbmcgZGlzdHJpYnV0aW9uLiBUaGlzIG1ldGhvZCB3b3JrcyB3ZWxsIHdoZW4gdGhlIGJvb3RzdHJhcCBkaXN0cmlidXRpb24gaXMgYXBwcm94aW1hdGVseSBzeW1tZXRyaWMgYW5kIHRoZSBlc3RpbWF0b3IgaGFzIGEgbG93IGFtb3VudCBvZiBiaWFzLg0KDQojIyBNYW51YWxseSBCdWlsZGluZyB0aGUgQ29uZmlkZW5jZSBJbnRlcnZhbA0KRmlyc3QsIFdlIHdpbGwgbWFudWFsbHkgYnVpbGQgdGhpcyBjb25maWRlbmNlIGludGVydmFsLiBXZSB3aWxsIHVzZSB0aGUgc2FtZSBzYW1wbGluZyBkaXN0cmlidXRpb24gZnJvbSBlYXJsaWVyLiBTaW5jZSB0aGUgc2FtcGxpbmcgZGlzdHJpYnV0aW9uIGxvb2tzIHJvdWdobHkgc3ltbWV0cmljIGFuZCB3ZSBhcmUgYnVpbGRpbmcgYSA5NSUgY29uZmlkZW5jZSBpbnRlcnZhbCwgd2Ugd2lsbCBjYWxjdWxhdGUgdGhlIDIuNSUgYW5kIDk3LjUlIHBlcmNlbnRpbGVzIGFuZCB1c2UgdGhvc2UgdmFsdWVzIGFzIHRoZSBsb3dlciBhbmQgdXBwZXIgbGltaXRzIG9mIHRoaXMgY29uZmlkZW5jZSBpbnRlcnZhbC4NCmBgYHtyfQ0KYm9vdC5tZWFuLnZhbHVlcyA8LSBib290Lm1lYW5zJHQNCmFscGhhIDwtIDAuMDUgIyAxIC0gYWxwaGEgPSBsZXZlbCBvZiBjb25maWRlbmNlDQoNCiMgVGhlIENPbmZpZGVuY2UgSW50ZXJ2YWwNCmNpX3BlcmNlbnRpbGVfbWFudWFsIDwtIHF1YW50aWxlKGJvb3QubWVhbi52YWx1ZXMsIHByb2JzPWMoYWxwaGEvMiwgMS1hbHBoYS8yKSkNCmNpX3BlcmNlbnRpbGVfbWFudWFsDQpgYGANCk91ciByZXN1bHRpbmcgY29uZmlkZW5jZSBpbnRlcnZhbCBpcyAoMy4yNDU2LCA1LjcyOTUpLg0KDQoNCiMjIENvbnN0cnVjdGluZyB0aGUgSW50ZXJ2YWwgdmlhIGBib290YCBQYWNrYWdlIA0KVGhlbiwgd2Ugd2lsbCBjb25zdHJ1Y3Qgb3VyIGNvbmZpZGVuY2UgaW50ZXJ2YWwgdmlhIHRoZSBmdW5jdGlvbnMgZnJvbSB0aGUgYm9vdCBwYWNrYWdlLg0KYGBge3J9DQojIyBHZW5lcmF0ZSA5NSUgQm9vdHN0cmFwIFBlcmNlbnRpbGUgQ29uZmlkZW5jZSBJbnRlcnZhbCBvZiBTYW1wbGUgTWVhbg0Kc2V0LnNlZWQoMSkgIyBzdGlsbCBjb250cm9scyByYW5kb21uZXNzIG9mIHNhbXBsaW5nDQoNCiMgY3JlYXRlcyBzdGF0aXN0aWMgZnVuY3Rpb24gDQptZWFuX3N0YXQgPC0gZnVuY3Rpb24oZGF0YSwgaW5kaWNlcykgew0KICBzYW1wbGVfZGF0YTwtIGRhdGFbaW5kaWNlc10NCiAgcmV0dXJuKG1lYW4oc2FtcGxlX2RhdGEpKQ0KfQ0KDQojIEJvb3QgZnVuY3Rpb24gZ2VuZXJhdGluZyBib290c3RyYXAgc2FtcGxpbmcgZGlzdHJpYnV0aW9uIG9mIHRoZSBtZWFuDQpib290Lm1lYW5zIDwtIGJvb3QobGVhZCwgbWVhbl9zdGF0LCBSID0gNTAwMCkgIyBnZW5lcmF0aW5nIDUwMDAgc2FtcGxlcw0KIyA5NSUgQ29uZmlkZW5jZSBJbnRlcnZhbCBmb3IgQm9vdHN0cmFwIFNhbXBsZSBNZWFuDQojIFBlcmNlbnRpbGUgQ0kNCmNpX2Jvb3RfcGVyY2VudCA8LSBib290LmNpKGJvb3QubWVhbnMsIHR5cGU9InBlcmMiKQ0KY2lfYm9vdF9wZXJjZW50DQpgYGANClRoZSBSZXN1bHRpbmcgQ29uZmlkZW5jZSBJbnRlcnZhbCBpcyAoMy4yNDMwLCA1LjczMDApLg0KDQojIyBUTyBSRUNBUA0KVGhlIG1hbnVhbGx5IGNvbnN0cnVjdGVkIHBlcmNlbnRpbGUgY29uZmlkZW5jZSBpbnRlcnZhbCBpcyAoMy4yNDU2LCA1LjcyOTUpLCBhbmQgdGhlIHBlcmNlbnRpbGUgY29uZmlkZW5jZSBpbnRlcnZhbCBjb25zdHJ1Y3RlZCB2aWEgdGhlIGJvb3QgcGFja2FnZSBpcyAoMy4yNTMwLCA1LjczMDApLg0KDQoNCiMgUGFydCBDDQpGb3IgdGhpcyBwYXJ0LCB3ZSB3aWxsIGJ1aWxkIHRoZSBCaWFzLUNvcnJlY3RlZCBhbmQgQWNjZWxlcmF0ZWQgKEJDYSkgQm9vdHN0cmFwIENvbmZpZGVuY2UgSW50ZXJ2YWwuIFRoaXMgbWV0aG9kIGlzIGVzc2VudGlhbGx5IGFuIGVuaGFuY2VkIHZlcnNpb24gb2YgdGhlIHBlcmNlbnRpbGUgbWV0aG9kOiBpdCBwcm92aWRlcyBhZGp1c3RlZCBxdWFudGlsZXMgYnkgYWRqdXN0aW5nIGZvciBiaWFzIGFuZCBza2V3bmVzcyBpbiB0aGUgc2FtcGxpbmcgZGlzdHJpYnV0aW9uLiBUaGlzIG9jY3VycyB3aXRoIHR3byBhZGp1c3RtZW50IHBhcmFtZXRlcnM6IHRoZSBiaWFzIGNvcnJlY3Rpb24gZmFjdG9yLCAkel8wJCwgd2hpY2ggbWVhc3VyZXMgbWVkaWFuIGJpYXMgYnkgY29tcGFyaW5nIHRoZSBib290c3RyYXAgc2FtcGxlcyB0byB0aGUgb3JpZ2luYWwgc2FtcGxlLCBhbmQgdGhlIGFjY2VsZXJhdGlvbiBmYWN0b3IsICRhJCwgd2hpY2ggbWVhc3VyZXMgaG93IHRoZSBzdGFuZGFyZCBlcnJvciBjaGFuZ2VzLg0KDQpUbyBjb25zdHJ1Y3QgdGhpcyBpbnRlcnZhbCwgd2UgbmVlZCB0byByZWx5IG9uIGEgc3BlY2lmaWMgdHlwZSBvZiByZXNhbXBsaW5nIG1ldGhvZCBjYWxsZWQgYSBqYWNra25pZmUuIFRoaXMgaXMgYSByZXNhbXBsaW5nIG1ldGhvZCBpbiB3aGljaCB5b3UgdGFrZSBuIHN1YnNhbXBsZXMgb2YgeW91ciBvcmlnaW5hbCBzYW1wbGUsIGxlYXZpbmcgb25lIG9ic2VydmF0aW9uIG91dCBvZiBlYWNoIG9mIHRoZW0gYW5kIHRoZW4gY2FsY3VsYXRpbmcgYW55IHN0YXRpc3RpYyhzKSBvZiBpbnRlcmVzdC4gVGhlbiwgd2UgZ2V0ICR6XzAkIGJ5IGdldHRpbmcgdGhlIHByb3BvcnRpb24gb2Ygb2JzZXJ2YXRpb25zIGluIG91ciBib290c3RyYXAgc2FtcGxlIHRoYXQgaXMgc21hbGxlciB0aGFuIG91ciBzdGF0aXN0aWMsIGFuZCB0aGVuIHdlIGdldCAkYSQgYnkgc2VlaW5nIGhvdyBmYXIgdGhlIGNvbmZpZGVuY2UgaW50ZXJ2YWwgbW92ZXMgYmFzZWQgb24gdGhlIGJpYXMgYWRqdXN0bWVudC4NCg0KDQpgYGB7cn0NCiMjIE1hbnVhbGx5IEJ1aWxkaW5nIEEgOTUlIEJDYSBDb25maWRlbmNlIEludGVydmFsDQoNCiMgQ3JlYXRlcyBmdW5jdGlvbg0KY2lfYmNhIDwtIGZ1bmN0aW9uKGRhdGEsIEIsIGFscGhhLCBvcmlnaW5hbF9lc3RpbWF0ZSl7IA0KICBuID0gbGVuZ3RoKGRhdGEpDQogIGJvb3RfbWVhbnMgPC0gbnVtZXJpYyhCKQ0KICANCiMgQm9vdHN0cmFwcGluZyBhbmQgRmluZGluZyB0aGUgTGlrZWxpaG9vZCBFc3RpbWF0b3JzIGZvciBNZWFuIGFuZCBWYXJpYW5jZQ0KZm9yIChpIGluIDE6Qikgew0KICAgICBib290X3NhbXBsZSA9IHNhbXBsZShkYXRhLCBzaXplID0gbiwgcmVwbGFjZT0gVFJVRSkNCiAgICAgbWVhbi5sb2dub3JtW2ldID0gc3VtKGxvZyhib290X3NhbXBsZSkpL24NCiAgICAgdmFyLmxvZ25vcm1baV0gPSBzdW0oKGxvZyhib290X3NhbXBsZSkgLSBtZWFuLmxvZ25vcm1baV0pXjIpL24NCiAgICAgYm9vdHN0cmFwX21lYW5zW2ldID0gZXhwKG1lYW4ubG9nbm9ybVtpXSArDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICh2YXIubG9nbm9ybVtpXS8yKSkNCiAgICAgDQogICAgICMgYmlhcyBjb3JyZWN0aW9uIGZhY3RvciBiZWxvdw0KICAgICAjIyBjYW4gdXNlIG5vcm1hbCBpZiBzdGF0ZW1lbnQgc3ludGF4LCBqdXN0IGluY29ycG9yYXRlIHRoZSBbaV0gdG8gaW5kaWNhdGUgdGhhdCB0aGUgc3RhdGVtZW50IGlzIGV2YWx1YXRpbmcgZWxlbWVudCBieSBlbGVtZW50DQogICAgICAgICBpZiAoYm9vdHN0cmFwX2V4X2VzdGltYXRlc1tpXSA8IG9yaWdpbmFsX2VzdGltYXRlICl7DQoNCiAgICAgICAgIH0NCiAgICAgfSAjIEVORCBCT09UU1RSQVAgTE9PUA0KICAgICANCiAgICAgICMjIyMgU1RBUlQgQ09SUkVDVElPTiBDQUxDVUxBVElPTiAgDQogICAgICAgIHByb3BfbGVzcyA9IHByb3BfbGVzcy9iDQogICAgICAgIHowID0gcW5vcm0ocHJvcF9sZXNzKQ0KICAgICAgICAjIG5vdyBoYXZlIGJpYXMgY29ycmVjdGlvbg0KICAgICAgIyMjIyBFTkQgQklBUyBDT1JSRUNUSU9OIENBTENVTEFUSU9ODQogIA0KICAgICAgICANCiAgICAgICMjIyMgU1RBUlQgQUNDRUxFUkFUSU9OIENBTENVTEFUSU9ODQogICAgICAgICAgIyBnb29kIHByYWN0aWNlIHRvIHVzZSBkaWZmZXJlbnQgImNvdW50aW5nIHZhcmlhYmxlIHRoYW4gd2FzIGVhcmxpZXIgdXNlZCBpbiBmdW5jdGlvbiwgSSdsbCB1c2UgaiBpbnN0ZWFkIG9mIGkNCiAgICAgamFja192YWxzID0gbnVtZXJpYyhuKQ0KICAgICANCiAgICAgZm9yIChqIGluIDE6bil7ICMgU1RBUlQgSkFDSyBMT09QDQogICAgICAgamFja19zYW1wbGUgPSBkYXRhWy1qXQ0KICAgICAgIA0KICAgICAgIG11X2phY2sgPSBzdW0obG9nKGphY2tfc2FtcGxlKSkgLyAobi0xKQ0KICAgICAgICAjIHRoZSBqYWNra25pZmUgZXN0aW1hdGUgaXMgY29tcHV0ZWQgYnkgbGVhdmluZyBPVVQgdGhlIGl0aCBvYnNlcnZhdGlvbg0KICAgICAgIHRoZXRhX3NxdWFyZWRfamFjayA9IHN1bSgobG9nKGphY2tfc2FtcGxlKS1tdV9qYWNrKV4yKSAvIChuLTEpDQogICAgICAgamFja192YWxzW2pdID0gZXhwKG11X2phY2sgKyAodGhldGFfc3F1YXJlZF9qYWNrLzIpKQ0KICAgICB9ICMgRU5EIEpBQ0sgTE9PUA0KICAgICANCiAgICAgICB0aGV0YV9qYWNrX21lYW4gPSBtZWFuKGphY2tfdmFscykNCiAgICAgICAgICAgICAjIHdlIHdhbnQgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgdG90YWwgYXZlcmFnZSBhbmQgZWFjaCBqYWNra25pZmUgZXN0aW1hdGUgdGhhdCBsZWZ0IG9uZSBvdXQNCiAgICAgICBudW1lcmF0b3IgPSBzdW0oKHRoZXRhX2phY2tfbWVhbiAtIGphY2tfdmFscyleMykNCiAgICAgICBkZW5vbWluYXRvciA9IHN1bSgodGhldGFfamFja19tZWFuIC0gamFja192YWxzKV4yKQ0KICAgICAgIA0KICAgICAgIGFfaGF0ID0gbnVtZXJhdG9yLyAoNiAqIGRlbm9taW5hdG9yXigzLzIpKQ0KICAgICAjIyMjIEVORCBBQ0NFTEVSQVRJT04gQ0FMQ1VMQVRJT04NCiAgICAgICANCiAgICAgICANCiAgICAjIyMgRklOQUwgT1VUUFVUL0lOVEVSVkFMDQogICAgICAgel9zY29yZTEgPSBxbm9ybShhbHBoYS8yKQ0KICAgICAgIHpfc2NvcmUyID0gcW5vcm0oMS1hbHBoYS8yKQ0KICAgICAgIGFscGhhMSA9IHBub3JtKHowICsgKHowICsgel9zY29yZTEpLygxLWFfaGF0Kih6MCArIHpfc2NvcmUxKSkpDQogICAgICAgYWxwaGEyID0gcG5vcm0oejAgKyAoejAgKyB6X3Njb3JlMikvKDEtYV9oYXQqKHowICsgel9zY29yZTIpKSkNCiAgICAgICANCiAgICAgICBsb3dlciA9IHF1YW50aWxlKGJvb3RzdHJhcF9leF9lc3RpbWF0ZXMsIGFscGhhMSkNCiAgICAgICB1cHBlciA9IHF1YW50aWxlKGJvb3RzdHJhcF9leF9lc3RpbWF0ZXMsIGFscGhhMikNCiAgICAgICByZXN1bHRzID0gcmJpbmQobG93ZXIsdXBwZXIpDQogICAgICAgcm93bmFtZXMocmVzdWx0cykgPSBjKCJMb3dlciBFc3RpbWF0ZSIsICJIaWdoZXIgRXN0aW1hdGUiKQ0KICAgICAgIGNvbG5hbWVzKHJlc3VsdHMpID0gIkJDQSINCiAgICAgICANCiAgICAgICByZXR1cm4ocmVzdWx0cykNCiAgICAgICAgICAgIA0KfQ0KYGBgDQoNCg0KDQogICAgDQojIyBVc2luZyB0aGUgYGJvb3RgIFBhY2thZ2UNCmBgYHtyfQ0Kc2V0LnNlZWQoMSkNCg0KbWVhbl9zdGF0IDwtIGZ1bmN0aW9uKGRhdGEsIGluZGljZXMpIHsNCiAgc2FtcGxlX2RhdGEgPC0gZGF0YVtpbmRpY2VzXQ0KICByZXR1cm4obWVhbihkYXRhW2luZGljZXNdKSkNCn0NCg0KYm9vdC5tZWFuczwtIGJvb3QobGVhZCwgbWVhbl9zdGF0LCBSPTUwMDApDQoNCmNpX2JjX2FjYyA8LSBib290LmNpKGJvb3QubWVhbnMsIHR5cGU9ImJjYSIpDQpjaV9iY19hY2MgDQpgYGANClRoZSByZXN1bHRpbmcgY29uZmlkZW5jZSBpbnRlcnZhbCBpcyAoMy4zOTEsIDUuOTkxKS4NCg0KIyMgVE8gUkVDQVANClRoZSBtYW51YWxseSBjb25zdHJ1Y3RlZCBCaWFzLUNvcnJlY3RlZCBhbmQgQWNjZWxlcmF0ZWQgaW50ZXJ2YWwgaXMgKCwpIGFuZCB0aGUgY29uZmlkZW5jZSBpbnRlcnZhbCBjb25zdHJ1Y3RlZCB2aWEgdGhlIGJvb3QgcGFja2FnZSBpcyAoMy4zOTEsIDUuOTkxKQ0KDQojIFBhcnQgRA0KRm9yIFBhcnQgRCwgd2Ugd2lsbCBiZSBjb25zdHJ1Y3RpbmcgYSBzdHVkZW50aXplZCAoYXN5bXB0b3RpYykgYm9vdHN0cmFwIGNvbmZpZGVuY2UgaW50ZXJ2YWwuIFRoaXMgbWV0aG9kIGFjY291bnRzIGZvciB2YXJpYWJpbGl0eSBhY3Jvc3MgYm9vdHN0cmFwIHNhbXBsZXMuDQoNCmBgYHtyfQ0KIyMgVXNpbmcgdGhlIGJvb3QgUGFja2FnZQ0KDQpzZXQuc2VlZCgxKQ0KDQptZWFuX3N0YXQgPC0gZnVuY3Rpb24oZGF0YSwgaW5kaWNlcykgew0KICBzYW1wbGVfZGF0YSA8LSBkYXRhW2luZGljZXNdDQogIHJldHVybihtZWFuKGRhdGFbaW5kaWNlc10pKQ0KDQp9DQogIA0KI2Jvb3RfcmVzdWx0IDwtIGJvb3QobGVhZCwgbWVhbl9zdGF0LCBSPTUwMDApDQojYm9vdC5jaShib290X3Jlc3VsdCwgdHlwZT0ic3R1ZCIpDQpgYGANCg==