Checking error assumptions
Constant variance
Let’s begin with the notion of “identically distributed”, which
suggests no change in the variance across the model space. For example,
if our errors are assumed to be normally distributed, such that
\[
\epsilon_i \sim \text{N}(0, \sigma^2) ~ \Rightarrow ~
\boldsymbol{\epsilon} \sim \text{MVN}(\mathbf{0}, \sigma^2 \mathbf{I})
\]
then we expect no difference in \(\sigma^2\) among any of the \(\epsilon_i\).
Residuals versus fitted values
To check this assumption, we can plot our estimates of the residuals
\(e_i = y- \hat{y}\) against our fitted
values \(\hat{y}_i\) and look for any
patterns. Here are three examples of simple linear regression models fit
to to three simulated data sets. The first is linear, but the other two
exhibit some classical problems.
set.seed(514)
## sample size
nn <- 40
## set x & e
xx <- runif(nn, 0, 10)
ee <- rnorm(nn)
## linear model
y1 <- 1 + 0.5 * xx + ee
m1 <- lm(y1 ~ xx)
e1 <- resid(m1)
## log-linear model
y2 <- exp(0.1 + 0.3 * xx + ee)
m2 <- lm(y2 ~ xx)
e2 <- resid(m2)
## quadratic model
y3 <- 0.2 * (xx - 5)^2 - 1 + ee
m3 <- lm(y3 ~ xx)
e3 <- resid(m3)
We can plot the residuals against the fitted value and check for
problems.
## set plot area
par(mfrow = c(1,3),
mai = c(0.9,0.5,0.5,0.2),
omi = c(0, 0, 0, 0),
cex = 0.9)
## plot errors
## well behaved errors (left)
plot(fitted(m1), e1, pch = 16, las = 1, xpd = NA,
cex.lab = 1.5, xlab = "Fitted values", ylab = "Residuals",
main = "No problem")
abline(h = 0, lty ="dashed")
## heteroscedastic errors (middle)
plot(fitted(m2), e2, pch = 16, las = 1,
cex.lab = 1.5, xlab = "Fitted values", ylab = "",
main = "Heteroscedastic")
abline(h = 0, lty ="dashed")
## nonlinear errors (right)
plot(fitted(m3), e3, pch = 16, las = 1,
cex.lab = 1.5, xlab = "Fitted values", ylab = "",
main = "Nonlinear")
abline(h = 0, lty ="dashed")

Levene’s test
We can formally test the assumption of homogeneous variance via
Levene’s Test, which compares the absolute values of the
residuals in \(j\) groups of data to
their group mean, such that
\[
Z_{ij} = \left| y_{ij} - \bar{y}_j \right|.
\]
Levene’s test is a one-way ANOVA of this absolute difference in the
residuals. The statistic for Levene’s Test is
\[
W=\frac{(n-k)}{(k-1)} \cdot \frac{\sum_{j=1}^{k} n_{j} \left( Z_{j} -
\bar{Z} \right)^{2} }{ \sum_{j=1}^{k} \sum_{i=1}^{n_{j} } \left( Z_{i j}
- \bar{Z_{i} } \right)^{2} }
\] where
- \(k\) is the number of different
groups in the test
- \(n_j\) is the number of
observations in the \(j\)th
group
- \(n\) is the total number of
observations
- \(\bar{Z_{i}}\) is the mean of the
\(Z_{ij}\) in group \(j\)
- \(\bar{Z}\) is the overall mean of
all the \(Z_{ij}\)
The test statistic \(W\) is
approximately \(F\)-distributed with
\(k-1\) and \(N-k\) degrees of freedom.
Levene’s test is easy to compute in R. Here is the
test for the “well behaved” residuals from model m1
above.
## split residuals (e1) into 2 groups
yh <- fitted(m1)
g1 <- e1[yh <= median(yh)]
g2 <- e1[yh > median(yh)]
## Levene's test
var.test(g1, g2)
##
## F test to compare two variances
##
## data: g1 and g2
## F = 2.1135, num df = 19, denom df = 19, p-value = 0.1115
## alternative hypothesis: true ratio of variances is not equal to 1
## 95 percent confidence interval:
## 0.8365508 5.3396652
## sample estimates:
## ratio of variances
## 2.113504
You can see there is no justification to reject \(H_0: \text{Var}(group_1) =
\text{Var}(group_2)\) based on the residuals from the well
behaved model.
Repeat the test for a set of residuals with clear heteroscedasticity
as in the e2 set above.
## split residuals (e2) into 2 groups
g1 <- e2[yh <= median(yh)]
g2 <- e2[yh > median(yh)]
## Levene's test
var.test(g1, g2)
##
## F test to compare two variances
##
## data: g1 and g2
## F = 1.656, num df = 19, denom df = 19, p-value = 0.2804
## alternative hypothesis: true ratio of variances is not equal to 1
## 95 percent confidence interval:
## 0.6554471 4.1836891
## sample estimates:
## ratio of variances
## 1.655955
Here we would reject \(H_0\) and
conclude that the variances in the two groups are not equal.
Normality of errors
We seek a method for assessing whether our residuals are indeed
normally distributed. The easiest way is via a so-called \(Q\)-\(Q\)
plot (for quantile-quantile).
Normally distributed errors
As we saw in lecture, here are some quantiles for a “standard” normal
distribution (ie., the mean is 0 and the variance is 1).
## set plot area
par(mai = c(1,1,0.1,0.1),
omi = c(0, 0, 0, 0),
cex = 1.2)
## plot Gaussian pdf
curve(dnorm, -4, 4, las = 1, bty = "n", lwd = 2,
ylab = "Density", xlab = expression(epsilon))
abline(v = qnorm(c(0.5)), lty = "dashed")
abline(v = qnorm(c(0.25, 0.75)), lty = "dashed", col = "purple")
abline(v = qnorm(c(0.1, 0.9)), lty = "dashed", col = "blue")
abline(v = qnorm(c(0.025, 0.975)), lty = "dashed", col = "red")

Heavy-tailed distribution
In contrast, here are the quantiles for a heavy-tailed (leptokurtic)
distribution.
## set plot area
par(mai = c(1,1,0.1,0.1),
omi = c(0, 0, 0, 0),
cex = 1.2)
## plot Gaussian pdf
curve(dnorm, -4, 4, las = 1, bty = "n", lwd = 2, col = "gray",
ylab = "Density", xlab = expression(epsilon))
## plot Cauchy
curve(dcauchy(x, 0, 0.8), -4, 4, las = 1, bty = "n", lwd = 2, add = TRUE,
ylab = "Density", xlab = expression(epsilon))
abline(v = qcauchy(c(0.5)), lty = "dashed")
abline(v = qcauchy(c(0.25, 0.75)), lty = "dashed", col = "purple")
abline(v = qcauchy(c(0.1, 0.9)), lty = "dashed", col = "blue")
abline(v = qcauchy(c(0.025, 0.975)), lty = "dashed", col = "red")

Short-tailed distribution
Here is a short-tailed (platykurtic) distribution. Notice that I made
up a pdf based on a Butterworth
function.
## set plot area
par(mai = c(1,1,0.1,0.1),
omi = c(0, 0, 0, 0),
cex = 1.2)
## Butterworth fx
butter <- function(x, c = 1, n = 4) {
0.4 / (1 + (x / c)^n)
}
ii <- seq(-40,40)/10
ww <- round(butter(ii, 1, 6)*1e4, 0)
vv <- NULL
for(i in 1:length(ww)) {
tmp <- rep(ii[i], ww[i])
vv <- c(vv, tmp)
}
qb <- quantile(vv, c(2.5, 10, 25, 50, 75, 90, 97.5)/100)
## plot Gaussian pdf
curve(dnorm, -4, 4, las = 1, bty = "n", lwd = 2, col = "gray",
ylab = "Density", xlab = expression(epsilon))
## plot Butterworth
curve(butter(x, 1, 4), -4, 4, las = 1, bty = "n", lwd = 2, add = TRUE,
ylab = "Density", xlab = expression(epsilon))
abline(v = qb[4], lty = "dashed")
abline(v = qb[c(3,5)], lty = "dashed", col = "purple")
abline(v = qb[c(2,6)], lty = "dashed", col = "blue")
abline(v = qb[c(1,7)], lty = "dashed", col = "red")

Here is a comparisons of the \(Q\)-\(Q\)
plots for these three examples via qqnorm(x).
## set plot area
par(mfrow = c(1,3),
mai = c(0.9,0.5,0.5,0.2),
omi = c(0, 0, 0, 0),
cex = 0.9)
## Q-Q plots
## normal
z1 <- rnorm(nn)
qqnorm(z1, pch =16, main = "Normal", xpd = NA)
qqline(z1)
## leptokurtic
z2 <- rcauchy(nn)
qqnorm(z2, pch =16, main = "Heavy-tailed")
qqline(z2)
## platykurtic
ii <- sample(seq(-40,40)/10, nn)
z3 <- butter(ii, nn) * ii
qqnorm(z3, pch =16, main = "Light-tailed")
qqline(z3)

Correlated errors
One component of IID errors is “independent”, which means we
expect no correlation among any of the errors. This assumption may be
violated when working with
Temporal data
Spatial data
Blocked data
For example, let’s examine the data on tree rings and climate proxies
in the globwarm dataset from the faraway
package.
Plot tree growth (wusa) versus temperature
(nhtemp).
## get raw data
data(globwarm, package = "faraway")
## trim to recent years
dat <- globwarm[globwarm$year > 1960,]
## set plot area
par(mai = c(1,1,0.1,0.1),
omi = c(0, 0, 0, 0),
cex = 1.2)
## plot regr
plot(dat$nhtemp, dat$wusa, pch = 16, las = 1, xpd = NA,
cex.lab = 1.2, xlab = "Temperature", ylab = "Tree growth", main = "")

Fit a simple regression model where tree growth (wusa)
is a function of temperature (nhtemp).
## fit a model
mm <- lm(wusa ~ nhtemp, dat)
## extract fits
ff <- fitted(mm)
## extract residuals
ee <- resid(mm)
Here is a plot of the residuals versus the fitted values (left) and
the residuals at time \(t\) against
those at time \(t+1\) (right). Notice
the strong correlation between the residuals.
## set plot area
par(mfrow = c(1,2),
mai = c(0.9, 0.9, 0.1, 0.1),
omi = c(0.1, 0.1, 0.4, 0.1),
cex = 1)
## plots
plot(ff, ee, pch = 16, las = 1, xpd = NA,
cex.lab = 1.2, xlab = "Fitted values", ylab = "Residuals", main = "")
abline(h = 0, lty ="dashed")
plot(ee[1:(length(ee)-1)], ee[2:length(ee)],
pch = 16, las = 1, cex.lab = 1.2,
xlab = expression(italic(e[t])),
ylab = expression(italic(e)[italic(t)+1]),
main = "")

We can estimate the autocorrelation function in
R with the acf() function.
## set plot area
par(mai = c(0.9, 0.9, 0.1, 0.1),
omi = c(0.1, 0.1, 0.4, 0))
## plot acf
acf(ee,
ylab = expression(paste("Correlation of ", italic(e[t]), " & ", italic(e[t + h]))),
main = "", cex.lab = 1.3)

This suggests we should instead use a model along the lines of
\[
y_t = \mathbf{X}_t \boldsymbol{\beta} + \epsilon_t \\
\epsilon_t \sim \text{N}(\phi \epsilon_{t-1}, \sigma^2).
\]
We cannot fit this model using the base function lm() in
R, but we can use the gls() function in
the nlme
package.
Specifically, we specify the correlation argument using
the function corAR1(value, form, ...), which fits a
first-order autoregressive model, or AR(1). We can ignore the
value argument because we want to estimate \(\phi\) rather than prescribe it. The
form argument specifies the time covariate (predictor) as a
one-sided formula; here we use year. We also need to
eliminate the NA’s from the data set before passing it to
gls().
## load nlme pkg
require(nlme)
## fit model with AR(1) errors
glmod <- gls(nhtemp ~ wusa,
correlation = corAR1(form = ~ year),
data = na.omit(globwarm))
## examine parameters
summary(glmod)
## Generalized least squares fit by REML
## Model: nhtemp ~ wusa
## Data: na.omit(globwarm)
## AIC BIC logLik
## -134.713 -122.8616 71.3565
##
## Correlation Structure: AR(1)
## Formula: ~year
## Parameter estimate(s):
## Phi
## 0.7460783
##
## Coefficients:
## Value Std.Error t-value p-value
## (Intercept) -0.2034841 0.05807001 -3.504116 0.0006
## wusa 0.1421112 0.05635742 2.521606 0.0128
##
## Correlation:
## (Intr)
## wusa -0.604
##
## Standardized residuals:
## Min Q1 Med Q3 Max
## -2.0957078 -0.5849720 -0.1230105 0.4265090 3.4448501
##
## Residual standard error: 0.2168318
## Degrees of freedom: 145 total; 143 residual
We can see that the AR(1) coefficient \(\phi\) is ~0.75, which is rather high.
We can get the 95% confidence intervals around the regression and
AR(1) parameters with intervals().
intervals(glmod)
## Approximate 95% confidence intervals
##
## Coefficients:
## lower est. upper
## (Intercept) -0.31827062 -0.2034841 -0.08869753
## wusa 0.03070993 0.1421112 0.25351247
##
## Correlation structure:
## lower est. upper
## Phi 0.5970891 0.7460783 0.8453101
##
## Residual standard error:
## lower est. upper
## 0.1705518 0.2168318 0.2756700
Unusual observations
It is often the case that one or more data points do not fit our
model well; we refer to these as outliers. Some outliers affect
the fit of the model and we refer to these as influential
observations. Leverage points, on the other hand, are extreme
in the predictor \((X)\) space and may
or may not affect model fit.
Here are some examples of unusual observations.
## create data
xr <- round(1:10 + rnorm(10, 0, 0.2), 1)
simdata <- data.frame(x = xr,
y = xr + rnorm(10))
mm <- lm(y ~ x, simdata)
## no leverage or influence
p1 <- c(5.5,12)
m1 <- lm(y ~ x, rbind(simdata, p1))
## high leverage but no influence
p2 <- c(17,17)
m2 <- lm(y ~ x, rbind(simdata, p2))
## high leverage and influence
p3 <- c(17,5.1)
m3 <- lm(y ~ x, rbind(simdata, p3))
## set plot area
par(mfrow = c(1,3),
mai = c(0.9, 0.9, 0.6, 0.1),
omi = c(0, 0, 0, 0),
cex = 0.9)
## plot examples
## no leverage or influence (left)
plot(y ~ x, rbind(simdata, p1), pch = 16, las = 1, xpd = NA,
cex.lab = 1.5, xlab = expression(italic(x)), ylab = expression(italic(y)),
main = "No leverage or influence", cex.main = 1)
points(5.5, 12, pch = 16, cex = 1.5, col ="red")
abline(mm)
abline(m1, lty=2, col ="red")
## high leverage but no influence (middle)
plot(y ~ x, rbind(simdata, p2), pch = 16, las = 1,
cex.lab = 1.5, xlab = expression(italic(x)), ylab = expression(italic(y)),
main = "Leverage but no influence", cex.main = 1)
points(17, 17, pch = 16, cex = 1.5, col ="red")
abline(mm)
abline(m2, lty=2, col ="red")
## high leverage and influence (right)
plot(y ~ x, rbind(simdata, p3), pch = 16, las = 1,
cex.lab = 1.5, xlab = expression(italic(x)), ylab = expression(italic(y)),
main = "Leverage and influence", cex.main = 1)
points(17, 5.1, pch = 16, cex = 1.5, col ="red")
abline(mm)
abline(m3, lty=2, col ="red")

