Set-up

library(tidyverse)

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.

1 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?

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

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

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

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

3.1 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:

  1. 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)) 
  1. 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”.

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

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

4.1 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?

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

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

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

4.4 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:

0.58763 / 0.20994
[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!

5 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:

broom::tidy(model)

and augment() “augments” the model by creating a tibble and adding predicted values, residuals, and other stuff:

broom::augment(model)

6 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:

0.007380 / 0.007345
[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=