5 Multivariate Linear Models

Correlations are not rare in nature but they don’t indicate causal relationships. To distinguish mere association from evidence of causation - much of statistical effort is devoted to multivariate regression. Reasons often given for multivariate models include:

  1. Statistical “control” for confounds. A confound is a variable that may be correlated with another variable of interest.
  2. Multiple causation. Even when confounds are absent a phenomenon may arise from multiple causes. When causation is multiple one cause can hide another. Multivariate models can help in such setting.
  3. Interactions.Even when variables are completely uncorrelated, the importance of each may still depend upone the other.

We’ll focus on two thigs multivariate models can help with:

5.1. Spurious association

Let’s explore correlation between divorce rate and marriage rate. Another predictor associated with divorce is the median age at marriage. It is also can be a good predictor of divorce rate - higher age at marriage predicts less divorce.

So let’s create a linear regression model:

\[D_i {\sim} Normal(\mu_i, \sigma)\\ \mu_i = \alpha + \beta_A A_i\\ \alpha {\sim} Normal(10, 10)\\ \beta {\sim} Normal(0, 1)\\ \sigma {\sim} Uniform(0, 10)\]

\(D_i\) is the divorce rate for State i, and \(A_i\) is State’s median age at marriage. We’re going to standardize the predictor here, because it’s a good habit to get into.

library(rethinking)
data(WaffleDivorce)
d <- WaffleDivorce
#standardize predictor
d$MedianAgeMarriage.s <- (d$MedianAgeMarriage - mean(d$MedianAgeMarriage)) / sd(d$MedianAgeMarriage)
#fit model
m5.1 <- map(
  alist(
    Divorce ~ dnorm(mu, sigma),
    mu <- a + bA * MedianAgeMarriage.s,
    a ~ dnorm(10, 10),
    bA ~ dnorm(0, 1), 
    sigma ~ dunif(0, 10)
  ), data = d
)

And the following code will compute the shaded confidence region.

precis(m5.1)
       Mean StdDev  5.5% 94.5%
a      9.69   0.20  9.36 10.01
bA    -1.04   0.20 -1.37 -0.72
sigma  1.45   0.14  1.22  1.68
#compute percentile interval of mean
MAM.seq <- seq(from = -3, to = 3.5, length.out = 30)
mu <- link(m5.1, data = data.frame(MedianAgeMarriage.s = MAM.seq))
[ 100 / 1000 ]
[ 200 / 1000 ]
[ 300 / 1000 ]
[ 400 / 1000 ]
[ 500 / 1000 ]
[ 600 / 1000 ]
[ 700 / 1000 ]
[ 800 / 1000 ]
[ 900 / 1000 ]
[ 1000 / 1000 ]
mu.PI <- apply(mu, 2, PI)
#plot it all
plot(Divorce ~ MedianAgeMarriage.s, data = d, col = rangi2)
abline(m5.1)
only using the first two of 3 regression coefficients
shade(mu.PI, MAM.seq)

As we can see from precis() output each additional standard deviation (sigma?) of delay in marriage (1.04 years) predicts a decrease of about one divorce per thousands abults, with a 89% interval from about -1.4 to -0.7. So it’s reliably negative, even though the magnitude of the difference may vary quite a lot - the upper bound is half the lower bound. The magnitute of difference means that even though the association here is implausibly positive, it could be both much stronger of weaker than the mean.

We can fit a similar regression for another relationship - marriage rate:

#standardize predictor
d$Marriage.s <- (d$Marriage - mean(d$Marriage)) / sd(d$Marriage)
#fit model
m5.2 <- map(
  alist(
    Divorce ~ dnorm(mu, sigma),
    mu <- a + bR * Marriage,
    a ~ dnorm(10, 10),
    bR ~ dnorm(0, 1), 
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.2)
      Mean StdDev 5.5% 94.5%
a     6.16   1.27 4.13  8.20
bR    0.18   0.06 0.08  0.27
sigma 1.67   0.17 1.40  1.94

And this shows an increase of 0.18 divorces for every additional standard deviation of marriage rate. So this relationship is not that strong as the previous one.

But comparing just parameter means between different bivariate regressions is not way to decide which predictor is better, so we’ll build a multivariate model with the goal of measuring the partial value of each preditor. The question we want answered is:

What is the predictive value of a variable, one we already know all of the other predictor variables?

In our case this question can be divided into two separate questions: * After we already know marriage rate, what additional value is here in also knowing age at marriage? * After we already know age at marriage, what additional value is there in also knowing marriate rate?

5.1.1. Multivariate notation

The strategy:

  1. Nominate the predictor variables you want in the linear model of the mean
  2. For each predictor, make a parameter that will measure its association with the outcome
  3. Multiply the parameter by the variable and add the term to the linear model

\[D_i {\sim} Normal(\mu_i, \sigma)\\ \mu_i = \alpha + \beta_RR_i + \beta_aA_i\\ \alpha {\sim} Normal(10, 10)\\ \beta_R {\sim} Normal(0, 1)\\ \beta_A {\sim} Normal(0, 1)\\ \sigma {\sim} Uniform(0, 10)\]

R was chosen here for marriage rate and A for age at marriage.

So what does it mean to assume \(\\mu_i = \alpha + \beta_RR_i + \beta_aA_i\)? It means that the expected outcome for any State with marriage rate \(R_i\) and median age at marriage \(A_i\) is the sume of three independent terms. The first term is a constant, \(\alpha\). The second is the product of marriage rate, \(R_i\), and the coefficient \(\beta_R\), that measures the association between marriage rate and divorce rate. The third is similar, but for association between medin age at marriage instead.

5.1.2. Fitting the model

To fit this model to the divorce data, we just expand our linear model.

m5.3 <- map(
  alist(
    Divorce ~ dnorm(mu, sigma),
    mu <- a + bR*Marriage.s + bA*MedianAgeMarriage.s,
    a ~ dnorm(10, 10),
    bR ~ dnorm(0, 1),
    bA ~ dnorm(0, 1),
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.3)
       Mean StdDev  5.5% 94.5%
a      9.69   0.20  9.36 10.01
bR    -0.13   0.28 -0.58  0.31
bA    -1.13   0.28 -1.58 -0.69
sigma  1.44   0.14  1.21  1.67

The posterior mean for marriage rate, \(B_R\), is now close to zero, with plenty of probability of both sizes of zero. The posterior mean for age at marriage, \(B_A\), has gotten actually slightly farther from zero, but is essentially unchanged.

It will help to visualize these posterir distribution estimates:

rethinking::precis_plot(precis(m5.3))

This is the result, with MAP values shown by the points and the percentile intervals by the solid horizontal lines.

You can interpret these estimates as saying:

Once we know median age at marriage for a State, there is little or no additional predictive power in also knowing the rate of marriage in that State

5.1.3 Plotting multivariate posteriors

There are three useful types of interpretive plots:

  1. Predictor residuals plots - show the outcome against residual predictor values
  2. Counterfactual plots - show the impled preictions for imaginary experiments in which the different predictor variables can be changed independently of one another.
  3. Posterior predicton plots - show model-based predictions agains raw data, or otherwise display the error in prediction.

5.1.3.1. Predictor residual plots

A predictor variable residual is the average prediction error when we use all of the other predictor variables to model a predictor of interest. The benifit of computing these things is that, once plotted against the outcome, we have a bivariate regression of sorts that has already ‘controlled’ for all of the other predictor variables. It just leaves in the variation that is not expected by the model of the mean, \(\mu\), as a function of the other predictors.

In our multivariate model of divorce rate, we have two predictors: 1) marriage rate (Marriage.s) and 2) median age at marriage (MedianAgeMarriage.s). To compute predictor residuals for either, we just use the other predictor to model it. So for marriage rate, this is the model we need:

\[R_i {\sim} Normal(\mu_i, \sigma)\\ \mu_i = \alpha + \beta A_i\\ \alpha {\sim} Normal(0, 10)\\ \beta {\sim} Normal(0, 1)\\ \sigma {\sim} Uniform(0, 10)\]

As before \(R\) is for marriage rate and \(A\) is for age at marriage.

This code will fit the model:

m5.4 <- map(
  alist(
    Marriage.s ~ dnorm(mu, sigma),
    mu <-  a + b*MedianAgeMarriage.s,
    a ~ dnorm(0, 10),
    b ~ dnorm(0, 1),
    sigma ~ dunif(0, 10)
  ), data = d
)

And then we compute the residuals by substracting the observed marriage rate in each State from the predicted rate, base upon usign age at marriage:

#compute expected MAP, for each state
mu <- coef(m5.4)["a"] + coef(m5.4)["b"] * d$MedianAgeMarriage.s
#compute residual for each state
m.resid <- d$Marriage.s - mu

When a residual is positive, that means that the observed rate was in excess of what we’d expect, given the median age at marriage in that State (and below when negative). States with positive redisuals marry fast for their age of marriage and vise versa.

It will help to plot the relationship between these two variables, and show the residuals as well.

plot(Marriage.s ~ MedianAgeMarriage.s, d, col=rangi2)
abline(m5.4)
only using the first two of 3 regression coefficients
#loop over states
for(i in 1:length(m.resid)) {
  x <- d$MedianAgeMarriage.s[i] # x location of line segment
  y <- d$Marriage.s[i] # observed endpoint of line segment
  
  #draw the line segment
  lines(c(x, x), c(mu[i], y), lwd = 0.5, col = col.alpha("black", 0.7))
}

Redisual marriage rate in each states, after accounting for the linear association with median age at marriage. Each gray line represent a residual, the distance of each observed marriage rate from the expected value, attemping to predict marriage rate with median age at marriage alone. So states that lie above the black regression line have higher rates of marriage than expected, according to age of marriage, and vise versa.

Notice that the residuals are variation in marriage rate that is left over, after taking out the purely linear relationship between two variables.

To use these residuals, let’s put then on a horizontal axis and plot them agains the actual outcome of interest, divorce rate.

PLOT HERE

You can think of this lot as displaying the linear relationship between divorce and marriage rates, having statistically “controlled” for media age of marriage. The vertical dashed line indicates marriage rate that exactly matches the expectation from median age at marriage. So states to the right of the line marry faster than expected; to the left - slower. Average divorce rate on both sides of the line is abot the same, and so the regression line demonstates little relationship between divorce and marriage rates. The slope of this line is -.13, exactly what we found in the multivariate model, m5.3.

PLOT HERE

This plot shows the same kind of calculation, but now for median age at marriage, “controlling” for marriage rate. So states to the right have older-than-expected median age at marriage, than those of the left. Now we find that the average divorce rate on the right is lower than on the left, as indicated by the regression line. States in which people marry older than expected for a given rate of marriage ten to have less divorce. The slope of the regression line here is -1.13, again the same as in the multivariate model, m5.3.

5.1.3.2 Counterfactual plots.

These plots show the implied predictions of the model. We call them counterfactual, because they can be produced for any values of the predictor variable you line, even unobserved or impossible combinations like very high median age or marriage and very high marriage rate.

The simplest use of a counterfactual plot is to see how the predictions change as you change only one predictor at a time. This means holding the values of all predictors constant, except for a single predictor of interest.

Let’s draw a pair of counterfactual plots for the divorce model. Beginning with a plot showing the impact of changes in Marriage.s on predictions:

#prepare new counterfactual data
A.avg <- mean(d$MedianAgeMarriage.s)
R.seq <- seq(from = -3, to = 3, length.out = 30)
pred.data <- data.frame(
  Marriage.s=R.seq, 
  MedianAgeMarriage.s=A.avg
)
#compute counterfactual mean divorce rate (mu)
mu <- link(m5.3, data = pred.data)
[ 100 / 1000 ]
[ 200 / 1000 ]
[ 300 / 1000 ]
[ 400 / 1000 ]
[ 500 / 1000 ]
[ 600 / 1000 ]
[ 700 / 1000 ]
[ 800 / 1000 ]
[ 900 / 1000 ]
[ 1000 / 1000 ]
mu.mean <- apply(mu, 2, mean)
mu.PI <- apply(mu, 2, PI)
#simulate counterfactual divorce outcomes
R.sim <- rethinking::sim(m5.3, data = pred.data, n = 1e4)
[ 1000 / 10000 ]
[ 2000 / 10000 ]
[ 3000 / 10000 ]
[ 4000 / 10000 ]
[ 5000 / 10000 ]
[ 6000 / 10000 ]
[ 7000 / 10000 ]
[ 8000 / 10000 ]
[ 9000 / 10000 ]
[ 10000 / 10000 ]
R.PI <- apply(R.sim, 2, PI)
#display predictions, hiding raw data with type = 'n'
plot(Divorce ~ Marriage.s, data = d, type = "n")
mtext("MedianAgeMarriage.s = 0")
lines(R.seq, mu.mean)
shade(mu.PI, R.seq)
shade(R.PI, R.seq)

The strategy above is to build a new list of data that describe the counterfactual cases we wish to simulate predictions for. The list names pred.data holds these cases. Not that the observed values for MedianAgeMarriage.s are not used. Instead we compute the average value and then use it inside the linear model. So Marriage.S changes across the values of R.seq, while the other predictor is held constant as it mean, A.avg.

Let’s do the same for MedianAgeMarriage.s which are allowed to vary and Marriage.s being held constant:

R.avg <- mean(d$Marriage.s)
A.seq <- seq(from = -3, to = 3.5, length.out = 30)
pred.data2 <- data.frame(
  Marriage.s = R.avg, 
  MedianAgeMarriage.s = A.seq
)
#compute counterfactual mean divorce rate (mu)
mu <- link(m5.3, data = pred.data2)
[ 100 / 1000 ]
[ 200 / 1000 ]
[ 300 / 1000 ]
[ 400 / 1000 ]
[ 500 / 1000 ]
[ 600 / 1000 ]
[ 700 / 1000 ]
[ 800 / 1000 ]
[ 900 / 1000 ]
[ 1000 / 1000 ]
mu.mean <- apply(mu, 2, mean)
mu.PI <- apply(mu, 2, PI)
#simulate counterfactual divorce outcomes
A.sim <- rethinking::sim(m5.3, data = pred.data2, n = 1e4)
[ 1000 / 10000 ]
[ 2000 / 10000 ]
[ 3000 / 10000 ]
[ 4000 / 10000 ]
[ 5000 / 10000 ]
[ 6000 / 10000 ]
[ 7000 / 10000 ]
[ 8000 / 10000 ]
[ 9000 / 10000 ]
[ 10000 / 10000 ]
A.PI <- apply(A.sim, 2, PI)
#display predictions, hiding raw data with type = 'n'
plot(Divorce ~ MedianAgeMarriage.s, data = d, type = "n")
mtext("MedianAgeMarriage.s = 0")
lines(A.seq, mu.mean)
shade(mu.PI, A.seq)
shade(A.PI, A.seq)

These plots have the same splots as the resudual plots, but they don’t display any data, raw or residual, because they are counterfactual. And they also show percentile intervals on the scale of the data, instead of on the redisual scale. As the result, they are dicrect displays of the impact on prediction of a change in each variable.

#5.1.3.3. Posterior prediction plots

In addition to understanting the estimates, it’s importatn to check the model fit agains the observed data.

  1. Did the model fit correctly? (Compare implied predictions to the raw data)
  2. how does the model fail? (By inspecting the individual cases where the model maeks poor predictions, you might get an idea of how to improve the model)

Let’s begin by simulation prediction, averaing over the posterior.

#call rethinking::link() without specifying new data, so it uses original data
mu <- link(m5.3)
[ 100 / 1000 ]
[ 200 / 1000 ]
[ 300 / 1000 ]
[ 400 / 1000 ]
[ 500 / 1000 ]
[ 600 / 1000 ]
[ 700 / 1000 ]
[ 800 / 1000 ]
[ 900 / 1000 ]
[ 1000 / 1000 ]
#summarise samples across cases
mu.mean <- apply(mu, 2, mean)
mu.PI <- apply(mu, 2, PI)
#simulate observations, again no new data, so uses original data
divorce.sim <- rethinking::sim(m5.3, n = 1e4)
[ 1000 / 10000 ]
[ 2000 / 10000 ]
[ 3000 / 10000 ]
[ 4000 / 10000 ]
[ 5000 / 10000 ]
[ 6000 / 10000 ]
[ 7000 / 10000 ]
[ 8000 / 10000 ]
[ 9000 / 10000 ]
[ 10000 / 10000 ]
divorce.PI <- apply(divorce.sim, 2, PI)

The code is similar we’ve seen before but now we use the original observed data.

For multivariate models, there are many different ways to diplay these simulations. The simplest is to just plot predictions against observed.

plot(mu.mean ~ d$Divorce, col = rangi2, ylim = range(mu.PI), 
     xlab = "Observed divorce", ylab = "Predicted divorce")
abline(a = 0, b = 1, lty = 2)
for(i in 1:nrow(d)) {
  lines(rep(d$Divorce[i], 2), c(mu.PI[1, i], mu.PI[2, i]), col = rangi2)
}

It’s easy to see from the plot that the model under-predicts for States with very high divorce rate while over-predicts for States with very lower divorce rate.

plot(mu.mean ~ d$Divorce, col = rangi2, ylim = range(mu.PI),  xlab = "Observed divorce", ylab = "Predicted divorce")
abline(a = 0, b = 1, lty = 2)
for(i in 1:nrow(d)) {
  lines(rep(d$Divorce[i], 2), c(mu.PI[1, i], mu.PI[2, i]), col = rangi2)
}
#doesn't work in notebook, only as a part of script or in console (better in console)
#just click on several points and then right-click in console (or ESC) to see the labels
identify(x = d$Divorce, y = mu.mean, labels = as.character(d$Loc), cex = 0.8)
integer(0)

This plot makes is hard to see the amount of prediction error. For this reason, we’ll use the residual plot that show the mean prediction error for each row.

#compute residuals
divorce.resid <- d$Divorce - mu.mean
#get ordering by divorce rate
o <- order(divorce.resid)
#make the plot
dotchart(divorce.resid[o], labels = d$Loc[o], xlim = c(-6, 5), cex = 0.6)
abline(v = 0, col = col.alpha("black", 0.2))
for(i in 1:nrow(d)) {
  j <- o[i] # which state in order
  lines(d$Divorce[j] - c(mu.PI[1, j], mu.PI[2, j]), rep(i, 2))
  points(d$Divorce[j] - c(divorce.PI[1, j], divorce.PI[2, j]), rep(i, 2), pch = 3, cex=0.6, col = "gray")
}

