Set-up
Caveats
This is very shallow discussion of linear models. Focus is on inference (i.e. hypothesis tests on regression coefficients). We leave the many other topics in linear modeling (including the assumptions of linear models) to the reader.
Linear relationships
Life is about relationships. And relationships are about co-variation: two things moving or varying together.
Let’s continue working with the data nhanes
which records, among other things, data on human heights in a sample of over 10,000 people. This data comes from a CDC survey.
nhanes = read_csv("https://raw.githubusercontent.com/lrdegeest/r_for_data_science/main/data/nhanes.csv")
Consider the simple relationship between height and weight. Do you get heavier when you get taller?
Plot the relationship between height and weight and include a regression line:
nhanes %>%
ggplot(data = ., aes(x = weight, y = height)) +
geom_point() +
geom_smooth(method = 'lm')
That blue line is the linear model:
\[
\begin{aligned}
\text{weight} &= f(\text{height}) + \epsilon \\
&= \beta_0 + \beta_1\text{height} + \epsilon
\end{aligned}
\]
and we know we can estimate the parameters of our model with lm
:
lm(formula = weight ~ height, data = nhanes)
Call:
lm(formula = weight ~ height, data = nhanes)
Coefficients:
(Intercept) height
-55.4073 0.7593
But how exactly are those values chosen?
OLS is a minimization problem
lm()
is an example of Ordinary Least Squares. It fits a line through a spray of points by solving a minimization problem.
What to minimize? Well, how about minimizing the error, or the difference between the observed value (\(y\)) and the predicted value (\(\hat{y}\))?
The idea is to find the “least costly” line (cost in terms of error). Set up the cost function \(C\)
\[
\begin{aligned}
C(\cdot) &= \sum_{i=1}^n (y_i - \hat{y_i})^2 \\
&= \sum_{i=1}^n (y_i - (\hat{\beta_0} + \hat{\beta_1}\text{height}))^2
\end{aligned}
\]
This is a straightforward calculus problem: find the values of \(\beta_0\) and \(\beta_1\) that minimize the cost function. The problem can be written as
\[
(\hat{\beta_0}, \hat{\beta_1}) = \underset{\beta_0, \beta_1}{\operatorname{argmin}} C(\cdot)
\]
and the solutions \(\hat{\beta_0}\) and \(\hat{beta_1}\) (the estimates of \(\beta_0\) and \(\beta_1\)) are the values of the parameters that satisfy the first-order condition, i.e. the points where the gradient (vector of first derivatives) is equal to zero:
\[
\nabla C =
\begin{bmatrix}
\frac{\partial C}{\partial \beta_0}\\
\frac{\partial C}{\partial \beta_1}
\end{bmatrix}
= 0
\]
One way to solve this problem is through maximum likelihood (MLE), a general method of optimizing a function to data (or “finding the parameters that maximize the likelihood of the data”, hence “maximum likelihood”). Let’s see it in action using R’s built-in optimizer optim
:
# set up a likelihood function
ols_log_likelihood = function(theta){
x = as.matrix(nhanes$height)
X = cbind(1,x)
y = as.matrix(nhanes$weight)
k = ncol(X)
beta = theta[1:k]
sigma = theta[k+1]
expected_y = X %*% beta
LL = sum(dnorm(y, mean = expected_y, sd = sigma, log = TRUE))
return(-LL)
}
# optimize it with starting values
ml_estimate = optim(ols_log_likelihood, par=c(1, 1, 1))
# coefficient on height
ml_estimate$par[1]
[1] 0.7595684
MLE is a general algorithm to find the parameters that best fit the data. It can be used for many different function forms. OLS is a special case of MLE when we assume the functional form is linear (and errors are normally distributed). When we solve \(\nabla C = = 0\) we derive the familiar formula for the slope coefficient:
\[
\hat{\beta_1} = \frac{\sum_{i=1}^n (x_i - \bar{y})(x_i - \bar{y})}{\sum_{i=1}^n (x_i - \bar{x})^2} = \frac{\text{Cov}(x,y)}{\text{Var}(x)}
\] and for the intercept:
\[
\hat{\beta_0} = \bar{y} - \hat{\beta_1}\bar{x}
\] The OLS solutions can also be expressed in matrix from:
\[
\beta = (X'X)^{-1} X'y
\] and then solved with linear algebra:
# turn the height column into a matrix
x = as.matrix(cbind(1,nhanes$height))
# turn the weight column into a matrix
y = as.matrix(nhanes$weight)
# coefficient beta_1
## t(x) = transpose of x
## solve() = inverse
## %*% = matrix multiplication
solve(t(x) %*% x) %*% t(x) %*% y
[,1]
[1,] -55.4073453
[2,] 0.7593451
This is the basic idea of what lm
is doing under the hood.
Big picture
Don’t worry about the finer details. The bigger picture is that we get (basically - the optimizer is sensitive to initial values) the same results with optim
as we do lm
.
The even bigger picture is to think about model-fitting as an optimization problem – because every estimator is solving some optimization problem. If you can set up a “cost” function, you can optimize it.
Interpretation
In the generalized linear model:
\[
\begin{aligned}
y &= f(x) \\
&= \beta_0 + \beta_1x + \epsilon
\end{aligned}
\]
where \(\beta_0\) (“beta naught”) is the intercept, \(\beta_1\) (“beta one”) is the slope, and \(\epsilon\) (“epsilon”) is the error, the slope captures how changes in \(x\) lead to changes in \(y\):
A one unit increase in \(x\) is associated with a \(\beta_1\) change in y, on average.
So in our model of weight (kilograms) and height (inches:
lm(formula = weight ~ height, data = nhanes)
Call:
lm(formula = weight ~ height, data = nhanes)
Coefficients:
(Intercept) height
-55.4073 0.7593
A one inch increase in height is associated with an average increase in weight of 0.76 kilograms.
Multiple regression
But do we really think that weight only depends on height?
For instance, what about sex? Does weight vary on average between men and women?
nhanes %>%
group_by(sex) %>% #
summarise(mean_weight = mean(weight))
So if we estimate lm(weight ~ height, data = nhanes)
, are we really capturing the effect of height on weight?
Or are we also picking up the “signals” or effects of other variables (like sex) on weight?
When our model fails to “pick up the signal” of omitted variables, the model suffers from omitted variable bias.
Fortunately it is straightforward to extend our model with one variable.
Multiple regression is just linear regression with multiple variables. We simply add variables to the model:
\[
\begin{aligned}
\text{weight} &= f(\text{height}, \text{sex}, \text{age}) + \epsilon \\
&= \beta_0 + \beta_1\text{height} + \beta_2\text{sex} + \beta_3\text{age} + \epsilon
\end{aligned}
\]
To estimate this multiple regression, we just need add the terms (literally) inside lm()
:
lm(formula = weight ~ height + sex + age, data = nhanes)
Call:
lm(formula = weight ~ height + sex + age, data = nhanes)
Coefficients:
(Intercept) height sexMale age
-60.3245 0.7499 1.5007 0.1217
Interpretation:
A one inch increase in height is associated with an average 0.75 kg increase in weight, controling for sex and height.
Checkpiont: “Control for”
What exactly does it mean to “control for” a variable? For example, “control for sex” (or “adjust for sex”)?
It means to account for the variation in weight due to sex.
Why control? So we can isolate the “signal” (the variation in weight due to height).
We can show this in three steps:
- Create a variable (with
mutate()
) that calculates the average height of a person by sex and add it to a new data frame called nhanes2
:
nhanes2 = nhanes %>%
group_by(sex) %>%
mutate(height_by_sex = mean(height))
- Create a variable
height_no_sex
that subtracts height
from height_by_sex
to remove the variation in height due to sex:
nhanes2 = nhanes2 %>%
mutate(height_no_sex = height - height_by_sex)
Now we have a variable height_no_sex
that is “sex neutral”.
- Finally, run a regression on weight and our new variable:
lm(formula = weight ~ height_no_sex, data = nhanes2)
Call:
lm(formula = weight ~ height_no_sex, data = nhanes2)
Coefficients:
(Intercept) height_no_sex
71.8975 0.6651
Notice how the coefficient on height_no_sex
(0.6651) is the same as the coefficient on height
(0.6651) in the model with both height
and sex
!
lm(formula = weight ~ height + sex, data = nhanes2)
Call:
lm(formula = weight ~ height + sex, data = nhanes2)
Coefficients:
(Intercept) height sexMale
-40.8465 0.6651 2.6094
Inference
We know that regression coefficients are random variables that vary across samples:
nhanes %>%
slice_sample(n = 100) %>%
lm(formula = weight ~ height + sex + age, data = .)
Call:
lm(formula = weight ~ height + sex + age, data = .)
Coefficients:
(Intercept) height sexMale age
-33.76777 0.59353 5.23529 0.08136
so we run a regression to infer about the population (the data we don’t have) from our sample (the data we do have).
Our hypothesis test on each regression coefficient essentially tests whether there is or is not a relationship between the variable and the outcome in the population:
\[
\begin{aligned}
H_0 &: \beta_1 = 0 \\
H_A &: \beta_1 \neq 0
\end{aligned}
\]
The null states the expected value of the coefficient is zero. It is like saying “on average we would find no relationship between height and weight”.
You can think of this in terms of the legal presumption of innocence:
\[
\begin{aligned}
H_0 &: \text{innocent} \\
H_A &: \text{guilty}
\end{aligned}
\]
The idea is that the prosecutor (the researcher) must gather evidence (data) to reject the defendant’s innocence (i.e. reject \(H_0\)). If the data are lacking then you fail to reject the null hypothesis.
P-values
How do we know if our evidence (data) rejects the null hypothesis?
Our estimate for \(\beta_1\) (the effect of height) is about 0.75. But consider this thought experiment.
If the null hypothesis were correct, and \(E[\beta_1] = 0\) (on average there is no effect of height)…
…then what is the probability we would observe \(\hat{\beta_1} = 0.75\)?
In other words, what is the probability we observe an effect that is not zero if the “truth” (expected value of the sampling distribution) is zero?
Reject or fail to reject
We cannot prove things with data.
Why?
Because we observe samples of the population, not the population itself.
We use those samples to infer about the population.
We then use hypotheses to do inference.
And since we cannot prove anything, we can only reject or fail to reject hypotheses.
If the probability is very close to zero, then it is unlikely the null hypothesis is true, and we can reject it.
But if the probability is very close to one, the it is likely the null hypothesis is true, and we fail to reject it.
P-values with summary()
This probability is called a p-value.
P-values are calculated for you with the function summary()
.
summary()
takes the output of lm()
and spits out the estimated coefficients – as well the hypothesis tests and other regression diagnostics.
Let’s see this with a random sample:
set.seed(123)
nhanes %>%
slice_sample(n = 100) %>%
lm(formula = weight ~ height + sex + age, data = .) %>%
summary()
Call:
lm(formula = weight ~ height + sex + age, data = .)
Residuals:
Min 1Q Median 3Q Max
-26.452 -9.325 -1.360 6.163 50.331
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) -32.70723 35.40902 -0.924 0.3580
height 0.58763 0.20994 2.799 0.0062 **
sexMale 2.01869 3.71059 0.544 0.5877
age 0.07428 0.07947 0.935 0.3523
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Residual standard error: 12.9 on 96 degrees of freedom
Multiple R-squared: 0.179, Adjusted R-squared: 0.1533
F-statistic: 6.975 on 3 and 96 DF, p-value: 0.0002701
The p-values are shown in the column Pr(>|t|)
.
Interpretating p-values
If the probability is very close to zero, then it is unlikely the null hypothesis is true, and we can reject it.
How close to zero is close enough?
There is no hard-and-fast rule. So science has coordinated on a set of thresholds so that the convention is to compare your p-values to these thresholds:
- 10% or 0.10: “weak evidence to reject \(H_0\)”
- 5% or 0.05: “evidence to reject \(H_0\)”
- 1% or 0.01: “strong evidence to reject \(H_0\)”
If the p-value is below a threshold, say 5%, we say that we reject the null hypothesis at the 5% level.
And if we reject the null, we say the effect is statistically significant.
Let’s apply this to our coefficients:
- The p-value to
height
is 0.00. We reject at the 1% level. Statistically significant.
- The p-value to
age
is 0.00. We reject at the 1% level. Statistically significant.
- The p-value to
sex==Male
is 0.00. We reject at the 1% level. Statistically significant.
Illustrating p-values
The p-value is the probability of the test statistic under a true null hypothesis. Let’s unpack this.
The test statistic or t-value is the coefficient divided by it’s standard error. The test statistic for our coefficient on height is:
[1] 2.799038
The p-value is the two-tailed probability of this value for our degrees of freedom \(n - k\). We have \(n=100\) (our random sample) and \(k=4\) (three coefficients and an intercept), so:
2*pt(-abs(2.799038), df = 100 - 4)
[1] 0.006195828
This is number is literally the area underneath the curve of the t-distribution, which is centered at zero (the null hypothesis):
# set the test stat
test_stat = 2.799038
# create a bunch of t-stats
t_values = seq(from=-4, to=4, by = 0.01)
# calculate the densities for each element
t_densities = dt(t_values, df = length(t_values) - 1)
# make a dataframe out of the t_value and t_density
t_dataframe = tibble("t_value" = t_values, "t_density" = t_densities)
# plot the t-distribution
ggplot(t_dataframe, aes(x=t_value, y=t_density)) +
geom_line() +
geom_area(aes(t_values) , fill = "gray") +
geom_vline(xintercept = test_stat, color="red") +
geom_vline(xintercept = -test_stat, color="red") +
geom_area(data = filter(t_dataframe, t_value > test_stat), fill="red") +
geom_area(data = filter(t_dataframe, t_value < -test_stat), fill="red") +
labs(x = "t stat", y = "P(t stat)")
and so the p-value is just the integral from \(-\infty\) to -2.799038 for the lower tail, and times two for the upper tail:
2*integrate(f = function(x) dt(x, df = 96), lower = -Inf, upper = -2.799038)$value
The probability is small because the area under the curve is small. By contrast, plot the p-value for the test stat on age
:
# set the test stat
test_stat = 0.935
# create a bunch of t-stats
t_values = seq(from=-4, to=4, by = 0.01)
# calculate the densities for each element
t_densities = dt(t_values, df = length(t_values) - 1)
# make a dataframe out of the t_value and t_density
t_dataframe = tibble("t_value" = t_values, "t_density" = t_densities)
Warning in readChar(file, size, TRUE) :
truncating string with embedded nuls
Warning in readChar(file, size, TRUE) :
truncating string with embedded nuls
Warning in readChar(file, size, TRUE) :
truncating string with embedded nuls
# plot the t-distribution
ggplot(t_dataframe, aes(x=t_value, y=t_density)) +
geom_line() +
geom_area(aes(t_values) , fill = "gray") +
geom_vline(xintercept = test_stat, color="red") +
geom_vline(xintercept = -test_stat, color="red") +
geom_area(data = filter(t_dataframe, t_value > test_stat), fill="red") +
geom_area(data = filter(t_dataframe, t_value < -test_stat), fill="red") +
labs(x = "t stat", y = "P(t stat)")
The thing to keep in mind about p-values is they are massively influenced by the amount of data. This is because the test statistic is the coefficient divided by the standard error, and the standard error is divided by the square root of the number of observations. So if we increase the sample size:
nhanes %>%
slice_sample(n = 1000) %>%
lm(formula = weight ~ height + sex + age, data = .) %>%
summary()
Call:
lm(formula = weight ~ height + sex + age, data = .)
Residuals:
Min 1Q Median 3Q Max
-38.839 -9.118 -1.956 7.117 75.414
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) -35.10780 11.06138 -3.174 0.00155 **
height 0.60110 0.06623 9.077 < 2e-16 ***
sexMale 2.11225 1.24816 1.692 0.09090 .
age 0.11505 0.02567 4.482 8.26e-06 ***
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Residual standard error: 13.39 on 996 degrees of freedom
Multiple R-squared: 0.1928, Adjusted R-squared: 0.1904
F-statistic: 79.29 on 3 and 996 DF, p-value: < 2.2e-16
more often than not we reject null hypotheses.
Keep this in mind when if you run a regression on thousands or millions of data points. Significant coefficients aren’t that meaningful, and you have to think harder about why variables might be related. By contrast, it’s more meaningful if you don’t find a significant relationship!
Tidy models
The output of summary()
is clearly not tidy data. The package broom
makes it easier to work with model objects.
Say we have this model:
model = nhanes %>%
lm(formula = weight ~ height + sex + age, data = .)
tidy()
turns the model into a tibble:
and augment()
“augments” the model by creating a tibble and adding predicted values, residuals, and other stuff:
Checkpoint
Draw 500 random values from diamonds
and estimate log prices as a function of carats, table, depth and color. Assign the model to the object diamonds_model
. Use a mutated variable “log_prices” (this make it easier to use broom
).
set.seed(123)
model_diamonds = diamonds %>%
slice_sample(n = 500) %>%
mutate(log_price = log(price)) %>%
lm(formula = log_price ~ carat + table + depth + color, data = .)
summary(model_diamonds)
Call:
lm(formula = log_price ~ carat + table + depth + color, data = .)
Residuals:
Min 1Q Median 3Q Max
-1.13876 -0.20807 0.05122 0.23060 0.89644
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 6.365288 0.890000 7.152 3.13e-12 ***
carat 2.117769 0.035346 59.915 < 2e-16 ***
table 0.007380 0.007345 1.005 0.3155
depth -0.012092 0.011249 -1.075 0.2829
color.L -0.426183 0.054640 -7.800 3.76e-14 ***
color.Q -0.202207 0.050293 -4.021 6.72e-05 ***
color.C -0.050637 0.047388 -1.069 0.2858
color^4 0.018607 0.044357 0.419 0.6750
color^5 -0.041540 0.040047 -1.037 0.3001
color^6 -0.076617 0.035875 -2.136 0.0332 *
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Residual standard error: 0.343 on 490 degrees of freedom
Multiple R-squared: 0.8888, Adjusted R-squared: 0.8867
F-statistic: 435.1 on 9 and 490 DF, p-value: < 2.2e-16
Verify the test statistic for the coefficient on table:
[1] 1.004765
Verify the p-value for the coefficient on table:
2*pt(-abs(1.004765), df = 490)
[1] 0.3155059
Calculate the average squared error of the model, i.e. the average difference between observed log prices and predicted log prices:
broom::augment(model_diamonds) %>%
summarise(avg_error = mean((log_price - .fitted)^2))
LS0tCnRpdGxlOiAiTGluZWFyIE1vZGVscyAoQ29tcGxldGVkIE5vdGVib29rKSIKc3VidGl0bGU6ICJSIGZvciBEYXRhIFNjaWVuY2UiCmF1dGhvcjogIkxERyIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOgogICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCiAgICB0aGVtZTogcmVhZGFibGUKICAgIGhpZ2hsaWdodDogcHlnbWVudHMKICAgIHRvYzogdHJ1ZQogICAgdG9jX2Zsb2F0OiAKICAgICAgY29sbGFwc2VkOiB5ZXMgICAgICAKLS0tCgojIFNldC11cCB7LX0KIApgYGB7ciBsb2FkIHBhY2thZ2VzLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKYGBgCgojIyBDYXZlYXRzIHstfQoKVGhpcyBpcyAqKnZlcnkqKiBzaGFsbG93IGRpc2N1c3Npb24gb2YgbGluZWFyIG1vZGVscy4gRm9jdXMgaXMgb24gKippbmZlcmVuY2UqKiAoaS5lLiBoeXBvdGhlc2lzIHRlc3RzIG9uIHJlZ3Jlc3Npb24gY29lZmZpY2llbnRzKS4gV2UgbGVhdmUgdGhlIG1hbnkgb3RoZXIgdG9waWNzIGluIGxpbmVhciBtb2RlbGluZyAoaW5jbHVkaW5nIHRoZSBhc3N1bXB0aW9ucyBvZiBsaW5lYXIgbW9kZWxzKSB0byB0aGUgcmVhZGVyLiAKCiMgTGluZWFyIHJlbGF0aW9uc2hpcHMKCkxpZmUgaXMgYWJvdXQgcmVsYXRpb25zaGlwcy4gQW5kIHJlbGF0aW9uc2hpcHMgYXJlIGFib3V0ICoqY28tdmFyaWF0aW9uKio6IHR3byB0aGluZ3MgbW92aW5nIG9yIHZhcnlpbmcgdG9nZXRoZXIuICAKCkxldCdzIGNvbnRpbnVlIHdvcmtpbmcgd2l0aCB0aGUgZGF0YSBgbmhhbmVzYCB3aGljaCByZWNvcmRzLCBhbW9uZyBvdGhlciB0aGluZ3MsIGRhdGEgb24gaHVtYW4gaGVpZ2h0cyBpbiBhIHNhbXBsZSBvZiBvdmVyIDEwLDAwMCBwZW9wbGUuIFRoaXMgZGF0YSBjb21lcyBmcm9tIGEgW0NEQyBzdXJ2ZXldKGh0dHBzOi8vd3d3bi5jZGMuZ292L25jaHMvbmhhbmVzL2NvbnRpbnU9b3VzbmhhbmVzL2RlZmF1bHQuYXNweCkuIAoKYGBge3IgbG9hZCBuaGFuZXMsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZT1GQUxTRX0KbmhhbmVzID0gcmVhZF9jc3YoImh0dHBzOi8vcmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbS9scmRlZ2Vlc3Qvcl9mb3JfZGF0YV9zY2llbmNlL21haW4vZGF0YS9uaGFuZXMuY3N2IikKYGBgCgpDb25zaWRlciB0aGUgc2ltcGxlIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIGhlaWdodCBhbmQgd2VpZ2h0LiBEbyB5b3UgZ2V0IGhlYXZpZXIgd2hlbiB5b3UgZ2V0IHRhbGxlcj8gCgpQbG90IHRoZSByZWxhdGlvbnNoaXAgYmV0d2VlbiBoZWlnaHQgYW5kIHdlaWdodCBhbmQgaW5jbHVkZSBhIHJlZ3Jlc3Npb24gbGluZToKCmBgYHtyIHBsb3Qgd2VpZ2h0IGhlaWdodH0KbmhhbmVzICU+JSAKICBnZ3Bsb3QoZGF0YSA9IC4sIGFlcyh4ID0gd2VpZ2h0LCB5ID0gaGVpZ2h0KSkgKyAKICBnZW9tX3BvaW50KCkgKyAKICBnZW9tX3Ntb290aChtZXRob2QgPSAnbG0nKQpgYGAKClRoYXQgYmx1ZSBsaW5lIGlzIHRoZSBsaW5lYXIgbW9kZWw6CgokJApcYmVnaW57YWxpZ25lZH0KXHRleHR7d2VpZ2h0fSAmPSBmKFx0ZXh0e2hlaWdodH0pICsgXGVwc2lsb24gXFwKICAgICAgICAgICAgICAgICY9IFxiZXRhXzAgKyBcYmV0YV8xXHRleHR7aGVpZ2h0fSArIFxlcHNpbG9uClxlbmR7YWxpZ25lZH0KJCQKCmFuZCB3ZSBrbm93IHdlIGNhbiBlc3RpbWF0ZSB0aGUgKipwYXJhbWV0ZXJzKiogb2Ygb3VyIG1vZGVsIHdpdGggYGxtYDoKCmBgYHtyIGxtIHdlaWdodCBoZWlnaHR9CmxtKGZvcm11bGEgPSB3ZWlnaHQgfiBoZWlnaHQsIGRhdGEgPSBuaGFuZXMpCmBgYAoKQnV0IGhvdyBleGFjdGx5IGFyZSB0aG9zZSB2YWx1ZXMgY2hvc2VuPwoKIyMgT0xTIGlzIGEgbWluaW1pemF0aW9uIHByb2JsZW0KCmBsbSgpYCBpcyBhbiBleGFtcGxlIG9mICoqT3JkaW5hcnkgTGVhc3QgU3F1YXJlcyoqLiBJdCBmaXRzIGEgbGluZSB0aHJvdWdoIGEgc3ByYXkgb2YgcG9pbnRzIGJ5IHNvbHZpbmcgYSAqKm1pbmltaXphdGlvbioqIHByb2JsZW0uIAoKV2hhdCB0byBtaW5pbWl6ZT8gV2VsbCwgaG93IGFib3V0IG1pbmltaXppbmcgdGhlICoqZXJyb3IqKiwgb3IgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgKipvYnNlcnZlZCoqIHZhbHVlICgkeSQpIGFuZCB0aGUgKipwcmVkaWN0ZWQqKiB2YWx1ZSAoJFxoYXR7eX0kKT8KClRoZSBpZGVhIGlzIHRvIGZpbmQgdGhlICJsZWFzdCBjb3N0bHkiIGxpbmUgKGNvc3QgaW4gdGVybXMgb2YgZXJyb3IpLiBTZXQgdXAgdGhlIGNvc3QgZnVuY3Rpb24gJEMkCgokJApcYmVnaW57YWxpZ25lZH0KICBDKFxjZG90KSAgJj0gXHN1bV97aT0xfV5uICh5X2kgLSBcaGF0e3lfaX0pXjIgXFwKICAgICAgICAgICAgICAgICY9ICBcc3VtX3tpPTF9Xm4gKHlfaSAtIChcaGF0e1xiZXRhXzB9ICsgXGhhdHtcYmV0YV8xfVx0ZXh0e2hlaWdodH0pKV4yClxlbmR7YWxpZ25lZH0KJCQKClRoaXMgaXMgYSBzdHJhaWdodGZvcndhcmQgY2FsY3VsdXMgcHJvYmxlbTogZmluZCB0aGUgdmFsdWVzIG9mICRcYmV0YV8wJCBhbmQgJFxiZXRhXzEkIHRoYXQgKiptaW5pbWl6ZSoqIHRoZSBjb3N0IGZ1bmN0aW9uLiBUaGUgcHJvYmxlbSBjYW4gYmUgd3JpdHRlbiBhcwoKJCQKKFxoYXR7XGJldGFfMH0sIFxoYXR7XGJldGFfMX0pID0gXHVuZGVyc2V0e1xiZXRhXzAsIFxiZXRhXzF9e1xvcGVyYXRvcm5hbWV7YXJnbWlufX0gQyhcY2RvdCkKJCQKCmFuZCB0aGUgc29sdXRpb25zICRcaGF0e1xiZXRhXzB9JCBhbmQgJFxoYXR7YmV0YV8xfSQgKHRoZSBlc3RpbWF0ZXMgb2YgJFxiZXRhXzAkIGFuZCAkXGJldGFfMSQpIGFyZSB0aGUgdmFsdWVzIG9mIHRoZSBwYXJhbWV0ZXJzIHRoYXQgc2F0aXNmeSB0aGUgKipmaXJzdC1vcmRlciBjb25kaXRpb24qKiwgaS5lLiB0aGUgcG9pbnRzIHdoZXJlIHRoZSBncmFkaWVudCAodmVjdG9yIG9mIGZpcnN0IGRlcml2YXRpdmVzKSBpcyBlcXVhbCB0byB6ZXJvOgoKJCQKXG5hYmxhIEMgPSAKXGJlZ2lue2JtYXRyaXh9CiAgXGZyYWN7XHBhcnRpYWwgQ317XHBhcnRpYWwgXGJldGFfMH1cXAogIFxmcmFje1xwYXJ0aWFsIEN9e1xwYXJ0aWFsIFxiZXRhXzF9IApcZW5ke2JtYXRyaXh9Cj0gMAokJAoKT25lIHdheSB0byBzb2x2ZSB0aGlzIHByb2JsZW0gaXMgdGhyb3VnaCAqKm1heGltdW0gbGlrZWxpaG9vZCoqIChNTEUpLCBhIGdlbmVyYWwgbWV0aG9kIG9mIG9wdGltaXppbmcgYSBmdW5jdGlvbiB0byBkYXRhIChvciAiZmluZGluZyB0aGUgcGFyYW1ldGVycyB0aGF0IG1heGltaXplIHRoZSBsaWtlbGlob29kIG9mIHRoZSBkYXRhIiwgaGVuY2UgIm1heGltdW0gbGlrZWxpaG9vZCIpLiBMZXQncyBzZWUgaXQgaW4gYWN0aW9uIHVzaW5nIFIncyBidWlsdC1pbiBvcHRpbWl6ZXIgYG9wdGltYDoKCmBgYHtyIG9scyBtbGV9CiMgc2V0IHVwIGEgbGlrZWxpaG9vZCBmdW5jdGlvbgpvbHNfbG9nX2xpa2VsaWhvb2QgPSBmdW5jdGlvbih0aGV0YSl7CiAgeCA9IGFzLm1hdHJpeChuaGFuZXMkaGVpZ2h0KQogIFggPSBjYmluZCgxLHgpCiAgeSA9IGFzLm1hdHJpeChuaGFuZXMkd2VpZ2h0KQogIGsgPSBuY29sKFgpCiAgYmV0YSA9IHRoZXRhWzE6a10KICBzaWdtYSA9IHRoZXRhW2srMV0KICBleHBlY3RlZF95ID0gWCAlKiUgYmV0YSAKICBMTCA9IHN1bShkbm9ybSh5LCBtZWFuID0gZXhwZWN0ZWRfeSwgc2QgPSBzaWdtYSwgbG9nID0gVFJVRSkpCiAgcmV0dXJuKC1MTCkKfQoKIyBvcHRpbWl6ZSBpdCB3aXRoIHN0YXJ0aW5nIHZhbHVlcwptbF9lc3RpbWF0ZSA9IG9wdGltKG9sc19sb2dfbGlrZWxpaG9vZCwgcGFyPWMoMSwgMSwgMSkpCiMgY29lZmZpY2llbnQgb24gaGVpZ2h0Cm1sX2VzdGltYXRlJHBhclsxXQpgYGAKCk1MRSBpcyBhIGdlbmVyYWwgYWxnb3JpdGhtIHRvIGZpbmQgdGhlIHBhcmFtZXRlcnMgdGhhdCBiZXN0IGZpdCB0aGUgZGF0YS4gSXQgY2FuIGJlIHVzZWQgZm9yIG1hbnkgZGlmZmVyZW50IGZ1bmN0aW9uIGZvcm1zLiBPTFMgaXMgYSBzcGVjaWFsIGNhc2Ugb2YgTUxFIHdoZW4gd2UgYXNzdW1lIHRoZSBmdW5jdGlvbmFsIGZvcm0gaXMgbGluZWFyIChhbmQgZXJyb3JzIGFyZSBub3JtYWxseSBkaXN0cmlidXRlZCkuIFdoZW4gd2Ugc29sdmUgJFxuYWJsYSBDID0gID0gMCQgd2UgZGVyaXZlIHRoZSBmYW1pbGlhciBmb3JtdWxhIGZvciB0aGUgc2xvcGUgY29lZmZpY2llbnQ6CgokJApcaGF0e1xiZXRhXzF9ID0gXGZyYWN7XHN1bV97aT0xfV5uICh4X2kgLSBcYmFye3l9KSh4X2kgLSBcYmFye3l9KX17XHN1bV97aT0xfV5uICh4X2kgLSBcYmFye3h9KV4yfSA9IFxmcmFje1x0ZXh0e0Nvdn0oeCx5KX17XHRleHR7VmFyfSh4KX0KJCQKYW5kIGZvciB0aGUgaW50ZXJjZXB0OgoKJCQKXGhhdHtcYmV0YV8wfSA9IFxiYXJ7eX0gLSBcaGF0e1xiZXRhXzF9XGJhcnt4fQokJApUaGUgT0xTIHNvbHV0aW9ucyBjYW4gYWxzbyBiZSBleHByZXNzZWQgaW4gbWF0cml4IGZyb206CgokJApcYmV0YSA9IChYJ1gpXnstMX0gWCd5CiQkCmFuZCB0aGVuIHNvbHZlZCB3aXRoIGxpbmVhciBhbGdlYnJhOgoKYGBge3Igb2xzIGxpbiBhbGd9CiMgdHVybiB0aGUgaGVpZ2h0IGNvbHVtbiBpbnRvIGEgbWF0cml4CnggPSBhcy5tYXRyaXgoY2JpbmQoMSxuaGFuZXMkaGVpZ2h0KSkKIyB0dXJuIHRoZSB3ZWlnaHQgY29sdW1uIGludG8gYSBtYXRyaXgKeSA9IGFzLm1hdHJpeChuaGFuZXMkd2VpZ2h0KQojIGNvZWZmaWNpZW50IGJldGFfMQojIyB0KHgpID0gdHJhbnNwb3NlIG9mIHgKIyMgc29sdmUoKSA9IGludmVyc2UKIyMgJSolID0gbWF0cml4IG11bHRpcGxpY2F0aW9uCnNvbHZlKHQoeCkgJSolIHgpICUqJSB0KHgpICUqJSB5CmBgYAoKVGhpcyBpcyB0aGUgYmFzaWMgaWRlYSBvZiB3aGF0IGBsbWAgaXMgZG9pbmcgdW5kZXIgdGhlIGhvb2QuCgojIyBCaWcgcGljdHVyZQoKRG9uJ3Qgd29ycnkgYWJvdXQgdGhlIGZpbmVyIGRldGFpbHMuIFRoZSBiaWdnZXIgcGljdHVyZSBpcyB0aGF0IHdlIGdldCAoYmFzaWNhbGx5IC0gdGhlIG9wdGltaXplciBpcyBzZW5zaXRpdmUgdG8gaW5pdGlhbCB2YWx1ZXMpIHRoZSBzYW1lIHJlc3VsdHMgd2l0aCBgb3B0aW1gIGFzIHdlIGRvIGBsbWAuIAoKVGhlIGV2ZW4gYmlnZ2VyIHBpY3R1cmUgaXMgdG8gdGhpbmsgYWJvdXQgbW9kZWwtZml0dGluZyBhcyBhbiBvcHRpbWl6YXRpb24gcHJvYmxlbSAtLSBiZWNhdXNlIGV2ZXJ5IGVzdGltYXRvciBpcyBzb2x2aW5nIHNvbWUgb3B0aW1pemF0aW9uIHByb2JsZW0uIElmIHlvdSBjYW4gc2V0IHVwIGEgImNvc3QiIGZ1bmN0aW9uLCB5b3UgY2FuIG9wdGltaXplIGl0LiAKCiMgSW50ZXJwcmV0YXRpb24KCkluIHRoZSBnZW5lcmFsaXplZCBsaW5lYXIgbW9kZWw6CgokJApcYmVnaW57YWxpZ25lZH0KICB5ICY9IGYoeCkgXFwKICAgICY9IFxiZXRhXzAgKyBcYmV0YV8xeCArIFxlcHNpbG9uClxlbmR7YWxpZ25lZH0KJCQKCndoZXJlICRcYmV0YV8wJCAgKCJiZXRhIG5hdWdodCIpIGlzIHRoZSAqKmludGVyY2VwdCoqLCAkXGJldGFfMSQgKCJiZXRhIG9uZSIpIGlzIHRoZSAqKnNsb3BlKiosIGFuZCAkXGVwc2lsb24kICgiZXBzaWxvbiIpIGlzIHRoZSAqKmVycm9yKiosIHRoZSBzbG9wZSBjYXB0dXJlcyBob3cgY2hhbmdlcyBpbiAkeCQgbGVhZCB0byBjaGFuZ2VzIGluICR5JDogCgo+IEEgb25lIHVuaXQgaW5jcmVhc2UgaW4gJHgkIGlzIGFzc29jaWF0ZWQgd2l0aCBhICRcYmV0YV8xJCBjaGFuZ2UgaW4geSwgKipvbiBhdmVyYWdlKiouCgpTbyBpbiBvdXIgbW9kZWwgb2Ygd2VpZ2h0IChraWxvZ3JhbXMpIGFuZCBoZWlnaHQgKGluY2hlczoKCmBgYHtyIGxtIHdlaWdodCBoZWlnaHQgYWdhaW59CmxtKGZvcm11bGEgPSB3ZWlnaHQgfiBoZWlnaHQsIGRhdGEgPSBuaGFuZXMpCmBgYAoKQSBvbmUgaW5jaCBpbmNyZWFzZSBpbiBoZWlnaHQgaXMgYXNzb2NpYXRlZCB3aXRoIGFuICoqYXZlcmFnZSoqIGluY3JlYXNlIGluIHdlaWdodCBvZiAwLjc2IGtpbG9ncmFtcy4KCiMgTXVsdGlwbGUgcmVncmVzc2lvbiAKCkJ1dCBkbyB3ZSByZWFsbHkgdGhpbmsgdGhhdCB3ZWlnaHQgKm9ubHkqIGRlcGVuZHMgb24gaGVpZ2h0PyAKCkZvciBpbnN0YW5jZSwgd2hhdCBhYm91dCBzZXg/IERvZXMgd2VpZ2h0IHZhcnkgb24gYXZlcmFnZSBiZXR3ZWVuIG1lbiBhbmQgd29tZW4/CgpgYGB7ciBhdmcgd2VpZ2h0IGJ5IHNleCwgbWVzc2FnZT1GQUxTRX0KbmhhbmVzICU+JSAKICBncm91cF9ieShzZXgpICU+JSAjCiAgc3VtbWFyaXNlKG1lYW5fd2VpZ2h0ID0gbWVhbih3ZWlnaHQpKSAKYGBgCgpTbyBpZiB3ZSBlc3RpbWF0ZSBgbG0od2VpZ2h0IH4gaGVpZ2h0LCBkYXRhID0gbmhhbmVzKWAsIGFyZSB3ZSAqcmVhbGx5KiBjYXB0dXJpbmcgdGhlIGVmZmVjdCBvZiBoZWlnaHQgb24gd2VpZ2h0PyAKCk9yIGFyZSB3ZSBhbHNvIHBpY2tpbmcgdXAgdGhlICJzaWduYWxzIiBvciBlZmZlY3RzIG9mIG90aGVyIHZhcmlhYmxlcyAobGlrZSBzZXgpIG9uIHdlaWdodD8KCldoZW4gb3VyIG1vZGVsIGZhaWxzIHRvICJwaWNrIHVwIHRoZSBzaWduYWwiIG9mICoqb21pdHRlZCB2YXJpYWJsZXMqKiwgdGhlIG1vZGVsIHN1ZmZlcnMgZnJvbSAqKm9taXR0ZWQgdmFyaWFibGUgYmlhcyoqLiAKCkZvcnR1bmF0ZWx5IGl0IGlzIHN0cmFpZ2h0Zm9yd2FyZCB0byBleHRlbmQgb3VyIG1vZGVsIHdpdGggb25lIHZhcmlhYmxlLiAKCioqTXVsdGlwbGUgcmVncmVzc2lvbioqIGlzIGp1c3QgbGluZWFyIHJlZ3Jlc3Npb24gd2l0aCBtdWx0aXBsZSB2YXJpYWJsZXMuIFdlIHNpbXBseSAqKmFkZCoqIHZhcmlhYmxlcyB0byB0aGUgbW9kZWw6CgokJApcYmVnaW57YWxpZ25lZH0KXHRleHR7d2VpZ2h0fSAmPSBmKFx0ZXh0e2hlaWdodH0sIFx0ZXh0e3NleH0sIFx0ZXh0e2FnZX0pICsgXGVwc2lsb24gXFwKICAgICAgICAgICAgICAgICY9IFxiZXRhXzAgKyBcYmV0YV8xXHRleHR7aGVpZ2h0fSArIFxiZXRhXzJcdGV4dHtzZXh9ICsgXGJldGFfM1x0ZXh0e2FnZX0gKyBcZXBzaWxvbgpcZW5ke2FsaWduZWR9CiQkCgpUbyBlc3RpbWF0ZSB0aGlzIG11bHRpcGxlIHJlZ3Jlc3Npb24sIHdlIGp1c3QgbmVlZCBhZGQgdGhlIHRlcm1zIChsaXRlcmFsbHkpIGluc2lkZSBgbG0oKWA6CgpgYGB7ciBtdWx0aXBsZSByZWdyZXNzaW9ufQpsbShmb3JtdWxhID0gd2VpZ2h0IH4gaGVpZ2h0ICsgc2V4ICsgYWdlLCBkYXRhID0gbmhhbmVzKQpgYGAKCkludGVycHJldGF0aW9uOgoKPiBBIG9uZSBpbmNoIGluY3JlYXNlIGluIGhlaWdodCBpcyBhc3NvY2lhdGVkIHdpdGggYW4gYXZlcmFnZSAwLjc1IGtnIGluY3JlYXNlIGluIHdlaWdodCwgY29udHJvbGluZyBmb3Igc2V4IGFuZCBoZWlnaHQuCgojIyBDaGVja3Bpb250OiAiQ29udHJvbCBmb3IiCgpXaGF0IGV4YWN0bHkgZG9lcyBpdCBtZWFuIHRvICJjb250cm9sIGZvciIgYSB2YXJpYWJsZT8gRm9yIGV4YW1wbGUsICJjb250cm9sIGZvciBzZXgiIChvciAiYWRqdXN0IGZvciBzZXgiKT8KCkl0IG1lYW5zIHRvIGFjY291bnQgZm9yIHRoZSB2YXJpYXRpb24gaW4gd2VpZ2h0IGR1ZSB0byBzZXguIAoKV2h5IGNvbnRyb2w/IFNvIHdlIGNhbiAqKmlzb2xhdGUqKiB0aGUgInNpZ25hbCIgKHRoZSB2YXJpYXRpb24gaW4gd2VpZ2h0IGR1ZSB0byBoZWlnaHQpLgoKV2UgY2FuIHNob3cgdGhpcyBpbiB0aHJlZSBzdGVwczoKCjEuIENyZWF0ZSBhIHZhcmlhYmxlICh3aXRoIGBtdXRhdGUoKWApIHRoYXQgY2FsY3VsYXRlcyB0aGUgYXZlcmFnZSBoZWlnaHQgb2YgYSBwZXJzb24gYnkgc2V4IGFuZCBhZGQgaXQgdG8gYSBuZXcgZGF0YSBmcmFtZSBjYWxsZWQgYG5oYW5lczJgOgoKYGBge3IgbXV0YXRlIGhlaWdodF9ieV9zZXh9Cm5oYW5lczIgPSBuaGFuZXMgJT4lIAogIGdyb3VwX2J5KHNleCkgJT4lIAogIG11dGF0ZShoZWlnaHRfYnlfc2V4ID0gbWVhbihoZWlnaHQpKSAKYGBgCgoyLiBDcmVhdGUgYSB2YXJpYWJsZSBgaGVpZ2h0X25vX3NleGAgdGhhdCBzdWJ0cmFjdHMgYGhlaWdodGAgZnJvbSBgaGVpZ2h0X2J5X3NleGAgdG8gcmVtb3ZlIHRoZSB2YXJpYXRpb24gaW4gaGVpZ2h0IGR1ZSB0byBzZXg6CgpgYGB7ciBtdXRhdGUgaGVpZ2h0X25vX3NleH0KbmhhbmVzMiA9IG5oYW5lczIgJT4lIAogIG11dGF0ZShoZWlnaHRfbm9fc2V4ID0gaGVpZ2h0IC0gaGVpZ2h0X2J5X3NleCkKYGBgCgpOb3cgd2UgaGF2ZSBhIHZhcmlhYmxlIGBoZWlnaHRfbm9fc2V4YCB0aGF0IGlzICJzZXggbmV1dHJhbCIuIAoKMy4gRmluYWxseSwgcnVuIGEgcmVncmVzc2lvbiBvbiB3ZWlnaHQgYW5kIG91ciBuZXcgdmFyaWFibGU6CgpgYGB7ciByZWdyZXNzIHdlaWdodCBhcyBhIGZ1bmN0aW9uIG9mIGhlaWdodF9ub19zZXh9CmxtKGZvcm11bGEgPSB3ZWlnaHQgfiBoZWlnaHRfbm9fc2V4LCBkYXRhID0gbmhhbmVzMikKYGBgCgpOb3RpY2UgaG93IHRoZSBjb2VmZmljaWVudCBvbiBgaGVpZ2h0X25vX3NleGAgKDAuNjY1MSkgaXMgdGhlIHNhbWUgYXMgdGhlIGNvZWZmaWNpZW50IG9uIGBoZWlnaHRgICgwLjY2NTEpIGluIHRoZSBtb2RlbCB3aXRoIGJvdGggYGhlaWdodGAgYW5kIGBzZXhgIQoKYGBge3Igd2VpZ2h0IGFzIGZ1bmN0aW9uIG9mIGhlaWdodCBhbmQgc2V4fQpsbShmb3JtdWxhID0gd2VpZ2h0IH4gaGVpZ2h0ICsgc2V4LCBkYXRhID0gbmhhbmVzMikKYGBgCgojIEluZmVyZW5jZQoKV2Uga25vdyB0aGF0IHJlZ3Jlc3Npb24gY29lZmZpY2llbnRzIGFyZSAqKnJhbmRvbSB2YXJpYWJsZXMqKiB0aGF0IHZhcnkgYWNyb3NzIHNhbXBsZXM6CgpgYGB7ciByYW5kb20gdmFyaWFibGVzfQpuaGFuZXMgJT4lIAogIHNsaWNlX3NhbXBsZShuID0gMTAwKSAlPiUgCiAgbG0oZm9ybXVsYSA9IHdlaWdodCB+IGhlaWdodCArIHNleCArIGFnZSwgZGF0YSA9IC4pCmBgYAoKc28gd2UgcnVuIGEgcmVncmVzc2lvbiB0byAqKmluZmVyKiogYWJvdXQgdGhlIHBvcHVsYXRpb24gKHRoZSBkYXRhIHdlIGRvbid0IGhhdmUpIGZyb20gb3VyIHNhbXBsZSAodGhlIGRhdGEgd2UgZG8gaGF2ZSkuCgpPdXIgaHlwb3RoZXNpcyB0ZXN0IG9uIGVhY2ggcmVncmVzc2lvbiBjb2VmZmljaWVudCBlc3NlbnRpYWxseSB0ZXN0cyB3aGV0aGVyIHRoZXJlICoqaXMqKiBvciAqKmlzIG5vdCoqIGEgcmVsYXRpb25zaGlwIGJldHdlZW4gdGhlIHZhcmlhYmxlIGFuZCB0aGUgb3V0Y29tZSAqKmluIHRoZSBwb3B1bGF0aW9uKio6CgokJApcYmVnaW57YWxpZ25lZH0KSF8wICY6IFxiZXRhXzEgPSAwIFxcCkhfQSAmOiBcYmV0YV8xIFxuZXEgMApcZW5ke2FsaWduZWR9CiQkCgpUaGUgbnVsbCBzdGF0ZXMgdGhlIGV4cGVjdGVkIHZhbHVlIG9mIHRoZSBjb2VmZmljaWVudCBpcyB6ZXJvLiBJdCBpcyBsaWtlIHNheWluZyAib24gYXZlcmFnZSB3ZSB3b3VsZCBmaW5kIG5vIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIGhlaWdodCBhbmQgd2VpZ2h0Ii4gCgpZb3UgY2FuIHRoaW5rIG9mIHRoaXMgaW4gdGVybXMgb2YgdGhlIGxlZ2FsIHByZXN1bXB0aW9uIG9mIGlubm9jZW5jZToKCiQkClxiZWdpbnthbGlnbmVkfQpIXzAgJjogXHRleHR7aW5ub2NlbnR9IFxcCkhfQSAmOiBcdGV4dHtndWlsdHl9ClxlbmR7YWxpZ25lZH0KJCQKClRoZSBpZGVhIGlzIHRoYXQgdGhlIHByb3NlY3V0b3IgKHRoZSByZXNlYXJjaGVyKSBtdXN0IGdhdGhlciBldmlkZW5jZSAoZGF0YSkgdG8gKipyZWplY3QqKiB0aGUgZGVmZW5kYW50J3MgaW5ub2NlbmNlIChpLmUuIHJlamVjdCAkSF8wJCkuIElmIHRoZSBkYXRhIGFyZSBsYWNraW5nIHRoZW4geW91ICoqZmFpbCB0byByZWplY3QqKiB0aGUgbnVsbCBoeXBvdGhlc2lzLiAKCiMjIFAtdmFsdWVzCgpIb3cgZG8gd2Uga25vdyBpZiBvdXIgZXZpZGVuY2UgKGRhdGEpIHJlamVjdHMgdGhlIG51bGwgaHlwb3RoZXNpcz8gCgpPdXIgZXN0aW1hdGUgZm9yICRcYmV0YV8xJCAodGhlIGVmZmVjdCBvZiBoZWlnaHQpIGlzIGFib3V0IDAuNzUuIEJ1dCBjb25zaWRlciB0aGlzIHRob3VnaHQgZXhwZXJpbWVudC4KCipJZiogdGhlIG51bGwgaHlwb3RoZXNpcyB3ZXJlIGNvcnJlY3QsIGFuZCAkRVtcYmV0YV8xXSA9IDAkIChvbiBhdmVyYWdlIHRoZXJlIGlzICoqbm8qKiBlZmZlY3Qgb2YgaGVpZ2h0KS4uLgoKLi4udGhlbiB3aGF0IGlzIHRoZSAqKnByb2JhYmlsaXR5Kiogd2Ugd291bGQgb2JzZXJ2ZSAkXGhhdHtcYmV0YV8xfSA9IDAuNzUkPyAKCkluIG90aGVyIHdvcmRzLCB3aGF0IGlzIHRoZSBwcm9iYWJpbGl0eSB3ZSBvYnNlcnZlIGFuIGVmZmVjdCB0aGF0ICoqaXMgbm90KiogemVybyBpZiB0aGUgInRydXRoIiAoZXhwZWN0ZWQgdmFsdWUgb2YgdGhlIHNhbXBsaW5nIGRpc3RyaWJ1dGlvbikgaXMgemVybz8gCgojIyBSZWplY3Qgb3IgZmFpbCB0byByZWplY3QKCldlIGNhbm5vdCBwcm92ZSB0aGluZ3Mgd2l0aCBkYXRhLiAKCldoeT8gCgpCZWNhdXNlIHdlIG9ic2VydmUgc2FtcGxlcyBvZiB0aGUgcG9wdWxhdGlvbiwgbm90IHRoZSBwb3B1bGF0aW9uIGl0c2VsZi4gCgpXZSB1c2UgdGhvc2Ugc2FtcGxlcyB0byAqKmluZmVyKiogYWJvdXQgdGhlIHBvcHVsYXRpb24uIAoKV2UgdGhlbiB1c2UgaHlwb3RoZXNlcyB0byBkbyBpbmZlcmVuY2UuIAoKQW5kIHNpbmNlIHdlIGNhbm5vdCBwcm92ZSBhbnl0aGluZywgd2UgY2FuIG9ubHkgKipyZWplY3QqKiBvciAqKmZhaWwgdG8gcmVqZWN0KiogaHlwb3RoZXNlcy4KCklmIHRoZSBwcm9iYWJpbGl0eSBpcyB2ZXJ5IGNsb3NlIHRvIHplcm8sIHRoZW4gaXQgaXMgKip1bmxpa2VseSoqIHRoZSBudWxsIGh5cG90aGVzaXMgaXMgdHJ1ZSwgYW5kIHdlIGNhbiByZWplY3QgaXQuIAoKQnV0IGlmIHRoZSBwcm9iYWJpbGl0eSBpcyB2ZXJ5IGNsb3NlIHRvIG9uZSwgdGhlIGl0IGlzICoqbGlrZWx5KiogdGhlIG51bGwgaHlwb3RoZXNpcyBpcyB0cnVlLCBhbmQgd2UgKipmYWlsIHRvIHJlamVjdCoqIGl0LiAKCiMjIyBQLXZhbHVlcyB3aXRoIGBzdW1tYXJ5KClgCgpUaGlzIHByb2JhYmlsaXR5IGlzIGNhbGxlZCBhICoqcC12YWx1ZSoqLiAKClAtdmFsdWVzIGFyZSBjYWxjdWxhdGVkIGZvciB5b3Ugd2l0aCB0aGUgZnVuY3Rpb24gYHN1bW1hcnkoKWAuCgpgc3VtbWFyeSgpYCB0YWtlcyB0aGUgb3V0cHV0IG9mIGBsbSgpYCBhbmQgc3BpdHMgb3V0IHRoZSBlc3RpbWF0ZWQgY29lZmZpY2llbnRzIC0tIGFzIHdlbGwgdGhlIGh5cG90aGVzaXMgdGVzdHMgYW5kIG90aGVyIHJlZ3Jlc3Npb24gZGlhZ25vc3RpY3MuIAoKTGV0J3Mgc2VlIHRoaXMgd2l0aCBhIHJhbmRvbSBzYW1wbGU6CgpgYGB7ciBzdW1tYXJ5fQpzZXQuc2VlZCgxMjMpCm5oYW5lcyAlPiUgCiAgc2xpY2Vfc2FtcGxlKG4gPSAxMDApICU+JSAKICBsbShmb3JtdWxhID0gd2VpZ2h0IH4gaGVpZ2h0ICsgc2V4ICsgYWdlLCBkYXRhID0gLikgJT4lIAogIHN1bW1hcnkoKQpgYGAKClRoZSBwLXZhbHVlcyBhcmUgc2hvd24gaW4gdGhlIGNvbHVtbiBgUHIoPnx0fClgLgoKIyMgSW50ZXJwcmV0YXRpbmcgcC12YWx1ZXMKCklmIHRoZSBwcm9iYWJpbGl0eSBpcyB2ZXJ5IGNsb3NlIHRvIHplcm8sIHRoZW4gaXQgaXMgKip1bmxpa2VseSoqIHRoZSBudWxsIGh5cG90aGVzaXMgaXMgdHJ1ZSwgYW5kIHdlIGNhbiByZWplY3QgaXQuIAoKSG93IGNsb3NlIHRvIHplcm8gaXMgY2xvc2UgZW5vdWdoPyAKClRoZXJlIGlzIG5vIGhhcmQtYW5kLWZhc3QgcnVsZS4gU28gc2NpZW5jZSBoYXMgKipjb29yZGluYXRlZCoqIG9uIGEgc2V0IG9mICoqdGhyZXNob2xkcyoqIHNvIHRoYXQgdGhlICoqY29udmVudGlvbioqIGlzIHRvIGNvbXBhcmUgeW91ciBwLXZhbHVlcyB0byB0aGVzZSB0aHJlc2hvbGRzOiAKCiogMTAlIG9yIDAuMTA6ICJ3ZWFrIGV2aWRlbmNlIHRvIHJlamVjdCAkSF8wJCIKKiA1JSBvciAwLjA1OiAiZXZpZGVuY2UgdG8gcmVqZWN0ICRIXzAkIgoqIDElIG9yIDAuMDE6ICJzdHJvbmcgZXZpZGVuY2UgdG8gcmVqZWN0ICRIXzAkIgoKSWYgdGhlIHAtdmFsdWUgaXMgYmVsb3cgYSB0aHJlc2hvbGQsIHNheSA1JSwgd2Ugc2F5IHRoYXQgd2UgcmVqZWN0IHRoZSBudWxsIGh5cG90aGVzaXMgYXQgdGhlIDUlIGxldmVsLiAKCkFuZCBpZiB3ZSByZWplY3QgdGhlIG51bGwsIHdlIHNheSB0aGUgZWZmZWN0IGlzICoqc3RhdGlzdGljYWxseSBzaWduaWZpY2FudCoqLiAKCkxldCdzIGFwcGx5IHRoaXMgdG8gb3VyIGNvZWZmaWNpZW50czoKCiogVGhlIHAtdmFsdWUgdG8gYGhlaWdodGAgaXMgMC4wMC4gV2UgcmVqZWN0IGF0IHRoZSAxJSBsZXZlbC4gU3RhdGlzdGljYWxseSBzaWduaWZpY2FudC4KKiBUaGUgcC12YWx1ZSB0byBgYWdlYCBpcyAwLjAwLiBXZSByZWplY3QgYXQgdGhlIDElIGxldmVsLiBTdGF0aXN0aWNhbGx5IHNpZ25pZmljYW50LgoqIFRoZSBwLXZhbHVlIHRvIGBzZXg9PU1hbGVgIGlzIDAuMDAuIFdlIHJlamVjdCBhdCB0aGUgMSUgbGV2ZWwuIFN0YXRpc3RpY2FsbHkgc2lnbmlmaWNhbnQuCgojIyBJbGx1c3RyYXRpbmcgcC12YWx1ZXMKClRoZSBwLXZhbHVlIGlzIHRoZSBwcm9iYWJpbGl0eSBvZiB0aGUgdGVzdCBzdGF0aXN0aWMgdW5kZXIgYSB0cnVlIG51bGwgaHlwb3RoZXNpcy4gTGV0J3MgdW5wYWNrIHRoaXMuCgpUaGUgdGVzdCBzdGF0aXN0aWMgb3IgdC12YWx1ZSBpcyB0aGUgY29lZmZpY2llbnQgZGl2aWRlZCBieSBpdCdzIHN0YW5kYXJkIGVycm9yLiBUaGUgdGVzdCBzdGF0aXN0aWMgZm9yIG91ciBjb2VmZmljaWVudCBvbiBoZWlnaHQgaXM6CgpgYGB7ciB0ZXN0IHN0YXR9CjAuNTg3NjMgLyAwLjIwOTk0CmBgYAoKVGhlIHAtdmFsdWUgaXMgdGhlIHR3by10YWlsZWQgcHJvYmFiaWxpdHkgb2YgdGhpcyB2YWx1ZSBmb3Igb3VyIGRlZ3JlZXMgb2YgZnJlZWRvbSAkbiAtIGskLiBXZSBoYXZlICRuPTEwMCQgKG91ciByYW5kb20gc2FtcGxlKSBhbmQgJGs9NCQgKHRocmVlIGNvZWZmaWNpZW50cyBhbmQgYW4gaW50ZXJjZXB0KSwgc286CgpgYGB7ciBwdmFsfQoyKnB0KC1hYnMoMi43OTkwMzgpLCBkZiA9IDEwMCAtIDQpCmBgYAoKVGhpcyBpcyBudW1iZXIgaXMgbGl0ZXJhbGx5IHRoZSBhcmVhIHVuZGVybmVhdGggdGhlIGN1cnZlIG9mIHRoZSB0LWRpc3RyaWJ1dGlvbiwgd2hpY2ggaXMgY2VudGVyZWQgYXQgemVybyAodGhlIG51bGwgaHlwb3RoZXNpcyk6CgpgYGB7ciBpbGx1c3RyYXRlIHQtZGlzdHJpYnV0aW9uIGhlaWdodH0KIyBzZXQgdGhlIHRlc3Qgc3RhdAp0ZXN0X3N0YXQgPSAyLjc5OTAzOAojIGNyZWF0ZSBhIGJ1bmNoIG9mIHQtc3RhdHMKdF92YWx1ZXMgPSBzZXEoZnJvbT0tNCwgdG89NCwgYnkgPSAwLjAxKQojIGNhbGN1bGF0ZSB0aGUgZGVuc2l0aWVzIGZvciBlYWNoIGVsZW1lbnQKdF9kZW5zaXRpZXMgPSBkdCh0X3ZhbHVlcywgZGYgPSBsZW5ndGgodF92YWx1ZXMpICAtIDEpIAojIG1ha2UgYSBkYXRhZnJhbWUgb3V0IG9mIHRoZSB0X3ZhbHVlIGFuZCB0X2RlbnNpdHkKdF9kYXRhZnJhbWUgPSB0aWJibGUoInRfdmFsdWUiID0gdF92YWx1ZXMsICJ0X2RlbnNpdHkiID0gdF9kZW5zaXRpZXMpCiMgcGxvdCB0aGUgdC1kaXN0cmlidXRpb24KZ2dwbG90KHRfZGF0YWZyYW1lLCBhZXMoeD10X3ZhbHVlLCB5PXRfZGVuc2l0eSkpICsgCiAgZ2VvbV9saW5lKCkgKyAKICBnZW9tX2FyZWEoYWVzKHRfdmFsdWVzKSAsIGZpbGwgPSAiZ3JheSIpICsKICBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQgPSB0ZXN0X3N0YXQsIGNvbG9yPSJyZWQiKSArIAogIGdlb21fdmxpbmUoeGludGVyY2VwdCA9IC10ZXN0X3N0YXQsIGNvbG9yPSJyZWQiKSArCiAgZ2VvbV9hcmVhKGRhdGEgPSBmaWx0ZXIodF9kYXRhZnJhbWUsIHRfdmFsdWUgPiB0ZXN0X3N0YXQpLCBmaWxsPSJyZWQiKSArIAogIGdlb21fYXJlYShkYXRhID0gZmlsdGVyKHRfZGF0YWZyYW1lLCB0X3ZhbHVlIDwgLXRlc3Rfc3RhdCksIGZpbGw9InJlZCIpICsKICBsYWJzKHggPSAidCBzdGF0IiwgeSA9ICJQKHQgc3RhdCkiKQpgYGAKCmFuZCBzbyB0aGUgcC12YWx1ZSBpcyBqdXN0IHRoZSBpbnRlZ3JhbCBmcm9tICQtXGluZnR5JCB0byAtMi43OTkwMzggZm9yIHRoZSBsb3dlciB0YWlsLCBhbmQgdGltZXMgdHdvIGZvciB0aGUgdXBwZXIgdGFpbDoKCmBgYHtyfQoyKmludGVncmF0ZShmID0gZnVuY3Rpb24oeCkgZHQoeCwgZGYgPSA5NiksIGxvd2VyID0gLUluZiwgdXBwZXIgPSAtMi43OTkwMzgpJHZhbHVlCmBgYAoKVGhlIHByb2JhYmlsaXR5IGlzIHNtYWxsIGJlY2F1c2UgdGhlIGFyZWEgdW5kZXIgdGhlIGN1cnZlIGlzIHNtYWxsLiBCeSBjb250cmFzdCwgcGxvdCB0aGUgcC12YWx1ZSBmb3IgdGhlIHRlc3Qgc3RhdCBvbiBgYWdlYDoKCmBgYHtyIGlsbHVzdHJhdGUgdC1kaXN0cmlidXRpb24gYWdlfQojIHNldCB0aGUgdGVzdCBzdGF0CnRlc3Rfc3RhdCA9IDAuOTM1CiMgY3JlYXRlIGEgYnVuY2ggb2YgdC1zdGF0cwp0X3ZhbHVlcyA9IHNlcShmcm9tPS00LCB0bz00LCBieSA9IDAuMDEpCiMgY2FsY3VsYXRlIHRoZSBkZW5zaXRpZXMgZm9yIGVhY2ggZWxlbWVudAp0X2RlbnNpdGllcyA9IGR0KHRfdmFsdWVzLCBkZiA9IGxlbmd0aCh0X3ZhbHVlcykgIC0gMSkgCiMgbWFrZSBhIGRhdGFmcmFtZSBvdXQgb2YgdGhlIHRfdmFsdWUgYW5kIHRfZGVuc2l0eQp0X2RhdGFmcmFtZSA9IHRpYmJsZSgidF92YWx1ZSIgPSB0X3ZhbHVlcywgInRfZGVuc2l0eSIgPSB0X2RlbnNpdGllcykKIyBwbG90IHRoZSB0LWRpc3RyaWJ1dGlvbgpnZ3Bsb3QodF9kYXRhZnJhbWUsIGFlcyh4PXRfdmFsdWUsIHk9dF9kZW5zaXR5KSkgKyAKICBnZW9tX2xpbmUoKSArIAogIGdlb21fYXJlYShhZXModF92YWx1ZXMpICwgZmlsbCA9ICJncmF5IikgKwogIGdlb21fdmxpbmUoeGludGVyY2VwdCA9IHRlc3Rfc3RhdCwgY29sb3I9InJlZCIpICsgCiAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ID0gLXRlc3Rfc3RhdCwgY29sb3I9InJlZCIpICsKICBnZW9tX2FyZWEoZGF0YSA9IGZpbHRlcih0X2RhdGFmcmFtZSwgdF92YWx1ZSA+IHRlc3Rfc3RhdCksIGZpbGw9InJlZCIpICsgCiAgZ2VvbV9hcmVhKGRhdGEgPSBmaWx0ZXIodF9kYXRhZnJhbWUsIHRfdmFsdWUgPCAtdGVzdF9zdGF0KSwgZmlsbD0icmVkIikgKwogIGxhYnMoeCA9ICJ0IHN0YXQiLCB5ID0gIlAodCBzdGF0KSIpCmBgYAoKVGhlIHRoaW5nIHRvIGtlZXAgaW4gbWluZCBhYm91dCBwLXZhbHVlcyBpcyB0aGV5IGFyZSBtYXNzaXZlbHkgaW5mbHVlbmNlZCBieSB0aGUgYW1vdW50IG9mIGRhdGEuIFRoaXMgaXMgYmVjYXVzZSB0aGUgdGVzdCBzdGF0aXN0aWMgaXMgdGhlIGNvZWZmaWNpZW50IGRpdmlkZWQgYnkgdGhlIHN0YW5kYXJkIGVycm9yLCBhbmQgdGhlIHN0YW5kYXJkIGVycm9yIGlzIGRpdmlkZWQgYnkgdGhlIHNxdWFyZSByb290IG9mIHRoZSBudW1iZXIgb2Ygb2JzZXJ2YXRpb25zLiBTbyBpZiB3ZSBpbmNyZWFzZSB0aGUgc2FtcGxlIHNpemU6CgpgYGB7ciBiaWdnZXIgc2FtcGxlfQpuaGFuZXMgJT4lIAogIHNsaWNlX3NhbXBsZShuID0gMTAwMCkgJT4lIAogIGxtKGZvcm11bGEgPSB3ZWlnaHQgfiBoZWlnaHQgKyBzZXggKyBhZ2UsIGRhdGEgPSAuKSAlPiUgCiAgc3VtbWFyeSgpCmBgYAoKbW9yZSBvZnRlbiB0aGFuIG5vdCB3ZSByZWplY3QgbnVsbCBoeXBvdGhlc2VzLiAKCktlZXAgdGhpcyBpbiBtaW5kIHdoZW4gaWYgeW91IHJ1biBhIHJlZ3Jlc3Npb24gb24gdGhvdXNhbmRzIG9yIG1pbGxpb25zIG9mIGRhdGEgcG9pbnRzLiBTaWduaWZpY2FudCBjb2VmZmljaWVudHMgYXJlbid0IHRoYXQgbWVhbmluZ2Z1bCwgYW5kIHlvdSBoYXZlIHRvIHRoaW5rIGhhcmRlciBhYm91dCAqKndoeSoqIHZhcmlhYmxlcyBtaWdodCBiZSByZWxhdGVkLiBCeSBjb250cmFzdCwgaXQncyBtb3JlIG1lYW5pbmdmdWwgaWYgeW91ICoqZG9uJ3QqKiBmaW5kIGEgc2lnbmlmaWNhbnQgcmVsYXRpb25zaGlwIQoKIyBUaWR5IG1vZGVscyAKClRoZSBvdXRwdXQgb2YgYHN1bW1hcnkoKWAgaXMgY2xlYXJseSBub3QgdGlkeSBkYXRhLiBUaGUgcGFja2FnZSBgYnJvb21gIG1ha2VzIGl0IGVhc2llciB0byB3b3JrIHdpdGggbW9kZWwgb2JqZWN0cy4gCgpTYXkgd2UgaGF2ZSB0aGlzIG1vZGVsOgoKYGBge3IgYnJvb20gbW9kZWx9Cm1vZGVsID0gbmhhbmVzICU+JSAKICBsbShmb3JtdWxhID0gd2VpZ2h0IH4gaGVpZ2h0ICsgc2V4ICsgYWdlLCBkYXRhID0gLikKYGBgCgpgdGlkeSgpYCB0dXJucyB0aGUgbW9kZWwgaW50byBhIHRpYmJsZToKCmBgYHtyIHRpZHkgYnJvb219CmJyb29tOjp0aWR5KG1vZGVsKQpgYGAKCmFuZCBgYXVnbWVudCgpYCAiYXVnbWVudHMiIHRoZSBtb2RlbCBieSBjcmVhdGluZyBhIHRpYmJsZSBhbmQgYWRkaW5nIHByZWRpY3RlZCB2YWx1ZXMsIHJlc2lkdWFscywgYW5kIG90aGVyIHN0dWZmOgoKYGBge3IgdGlkeSBhdWdtZW50fQpicm9vbTo6YXVnbWVudChtb2RlbCkKYGBgCgojIENoZWNrcG9pbnQKCkRyYXcgNTAwIHJhbmRvbSB2YWx1ZXMgZnJvbSBgZGlhbW9uZHNgIGFuZCBlc3RpbWF0ZSBsb2cgcHJpY2VzIGFzIGEgZnVuY3Rpb24gb2YgY2FyYXRzLCB0YWJsZSwgZGVwdGggYW5kIGNvbG9yLiBBc3NpZ24gdGhlIG1vZGVsIHRvIHRoZSBvYmplY3QgYGRpYW1vbmRzX21vZGVsYC4gVXNlIGEgbXV0YXRlZCB2YXJpYWJsZSAibG9nX3ByaWNlcyIgKHRoaXMgbWFrZSBpdCBlYXNpZXIgdG8gdXNlIGBicm9vbWApLgoKYGBge3IgY2hlY2twb2ludCBkaWFtb25kcyAxfQpzZXQuc2VlZCgxMjMpCgptb2RlbF9kaWFtb25kcyA9IGRpYW1vbmRzICU+JSAKICBzbGljZV9zYW1wbGUobiA9IDUwMCkgJT4lIAogIG11dGF0ZShsb2dfcHJpY2UgPSBsb2cocHJpY2UpKSAlPiUgCiAgbG0oZm9ybXVsYSA9IGxvZ19wcmljZSB+IGNhcmF0ICsgdGFibGUgKyBkZXB0aCArIGNvbG9yLCBkYXRhID0gLikKCnN1bW1hcnkobW9kZWxfZGlhbW9uZHMpCmBgYAoKVmVyaWZ5IHRoZSB0ZXN0IHN0YXRpc3RpYyBmb3IgdGhlIGNvZWZmaWNpZW50IG9uIHRhYmxlOgoKYGBge3IgY2hlY2twb2ludCBkaWFtb25kcyAyfQowLjAwNzM4MCAvIDAuMDA3MzQ1CmBgYAoKVmVyaWZ5IHRoZSBwLXZhbHVlIGZvciB0aGUgY29lZmZpY2llbnQgb24gdGFibGU6CgpgYGB7ciBjaGVja3BvaW50IGRpYW1vbmRzIDN9CjIqcHQoLWFicygxLjAwNDc2NSksIGRmID0gNDkwKQpgYGAKCkNhbGN1bGF0ZSB0aGUgKiphdmVyYWdlIHNxdWFyZWQgZXJyb3IqKiBvZiB0aGUgbW9kZWwsIGkuZS4gdGhlIGF2ZXJhZ2UgZGlmZmVyZW5jZSBiZXR3ZWVuIG9ic2VydmVkIGxvZyBwcmljZXMgYW5kIHByZWRpY3RlZCBsb2cgcHJpY2VzOgoKYGBge3IgY2hlY2twb2ludCBkaWFtb25kcyA0fQpicm9vbTo6YXVnbWVudChtb2RlbF9kaWFtb25kcykgJT4lIAogIHN1bW1hcmlzZShhdmdfZXJyb3IgPSBtZWFuKChsb2dfcHJpY2UgLSAuZml0dGVkKV4yKSkKYGBgCgo=