Identifying leverage points
Recall that we can use the “hat matrix” \((\mathbf{H})\) to project the \(n\)-dimensional data \(\mathbf{y}\) onto the \(k\)-dimensional model.
As a reminder, for our linear model given by
\[
\mathbf{y} = \mathbf{X} \boldsymbol{\beta} + \boldsymbol{\epsilon} \\
\boldsymbol{\epsilon} \sim \text{MVN}(\mathbf{0}, \sigma^2 \mathbf{I})
\]
we have
\[
\begin{align}
\mathbf{\hat{y}} &= \mathbf{X} \boldsymbol{\hat{\beta}} \\
&= \mathbf{X} \left( (\mathbf{X}^{\top} \mathbf{X})^{-1}
\mathbf{X}^{\top} \mathbf{y} \right) \\
&= \mathbf{X} (\mathbf{X}^{\top} \mathbf{X})^{-1}
\mathbf{X}^{\top} \mathbf{y} \\
&= \mathbf{H} \mathbf{y}
\end{align}
\]
The values along the diagonal of \(\mathbf{H}\) are known as the
leverages (where \(\mathbf{H}_{ii} =
h_i\)). These leverage values give an indication of the influence
of a particular \(x_{ij}\) on the model
fit. The residuals are thus
\[
\begin{aligned}
\boldsymbol{\hat{\epsilon}} &= \mathbf{e} \\
&= \mathbf{y} - \mathbf{\hat{y}} \\
&= \mathbf{y} - \mathbf{H} \mathbf{y} \\
&= \mathbf{y} (\mathbf{I} - \mathbf{H}).
\end{aligned}
\]
From this it follows that
\[
\begin{aligned}
\text{Var}(\boldsymbol{\hat{\epsilon}}) &= \text{Var}(\mathbf{e}) \\
&= \text{Var}(\mathbf{y} (\mathbf{I} - \mathbf{H})) \\
&= (\mathbf{I} - \mathbf{H}) \text{Var}(\mathbf{y} ) (\mathbf{I} -
\mathbf{H})^{\top} \\
&= \sigma^2 (\mathbf{I} - \mathbf{H})^2 \\
&= \sigma^2 (\mathbf{I} - \mathbf{H})
\end{aligned}
\]
and therefore the variance of an individual residual is
\[
\text{Var}(\widehat{\epsilon}_{i}) = \sigma^2 (1 - h_i).
\]
From this relationship we can see that large \(h_i\) lead to small variances of \(\hat{\epsilon}_i\) & hence \(\hat{y}_i\) tends to \(y_i\). The hat matrix \(\mathbf{H}\) has dimensions \(n \times n\) and
\[
\text{trace}(\mathbf{H}) = \sum_{i = 1}^n h_i = k
\]
Thus, on average we should expect that the average leverage value is
\(\bar{h}_i = \frac{k}{n}\). Any \(h_i > 2 \frac{k}{n}\) deserve closer
inspection.
We can easily compute the \(h_i\) in
R via the function hatvalues() as shown
here.
## leverages of points in middle plot above
hv <- hatvalues(m2)
## trace(H) = number of parameters in the model
k <- sum(hv)
## expected value for h_i (~= 0.36)
Eh <- 2 * (k / length(hv))
## are any h_i > Eh?
hv > Eh
## 1 2 3 4 5 6 7 8 9 10 11
## FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE
We can also plot the individual leverage values to see whether they
exceed their expectation, or identify high leverage via a half-normal
plot.
## revised `halfnorm()` from Faraway
## `nlab` gives the number of points to label in the plot
## `labels` can be a character vector the same length as `x`
## that can be used to label the points in the plot
## `ylab` can be used to labeling of the y-axis
halfnorm <- function(x, nlab = 1, labels = NULL, ylab = "Sorted data") {
x <- abs(x)
labord <- order(x)
x <- sort(x)
i <- order(x)
n <- length(x)
ui <- qnorm((n + 1:n)/(2 * n + 1))
if(is.null(labels)) {
labels <- as.character(1:length(x))
}
plot(ui, x[i], pch = 16, las = 1,
xlab = "Half-normal quantiles", ylab = ylab,
ylim = c(0, max(x)), type = "n")
if(nlab < n) {
points(ui[1:(n - nlab)], x[i][1:(n - nlab)], pch = 16)
}
text(x = ui[(n - nlab + 1):n], y = x[i][(n - nlab + 1):n],
labels = labels[labord][(n - nlab + 1):n])
}
## set plot area
par(mfrow = c(1,2),
mai = c(0.9,0.9,0.1,0.3),
omi = c(0.5, 0.4, 0.5, 0),
cex = 1)
## plot of inidivdual leverages (left)
plot(model.matrix(m2)[,2], hv, pch = 16, las = 1,
ylab = "Leverage", xlab = expression(italic(x)))
mtext(expression(italic(h)^{"*"}), 4, line = 0.3, cex = 1.1, at = Eh, las = 1)
abline(h = Eh, lty = "dashed")
## half-normal plot of the leverages (right)
halfnorm(hv)

Identifying outliers
We saw in lecture that we can standardize the model residuals to help
identify outliers. Specifically, we can use the leverages to do so, such
that the studentized residual \(t_i\) is given by
\[
t_i = \frac{y_{i} - \hat{y}_{(i)}}{ \hat{\sigma}_{(i)} \sqrt{ 1 - h_i }
} = e_i \sqrt{ \frac{n - k - 1}{n - k - e_i^2} }
\]
and \(e_i\) is the residual for the
\(i\)th case based on a
model that includes all of the data. This \(t_i\) statistic is distributed as a \(t\)-distribution with \(n - k - 1\) degrees of freedom.
Note, however, that this requires us to undertake \(n\) different null hypothesis tests. Thus,
if we chose a Type-I error rate of \(\alpha\) = 0.05, we should expect that 1 in
20 of these tests would be significant by chance alone. To account for
all of these tests, we can employ a Bonferroni correction,
which instead sets the threshold at \(\alpha_B
= \alpha / n\). This correction factor comes up elsewhere in
statistical testing and is known to be conservative; it finds fewer
outliers than the nominal level of confidence would.
Computing the studentized residuals in R is easy
with the rstudent() function. We can then compare them to
the critical \(t\) value with
qt().
Computing the studentized residuals for case #1 above (left-hand
plot).
## get sample size
n_m1 <- nrow(model.matrix(m1))
## get studentized e
t_stud <- rstudent(m1)
## Bonferroni alpha
alpha <- 0.05 / n_m1
## critical t value
df <- n_m1 - length(coef(m1)) - 1
t_crit <- qt(1 - alpha/2, df)
## compare t_stud to t_crit
t_stud > t_crit
## 1 2 3 4 5 6 7 8 9 10 11
## FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE
We can see that the 11th datum is an outlier (as we
suspected from the above plot).
Identifying influential observations
Influential observations might not be outliers nor have high
leverage, but we want to identify them anyway. We saw in lecture that
Cook’s Distance \((D)\) is a popular
choice, where
\[
D_i = e_i^2 \frac{1}{k} \left( \frac{h_i}{1 - h_i} \right).
\]
The idea here is that \(D_i\)
combines the magnitude of a residual and its leverage. It’s easy to
calculate the \(D_i\) with the
cooks.distance() function. We can then visually inspect
\(D\) with a half-normal plot (we’ll
label the 2 values with the highest \(D\) by setting nlab = 2).
## Cook's D
cook <- cooks.distance(m2)
## half-normal plot
par(mai = c(1,1,0.1,0.1),
omi = c(0, 0, 0, 0),
cex = 1)
halfnorm(cook, nlab = 2, ylab = "Cook’s Distance")

Problems with errors
The models we have been using assume that the errors are independent
and identically distributed (IID). Let’s explore some of the options for
dealing with situations where those assumptions may be violated.
Weighted least squares
In cases where the errors are independent, but not
identically distributed, we can use weighted least squares. Let’s
consider a data set from the famous statistician Francis Galton,
which contains information he collected on the size of pea seeds in
parent plants and their offspring plants, and the frequency of each of
the paired measurements. The data are contained in the accompanying file
galton_peas.csv.
Begin by reading in the data and plotting them.
## read data file
peas <- read.csv("galton_peas.csv")
## set plot area
par(mai = c(1,1,0.1,0.1),
omi = c(0, 0, 0, 0),
cex = 1)
## plot the data
plot(peas$parent, peas$offspring, pch = 16, las = 1,
xlab = "Size of parent seed (mm)", ylab = "Size of offspring seed (mm)")