It’s much easier to see the large model failures, such as ID and ME.

Another common use for these simulations is to constuct novel predictor residual plots. Once you’ve computed the divorce residuals (as done above), you can plot those residuals against new predictor variables. This is a quick way to see if remaining variation in theoutcome is associated with another predictor.

5.2. Masked relationship

The divorce rate example demonstrates that multiple predictor variables are useful for knocking out spurious association. A second reason to use more than one predictor variable is to measure the direct influences of multiple factors on an outcome, when non of those infuences is apparent from bivariate relationships. This problem tends to aries when there’re two predictor variables that are correlated with one another, but one correlated positively and other negatively.

Let’s see an example of milk:

library(rethinking)
data("milk")
d <- milk
glimpse(d)
Observations: 29
Variables: 8
$ clade          <fct> Strepsirrhine, Strepsirrhine, Strepsirrhine, Strepsirrhine, Strepsirrhine, New Wo...
$ species        <fct> Eulemur fulvus, E macaco, E mongoz, E rubriventer, Lemur catta, Alouatta seniculu...
$ kcal.per.g     <dbl> 0.49, 0.51, 0.46, 0.48, 0.60, 0.47, 0.56, 0.89, 0.91, 0.92, 0.80, 0.46, 0.71, 0.7...
$ perc.fat       <dbl> 16.60, 19.27, 14.11, 14.91, 27.28, 21.22, 29.66, 53.41, 46.08, 50.58, 41.35, 3.93...
$ perc.protein   <dbl> 15.42, 16.91, 16.85, 13.18, 19.50, 23.58, 23.46, 15.80, 23.34, 22.33, 20.85, 25.3...
$ perc.lactose   <dbl> 67.98, 63.82, 69.04, 71.91, 53.22, 55.20, 46.88, 30.79, 30.58, 27.09, 37.80, 70.7...
$ mass           <dbl> 1.95, 2.09, 2.51, 1.62, 2.19, 5.25, 5.37, 2.51, 0.71, 0.68, 0.12, 0.47, 0.32, 0.6...
$ neocortex.perc <dbl> 55.16, NA, NA, NA, NA, 64.54, 64.54, 67.64, NA, 68.85, 58.85, 61.69, 60.32, NA, N...

The popular hypothesis has it that primates with larger brains product more energetic milk, so that brains can grow quickly. So the variables we’ll consider now are:

  • kcal.per.g - Kilocaliries of energy per gram of milk
  • mass - Average female body mass, in kg
  • neocortex.perc - the percent of total brain mass that is neocortex mass.

The question here is to what extent energy content of milk, measured here by kilocalories, is related to the percent of the brain mass that is neocortex. Female mass is used here to see the masking that hides relationship among the variable.

But before fitting a model, let’s exclude the missing values from the data.

d <- d[complete.cases(d), ]
m5.5 <- map(
  alist(
    kcal.per.g ~ dnorm(mu, sigma), 
    mu <- a + bn*neocortex.perc, 
    a ~ dnorm(0, 100), 
    bn ~ dnorm(0, 1), 
    sigma ~ dunif(0, 1)
  ), data = d
)
precis(m5.5, digits = 3)
       Mean StdDev   5.5% 94.5%
a     0.353  0.471 -0.399 1.106
bn    0.005  0.007 -0.007 0.016
sigma 0.166  0.028  0.120 0.211

Next we can plot the predicted mean and 89% interval:

np.seq <- 0:100
pred.data <- data.frame(neocortex.perc = np.seq)
mu <- link(m5.5, data = pred.data, n = 1e4)
[ 1000 / 10000 ]
[ 2000 / 10000 ]
[ 3000 / 10000 ]
[ 4000 / 10000 ]
[ 5000 / 10000 ]
[ 6000 / 10000 ]
[ 7000 / 10000 ]
[ 8000 / 10000 ]
[ 9000 / 10000 ]
[ 10000 / 10000 ]
mu.mean <- apply(mu, 2, mean)
mu.PI <- apply(mu, 2, PI)
plot(kcal.per.g ~ neocortex.perc, data = d, col = rangi2)
lines(np.seq, mu.mean)
lines(np.seq, mu.PI[1, ], lty = 2)
lines(np.seq, mu.PI[2, ], lty = 2)

MAP line is weakly positive, but it’s highly imprecise.

Now let’s consider another predictor variable, adult female body mass, mass in our data frame. Let’s use log of mass as a predictor.

d$log.mass <- log(d$mass)
m5.6 <- map(
  alist(
    kcal.per.g ~ dnorm(mu, sigma), 
    mu <- a + bm*log.mass, 
    a ~ dnorm(0, 100), 
    bm ~ dnorm(0, 1), 
    sigma ~ dunif(0, 1)
  ), data = d
)
precis(m5.6, digits = 3)
        Mean StdDev   5.5% 94.5%
a      0.705  0.049  0.627 0.783
bm    -0.032  0.020 -0.064 0.001
sigma  0.157  0.027  0.114 0.200

So log-mass is negatively correlated with kilocalories and this influence is stronger than neocortex one.

Now let’s see what happens when we add both predictor variables at the same time to the regression:

m5.7 <- map(
  alist(
    kcal.per.g ~ dnorm(mu, sigma), 
    mu <- a + bm*log.mass + bn*neocortex.perc, 
    a ~ dnorm(0, 100), 
    bn ~ dnorm(0, 1),
    bm ~ dnorm(0, 1), 
    sigma ~ dunif(0, 1)
  ), data = d
)
precis(m5.7, digits = 3)
        Mean StdDev   5.5%  94.5%
a     -1.084  0.468 -1.832 -0.337
bn     0.028  0.007  0.016  0.040
bm    -0.096  0.022 -0.132 -0.060
sigma  0.115  0.020  0.083  0.146

By incorporating both predictor variable in the regression, the estimated association of both with the outcome has increased.

Let’s plot the intervals for the predicted mean kilocalories, for this new model.

mean.log.mass <- mean(log(d$mass))
mean.neocortex.perc = mean(d$neocortex.perc)
np.seq <- 0:100
#neocortex perc
pred.data <- data.frame(
  neocortex.perc = np.seq, 
  log.mass = mean.log.mass
)
mu <- link(m5.7, data = pred.data, n = 1e4)
[ 1000 / 10000 ]
[ 2000 / 10000 ]
[ 3000 / 10000 ]
[ 4000 / 10000 ]
[ 5000 / 10000 ]
[ 6000 / 10000 ]
[ 7000 / 10000 ]
[ 8000 / 10000 ]
[ 9000 / 10000 ]
[ 10000 / 10000 ]
mu.mean <- apply(mu, 2, mean)
mu.PI <- apply(mu, 2, PI)
plot(kcal.per.g ~ neocortex.perc, data = d, type = "n", main = "Neocortex Perc vs kcal per gramm ")
lines(np.seq, mu.mean)
lines(np.seq, mu.PI[1, ], lty = 2)
lines(np.seq, mu.PI[2, ], lty = 2)

#log mass
np.seq <- -100:100
pred.data <- data.frame(
  log.mass = np.seq, 
  neocortex.perc = mean.neocortex.perc
)
mu <- link(m5.7, data = pred.data, n = 1e4)
[ 1000 / 10000 ]
[ 2000 / 10000 ]
[ 3000 / 10000 ]
[ 4000 / 10000 ]
[ 5000 / 10000 ]
[ 6000 / 10000 ]
[ 7000 / 10000 ]
[ 8000 / 10000 ]
[ 9000 / 10000 ]
[ 10000 / 10000 ]
mu.mean <- apply(mu, 2, mean)
mu.PI <- apply(mu, 2, PI)
plot(kcal.per.g ~ log.mass, data = d, type = "n", main = "Log Mass vs kcal per gramm ")
lines(np.seq, mu.mean)
lines(np.seq, mu.PI[1, ], lty = 2)
lines(np.seq, mu.PI[2, ], lty = 2)

Since one variable is positively correlated with the outcome and another is negatively correlated, they tend to cancel one another out.

5.3 When adding variables hurts

There’re several good, purely statistical reasons to avoid doing this.

  1. Multicollinearity - strong correlation between two or more predictor variables. The consequence of it is that the posterior distribution will say that a veray large range of parameter are plausible.
  2. Post-treatment bias - statistically controlling for consequences of a causal factor.
  3. Overfitting

5.3.1. Multicollinear legs

N <- 100 # number of individuals
height <- rnorm(N, 10, 2) #sim total height of each
leg_prop <- runif(N, 0.4, 0.5) #leg as proportion of heigh
leg_left <- leg_prop * height + rnorm(N, 0, 0.02) #sim left leg as proportion + error
leg_right <- leg_prop * height + rnorm(N, 0, 0.02) #sim right leg as proportion + error
d <- data.frame(height, leg_left, leg_right)

Now let’s analyze these data, prediction the outcome height with both predictions, leg_left and leg_right. Our expectation that beta coefficient is equal to 10 / 4.5 = 2.2 (4.5 = 10 * 0.45 - average proportion of the leg).

