Introduction
For this assignment, we will focus on comparing a asymptotic \(\chi^2\) hypothesis test to a bootstrapped
hypothesis test to determine whether or not a sample came from one
distribution or another. Specifically, we will do a Wald \(\chi^2\) and a bootstrapped hypothesis test
to determine if a sample came from a Weibull distribution or an
exponential distribution.
The sample we will use for our tests is a sample consisting of 75
failure times for gearboxes used in wind turbines at a distribution
company’s facility.
times <- c(5.2, 7.8, 9.1, 11.3, 12.5, 13.0, 14.2, 15.1, 15.9, 16.7, 17.2, 17.8, 18.4, 18.9, 19.3, 19.7, 20.2, 20.6, 21.0, 21.5, 21.9, 22.3, 22.7, 23.1, 23.5, 23.9, 24.3, 24.7, 25.1, 25.5, 25.9, 26.3, 26.7, 27.1, 27.5, 27.9, 28.3, 28.7, 29.1, 29.5, 29.9, 30.3, 30.7, 31.1, 31.5, 31.9, 32.3, 32.7, 33.1, 33.5, 33.9, 34.3, 34.7, 35.1, 35.5, 35.9, 36.3, 36.7, 37.1, 37.5, 37.9, 38.3, 38.7, 39.1, 39.5, 39.9, 40.3, 40.7, 41.1, 41.5,
41.9, 42.3, 42.7, 43.1, 43.5)
Part A
For this part, we will find the maximum likelihood estimators of the
Weibull distribution, treating this sample as if it comes from a Weibull
distribution.
First, we’ll start with the log-likelihood function for the weibull
distribution:
$$ \[\begin{align}
\ell(k, \lambda; \mathbf{t}) &= \ln L(k, \lambda; \mathbf{t}) \\
&= \sum_{i=1}^{n} \ln \left[ \frac{k}{\lambda} \left(
\frac{t_i}{\lambda} \right)^{k-1} \exp\left( -\left( \frac{t_i}{\lambda}
\right)^k \right) \right] \\
&= \sum_{i=1}^{n} \left[ \ln k - \ln \lambda + (k-1)(\ln t_i -
\ln \lambda) - \left( \frac{t_i}{\lambda} \right)^k \right] \\
&= \sum_{i=1}^{n} \left[ \ln k - k \ln \lambda + (k-1) \ln t_i -
\left( \frac{t_i}{\lambda} \right)^k \right]
\end{align}\]
$$
From there, we can take the partial derivatives (one with respect to
each variable), set them both equal to 0, and then solve for the two
parameters and get their maximum likelihood estimates. If done right,
the maximum likelihood estimates are: \[
\begin{align}
\hat{\lambda} &= \left( \frac{1}{n} \sum_{i=1}^{n}
x_i^{\hat{\beta}} \right)^{1/\hat{\beta}} \quad \\
\frac{1}{\hat{\beta}} &= \frac{\sum_{i=1}^{n} (t_i^{\hat{\beta}}
\ln x_i)}{\sum_{i=1}^{n} x_i^{\hat{\beta}}} - \frac{1}{n} \sum_{i=1}^{n}
\ln x_i \quad
\end{align}
\]
Where \(\lambda\) is the scale
parameter and \(\beta\) is the shape
parameter.
To obtain these parameters, we will use R’s built in optim()
function, which will solve a system of equations numerically. The
following code will be used to obtain the parameter estimates:
## Manual MLE implementation for Weibull distribution
# Create Weibull log-likelihood function
weibull.loglik <- function(params, data) {
shape <- params[1] # passing the parameters
scale <- params[2]
n <- length(data) # sample size
# Log-likelihood for Weibull distribution
loglik <- n * log(shape) - n * shape * log(scale) +
(shape - 1) * sum(log(data)) -
sum((data / scale)^shape)
return(loglik) # Return
}
# Score equation
weibull.score <- function(params, data) {
shape <- params[1]
scale <- params[2]
n <- length(data)
# Gradient for shape parameter
grad_shape <- n/shape - n * log(scale) +
sum(log(data)) -
sum((data/scale)^shape * log(data/scale))
# Gradient for scale parameter
grad_scale <- -(n * shape)/scale +
(shape/scale) * sum((data/scale)^shape)
return(c(grad_shape, grad_scale))
}
# Need to provide initial values for parameters
initial.params <- c(shape = 1, scale = 5) # Reasonable starting values
# Using optim with Nelder-Mead method
mle.result.weibull <- optim(
par = initial.params,
fn = weibull.loglik,
gr = weibull.score,
data = times,
method = "L-BFGS-B",
hessian = TRUE,
control = list(trace = FALSE,
fnscale = -1,
maxit = 500,
abstol = 1e-8)
)
##
mle.result.weibull$par
shape scale
3.370783 31.418204
The estimate for the shape parameter is 3.370783, while the estimate
for the scale parameter is 31.418204.
To verify, we can use the fitdistr() function from the
MASS package:
mle.weibull.fit <- fitdistr(times, "weibull")
mle.weibull.fit
shape scale
3.3707800 31.4184018
( 0.3206184) ( 1.1278755)
They’re just about the same, so we can say that our original
estimates are correct.
Part B
For this part, we will find the maximum likelihood estimator for the
exponential distribution, treating this sample as if it came from an
exponential distribution.
In the case of the exponential distribution, we are only estimating
the scale parameter because an exponential random variable is just a
Weibull random variable with the shape parameter, \(\beta\), set to 1.
Depending on how we write the density function for the exponential,
the resulting maximum likelihood estimate for the scale parameter is:
\[
\hat{\lambda} = \frac{1}{n} \sum x_i = \bar{x} \implies
\frac{1}{\hat{\lambda}} = \frac{n}{\sum x_i} = \frac{1}{\bar{x}}
\]
Regardless of how the estimator is written, the process for solving
for \(\lambda\) is the same. In this
case, since we only have one parameter to solve for, and it has a simple
form, we can use simpler methods to solve for it. Since we already
determined that \(\lambda\) is just the
sample mean, we will use that estimate.
First, since we did it manually in Part A, we can do it manually in
this part as well.
## Manual MLE implementation for Exponential distribution
# Create Exponential Log-Likelihood Function
exponential.loglik <- function(params, data) {
scale <- params[1]
n <- length(data) # sample size
# Log-likelihood for Exponential Distribution
loglik <- -n*log(scale) - sum(data)/scale
return(loglik) # Return
}
# Score equation
exponential.score <- function(params, data) {
scale <- params[1]
n <- length(data)
# Gradient for scale parameter
grad_scale <- -(n/scale) + sum(data)/scale^2
return(grad_scale)
}
# Need to provide initial values for parameters
# Reasonable starting values
# Using optim with Nelder-Mead method
mle.result.exponential <- optim(
par = 5, # Just a generic number for an estimate
fn = exponential.loglik,
gr = exponential.score,
data = times,
method = "L-BFGS-B",
hessian = TRUE,
control = list(trace = FALSE,
fnscale = -1,
maxit = 500,
abstol = 1e-8)
)
##
mle.result.exponential$par
[1] 28.18533
Now let’s plug the sample mean for the mle:
## Using Sample Mean as MLE For Exponential
mle.exponential.scale <- mean(times)
mle.exponential.scale
[1] 28.18533
The mean of our sample is 28.18533, so the estimate for our scale
parameter is 28.18533.
To verify, we can use fitdistr() from the MASS
package:
## Verifying MLE For Exponential via fitdistr()
exponential.fit <- fitdistr(times, "exponential")
exponential.fit
rate
0.035479446
(0.004096813)
As we can see, R gave us the estimate for the rate parameter. But we
need the estimate for the scale parameter. The good news is that we can
get the estimate for the scale parameter, as it is just the inverse of
the rate parameter. In other words, scale = 1/rate.
mle.fit <- 1/exponential.fit$estimate
mle.fit
rate
28.18533
Part C
For this part, we will conduct the first of two hypothesis tests to
determine whether or not this data comes from a Weibull distribution or
an exponential distribution. Specifically, we will conduct a likelihood
ratio \(\chi^2\) test. Our null
hypothesis, \(H_0\), is that this data
comes from an exponential distribution. In other words, our null
hypothesis is that \(\beta = 1\). Our
alternative hypothesis, \(H_a\), is
that it our data comes from a Weibull distribution. In other words, our
alternative hypothesis is that \(\beta \neq
1\). To put into symbols: \[
H_0: \beta = 1 (Exponential) \\
H_a: \beta \neq 1 (Weibull)
\]
This test will be done at significance level \(\alpha = 0.05\).
## Likelihood Ratio Test using both Log-Likelihood Functions
# Weibull Log-Likelihood Function
loglike.weibull <- function(data, lambda, beta){
n <- length(data)
n*log(beta)-n*beta*log(lambda)+(beta-1)*sum(log(data))-sum((data/lambda)^beta)
}
# Exponential Log-Likelihood Function
loglike.exponential <- function(data, lambda){
n <- length(data)
-n*log(lambda)-sum(data)/lambda
}
## Evaluate Log Likelihood @ MLE
scale.est.weibull <- mle.result.weibull$par[[2]]
shape.est.weibull <- mle.result.weibull$par[[1]]
scale.est.exponential <- mle.fit
# Exponential vs Weibull Hypotheses
LogLike.Alt <- loglike.weibull(times, scale.est.weibull, shape.est.weibull)
LogLike.Null <- loglike.exponential(times, scale.est.exponential)
ratio <- 2*(LogLike.Alt - LogLike.Null) #Computes likelihood ratio
## Getting p-value for ratio test
pvalue.ratio <- 1 - pchisq(ratio, df = 1) #Gets p-value
# STatistic and p-value together
test1 <- c(ratio, pvalue.ratio)
test1
rate rate
100.6144 0.0000
Our \(\chi^2\) statistic is
100.6144, and the p-value is \(\approx\) 0, which so it’s safe to say that
we can reject the null hypothesis and conclude that there is sufficient
evidence to say that this sample came from an weibull distribution.
Part D
For this part, we will conduct the second of our hypothesis tests to
determine whether or not this sample came from a Weibull distribution or
an exponential distribution. Specifically, we will use a bootstrapped
likelihood ratio hypothesis test. The null hypothesis, the alternative
hypothesis, and the level of significance will be the same as the
likelihood ratio test from Part C.
# Bootstrap Likelihood Ratio test for normal mean
set.seed(1)
bootstrap_lrt_test <- function(data, scale_0, B = 10000) {
n <- length(data)
# MLE of Exponential
scale_hat <- mean(data)
scale_0 <- mean(data)
# Log-likelihoods
logL_hat <- sum(dexp(data, rate = 1/scale_hat, log = TRUE))
logL0 <- sum(dexp(data, rate = 1/scale_0, log = TRUE))
# Likelihood Ratio Test Statistic
LR_obs <- -2 * (logL0 - logL_hat)
# Bootstrap distribution
LR_star <- numeric(B)
for (b in 1:B) {
# Generate data under H0: Exp(Scale)
bs_sample <- rexp(n, rate = 1/scale_0)
# MLE from bootstrap sample
scale_1 <- mean(bs_sample)
# Likelihoods
logL_star <- sum(dexp(bs_sample, rate = 1/scale_hat, log = TRUE))
logL_star0 <- sum(dexp(bs_sample, rate = 1/scale_0, log = TRUE))
LR_star[b] <- -2 * (logL_star0 - logL_star)
}
p_value <- (sum(LR_star >= LR_obs) + 1) / (B + 1)
return(list(
LR_obs = LR_obs,
p_value = p_value,
scale_1 = scale_1,
scale_0 = scale_0
))
}
bootstrap_lrt_test(times)
$LR_obs
[1] 0
$p_value
[1] 1
$scale_1
[1] 22.82617
$scale_0
[1] 28.18533
It’s hard to determine what exactly our test statistic is, but one
thing is clear: the p-value for the test is \(\approx\) 1, so this time we will fail to
reject the null hypothesis, and we can conclude that there is
insufficient evidence to say that this sample came from a weibull
distribution.
Part E
The two tests did not generate the same result. What is odd is how
much the bootstrapped estimate for the scale parameter changed as n
increases. If n = 1000, then the scale parameter is estimated to be
26.5558. If n = 5000, then the scale parameter is estimated to be
30.10166. If n = 10,000, then the scale parameter is estimated to be
22.82617.
Still, based on the non-bootstrapped likelihood ratio test, i would
be inclined to believe that the Weibull distribution is a better fit for
this data.
LS0tDQp0aXRsZTogIlNUQSA1MTIgQXNzaWdubWVudCAxMjogQm9vdHN0cmFwIFRlc3RpbmcgSHlwb3RoZXNpcyINCmF1dGhvcjogIklhbiBWYW5XcmlnaHQiDQpkYXRlOiAiMDQvMjAvMjAyNiINCm91dHB1dDoNCiAgaHRtbF9kb2N1bWVudDogDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6IDQNCiAgICB0b2NfZmxvYXQ6IHllcw0KICAgIG51bWJlcl9zZWN0aW9uczogeWVzDQogICAgdG9jX2NvbGxhcHNlZDogeWVzDQogICAgY29kZV9mb2xkaW5nOiBzaG93DQogICAgY29kZV9kb3dubG9hZDogeWVzDQogICAgc21vb3RoX3Njcm9sbDogeWVzDQogICAgdGhlbWU6IGx1bWVuDQogIHBkZl9kb2N1bWVudDogDQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6IDQNCiAgICBmaWdfY2FwdGlvbjogeWVzDQogICAgbnVtYmVyX3NlY3Rpb25zOiB5ZXMNCiAgICBmaWdfd2lkdGg6IDMNCiAgICBmaWdfaGVpZ2h0OiAzDQogIHdvcmRfZG9jdW1lbnQ6IA0KICAgIHRvYzogeWVzDQogICAgdG9jX2RlcHRoOiA0DQogICAgZmlnX2NhcHRpb246IHllcw0KICAgIGtlZXBfbWQ6IHllcw0KZWRpdG9yX29wdGlvbnM6IA0KICBjaHVua19vdXRwdXRfdHlwZTogaW5saW5lDQotLS0NCg0KYGBge2NzcywgZWNobyA9IEZBTFNFfQ0KI1RPQzo6YmVmb3JlIHsNCiAgY29udGVudDogIlRhYmxlIG9mIENvbnRlbnRzIjsNCiAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogIGZvbnQtc2l6ZTogMS4yZW07DQogIGRpc3BsYXk6IGJsb2NrOw0KICBjb2xvcjogbmF2eTsNCiAgbWFyZ2luLWJvdHRvbTogMTBweDsNCn0NCg0KDQpkaXYjVE9DIGxpIHsgICAgIC8qIHRhYmxlIG9mIGNvbnRlbnQgICovDQogICAgbGlzdC1zdHlsZTp1cHBlci1yb21hbjsNCiAgICBiYWNrZ3JvdW5kLWltYWdlOm5vbmU7DQogICAgYmFja2dyb3VuZC1yZXBlYXQ6bm9uZTsNCiAgICBiYWNrZ3JvdW5kLXBvc2l0aW9uOjA7DQp9DQoNCmgxLnRpdGxlIHsgICAgLyogbGV2ZWwgMSBoZWFkZXIgb2YgdGl0bGUgICovDQogIGZvbnQtc2l6ZTogMjJweDsNCiAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogIGNvbG9yOiBEYXJrUmVkOw0KICB0ZXh0LWFsaWduOiBjZW50ZXI7DQogIGZvbnQtZmFtaWx5OiAiR2lsbCBTYW5zIiwgc2Fucy1zZXJpZjsNCn0NCg0KaDQuYXV0aG9yIHsgLyogSGVhZGVyIDQgLSBhbmQgdGhlIGF1dGhvciBhbmQgZGF0YSBoZWFkZXJzIHVzZSB0aGlzIHRvbyAgKi8NCiAgZm9udC1zaXplOiAxNXB4Ow0KICBmb250LXdlaWdodDogYm9sZDsNCiAgZm9udC1mYW1pbHk6IHN5c3RlbS11aTsNCiAgY29sb3I6IG5hdnk7DQogIHRleHQtYWxpZ246IGNlbnRlcjsNCn0NCg0KaDQuZGF0ZSB7IC8qIEhlYWRlciA0IC0gYW5kIHRoZSBhdXRob3IgYW5kIGRhdGEgaGVhZGVycyB1c2UgdGhpcyB0b28gICovDQogIGZvbnQtc2l6ZTogMThweDsNCiAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogIGZvbnQtZmFtaWx5OiAiR2lsbCBTYW5zIiwgc2Fucy1zZXJpZjsNCiAgY29sb3I6IERhcmtCbHVlOw0KICB0ZXh0LWFsaWduOiBjZW50ZXI7DQp9DQoNCmgxIHsgLyogSGVhZGVyIDEgLSBhbmQgdGhlIGF1dGhvciBhbmQgZGF0YSBoZWFkZXJzIHVzZSB0aGlzIHRvbyAgKi8NCiAgICBmb250LXNpemU6IDIwcHg7DQogICAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogICAgZm9udC1mYW1pbHk6ICJUaW1lcyBOZXcgUm9tYW4iLCBUaW1lcywgc2VyaWY7DQogICAgY29sb3I6IGRhcmtyZWQ7DQogICAgdGV4dC1hbGlnbjogY2VudGVyOw0KfQ0KDQpoMiB7IC8qIEhlYWRlciAyIC0gYW5kIHRoZSBhdXRob3IgYW5kIGRhdGEgaGVhZGVycyB1c2UgdGhpcyB0b28gICovDQogICAgZm9udC1zaXplOiAxOHB4Ow0KICAgIGZvbnQtd2VpZ2h0OiBib2xkOw0KICAgIGZvbnQtZmFtaWx5OiAiVGltZXMgTmV3IFJvbWFuIiwgVGltZXMsIHNlcmlmOw0KICAgIGNvbG9yOiBuYXZ5Ow0KICAgIHRleHQtYWxpZ246IGxlZnQ7DQp9DQoNCmgzIHsgLyogSGVhZGVyIDMgLSBhbmQgdGhlIGF1dGhvciBhbmQgZGF0YSBoZWFkZXJzIHVzZSB0aGlzIHRvbyAgKi8NCiAgICBmb250LXNpemU6IDE2cHg7DQogICAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogICAgZm9udC1mYW1pbHk6ICJUaW1lcyBOZXcgUm9tYW4iLCBUaW1lcywgc2VyaWY7DQogICAgY29sb3I6IG5hdnk7DQogICAgdGV4dC1hbGlnbjogbGVmdDsNCn0NCg0KaDQgeyAvKiBIZWFkZXIgNCAtIGFuZCB0aGUgYXV0aG9yIGFuZCBkYXRhIGhlYWRlcnMgdXNlIHRoaXMgdG9vICAqLw0KICAgIGZvbnQtc2l6ZTogMTRweDsNCiAgZm9udC13ZWlnaHQ6IGJvbGQ7DQogICAgZm9udC1mYW1pbHk6ICJUaW1lcyBOZXcgUm9tYW4iLCBUaW1lcywgc2VyaWY7DQogICAgY29sb3I6IGRhcmtyZWQ7DQogICAgdGV4dC1hbGlnbjogbGVmdDsNCn0NCg0KLyogQWRkIGRvdHMgYWZ0ZXIgbnVtYmVyZWQgaGVhZGVycyAqLw0KLmhlYWRlci1zZWN0aW9uLW51bWJlcjo6YWZ0ZXIgew0KICBjb250ZW50OiAiLiI7DQoNCmJvZHkgeyBiYWNrZ3JvdW5kLWNvbG9yOndoaXRlOyB9DQoNCi5oaWdobGlnaHRtZSB7IGJhY2tncm91bmQtY29sb3I6eWVsbG93OyB9DQoNCnAgeyBiYWNrZ3JvdW5kLWNvbG9yOndoaXRlOyB9DQoNCn0NCmBgYA0KDQpgYGB7aHRtbCwgZWNobz1GQUxTRX0NCjxidXR0b24gaWQ9InRvZ2dsZVRPQ0J0biIgY2xhc3M9ImJ0biBidG4tZGVmYXVsdCIgc3R5bGU9InBvc2l0aW9uOiBmaXhlZDsgYm90dG9tOiAyMHB4OyByaWdodDogMjBweDsgei1pbmRleDogMTAwMDsiPg0KICBUb2dnbGUgVE9DDQo8L2J1dHRvbj4NCg0KPHNjcmlwdD4NCmRvY3VtZW50LmdldEVsZW1lbnRCeUlkKCJ0b2dnbGVUT0NCdG4iKS5vbmNsaWNrID0gZnVuY3Rpb24oKSB7DQogIHZhciB0b2MgPSBkb2N1bWVudC5xdWVyeVNlbGVjdG9yKCIubGlzdC1ncm91cCwgI1RPQywgLnRvY2lmeSIpOw0KICBpZiAodG9jKSB7DQogICAgaWYgKHRvYy5zdHlsZS5kaXNwbGF5ID09PSAibm9uZSIpIHsNCiAgICAgIHRvYy5zdHlsZS5kaXNwbGF5ID0gIiI7DQogICAgfSBlbHNlIHsNCiAgICAgIHRvYy5zdHlsZS5kaXNwbGF5ID0gIm5vbmUiOw0KICAgIH0NCiAgfQ0KfTsNCjwvc2NyaXB0Pg0KDQpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0NCiMgY29kZSBjaHVuayBzcGVjaWZpZXMgd2hldGhlciB0aGUgUiBjb2RlLCB3YXJuaW5ncywgYW5kIG91dHB1dCANCiMgd2lsbCBiZSBpbmNsdWRlZCBpbiB0aGUgb3V0cHV0IGZpbGVzLg0KaWYgKCFyZXF1aXJlKCJrbml0ciIpKSB7DQogICBpbnN0YWxsLnBhY2thZ2VzKCJrbml0ciIpDQogICBsaWJyYXJ5KGtuaXRyKQ0KfQ0KaWYgKCFyZXF1aXJlKCJwYW5kZXIiKSkgew0KICAgaW5zdGFsbC5wYWNrYWdlcygicGFuZGVyIikNCiAgIGxpYnJhcnkocGFuZGVyKQ0KfQ0KaWYgKCFyZXF1aXJlKCJnZ3Bsb3QyIikpIHsNCiAgaW5zdGFsbC5wYWNrYWdlcygiZ2dwbG90MiIpDQogIGxpYnJhcnkoZ2dwbG90MikNCn0NCmlmICghcmVxdWlyZSgidGlkeXZlcnNlIikpIHsNCiAgaW5zdGFsbC5wYWNrYWdlcygidGlkeXZlcnNlIikNCiAgbGlicmFyeSh0aWR5dmVyc2UpDQp9DQoNCmlmICghcmVxdWlyZSgicGxvdGx5IikpIHsNCiAgaW5zdGFsbC5wYWNrYWdlcygicGxvdGx5IikNCiAgbGlicmFyeShwbG90bHkpDQp9DQppZiAoIXJlcXVpcmUoImZpdGRpc3RycGx1cyIpKSB7DQogIGluc3RhbGwucGFja2FnZXMoImZpdGRpc3RycGx1cyIpDQogIGxpYnJhcnkoZml0ZGlzdHJwbHVzKQ0KfQ0KaWYgKCFyZXF1aXJlKCJNQVNTIikpIHsNCiAgaW5zdGFsbC5wYWNrYWdlcygiTUFTUyIpDQogIGxpYnJhcnkoTUFTUykNCn0NCg0KIyMgbGlicmFyeShmaXRkaXN0cnBsdXMpDQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUsICAgICAgICMgaW5jbHVkZSBjb2RlIGNodW5rIGluIHRoZSBvdXRwdXQgZmlsZQ0KICAgICAgICAgICAgICAgICAgICAgIHdhcm5pbmcgPSBGQUxTRSwgICAjIHNvbWV0aW1lcywgeW91IGNvZGUgbWF5IHByb2R1Y2Ugd2FybmluZyBtZXNzYWdlcywNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyB5b3UgY2FuIGNob29zZSB0byBpbmNsdWRlIHRoZSB3YXJuaW5nIG1lc3NhZ2VzIGluDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgdGhlIG91dHB1dCBmaWxlLiANCiAgICAgICAgICAgICAgICAgICAgICByZXN1bHRzID0gVFJVRSwgICAgIyB5b3UgY2FuIGFsc28gZGVjaWRlIHdoZXRoZXIgdG8gaW5jbHVkZSB0aGUgb3V0cHV0DQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgaW4gdGhlIG91dHB1dCBmaWxlLg0KICAgICAgICAgICAgICAgICAgICAgIG1lc3NhZ2UgPSBGQUxTRSwNCiAgICAgICAgICAgICAgICAgICAgICBjb21tZW50ID0gTkENCiAgICAgICAgICAgICAgICAgICAgICApICANCmBgYA0KDQpcDQoNCiMgSW50cm9kdWN0aW9uDQpGb3IgdGhpcyBhc3NpZ25tZW50LCB3ZSB3aWxsIGZvY3VzIG9uIGNvbXBhcmluZyBhIGFzeW1wdG90aWMgJFxjaGleMiQgaHlwb3RoZXNpcyB0ZXN0IHRvIGEgYm9vdHN0cmFwcGVkIGh5cG90aGVzaXMgdGVzdCB0byBkZXRlcm1pbmUgd2hldGhlciBvciBub3QgYSBzYW1wbGUgY2FtZSBmcm9tIG9uZSBkaXN0cmlidXRpb24gb3IgYW5vdGhlci4gU3BlY2lmaWNhbGx5LCB3ZSB3aWxsIGRvIGEgV2FsZCAkXGNoaV4yJCBhbmQgYSBib290c3RyYXBwZWQgaHlwb3RoZXNpcyB0ZXN0IHRvIGRldGVybWluZSBpZiBhIHNhbXBsZSBjYW1lIGZyb20gYSBXZWlidWxsIGRpc3RyaWJ1dGlvbiBvciBhbiBleHBvbmVudGlhbCBkaXN0cmlidXRpb24uDQoNClRoZSBzYW1wbGUgd2Ugd2lsbCB1c2UgZm9yIG91ciB0ZXN0cyBpcyBhIHNhbXBsZSBjb25zaXN0aW5nIG9mIDc1IGZhaWx1cmUgdGltZXMgZm9yIGdlYXJib3hlcyB1c2VkIGluIHdpbmQgdHVyYmluZXMgYXQgYSBkaXN0cmlidXRpb24gY29tcGFueSdzIGZhY2lsaXR5Lg0KYGBge3J9DQp0aW1lcyA8LSBjKDUuMiwgNy44LCA5LjEsIDExLjMsIDEyLjUsIDEzLjAsIDE0LjIsIDE1LjEsIDE1LjksIDE2LjcsIDE3LjIsIDE3LjgsIDE4LjQsIDE4LjksIDE5LjMsIDE5LjcsIDIwLjIsIDIwLjYsIDIxLjAsIDIxLjUsIDIxLjksIDIyLjMsIDIyLjcsIDIzLjEsIDIzLjUsIDIzLjksIDI0LjMsIDI0LjcsIDI1LjEsIDI1LjUsIDI1LjksIDI2LjMsIDI2LjcsIDI3LjEsIDI3LjUsIDI3LjksIDI4LjMsIDI4LjcsIDI5LjEsIDI5LjUsIDI5LjksIDMwLjMsIDMwLjcsIDMxLjEsIDMxLjUsIDMxLjksIDMyLjMsIDMyLjcsIDMzLjEsIDMzLjUsIDMzLjksIDM0LjMsIDM0LjcsIDM1LjEsIDM1LjUsIDM1LjksIDM2LjMsIDM2LjcsIDM3LjEsIDM3LjUsIDM3LjksIDM4LjMsIDM4LjcsIDM5LjEsIDM5LjUsIDM5LjksIDQwLjMsIDQwLjcsIDQxLjEsIDQxLjUsDQo0MS45LCA0Mi4zLCA0Mi43LCA0My4xLCA0My41KQ0KYGBgDQoNCiMgUGFydCBBDQpGb3IgdGhpcyBwYXJ0LCB3ZSB3aWxsIGZpbmQgdGhlIG1heGltdW0gbGlrZWxpaG9vZCBlc3RpbWF0b3JzIG9mIHRoZSBXZWlidWxsIGRpc3RyaWJ1dGlvbiwgdHJlYXRpbmcgdGhpcyBzYW1wbGUgYXMgaWYgaXQgY29tZXMgZnJvbSBhIFdlaWJ1bGwgZGlzdHJpYnV0aW9uLg0KDQpGaXJzdCwgd2UnbGwgc3RhcnQgd2l0aCB0aGUgbG9nLWxpa2VsaWhvb2QgZnVuY3Rpb24gZm9yIHRoZSB3ZWlidWxsIGRpc3RyaWJ1dGlvbjoNCg0KJCQNClxiZWdpbnthbGlnbn0NCiAgICBcZWxsKGssIFxsYW1iZGE7IFxtYXRoYmZ7dH0pICY9IFxsbiBMKGssIFxsYW1iZGE7IFxtYXRoYmZ7dH0pIFxcDQogICAgJj0gXHN1bV97aT0xfV57bn0gXGxuIFxsZWZ0WyBcZnJhY3trfXtcbGFtYmRhfSBcbGVmdCggXGZyYWN7dF9pfXtcbGFtYmRhfSBccmlnaHQpXntrLTF9IFxleHBcbGVmdCggLVxsZWZ0KCBcZnJhY3t0X2l9e1xsYW1iZGF9IFxyaWdodCleayBccmlnaHQpIFxyaWdodF0gXFwNCiAgICAmPSBcc3VtX3tpPTF9XntufSBcbGVmdFsgXGxuIGsgLSBcbG4gXGxhbWJkYSArIChrLTEpKFxsbiB0X2kgLSBcbG4gXGxhbWJkYSkgLSBcbGVmdCggXGZyYWN7dF9pfXtcbGFtYmRhfSBccmlnaHQpXmsgXHJpZ2h0XSBcXA0KICAgICY9IFxzdW1fe2k9MX1ee259IFxsZWZ0WyBcbG4gayAtIGsgXGxuIFxsYW1iZGEgKyAoay0xKSBcbG4gdF9pIC0gXGxlZnQoIFxmcmFje3RfaX17XGxhbWJkYX0gXHJpZ2h0KV5rIFxyaWdodF0NClxlbmR7YWxpZ259DQoNCiQkDQoNCkZyb20gdGhlcmUsIHdlIGNhbiB0YWtlIHRoZSBwYXJ0aWFsIGRlcml2YXRpdmVzIChvbmUgd2l0aCByZXNwZWN0IHRvIGVhY2ggdmFyaWFibGUpLCBzZXQgdGhlbSBib3RoIGVxdWFsIHRvIDAsIGFuZCB0aGVuIHNvbHZlIGZvciB0aGUgdHdvIHBhcmFtZXRlcnMgYW5kIGdldCB0aGVpciBtYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGVzLiBJZiBkb25lIHJpZ2h0LCB0aGUgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRlcyBhcmU6DQokJA0KXGJlZ2lue2FsaWdufQ0KICAgIFxoYXR7XGxhbWJkYX0gJj0gXGxlZnQoIFxmcmFjezF9e259IFxzdW1fe2k9MX1ee259IHhfaV57XGhhdHtcYmV0YX19IFxyaWdodCleezEvXGhhdHtcYmV0YX19IFxxdWFkIFxcDQogICAgXGZyYWN7MX17XGhhdHtcYmV0YX19ICY9IFxmcmFje1xzdW1fe2k9MX1ee259ICh0X2lee1xoYXR7XGJldGF9fSBcbG4geF9pKX17XHN1bV97aT0xfV57bn0geF9pXntcaGF0e1xiZXRhfX19IC0gXGZyYWN7MX17bn0gXHN1bV97aT0xfV57bn0gXGxuIHhfaSBccXVhZA0KXGVuZHthbGlnbn0NCiQkDQoNCldoZXJlICRcbGFtYmRhJCBpcyB0aGUgc2NhbGUgcGFyYW1ldGVyIGFuZCAkXGJldGEkIGlzIHRoZSBzaGFwZSBwYXJhbWV0ZXIuDQoNClRvIG9idGFpbiB0aGVzZSBwYXJhbWV0ZXJzLCB3ZSB3aWxsIHVzZSBSJ3MgYnVpbHQgaW4gb3B0aW0oKSBmdW5jdGlvbiwgd2hpY2ggd2lsbCBzb2x2ZSBhIHN5c3RlbSBvZiBlcXVhdGlvbnMgbnVtZXJpY2FsbHkuIFRoZSBmb2xsb3dpbmcgY29kZSB3aWxsIGJlIHVzZWQgdG8gb2J0YWluIHRoZSBwYXJhbWV0ZXIgZXN0aW1hdGVzOg0KYGBge3J9DQojIyBNYW51YWwgTUxFIGltcGxlbWVudGF0aW9uIGZvciBXZWlidWxsIGRpc3RyaWJ1dGlvbg0KDQojIENyZWF0ZSBXZWlidWxsIGxvZy1saWtlbGlob29kIGZ1bmN0aW9uDQp3ZWlidWxsLmxvZ2xpayA8LSBmdW5jdGlvbihwYXJhbXMsIGRhdGEpIHsNCiAgc2hhcGUgPC0gcGFyYW1zWzFdICAjIHBhc3NpbmcgdGhlIHBhcmFtZXRlcnMNCiAgc2NhbGUgPC0gcGFyYW1zWzJdDQoNCm4gPC0gbGVuZ3RoKGRhdGEpICAgIyBzYW1wbGUgc2l6ZQ0KICANCiMgTG9nLWxpa2VsaWhvb2QgZm9yIFdlaWJ1bGwgZGlzdHJpYnV0aW9uDQpsb2dsaWsgPC0gbiAqIGxvZyhzaGFwZSkgLSBuICogc2hhcGUgKiBsb2coc2NhbGUpICsgDQogICAgICAgICAgICAoc2hhcGUgLSAxKSAqIHN1bShsb2coZGF0YSkpIC0gDQogICAgICAgICAgICBzdW0oKGRhdGEgLyBzY2FsZSlec2hhcGUpDQogIA0KICByZXR1cm4obG9nbGlrKSAgICAjIFJldHVybg0KfQ0KDQoNCiMgU2NvcmUgZXF1YXRpb24NCg0Kd2VpYnVsbC5zY29yZSA8LSBmdW5jdGlvbihwYXJhbXMsIGRhdGEpIHsNCiAgc2hhcGUgPC0gcGFyYW1zWzFdDQogIHNjYWxlIDwtIHBhcmFtc1syXQ0KICBuIDwtIGxlbmd0aChkYXRhKQ0KICANCiMgR3JhZGllbnQgZm9yIHNoYXBlIHBhcmFtZXRlcg0KZ3JhZF9zaGFwZSA8LSBuL3NoYXBlIC0gbiAqIGxvZyhzY2FsZSkgKyANCiAgICAgICAgICAgICAgICBzdW0obG9nKGRhdGEpKSAtIA0KICAgICAgICAgICAgICAgIHN1bSgoZGF0YS9zY2FsZSlec2hhcGUgKiBsb2coZGF0YS9zY2FsZSkpDQogIA0KIyBHcmFkaWVudCBmb3Igc2NhbGUgcGFyYW1ldGVyDQpncmFkX3NjYWxlIDwtIC0obiAqIHNoYXBlKS9zY2FsZSArIA0KICAgICAgICAgICAgICAgIChzaGFwZS9zY2FsZSkgKiBzdW0oKGRhdGEvc2NhbGUpXnNoYXBlKQ0KICANCiAgcmV0dXJuKGMoZ3JhZF9zaGFwZSwgZ3JhZF9zY2FsZSkpDQp9DQoNCiMgTmVlZCB0byBwcm92aWRlIGluaXRpYWwgdmFsdWVzIGZvciBwYXJhbWV0ZXJzDQppbml0aWFsLnBhcmFtcyA8LSBjKHNoYXBlID0gMSwgc2NhbGUgPSA1KSAgIyBSZWFzb25hYmxlIHN0YXJ0aW5nIHZhbHVlcw0KDQoNCiMgVXNpbmcgb3B0aW0gd2l0aCBOZWxkZXItTWVhZCBtZXRob2QNCm1sZS5yZXN1bHQud2VpYnVsbCA8LSBvcHRpbSgNCiAgcGFyID0gaW5pdGlhbC5wYXJhbXMsDQogIGZuID0gd2VpYnVsbC5sb2dsaWssDQogIGdyID0gd2VpYnVsbC5zY29yZSwNCiAgZGF0YSA9IHRpbWVzLA0KICBtZXRob2QgPSAiTC1CRkdTLUIiLA0KICBoZXNzaWFuID0gVFJVRSwNCiAgY29udHJvbCA9IGxpc3QodHJhY2UgPSBGQUxTRSwNCiAgICAgICAgICAgICAgICAgZm5zY2FsZSA9IC0xLA0KICAgICAgICAgICAgICAgICBtYXhpdCA9IDUwMCwNCiAgICAgICAgICAgICAgICAgYWJzdG9sID0gMWUtOCkNCikNCiMjDQptbGUucmVzdWx0LndlaWJ1bGwkcGFyDQpgYGANClRoZSBlc3RpbWF0ZSBmb3IgdGhlIHNoYXBlIHBhcmFtZXRlciBpcyAzLjM3MDc4Mywgd2hpbGUgdGhlIGVzdGltYXRlIGZvciB0aGUgc2NhbGUgcGFyYW1ldGVyIGlzIDMxLjQxODIwNC4NCg0KVG8gdmVyaWZ5LCB3ZSBjYW4gdXNlIHRoZSBmaXRkaXN0cigpIGZ1bmN0aW9uIGZyb20gdGhlIGBNQVNTYCBwYWNrYWdlOg0KDQpgYGB7cn0NCm1sZS53ZWlidWxsLmZpdCA8LSBmaXRkaXN0cih0aW1lcywgIndlaWJ1bGwiKQ0KbWxlLndlaWJ1bGwuZml0DQpgYGANClRoZXkncmUganVzdCBhYm91dCB0aGUgc2FtZSwgc28gd2UgY2FuIHNheSB0aGF0IG91ciBvcmlnaW5hbCBlc3RpbWF0ZXMgYXJlIGNvcnJlY3QuDQoNCg0KIyBQYXJ0IEINCkZvciB0aGlzIHBhcnQsIHdlIHdpbGwgZmluZCB0aGUgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRvciBmb3IgdGhlIGV4cG9uZW50aWFsIGRpc3RyaWJ1dGlvbiwgdHJlYXRpbmcgdGhpcyBzYW1wbGUgYXMgaWYgaXQgY2FtZSBmcm9tIGFuIGV4cG9uZW50aWFsIGRpc3RyaWJ1dGlvbi4NCg0KSW4gdGhlIGNhc2Ugb2YgdGhlIGV4cG9uZW50aWFsIGRpc3RyaWJ1dGlvbiwgd2UgYXJlIG9ubHkgZXN0aW1hdGluZyB0aGUgc2NhbGUgcGFyYW1ldGVyIGJlY2F1c2UgYW4gZXhwb25lbnRpYWwgcmFuZG9tIHZhcmlhYmxlIGlzIGp1c3QgYSBXZWlidWxsIHJhbmRvbSB2YXJpYWJsZSB3aXRoIHRoZSBzaGFwZSBwYXJhbWV0ZXIsICRcYmV0YSQsIHNldCB0byAxLg0KDQpEZXBlbmRpbmcgb24gaG93IHdlIHdyaXRlIHRoZSBkZW5zaXR5IGZ1bmN0aW9uIGZvciB0aGUgZXhwb25lbnRpYWwsIHRoZSByZXN1bHRpbmcgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRlIGZvciB0aGUgc2NhbGUgcGFyYW1ldGVyIGlzOg0KJCQNClxoYXR7XGxhbWJkYX0gPSBcZnJhY3sxfXtufSBcc3VtIHhfaSA9IFxiYXJ7eH0gXGltcGxpZXMgXGZyYWN7MX17XGhhdHtcbGFtYmRhfX0gPSBcZnJhY3tufXtcc3VtIHhfaX0gPSBcZnJhY3sxfXtcYmFye3h9fQ0KJCQgDQoNClJlZ2FyZGxlc3Mgb2YgaG93IHRoZSBlc3RpbWF0b3IgaXMgd3JpdHRlbiwgdGhlIHByb2Nlc3MgZm9yIHNvbHZpbmcgZm9yICRcbGFtYmRhJCBpcyB0aGUgc2FtZS4gSW4gdGhpcyBjYXNlLCBzaW5jZSB3ZSBvbmx5IGhhdmUgb25lIHBhcmFtZXRlciB0byBzb2x2ZSBmb3IsIGFuZCBpdCBoYXMgYSBzaW1wbGUgZm9ybSwgd2UgY2FuIHVzZSBzaW1wbGVyIG1ldGhvZHMgdG8gc29sdmUgZm9yIGl0LiBTaW5jZSB3ZSBhbHJlYWR5IGRldGVybWluZWQgdGhhdCAkXGxhbWJkYSQgaXMganVzdCB0aGUgc2FtcGxlIG1lYW4sIHdlIHdpbGwgdXNlIHRoYXQgZXN0aW1hdGUuDQoNCkZpcnN0LCBzaW5jZSB3ZSBkaWQgaXQgbWFudWFsbHkgaW4gUGFydCBBLCB3ZSBjYW4gZG8gaXQgbWFudWFsbHkgaW4gdGhpcyBwYXJ0IGFzIHdlbGwuDQoNCmBgYHtyfQ0KIyMgTWFudWFsIE1MRSBpbXBsZW1lbnRhdGlvbiBmb3IgRXhwb25lbnRpYWwgZGlzdHJpYnV0aW9uDQoNCiMgQ3JlYXRlIEV4cG9uZW50aWFsIExvZy1MaWtlbGlob29kIEZ1bmN0aW9uDQpleHBvbmVudGlhbC5sb2dsaWsgPC0gZnVuY3Rpb24ocGFyYW1zLCBkYXRhKSB7DQogIHNjYWxlIDwtIHBhcmFtc1sxXQ0KDQpuIDwtIGxlbmd0aChkYXRhKSAgICMgc2FtcGxlIHNpemUNCiAgDQojIExvZy1saWtlbGlob29kIGZvciBFeHBvbmVudGlhbCBEaXN0cmlidXRpb24NCmxvZ2xpayA8LSAtbipsb2coc2NhbGUpIC0gc3VtKGRhdGEpL3NjYWxlDQogIA0KICByZXR1cm4obG9nbGlrKSAgICAjIFJldHVybiANCn0NCg0KDQojIFNjb3JlIGVxdWF0aW9uDQoNCmV4cG9uZW50aWFsLnNjb3JlIDwtIGZ1bmN0aW9uKHBhcmFtcywgZGF0YSkgew0KICBzY2FsZSA8LSBwYXJhbXNbMV0NCiAgbiA8LSBsZW5ndGgoZGF0YSkNCg0KICANCiMgR3JhZGllbnQgZm9yIHNjYWxlIHBhcmFtZXRlcg0KZ3JhZF9zY2FsZSA8LSAtKG4vc2NhbGUpICsgc3VtKGRhdGEpL3NjYWxlXjINCg0KICByZXR1cm4oZ3JhZF9zY2FsZSkNCn0NCg0KIyBOZWVkIHRvIHByb3ZpZGUgaW5pdGlhbCB2YWx1ZXMgZm9yIHBhcmFtZXRlcnMNCiAgIyBSZWFzb25hYmxlIHN0YXJ0aW5nIHZhbHVlcw0KDQoNCiMgVXNpbmcgb3B0aW0gd2l0aCBOZWxkZXItTWVhZCBtZXRob2QNCm1sZS5yZXN1bHQuZXhwb25lbnRpYWwgPC0gb3B0aW0oDQogIHBhciA9IDUsICMgSnVzdCBhIGdlbmVyaWMgbnVtYmVyIGZvciBhbiBlc3RpbWF0ZQ0KICBmbiA9IGV4cG9uZW50aWFsLmxvZ2xpaywNCiAgZ3IgPSBleHBvbmVudGlhbC5zY29yZSwNCiAgZGF0YSA9IHRpbWVzLA0KICBtZXRob2QgPSAiTC1CRkdTLUIiLA0KICBoZXNzaWFuID0gVFJVRSwNCiAgY29udHJvbCA9IGxpc3QodHJhY2UgPSBGQUxTRSwNCiAgICAgICAgICAgICAgICAgZm5zY2FsZSA9IC0xLA0KICAgICAgICAgICAgICAgICBtYXhpdCA9IDUwMCwNCiAgICAgICAgICAgICAgICAgYWJzdG9sID0gMWUtOCkNCikNCiMjDQptbGUucmVzdWx0LmV4cG9uZW50aWFsJHBhcg0KYGBgDQoNCk5vdyBsZXQncyBwbHVnIHRoZSBzYW1wbGUgbWVhbiBmb3IgdGhlIG1sZToNCmBgYHtyfQ0KIyMgVXNpbmcgU2FtcGxlIE1lYW4gYXMgTUxFIEZvciBFeHBvbmVudGlhbCANCg0KbWxlLmV4cG9uZW50aWFsLnNjYWxlIDwtIG1lYW4odGltZXMpDQptbGUuZXhwb25lbnRpYWwuc2NhbGUNCmBgYA0KDQpUaGUgbWVhbiBvZiBvdXIgc2FtcGxlIGlzIDI4LjE4NTMzLCBzbyB0aGUgZXN0aW1hdGUgZm9yIG91ciBzY2FsZSBwYXJhbWV0ZXIgaXMgMjguMTg1MzMuDQoNClRvIHZlcmlmeSwgd2UgY2FuIHVzZSBmaXRkaXN0cigpIGZyb20gdGhlIGBNQVNTYCBwYWNrYWdlOg0KYGBge3J9DQojIyBWZXJpZnlpbmcgTUxFIEZvciBFeHBvbmVudGlhbCB2aWEgZml0ZGlzdHIoKQ0KDQpleHBvbmVudGlhbC5maXQgPC0gZml0ZGlzdHIodGltZXMsICJleHBvbmVudGlhbCIpDQpleHBvbmVudGlhbC5maXQNCmBgYA0KQXMgd2UgY2FuIHNlZSwgUiBnYXZlIHVzIHRoZSBlc3RpbWF0ZSBmb3IgdGhlIHJhdGUgcGFyYW1ldGVyLiBCdXQgd2UgbmVlZCB0aGUgZXN0aW1hdGUgZm9yIHRoZSBzY2FsZSBwYXJhbWV0ZXIuIFRoZSBnb29kIG5ld3MgaXMgdGhhdCB3ZSBjYW4gZ2V0IHRoZSBlc3RpbWF0ZSBmb3IgdGhlIHNjYWxlIHBhcmFtZXRlciwgYXMgaXQgaXMganVzdCB0aGUgaW52ZXJzZSBvZiB0aGUgcmF0ZSBwYXJhbWV0ZXIuIEluIG90aGVyIHdvcmRzLCBzY2FsZSA9IDEvcmF0ZS4NCg0KYGBge3J9DQptbGUuZml0IDwtIDEvZXhwb25lbnRpYWwuZml0JGVzdGltYXRlDQptbGUuZml0DQpgYGANCg0KIyBQYXJ0IEMNCkZvciB0aGlzIHBhcnQsIHdlIHdpbGwgY29uZHVjdCB0aGUgZmlyc3Qgb2YgdHdvIGh5cG90aGVzaXMgdGVzdHMgdG8gZGV0ZXJtaW5lIHdoZXRoZXIgb3Igbm90IHRoaXMgZGF0YSBjb21lcyBmcm9tIGEgV2VpYnVsbCBkaXN0cmlidXRpb24gb3IgYW4gZXhwb25lbnRpYWwgZGlzdHJpYnV0aW9uLiBTcGVjaWZpY2FsbHksIHdlIHdpbGwgY29uZHVjdCBhIGxpa2VsaWhvb2QgcmF0aW8gJFxjaGleMiQgdGVzdC4gT3VyIG51bGwgaHlwb3RoZXNpcywgJEhfMCQsIGlzIHRoYXQgdGhpcyBkYXRhIGNvbWVzIGZyb20gYW4gZXhwb25lbnRpYWwgZGlzdHJpYnV0aW9uLiBJbiBvdGhlciB3b3Jkcywgb3VyIG51bGwgaHlwb3RoZXNpcyBpcyB0aGF0ICRcYmV0YSA9IDEkLiBPdXIgYWx0ZXJuYXRpdmUgaHlwb3RoZXNpcywgJEhfYSQsIGlzIHRoYXQgaXQgb3VyIGRhdGEgY29tZXMgZnJvbSBhIFdlaWJ1bGwgZGlzdHJpYnV0aW9uLiBJbiBvdGhlciB3b3Jkcywgb3VyIGFsdGVybmF0aXZlIGh5cG90aGVzaXMgaXMgdGhhdCAkXGJldGEgXG5lcSAxJC4gVG8gcHV0IGludG8gc3ltYm9sczoNCiQkDQpIXzA6IFxiZXRhID0gMSAoRXhwb25lbnRpYWwpIFxcDQpIX2E6IFxiZXRhIFxuZXEgMSAoV2VpYnVsbCkNCiQkIA0KDQpUaGlzIHRlc3Qgd2lsbCBiZSBkb25lIGF0IHNpZ25pZmljYW5jZSBsZXZlbCAkXGFscGhhID0gMC4wNSQuIA0KYGBge3J9DQojIyBMaWtlbGlob29kIFJhdGlvIFRlc3QgdXNpbmcgYm90aCBMb2ctTGlrZWxpaG9vZCBGdW5jdGlvbnMNCg0KIyBXZWlidWxsIExvZy1MaWtlbGlob29kIEZ1bmN0aW9uDQpsb2dsaWtlLndlaWJ1bGwgPC0gZnVuY3Rpb24oZGF0YSwgbGFtYmRhLCBiZXRhKXsNCiAgbiA8LSBsZW5ndGgoZGF0YSkNCiAgbipsb2coYmV0YSktbipiZXRhKmxvZyhsYW1iZGEpKyhiZXRhLTEpKnN1bShsb2coZGF0YSkpLXN1bSgoZGF0YS9sYW1iZGEpXmJldGEpDQp9DQoNCiMgRXhwb25lbnRpYWwgTG9nLUxpa2VsaWhvb2QgRnVuY3Rpb24NCmxvZ2xpa2UuZXhwb25lbnRpYWwgPC0gZnVuY3Rpb24oZGF0YSwgbGFtYmRhKXsgDQogIG4gPC0gbGVuZ3RoKGRhdGEpDQogIC1uKmxvZyhsYW1iZGEpLXN1bShkYXRhKS9sYW1iZGENCn0NCg0KIyMgRXZhbHVhdGUgTG9nIExpa2VsaWhvb2QgQCBNTEUNCnNjYWxlLmVzdC53ZWlidWxsIDwtIG1sZS5yZXN1bHQud2VpYnVsbCRwYXJbWzJdXQ0Kc2hhcGUuZXN0LndlaWJ1bGwgPC0gbWxlLnJlc3VsdC53ZWlidWxsJHBhcltbMV1dDQpzY2FsZS5lc3QuZXhwb25lbnRpYWwgPC0gbWxlLmZpdA0KDQojIEV4cG9uZW50aWFsIHZzIFdlaWJ1bGwgSHlwb3RoZXNlcw0KTG9nTGlrZS5BbHQgPC0gbG9nbGlrZS53ZWlidWxsKHRpbWVzLCBzY2FsZS5lc3Qud2VpYnVsbCwgc2hhcGUuZXN0LndlaWJ1bGwpDQpMb2dMaWtlLk51bGwgPC0gbG9nbGlrZS5leHBvbmVudGlhbCh0aW1lcywgc2NhbGUuZXN0LmV4cG9uZW50aWFsKQ0KDQpyYXRpbyA8LSAyKihMb2dMaWtlLkFsdCAtIExvZ0xpa2UuTnVsbCkgI0NvbXB1dGVzIGxpa2VsaWhvb2QgcmF0aW8NCg0KIyMgR2V0dGluZyBwLXZhbHVlIGZvciByYXRpbyB0ZXN0DQpwdmFsdWUucmF0aW8gPC0gMSAtIHBjaGlzcShyYXRpbywgZGYgPSAxKSAjR2V0cyBwLXZhbHVlDQoNCiMgU1RhdGlzdGljIGFuZCBwLXZhbHVlIHRvZ2V0aGVyDQp0ZXN0MSA8LSBjKHJhdGlvLCBwdmFsdWUucmF0aW8pDQp0ZXN0MQ0KYGBgDQpPdXIgJFxjaGleMiQgc3RhdGlzdGljIGlzIDEwMC42MTQ0LCBhbmQgdGhlIHAtdmFsdWUgaXMgJFxhcHByb3gkIDAsIHdoaWNoIHNvIGl0J3Mgc2FmZSB0byBzYXkgdGhhdCB3ZSBjYW4gcmVqZWN0IHRoZSBudWxsIGh5cG90aGVzaXMgYW5kIGNvbmNsdWRlIHRoYXQgdGhlcmUgaXMgc3VmZmljaWVudCBldmlkZW5jZSB0byBzYXkgdGhhdCB0aGlzIHNhbXBsZSBjYW1lIGZyb20gYW4gd2VpYnVsbCBkaXN0cmlidXRpb24uDQoNCiMgUGFydCBEDQpGb3IgdGhpcyBwYXJ0LCB3ZSB3aWxsIGNvbmR1Y3QgdGhlIHNlY29uZCBvZiBvdXIgaHlwb3RoZXNpcyB0ZXN0cyB0byBkZXRlcm1pbmUgd2hldGhlciBvciBub3QgdGhpcyBzYW1wbGUgY2FtZSBmcm9tIGEgV2VpYnVsbCBkaXN0cmlidXRpb24gb3IgYW4gZXhwb25lbnRpYWwgZGlzdHJpYnV0aW9uLiBTcGVjaWZpY2FsbHksIHdlIHdpbGwgdXNlIGEgYm9vdHN0cmFwcGVkIGxpa2VsaWhvb2QgcmF0aW8gaHlwb3RoZXNpcyB0ZXN0LiBUaGUgbnVsbCBoeXBvdGhlc2lzLCB0aGUgYWx0ZXJuYXRpdmUgaHlwb3RoZXNpcywgYW5kIHRoZSBsZXZlbCBvZiBzaWduaWZpY2FuY2Ugd2lsbCBiZSB0aGUgc2FtZSBhcyB0aGUgbGlrZWxpaG9vZCByYXRpbyB0ZXN0IGZyb20gUGFydCBDLg0KDQoNCmBgYHtyfQ0KIyBCb290c3RyYXAgTGlrZWxpaG9vZCBSYXRpbyB0ZXN0IGZvciBub3JtYWwgbWVhbg0Kc2V0LnNlZWQoMSkNCg0KYm9vdHN0cmFwX2xydF90ZXN0IDwtIGZ1bmN0aW9uKGRhdGEsIHNjYWxlXzAsIEIgPSAxMDAwMCkgew0KDQpuIDwtIGxlbmd0aChkYXRhKQ0KDQojIE1MRSBvZiBFeHBvbmVudGlhbA0Kc2NhbGVfaGF0IDwtIG1lYW4oZGF0YSkNCg0Kc2NhbGVfMCA8LSBtZWFuKGRhdGEpDQogICAgDQojIExvZy1saWtlbGlob29kcw0KbG9nTF9oYXQgPC0gc3VtKGRleHAoZGF0YSwgcmF0ZSA9IDEvc2NhbGVfaGF0LCBsb2cgPSBUUlVFKSkNCmxvZ0wwIDwtIHN1bShkZXhwKGRhdGEsIHJhdGUgPSAxL3NjYWxlXzAsIGxvZyA9IFRSVUUpKQ0KDQogICAgDQojIExpa2VsaWhvb2QgUmF0aW8gVGVzdCBTdGF0aXN0aWMNCkxSX29icyA8LSAtMiAqIChsb2dMMCAtIGxvZ0xfaGF0KQ0KDQojIEJvb3RzdHJhcCBkaXN0cmlidXRpb24NCkxSX3N0YXIgPC0gbnVtZXJpYyhCKQ0KICAgIGZvciAoYiBpbiAxOkIpIHsNCiMgR2VuZXJhdGUgZGF0YSB1bmRlciBIMDogRXhwKFNjYWxlKQ0KICAgICAgICAgYnNfc2FtcGxlIDwtIHJleHAobiwgcmF0ZSA9IDEvc2NhbGVfMCkNCiAgICAgICAgDQogICAgICAgICMgTUxFIGZyb20gYm9vdHN0cmFwIHNhbXBsZQ0KICAgICAgICBzY2FsZV8xIDwtIG1lYW4oYnNfc2FtcGxlKQ0KICAgICAgICANCiAgICAgICAgIyBMaWtlbGlob29kcw0KICAgICAgICBsb2dMX3N0YXIgPC0gc3VtKGRleHAoYnNfc2FtcGxlLCByYXRlID0gMS9zY2FsZV9oYXQsIGxvZyA9IFRSVUUpKQ0KICAgICAgICBsb2dMX3N0YXIwIDwtIHN1bShkZXhwKGJzX3NhbXBsZSwgcmF0ZSA9IDEvc2NhbGVfMCwgbG9nID0gVFJVRSkpDQogICAgICAgIA0KICAgICAgICBMUl9zdGFyW2JdIDwtIC0yICogKGxvZ0xfc3RhcjAgLSBsb2dMX3N0YXIpDQogICAgfQ0KICAgIA0KcF92YWx1ZSA8LSAoc3VtKExSX3N0YXIgPj0gTFJfb2JzKSArIDEpIC8gKEIgKyAxKQ0KICAgIA0KIHJldHVybihsaXN0KA0KICAgICAgICBMUl9vYnMgPSBMUl9vYnMsDQogICAgICAgIHBfdmFsdWUgPSBwX3ZhbHVlLA0KICAgICAgICBzY2FsZV8xID0gc2NhbGVfMSwNCiAgICAgICAgc2NhbGVfMCA9IHNjYWxlXzANCiAgICApKQ0KfQ0KDQpib290c3RyYXBfbHJ0X3Rlc3QodGltZXMpDQpgYGANCkl0J3MgaGFyZCB0byBkZXRlcm1pbmUgd2hhdCBleGFjdGx5IG91ciB0ZXN0IHN0YXRpc3RpYyBpcywgYnV0IG9uZSB0aGluZyBpcyBjbGVhcjogdGhlIHAtdmFsdWUgZm9yIHRoZSB0ZXN0IGlzICRcYXBwcm94JCAxLCBzbyB0aGlzIHRpbWUgd2Ugd2lsbCBmYWlsIHRvIHJlamVjdCB0aGUgbnVsbCBoeXBvdGhlc2lzLCBhbmQgd2UgY2FuIGNvbmNsdWRlIHRoYXQgdGhlcmUgaXMgaW5zdWZmaWNpZW50IGV2aWRlbmNlIHRvIHNheSB0aGF0IHRoaXMgc2FtcGxlIGNhbWUgZnJvbSBhIHdlaWJ1bGwgZGlzdHJpYnV0aW9uLg0KDQojIFBhcnQgRQ0KVGhlIHR3byB0ZXN0cyBkaWQgbm90IGdlbmVyYXRlIHRoZSBzYW1lIHJlc3VsdC4gV2hhdCBpcyBvZGQgaXMgaG93IG11Y2ggdGhlIGJvb3RzdHJhcHBlZCBlc3RpbWF0ZSBmb3IgdGhlIHNjYWxlIHBhcmFtZXRlciBjaGFuZ2VkIGFzIG4gaW5jcmVhc2VzLiBJZiBuID0gMTAwMCwgdGhlbiB0aGUgc2NhbGUgcGFyYW1ldGVyIGlzIGVzdGltYXRlZCB0byBiZSAyNi41NTU4LiBJZiBuID0gNTAwMCwgdGhlbiB0aGUgc2NhbGUgcGFyYW1ldGVyIGlzIGVzdGltYXRlZCB0byBiZSAzMC4xMDE2Ni4gSWYgbiA9IDEwLDAwMCwgdGhlbiB0aGUgc2NhbGUgcGFyYW1ldGVyIGlzIGVzdGltYXRlZCB0byBiZSAyMi44MjYxNy4gDQoNClN0aWxsLCBiYXNlZCBvbiB0aGUgbm9uLWJvb3RzdHJhcHBlZCBsaWtlbGlob29kIHJhdGlvIHRlc3QsIGkgd291bGQgYmUgaW5jbGluZWQgdG8gYmVsaWV2ZSB0aGF0IHRoZSBXZWlidWxsIGRpc3RyaWJ1dGlvbiBpcyBhIGJldHRlciBmaXQgZm9yIHRoaXMgZGF0YS4NCg0K