Each of the \(y_i\) here is actually
a weighted mean of the offspring pea size in each of the parent size
groups, so we should use a weighted regression with \(w_i = 1 / n_i\). This is easy to do with
lm() by passing an additional weights
argument. We’ll also fit a regular unweighted model for comparison.
## fit weighted regression
mpw <- lm(offspring ~ parent, peas, weights = 1/n)
faraway::sumary(mpw)
## Estimate Std. Error t value Pr(>|t|)
## (Intercept) 10.481595 2.817401 3.7203 0.004768
## parent 0.852906 0.040052 21.2951 5.217e-09
##
## n = 11, p = 2, Residual SE = 0.10594, R-Squared = 0.98
## compare to unweighted regression
mp <- lm(offspring ~ parent, peas)
faraway::sumary(mp)
## Estimate Std. Error t value Pr(>|t|)
## (Intercept) 16.042402 3.822194 4.1972 0.002316
## parent 0.765672 0.055744 13.7354 2.418e-07
##
## n = 11, p = 2, Residual SE = 0.55883, R-Squared = 0.95
Our weighted regression has a much lower Residual SE
\((\widehat{\sigma}^2)\) and the
parameter estimates are different as well.
Robust regression
We saw in lecture that we can use robust regression in cases where
the errors follow a non-normal distribution. Recall that the idea is to
replace the squared function in our estimate of \(SSE\) with some other function.
Huber’s method
One of the possibilities is Huber’s method where
\[
SSE = \sum^n_{i = 1} f(z) \\
~ \\
f(z) = \left\{
\begin{matrix}
\frac{z^2}{2} & \text{if} ~ \left| z \right| \leq c \\
c \left| z \right| - \frac{c^2}{2} & \text{otherwise}
\end{matrix}
\right.
\]
and \(c = \widehat{\sigma} \propto
\text{Median}(\left| \widehat{\epsilon} \right|)\).
As an example, let’s return to the plant data from the Galapagos
Archipelago that we used last week in lab.
Begin by fitting a normal regression model and plot the residuals
against the fitted values.
## get the data
library(faraway)
head(gala)
## Species Endemics Area Elevation Nearest Scruz Adjacent
## Baltra 58 23 25.09 346 0.6 0.6 1.84
## Bartolome 31 21 1.24 109 0.6 26.3 572.33
## Caldwell 3 3 0.21 114 2.8 58.7 0.78
## Champion 25 9 0.10 46 1.9 47.4 0.18
## Coamano 2 1 0.05 77 1.9 1.9 903.82
## Daphne.Major 18 11 0.34 119 8.0 8.0 1.84
## fit normal regr model
gm <- lm(Species ~ Area, gala)
## examine fit
sumary(gm)
## Estimate Std. Error t value Pr(>|t|)
## (Intercept) 63.782861 17.524416 3.6397 0.0010943
## Area 0.081963 0.019713 4.1578 0.0002748
##
## n = 30, p = 2, Residual SE = 91.73159, R-Squared = 0.38
## set plot area
par(mai = c(1,1,0.1,0.1),
omi = c(0, 0, 0, 0),
cex = 1)
## plot residuals vs y_hat
plot(fitted(gm), resid(gm), pch = 16, las = 1,
ylab = expression(italic(e)), xlab = expression(hat(italic(y))))

This plot reveals some obvious problems with our model assumptions,
so now let’s fit our robust model. To do so, we can use the
rlm() function in the MASS package,
wherein the default option is to use Huber’s method.
## fit robust regr model
rgm <- MASS::rlm(Species ~ Area, gala)
## examine fit
summary(rgm)
##
## Call: rlm(formula = Species ~ Area, data = gala)
## Residuals:
## Min 1Q Median 3Q Max
## -42.92 -32.87 -10.07 22.40 334.29
##
## Coefficients:
## Value Std. Error t value
## (Intercept) 44.9056 8.8575 5.0698
## Area 0.0717 0.0100 7.1965
##
## Residual standard error: 48.67 on 28 degrees of freedom
Here we see that the parameter estimates have changed somewhat and
the estimate of the residual standard error has decreased substantially.
Let’s go a step further and find out which of the islands had high
influence and hence low weighting.
## extract weights from model fit
wts <- round(rgm$w, 2)
names(wts) <- row.names(gala)
## sort and inspect them
sort(wts)
## SantaCruz SantaMaria SanCristobal SanSalvador Baltra Bartolome
## 0.20 0.29 0.33 0.43 1.00 1.00
## Caldwell Champion Coamano Daphne.Major Daphne.Minor Darwin
## 1.00 1.00 1.00 1.00 1.00 1.00
## Eden Enderby Espanola Fernandina Gardner1 Gardner2
## 1.00 1.00 1.00 1.00 1.00 1.00
## Genovesa Isabela Marchena Onslow Pinta Pinzon
## 1.00 1.00 1.00 1.00 1.00 1.00
## Las.Plazas Rabida SantaFe Seymour Tortuga Wolf
## 1.00 1.00 1.00 1.00 1.00 1.00
Four of the islands have been discounted in the estimation
procedure.
Trimmed least squares
M-estimation will fail if the large errors are numerous and extreme
in value. If this is the case, then we can use least trimmed
squares (LTS) as a resistant regression method that deals well with
this situation. LTS minimizes the sum of squares of the \(q\) smallest residuals, such that
\[
SSE = \sum^n_{i = 1} e^2_{i} ~ \rightarrow ~ SSE_q = \sum^q_{i = 1}
e^2_{(i)}
\]
and \((i)\) indicates the residuals
are sorted in ascending order. The default is \(q = \lfloor n/2 \rfloor + \lfloor (k + 1) / 2
\rfloor\) where \(\lfloor \cdot
\rfloor\) is the floor function, which always rounds a number
down to the nearest integer (type ?floor for help on this
function in R).
We can fit an LTS model with the ltsreg() function in
the MASS package.
Fit an LTS model to the Galapagos plant data and examine the
estimated parameters.
## fit LTS model
ltm <- MASS::ltsreg(Species ~ Area, gala)
## examine fit
coef(ltm)
## (Intercept) Area
## 8.400631 1.616162
This method does not automatically report the uncertainty in the
parameter estimates, but we can use our bootstrapping method to estimate
a confidence interval around them.
## number of boostrap samples
nb <- 1000
## empty matrix for beta estimates
beta_est <- matrix(NA, nb, 2)
## residuals from our model
resids <- residuals(ltm)
## sample many times
for(i in 1:nb) {
## sample w/ replacement from e
e_star <- sample(resids, rep = TRUE)
## calculate y_star
y_star <- predict(ltm) + e_star
## re-estimate model
beta_star <- MASS::ltsreg(y_star ~ Area, gala)
## save estimated betas
beta_est[i,] <- coef(beta_star)
}
## extract 2.5% and 97.5% values (with the median)
CI95 <- apply(beta_est, 2, quantile, c(0.025, 0.5, 0.975))
colnames(CI95) <- c("Intercept", "Area")
t(round(CI95, 2))
## 2.5% 50% 97.5%
## Intercept 3.97 8.44 18.94
## Area 1.60 1.62 1.70
LS0tCnRpdGxlOiAiTW9kZWwgZGlhZ25vc3RpY3MgYW5kPGJyPnByb2JsZW1zIHdpdGggZXJyb3JzIgphdXRob3I6ICJNYXJrIFNjaGV1ZXJlbGwiCmRhdGU6ICIxNyBBcHJpbCAyMDI2IgpvdXRwdXQ6CiAgaHRtbF9kb2N1bWVudDoKICAgIHRoZW1lOiAKICAgICAgYm9vdHN3YXRjaDogam91cm5hbAogICAgICBwcmltYXJ5OiAiIzMyMDA2ZSIKICAgIGhpZ2hsaWdodDogdGV4dG1hdGUKICAgIGNzczogLi4vbGVjdHVyZV9pbnN0LmNzcwogICAgY29kZV9kb3dubG9hZDogdHJ1ZQogICAgY29kZV9mb2xkaW5nOiBzaG93CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgdG9jX2RlcHRoOiA0Ci0tLQoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSwgbWVzc2FnZSA9IEZBTFNFKQpgYGAKCiMgQmFja2dyb3VuZAoKVGhlIG1vZGVscyB3ZSBoYXZlIGJlZW4gZGlzY3Vzc2luZyBpbiBjbGFzcyBhc3N1bWUgdGhhdCB0aGUgZXJyb3JzIGFyZSAqaW5kZXBlbmRlbnQgYW5kIGlkZW50aWNhbGx5IGRpc3RyaWJ1dGVkKiAoSUlEKS4gSW4gdGhpcyBsYWIgd2Ugd2lsbCBleHBsb3JlIHNvbWUgb3B0aW9ucyBmb3IgaWRlbnRpZnlpbmcgcHJvYmxlbXMgd2l0aCBvdXIgZXJyb3JzLCBhbmQgdGFraW5nIGNvcnJlY3RpdmUgYWN0aW9ucyBhZnRlciB3ZSBpZGVudGlmeSB0aGVtLgoKCiMgQ2hlY2tpbmcgZXJyb3IgYXNzdW1wdGlvbnMKCiMjIENvbnN0YW50IHZhcmlhbmNlCgpMZXQncyBiZWdpbiB3aXRoIHRoZSBub3Rpb24gb2YgImlkZW50aWNhbGx5IGRpc3RyaWJ1dGVkIiwgd2hpY2ggc3VnZ2VzdHMgbm8gY2hhbmdlIGluIHRoZSB2YXJpYW5jZSBhY3Jvc3MgdGhlIG1vZGVsIHNwYWNlLiBGb3IgZXhhbXBsZSwgaWYgb3VyIGVycm9ycyBhcmUgYXNzdW1lZCB0byBiZSBub3JtYWxseSBkaXN0cmlidXRlZCwgc3VjaCB0aGF0CgokJApcZXBzaWxvbl9pIFxzaW0gXHRleHR7Tn0oMCwgXHNpZ21hXjIpIH4gXFJpZ2h0YXJyb3cgfiBcYm9sZHN5bWJvbHtcZXBzaWxvbn0gXHNpbSBcdGV4dHtNVk59KFxtYXRoYmZ7MH0sIFxzaWdtYV4yIFxtYXRoYmZ7SX0pCiQkCgp0aGVuIHdlIGV4cGVjdCBubyBkaWZmZXJlbmNlIGluICRcc2lnbWFeMiQgYW1vbmcgYW55IG9mIHRoZSAkXGVwc2lsb25faSQuCgojIyMgUmVzaWR1YWxzIHZlcnN1cyBmaXR0ZWQgdmFsdWVzCgpUbyBjaGVjayB0aGlzIGFzc3VtcHRpb24sIHdlIGNhbiBwbG90IG91ciBlc3RpbWF0ZXMgb2YgdGhlIHJlc2lkdWFscyAkZV9pID0geS0gXGhhdHt5fSQgYWdhaW5zdCBvdXIgZml0dGVkIHZhbHVlcyAkXGhhdHt5fV9pJCBhbmQgbG9vayBmb3IgYW55IHBhdHRlcm5zLiBIZXJlIGFyZSB0aHJlZSBleGFtcGxlcyBvZiBzaW1wbGUgbGluZWFyIHJlZ3Jlc3Npb24gbW9kZWxzIGZpdCB0byB0byB0aHJlZSBzaW11bGF0ZWQgZGF0YSBzZXRzLiBUaGUgZmlyc3QgaXMgbGluZWFyLCBidXQgdGhlIG90aGVyIHR3byBleGhpYml0IHNvbWUgY2xhc3NpY2FsIHByb2JsZW1zLgoKYGBge3IgZml0X25vbmNvbnN0YW50X3ZhcmlhbmNlLCBlY2hvID0gVFJVRX0Kc2V0LnNlZWQoNTE0KQojIyBzYW1wbGUgc2l6ZQpubiA8LSA0MAojIyBzZXQgeCAmIGUKeHggPC0gcnVuaWYobm4sIDAsIDEwKQplZSA8LSBybm9ybShubikKIyMgbGluZWFyIG1vZGVsCnkxIDwtIDEgKyAwLjUgKiB4eCArIGVlCm0xIDwtIGxtKHkxIH4geHgpCmUxIDwtIHJlc2lkKG0xKQojIyBsb2ctbGluZWFyIG1vZGVsCnkyIDwtIGV4cCgwLjEgKyAwLjMgKiB4eCArIGVlKQptMiA8LSBsbSh5MiB+IHh4KQplMiA8LSByZXNpZChtMikKIyMgcXVhZHJhdGljIG1vZGVsCnkzIDwtIDAuMiAqICh4eCAtIDUpXjIgLSAxICsgZWUKbTMgPC0gbG0oeTMgfiB4eCkKZTMgPC0gcmVzaWQobTMpCmBgYAoKOjo6IHRpcAoKV2UgY2FuIHBsb3QgdGhlIHJlc2lkdWFscyBhZ2FpbnN0IHRoZSBmaXR0ZWQgdmFsdWUgYW5kIGNoZWNrIGZvciBwcm9ibGVtcy4KCjo6OgoKYGBge3IgcGxvdF9ub25jb25zdGFudF92YXJpYW5jZSwgZWNobyA9IFRSVUUsIGZpZy53aWR0aCA9IDguNSwgZmlnLmhlaWdodCA9IDQsIGZpZy5hbGlnbj0iY2VudGVyIn0KIyMgc2V0IHBsb3QgYXJlYQpwYXIobWZyb3cgPSBjKDEsMyksCiAgICBtYWkgPSBjKDAuOSwwLjUsMC41LDAuMiksCiAgICBvbWkgPSBjKDAsIDAsIDAsIDApLAogICAgY2V4ID0gMC45KQojIyBwbG90IGVycm9ycwojIyB3ZWxsIGJlaGF2ZWQgZXJyb3JzIChsZWZ0KQpwbG90KGZpdHRlZChtMSksIGUxLCBwY2ggPSAxNiwgbGFzID0gMSwgeHBkID0gTkEsCiAgICAgY2V4LmxhYiA9IDEuNSwgeGxhYiA9ICJGaXR0ZWQgdmFsdWVzIiwgeWxhYiA9ICJSZXNpZHVhbHMiLAogICAgIG1haW4gPSAiTm8gcHJvYmxlbSIpCmFibGluZShoID0gMCwgbHR5ID0iZGFzaGVkIikKIyMgaGV0ZXJvc2NlZGFzdGljIGVycm9ycyAobWlkZGxlKQpwbG90KGZpdHRlZChtMiksIGUyLCBwY2ggPSAxNiwgbGFzID0gMSwKICAgICBjZXgubGFiID0gMS41LCB4bGFiID0gIkZpdHRlZCB2YWx1ZXMiLCB5bGFiID0gIiIsCiAgICAgbWFpbiA9ICJIZXRlcm9zY2VkYXN0aWMiKQphYmxpbmUoaCA9IDAsIGx0eSA9ImRhc2hlZCIpCiMjIG5vbmxpbmVhciBlcnJvcnMgKHJpZ2h0KQpwbG90KGZpdHRlZChtMyksIGUzLCBwY2ggPSAxNiwgbGFzID0gMSwKICAgICBjZXgubGFiID0gMS41LCB4bGFiID0gIkZpdHRlZCB2YWx1ZXMiLCB5bGFiID0gIiIsCiAgICAgbWFpbiA9ICJOb25saW5lYXIiKQphYmxpbmUoaCA9IDAsIGx0eSA9ImRhc2hlZCIpCmBgYAoKCiMjIyBMZXZlbmUncyB0ZXN0CgpXZSBjYW4gZm9ybWFsbHkgdGVzdCB0aGUgYXNzdW1wdGlvbiBvZiBob21vZ2VuZW91cyB2YXJpYW5jZSB2aWEgKkxldmVuZSdzIFRlc3QqLCB3aGljaCBjb21wYXJlcyB0aGUgYWJzb2x1dGUgdmFsdWVzIG9mIHRoZSByZXNpZHVhbHMgaW4gJGokIGdyb3VwcyBvZiBkYXRhIHRvIHRoZWlyIGdyb3VwIG1lYW4sIHN1Y2ggdGhhdAoKJCQKWl97aWp9ID0gXGxlZnR8IHlfe2lqfSAtIFxiYXJ7eX1faiBccmlnaHR8LgokJAoKTGV2ZW5lJ3MgdGVzdCBpcyBhIG9uZS13YXkgQU5PVkEgb2YgdGhpcyBhYnNvbHV0ZSBkaWZmZXJlbmNlIGluIHRoZSByZXNpZHVhbHMuIFRoZSBzdGF0aXN0aWMgZm9yICpMZXZlbmUncyBUZXN0KiBpcwoKJCQKVz1cZnJhY3sobi1rKX17KGstMSl9IFxjZG90IFxmcmFje1xzdW1fe2o9MX1ee2t9IG5fe2p9IFxsZWZ0KCBaX3tqfSAtIFxiYXJ7Wn0gXHJpZ2h0KV57Mn0gfXsgXHN1bV97aj0xfV57a30gXHN1bV97aT0xfV57bl97an0gfSBcbGVmdCggWl97aSBqfSAtIFxiYXJ7Wl97aX0gfSBccmlnaHQpXnsyfSB9CiQkCndoZXJlCgoqICRrJCBpcyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBncm91cHMgaW4gdGhlIHRlc3QKKiAkbl9qJCBpcyB0aGUgbnVtYmVyIG9mIG9ic2VydmF0aW9ucyBpbiB0aGUgJGokPHN1cD50aDwvc3VwPiBncm91cAoqICRuJCBpcyB0aGUgdG90YWwgbnVtYmVyIG9mIG9ic2VydmF0aW9ucwoqICRcYmFye1pfe2l9fSQgaXMgdGhlIG1lYW4gb2YgdGhlICRaX3tpan0kIGluIGdyb3VwICRqJAoqICRcYmFye1p9JCBpcyB0aGUgb3ZlcmFsbCBtZWFuIG9mIGFsbCB0aGUgJFpfe2lqfSQKClRoZSB0ZXN0IHN0YXRpc3RpYyAkVyQgaXMgYXBwcm94aW1hdGVseSAkRiQtZGlzdHJpYnV0ZWQgd2l0aCAkay0xJCBhbmQgJE4tayQgZGVncmVlcyBvZiBmcmVlZG9tLiAKCjo6OiB0aXAKCkxldmVuZSdzIHRlc3QgaXMgZWFzeSB0byBjb21wdXRlIGluICoqUioqLiBIZXJlIGlzIHRoZSB0ZXN0IGZvciB0aGUgIndlbGwgYmVoYXZlZCIgcmVzaWR1YWxzIGZyb20gbW9kZWwgYG0xYCBhYm92ZS4KCjo6OgoKYGBge3IgbGV2ZW5lX2dvb2QsIGVjaG8gPSBUUlVFfQojIyBzcGxpdCByZXNpZHVhbHMgKGUxKSBpbnRvIDIgZ3JvdXBzCnloIDwtIGZpdHRlZChtMSkKZzEgPC0gZTFbeWggPD0gbWVkaWFuKHloKV0KZzIgPC0gZTFbeWggPiBtZWRpYW4oeWgpXQojIyBMZXZlbmUncyB0ZXN0CnZhci50ZXN0KGcxLCBnMikKYGBgCgpZb3UgY2FuIHNlZSB0aGVyZSBpcyBubyBqdXN0aWZpY2F0aW9uIHRvIHJlamVjdCAkSF8wOiBcdGV4dHtWYXJ9KGdyb3VwXzEpID0gXHRleHR7VmFyfShncm91cF8yKSQgYmFzZWQgb24gdGhlIHJlc2lkdWFscyBmcm9tIHRoZSB3ZWxsIGJlaGF2ZWQgbW9kZWwuCgo6OjogdGFzawoKUmVwZWF0IHRoZSB0ZXN0IGZvciBhIHNldCBvZiByZXNpZHVhbHMgd2l0aCBjbGVhciBoZXRlcm9zY2VkYXN0aWNpdHkgYXMgaW4gdGhlIGBlMmAgc2V0IGFib3ZlLgoKOjo6CgpgYGB7ciBsZXZlbmVfYmFkLCBlY2hvID0gVFJVRX0KIyMgc3BsaXQgcmVzaWR1YWxzIChlMikgaW50byAyIGdyb3VwcwpnMSA8LSBlMlt5aCA8PSBtZWRpYW4oeWgpXQpnMiA8LSBlMlt5aCA+IG1lZGlhbih5aCldCiMjIExldmVuZSdzIHRlc3QKdmFyLnRlc3QoZzEsIGcyKQpgYGAKCjo6OiBub3RlCgpIZXJlIHdlIHdvdWxkIHJlamVjdCAkSF8wJCBhbmQgY29uY2x1ZGUgdGhhdCB0aGUgdmFyaWFuY2VzIGluIHRoZSB0d28gZ3JvdXBzIGFyZSBub3QgZXF1YWwuCgo6OjoKCiMjIE5vcm1hbGl0eSBvZiBlcnJvcnMKCldlIHNlZWsgYSBtZXRob2QgZm9yIGFzc2Vzc2luZyB3aGV0aGVyIG91ciByZXNpZHVhbHMgYXJlIGluZGVlZCBub3JtYWxseSBkaXN0cmlidXRlZC4gVGhlIGVhc2llc3Qgd2F5IGlzIHZpYSBhIHNvLWNhbGxlZCAkUSQtJFEkIHBsb3QgKGZvciBxdWFudGlsZS1xdWFudGlsZSkuIAoKIyMjIE5vcm1hbGx5IGRpc3RyaWJ1dGVkIGVycm9ycwoKQXMgd2Ugc2F3IGluIGxlY3R1cmUsIGhlcmUgYXJlIHNvbWUgcXVhbnRpbGVzIGZvciBhICJzdGFuZGFyZCIgbm9ybWFsIGRpc3RyaWJ1dGlvbiAoaWUuLCB0aGUgbWVhbiBpcyAwIGFuZCB0aGUgdmFyaWFuY2UgaXMgMSkuCgpgYGB7ciBRUV90aGVvcnksIGVjaG8gPSBUUlVFLCBmaWcud2lkdGggPSA2LCBmaWcuaGVpZ2h0ID0gNSwgZmlnLmFsaWduPSJjZW50ZXIifQojIyBzZXQgcGxvdCBhcmVhCnBhcihtYWkgPSBjKDEsMSwwLjEsMC4xKSwKICAgIG9taSA9IGMoMCwgMCwgMCwgMCksCiAgICBjZXggPSAxLjIpCgojIyBwbG90IEdhdXNzaWFuIHBkZgpjdXJ2ZShkbm9ybSwgLTQsIDQsIGxhcyA9IDEsIGJ0eSA9ICJuIiwgbHdkID0gMiwKICAgICAgeWxhYiA9ICJEZW5zaXR5IiwgeGxhYiA9IGV4cHJlc3Npb24oZXBzaWxvbikpCmFibGluZSh2ID0gcW5vcm0oYygwLjUpKSwgbHR5ID0gImRhc2hlZCIpCmFibGluZSh2ID0gcW5vcm0oYygwLjI1LCAwLjc1KSksIGx0eSA9ICJkYXNoZWQiLCBjb2wgPSAicHVycGxlIikKYWJsaW5lKHYgPSBxbm9ybShjKDAuMSwgMC45KSksIGx0eSA9ICJkYXNoZWQiLCBjb2wgPSAiYmx1ZSIpCmFibGluZSh2ID0gcW5vcm0oYygwLjAyNSwgMC45NzUpKSwgbHR5ID0gImRhc2hlZCIsIGNvbCA9ICJyZWQiKQpgYGAKCiMjIyBIZWF2eS10YWlsZWQgZGlzdHJpYnV0aW9uCgpJbiBjb250cmFzdCwgaGVyZSBhcmUgdGhlIHF1YW50aWxlcyBmb3IgYSBoZWF2eS10YWlsZWQgKGxlcHRva3VydGljKSBkaXN0cmlidXRpb24uCgpgYGB7ciBRUV90aGVvcnlfbGVwdG8sIGVjaG8gPSBUUlVFLCBmaWcud2lkdGggPSA2LCBmaWcuaGVpZ2h0ID0gNSwgZmlnLmFsaWduPSJjZW50ZXIifQojIyBzZXQgcGxvdCBhcmVhCnBhcihtYWkgPSBjKDEsMSwwLjEsMC4xKSwKICAgIG9taSA9IGMoMCwgMCwgMCwgMCksCiAgICBjZXggPSAxLjIpCgojIyBwbG90IEdhdXNzaWFuIHBkZgpjdXJ2ZShkbm9ybSwgLTQsIDQsIGxhcyA9IDEsIGJ0eSA9ICJuIiwgbHdkID0gMiwgY29sID0gImdyYXkiLAogICAgICB5bGFiID0gIkRlbnNpdHkiLCB4bGFiID0gZXhwcmVzc2lvbihlcHNpbG9uKSkKIyMgcGxvdCBDYXVjaHkKY3VydmUoZGNhdWNoeSh4LCAwLCAwLjgpLCAtNCwgNCwgbGFzID0gMSwgYnR5ID0gIm4iLCBsd2QgPSAyLCBhZGQgPSBUUlVFLAogICAgICB5bGFiID0gIkRlbnNpdHkiLCB4bGFiID0gZXhwcmVzc2lvbihlcHNpbG9uKSkKYWJsaW5lKHYgPSBxY2F1Y2h5KGMoMC41KSksIGx0eSA9ICJkYXNoZWQiKQphYmxpbmUodiA9IHFjYXVjaHkoYygwLjI1LCAwLjc1KSksIGx0eSA9ICJkYXNoZWQiLCBjb2wgPSAicHVycGxlIikKYWJsaW5lKHYgPSBxY2F1Y2h5KGMoMC4xLCAwLjkpKSwgbHR5ID0gImRhc2hlZCIsIGNvbCA9ICJibHVlIikKYWJsaW5lKHYgPSBxY2F1Y2h5KGMoMC4wMjUsIDAuOTc1KSksIGx0eSA9ICJkYXNoZWQiLCBjb2wgPSAicmVkIikKYGBgCgojIyMgU2hvcnQtdGFpbGVkIGRpc3RyaWJ1dGlvbgoKSGVyZSBpcyBhIHNob3J0LXRhaWxlZCAocGxhdHlrdXJ0aWMpIGRpc3RyaWJ1dGlvbi4gTm90aWNlIHRoYXQgSSBtYWRlIHVwIGEgcGRmIGJhc2VkIG9uIGEgW0J1dHRlcndvcnRoIGZ1bmN0aW9uXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9CdXR0ZXJ3b3J0aF9maWx0ZXIpLgoKYGBge3IgUVFfdGhlb3J5X3BsYXR5LCBlY2hvID0gVFJVRSwgZmlnLndpZHRoID0gNiwgZmlnLmhlaWdodCA9IDUsIGZpZy5hbGlnbj0iY2VudGVyIn0KIyMgc2V0IHBsb3QgYXJlYQpwYXIobWFpID0gYygxLDEsMC4xLDAuMSksCiAgICBvbWkgPSBjKDAsIDAsIDAsIDApLAogICAgY2V4ID0gMS4yKQoKIyMgQnV0dGVyd29ydGggZngKYnV0dGVyIDwtIGZ1bmN0aW9uKHgsIGMgPSAxLCBuID0gNCkgewogIDAuNCAvICgxICsgKHggLyBjKV5uKQp9CmlpIDwtIHNlcSgtNDAsNDApLzEwCnd3IDwtIHJvdW5kKGJ1dHRlcihpaSwgMSwgNikqMWU0LCAwKQp2diA8LSBOVUxMCmZvcihpIGluIDE6bGVuZ3RoKHd3KSkgewogIHRtcCA8LSByZXAoaWlbaV0sIHd3W2ldKQogIHZ2IDwtIGModnYsIHRtcCkKfQpxYiA8LSBxdWFudGlsZSh2diwgYygyLjUsIDEwLCAyNSwgNTAsIDc1LCA5MCwgOTcuNSkvMTAwKQojIyBwbG90IEdhdXNzaWFuIHBkZgpjdXJ2ZShkbm9ybSwgLTQsIDQsIGxhcyA9IDEsIGJ0eSA9ICJuIiwgbHdkID0gMiwgY29sID0gImdyYXkiLAogICAgICB5bGFiID0gIkRlbnNpdHkiLCB4bGFiID0gZXhwcmVzc2lvbihlcHNpbG9uKSkKIyMgcGxvdCBCdXR0ZXJ3b3J0aApjdXJ2ZShidXR0ZXIoeCwgMSwgNCksIC00LCA0LCBsYXMgPSAxLCBidHkgPSAibiIsIGx3ZCA9IDIsIGFkZCA9IFRSVUUsCiAgICAgIHlsYWIgPSAiRGVuc2l0eSIsIHhsYWIgPSBleHByZXNzaW9uKGVwc2lsb24pKQphYmxpbmUodiA9IHFiWzRdLCBsdHkgPSAiZGFzaGVkIikKYWJsaW5lKHYgPSBxYltjKDMsNSldLCBsdHkgPSAiZGFzaGVkIiwgY29sID0gInB1cnBsZSIpCmFibGluZSh2ID0gcWJbYygyLDYpXSwgbHR5ID0gImRhc2hlZCIsIGNvbCA9ICJibHVlIikKYWJsaW5lKHYgPSBxYltjKDEsNyldLCBsdHkgPSAiZGFzaGVkIiwgY29sID0gInJlZCIpCmBgYAoKOjo6IHRpcAoKSGVyZSBpcyBhIGNvbXBhcmlzb25zIG9mIHRoZSAkUSQtJFEkIHBsb3RzIGZvciB0aGVzZSB0aHJlZSBleGFtcGxlcyB2aWEgYHFxbm9ybSh4KWAuCgo6OjoKCmBgYHtyIHFxX3Bsb3RzLCBlY2hvID0gVFJVRSwgZmlnLndpZHRoID0gOC41LCBmaWcuaGVpZ2h0ID0gNCwgZmlnLmFsaWduPSJjZW50ZXIifQojIyBzZXQgcGxvdCBhcmVhCnBhcihtZnJvdyA9IGMoMSwzKSwKICAgIG1haSA9IGMoMC45LDAuNSwwLjUsMC4yKSwKICAgIG9taSA9IGMoMCwgMCwgMCwgMCksCiAgICBjZXggPSAwLjkpCiMjIFEtUSBwbG90cwojIyBub3JtYWwKejEgPC0gcm5vcm0obm4pCnFxbm9ybSh6MSwgcGNoID0xNiwgbWFpbiA9ICJOb3JtYWwiLCB4cGQgPSBOQSkKcXFsaW5lKHoxKQojIyBsZXB0b2t1cnRpYwp6MiA8LSByY2F1Y2h5KG5uKQpxcW5vcm0oejIsIHBjaCA9MTYsIG1haW4gPSAiSGVhdnktdGFpbGVkIikKcXFsaW5lKHoyKQojIyBwbGF0eWt1cnRpYwppaSA8LSBzYW1wbGUoc2VxKC00MCw0MCkvMTAsIG5uKQp6MyA8LSBidXR0ZXIoaWksIG5uKSAqIGlpCnFxbm9ybSh6MywgcGNoID0xNiwgbWFpbiA9ICJMaWdodC10YWlsZWQiKQpxcWxpbmUoejMpCmBgYAoKPGJyPgoKIyMgQ29ycmVsYXRlZCBlcnJvcnMKCk9uZSBjb21wb25lbnQgb2YgKklJRCogZXJyb3JzIGlzICJpbmRlcGVuZGVudCIsIHdoaWNoIG1lYW5zIHdlIGV4cGVjdCBubyBjb3JyZWxhdGlvbiBhbW9uZyBhbnkgb2YgdGhlIGVycm9ycy4gVGhpcyBhc3N1bXB0aW9uIG1heSBiZSB2aW9sYXRlZCB3aGVuIHdvcmtpbmcgd2l0aAoKKiBUZW1wb3JhbCBkYXRhCgoqIFNwYXRpYWwgZGF0YQoKKiBCbG9ja2VkIGRhdGEKCkZvciBleGFtcGxlLCBsZXQncyBleGFtaW5lIHRoZSBkYXRhIG9uIHRyZWUgcmluZ3MgYW5kIGNsaW1hdGUgcHJveGllcyBpbiB0aGUgYGdsb2J3YXJtYCBkYXRhc2V0IGZyb20gdGhlICoqZmFyYXdheSoqIHBhY2thZ2UuIAoKOjo6IHRhc2sKClBsb3QgdHJlZSBncm93dGggKGB3dXNhYCkgdmVyc3VzIHRlbXBlcmF0dXJlIChgbmh0ZW1wYCkuIAoKOjo6CgpgYGB7ciB0cmVlX3JpbmdzLCBlY2hvID0gVFJVRSwgZmlnLndpZHRoID0gNiwgZmlnLmhlaWdodCA9IDYsIGZpZy5hbGlnbj0iY2VudGVyIn0KIyMgZ2V0IHJhdyBkYXRhCmRhdGEoZ2xvYndhcm0sIHBhY2thZ2UgPSAiZmFyYXdheSIpCiMjIHRyaW0gdG8gcmVjZW50IHllYXJzCmRhdCA8LSBnbG9id2FybVtnbG9id2FybSR5ZWFyID4gMTk2MCxdCgojIyBzZXQgcGxvdCBhcmVhCnBhcihtYWkgPSBjKDEsMSwwLjEsMC4xKSwKICAgIG9taSA9IGMoMCwgMCwgMCwgMCksCiAgICBjZXggPSAxLjIpCgojIyBwbG90IHJlZ3IKcGxvdChkYXQkbmh0ZW1wLCBkYXQkd3VzYSwgcGNoID0gMTYsIGxhcyA9IDEsIHhwZCA9IE5BLAogICAgIGNleC5sYWIgPSAxLjIsIHhsYWIgPSAiVGVtcGVyYXR1cmUiLCB5bGFiID0gIlRyZWUgZ3Jvd3RoIiwgbWFpbiA9ICIiKQpgYGAKCjxicj4KCjo6OiB0YXNrCgpGaXQgYSBzaW1wbGUgcmVncmVzc2lvbiBtb2RlbCB3aGVyZSB0cmVlIGdyb3d0aCAoYHd1c2FgKSBpcyBhIGZ1bmN0aW9uIG9mIHRlbXBlcmF0dXJlIChgbmh0ZW1wYCkuCgo6OjoKCmBgYHtyIGZpdF90cmVlX3JpbmdzfQojIyBmaXQgYSBtb2RlbAptbSA8LSBsbSh3dXNhIH4gbmh0ZW1wLCBkYXQpCiMjIGV4dHJhY3QgZml0cwpmZiA8LSBmaXR0ZWQobW0pCiMjIGV4dHJhY3QgcmVzaWR1YWxzCmVlIDwtIHJlc2lkKG1tKQpgYGAKCjo6OiB0aXAKCkhlcmUgaXMgYSBwbG90IG9mIHRoZSByZXNpZHVhbHMgdmVyc3VzIHRoZSBmaXR0ZWQgdmFsdWVzIChsZWZ0KSBhbmQgdGhlIHJlc2lkdWFscyBhdCB0aW1lICR0JCBhZ2FpbnN0IHRob3NlIGF0IHRpbWUgJHQrMSQgKHJpZ2h0KS4gTm90aWNlIHRoZSBzdHJvbmcgY29ycmVsYXRpb24gYmV0d2VlbiB0aGUgcmVzaWR1YWxzLgoKOjo6CgpgYGB7ciB0cmVlX3JpbmdzX2VlLCBlY2hvID0gVFJVRSwgZmlnLndpZHRoID0gNywgZmlnLmhlaWdodCA9IDQsIGZpZy5hbGlnbj0iY2VudGVyIn0KIyMgc2V0IHBsb3QgYXJlYQpwYXIobWZyb3cgPSBjKDEsMiksCiAgICBtYWkgPSBjKDAuOSwgMC45LCAwLjEsIDAuMSksCiAgICBvbWkgPSBjKDAuMSwgMC4xLCAwLjQsIDAuMSksCiAgICBjZXggPSAxKQojIyBwbG90cwpwbG90KGZmLCBlZSwgcGNoID0gMTYsIGxhcyA9IDEsIHhwZCA9IE5BLAogICAgIGNleC5sYWIgPSAxLjIsIHhsYWIgPSAiRml0dGVkIHZhbHVlcyIsIHlsYWIgPSAiUmVzaWR1YWxzIiwgbWFpbiA9ICIiKQphYmxpbmUoaCA9IDAsIGx0eSA9ImRhc2hlZCIpCnBsb3QoZWVbMToobGVuZ3RoKGVlKS0xKV0sIGVlWzI6bGVuZ3RoKGVlKV0sIAogICAgIHBjaCA9IDE2LCBsYXMgPSAxLCBjZXgubGFiID0gMS4yLCAKICAgICB4bGFiID0gZXhwcmVzc2lvbihpdGFsaWMoZVt0XSkpLCAKICAgICB5bGFiID0gZXhwcmVzc2lvbihpdGFsaWMoZSlbaXRhbGljKHQpKzFdKSwKICAgICBtYWluID0gIiIpCmBgYAoKOjo6IHRpcAoKV2UgY2FuIGVzdGltYXRlIHRoZSAqYXV0b2NvcnJlbGF0aW9uIGZ1bmN0aW9uKiBpbiAqKlIqKiB3aXRoIHRoZSBgYWNmKClgIGZ1bmN0aW9uLgoKOjo6CgpgYGB7ciB0cmVlX3JpbmdzX2FjZiwgZWNobyA9IFRSVUUsIGZpZy53aWR0aCA9IDYsIGZpZy5oZWlnaHQgPSA1LCBmaWcuYWxpZ249ImNlbnRlciJ9CiMjIHNldCBwbG90IGFyZWEKcGFyKG1haSA9IGMoMC45LCAwLjksIDAuMSwgMC4xKSwKICAgIG9taSA9IGMoMC4xLCAwLjEsIDAuNCwgMCkpCiMjIHBsb3QgYWNmCmFjZihlZSwKICAgIHlsYWIgPSBleHByZXNzaW9uKHBhc3RlKCJDb3JyZWxhdGlvbiBvZiAiLCBpdGFsaWMoZVt0XSksICIgJiAiLCBpdGFsaWMoZVt0ICsgaF0pKSksCiAgICBtYWluID0gIiIsIGNleC5sYWIgPSAxLjMpCmBgYAoKPGJyPgoKOjo6IHRpcAoKVGhpcyBzdWdnZXN0cyB3ZSBzaG91bGQgaW5zdGVhZCB1c2UgYSBtb2RlbCBhbG9uZyB0aGUgbGluZXMgb2YKCiQkCnlfdCA9IFxtYXRoYmZ7WH1fdCBcYm9sZHN5bWJvbHtcYmV0YX0gKyBcZXBzaWxvbl90ICBcXApcZXBzaWxvbl90IFxzaW0gXHRleHR7Tn0oXHBoaSBcZXBzaWxvbl97dC0xfSwgXHNpZ21hXjIpLgokJAoKOjo6Cgo6Ojogbm90ZQoKV2UgY2Fubm90IGZpdCB0aGlzIG1vZGVsIHVzaW5nIHRoZSBiYXNlIGZ1bmN0aW9uIGBsbSgpYCBpbiAqKlIqKiwgYnV0IHdlIGNhbiB1c2UgdGhlIGBnbHMoKWAgZnVuY3Rpb24gaW4gdGhlIFsqKm5sbWUqKiBwYWNrYWdlXShodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvbmxtZS9pbmRleC5odG1sKS4KCjo6OgoKU3BlY2lmaWNhbGx5LCB3ZSBzcGVjaWZ5IHRoZSBgY29ycmVsYXRpb25gIGFyZ3VtZW50IHVzaW5nIHRoZSBmdW5jdGlvbiBgY29yQVIxKHZhbHVlLCBmb3JtLCAuLi4pYCwgd2hpY2ggZml0cyBhIGZpcnN0LW9yZGVyIGF1dG9yZWdyZXNzaXZlIG1vZGVsLCBvciBBUigxKS4gV2UgY2FuIGlnbm9yZSB0aGUgYHZhbHVlYCBhcmd1bWVudCBiZWNhdXNlIHdlIHdhbnQgdG8gZXN0aW1hdGUgJFxwaGkkIHJhdGhlciB0aGFuIHByZXNjcmliZSBpdC4gVGhlIGBmb3JtYCBhcmd1bWVudCBzcGVjaWZpZXMgdGhlIHRpbWUgY292YXJpYXRlIChwcmVkaWN0b3IpIGFzIGEgb25lLXNpZGVkIGZvcm11bGE7IGhlcmUgd2UgdXNlIGB5ZWFyYC4gV2UgYWxzbyBuZWVkIHRvIGVsaW1pbmF0ZSB0aGUgYE5BYCdzIGZyb20gdGhlIGRhdGEgc2V0IGJlZm9yZSBwYXNzaW5nIGl0IHRvIGBnbHMoKWAuCgpgYGB7ciBmaXRfZ2xzfQojIyBsb2FkIG5sbWUgcGtnCnJlcXVpcmUobmxtZSkKIyMgZml0IG1vZGVsIHdpdGggQVIoMSkgZXJyb3JzCmdsbW9kIDwtIGdscyhuaHRlbXAgfiB3dXNhLAogICAgICAgICAgICAgY29ycmVsYXRpb24gPSBjb3JBUjEoZm9ybSA9IH4geWVhciksCiAgICAgICAgICAgICBkYXRhID0gbmEub21pdChnbG9id2FybSkpCiMjIGV4YW1pbmUgcGFyYW1ldGVycwpzdW1tYXJ5KGdsbW9kKQpgYGAKCjo6OiBub3RlCgpXZSBjYW4gc2VlIHRoYXQgdGhlIEFSKDEpIGNvZWZmaWNpZW50ICRccGhpJCBpcyB+MC43NSwgd2hpY2ggaXMgcmF0aGVyIGhpZ2guIAoKOjo6Cgo6OjogdGlwCgpXZSBjYW4gZ2V0IHRoZSA5NSUgY29uZmlkZW5jZSBpbnRlcnZhbHMgYXJvdW5kIHRoZSByZWdyZXNzaW9uIGFuZCBBUigxKSBwYXJhbWV0ZXJzIHdpdGggYGludGVydmFscygpYC4KCjo6OgoKYGBge3IgY29uZmludF9BUjF9CmludGVydmFscyhnbG1vZCkKYGBgCgojIFVudXN1YWwgb2JzZXJ2YXRpb25zCgpJdCBpcyBvZnRlbiB0aGUgY2FzZSB0aGF0IG9uZSBvciBtb3JlIGRhdGEgcG9pbnRzIGRvIG5vdCBmaXQgb3VyIG1vZGVsIHdlbGw7IHdlIHJlZmVyIHRvIHRoZXNlIGFzICpvdXRsaWVycyouIFNvbWUgb3V0bGllcnMgYWZmZWN0IHRoZSBmaXQgb2YgdGhlIG1vZGVsIGFuZCB3ZSByZWZlciB0byB0aGVzZSBhcyAqaW5mbHVlbnRpYWwqIG9ic2VydmF0aW9ucy4gKkxldmVyYWdlIHBvaW50cyosIG9uIHRoZSBvdGhlciBoYW5kLCBhcmUgZXh0cmVtZSBpbiB0aGUgcHJlZGljdG9yICQoWCkkIHNwYWNlIGFuZCBtYXkgb3IgbWF5IG5vdCBhZmZlY3QgbW9kZWwgZml0LgoKSGVyZSBhcmUgc29tZSBleGFtcGxlcyBvZiB1bnVzdWFsIG9ic2VydmF0aW9ucy4KCmBgYHtyIG91dGxpZXJzLCBlY2hvID0gVFJVRSwgZmlnLndpZHRoID0gOCwgZmlnLmhlaWdodCA9IDQsIGZpZy5hbGlnbj0iY2VudGVyIn0KIyMgY3JlYXRlIGRhdGEKeHIgPC0gcm91bmQoMToxMCArIHJub3JtKDEwLCAwLCAwLjIpLCAxKQpzaW1kYXRhIDwtIGRhdGEuZnJhbWUoeCA9IHhyLAogICAgICAgICAgICAgICAgICAgICAgeSA9IHhyICsgcm5vcm0oMTApKQptbSA8LSBsbSh5IH4geCwgc2ltZGF0YSkKIyMgbm8gbGV2ZXJhZ2Ugb3IgaW5mbHVlbmNlCnAxIDwtIGMoNS41LDEyKQptMSA8LSBsbSh5IH4geCwgcmJpbmQoc2ltZGF0YSwgcDEpKQojIyBoaWdoIGxldmVyYWdlIGJ1dCBubyBpbmZsdWVuY2UKcDIgPC0gYygxNywxNykKbTIgPC0gbG0oeSB+IHgsIHJiaW5kKHNpbWRhdGEsIHAyKSkKIyMgaGlnaCBsZXZlcmFnZSBhbmQgaW5mbHVlbmNlCnAzIDwtIGMoMTcsNS4xKQptMyA8LSBsbSh5IH4geCwgcmJpbmQoc2ltZGF0YSwgcDMpKQojIyBzZXQgcGxvdCBhcmVhCnBhcihtZnJvdyA9IGMoMSwzKSwKICAgIG1haSA9IGMoMC45LCAwLjksIDAuNiwgMC4xKSwKICAgIG9taSA9IGMoMCwgMCwgMCwgMCksCiAgICBjZXggPSAwLjkpCiMjIHBsb3QgZXhhbXBsZXMKIyMgbm8gbGV2ZXJhZ2Ugb3IgaW5mbHVlbmNlIChsZWZ0KQpwbG90KHkgfiB4LCByYmluZChzaW1kYXRhLCBwMSksIHBjaCA9IDE2LCBsYXMgPSAxLCB4cGQgPSBOQSwKICAgICBjZXgubGFiID0gMS41LCB4bGFiID0gZXhwcmVzc2lvbihpdGFsaWMoeCkpLCB5bGFiID0gZXhwcmVzc2lvbihpdGFsaWMoeSkpLAogICAgIG1haW4gPSAiTm8gbGV2ZXJhZ2Ugb3IgaW5mbHVlbmNlIiwgY2V4Lm1haW4gPSAxKQpwb2ludHMoNS41LCAxMiwgcGNoID0gMTYsIGNleCA9IDEuNSwgY29sID0icmVkIikKYWJsaW5lKG1tKQphYmxpbmUobTEsIGx0eT0yLCBjb2wgPSJyZWQiKQojIyBoaWdoIGxldmVyYWdlIGJ1dCBubyBpbmZsdWVuY2UgKG1pZGRsZSkKcGxvdCh5IH4geCwgcmJpbmQoc2ltZGF0YSwgcDIpLCBwY2ggPSAxNiwgbGFzID0gMSwKICAgICBjZXgubGFiID0gMS41LCB4bGFiID0gZXhwcmVzc2lvbihpdGFsaWMoeCkpLCB5bGFiID0gZXhwcmVzc2lvbihpdGFsaWMoeSkpLAogICAgIG1haW4gPSAiTGV2ZXJhZ2UgYnV0IG5vIGluZmx1ZW5jZSIsIGNleC5tYWluID0gMSkKcG9pbnRzKDE3LCAxNywgcGNoID0gMTYsIGNleCA9IDEuNSwgY29sID0icmVkIikKYWJsaW5lKG1tKQphYmxpbmUobTIsIGx0eT0yLCBjb2wgPSJyZWQiKQojIyBoaWdoIGxldmVyYWdlIGFuZCBpbmZsdWVuY2UgKHJpZ2h0KQpwbG90KHkgfiB4LCByYmluZChzaW1kYXRhLCBwMyksIHBjaCA9IDE2LCBsYXMgPSAxLAogICAgIGNleC5sYWIgPSAxLjUsIHhsYWIgPSBleHByZXNzaW9uKGl0YWxpYyh4KSksIHlsYWIgPSBleHByZXNzaW9uKGl0YWxpYyh5KSksCiAgICAgbWFpbiA9ICJMZXZlcmFnZSBhbmQgaW5mbHVlbmNlIiwgY2V4Lm1haW4gPSAxKQpwb2ludHMoMTcsIDUuMSwgcGNoID0gMTYsIGNleCA9IDEuNSwgY29sID0icmVkIikKYWJsaW5lKG1tKQphYmxpbmUobTMsIGx0eT0yLCBjb2wgPSJyZWQiKQpgYGAKCjxicj4KCiMjIElkZW50aWZ5aW5nIGxldmVyYWdlIHBvaW50cwoKOjo6IHRpcAoKUmVjYWxsIHRoYXQgd2UgY2FuIHVzZSB0aGUgImhhdCBtYXRyaXgiICQoXG1hdGhiZntIfSkkIHRvIHByb2plY3QgdGhlICRuJC1kaW1lbnNpb25hbCBkYXRhICRcbWF0aGJme3l9JCBvbnRvIHRoZSAkayQtZGltZW5zaW9uYWwgbW9kZWwuIAoKOjo6CgpBcyBhIHJlbWluZGVyLCBmb3Igb3VyIGxpbmVhciBtb2RlbCBnaXZlbiBieQoKJCQKXG1hdGhiZnt5fSA9IFxtYXRoYmZ7WH0gXGJvbGRzeW1ib2x7XGJldGF9ICsgXGJvbGRzeW1ib2x7XGVwc2lsb259ICBcXApcYm9sZHN5bWJvbHtcZXBzaWxvbn0gXHNpbSBcdGV4dHtNVk59KFxtYXRoYmZ7MH0sIFxzaWdtYV4yIFxtYXRoYmZ7SX0pCiQkCgp3ZSBoYXZlCgokJApcYmVnaW57YWxpZ259ClxtYXRoYmZ7XGhhdHt5fX0gJj0gXG1hdGhiZntYfSBcYm9sZHN5bWJvbHtcaGF0e1xiZXRhfX0gXFwKICAmPSBcbWF0aGJme1h9IFxsZWZ0KCAoXG1hdGhiZntYfV57XHRvcH0gXG1hdGhiZntYfSleey0xfSBcbWF0aGJme1h9XntcdG9wfSBcbWF0aGJme3l9IFxyaWdodCkgXFwKICAmPSBcbWF0aGJme1h9IChcbWF0aGJme1h9XntcdG9wfSBcbWF0aGJme1h9KV57LTF9IFxtYXRoYmZ7WH1ee1x0b3B9IFxtYXRoYmZ7eX0gXFwKICAmPSBcbWF0aGJme0h9IFxtYXRoYmZ7eX0KXGVuZHthbGlnbn0KJCQKClRoZSB2YWx1ZXMgYWxvbmcgdGhlIGRpYWdvbmFsIG9mICRcbWF0aGJme0h9JCBhcmUga25vd24gYXMgdGhlICpsZXZlcmFnZXMqICh3aGVyZSAkXG1hdGhiZntIfV97aWl9ID0gaF9pJCkuIFRoZXNlIGxldmVyYWdlIHZhbHVlcyBnaXZlIGFuIGluZGljYXRpb24gb2YgdGhlIGluZmx1ZW5jZSBvZiBhIHBhcnRpY3VsYXIgJHhfe2lqfSQgb24gdGhlIG1vZGVsIGZpdC4gVGhlIHJlc2lkdWFscyBhcmUgdGh1cwoKJCQKXGJlZ2lue2FsaWduZWR9Clxib2xkc3ltYm9se1xoYXR7XGVwc2lsb259fSAmPSBcbWF0aGJme2V9IFxcCiAgJj0gXG1hdGhiZnt5fSAtIFxtYXRoYmZ7XGhhdHt5fX0gXFwKICAmPSBcbWF0aGJme3l9IC0gXG1hdGhiZntIfSBcbWF0aGJme3l9IFxcCiAgJj0gXG1hdGhiZnt5fSAoXG1hdGhiZntJfSAtIFxtYXRoYmZ7SH0pLgpcZW5ke2FsaWduZWR9CiQkCgpGcm9tIHRoaXMgaXQgZm9sbG93cyB0aGF0CgokJApcYmVnaW57YWxpZ25lZH0KXHRleHR7VmFyfShcYm9sZHN5bWJvbHtcaGF0e1xlcHNpbG9ufX0pICY9IFx0ZXh0e1Zhcn0oXG1hdGhiZntlfSkgXFwKICAmPSBcdGV4dHtWYXJ9KFxtYXRoYmZ7eX0gKFxtYXRoYmZ7SX0gLSBcbWF0aGJme0h9KSkgXFwKICAmPSAoXG1hdGhiZntJfSAtIFxtYXRoYmZ7SH0pIFx0ZXh0e1Zhcn0oXG1hdGhiZnt5fSApIChcbWF0aGJme0l9IC0gXG1hdGhiZntIfSlee1x0b3B9IFxcCiAgJj0gXHNpZ21hXjIgKFxtYXRoYmZ7SX0gLSBcbWF0aGJme0h9KV4yIFxcCiAgJj0gXHNpZ21hXjIgKFxtYXRoYmZ7SX0gLSBcbWF0aGJme0h9KQpcZW5ke2FsaWduZWR9CiQkCgphbmQgdGhlcmVmb3JlIHRoZSB2YXJpYW5jZSBvZiBhbiBpbmRpdmlkdWFsIHJlc2lkdWFsIGlzIAoKJCQKXHRleHR7VmFyfShcd2lkZWhhdHtcZXBzaWxvbn1fe2l9KSA9IFxzaWdtYV4yICgxIC0gaF9pKS4KJCQKCkZyb20gdGhpcyByZWxhdGlvbnNoaXAgd2UgY2FuIHNlZSB0aGF0IGxhcmdlICRoX2kkIGxlYWQgdG8gc21hbGwgdmFyaWFuY2VzIG9mICRcaGF0e1xlcHNpbG9ufV9pJCAmIGhlbmNlICRcaGF0e3l9X2kkIHRlbmRzIHRvICR5X2kkLiBUaGUgaGF0IG1hdHJpeCAkXG1hdGhiZntIfSQgaGFzIGRpbWVuc2lvbnMgJG4gXHRpbWVzIG4kIGFuZAoKJCQKXHRleHR7dHJhY2V9KFxtYXRoYmZ7SH0pID0gXHN1bV97aSA9IDF9Xm4gaF9pID0gawokJAoKVGh1cywgb24gYXZlcmFnZSB3ZSBzaG91bGQgZXhwZWN0IHRoYXQgdGhlIGF2ZXJhZ2UgbGV2ZXJhZ2UgdmFsdWUgaXMgJFxiYXJ7aH1faSA9IFxmcmFje2t9e259JC4gQW55ICRoX2kgPiAyIFxmcmFje2t9e259JCBkZXNlcnZlIGNsb3NlciBpbnNwZWN0aW9uLgoKOjo6IHRpcAoKV2UgY2FuIGVhc2lseSBjb21wdXRlIHRoZSAkaF9pJCBpbiAqKlIqKiB2aWEgdGhlIGZ1bmN0aW9uIGBoYXR2YWx1ZXMoKWAgYXMgc2hvd24gaGVyZS4KCjo6OgoKYGBge3IgZXhfaGF0X3ZhbHVlcywgZWNobyA9IFRSVUV9CiMjIGxldmVyYWdlcyBvZiBwb2ludHMgaW4gbWlkZGxlIHBsb3QgYWJvdmUKaHYgPC0gaGF0dmFsdWVzKG0yKQojIyB0cmFjZShIKSA9IG51bWJlciBvZiBwYXJhbWV0ZXJzIGluIHRoZSBtb2RlbAprIDwtIHN1bShodikKIyMgZXhwZWN0ZWQgdmFsdWUgZm9yIGhfaSAofj0gMC4zNikKRWggPC0gMiAqIChrIC8gbGVuZ3RoKGh2KSkKIyMgYXJlIGFueSBoX2kgPiBFaD8KaHYgPiBFaApgYGAKCjo6OiB0aXAKCldlIGNhbiBhbHNvIHBsb3QgdGhlIGluZGl2aWR1YWwgbGV2ZXJhZ2UgdmFsdWVzIHRvIHNlZSB3aGV0aGVyIHRoZXkgZXhjZWVkIHRoZWlyIGV4cGVjdGF0aW9uLCBvciBpZGVudGlmeSBoaWdoIGxldmVyYWdlIHZpYSBhIGhhbGYtbm9ybWFsIHBsb3QuCgo6OjoKCmBgYHtyIGxldmVyYWdlX3Bsb3RzLCBlY2hvID0gVFJVRSwgZmlnLndpZHRoID0gOCwgZmlnLmhlaWdodCA9IDQuNSwgZmlnLmFsaWduPSJjZW50ZXIifQojIyByZXZpc2VkIGBoYWxmbm9ybSgpYCBmcm9tIEZhcmF3YXkKIyMgYG5sYWJgIGdpdmVzIHRoZSBudW1iZXIgb2YgcG9pbnRzIHRvIGxhYmVsIGluIHRoZSBwbG90CiMjIGBsYWJlbHNgIGNhbiBiZSBhIGNoYXJhY3RlciB2ZWN0b3IgdGhlIHNhbWUgbGVuZ3RoIGFzIGB4YAojIyAgICAgICAgICB0aGF0IGNhbiBiZSB1c2VkIHRvIGxhYmVsIHRoZSBwb2ludHMgaW4gdGhlIHBsb3QKIyMgYHlsYWJgIGNhbiBiZSB1c2VkIHRvIGxhYmVsaW5nIG9mIHRoZSB5LWF4aXMKaGFsZm5vcm0gPC0gZnVuY3Rpb24oeCwgbmxhYiA9IDEsIGxhYmVscyA9IE5VTEwsIHlsYWIgPSAiU29ydGVkIGRhdGEiKSB7CiAgeCA8LSBhYnMoeCkKICBsYWJvcmQgPC0gb3JkZXIoeCkKICB4IDwtIHNvcnQoeCkKICBpIDwtIG9yZGVyKHgpCiAgbiA8LSBsZW5ndGgoeCkKICB1aSA8LSBxbm9ybSgobiArIDE6bikvKDIgKiBuICsgMSkpCiAgaWYoaXMubnVsbChsYWJlbHMpKSB7CiAgICBsYWJlbHMgPC0gYXMuY2hhcmFjdGVyKDE6bGVuZ3RoKHgpKQogIH0KICBwbG90KHVpLCB4W2ldLCBwY2ggPSAxNiwgbGFzID0gMSwKICAgICAgIHhsYWIgPSAiSGFsZi1ub3JtYWwgcXVhbnRpbGVzIiwgeWxhYiA9IHlsYWIsIAogICAgICAgeWxpbSA9IGMoMCwgbWF4KHgpKSwgdHlwZSA9ICJuIikKICBpZihubGFiIDwgbikgewogICAgcG9pbnRzKHVpWzE6KG4gLSBubGFiKV0sIHhbaV1bMToobiAtIG5sYWIpXSwgcGNoID0gMTYpCiAgfQogIHRleHQoeCA9IHVpWyhuIC0gbmxhYiArIDEpOm5dLCB5ID0geFtpXVsobiAtIG5sYWIgKyAxKTpuXSwKICAgICAgIGxhYmVscyA9IGxhYmVsc1tsYWJvcmRdWyhuIC0gbmxhYiArIDEpOm5dKQp9CiMjIHNldCBwbG90IGFyZWEKcGFyKG1mcm93ID0gYygxLDIpLAogICAgbWFpID0gYygwLjksMC45LDAuMSwwLjMpLAogICAgb21pID0gYygwLjUsIDAuNCwgMC41LCAwKSwKICAgIGNleCA9IDEpCiMjIHBsb3Qgb2YgaW5pZGl2ZHVhbCBsZXZlcmFnZXMgKGxlZnQpCnBsb3QobW9kZWwubWF0cml4KG0yKVssMl0sIGh2LCBwY2ggPSAxNiwgbGFzID0gMSwKICAgICB5bGFiID0gIkxldmVyYWdlIiwgeGxhYiA9IGV4cHJlc3Npb24oaXRhbGljKHgpKSkKbXRleHQoZXhwcmVzc2lvbihpdGFsaWMoaCleeyIqIn0pLCA0LCBsaW5lID0gMC4zLCBjZXggPSAxLjEsIGF0ID0gRWgsIGxhcyA9IDEpCmFibGluZShoID0gRWgsIGx0eSA9ICJkYXNoZWQiKQojIyBoYWxmLW5vcm1hbCBwbG90IG9mIHRoZSBsZXZlcmFnZXMgKHJpZ2h0KQpoYWxmbm9ybShodikKYGBgCgojIyBJZGVudGlmeWluZyBvdXRsaWVycwoKV2Ugc2F3IGluIGxlY3R1cmUgdGhhdCB3ZSBjYW4gc3RhbmRhcmRpemUgdGhlIG1vZGVsIHJlc2lkdWFscyB0byBoZWxwIGlkZW50aWZ5IG91dGxpZXJzLiBTcGVjaWZpY2FsbHksIHdlIGNhbiB1c2UgdGhlIGxldmVyYWdlcyB0byBkbyBzbywgc3VjaCB0aGF0IHRoZSAqc3R1ZGVudGl6ZWQgcmVzaWR1YWwqICR0X2kkIGlzIGdpdmVuIGJ5CgokJAp0X2kgPSBcZnJhY3t5X3tpfSAtIFxoYXR7eX1feyhpKX19eyBcaGF0e1xzaWdtYX1feyhpKX0gXHNxcnR7IDEgLSBoX2kgfSB9ID0gZV9pIFxzcXJ0eyBcZnJhY3tuIC0gayAtIDF9e24gLSBrIC0gZV9pXjJ9IH0KJCQKCmFuZCAkZV9pJCBpcyB0aGUgcmVzaWR1YWwgZm9yIHRoZSAkaSQ8c3VwPnRoPC9zdXA+IGNhc2UgYmFzZWQgb24gYSBtb2RlbCB0aGF0IGluY2x1ZGVzICphbGwqIG9mIHRoZSBkYXRhLiBUaGlzICR0X2kkIHN0YXRpc3RpYyBpcyBkaXN0cmlidXRlZCBhcyBhICR0JC1kaXN0cmlidXRpb24gd2l0aCAkbiAtIGsgLSAxJCBkZWdyZWVzIG9mIGZyZWVkb20uCgpOb3RlLCBob3dldmVyLCB0aGF0IHRoaXMgcmVxdWlyZXMgdXMgdG8gdW5kZXJ0YWtlICRuJCBkaWZmZXJlbnQgbnVsbCBoeXBvdGhlc2lzIHRlc3RzLiBUaHVzLCBpZiB3ZSBjaG9zZSBhIFR5cGUtSSBlcnJvciByYXRlIG9mICRcYWxwaGEkID0gMC4wNSwgd2Ugc2hvdWxkIGV4cGVjdCB0aGF0IDEgaW4gMjAgb2YgdGhlc2UgdGVzdHMgd291bGQgYmUgc2lnbmlmaWNhbnQgYnkgY2hhbmNlIGFsb25lLiBUbyBhY2NvdW50IGZvciBhbGwgb2YgdGhlc2UgdGVzdHMsIHdlIGNhbiBlbXBsb3kgYSAqQm9uZmVycm9uaSBjb3JyZWN0aW9uKiwgd2hpY2ggaW5zdGVhZCBzZXRzIHRoZSB0aHJlc2hvbGQgYXQgJFxhbHBoYV9CID0gXGFscGhhIC8gbiQuIFRoaXMgY29ycmVjdGlvbiBmYWN0b3IgY29tZXMgdXAgZWxzZXdoZXJlIGluIHN0YXRpc3RpY2FsIHRlc3RpbmcgYW5kIGlzIGtub3duIHRvIGJlIGNvbnNlcnZhdGl2ZTsgaXQgZmluZHMgZmV3ZXIgb3V0bGllcnMgdGhhbiB0aGUgbm9taW5hbCBsZXZlbCBvZiBjb25maWRlbmNlIHdvdWxkLgoKOjo6IHRpcAoKQ29tcHV0aW5nIHRoZSBzdHVkZW50aXplZCByZXNpZHVhbHMgaW4gKipSKiogaXMgZWFzeSB3aXRoIHRoZSBgcnN0dWRlbnQoKWAgZnVuY3Rpb24uIFdlIGNhbiB0aGVuIGNvbXBhcmUgdGhlbSB0byB0aGUgY3JpdGljYWwgJHQkIHZhbHVlIHdpdGggYHF0KClgLiAKCjo6OgoKOjo6IHRhc2sKCkNvbXB1dGluZyB0aGUgc3R1ZGVudGl6ZWQgcmVzaWR1YWxzIGZvciBjYXNlICMxIGFib3ZlIChsZWZ0LWhhbmQgcGxvdCkuCgo6OjoKCmBgYHtyIHN0dWRlbnRfdCwgZWNobyA9IFRSVUV9CiMjIGdldCBzYW1wbGUgc2l6ZQpuX20xIDwtIG5yb3cobW9kZWwubWF0cml4KG0xKSkKIyMgZ2V0IHN0dWRlbnRpemVkIGUKdF9zdHVkIDwtIHJzdHVkZW50KG0xKQojIyBCb25mZXJyb25pIGFscGhhCmFscGhhIDwtIDAuMDUgLyBuX20xCiMjIGNyaXRpY2FsIHQgdmFsdWUKZGYgPC0gbl9tMSAtIGxlbmd0aChjb2VmKG0xKSkgLSAxIAp0X2NyaXQgPC0gcXQoMSAtIGFscGhhLzIsIGRmKQojIyBjb21wYXJlIHRfc3R1ZCB0byB0X2NyaXQKdF9zdHVkID4gdF9jcml0CmBgYAoKOjo6IG5vdGUKCldlIGNhbiBzZWUgdGhhdCB0aGUgYHIgd2hpY2godF9zdHVkID4gdF9jcml0KWA8c3VwPnRoPC9zdXA+IGRhdHVtIGlzIGFuIG91dGxpZXIgKGFzIHdlIHN1c3BlY3RlZCBmcm9tIHRoZSBhYm92ZSBwbG90KS4KCjo6OgoKIyMgSWRlbnRpZnlpbmcgaW5mbHVlbnRpYWwgb2JzZXJ2YXRpb25zCgpJbmZsdWVudGlhbCBvYnNlcnZhdGlvbnMgbWlnaHQgbm90IGJlIG91dGxpZXJzIG5vciBoYXZlIGhpZ2ggbGV2ZXJhZ2UsIGJ1dCB3ZSB3YW50IHRvIGlkZW50aWZ5IHRoZW0gYW55d2F5LiBXZSBzYXcgaW4gbGVjdHVyZSB0aGF0IENvb2sncyBEaXN0YW5jZSAkKEQpJCBpcyBhIHBvcHVsYXIgY2hvaWNlLCB3aGVyZQoKJCQKRF9pID0gZV9pXjIgXGZyYWN7MX17a30gXGxlZnQoIFxmcmFje2hfaX17MSAtIGhfaX0gXHJpZ2h0KS4KJCQKClRoZSBpZGVhIGhlcmUgaXMgdGhhdCAkRF9pJCBjb21iaW5lcyB0aGUgbWFnbml0dWRlIG9mIGEgcmVzaWR1YWwgYW5kIGl0cyBsZXZlcmFnZS4gSXQncyBlYXN5IHRvIGNhbGN1bGF0ZSB0aGUgJERfaSQgd2l0aCB0aGUgYGNvb2tzLmRpc3RhbmNlKClgIGZ1bmN0aW9uLiBXZSBjYW4gdGhlbiB2aXN1YWxseSBpbnNwZWN0ICREJCB3aXRoIGEgaGFsZi1ub3JtYWwgcGxvdCAod2UnbGwgbGFiZWwgdGhlIDIgdmFsdWVzIHdpdGggdGhlIGhpZ2hlc3QgJEQkIGJ5IHNldHRpbmcgYG5sYWIgPSAyYCkuCgpgYGB7ciBjb29rc19kLCBlY2hvID0gVFJVRSwgZmlnLndpZHRoID0gNSwgZmlnLmhlaWdodCA9IDUsIGZpZy5hbGlnbj0iY2VudGVyIn0KIyMgQ29vaydzIEQKY29vayA8LSBjb29rcy5kaXN0YW5jZShtMikKIyMgaGFsZi1ub3JtYWwgcGxvdApwYXIobWFpID0gYygxLDEsMC4xLDAuMSksCiAgICBvbWkgPSBjKDAsIDAsIDAsIDApLAogICAgY2V4ID0gMSkKaGFsZm5vcm0oY29vaywgbmxhYiA9IDIsIHlsYWIgPSAiQ29va+KAmXMgRGlzdGFuY2UiKQpgYGAKCjxicj4KCiMgUHJvYmxlbXMgd2l0aCBlcnJvcnMKClRoZSBtb2RlbHMgd2UgaGF2ZSBiZWVuIHVzaW5nIGFzc3VtZSB0aGF0IHRoZSBlcnJvcnMgYXJlIGluZGVwZW5kZW50IGFuZCBpZGVudGljYWxseSBkaXN0cmlidXRlZCAoSUlEKS4gTGV0J3MgZXhwbG9yZSBzb21lIG9mIHRoZSBvcHRpb25zIGZvciBkZWFsaW5nIHdpdGggc2l0dWF0aW9ucyB3aGVyZSB0aG9zZSBhc3N1bXB0aW9ucyBtYXkgYmUgdmlvbGF0ZWQuCgojIyBXZWlnaHRlZCBsZWFzdCBzcXVhcmVzCgpJbiBjYXNlcyB3aGVyZSB0aGUgZXJyb3JzIGFyZSBpbmRlcGVuZGVudCwgYnV0ICpub3QqIGlkZW50aWNhbGx5IGRpc3RyaWJ1dGVkLCB3ZSBjYW4gdXNlIHdlaWdodGVkIGxlYXN0IHNxdWFyZXMuIExldCdzIGNvbnNpZGVyIGEgZGF0YSBzZXQgZnJvbSB0aGUgZmFtb3VzIHN0YXRpc3RpY2lhbiBbRnJhbmNpcyBHYWx0b25dKGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0ZyYW5jaXNfR2FsdG9uKSwgd2hpY2ggY29udGFpbnMgaW5mb3JtYXRpb24gaGUgY29sbGVjdGVkIG9uIHRoZSBzaXplIG9mIHBlYSBzZWVkcyBpbiBwYXJlbnQgcGxhbnRzIGFuZCB0aGVpciBvZmZzcHJpbmcgcGxhbnRzLCBhbmQgdGhlIGZyZXF1ZW5jeSBvZiBlYWNoIG9mIHRoZSBwYWlyZWQgbWVhc3VyZW1lbnRzLiBUaGUgZGF0YSBhcmUgY29udGFpbmVkIGluIHRoZSBhY2NvbXBhbnlpbmcgZmlsZSBgZ2FsdG9uX3BlYXMuY3N2YC4KCjo6OiB0YXNrCgpCZWdpbiBieSByZWFkaW5nIGluIHRoZSBkYXRhIGFuZCBwbG90dGluZyB0aGVtLgoKOjo6CgpgYGB7ciBnYWx0b25fcGVhcywgZWNobyA9IFRSVUUsIGZpZy53aWR0aCA9IDUsIGZpZy5oZWlnaHQgPSA1LCBmaWcuYWxpZ249ImNlbnRlciJ9CiMjIHJlYWQgZGF0YSBmaWxlCnBlYXMgPC0gcmVhZC5jc3YoImdhbHRvbl9wZWFzLmNzdiIpCiMjIHNldCBwbG90IGFyZWEKcGFyKG1haSA9IGMoMSwxLDAuMSwwLjEpLAogICAgb21pID0gYygwLCAwLCAwLCAwKSwKICAgIGNleCA9IDEpCiMjIHBsb3QgdGhlIGRhdGEKcGxvdChwZWFzJHBhcmVudCwgcGVhcyRvZmZzcHJpbmcsIHBjaCA9IDE2LCBsYXMgPSAxLAogICAgIHhsYWIgPSAiU2l6ZSBvZiBwYXJlbnQgc2VlZCAobW0pIiwgeWxhYiA9ICJTaXplIG9mIG9mZnNwcmluZyBzZWVkIChtbSkiKQpgYGAKCjxicj4KCkVhY2ggb2YgdGhlICR5X2kkIGhlcmUgaXMgYWN0dWFsbHkgYSB3ZWlnaHRlZCBtZWFuIG9mIHRoZSBvZmZzcHJpbmcgcGVhIHNpemUgaW4gZWFjaCBvZiB0aGUgcGFyZW50IHNpemUgZ3JvdXBzLCBzbyB3ZSBzaG91bGQgdXNlIGEgd2VpZ2h0ZWQgcmVncmVzc2lvbiB3aXRoICR3X2kgPSAxIC8gbl9pJC4gVGhpcyBpcyBlYXN5IHRvIGRvIHdpdGggYGxtKClgIGJ5IHBhc3NpbmcgYW4gYWRkaXRpb25hbCBgd2VpZ2h0c2AgYXJndW1lbnQuIFdlJ2xsIGFsc28gZml0IGEgcmVndWxhciB1bndlaWdodGVkIG1vZGVsIGZvciBjb21wYXJpc29uLgoKYGBge3IgZml0X2dhbHRvbl9wZWFzfQojIyBmaXQgd2VpZ2h0ZWQgcmVncmVzc2lvbgptcHcgPC0gbG0ob2Zmc3ByaW5nIH4gcGFyZW50LCBwZWFzLCB3ZWlnaHRzID0gMS9uKQpmYXJhd2F5OjpzdW1hcnkobXB3KQojIyBjb21wYXJlIHRvIHVud2VpZ2h0ZWQgcmVncmVzc2lvbgptcCA8LSBsbShvZmZzcHJpbmcgfiBwYXJlbnQsIHBlYXMpCmZhcmF3YXk6OnN1bWFyeShtcCkKYGBgCgo6Ojogbm90ZQoKT3VyIHdlaWdodGVkIHJlZ3Jlc3Npb24gaGFzIGEgbXVjaCBsb3dlciBgUmVzaWR1YWwgU0VgICQoXHdpZGVoYXR7XHNpZ21hfV4yKSQgYW5kIHRoZSBwYXJhbWV0ZXIgZXN0aW1hdGVzIGFyZSBkaWZmZXJlbnQgYXMgd2VsbC4KCjo6OgoKIyMgUm9idXN0IHJlZ3Jlc3Npb24KCldlIHNhdyBpbiBsZWN0dXJlIHRoYXQgd2UgY2FuIHVzZSByb2J1c3QgcmVncmVzc2lvbiBpbiBjYXNlcyB3aGVyZSB0aGUgZXJyb3JzIGZvbGxvdyBhIG5vbi1ub3JtYWwgZGlzdHJpYnV0aW9uLiBSZWNhbGwgdGhhdCB0aGUgaWRlYSBpcyB0byByZXBsYWNlIHRoZSBzcXVhcmVkIGZ1bmN0aW9uIGluIG91ciBlc3RpbWF0ZSBvZiAkU1NFJCB3aXRoIHNvbWUgb3RoZXIgZnVuY3Rpb24uCgojIyMgSHViZXIncyBtZXRob2QKCk9uZSBvZiB0aGUgcG9zc2liaWxpdGllcyBpcyAqSHViZXIncyBtZXRob2QqIHdoZXJlCgokJApTU0UgPSBcc3VtXm5fe2kgPSAxfSBmKHopIFxcCn4gXFwKZih6KSA9IFxsZWZ0XHsgClxiZWdpbnttYXRyaXh9ClxmcmFje3peMn17Mn0gJiBcdGV4dHtpZn0gfiBcbGVmdHwgeiBccmlnaHR8IFxsZXEgYyBcXApjIFxsZWZ0fCB6IFxyaWdodHwgLSBcZnJhY3tjXjJ9ezJ9ICYgXHRleHR7b3RoZXJ3aXNlfQpcZW5ke21hdHJpeH0KXHJpZ2h0LgokJAoKYW5kICRjID0gXHdpZGVoYXR7XHNpZ21hfSBccHJvcHRvIFx0ZXh0e01lZGlhbn0oXGxlZnR8IFx3aWRlaGF0e1xlcHNpbG9ufSBccmlnaHR8KSQuCgpBcyBhbiBleGFtcGxlLCBsZXQncyByZXR1cm4gdG8gdGhlIHBsYW50IGRhdGEgZnJvbSB0aGUgR2FsYXBhZ29zIEFyY2hpcGVsYWdvIHRoYXQgd2UgdXNlZCBsYXN0IHdlZWsgaW4gbGFiLiAKCjo6OiB0YXNrCgpCZWdpbiBieSBmaXR0aW5nIGEgbm9ybWFsIHJlZ3Jlc3Npb24gbW9kZWwgYW5kIHBsb3QgdGhlIHJlc2lkdWFscyBhZ2FpbnN0IHRoZSBmaXR0ZWQgdmFsdWVzLgoKOjo6CgpgYGB7ciBwbGFpbl9nYWxhLCBlY2hvID0gVFJVRSwgZmlnLndpZHRoID0gNSwgZmlnLmhlaWdodCA9IDUsIGZpZy5hbGlnbj0iY2VudGVyIn0KIyMgZ2V0IHRoZSBkYXRhCmxpYnJhcnkoZmFyYXdheSkKaGVhZChnYWxhKQojIyBmaXQgbm9ybWFsIHJlZ3IgbW9kZWwKZ20gPC0gbG0oU3BlY2llcyB+IEFyZWEsIGdhbGEpCiMjIGV4YW1pbmUgZml0CnN1bWFyeShnbSkKIyMgc2V0IHBsb3QgYXJlYQpwYXIobWFpID0gYygxLDEsMC4xLDAuMSksCiAgICBvbWkgPSBjKDAsIDAsIDAsIDApLAogICAgY2V4ID0gMSkKIyMgcGxvdCByZXNpZHVhbHMgdnMgeV9oYXQKcGxvdChmaXR0ZWQoZ20pLCByZXNpZChnbSksIHBjaCA9IDE2LCBsYXMgPSAxLAogICAgIHlsYWIgPSBleHByZXNzaW9uKGl0YWxpYyhlKSksIHhsYWIgPSBleHByZXNzaW9uKGhhdChpdGFsaWMoeSkpKSkKYGBgCgo8YnI+CgpUaGlzIHBsb3QgcmV2ZWFscyBzb21lIG9idmlvdXMgcHJvYmxlbXMgd2l0aCBvdXIgbW9kZWwgYXNzdW1wdGlvbnMsIHNvIG5vdyBsZXQncyBmaXQgb3VyIHJvYnVzdCBtb2RlbC4gVG8gZG8gc28sIHdlIGNhbiB1c2UgdGhlIGBybG0oKWAgZnVuY3Rpb24gaW4gdGhlICoqTUFTUyoqIHBhY2thZ2UsIHdoZXJlaW4gdGhlIGRlZmF1bHQgb3B0aW9uIGlzIHRvIHVzZSBIdWJlcidzIG1ldGhvZC4KCmBgYHtyIHJvYnVzdF9odWJlcn0KIyMgZml0IHJvYnVzdCByZWdyIG1vZGVsCnJnbSA8LSBNQVNTOjpybG0oU3BlY2llcyB+IEFyZWEsIGdhbGEpCiMjIGV4YW1pbmUgZml0CnN1bW1hcnkocmdtKQpgYGAKCkhlcmUgd2Ugc2VlIHRoYXQgdGhlIHBhcmFtZXRlciBlc3RpbWF0ZXMgaGF2ZSBjaGFuZ2VkIHNvbWV3aGF0IGFuZCB0aGUgZXN0aW1hdGUgb2YgdGhlIHJlc2lkdWFsIHN0YW5kYXJkIGVycm9yIGhhcyBkZWNyZWFzZWQgc3Vic3RhbnRpYWxseS4gTGV0J3MgZ28gYSBzdGVwIGZ1cnRoZXIgYW5kIGZpbmQgb3V0IHdoaWNoIG9mIHRoZSBpc2xhbmRzIGhhZCBoaWdoIGluZmx1ZW5jZSBhbmQgaGVuY2UgbG93IHdlaWdodGluZy4KCmBgYHtyIGh1YmVyX3d0c30KIyMgZXh0cmFjdCB3ZWlnaHRzIGZyb20gbW9kZWwgZml0Cnd0cyA8LSByb3VuZChyZ20kdywgMikKbmFtZXMod3RzKSA8LSByb3cubmFtZXMoZ2FsYSkKIyMgc29ydCBhbmQgaW5zcGVjdCB0aGVtCnNvcnQod3RzKQpgYGAKCjo6OiBub3RlCgpGb3VyIG9mIHRoZSBpc2xhbmRzIGhhdmUgYmVlbiBkaXNjb3VudGVkIGluIHRoZSBlc3RpbWF0aW9uIHByb2NlZHVyZS4KCjo6OgoKIyMjIFRyaW1tZWQgbGVhc3Qgc3F1YXJlcwoKTS1lc3RpbWF0aW9uIHdpbGwgZmFpbCBpZiB0aGUgbGFyZ2UgZXJyb3JzIGFyZSBudW1lcm91cyBhbmQgZXh0cmVtZSBpbiB2YWx1ZS4gSWYgdGhpcyBpcyB0aGUgY2FzZSwgdGhlbiB3ZSBjYW4gdXNlICpsZWFzdCB0cmltbWVkIHNxdWFyZXMqIChMVFMpIGFzIGEgcmVzaXN0YW50IHJlZ3Jlc3Npb24gbWV0aG9kIHRoYXQgZGVhbHMgd2VsbCB3aXRoIHRoaXMgc2l0dWF0aW9uLiBMVFMgbWluaW1pemVzIHRoZSBzdW0gb2Ygc3F1YXJlcyBvZiB0aGUgJHEkIHNtYWxsZXN0IHJlc2lkdWFscywgc3VjaCB0aGF0CgokJApTU0UgPSBcc3VtXm5fe2kgPSAxfSBlXjJfe2l9IH4gXHJpZ2h0YXJyb3cgfiBTU0VfcSA9IFxzdW1ecV97aSA9IDF9IGVeMl97KGkpfQokJAoKYW5kICQoaSkkIGluZGljYXRlcyB0aGUgcmVzaWR1YWxzIGFyZSBzb3J0ZWQgaW4gYXNjZW5kaW5nIG9yZGVyLiBUaGUgZGVmYXVsdCBpcyAkcSA9IFxsZmxvb3Igbi8yIFxyZmxvb3IgKyBcbGZsb29yIChrICsgMSkgLyAyIFxyZmxvb3IkIHdoZXJlICRcbGZsb29yIFxjZG90IFxyZmxvb3IkIGlzIHRoZSBmbG9vciBmdW5jdGlvbiwgd2hpY2ggYWx3YXlzIHJvdW5kcyBhIG51bWJlciBkb3duIHRvIHRoZSBuZWFyZXN0IGludGVnZXIgKHR5cGUgYD9mbG9vcmAgZm9yIGhlbHAgb24gdGhpcyBmdW5jdGlvbiBpbiAqKlIqKikuCgo6OjogdGlwCgpXZSBjYW4gZml0IGFuIExUUyBtb2RlbCB3aXRoIHRoZSBgbHRzcmVnKClgIGZ1bmN0aW9uIGluIHRoZSAqKk1BU1MqKiBwYWNrYWdlLiAKCjo6OgoKOjo6IHRhc2sKCkZpdCBhbiBMVFMgbW9kZWwgdG8gdGhlIEdhbGFwYWdvcyBwbGFudCBkYXRhIGFuZCBleGFtaW5lIHRoZSBlc3RpbWF0ZWQgcGFyYW1ldGVycy4KCjo6OgoKYGBge3IgTFRTfQojIyBmaXQgTFRTIG1vZGVsCmx0bSA8LSBNQVNTOjpsdHNyZWcoU3BlY2llcyB+IEFyZWEsIGdhbGEpCiMjIGV4YW1pbmUgZml0CmNvZWYobHRtKQpgYGAKClRoaXMgbWV0aG9kIGRvZXMgbm90IGF1dG9tYXRpY2FsbHkgcmVwb3J0IHRoZSB1bmNlcnRhaW50eSBpbiB0aGUgcGFyYW1ldGVyIGVzdGltYXRlcywgYnV0IHdlIGNhbiB1c2Ugb3VyIGJvb3RzdHJhcHBpbmcgbWV0aG9kIHRvIGVzdGltYXRlIGEgY29uZmlkZW5jZSBpbnRlcnZhbCBhcm91bmQgdGhlbS4KCmBgYHtyIGJvb3RzdHJhcF9DSX0KIyMgbnVtYmVyIG9mIGJvb3N0cmFwIHNhbXBsZXMKbmIgPC0gMTAwMAojIyBlbXB0eSBtYXRyaXggZm9yIGJldGEgZXN0aW1hdGVzCmJldGFfZXN0IDwtIG1hdHJpeChOQSwgbmIsIDIpCiMjIHJlc2lkdWFscyBmcm9tIG91ciBtb2RlbApyZXNpZHMgPC0gcmVzaWR1YWxzKGx0bSkKIyMgc2FtcGxlIG1hbnkgdGltZXMKZm9yKGkgaW4gMTpuYikgewogICMjIHNhbXBsZSB3LyByZXBsYWNlbWVudCBmcm9tIGUKICBlX3N0YXIgPC0gc2FtcGxlKHJlc2lkcywgcmVwID0gVFJVRSkKICAjIyBjYWxjdWxhdGUgeV9zdGFyCiAgeV9zdGFyIDwtIHByZWRpY3QobHRtKSArIGVfc3RhcgogICMjIHJlLWVzdGltYXRlIG1vZGVsCiAgYmV0YV9zdGFyIDwtIE1BU1M6Omx0c3JlZyh5X3N0YXIgfiBBcmVhLCBnYWxhKQogICMjIHNhdmUgZXN0aW1hdGVkIGJldGFzCiAgYmV0YV9lc3RbaSxdIDwtIGNvZWYoYmV0YV9zdGFyKQp9CiMjIGV4dHJhY3QgMi41JSBhbmQgOTcuNSUgdmFsdWVzICh3aXRoIHRoZSBtZWRpYW4pCkNJOTUgPC0gYXBwbHkoYmV0YV9lc3QsIDIsIHF1YW50aWxlLCBjKDAuMDI1LCAwLjUsIDAuOTc1KSkKY29sbmFtZXMoQ0k5NSkgPC0gYygiSW50ZXJjZXB0IiwgIkFyZWEiKQp0KHJvdW5kKENJOTUsIDIpKQpgYGAKCg==