m5.8 <- map(
  alist(
    height ~ dnorm(mu, sigma),
    mu <- a + bl*leg_left + br*leg_right, 
    a ~ dnorm(10, 100),
    bl ~ dnorm(2, 10),
    br ~ dnorm(2, 10),
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.8)
       Mean StdDev  5.5% 94.5%
a      1.46   0.33  0.93  1.98
bl     2.35   2.16 -1.10  5.81
br    -0.45   2.16 -3.90  2.99
sigma  0.62   0.04  0.55  0.70
precis_plot(precis(m5.8))

Despite the fact that the precis plot looks odd, model did fit correctly, and the posterior distribution here is the right answer to the question we asked - what is the value of knowing each predictor, after already knowing all the other predictors? The answer to the question is wierd, but perfectly logical. The posterior distributino is the answer to this question, considering every possible combination of the parameters and assigning relative plausibilities to every combination, conditional on this model and these data. It might help to look at the bivariate posterio distribution for bl and br:

post <- extract.samples(m5.8)
plot(bl ~ br, post, col = col.alpha(rangi2, 0.1), pch = 16)

So the posterior distribution for these two parameters is very highly correlated - when br is large, bl is small.

One way to think about this phenomenon is that you have approximated this likelihood:

\[y_i {\sim} Normal(\mu_i, \sigma)\\ m_i = \alpha + \beta_1x_i + \beta_2x_i\]

Here is a single predictor, and it’s used twice. From the computer perspective this likelihood is really:

\[y_i {\sim} Normal(\mu_i, \sigma)\\ m_i = \alpha + (\beta_1 + \beta_2)x_i\]

So neither \(\beta_1\) nor \(\beta_2\) influence \(\mu\), only their sum \(\beta_1 + \beta_2\) influences it. This means that there’re infinite combinations of \(\beta_1\) and \(\beta_2\).

Just to check, let’s plot the sum:

sum_blbr <- post$bl + post$br
dens(sum_blbr, col = rangi2, lwd = 2, xlab = "sum of bl and br")

If you fit a regression with only one of the leg length, you’ll ge approximately the same posterior mean:

m5.9 <- map(
  alist(
    height ~ dnorm(mu, sigma),
    mu <- a + bl * leg_left,
    a ~ dnorm(10, 100),
    bl ~ dnorm(2, 10),
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.9)
      Mean StdDev 5.5% 94.5%
a     1.46   0.33 0.94  1.99
bl    1.90   0.07 1.78  2.01
sigma 0.62   0.04 0.55  0.70

The lesson here is - when two predictor variables are very strongly correlated, including both in a model may lead to confusion.

5.3.2 Multicollinear milk

library(rethinking)
data(milk)
d <- milk

In these data, we have variables perc.fat and perc.lactose that we might use to model the total energy content, kcal.per.g to explore a natural case of multicollinearity.

Let’s start by odeling kcal.per.g as a function of perc.fact and perc.lactose, but in two bivariate regressions:

m5.10 <- map(
  alist(
    kcal.per.g ~ dnorm(mu, sigma),
    mu <- a + bf * perc.fat, 
    a ~ dnorm(0.6, 10), 
    bf ~ dnorm(0, 1),
    sigma ~ dunif(0, 10)
  ), data = d
)
m5.11 <- map(
  alist(
    kcal.per.g ~ dnorm(mu, sigma),
    mu <- a + bl * perc.lactose, 
    a ~ dnorm(0.6, 10), 
    bl ~ dnorm(0, 1),
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.10, digits = 3)
       Mean StdDev  5.5% 94.5%
a     0.301  0.036 0.244 0.358
bf    0.010  0.001 0.008 0.012
sigma 0.073  0.010 0.058 0.089
precis_plot(precis(m5.10))

precis(m5.11, digits = 3)
        Mean StdDev   5.5%  94.5%
a      1.166  0.043  1.098  1.235
bl    -0.011  0.001 -0.012 -0.009
sigma  0.062  0.008  0.049  0.075
precis_plot(precis(m5.11))

The posterior means are essentially mirror images of one another.

Let’s fit a multivariate regression:

m5.12 <- map(
  alist(
    kcal.per.g ~ dnorm(mu, sigma),
    mu <- a + bl * perc.lactose + bf * perc.fat, 
    a ~ dnorm(0.6, 10), 
    bl ~ dnorm(0, 1),
    bf ~ dnorm(0, 1),
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.12)
       Mean StdDev  5.5% 94.5%
a      1.01   0.20  0.69  1.33
bl    -0.01   0.00 -0.01  0.00
bf     0.00   0.00  0.00  0.01
sigma  0.06   0.01  0.05  0.07
precis_plot(precis(m5.12))

Now the posterior means for both bf and bl are closer to zero. This happens because the variables perc.fact and perc.lactose contain much of the same information. In the case of fat and lactose, there two variables form essentially a single axis of the variation:

pairs(~ kcal.per.g + perc.fat + perc.lactose, data = d, col = rangi2)

Two variables are negatively correlated, and so strongly so that they are nearly redundant. Either helps in predicting kcal.per.g, but neither helps much once you already know the other.

You can compute the correlation between two variables with cor:

cor(d$perc.fat, d$perc.lactose)
[1] -0.9416373

What can be done about multicollinearity? The best thing to do is be aware of it. You can anticipate this problem by checking the predictor variables against one another in a pairs plot.

5.3.3 Post-treatment bias

It’s routine to worry about mistaken inferences that arise from omitting predictor variables. Such mistakes are often called omitted variable bias. It’s much less routing to worry about mistaken inferences arising from including variables that are consequences of other variables. We’ll call this post-treatment bias.

Plants in a greenhouse example Different in growth under different antifungail soil treatment. Four variables: initial height, final height, treatment, and presence of fungus. If your goal is to make a causal inference about the treatment, you shouldn’t include the presence of fungus, because it is a post-treatment effect.

Let’s simulate some data:

#number of plants
N <- 100
#simulate initial heights
h0 <- rnorm(N, 10, 2)
#assign treatments and simulate fungus and growth
treatment <- rep(0:1, each = N/2)
fungus <- rbinom(N, size = 1, prob = 0.5 - treatment * 0.4)
h1 <- h0 + rnorm(N, 5 - 3 * fungus)
#compose a clean data frame
d <- data.frame(h0 = h0, h1 =h1, treatment = treatment, fungus = fungus)

Then fit a model:

m5.13 <- map(
  alist(
    h1 ~ dnorm(mu, sigma),
    mu <- a + bh * h0 + bt * treatment + bf * fungus,
    a ~ dnorm(0, 100),
    c(bh, bt, bf) ~ dnorm(0, 10),
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.13)
       Mean StdDev  5.5% 94.5%
a      5.49   0.56  4.59  6.39
bh     0.96   0.05  0.89  1.04
bt    -0.15   0.20 -0.47  0.18
bf    -3.43   0.21 -3.77 -3.09
sigma  0.90   0.06  0.79  1.00
precis_plot(precis(m5.13))

The marginal posterior for bt, the effect of treatment, is actually negative here with little effect, while other predictors have important effect. The problem is that fungus is mostly a consequence of treatment. So when we control for fungus, the model is implicitly answering the question: Once we already know whether or not a plant developed fungus, does soil treatment matters?. The answer is ‘no’, because soil treatment has its effects on growth through reducing fungus.

What we actually want to know is the impact of treatment on growth.

m5.14 <- map(
  alist(
    h1 ~ dnorm(mu, sigma),
    mu <- a + bh * h0 + bt * treatment,
    a ~ dnorm(0, 100),
    c(bh, bt) ~ dnorm(0, 10),
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.14)
      Mean StdDev 5.5% 94.5%
a     1.87   0.97 0.31  3.42
bh    1.12   0.09 0.98  1.27
bt    1.40   0.34 0.86  1.94
sigma 1.69   0.12 1.50  1.88
precis_plot(precis(m5.14))

Now the impact of treatment is strong and positive.

5.4. Categorical variables

A common question for statistical methods is to what extent an outcome changes asa result of presence or absence of a category.

5.4.1. Binary categories

Let’s return to Kalahari height data

data("Howell1")
d <- Howell1
str(d)
'data.frame':   544 obs. of  4 variables:
 $ height: num  152 140 137 157 145 ...
 $ weight: num  47.8 36.5 31.9 53 41.3 ...
 $ age   : num  63 63 65 41 51 35 32 27 19 54 ...
 $ male  : int  1 0 0 1 0 1 0 1 0 1 ...

The male variable is our new predictor, an example of dummy variable.

\[h_i {\sim} Normal(\mu_i, \sigma)\\ \mu_i = \alpha + \beta_mm_i\\ \alpha {\sim} Normal(178, 100)\\ \beta_m {\sim} Normal(0, 10)\\ \sigma {\sim} Uniform(0, 50)\]

where \(m\) is a dummy variable indicating a male individual. The parameter \(\beta_m\) influences prediction only for those cases where \(m_i = 1\).

Let’s fit it:

m5.15 <- map(
  alist(
    height ~ dnorm(mu, sigma),
    mu <- a + bm * male,
    a ~ dnorm(178, 100),
    bm ~ dnorm(0, 10),
    sigma ~ dunif(0, 50)
  ), data = d
)
precis(m5.15)
        Mean StdDev   5.5%  94.5%
a     134.83   1.59 132.28 137.37
bm      7.29   2.28   3.64  10.94
sigma  27.31   0.83  25.99  28.63
precis_plot(precis(m5.15))

To interpret these estimates, you have to note that the parameter \(\alpha\) is now the average height among females. The parameter \(\beta_m\) then tells us the average difference between males and females = 7.3 cm.

Let’s sample from the posterior to derive a percentile inverval for average male height.

post <- extract.samples(m5.15)
mu.male <- post$a + post$bm
PI(mu.male)
      5%      94% 
139.4139 144.7717 

5.4.2. Many categories

When we have k categories, we need k - 1 dummy variables.

Get back to primate milk example with 4 types of primates:

data(milk)
d <- milk
unique(d$clade)
[1] Strepsirrhine    New World Monkey Old World Monkey Ape             
Levels: Ape New World Monkey Old World Monkey Strepsirrhine

Let’s create dummy variables:

library(dplyr)
d <- d %>% 
  mutate(clade.NWM = if_else(clade == "New World Monkey", 1, 0),
         clade.OWM = if_else(clade == "Old World Monkey", 1, 0),
         clade.S = if_else(clade == "Strepsirrhine", 1, 0), 
         )

There’s no need to make another variable for Ape, because it will be the default, “intercept” category.

Let’s specify the model for kcal.per.g:

\[k_i {\sim} Normal(\mu_i, \sigma)\\ \mu_i = \alpha + \beta_{NWM}NWM_i + \beta_{OWM}OWM_i + \beta_SS_i\\ \alpha {\sim} Normal(0.6, 10)\\ \beta_{NWM}{\sim} Normal(0, 1)\\ \beta_{OWM}{\sim} Normal(0, 1)\\ \beta_{S}{\sim} Normal(0, 1)\\ \sigma {\sim} Uniform(0, 10)\\\]

A linear model like this really defines four different linear models, each corresponsing to a different category.

m5.16 <- map(
  alist(
    kcal.per.g ~ dnorm(mu, sigma),
    mu <- a + b.NWM * clade.NWM + b.OWM * clade.OWM + b.S * clade.S,
    a ~ dnorm(0.6, 10),
    c(b.NWM, b.OWM, b.S) ~ dnorm(0, 1),
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.16)
       Mean StdDev  5.5% 94.5%
a      0.55   0.04  0.49  0.61
b.NWM  0.17   0.05  0.08  0.25
b.OWM  0.24   0.06  0.15  0.34
b.S   -0.04   0.06 -0.14  0.06
sigma  0.11   0.02  0.09  0.14
precis_plot(precis(m5.16))

To get posterior distribution for the average milk energy in each category, you can again use samples:

#sample posterior
post <- extract.samples(m5.16)
#compute averages for each category
mu.ape <- post$a
mu.NWM <- post$a + post$b.NWM
mu.OWM <- post$a + post$b.OWM
mu.S <- post$a + post$b.S
#summarize using precis
precis(data.frame(mu.ape, mu.NWM, mu.OWM, mu.S))
       Mean StdDev |0.89 0.89|
mu.ape 0.55   0.04  0.49  0.61
mu.NWM 0.71   0.04  0.65  0.77
mu.OWM 0.79   0.05  0.71  0.86
mu.S   0.51   0.05  0.43  0.59

Suppose we want to know the estimated difference between the two monkey groups. Then just subtract the estimated means to get a difference:

diff.NWM.OWM <- mu.NWM - mu.OWM
quantile(diff.NWM.OWM, probs = c(0.025, 0.5, 0.975))
       2.5%         50%       97.5% 
-0.19300099 -0.07438118  0.04406231 

5.4.3. Adding regular predictor variables

There’s not obstacle now in including other predictor variables, like perc.fat or log(mass) to the model.

\[\mu_i = \alpha + \beta_{NWM}NWM_i + \beta_{OWM}OWM_i + \beta_SS_i + \beta_FF_i\]

where \(F_i\) is the percent fat for the i-th case in the data and \(\beta_F\) is the slope that measure the influence of \(F\) on predictions about the mean milk energy.

5.4.4. Unique intercepts.

Another way to conceptualize categorical variables is to construct a vector of intercept parameters, one parameter for each category. Then you can create an index variable in your data frame that says which parameter goes with each case.

(d$clade_id <- coerce_index(d$clade))
 [1] 4 4 4 4 4 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1

This variable just gives the number of unique clade value. Then you tell map to maek a vector of intercepts, one intercept for each unique values in clade_id:

m5.16_alt <- map(
  alist(
    kcal.per.g ~ dnorm(mu, sigma),
    mu <- a[clade_id],
    a[clade_id] ~ dnorm(0.6, 10),
    sigma ~ dunif(0, 10)
  ), data = d
)
precis(m5.16_alt, depth = 2)
      Mean StdDev 5.5% 94.5%
a[1]  0.55   0.04 0.48  0.61
a[2]  0.71   0.04 0.65  0.78
a[3]  0.79   0.05 0.71  0.86
a[4]  0.51   0.05 0.43  0.59
sigma 0.11   0.02 0.09  0.14
precis_plot(precis(m5.16_alt, depth = 2))

Now you getn the same averages for each clade but this time directly from the fit model. You need to add depth = 2 to precis call in order to print out vector parameters like these.

5.5. Ordinary least squares and lm

If you ok with flat priors.

5.5.1. Design formulas

\[y_i {\sim} Normal(\mu_i, \sigma)\\ \mu_i = \alpha + \beta x_i\]

is equivalent to y ~ 1 + x.

Intercepts are optional y ~ x = y = 1 + x

To omit intercept y ~ 0 + x

Categorical variables y ~ 1 + as.factor(x)

Transform variables y ~ 1 + x + I(x^2) + I(x^3)

5.5.3 Building map formulas from lm formulas with rethinking::glimmmer()

data(cars)
glimmer(dist ~ speed, data = cars)
alist(
    dist ~ dnorm( mu , sigma ),
    mu <- Intercept +
        b_speed*speed,
    Intercept ~ dnorm(0,10),
    b_speed ~ dnorm(0,10),
    sigma ~ dcauchy(0,2)
)
LS0tCnRpdGxlOiAiU3RhdGlzdGljYWwgUmV0aGlua2luZy4gQ2hhcHRlciA1IgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgojIDUgTXVsdGl2YXJpYXRlIExpbmVhciBNb2RlbHMKCkNvcnJlbGF0aW9ucyBhcmUgbm90IHJhcmUgaW4gbmF0dXJlIGJ1dCB0aGV5IGRvbid0IGluZGljYXRlIGNhdXNhbCByZWxhdGlvbnNoaXBzLiBUbyBkaXN0aW5ndWlzaCBtZXJlIGFzc29jaWF0aW9uIGZyb20gZXZpZGVuY2Ugb2YgY2F1c2F0aW9uIC0gbXVjaCBvZiBzdGF0aXN0aWNhbCBlZmZvcnQgaXMgZGV2b3RlZCB0byAqKm11bHRpdmFyaWF0ZSByZWdyZXNzaW9uKiouIApSZWFzb25zIG9mdGVuIGdpdmVuIGZvciBtdWx0aXZhcmlhdGUgbW9kZWxzIGluY2x1ZGU6IAoKMS4gKipTdGF0aXN0aWNhbCAiY29udHJvbCIgZm9yIGNvbmZvdW5kcyoqLiBBICpjb25mb3VuZCogaXMgYSB2YXJpYWJsZSB0aGF0IG1heSBiZSBjb3JyZWxhdGVkIHdpdGggYW5vdGhlciB2YXJpYWJsZSBvZiBpbnRlcmVzdC4KMi4gKipNdWx0aXBsZSBjYXVzYXRpb24qKi4gRXZlbiB3aGVuIGNvbmZvdW5kcyBhcmUgYWJzZW50IGEgcGhlbm9tZW5vbiBtYXkgYXJpc2UgZnJvbSBtdWx0aXBsZSBjYXVzZXMuIFdoZW4gY2F1c2F0aW9uIGlzIG11bHRpcGxlIG9uZSBjYXVzZSBjYW4gaGlkZSBhbm90aGVyLiBNdWx0aXZhcmlhdGUgbW9kZWxzIGNhbiBoZWxwIGluIHN1Y2ggc2V0dGluZy4KMy4gKipJbnRlcmFjdGlvbnMqKi5FdmVuIHdoZW4gdmFyaWFibGVzIGFyZSBjb21wbGV0ZWx5IHVuY29ycmVsYXRlZCwgdGhlIGltcG9ydGFuY2Ugb2YgZWFjaCBtYXkgc3RpbGwgZGVwZW5kIHVwb25lIHRoZSBvdGhlci4gCgpXZSdsbCBmb2N1cyBvbiB0d28gdGhpZ3MgbXVsdGl2YXJpYXRlIG1vZGVscyBjYW4gaGVscCB3aXRoOiAKCiogcmV2ZWFsaW5nICpzcHVyaW91cyogY29ycmVsYXRpb25zCiogcmV2ZWFsaW5nIGltcG9ydGFudCBjb3JyZWxhdGlvbmcgdGhhdCBjYW4gYmUgKm1hc2tlZCogYnkgdW5yZXZlYWxlZCBjb3JyZWxhdGlvbnMgd2l0aCBvdGhlciB2YXJpYWJsZXMuIAoKCiMjIDUuMS4gU3B1cmlvdXMgYXNzb2NpYXRpb24KCkxldCdzIGV4cGxvcmUgY29ycmVsYXRpb24gYmV0d2VlbiBkaXZvcmNlIHJhdGUgYW5kIG1hcnJpYWdlIHJhdGUuIApBbm90aGVyIHByZWRpY3RvciBhc3NvY2lhdGVkIHdpdGggZGl2b3JjZSBpcyB0aGUgbWVkaWFuIGFnZSBhdCBtYXJyaWFnZS4gSXQgaXMgYWxzbyBjYW4gYmUgYSBnb29kIHByZWRpY3RvciBvZiBkaXZvcmNlIHJhdGUgLSBoaWdoZXIgYWdlIGF0IG1hcnJpYWdlIHByZWRpY3RzIGxlc3MgZGl2b3JjZS4gCgpTbyBsZXQncyBjcmVhdGUgYSBsaW5lYXIgcmVncmVzc2lvbiBtb2RlbDoKCiQkRF9pIHtcc2ltfSBOb3JtYWwoXG11X2ksIFxzaWdtYSlcXApcbXVfaSA9IFxhbHBoYSArIFxiZXRhX0EgQV9pXFwKXGFscGhhIHtcc2ltfSBOb3JtYWwoMTAsIDEwKVxcClxiZXRhIHtcc2ltfSBOb3JtYWwoMCwgMSlcXApcc2lnbWEge1xzaW19IFVuaWZvcm0oMCwgMTApJCQKCiREX2kkIGlzIHRoZSBkaXZvcmNlIHJhdGUgZm9yIFN0YXRlICppKiwgYW5kICRBX2kkIGlzIFN0YXRlJ3MgbWVkaWFuIGFnZSBhdCBtYXJyaWFnZS4gCldlJ3JlIGdvaW5nIHRvIHN0YW5kYXJkaXplIHRoZSBwcmVkaWN0b3IgaGVyZSwgYmVjYXVzZSBpdCdzIGEgZ29vZCBoYWJpdCB0byBnZXQgaW50by4KCmBgYHtyLCBtZXNzYWdlPUZBTFNFfQpsaWJyYXJ5KHJldGhpbmtpbmcpCmRhdGEoV2FmZmxlRGl2b3JjZSkKZCA8LSBXYWZmbGVEaXZvcmNlCgojc3RhbmRhcmRpemUgcHJlZGljdG9yCmQkTWVkaWFuQWdlTWFycmlhZ2UucyA8LSAoZCRNZWRpYW5BZ2VNYXJyaWFnZSAtIG1lYW4oZCRNZWRpYW5BZ2VNYXJyaWFnZSkpIC8gc2QoZCRNZWRpYW5BZ2VNYXJyaWFnZSkKCiNmaXQgbW9kZWwKbTUuMSA8LSBtYXAoCiAgYWxpc3QoCiAgICBEaXZvcmNlIH4gZG5vcm0obXUsIHNpZ21hKSwKICAgIG11IDwtIGEgKyBiQSAqIE1lZGlhbkFnZU1hcnJpYWdlLnMsCiAgICBhIH4gZG5vcm0oMTAsIDEwKSwKICAgIGJBIH4gZG5vcm0oMCwgMSksIAogICAgc2lnbWEgfiBkdW5pZigwLCAxMCkKICApLCBkYXRhID0gZAopCmBgYAoKQW5kIHRoZSBmb2xsb3dpbmcgY29kZSB3aWxsIGNvbXB1dGUgdGhlIHNoYWRlZCBjb25maWRlbmNlIHJlZ2lvbi4KCmBgYHtyfQpwcmVjaXMobTUuMSkKCiNjb21wdXRlIHBlcmNlbnRpbGUgaW50ZXJ2YWwgb2YgbWVhbgpNQU0uc2VxIDwtIHNlcShmcm9tID0gLTMsIHRvID0gMy41LCBsZW5ndGgub3V0ID0gMzApCm11IDwtIGxpbmsobTUuMSwgZGF0YSA9IGRhdGEuZnJhbWUoTWVkaWFuQWdlTWFycmlhZ2UucyA9IE1BTS5zZXEpKQptdS5QSSA8LSBhcHBseShtdSwgMiwgUEkpCgojcGxvdCBpdCBhbGwKcGxvdChEaXZvcmNlIH4gTWVkaWFuQWdlTWFycmlhZ2UucywgZGF0YSA9IGQsIGNvbCA9IHJhbmdpMikKYWJsaW5lKG01LjEpCnNoYWRlKG11LlBJLCBNQU0uc2VxKQoKYGBgCkFzIHdlIGNhbiBzZWUgZnJvbSBgcHJlY2lzKClgIG91dHB1dCBlYWNoIGFkZGl0aW9uYWwgc3RhbmRhcmQgZGV2aWF0aW9uIChgc2lnbWFgPykgb2YgZGVsYXkgaW4gIG1hcnJpYWdlICgxLjA0IHllYXJzKSBwcmVkaWN0cyBhIGRlY3JlYXNlIG9mIGFib3V0IG9uZSBkaXZvcmNlIHBlciB0aG91c2FuZHMgYWJ1bHRzLCB3aXRoIGEgODklIGludGVydmFsIGZyb20gYWJvdXQgLTEuNCB0byAtMC43LgpTbyBpdCdzIHJlbGlhYmx5IG5lZ2F0aXZlLCBldmVuIHRob3VnaCB0aGUgbWFnbml0dWRlIG9mIHRoZSBkaWZmZXJlbmNlIG1heSB2YXJ5IHF1aXRlIGEgbG90IC0gdGhlIHVwcGVyIGJvdW5kIGlzIGhhbGYgdGhlIGxvd2VyIGJvdW5kLiBUaGUgbWFnbml0dXRlIG9mIGRpZmZlcmVuY2UgbWVhbnMgdGhhdCBldmVuIHRob3VnaCB0aGUgYXNzb2NpYXRpb24gaGVyZSBpcyBpbXBsYXVzaWJseSBwb3NpdGl2ZSwgaXQgY291bGQgYmUgYm90aCBtdWNoIHN0cm9uZ2VyIG9mIHdlYWtlciB0aGFuIHRoZSBtZWFuLiAKCldlIGNhbiBmaXQgYSBzaW1pbGFyIHJlZ3Jlc3Npb24gZm9yIGFub3RoZXIgcmVsYXRpb25zaGlwIC0gbWFycmlhZ2UgcmF0ZToKCmBgYHtyfQojc3RhbmRhcmRpemUgcHJlZGljdG9yCmQkTWFycmlhZ2UucyA8LSAoZCRNYXJyaWFnZSAtIG1lYW4oZCRNYXJyaWFnZSkpIC8gc2QoZCRNYXJyaWFnZSkKCiNmaXQgbW9kZWwKbTUuMiA8LSBtYXAoCiAgYWxpc3QoCiAgICBEaXZvcmNlIH4gZG5vcm0obXUsIHNpZ21hKSwKICAgIG11IDwtIGEgKyBiUiAqIE1hcnJpYWdlLAogICAgYSB+IGRub3JtKDEwLCAxMCksCiAgICBiUiB+IGRub3JtKDAsIDEpLCAKICAgIHNpZ21hIH4gZHVuaWYoMCwgMTApCiAgKSwgZGF0YSA9IGQKKQoKcHJlY2lzKG01LjIpCmBgYAoKQW5kIHRoaXMgc2hvd3MgYW4gaW5jcmVhc2Ugb2YgMC4xOCBkaXZvcmNlcyBmb3IgZXZlcnkgYWRkaXRpb25hbCBzdGFuZGFyZCBkZXZpYXRpb24gb2YgbWFycmlhZ2UgcmF0ZS4gU28gdGhpcyByZWxhdGlvbnNoaXAgaXMgbm90IHRoYXQgc3Ryb25nIGFzIHRoZSBwcmV2aW91cyBvbmUuIAoKQnV0IGNvbXBhcmluZyBqdXN0IHBhcmFtZXRlciBtZWFucyBiZXR3ZWVuIGRpZmZlcmVudCBiaXZhcmlhdGUgcmVncmVzc2lvbnMgaXMgbm90IHdheSB0byBkZWNpZGUgd2hpY2ggcHJlZGljdG9yIGlzIGJldHRlciwgc28gd2UnbGwgYnVpbGQgYSBtdWx0aXZhcmlhdGUgbW9kZWwgd2l0aCB0aGUgZ29hbCBvZiBtZWFzdXJpbmcgdGhlIHBhcnRpYWwgdmFsdWUgb2YgZWFjaCBwcmVkaXRvci4gClRoZSBxdWVzdGlvbiB3ZSB3YW50IGFuc3dlcmVkIGlzOiAKCipXaGF0IGlzIHRoZSBwcmVkaWN0aXZlIHZhbHVlIG9mIGEgdmFyaWFibGUsIG9uZSB3ZSBhbHJlYWR5IGtub3cgYWxsIG9mIHRoZSBvdGhlciBwcmVkaWN0b3IgdmFyaWFibGVzPyoKCkluIG91ciBjYXNlIHRoaXMgcXVlc3Rpb24gY2FuIGJlIGRpdmlkZWQgaW50byB0d28gc2VwYXJhdGUgcXVlc3Rpb25zOiAKKiBBZnRlciB3ZSBhbHJlYWR5IGtub3cgbWFycmlhZ2UgcmF0ZSwgd2hhdCBhZGRpdGlvbmFsIHZhbHVlIGlzIGhlcmUgaW4gYWxzbyBrbm93aW5nIGFnZSBhdCBtYXJyaWFnZT8KKiBBZnRlciB3ZSBhbHJlYWR5IGtub3cgYWdlIGF0IG1hcnJpYWdlLCB3aGF0IGFkZGl0aW9uYWwgdmFsdWUgaXMgdGhlcmUgaW4gYWxzbyBrbm93aW5nIG1hcnJpYXRlIHJhdGU/IAoKIyMjIDUuMS4xLiBNdWx0aXZhcmlhdGUgbm90YXRpb24KClRoZSBzdHJhdGVneTogCgoxLiBOb21pbmF0ZSB0aGUgcHJlZGljdG9yIHZhcmlhYmxlcyB5b3Ugd2FudCBpbiB0aGUgbGluZWFyIG1vZGVsIG9mIHRoZSBtZWFuCjIuIEZvciBlYWNoIHByZWRpY3RvciwgbWFrZSBhIHBhcmFtZXRlciB0aGF0IHdpbGwgbWVhc3VyZSBpdHMgYXNzb2NpYXRpb24gd2l0aCB0aGUgb3V0Y29tZQozLiBNdWx0aXBseSB0aGUgcGFyYW1ldGVyIGJ5IHRoZSB2YXJpYWJsZSBhbmQgYWRkIHRoZSB0ZXJtIHRvIHRoZSBsaW5lYXIgbW9kZWwKCiQkRF9pIHtcc2ltfSBOb3JtYWwoXG11X2ksIFxzaWdtYSlcXApcbXVfaSA9IFxhbHBoYSArIFxiZXRhX1JSX2kgKyBcYmV0YV9hQV9pXFwKXGFscGhhIHtcc2ltfSBOb3JtYWwoMTAsIDEwKVxcClxiZXRhX1Ige1xzaW19IE5vcm1hbCgwLCAxKVxcClxiZXRhX0Ege1xzaW19IE5vcm1hbCgwLCAxKVxcClxzaWdtYSB7XHNpbX0gVW5pZm9ybSgwLCAxMCkkJAoKUiB3YXMgY2hvc2VuIGhlcmUgZm9yICptYXJyaWFnZSByYXRlKiBhbmQgQSBmb3IgKmFnZSBhdCBtYXJyaWFnZSouIAoKU28gd2hhdCBkb2VzIGl0IG1lYW4gdG8gYXNzdW1lICRcXG11X2kgPSBcYWxwaGEgKyBcYmV0YV9SUl9pICsgXGJldGFfYUFfaSQ/IEl0IG1lYW5zIHRoYXQgdGhlIGV4cGVjdGVkIG91dGNvbWUgZm9yIGFueSBTdGF0ZSB3aXRoIG1hcnJpYWdlIHJhdGUgJFJfaSQgYW5kIG1lZGlhbiBhZ2UgYXQgbWFycmlhZ2UgJEFfaSQgaXMgdGhlIHN1bWUgb2YgdGhyZWUgaW5kZXBlbmRlbnQgdGVybXMuClRoZSBmaXJzdCB0ZXJtIGlzIGEgY29uc3RhbnQsICRcYWxwaGEkLiAKVGhlIHNlY29uZCBpcyB0aGUgcHJvZHVjdCBvZiBtYXJyaWFnZSByYXRlLCAkUl9pJCwgYW5kIHRoZSBjb2VmZmljaWVudCAkXGJldGFfUiQsIHRoYXQgbWVhc3VyZXMgdGhlIGFzc29jaWF0aW9uIGJldHdlZW4gbWFycmlhZ2UgcmF0ZSBhbmQgZGl2b3JjZSByYXRlLiAKVGhlIHRoaXJkIGlzIHNpbWlsYXIsIGJ1dCBmb3IgYXNzb2NpYXRpb24gYmV0d2VlbiBtZWRpbiBhZ2UgYXQgbWFycmlhZ2UgaW5zdGVhZC4gCgojIyMgNS4xLjIuIEZpdHRpbmcgdGhlIG1vZGVsIAoKVG8gZml0IHRoaXMgbW9kZWwgdG8gdGhlIGRpdm9yY2UgZGF0YSwgd2UganVzdCBleHBhbmQgb3VyIGxpbmVhciBtb2RlbC4gCgpgYGB7cn0KbTUuMyA8LSBtYXAoCiAgYWxpc3QoCiAgICBEaXZvcmNlIH4gZG5vcm0obXUsIHNpZ21hKSwKICAgIG11IDwtIGEgKyBiUipNYXJyaWFnZS5zICsgYkEqTWVkaWFuQWdlTWFycmlhZ2UucywKICAgIGEgfiBkbm9ybSgxMCwgMTApLAogICAgYlIgfiBkbm9ybSgwLCAxKSwKICAgIGJBIH4gZG5vcm0oMCwgMSksCiAgICBzaWdtYSB+IGR1bmlmKDAsIDEwKQogICksIGRhdGEgPSBkCikKCnByZWNpcyhtNS4zKQpgYGAKClRoZSBwb3N0ZXJpb3IgbWVhbiBmb3IgbWFycmlhZ2UgcmF0ZSwgJEJfUiQsIGlzIG5vdyBjbG9zZSB0byB6ZXJvLCB3aXRoIHBsZW50eSBvZiBwcm9iYWJpbGl0eSBvZiBib3RoIHNpemVzIG9mIHplcm8uIFRoZSBwb3N0ZXJpb3IgbWVhbiBmb3IgYWdlIGF0IG1hcnJpYWdlLCAkQl9BJCwgaGFzIGdvdHRlbiBhY3R1YWxseSBzbGlnaHRseSBmYXJ0aGVyIGZyb20gemVybywgYnV0IGlzIGVzc2VudGlhbGx5IHVuY2hhbmdlZC4gCgpJdCB3aWxsIGhlbHAgdG8gdmlzdWFsaXplIHRoZXNlIHBvc3RlcmlyIGRpc3RyaWJ1dGlvbiBlc3RpbWF0ZXM6IAoKYGBge3J9CnJldGhpbmtpbmc6OnByZWNpc19wbG90KHByZWNpcyhtNS4zKSkKYGBgCgpUaGlzIGlzIHRoZSByZXN1bHQsIHdpdGggTUFQIHZhbHVlcyBzaG93biBieSB0aGUgcG9pbnRzIGFuZCB0aGUgcGVyY2VudGlsZSBpbnRlcnZhbHMgYnkgdGhlIHNvbGlkIGhvcml6b250YWwgbGluZXMuIAoKWW91IGNhbiBpbnRlcnByZXQgdGhlc2UgZXN0aW1hdGVzIGFzIHNheWluZzogCgoqT25jZSB3ZSBrbm93IG1lZGlhbiBhZ2UgYXQgbWFycmlhZ2UgZm9yIGEgU3RhdGUsIHRoZXJlIGlzIGxpdHRsZSBvciBubyBhZGRpdGlvbmFsIHByZWRpY3RpdmUgcG93ZXIgaW4gYWxzbyBrbm93aW5nIHRoZSByYXRlIG9mIG1hcnJpYWdlIGluIHRoYXQgU3RhdGUqCgojIyMgNS4xLjMgUGxvdHRpbmcgbXVsdGl2YXJpYXRlIHBvc3RlcmlvcnMgCgpUaGVyZSBhcmUgdGhyZWUgdXNlZnVsIHR5cGVzIG9mIGludGVycHJldGl2ZSBwbG90czogCgoxLiAqUHJlZGljdG9yIHJlc2lkdWFscyBwbG90cyogLSBzaG93IHRoZSBvdXRjb21lIGFnYWluc3QgKnJlc2lkdWFsKiBwcmVkaWN0b3IgdmFsdWVzCjIuICpDb3VudGVyZmFjdHVhbCBwbG90cyogLSBzaG93IHRoZSBpbXBsZWQgcHJlaWN0aW9ucyBmb3IgaW1hZ2luYXJ5IGV4cGVyaW1lbnRzIGluIHdoaWNoIHRoZSBkaWZmZXJlbnQgcHJlZGljdG9yIHZhcmlhYmxlcyBjYW4gYmUgY2hhbmdlZCBpbmRlcGVuZGVudGx5IG9mIG9uZSBhbm90aGVyLiAKMy4gKlBvc3RlcmlvciBwcmVkaWN0b24gcGxvdHMqIC0gc2hvdyBtb2RlbC1iYXNlZCBwcmVkaWN0aW9ucyBhZ2FpbnMgcmF3IGRhdGEsIG9yIG90aGVyd2lzZSBkaXNwbGF5IHRoZSBlcnJvciBpbiBwcmVkaWN0aW9uLiAKCiMjIyMgNS4xLjMuMS4gUHJlZGljdG9yIHJlc2lkdWFsIHBsb3RzCgpBICoqcHJlZGljdG9yIHZhcmlhYmxlIHJlc2lkdWFsKiogaXMgdGhlIGF2ZXJhZ2UgcHJlZGljdGlvbiBlcnJvciB3aGVuIHdlIHVzZSBhbGwgb2YgdGhlIG90aGVyIHByZWRpY3RvciB2YXJpYWJsZXMgdG8gbW9kZWwgYSBwcmVkaWN0b3Igb2YgaW50ZXJlc3QuIApUaGUgYmVuaWZpdCBvZiBjb21wdXRpbmcgdGhlc2UgdGhpbmdzIGlzIHRoYXQsIG9uY2UgcGxvdHRlZCBhZ2FpbnN0IHRoZSBvdXRjb21lLCB3ZSBoYXZlIGEgYml2YXJpYXRlIHJlZ3Jlc3Npb24gb2Ygc29ydHMgdGhhdCBoYXMgYWxyZWFkeSAnY29udHJvbGxlZCcgZm9yIGFsbCBvZiB0aGUgb3RoZXIgcHJlZGljdG9yIHZhcmlhYmxlcy4gSXQganVzdCBsZWF2ZXMgaW4gdGhlIHZhcmlhdGlvbiB0aGF0IGlzIG5vdCBleHBlY3RlZCBieSB0aGUgbW9kZWwgb2YgdGhlIG1lYW4sICRcbXUkLCBhcyBhIGZ1bmN0aW9uIG9mIHRoZSBvdGhlciBwcmVkaWN0b3JzLiAKCkluIG91ciBtdWx0aXZhcmlhdGUgbW9kZWwgb2YgZGl2b3JjZSByYXRlLCB3ZSBoYXZlIHR3byBwcmVkaWN0b3JzOiAxKSBtYXJyaWFnZSByYXRlIChgTWFycmlhZ2Uuc2ApIGFuZCAyKSBtZWRpYW4gYWdlIGF0IG1hcnJpYWdlIChgTWVkaWFuQWdlTWFycmlhZ2Uuc2ApLiBUbyBjb21wdXRlIHByZWRpY3RvciByZXNpZHVhbHMgZm9yIGVpdGhlciwgd2UganVzdCB1c2UgdGhlIG90aGVyIHByZWRpY3RvciB0byBtb2RlbCBpdC4gClNvIGZvciBtYXJyaWFnZSByYXRlLCB0aGlzIGlzIHRoZSBtb2RlbCB3ZSBuZWVkOiAKCiQkUl9pIHtcc2ltfSBOb3JtYWwoXG11X2ksIFxzaWdtYSlcXApcbXVfaSA9IFxhbHBoYSArIFxiZXRhIEFfaVxcClxhbHBoYSB7XHNpbX0gTm9ybWFsKDAsIDEwKVxcClxiZXRhIHtcc2ltfSBOb3JtYWwoMCwgMSlcXApcc2lnbWEge1xzaW19IFVuaWZvcm0oMCwgMTApJCQKCkFzIGJlZm9yZSAkUiQgaXMgZm9yIG1hcnJpYWdlIHJhdGUgYW5kICRBJCBpcyBmb3IgYWdlIGF0IG1hcnJpYWdlLiAKClRoaXMgY29kZSB3aWxsIGZpdCB0aGUgbW9kZWw6IAoKYGBge3J9Cm01LjQgPC0gbWFwKAogIGFsaXN0KAogICAgTWFycmlhZ2UucyB+IGRub3JtKG11LCBzaWdtYSksCiAgICBtdSA8LSAgYSArIGIqTWVkaWFuQWdlTWFycmlhZ2UucywKICAgIGEgfiBkbm9ybSgwLCAxMCksCiAgICBiIH4gZG5vcm0oMCwgMSksCiAgICBzaWdtYSB+IGR1bmlmKDAsIDEwKQogICksIGRhdGEgPSBkCikKYGBgCgpBbmQgdGhlbiB3ZSBjb21wdXRlIHRoZSAqcmVzaWR1YWxzKiBieSBzdWJzdHJhY3RpbmcgdGhlIG9ic2VydmVkIG1hcnJpYWdlIHJhdGUgaW4gZWFjaCBTdGF0ZSBmcm9tIHRoZSBwcmVkaWN0ZWQgcmF0ZSwgYmFzZSB1cG9uIHVzaWduIGFnZSBhdCBtYXJyaWFnZTogCgpgYGB7cn0KI2NvbXB1dGUgZXhwZWN0ZWQgTUFQLCBmb3IgZWFjaCBzdGF0ZQptdSA8LSBjb2VmKG01LjQpWyJhIl0gKyBjb2VmKG01LjQpWyJiIl0gKiBkJE1lZGlhbkFnZU1hcnJpYWdlLnMKCiNjb21wdXRlIHJlc2lkdWFsIGZvciBlYWNoIHN0YXRlCm0ucmVzaWQgPC0gZCRNYXJyaWFnZS5zIC0gbXUKYGBgCgpXaGVuIGEgcmVzaWR1YWwgaXMgcG9zaXRpdmUsIHRoYXQgbWVhbnMgdGhhdCB0aGUgb2JzZXJ2ZWQgcmF0ZSB3YXMgaW4gZXhjZXNzIG9mIHdoYXQgd2UnZCBleHBlY3QsIGdpdmVuIHRoZSBtZWRpYW4gYWdlIGF0IG1hcnJpYWdlIGluIHRoYXQgU3RhdGUgKGFuZCBiZWxvdyB3aGVuIG5lZ2F0aXZlKS4gClN0YXRlcyB3aXRoIHBvc2l0aXZlIHJlZGlzdWFscyBtYXJyeSBmYXN0IGZvciB0aGVpciBhZ2Ugb2YgbWFycmlhZ2UgYW5kIHZpc2UgdmVyc2EuCgpJdCB3aWxsIGhlbHAgdG8gcGxvdCB0aGUgcmVsYXRpb25zaGlwIGJldHdlZW4gdGhlc2UgdHdvIHZhcmlhYmxlcywgYW5kIHNob3cgdGhlIHJlc2lkdWFscyBhcyB3ZWxsLiAKCmBgYHtyfQpwbG90KE1hcnJpYWdlLnMgfiBNZWRpYW5BZ2VNYXJyaWFnZS5zLCBkLCBjb2w9cmFuZ2kyKQphYmxpbmUobTUuNCkKCiNsb29wIG92ZXIgc3RhdGVzCmZvcihpIGluIDE6bGVuZ3RoKG0ucmVzaWQpKSB7CiAgeCA8LSBkJE1lZGlhbkFnZU1hcnJpYWdlLnNbaV0gIyB4IGxvY2F0aW9uIG9mIGxpbmUgc2VnbWVudAogIHkgPC0gZCRNYXJyaWFnZS5zW2ldICMgb2JzZXJ2ZWQgZW5kcG9pbnQgb2YgbGluZSBzZWdtZW50CiAgCiAgI2RyYXcgdGhlIGxpbmUgc2VnbWVudAogIGxpbmVzKGMoeCwgeCksIGMobXVbaV0sIHkpLCBsd2QgPSAwLjUsIGNvbCA9IGNvbC5hbHBoYSgiYmxhY2siLCAwLjcpKQp9CmBgYAoqUmVkaXN1YWwgbWFycmlhZ2UgcmF0ZSBpbiBlYWNoIHN0YXRlcywgYWZ0ZXIgYWNjb3VudGluZyBmb3IgdGhlIGxpbmVhciBhc3NvY2lhdGlvbiB3aXRoIG1lZGlhbiBhZ2UgYXQgbWFycmlhZ2UuIEVhY2ggZ3JheSBsaW5lIHJlcHJlc2VudCBhIHJlc2lkdWFsLCB0aGUgZGlzdGFuY2Ugb2YgZWFjaCBvYnNlcnZlZCBtYXJyaWFnZSByYXRlIGZyb20gdGhlIGV4cGVjdGVkIHZhbHVlLCBhdHRlbXBpbmcgdG8gcHJlZGljdCBtYXJyaWFnZSByYXRlIHdpdGggbWVkaWFuIGFnZSBhdCBtYXJyaWFnZSBhbG9uZS4gU28gc3RhdGVzIHRoYXQgbGllIGFib3ZlIHRoZSBibGFjayByZWdyZXNzaW9uIGxpbmUgaGF2ZSBoaWdoZXIgcmF0ZXMgb2YgbWFycmlhZ2UgdGhhbiBleHBlY3RlZCwgYWNjb3JkaW5nIHRvIGFnZSBvZiBtYXJyaWFnZSwgYW5kIHZpc2UgdmVyc2EuKgoKTm90aWNlIHRoYXQgdGhlIHJlc2lkdWFscyBhcmUgdmFyaWF0aW9uIGluIG1hcnJpYWdlIHJhdGUgdGhhdCBpcyBsZWZ0IG92ZXIsIGFmdGVyIHRha2luZyBvdXQgdGhlIHB1cmVseSBsaW5lYXIgcmVsYXRpb25zaGlwIGJldHdlZW4gdHdvIHZhcmlhYmxlcy4gCgpUbyB1c2UgdGhlc2UgcmVzaWR1YWxzLCBsZXQncyBwdXQgdGhlbiBvbiBhIGhvcml6b250YWwgYXhpcyBhbmQgcGxvdCB0aGVtIGFnYWlucyB0aGUgYWN0dWFsIG91dGNvbWUgb2YgaW50ZXJlc3QsIGRpdm9yY2UgcmF0ZS4gCgoqKlBMT1QgSEVSRSoqCgpZb3UgY2FuIHRoaW5rIG9mIHRoaXMgbG90IGFzIGRpc3BsYXlpbmcgdGhlIGxpbmVhciByZWxhdGlvbnNoaXAgYmV0d2VlbiBkaXZvcmNlIGFuZCBtYXJyaWFnZSByYXRlcywgaGF2aW5nIHN0YXRpc3RpY2FsbHkgImNvbnRyb2xsZWQiIGZvciBtZWRpYSBhZ2Ugb2YgbWFycmlhZ2UuIFRoZSB2ZXJ0aWNhbCBkYXNoZWQgbGluZSBpbmRpY2F0ZXMgbWFycmlhZ2UgcmF0ZSB0aGF0IGV4YWN0bHkgbWF0Y2hlcyB0aGUgZXhwZWN0YXRpb24gZnJvbSBtZWRpYW4gYWdlIGF0IG1hcnJpYWdlLiBTbyBzdGF0ZXMgdG8gdGhlIHJpZ2h0IG9mIHRoZSBsaW5lIG1hcnJ5IGZhc3RlciB0aGFuIGV4cGVjdGVkOyB0byB0aGUgbGVmdCAtIHNsb3dlci4gQXZlcmFnZSBkaXZvcmNlIHJhdGUgb24gYm90aCBzaWRlcyBvZiB0aGUgbGluZSBpcyBhYm90IHRoZSBzYW1lLCBhbmQgc28gdGhlIHJlZ3Jlc3Npb24gbGluZSBkZW1vbnN0YXRlcyBsaXR0bGUgcmVsYXRpb25zaGlwIGJldHdlZW4gZGl2b3JjZSBhbmQgbWFycmlhZ2UgcmF0ZXMuIFRoZSBzbG9wZSBvZiB0aGlzIGxpbmUgaXMgYC0uMTNgLCBleGFjdGx5IHdoYXQgd2UgZm91bmQgaW4gdGhlIG11bHRpdmFyaWF0ZSBtb2RlbCwgYG01LjNgLiAKCgoqKlBMT1QgSEVSRSoqCgpUaGlzIHBsb3Qgc2hvd3MgdGhlIHNhbWUga2luZCBvZiBjYWxjdWxhdGlvbiwgYnV0IG5vdyBmb3IgbWVkaWFuIGFnZSBhdCBtYXJyaWFnZSwgImNvbnRyb2xsaW5nIiBmb3IgbWFycmlhZ2UgcmF0ZS4gU28gc3RhdGVzIHRvIHRoZSByaWdodCBoYXZlIG9sZGVyLXRoYW4tZXhwZWN0ZWQgbWVkaWFuIGFnZSBhdCBtYXJyaWFnZSwgdGhhbiB0aG9zZSBvZiB0aGUgbGVmdC4gTm93IHdlIGZpbmQgdGhhdCB0aGUgYXZlcmFnZSBkaXZvcmNlIHJhdGUgb24gdGhlIHJpZ2h0IGlzIGxvd2VyIHRoYW4gb24gdGhlIGxlZnQsIGFzIGluZGljYXRlZCBieSB0aGUgcmVncmVzc2lvbiBsaW5lLiBTdGF0ZXMgaW4gd2hpY2ggcGVvcGxlIG1hcnJ5IG9sZGVyIHRoYW4gZXhwZWN0ZWQgZm9yIGEgZ2l2ZW4gcmF0ZSBvZiBtYXJyaWFnZSB0ZW4gdG8gaGF2ZSBsZXNzIGRpdm9yY2UuIFRoZSBzbG9wZSBvZiB0aGUgcmVncmVzc2lvbiBsaW5lIGhlcmUgaXMgYC0xLjEzYCwgYWdhaW4gdGhlIHNhbWUgYXMgaW4gdGhlIG11bHRpdmFyaWF0ZSBtb2RlbCwgYG01LjNgLiAKCiMjIyMgNS4xLjMuMiBDb3VudGVyZmFjdHVhbCBwbG90cy4gCgpUaGVzZSBwbG90cyBzaG93IHRoZSAqKmltcGxpZWQqKiBwcmVkaWN0aW9ucyBvZiB0aGUgbW9kZWwuIApXZSBjYWxsIHRoZW0gKmNvdW50ZXJmYWN0dWFsKiwgYmVjYXVzZSB0aGV5IGNhbiBiZSBwcm9kdWNlZCBmb3IgYW55IHZhbHVlcyBvZiB0aGUgcHJlZGljdG9yIHZhcmlhYmxlIHlvdSBsaW5lLCBldmVuIHVub2JzZXJ2ZWQgb3IgaW1wb3NzaWJsZSBjb21iaW5hdGlvbnMgbGlrZSB2ZXJ5IGhpZ2ggbWVkaWFuIGFnZSBvciBtYXJyaWFnZSBhbmQgdmVyeSBoaWdoIG1hcnJpYWdlIHJhdGUuIAoKVGhlIHNpbXBsZXN0IHVzZSBvZiBhIGNvdW50ZXJmYWN0dWFsIHBsb3QgaXMgdG8gc2VlIGhvdyB0aGUgcHJlZGljdGlvbnMgY2hhbmdlIGFzIHlvdSBjaGFuZ2Ugb25seSBvbmUgcHJlZGljdG9yIGF0IGEgdGltZS4gVGhpcyBtZWFucyBob2xkaW5nIHRoZSB2YWx1ZXMgb2YgYWxsIHByZWRpY3RvcnMgY29uc3RhbnQsIGV4Y2VwdCBmb3IgYSBzaW5nbGUgcHJlZGljdG9yIG9mIGludGVyZXN0LiAKCkxldCdzIGRyYXcgYSBwYWlyIG9mIGNvdW50ZXJmYWN0dWFsIHBsb3RzIGZvciB0aGUgZGl2b3JjZSBtb2RlbC4gQmVnaW5uaW5nIHdpdGggYSBwbG90IHNob3dpbmcgdGhlIGltcGFjdCBvZiBjaGFuZ2VzIGluIGBNYXJyaWFnZS5zYCBvbiBwcmVkaWN0aW9uczogCgpgYGB7cn0KI3ByZXBhcmUgbmV3IGNvdW50ZXJmYWN0dWFsIGRhdGEKQS5hdmcgPC0gbWVhbihkJE1lZGlhbkFnZU1hcnJpYWdlLnMpClIuc2VxIDwtIHNlcShmcm9tID0gLTMsIHRvID0gMywgbGVuZ3RoLm91dCA9IDMwKQpwcmVkLmRhdGEgPC0gZGF0YS5mcmFtZSgKICBNYXJyaWFnZS5zPVIuc2VxLCAKICBNZWRpYW5BZ2VNYXJyaWFnZS5zPUEuYXZnCikKCiNjb21wdXRlIGNvdW50ZXJmYWN0dWFsIG1lYW4gZGl2b3JjZSByYXRlIChtdSkKbXUgPC0gbGluayhtNS4zLCBkYXRhID0gcHJlZC5kYXRhKQptdS5tZWFuIDwtIGFwcGx5KG11LCAyLCBtZWFuKQptdS5QSSA8LSBhcHBseShtdSwgMiwgUEkpCgojc2ltdWxhdGUgY291bnRlcmZhY3R1YWwgZGl2b3JjZSBvdXRjb21lcwpSLnNpbSA8LSByZXRoaW5raW5nOjpzaW0obTUuMywgZGF0YSA9IHByZWQuZGF0YSwgbiA9IDFlNCkKUi5QSSA8LSBhcHBseShSLnNpbSwgMiwgUEkpCgojZGlzcGxheSBwcmVkaWN0aW9ucywgaGlkaW5nIHJhdyBkYXRhIHdpdGggdHlwZSA9ICduJwpwbG90KERpdm9yY2UgfiBNYXJyaWFnZS5zLCBkYXRhID0gZCwgdHlwZSA9ICJuIikKbXRleHQoIk1lZGlhbkFnZU1hcnJpYWdlLnMgPSAwIikKbGluZXMoUi5zZXEsIG11Lm1lYW4pCnNoYWRlKG11LlBJLCBSLnNlcSkKc2hhZGUoUi5QSSwgUi5zZXEpCmBgYAoKVGhlIHN0cmF0ZWd5IGFib3ZlIGlzIHRvIGJ1aWxkIGEgbmV3IGxpc3Qgb2YgZGF0YSB0aGF0IGRlc2NyaWJlIHRoZSBjb3VudGVyZmFjdHVhbCBjYXNlcyB3ZSB3aXNoIHRvIHNpbXVsYXRlIHByZWRpY3Rpb25zIGZvci4gVGhlIGxpc3QgbmFtZXMgYHByZWQuZGF0YWAgaG9sZHMgdGhlc2UgY2FzZXMuIE5vdCB0aGF0IHRoZSBvYnNlcnZlZCB2YWx1ZXMgZm9yIGBNZWRpYW5BZ2VNYXJyaWFnZS5zYCBhcmUgbm90IHVzZWQuIEluc3RlYWQgd2UgY29tcHV0ZSB0aGUgYXZlcmFnZSB2YWx1ZSBhbmQgdGhlbiB1c2UgaXQgaW5zaWRlIHRoZSBsaW5lYXIgbW9kZWwuIFNvIGBNYXJyaWFnZS5TYCBjaGFuZ2VzIGFjcm9zcyB0aGUgdmFsdWVzIG9mIGBSLnNlcWAsIHdoaWxlIHRoZSBvdGhlciBwcmVkaWN0b3IgaXMgaGVsZCBjb25zdGFudCBhcyBpdCBtZWFuLCBgQS5hdmdgLiAKCkxldCdzIGRvIHRoZSBzYW1lIGZvciBgTWVkaWFuQWdlTWFycmlhZ2Uuc2Agd2hpY2ggYXJlIGFsbG93ZWQgdG8gdmFyeSBhbmQgYE1hcnJpYWdlLnNgIGJlaW5nIGhlbGQgY29uc3RhbnQ6IAoKYGBge3J9ClIuYXZnIDwtIG1lYW4oZCRNYXJyaWFnZS5zKQpBLnNlcSA8LSBzZXEoZnJvbSA9IC0zLCB0byA9IDMuNSwgbGVuZ3RoLm91dCA9IDMwKQpwcmVkLmRhdGEyIDwtIGRhdGEuZnJhbWUoCiAgTWFycmlhZ2UucyA9IFIuYXZnLCAKICBNZWRpYW5BZ2VNYXJyaWFnZS5zID0gQS5zZXEKKQoKI2NvbXB1dGUgY291bnRlcmZhY3R1YWwgbWVhbiBkaXZvcmNlIHJhdGUgKG11KQptdSA8LSBsaW5rKG01LjMsIGRhdGEgPSBwcmVkLmRhdGEyKQptdS5tZWFuIDwtIGFwcGx5KG11LCAyLCBtZWFuKQptdS5QSSA8LSBhcHBseShtdSwgMiwgUEkpCgojc2ltdWxhdGUgY291bnRlcmZhY3R1YWwgZGl2b3JjZSBvdXRjb21lcwpBLnNpbSA8LSByZXRoaW5raW5nOjpzaW0obTUuMywgZGF0YSA9IHByZWQuZGF0YTIsIG4gPSAxZTQpCkEuUEkgPC0gYXBwbHkoQS5zaW0sIDIsIFBJKQoKI2Rpc3BsYXkgcHJlZGljdGlvbnMsIGhpZGluZyByYXcgZGF0YSB3aXRoIHR5cGUgPSAnbicKcGxvdChEaXZvcmNlIH4gTWVkaWFuQWdlTWFycmlhZ2UucywgZGF0YSA9IGQsIHR5cGUgPSAibiIpCm10ZXh0KCJNZWRpYW5BZ2VNYXJyaWFnZS5zID0gMCIpCmxpbmVzKEEuc2VxLCBtdS5tZWFuKQpzaGFkZShtdS5QSSwgQS5zZXEpCnNoYWRlKEEuUEksIEEuc2VxKQpgYGAKClRoZXNlIHBsb3RzIGhhdmUgdGhlIHNhbWUgc3Bsb3RzIGFzIHRoZSByZXN1ZHVhbCBwbG90cywgYnV0IHRoZXkgZG9uJ3QgZGlzcGxheSBhbnkgZGF0YSwgcmF3IG9yIHJlc2lkdWFsLCBiZWNhdXNlIHRoZXkgYXJlIGNvdW50ZXJmYWN0dWFsLiBBbmQgdGhleSBhbHNvIHNob3cgcGVyY2VudGlsZSBpbnRlcnZhbHMgb24gdGhlIHNjYWxlIG9mIHRoZSBkYXRhLCBpbnN0ZWFkIG9mIG9uIHRoZSByZWRpc3VhbCBzY2FsZS4gQXMgdGhlIHJlc3VsdCwgdGhleSBhcmUgZGljcmVjdCBkaXNwbGF5cyBvZiB0aGUgaW1wYWN0IG9uIHByZWRpY3Rpb24gb2YgYSBjaGFuZ2UgaW4gZWFjaCB2YXJpYWJsZS4gCgojNS4xLjMuMy4gUG9zdGVyaW9yIHByZWRpY3Rpb24gcGxvdHMKCkluIGFkZGl0aW9uIHRvIHVuZGVyc3RhbnRpbmcgdGhlIGVzdGltYXRlcywgaXQncyBpbXBvcnRhdG4gdG8gY2hlY2sgdGhlIG1vZGVsIGZpdCBhZ2FpbnMgdGhlIG9ic2VydmVkIGRhdGEuIAoKMS4gRGlkIHRoZSBtb2RlbCBmaXQgY29ycmVjdGx5PyAoQ29tcGFyZSBpbXBsaWVkIHByZWRpY3Rpb25zIHRvIHRoZSByYXcgZGF0YSkKMi4gaG93IGRvZXMgdGhlIG1vZGVsIGZhaWw/IChCeSBpbnNwZWN0aW5nIHRoZSBpbmRpdmlkdWFsIGNhc2VzIHdoZXJlIHRoZSBtb2RlbCBtYWVrcyBwb29yIHByZWRpY3Rpb25zLCB5b3UgbWlnaHQgZ2V0IGFuIGlkZWEgb2YgaG93IHRvIGltcHJvdmUgdGhlIG1vZGVsKQoKTGV0J3MgYmVnaW4gYnkgc2ltdWxhdGlvbiBwcmVkaWN0aW9uLCBhdmVyYWluZyBvdmVyIHRoZSBwb3N0ZXJpb3IuIAoKYGBge3J9CiNjYWxsIHJldGhpbmtpbmc6OmxpbmsoKSB3aXRob3V0IHNwZWNpZnlpbmcgbmV3IGRhdGEsIHNvIGl0IHVzZXMgb3JpZ2luYWwgZGF0YQptdSA8LSBsaW5rKG01LjMpCgojc3VtbWFyaXNlIHNhbXBsZXMgYWNyb3NzIGNhc2VzCm11Lm1lYW4gPC0gYXBwbHkobXUsIDIsIG1lYW4pCm11LlBJIDwtIGFwcGx5KG11LCAyLCBQSSkKCiNzaW11bGF0ZSBvYnNlcnZhdGlvbnMsIGFnYWluIG5vIG5ldyBkYXRhLCBzbyB1c2VzIG9yaWdpbmFsIGRhdGEKZGl2b3JjZS5zaW0gPC0gcmV0aGlua2luZzo6c2ltKG01LjMsIG4gPSAxZTQpCmRpdm9yY2UuUEkgPC0gYXBwbHkoZGl2b3JjZS5zaW0sIDIsIFBJKQpgYGAKCgpUaGUgY29kZSBpcyBzaW1pbGFyIHdlJ3ZlIHNlZW4gYmVmb3JlIGJ1dCBub3cgd2UgdXNlIHRoZSBvcmlnaW5hbCBvYnNlcnZlZCBkYXRhLgoKRm9yIG11bHRpdmFyaWF0ZSBtb2RlbHMsIHRoZXJlIGFyZSBtYW55IGRpZmZlcmVudCB3YXlzIHRvIGRpcGxheSB0aGVzZSBzaW11bGF0aW9ucy4gClRoZSBzaW1wbGVzdCBpcyB0byBqdXN0IHBsb3QgcHJlZGljdGlvbnMgYWdhaW5zdCBvYnNlcnZlZC4gCgpgYGB7cn0KcGxvdChtdS5tZWFuIH4gZCREaXZvcmNlLCBjb2wgPSByYW5naTIsIHlsaW0gPSByYW5nZShtdS5QSSksIAogICAgIHhsYWIgPSAiT2JzZXJ2ZWQgZGl2b3JjZSIsIHlsYWIgPSAiUHJlZGljdGVkIGRpdm9yY2UiKQoKYWJsaW5lKGEgPSAwLCBiID0gMSwgbHR5ID0gMikKZm9yKGkgaW4gMTpucm93KGQpKSB7CiAgbGluZXMocmVwKGQkRGl2b3JjZVtpXSwgMiksIGMobXUuUElbMSwgaV0sIG11LlBJWzIsIGldKSwgY29sID0gcmFuZ2kyKQp9CmBgYAoKSXQncyBlYXN5IHRvIHNlZSBmcm9tIHRoZSBwbG90IHRoYXQgdGhlIG1vZGVsIHVuZGVyLXByZWRpY3RzIGZvciBTdGF0ZXMgd2l0aCB2ZXJ5IGhpZ2ggZGl2b3JjZSByYXRlIHdoaWxlIG92ZXItcHJlZGljdHMgZm9yIFN0YXRlcyB3aXRoIHZlcnkgbG93ZXIgZGl2b3JjZSByYXRlLiAKCmBgYHtyfQpwbG90KG11Lm1lYW4gfiBkJERpdm9yY2UsIGNvbCA9IHJhbmdpMiwgeWxpbSA9IHJhbmdlKG11LlBJKSwgIHhsYWIgPSAiT2JzZXJ2ZWQgZGl2b3JjZSIsIHlsYWIgPSAiUHJlZGljdGVkIGRpdm9yY2UiKQoKYWJsaW5lKGEgPSAwLCBiID0gMSwgbHR5ID0gMikKCmZvcihpIGluIDE6bnJvdyhkKSkgewogIGxpbmVzKHJlcChkJERpdm9yY2VbaV0sIDIpLCBjKG11LlBJWzEsIGldLCBtdS5QSVsyLCBpXSksIGNvbCA9IHJhbmdpMikKfQoKI2RvZXNuJ3Qgd29yayBpbiBub3RlYm9vaywgb25seSBhcyBhIHBhcnQgb2Ygc2NyaXB0IG9yIGluIGNvbnNvbGUgKGJldHRlciBpbiBjb25zb2xlKQojanVzdCBjbGljayBvbiBzZXZlcmFsIHBvaW50cyBhbmQgdGhlbiByaWdodC1jbGljayBpbiBjb25zb2xlIChvciBFU0MpIHRvIHNlZSB0aGUgbGFiZWxzCmlkZW50aWZ5KHggPSBkJERpdm9yY2UsIHkgPSBtdS5tZWFuLCBsYWJlbHMgPSBhcy5jaGFyYWN0ZXIoZCRMb2MpLCBjZXggPSAwLjgpCmBgYAoKVGhpcyBwbG90IG1ha2VzIGlzIGhhcmQgdG8gc2VlIHRoZSBhbW91bnQgb2YgcHJlZGljdGlvbiBlcnJvci4gRm9yIHRoaXMgcmVhc29uLCB3ZSdsbCB1c2UgdGhlICpyZXNpZHVhbCogcGxvdCB0aGF0IHNob3cgdGhlIG1lYW4gcHJlZGljdGlvbiBlcnJvciBmb3IgZWFjaCByb3cuIAoKYGBge3J9CiNjb21wdXRlIHJlc2lkdWFscwpkaXZvcmNlLnJlc2lkIDwtIGQkRGl2b3JjZSAtIG11Lm1lYW4KCiNnZXQgb3JkZXJpbmcgYnkgZGl2b3JjZSByYXRlCm8gPC0gb3JkZXIoZGl2b3JjZS5yZXNpZCkKCiNtYWtlIHRoZSBwbG90CmRvdGNoYXJ0KGRpdm9yY2UucmVzaWRbb10sIGxhYmVscyA9IGQkTG9jW29dLCB4bGltID0gYygtNiwgNSksIGNleCA9IDAuNikKYWJsaW5lKHYgPSAwLCBjb2wgPSBjb2wuYWxwaGEoImJsYWNrIiwgMC4yKSkKCmZvcihpIGluIDE6bnJvdyhkKSkgewogIGogPC0gb1tpXSAjIHdoaWNoIHN0YXRlIGluIG9yZGVyCiAgbGluZXMoZCREaXZvcmNlW2pdIC0gYyhtdS5QSVsxLCBqXSwgbXUuUElbMiwgal0pLCByZXAoaSwgMikpCiAgcG9pbnRzKGQkRGl2b3JjZVtqXSAtIGMoZGl2b3JjZS5QSVsxLCBqXSwgZGl2b3JjZS5QSVsyLCBqXSksIHJlcChpLCAyKSwgcGNoID0gMywgY2V4PTAuNiwgY29sID0gImdyYXkiKQp9CgpgYGAKCkl0J3MgbXVjaCBlYXNpZXIgdG8gc2VlIHRoZSBsYXJnZSBtb2RlbCBmYWlsdXJlcywgc3VjaCBhcyBJRCBhbmQgTUUuCgpBbm90aGVyIGNvbW1vbiB1c2UgZm9yIHRoZXNlIHNpbXVsYXRpb25zIGlzIHRvIGNvbnN0dWN0IG5vdmVsIHByZWRpY3RvciByZXNpZHVhbCBwbG90cy4gT25jZSB5b3UndmUgY29tcHV0ZWQgdGhlIGRpdm9yY2UgcmVzaWR1YWxzIChhcyBkb25lIGFib3ZlKSwgeW91IGNhbiBwbG90IHRob3NlIHJlc2lkdWFscyBhZ2FpbnN0IG5ldyBwcmVkaWN0b3IgdmFyaWFibGVzLiAqKlRoaXMgaXMgYSBxdWljayB3YXkgdG8gc2VlIGlmIHJlbWFpbmluZyB2YXJpYXRpb24gaW4gdGhlb3V0Y29tZSBpcyBhc3NvY2lhdGVkIHdpdGggYW5vdGhlciBwcmVkaWN0b3IqKi4KCgojIyA1LjIuIE1hc2tlZCByZWxhdGlvbnNoaXAKClRoZSBkaXZvcmNlIHJhdGUgZXhhbXBsZSBkZW1vbnN0cmF0ZXMgdGhhdCBtdWx0aXBsZSBwcmVkaWN0b3IgdmFyaWFibGVzIGFyZSB1c2VmdWwgZm9yIGtub2NraW5nIG91dCBzcHVyaW91cyBhc3NvY2lhdGlvbi4gCkEgc2Vjb25kIHJlYXNvbiB0byB1c2UgbW9yZSB0aGFuIG9uZSBwcmVkaWN0b3IgdmFyaWFibGUgaXMgdG8gbWVhc3VyZSB0aGUgZGlyZWN0IGluZmx1ZW5jZXMgb2YgbXVsdGlwbGUgZmFjdG9ycyBvbiBhbiBvdXRjb21lLCB3aGVuIG5vbiBvZiB0aG9zZSBpbmZ1ZW5jZXMgaXMgYXBwYXJlbnQgZnJvbSBiaXZhcmlhdGUgcmVsYXRpb25zaGlwcy4gVGhpcyBwcm9ibGVtIHRlbmRzIHRvIGFyaWVzIHdoZW4gKnRoZXJlJ3JlIHR3byBwcmVkaWN0b3IgdmFyaWFibGVzIHRoYXQgYXJlIGNvcnJlbGF0ZWQgd2l0aCBvbmUgYW5vdGhlciosIGJ1dCBvbmUgY29ycmVsYXRlZCBwb3NpdGl2ZWx5IGFuZCBvdGhlciBuZWdhdGl2ZWx5LiAKCkxldCdzIHNlZSBhbiBleGFtcGxlIG9mIGBtaWxrYDoKCmBgYHtyfQpsaWJyYXJ5KHJldGhpbmtpbmcpCmRhdGEoIm1pbGsiKQpkIDwtIG1pbGsKZ2xpbXBzZShkKQpgYGAKClRoZSBwb3B1bGFyIGh5cG90aGVzaXMgaGFzIGl0IHRoYXQgcHJpbWF0ZXMgd2l0aCBsYXJnZXIgYnJhaW5zIHByb2R1Y3QgbW9yZSBlbmVyZ2V0aWMgbWlsaywgc28gdGhhdCBicmFpbnMgY2FuIGdyb3cgcXVpY2tseS4gU28gdGhlIHZhcmlhYmxlcyB3ZSdsbCBjb25zaWRlciBub3cgYXJlOiAKCiogKmtjYWwucGVyLmcqIC0gS2lsb2NhbGlyaWVzIG9mIGVuZXJneSBwZXIgZ3JhbSBvZiBtaWxrCiogKm1hc3MqIC0gQXZlcmFnZSBmZW1hbGUgYm9keSBtYXNzLCBpbiBrZwoqICpuZW9jb3J0ZXgucGVyYyogLSB0aGUgcGVyY2VudCBvZiB0b3RhbCBicmFpbiBtYXNzIHRoYXQgaXMgbmVvY29ydGV4IG1hc3MuIAoKVGhlIHF1ZXN0aW9uIGhlcmUgaXMgdG8gd2hhdCBleHRlbnQgZW5lcmd5IGNvbnRlbnQgb2YgbWlsaywgbWVhc3VyZWQgaGVyZSBieSBraWxvY2Fsb3JpZXMsIGlzIHJlbGF0ZWQgdG8gdGhlIHBlcmNlbnQgb2YgdGhlIGJyYWluIG1hc3MgdGhhdCBpcyBuZW9jb3J0ZXguIEZlbWFsZSBtYXNzIGlzIHVzZWQgaGVyZSB0byBzZWUgdGhlIG1hc2tpbmcgdGhhdCBoaWRlcyByZWxhdGlvbnNoaXAgYW1vbmcgdGhlIHZhcmlhYmxlLiAKCkJ1dCBiZWZvcmUgZml0dGluZyBhIG1vZGVsLCBsZXQncyBleGNsdWRlIHRoZSBtaXNzaW5nIHZhbHVlcyBmcm9tIHRoZSBkYXRhLgoKYGBge3J9CmQgPC0gZFtjb21wbGV0ZS5jYXNlcyhkKSwgXQpgYGAKCgpgYGB7cn0KbTUuNSA8LSBtYXAoCiAgYWxpc3QoCiAgICBrY2FsLnBlci5nIH4gZG5vcm0obXUsIHNpZ21hKSwgCiAgICBtdSA8LSBhICsgYm4qbmVvY29ydGV4LnBlcmMsIAogICAgYSB+IGRub3JtKDAsIDEwMCksIAogICAgYm4gfiBkbm9ybSgwLCAxKSwgCiAgICBzaWdtYSB+IGR1bmlmKDAsIDEpCiAgKSwgZGF0YSA9IGQKKQpwcmVjaXMobTUuNSwgZGlnaXRzID0gMykKYGBgCgpOZXh0IHdlIGNhbiBwbG90IHRoZSBwcmVkaWN0ZWQgbWVhbiBhbmQgODklIGludGVydmFsOiAKCmBgYHtyfQpucC5zZXEgPC0gMDoxMDAKcHJlZC5kYXRhIDwtIGRhdGEuZnJhbWUobmVvY29ydGV4LnBlcmMgPSBucC5zZXEpCgptdSA8LSBsaW5rKG01LjUsIGRhdGEgPSBwcmVkLmRhdGEsIG4gPSAxZTQpCm11Lm1lYW4gPC0gYXBwbHkobXUsIDIsIG1lYW4pCm11LlBJIDwtIGFwcGx5KG11LCAyLCBQSSkKCnBsb3Qoa2NhbC5wZXIuZyB+IG5lb2NvcnRleC5wZXJjLCBkYXRhID0gZCwgY29sID0gcmFuZ2kyKQpsaW5lcyhucC5zZXEsIG11Lm1lYW4pCmxpbmVzKG5wLnNlcSwgbXUuUElbMSwgXSwgbHR5ID0gMikKbGluZXMobnAuc2VxLCBtdS5QSVsyLCBdLCBsdHkgPSAyKQoKYGBgCgpNQVAgbGluZSBpcyB3ZWFrbHkgcG9zaXRpdmUsIGJ1dCBpdCdzIGhpZ2hseSBpbXByZWNpc2UuIAoKTm93IGxldCdzIGNvbnNpZGVyIGFub3RoZXIgcHJlZGljdG9yIHZhcmlhYmxlLCBhZHVsdCBmZW1hbGUgYm9keSBtYXNzLCBgbWFzc2AgaW4gb3VyIGRhdGEgZnJhbWUuIExldCdzIHVzZSBsb2cgb2YgbWFzcyBhcyBhIHByZWRpY3Rvci4gCgpgYGB7cn0KZCRsb2cubWFzcyA8LSBsb2coZCRtYXNzKQptNS42IDwtIG1hcCgKICBhbGlzdCgKICAgIGtjYWwucGVyLmcgfiBkbm9ybShtdSwgc2lnbWEpLCAKICAgIG11IDwtIGEgKyBibSpsb2cubWFzcywgCiAgICBhIH4gZG5vcm0oMCwgMTAwKSwgCiAgICBibSB+IGRub3JtKDAsIDEpLCAKICAgIHNpZ21hIH4gZHVuaWYoMCwgMSkKICApLCBkYXRhID0gZAopCnByZWNpcyhtNS42LCBkaWdpdHMgPSAzKQpgYGAKClNvIGxvZy1tYXNzIGlzIG5lZ2F0aXZlbHkgY29ycmVsYXRlZCB3aXRoIGtpbG9jYWxvcmllcyBhbmQgdGhpcyBpbmZsdWVuY2UgaXMgc3Ryb25nZXIgdGhhbiBuZW9jb3J0ZXggb25lLiAKCk5vdyBsZXQncyBzZWUgd2hhdCBoYXBwZW5zIHdoZW4gd2UgYWRkIGJvdGggcHJlZGljdG9yIHZhcmlhYmxlcyBhdCB0aGUgc2FtZSB0aW1lIHRvIHRoZSByZWdyZXNzaW9uOiAKCmBgYHtyfQptNS43IDwtIG1hcCgKICBhbGlzdCgKICAgIGtjYWwucGVyLmcgfiBkbm9ybShtdSwgc2lnbWEpLCAKICAgIG11IDwtIGEgKyBibSpsb2cubWFzcyArIGJuKm5lb2NvcnRleC5wZXJjLCAKICAgIGEgfiBkbm9ybSgwLCAxMDApLCAKICAgIGJuIH4gZG5vcm0oMCwgMSksCiAgICBibSB+IGRub3JtKDAsIDEpLCAKICAgIHNpZ21hIH4gZHVuaWYoMCwgMSkKICApLCBkYXRhID0gZAopCnByZWNpcyhtNS43LCBkaWdpdHMgPSAzKQpgYGAKCkJ5IGluY29ycG9yYXRpbmcgYm90aCBwcmVkaWN0b3IgdmFyaWFibGUgaW4gdGhlIHJlZ3Jlc3Npb24sIHRoZSBlc3RpbWF0ZWQgYXNzb2NpYXRpb24gb2YgYm90aCB3aXRoIHRoZSBvdXRjb21lIGhhcyBpbmNyZWFzZWQuCgpMZXQncyBwbG90IHRoZSBpbnRlcnZhbHMgZm9yIHRoZSBwcmVkaWN0ZWQgbWVhbiBraWxvY2Fsb3JpZXMsIGZvciB0aGlzIG5ldyBtb2RlbC4gCgpgYGB7cn0KbWVhbi5sb2cubWFzcyA8LSBtZWFuKGxvZyhkJG1hc3MpKQptZWFuLm5lb2NvcnRleC5wZXJjID0gbWVhbihkJG5lb2NvcnRleC5wZXJjKQpucC5zZXEgPC0gMDoxMDAKCiNuZW9jb3J0ZXggcGVyYwpwcmVkLmRhdGEgPC0gZGF0YS5mcmFtZSgKICBuZW9jb3J0ZXgucGVyYyA9IG5wLnNlcSwgCiAgbG9nLm1hc3MgPSBtZWFuLmxvZy5tYXNzCikKCm11IDwtIGxpbmsobTUuNywgZGF0YSA9IHByZWQuZGF0YSwgbiA9IDFlNCkKbXUubWVhbiA8LSBhcHBseShtdSwgMiwgbWVhbikKbXUuUEkgPC0gYXBwbHkobXUsIDIsIFBJKQoKcGxvdChrY2FsLnBlci5nIH4gbmVvY29ydGV4LnBlcmMsIGRhdGEgPSBkLCB0eXBlID0gIm4iLCBtYWluID0gIk5lb2NvcnRleCBQZXJjIHZzIGtjYWwgcGVyIGdyYW1tICIpCmxpbmVzKG5wLnNlcSwgbXUubWVhbikKbGluZXMobnAuc2VxLCBtdS5QSVsxLCBdLCBsdHkgPSAyKQpsaW5lcyhucC5zZXEsIG11LlBJWzIsIF0sIGx0eSA9IDIpCgojbG9nIG1hc3MKbnAuc2VxIDwtIC0xMDA6MTAwCnByZWQuZGF0YSA8LSBkYXRhLmZyYW1lKAogIGxvZy5tYXNzID0gbnAuc2VxLCAKICBuZW9jb3J0ZXgucGVyYyA9IG1lYW4ubmVvY29ydGV4LnBlcmMKKQoKbXUgPC0gbGluayhtNS43LCBkYXRhID0gcHJlZC5kYXRhLCBuID0gMWU0KQptdS5tZWFuIDwtIGFwcGx5KG11LCAyLCBtZWFuKQptdS5QSSA8LSBhcHBseShtdSwgMiwgUEkpCgpwbG90KGtjYWwucGVyLmcgfiBsb2cubWFzcywgZGF0YSA9IGQsIHR5cGUgPSAibiIsIG1haW4gPSAiTG9nIE1hc3MgdnMga2NhbCBwZXIgZ3JhbW0gIikKbGluZXMobnAuc2VxLCBtdS5tZWFuKQpsaW5lcyhucC5zZXEsIG11LlBJWzEsIF0sIGx0eSA9IDIpCmxpbmVzKG5wLnNlcSwgbXUuUElbMiwgXSwgbHR5ID0gMikKYGBgCgpTaW5jZSBvbmUgdmFyaWFibGUgaXMgcG9zaXRpdmVseSBjb3JyZWxhdGVkIHdpdGggdGhlIG91dGNvbWUgYW5kIGFub3RoZXIgaXMgbmVnYXRpdmVseSBjb3JyZWxhdGVkLCB0aGV5IHRlbmQgdG8gY2FuY2VsIG9uZSBhbm90aGVyIG91dC4gCgoKIyMgNS4zIFdoZW4gYWRkaW5nIHZhcmlhYmxlcyBodXJ0cwoKVGhlcmUncmUgc2V2ZXJhbCBnb29kLCBwdXJlbHkgc3RhdGlzdGljYWwgcmVhc29ucyB0byBhdm9pZCBkb2luZyB0aGlzLgoKMS4gKipNdWx0aWNvbGxpbmVhcml0eSoqIC0gc3Ryb25nIGNvcnJlbGF0aW9uIGJldHdlZW4gdHdvIG9yIG1vcmUgcHJlZGljdG9yIHZhcmlhYmxlcy4gVGhlIGNvbnNlcXVlbmNlIG9mIGl0IGlzIHRoYXQgdGhlIHBvc3RlcmlvciBkaXN0cmlidXRpb24gd2lsbCBzYXkgdGhhdCBhIHZlcmF5IGxhcmdlIHJhbmdlIG9mIHBhcmFtZXRlciBhcmUgcGxhdXNpYmxlLgoyLiAqKlBvc3QtdHJlYXRtZW50IGJpYXMqKiAtIHN0YXRpc3RpY2FsbHkgY29udHJvbGxpbmcgZm9yIGNvbnNlcXVlbmNlcyBvZiBhIGNhdXNhbCBmYWN0b3IuCjMuICoqT3ZlcmZpdHRpbmcqKgoKCiMjIyA1LjMuMS4gTXVsdGljb2xsaW5lYXIgbGVncwoKYGBge3J9Ck4gPC0gMTAwICMgbnVtYmVyIG9mIGluZGl2aWR1YWxzCmhlaWdodCA8LSBybm9ybShOLCAxMCwgMikgI3NpbSB0b3RhbCBoZWlnaHQgb2YgZWFjaApsZWdfcHJvcCA8LSBydW5pZihOLCAwLjQsIDAuNSkgI2xlZyBhcyBwcm9wb3J0aW9uIG9mIGhlaWdoCmxlZ19sZWZ0IDwtIGxlZ19wcm9wICogaGVpZ2h0ICsgcm5vcm0oTiwgMCwgMC4wMikgI3NpbSBsZWZ0IGxlZyBhcyBwcm9wb3J0aW9uICsgZXJyb3IKbGVnX3JpZ2h0IDwtIGxlZ19wcm9wICogaGVpZ2h0ICsgcm5vcm0oTiwgMCwgMC4wMikgI3NpbSByaWdodCBsZWcgYXMgcHJvcG9ydGlvbiArIGVycm9yCmQgPC0gZGF0YS5mcmFtZShoZWlnaHQsIGxlZ19sZWZ0LCBsZWdfcmlnaHQpCmBgYAoKTm93IGxldCdzIGFuYWx5emUgdGhlc2UgZGF0YSwgcHJlZGljdGlvbiB0aGUgb3V0Y29tZSBgaGVpZ2h0YCB3aXRoIGJvdGggcHJlZGljdGlvbnMsIGBsZWdfbGVmdGAgYW5kIGBsZWdfcmlnaHRgLgpPdXIgZXhwZWN0YXRpb24gdGhhdCAqYmV0YSogY29lZmZpY2llbnQgaXMgZXF1YWwgdG8gMTAgLyA0LjUgPSAyLjIgKDQuNSA9IDEwICogMC40NSAtIGF2ZXJhZ2UgcHJvcG9ydGlvbiBvZiB0aGUgbGVnKS4gCgoKYGBge3J9Cm01LjggPC0gbWFwKAogIGFsaXN0KAogICAgaGVpZ2h0IH4gZG5vcm0obXUsIHNpZ21hKSwKICAgIG11IDwtIGEgKyBibCpsZWdfbGVmdCArIGJyKmxlZ19yaWdodCwgCiAgICBhIH4gZG5vcm0oMTAsIDEwMCksCiAgICBibCB+IGRub3JtKDIsIDEwKSwKICAgIGJyIH4gZG5vcm0oMiwgMTApLAogICAgc2lnbWEgfiBkdW5pZigwLCAxMCkKICApLCBkYXRhID0gZAopCnByZWNpcyhtNS44KQpwcmVjaXNfcGxvdChwcmVjaXMobTUuOCkpCmBgYAoKRGVzcGl0ZSB0aGUgZmFjdCB0aGF0IHRoZSBgcHJlY2lzYCBwbG90IGxvb2tzIG9kZCwgbW9kZWwgZGlkIGZpdCBjb3JyZWN0bHksIGFuZCB0aGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBoZXJlIGlzIHRoZSByaWdodCBhbnN3ZXIgdG8gdGhlIHF1ZXN0aW9uIHdlIGFza2VkIC0gKndoYXQgaXMgdGhlIHZhbHVlIG9mIGtub3dpbmcgZWFjaCBwcmVkaWN0b3IsIGFmdGVyIGFscmVhZHkga25vd2luZyBhbGwgdGhlIG90aGVyIHByZWRpY3RvcnM/KgpUaGUgYW5zd2VyIHRvIHRoZSBxdWVzdGlvbiBpcyB3aWVyZCwgYnV0IHBlcmZlY3RseSBsb2dpY2FsLiBUaGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlubyBpcyB0aGUgYW5zd2VyIHRvIHRoaXMgcXVlc3Rpb24sIGNvbnNpZGVyaW5nIGV2ZXJ5IHBvc3NpYmxlIGNvbWJpbmF0aW9uIG9mIHRoZSBwYXJhbWV0ZXJzIGFuZCBhc3NpZ25pbmcgcmVsYXRpdmUgcGxhdXNpYmlsaXRpZXMgdG8gZXZlcnkgY29tYmluYXRpb24sIGNvbmRpdGlvbmFsIG9uIHRoaXMgbW9kZWwgYW5kIHRoZXNlIGRhdGEuIEl0IG1pZ2h0IGhlbHAgdG8gbG9vayBhdCB0aGUgYml2YXJpYXRlIHBvc3RlcmlvIGRpc3RyaWJ1dGlvbiBmb3IgYGJsYCBhbmQgYGJyYDoKCmBgYHtyfQpwb3N0IDwtIGV4dHJhY3Quc2FtcGxlcyhtNS44KQpwbG90KGJsIH4gYnIsIHBvc3QsIGNvbCA9IGNvbC5hbHBoYShyYW5naTIsIDAuMSksIHBjaCA9IDE2KQpgYGAKClNvIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIGZvciB0aGVzZSB0d28gcGFyYW1ldGVycyBpcyB2ZXJ5IGhpZ2hseSBjb3JyZWxhdGVkIC0gd2hlbiBgYnJgIGlzIGxhcmdlLCBgYmxgIGlzIHNtYWxsLiAKCk9uZSB3YXkgdG8gdGhpbmsgYWJvdXQgdGhpcyBwaGVub21lbm9uIGlzIHRoYXQgeW91IGhhdmUgYXBwcm94aW1hdGVkIHRoaXMgbGlrZWxpaG9vZDoKCiQkeV9pIHtcc2ltfSBOb3JtYWwoXG11X2ksIFxzaWdtYSlcXAptX2kgPSBcYWxwaGEgKyBcYmV0YV8xeF9pICsgXGJldGFfMnhfaSQkCgpIZXJlIGlzIGEgc2luZ2xlIHByZWRpY3RvciwgYW5kIGl0J3MgdXNlZCB0d2ljZS4gRnJvbSB0aGUgY29tcHV0ZXIgcGVyc3BlY3RpdmUgdGhpcyBsaWtlbGlob29kIGlzIHJlYWxseTogCgoKJCR5X2kge1xzaW19IE5vcm1hbChcbXVfaSwgXHNpZ21hKVxcCm1faSA9IFxhbHBoYSArIChcYmV0YV8xICsgXGJldGFfMil4X2kkJAoKU28gbmVpdGhlciAkXGJldGFfMSQgbm9yICRcYmV0YV8yJCBpbmZsdWVuY2UgJFxtdSQsIG9ubHkgdGhlaXIgc3VtICRcYmV0YV8xICsgXGJldGFfMiQgaW5mbHVlbmNlcyBpdC4gVGhpcyBtZWFucyB0aGF0IHRoZXJlJ3JlIGluZmluaXRlIGNvbWJpbmF0aW9ucyBvZiAkXGJldGFfMSQgYW5kICRcYmV0YV8yJC4gCgpKdXN0IHRvIGNoZWNrLCBsZXQncyBwbG90IHRoZSBzdW06IAoKYGBge3J9CnN1bV9ibGJyIDwtIHBvc3QkYmwgKyBwb3N0JGJyCmRlbnMoc3VtX2JsYnIsIGNvbCA9IHJhbmdpMiwgbHdkID0gMiwgeGxhYiA9ICJzdW0gb2YgYmwgYW5kIGJyIikKYGBgCgpJZiB5b3UgZml0IGEgcmVncmVzc2lvbiB3aXRoIG9ubHkgb25lIG9mIHRoZSBsZWcgbGVuZ3RoLCB5b3UnbGwgZ2UgYXBwcm94aW1hdGVseSB0aGUgc2FtZSBwb3N0ZXJpb3IgbWVhbjoKCmBgYHtyfQptNS45IDwtIG1hcCgKICBhbGlzdCgKICAgIGhlaWdodCB+IGRub3JtKG11LCBzaWdtYSksCiAgICBtdSA8LSBhICsgYmwgKiBsZWdfbGVmdCwKICAgIGEgfiBkbm9ybSgxMCwgMTAwKSwKICAgIGJsIH4gZG5vcm0oMiwgMTApLAogICAgc2lnbWEgfiBkdW5pZigwLCAxMCkKICApLCBkYXRhID0gZAopCgpwcmVjaXMobTUuOSkKYGBgCgpUaGUgbGVzc29uIGhlcmUgaXMgLSAqd2hlbiB0d28gcHJlZGljdG9yIHZhcmlhYmxlcyBhcmUgdmVyeSBzdHJvbmdseSBjb3JyZWxhdGVkLCBpbmNsdWRpbmcgYm90aCBpbiBhIG1vZGVsIG1heSBsZWFkIHRvIGNvbmZ1c2lvbiouIAoKIyMjIDUuMy4yIE11bHRpY29sbGluZWFyIG1pbGsKCmBgYHtyfQpsaWJyYXJ5KHJldGhpbmtpbmcpCmRhdGEobWlsaykKZCA8LSBtaWxrCmBgYAoKSW4gdGhlc2UgZGF0YSwgd2UgaGF2ZSB2YXJpYWJsZXMgYHBlcmMuZmF0YCBhbmQgYHBlcmMubGFjdG9zZWAgdGhhdCB3ZSBtaWdodCB1c2UgdG8gbW9kZWwgdGhlIHRvdGFsIGVuZXJneSBjb250ZW50LCBga2NhbC5wZXIuZ2AgdG8gZXhwbG9yZSBhIG5hdHVyYWwgY2FzZSBvZiBtdWx0aWNvbGxpbmVhcml0eS4gCgpMZXQncyBzdGFydCBieSBvZGVsaW5nIGBrY2FsLnBlci5nYCBhcyBhIGZ1bmN0aW9uIG9mIGBwZXJjLmZhY3RgIGFuZCBgcGVyYy5sYWN0b3NlYCwgYnV0IGluIHR3byBiaXZhcmlhdGUgcmVncmVzc2lvbnM6CgpgYGB7cn0KbTUuMTAgPC0gbWFwKAogIGFsaXN0KAogICAga2NhbC5wZXIuZyB+IGRub3JtKG11LCBzaWdtYSksCiAgICBtdSA8LSBhICsgYmYgKiBwZXJjLmZhdCwgCiAgICBhIH4gZG5vcm0oMC42LCAxMCksIAogICAgYmYgfiBkbm9ybSgwLCAxKSwKICAgIHNpZ21hIH4gZHVuaWYoMCwgMTApCiAgKSwgZGF0YSA9IGQKKQoKbTUuMTEgPC0gbWFwKAogIGFsaXN0KAogICAga2NhbC5wZXIuZyB+IGRub3JtKG11LCBzaWdtYSksCiAgICBtdSA8LSBhICsgYmwgKiBwZXJjLmxhY3Rvc2UsIAogICAgYSB+IGRub3JtKDAuNiwgMTApLCAKICAgIGJsIH4gZG5vcm0oMCwgMSksCiAgICBzaWdtYSB+IGR1bmlmKDAsIDEwKQogICksIGRhdGEgPSBkCikKCnByZWNpcyhtNS4xMCwgZGlnaXRzID0gMykKcHJlY2lzX3Bsb3QocHJlY2lzKG01LjEwKSkKcHJlY2lzKG01LjExLCBkaWdpdHMgPSAzKQpwcmVjaXNfcGxvdChwcmVjaXMobTUuMTEpKQpgYGAKClRoZSBwb3N0ZXJpb3IgbWVhbnMgYXJlIGVzc2VudGlhbGx5IG1pcnJvciBpbWFnZXMgb2Ygb25lIGFub3RoZXIuCgpMZXQncyBmaXQgYSBtdWx0aXZhcmlhdGUgcmVncmVzc2lvbjogCgpgYGB7cn0KbTUuMTIgPC0gbWFwKAogIGFsaXN0KAogICAga2NhbC5wZXIuZyB+IGRub3JtKG11LCBzaWdtYSksCiAgICBtdSA8LSBhICsgYmwgKiBwZXJjLmxhY3Rvc2UgKyBiZiAqIHBlcmMuZmF0LCAKICAgIGEgfiBkbm9ybSgwLjYsIDEwKSwgCiAgICBibCB+IGRub3JtKDAsIDEpLAogICAgYmYgfiBkbm9ybSgwLCAxKSwKICAgIHNpZ21hIH4gZHVuaWYoMCwgMTApCiAgKSwgZGF0YSA9IGQKKQoKcHJlY2lzKG01LjEyKQpwcmVjaXNfcGxvdChwcmVjaXMobTUuMTIpKQpgYGAKTm93IHRoZSBwb3N0ZXJpb3IgbWVhbnMgZm9yIGJvdGggYGJmYCBhbmQgYGJsYCBhcmUgY2xvc2VyIHRvIHplcm8uIApUaGlzIGhhcHBlbnMgYmVjYXVzZSB0aGUgdmFyaWFibGVzIGBwZXJjLmZhY3RgIGFuZCBgcGVyYy5sYWN0b3NlYCBjb250YWluIG11Y2ggb2YgdGhlIHNhbWUgaW5mb3JtYXRpb24uIEluIHRoZSBjYXNlIG9mIGZhdCBhbmQgbGFjdG9zZSwgdGhlcmUgdHdvIHZhcmlhYmxlcyBmb3JtIGVzc2VudGlhbGx5IGEgc2luZ2xlIGF4aXMgb2YgdGhlIHZhcmlhdGlvbjogCgpgYGB7cn0KcGFpcnMofiBrY2FsLnBlci5nICsgcGVyYy5mYXQgKyBwZXJjLmxhY3Rvc2UsIGRhdGEgPSBkLCBjb2wgPSByYW5naTIpCmBgYAoKVHdvIHZhcmlhYmxlcyBhcmUgbmVnYXRpdmVseSBjb3JyZWxhdGVkLCBhbmQgc28gc3Ryb25nbHkgc28gdGhhdCB0aGV5IGFyZSBuZWFybHkgcmVkdW5kYW50LiBFaXRoZXIgaGVscHMgaW4gcHJlZGljdGluZyBga2NhbC5wZXIuZ2AsIGJ1dCBuZWl0aGVyIGhlbHBzIG11Y2ggKm9uY2UgeW91IGFscmVhZHkga25vdyB0aGUgb3RoZXIqLgoKWW91IGNhbiBjb21wdXRlIHRoZSBjb3JyZWxhdGlvbiBiZXR3ZWVuIHR3byB2YXJpYWJsZXMgd2l0aCBgY29yYDogCgpgYGB7cn0KY29yKGQkcGVyYy5mYXQsIGQkcGVyYy5sYWN0b3NlKQpgYGAKCldoYXQgY2FuIGJlIGRvbmUgYWJvdXQgbXVsdGljb2xsaW5lYXJpdHk/IFRoZSBiZXN0IHRoaW5nIHRvIGRvIGlzIGJlIGF3YXJlIG9mIGl0LiBZb3UgY2FuIGFudGljaXBhdGUgdGhpcyBwcm9ibGVtIGJ5IGNoZWNraW5nIHRoZSBwcmVkaWN0b3IgdmFyaWFibGVzIGFnYWluc3Qgb25lIGFub3RoZXIgaW4gYSBwYWlycyBwbG90LiAKCiMjIyA1LjMuMyBQb3N0LXRyZWF0bWVudCBiaWFzCgpJdCdzIHJvdXRpbmUgdG8gd29ycnkgYWJvdXQgbWlzdGFrZW4gaW5mZXJlbmNlcyB0aGF0IGFyaXNlIGZyb20gb21pdHRpbmcgcHJlZGljdG9yIHZhcmlhYmxlcy4gU3VjaCBtaXN0YWtlcyBhcmUgb2Z0ZW4gY2FsbGVkICoqb21pdHRlZCB2YXJpYWJsZSBiaWFzKiouIApJdCdzIG11Y2ggbGVzcyByb3V0aW5nIHRvIHdvcnJ5IGFib3V0IG1pc3Rha2VuIGluZmVyZW5jZXMgYXJpc2luZyBmcm9tIGluY2x1ZGluZyB2YXJpYWJsZXMgdGhhdCBhcmUgY29uc2VxdWVuY2VzIG9mIG90aGVyIHZhcmlhYmxlcy4gV2UnbGwgY2FsbCB0aGlzICoqcG9zdC10cmVhdG1lbnQgYmlhcyoqLgoKKipQbGFudHMgaW4gYSBncmVlbmhvdXNlIGV4YW1wbGUqKgpEaWZmZXJlbnQgaW4gZ3Jvd3RoIHVuZGVyIGRpZmZlcmVudCBhbnRpZnVuZ2FpbCBzb2lsIHRyZWF0bWVudC4gCipGb3VyIHZhcmlhYmxlcyo6IGluaXRpYWwgaGVpZ2h0LCBmaW5hbCBoZWlnaHQsIHRyZWF0bWVudCwgYW5kIHByZXNlbmNlIG9mIGZ1bmd1cy4gCklmIHlvdXIgZ29hbCBpcyB0byBtYWtlIGEgY2F1c2FsIGluZmVyZW5jZSBhYm91dCB0aGUgdHJlYXRtZW50LCB5b3Ugc2hvdWxkbid0IGluY2x1ZGUgdGhlIHByZXNlbmNlIG9mIGZ1bmd1cywgYmVjYXVzZSBpdCBpcyBhICpwb3N0LXRyZWF0bWVudCogZWZmZWN0LiAKCkxldCdzIHNpbXVsYXRlIHNvbWUgZGF0YTogCgpgYGB7cn0KI251bWJlciBvZiBwbGFudHMKTiA8LSAxMDAKCiNzaW11bGF0ZSBpbml0aWFsIGhlaWdodHMKaDAgPC0gcm5vcm0oTiwgMTAsIDIpCgojYXNzaWduIHRyZWF0bWVudHMgYW5kIHNpbXVsYXRlIGZ1bmd1cyBhbmQgZ3Jvd3RoCnRyZWF0bWVudCA8LSByZXAoMDoxLCBlYWNoID0gTi8yKQpmdW5ndXMgPC0gcmJpbm9tKE4sIHNpemUgPSAxLCBwcm9iID0gMC41IC0gdHJlYXRtZW50ICogMC40KQpoMSA8LSBoMCArIHJub3JtKE4sIDUgLSAzICogZnVuZ3VzKQoKI2NvbXBvc2UgYSBjbGVhbiBkYXRhIGZyYW1lCmQgPC0gZGF0YS5mcmFtZShoMCA9IGgwLCBoMSA9aDEsIHRyZWF0bWVudCA9IHRyZWF0bWVudCwgZnVuZ3VzID0gZnVuZ3VzKQpgYGAKCgpUaGVuIGZpdCBhIG1vZGVsOiAKCmBgYHtyfQptNS4xMyA8LSBtYXAoCiAgYWxpc3QoCiAgICBoMSB+IGRub3JtKG11LCBzaWdtYSksCiAgICBtdSA8LSBhICsgYmggKiBoMCArIGJ0ICogdHJlYXRtZW50ICsgYmYgKiBmdW5ndXMsCiAgICBhIH4gZG5vcm0oMCwgMTAwKSwKICAgIGMoYmgsIGJ0LCBiZikgfiBkbm9ybSgwLCAxMCksCiAgICBzaWdtYSB+IGR1bmlmKDAsIDEwKQogICksIGRhdGEgPSBkCikKCnByZWNpcyhtNS4xMykKcHJlY2lzX3Bsb3QocHJlY2lzKG01LjEzKSkKYGBgCgpUaGUgbWFyZ2luYWwgcG9zdGVyaW9yIGZvciBgYnRgLCB0aGUgZWZmZWN0IG9mIHRyZWF0bWVudCwgaXMgYWN0dWFsbHkgbmVnYXRpdmUgaGVyZSB3aXRoIGxpdHRsZSBlZmZlY3QsIHdoaWxlIG90aGVyIHByZWRpY3RvcnMgaGF2ZSBpbXBvcnRhbnQgZWZmZWN0LiAKVGhlIHByb2JsZW0gaXMgdGhhdCBgZnVuZ3VzYCBpcyBtb3N0bHkgYSBjb25zZXF1ZW5jZSBvZiBgdHJlYXRtZW50YC4gU28gd2hlbiB3ZSBjb250cm9sIGZvciBgZnVuZ3VzYCwgdGhlIG1vZGVsIGlzIGltcGxpY2l0bHkgYW5zd2VyaW5nIHRoZSBxdWVzdGlvbjogKk9uY2Ugd2UgYWxyZWFkeSBrbm93IHdoZXRoZXIgb3Igbm90IGEgcGxhbnQgZGV2ZWxvcGVkIGZ1bmd1cywgZG9lcyBzb2lsIHRyZWF0bWVudCBtYXR0ZXJzPyouIFRoZSBhbnN3ZXIgaXMgJ25vJywgYmVjYXVzZSBzb2lsIHRyZWF0bWVudCBoYXMgaXRzIGVmZmVjdHMgb24gZ3Jvd3RoIHRocm91Z2ggcmVkdWNpbmcgZnVuZ3VzLiAKCldoYXQgd2UgYWN0dWFsbHkgd2FudCB0byBrbm93IGlzIHRoZSBpbXBhY3Qgb2YgdHJlYXRtZW50IG9uIGdyb3d0aC4gCgpgYGB7cn0KbTUuMTQgPC0gbWFwKAogIGFsaXN0KAogICAgaDEgfiBkbm9ybShtdSwgc2lnbWEpLAogICAgbXUgPC0gYSArIGJoICogaDAgKyBidCAqIHRyZWF0bWVudCwKICAgIGEgfiBkbm9ybSgwLCAxMDApLAogICAgYyhiaCwgYnQpIH4gZG5vcm0oMCwgMTApLAogICAgc2lnbWEgfiBkdW5pZigwLCAxMCkKICApLCBkYXRhID0gZAopCgpwcmVjaXMobTUuMTQpCnByZWNpc19wbG90KHByZWNpcyhtNS4xNCkpCmBgYAoKTm93IHRoZSBpbXBhY3Qgb2YgdHJlYXRtZW50IGlzIHN0cm9uZyBhbmQgcG9zaXRpdmUuIAoKIyMgNS40LiBDYXRlZ29yaWNhbCB2YXJpYWJsZXMKCkEgY29tbW9uIHF1ZXN0aW9uIGZvciBzdGF0aXN0aWNhbCBtZXRob2RzIGlzIHRvIHdoYXQgZXh0ZW50IGFuIG91dGNvbWUgY2hhbmdlcyBhc2EgcmVzdWx0IG9mIHByZXNlbmNlIG9yIGFic2VuY2Ugb2YgYSBjYXRlZ29yeS4gCgojIyMgIDUuNC4xLiBCaW5hcnkgY2F0ZWdvcmllcwoKTGV0J3MgcmV0dXJuIHRvIEthbGFoYXJpIGhlaWdodCBkYXRhCgpgYGB7cn0KZGF0YSgiSG93ZWxsMSIpCmQgPC0gSG93ZWxsMQpzdHIoZCkKYGBgCgpUaGUgYG1hbGVgIHZhcmlhYmxlIGlzIG91ciBuZXcgcHJlZGljdG9yLCBhbiBleGFtcGxlIG9mICoqZHVtbXkgdmFyaWFibGUqKi4gCgokJGhfaSB7XHNpbX0gTm9ybWFsKFxtdV9pLCBcc2lnbWEpXFwgClxtdV9pID0gXGFscGhhICsgXGJldGFfbW1faVxcClxhbHBoYSB7XHNpbX0gTm9ybWFsKDE3OCwgMTAwKVxcClxiZXRhX20ge1xzaW19IE5vcm1hbCgwLCAxMClcXApcc2lnbWEge1xzaW19IFVuaWZvcm0oMCwgNTApJCQKCndoZXJlICRtJCBpcyBhIGR1bW15IHZhcmlhYmxlIGluZGljYXRpbmcgYSBtYWxlIGluZGl2aWR1YWwuIFRoZSBwYXJhbWV0ZXIgJFxiZXRhX20kIGluZmx1ZW5jZXMgcHJlZGljdGlvbiBvbmx5IGZvciB0aG9zZSBjYXNlcyB3aGVyZSAkbV9pID0gMSQuCgpMZXQncyBmaXQgaXQ6IAoKYGBge3J9Cm01LjE1IDwtIG1hcCgKICBhbGlzdCgKICAgIGhlaWdodCB+IGRub3JtKG11LCBzaWdtYSksCiAgICBtdSA8LSBhICsgYm0gKiBtYWxlLAogICAgYSB+IGRub3JtKDE3OCwgMTAwKSwKICAgIGJtIH4gZG5vcm0oMCwgMTApLAogICAgc2lnbWEgfiBkdW5pZigwLCA1MCkKICApLCBkYXRhID0gZAopCgpwcmVjaXMobTUuMTUpCnByZWNpc19wbG90KHByZWNpcyhtNS4xNSkpCmBgYApUbyBpbnRlcnByZXQgdGhlc2UgZXN0aW1hdGVzLCB5b3UgaGF2ZSB0byBub3RlIHRoYXQgdGhlIHBhcmFtZXRlciAkXGFscGhhJCBpcyBub3cgdGhlIGF2ZXJhZ2UgaGVpZ2h0IGFtb25nIGZlbWFsZXMuIFRoZSBwYXJhbWV0ZXIgJFxiZXRhX20kIHRoZW4gdGVsbHMgdXMgdGhlIGF2ZXJhZ2UgKmRpZmZlcmVuY2UqIGJldHdlZW4gbWFsZXMgYW5kIGZlbWFsZXMgPSA3LjMgY20uCgpMZXQncyBzYW1wbGUgZnJvbSB0aGUgcG9zdGVyaW9yIHRvIGRlcml2ZSBhIHBlcmNlbnRpbGUgaW52ZXJ2YWwgZm9yIGF2ZXJhZ2UgbWFsZSBoZWlnaHQuIAoKYGBge3J9CnBvc3QgPC0gZXh0cmFjdC5zYW1wbGVzKG01LjE1KQptdS5tYWxlIDwtIHBvc3QkYSArIHBvc3QkYm0KUEkobXUubWFsZSkKYGBgCgojIyMgNS40LjIuIE1hbnkgY2F0ZWdvcmllcwoKV2hlbiB3ZSBoYXZlICprKiBjYXRlZ29yaWVzLCB3ZSBuZWVkICprIC0gMSogZHVtbXkgdmFyaWFibGVzLiAKCkdldCBiYWNrIHRvIHByaW1hdGUgbWlsayBleGFtcGxlIHdpdGggNCB0eXBlcyBvZiBwcmltYXRlczogCgpgYGB7cn0KZGF0YShtaWxrKQpkIDwtIG1pbGsKdW5pcXVlKGQkY2xhZGUpCmBgYAoKTGV0J3MgY3JlYXRlIGR1bW15IHZhcmlhYmxlczogCgpgYGB7cn0KbGlicmFyeShkcGx5cikKCmQgPC0gZCAlPiUgCiAgbXV0YXRlKGNsYWRlLk5XTSA9IGlmX2Vsc2UoY2xhZGUgPT0gIk5ldyBXb3JsZCBNb25rZXkiLCAxLCAwKSwKICAgICAgICAgY2xhZGUuT1dNID0gaWZfZWxzZShjbGFkZSA9PSAiT2xkIFdvcmxkIE1vbmtleSIsIDEsIDApLAogICAgICAgICBjbGFkZS5TID0gaWZfZWxzZShjbGFkZSA9PSAiU3RyZXBzaXJyaGluZSIsIDEsIDApLCAKICAgICAgICAgKQpgYGAKClRoZXJlJ3Mgbm8gbmVlZCB0byBtYWtlIGFub3RoZXIgdmFyaWFibGUgZm9yIGBBcGVgLCBiZWNhdXNlIGl0IHdpbGwgYmUgdGhlIGRlZmF1bHQsICJpbnRlcmNlcHQiIGNhdGVnb3J5LiAKCkxldCdzIHNwZWNpZnkgdGhlIG1vZGVsIGZvciBga2NhbC5wZXIuZ2A6IAoKJCRrX2kge1xzaW19IE5vcm1hbChcbXVfaSwgXHNpZ21hKVxcIApcbXVfaSA9IFxhbHBoYSArIFxiZXRhX3tOV019TldNX2kgKyBcYmV0YV97T1dNfU9XTV9pICsgXGJldGFfU1NfaVxcClxhbHBoYSB7XHNpbX0gTm9ybWFsKDAuNiwgMTApXFwKXGJldGFfe05XTX17XHNpbX0gTm9ybWFsKDAsIDEpXFwKXGJldGFfe09XTX17XHNpbX0gTm9ybWFsKDAsIDEpXFwKXGJldGFfe1N9e1xzaW19IE5vcm1hbCgwLCAxKVxcClxzaWdtYSB7XHNpbX0gVW5pZm9ybSgwLCAxMClcXCQkCgpBIGxpbmVhciBtb2RlbCBsaWtlIHRoaXMgcmVhbGx5IGRlZmluZXMgZm91ciBkaWZmZXJlbnQgbGluZWFyIG1vZGVscywgZWFjaCBjb3JyZXNwb25zaW5nIHRvIGEgZGlmZmVyZW50IGNhdGVnb3J5LiAKYGBge3J9Cm01LjE2IDwtIG1hcCgKICBhbGlzdCgKICAgIGtjYWwucGVyLmcgfiBkbm9ybShtdSwgc2lnbWEpLAogICAgbXUgPC0gYSArIGIuTldNICogY2xhZGUuTldNICsgYi5PV00gKiBjbGFkZS5PV00gKyBiLlMgKiBjbGFkZS5TLAogICAgYSB+IGRub3JtKDAuNiwgMTApLAogICAgYyhiLk5XTSwgYi5PV00sIGIuUykgfiBkbm9ybSgwLCAxKSwKICAgIHNpZ21hIH4gZHVuaWYoMCwgMTApCiAgKSwgZGF0YSA9IGQKKQoKcHJlY2lzKG01LjE2KQpwcmVjaXNfcGxvdChwcmVjaXMobTUuMTYpKQpgYGAKClRvIGdldCBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIGZvciB0aGUgYXZlcmFnZSBtaWxrIGVuZXJneSBpbiBlYWNoIGNhdGVnb3J5LCB5b3UgY2FuIGFnYWluIHVzZSBzYW1wbGVzOiAKCmBgYHtyfQojc2FtcGxlIHBvc3Rlcmlvcgpwb3N0IDwtIGV4dHJhY3Quc2FtcGxlcyhtNS4xNikKCiNjb21wdXRlIGF2ZXJhZ2VzIGZvciBlYWNoIGNhdGVnb3J5Cm11LmFwZSA8LSBwb3N0JGEKbXUuTldNIDwtIHBvc3QkYSArIHBvc3QkYi5OV00KbXUuT1dNIDwtIHBvc3QkYSArIHBvc3QkYi5PV00KbXUuUyA8LSBwb3N0JGEgKyBwb3N0JGIuUwoKI3N1bW1hcml6ZSB1c2luZyBwcmVjaXMKcHJlY2lzKGRhdGEuZnJhbWUobXUuYXBlLCBtdS5OV00sIG11Lk9XTSwgbXUuUykpCmBgYAoKU3VwcG9zZSB3ZSB3YW50IHRvIGtub3cgdGhlIGVzdGltYXRlZCBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIHR3byBtb25rZXkgZ3JvdXBzLiBUaGVuIGp1c3Qgc3VidHJhY3QgdGhlIGVzdGltYXRlZCBtZWFucyB0byBnZXQgYSBkaWZmZXJlbmNlOiAKCmBgYHtyfQpkaWZmLk5XTS5PV00gPC0gbXUuTldNIC0gbXUuT1dNCnF1YW50aWxlKGRpZmYuTldNLk9XTSwgcHJvYnMgPSBjKDAuMDI1LCAwLjUsIDAuOTc1KSkKYGBgCgojIyMgNS40LjMuIEFkZGluZyByZWd1bGFyIHByZWRpY3RvciB2YXJpYWJsZXMgCgpUaGVyZSdzIG5vdCBvYnN0YWNsZSBub3cgaW4gaW5jbHVkaW5nIG90aGVyIHByZWRpY3RvciB2YXJpYWJsZXMsIGxpa2UgYHBlcmMuZmF0YCBvciBgbG9nKG1hc3MpYCB0byB0aGUgbW9kZWwuIAoKJCRcbXVfaSA9IFxhbHBoYSArIFxiZXRhX3tOV019TldNX2kgKyBcYmV0YV97T1dNfU9XTV9pICsgXGJldGFfU1NfaSArIFxiZXRhX0ZGX2kkJAoKd2hlcmUgJEZfaSQgaXMgdGhlIHBlcmNlbnQgZmF0IGZvciB0aGUgaS10aCBjYXNlIGluIHRoZSBkYXRhIGFuZCAkXGJldGFfRiQgaXMgdGhlIHNsb3BlIHRoYXQgbWVhc3VyZSB0aGUgaW5mbHVlbmNlIG9mICRGJCBvbiBwcmVkaWN0aW9ucyBhYm91dCB0aGUgbWVhbiBtaWxrIGVuZXJneS4KCiMjIyA1LjQuNC4gVW5pcXVlIGludGVyY2VwdHMuIAoKQW5vdGhlciB3YXkgdG8gY29uY2VwdHVhbGl6ZSBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgaXMgdG8gY29uc3RydWN0IGEgdmVjdG9yIG9mIGludGVyY2VwdCBwYXJhbWV0ZXJzLCBvbmUgcGFyYW1ldGVyIGZvciBlYWNoIGNhdGVnb3J5LiBUaGVuIHlvdSBjYW4gY3JlYXRlIGFuICoqaW5kZXggdmFyaWFibGUqKiBpbiB5b3VyIGRhdGEgZnJhbWUgdGhhdCBzYXlzIHdoaWNoIHBhcmFtZXRlciBnb2VzIHdpdGggZWFjaCBjYXNlLiAKCmBgYHtyfQooZCRjbGFkZV9pZCA8LSBjb2VyY2VfaW5kZXgoZCRjbGFkZSkpCmBgYAoKVGhpcyB2YXJpYWJsZSBqdXN0IGdpdmVzIHRoZSBudW1iZXIgb2YgdW5pcXVlIGNsYWRlIHZhbHVlLiAKVGhlbiB5b3UgdGVsbCBgbWFwYCB0byBtYWVrIGEgdmVjdG9yIG9mIGludGVyY2VwdHMsIG9uZSBpbnRlcmNlcHQgZm9yIGVhY2ggdW5pcXVlIHZhbHVlcyBpbiBgY2xhZGVfaWRgOiAKCmBgYHtyfQptNS4xNl9hbHQgPC0gbWFwKAogIGFsaXN0KAogICAga2NhbC5wZXIuZyB+IGRub3JtKG11LCBzaWdtYSksCiAgICBtdSA8LSBhW2NsYWRlX2lkXSwKICAgIGFbY2xhZGVfaWRdIH4gZG5vcm0oMC42LCAxMCksCiAgICBzaWdtYSB+IGR1bmlmKDAsIDEwKQogICksIGRhdGEgPSBkCikKCnByZWNpcyhtNS4xNl9hbHQsIGRlcHRoID0gMikKcHJlY2lzX3Bsb3QocHJlY2lzKG01LjE2X2FsdCwgZGVwdGggPSAyKSkKCmBgYAoKTm93IHlvdSBnZXRuIHRoZSBzYW1lIGF2ZXJhZ2VzIGZvciBlYWNoIGBjbGFkZWAgYnV0IHRoaXMgdGltZSBkaXJlY3RseSBmcm9tIHRoZSBmaXQgbW9kZWwuIApZb3UgbmVlZCB0byBhZGQgYGRlcHRoID0gMmAgdG8gYHByZWNpc2AgY2FsbCBpbiBvcmRlciB0byBwcmludCBvdXQgdmVjdG9yIHBhcmFtZXRlcnMgbGlrZSB0aGVzZS4gCgojIyA1LjUuIE9yZGluYXJ5IGxlYXN0IHNxdWFyZXMgYW5kIGxtCgpJZiB5b3Ugb2sgd2l0aCBmbGF0IHByaW9ycy4KCiMjIyA1LjUuMS4gRGVzaWduIGZvcm11bGFzCgokJHlfaSB7XHNpbX0gTm9ybWFsKFxtdV9pLCBcc2lnbWEpXFwKXG11X2kgPSBcYWxwaGEgKyBcYmV0YSB4X2kkJAoKaXMgZXF1aXZhbGVudCB0byBgeSB+IDEgKyB4YC4KCkludGVyY2VwdHMgYXJlIG9wdGlvbmFsCmB5IH4geGAgPSBgeSA9IDEgKyB4YAoKVG8gb21pdCBpbnRlcmNlcHQgYHkgfiAwICsgeGAKCkNhdGVnb3JpY2FsIHZhcmlhYmxlcyBgeSB+IDEgKyBhcy5mYWN0b3IoeClgCgpUcmFuc2Zvcm0gdmFyaWFibGVzCmB5IH4gMSArIHggKyBJKHheMikgKyBJKHheMylgCgojIyMgNS41LjMgQnVpbGRpbmcgbWFwIGZvcm11bGFzIGZyb20gbG0gZm9ybXVsYXMgd2l0aCByZXRoaW5raW5nOjpnbGltbW1lcigpCgpgYGB7cn0KZGF0YShjYXJzKQpnbGltbWVyKGRpc3QgfiBzcGVlZCwgZGF0YSA9IGNhcnMpCmBgYAoK