Preamble
Read stored results for heart data
library(tidyverse)
library(limma)
library(QFeatures)
library(msqrob2)
pe <- readRDS(
url(
"https://raw.githubusercontent.com/statOmics/SGA2020/gh-pages/assets/peHeart.rds",
"rb")
)
Linear regression
- Consider a vector of predictors \(\mathbf{x}_i=(x_1,\ldots,x_{p-1})\) and
- a real-valued response \(Y_i\)
- with \(i = 1, \ldots, n\)
- then the linear regression model can be written as \[
Y_i=f(\mathbf{x}) +\epsilon=\beta_0+\sum\limits_{j=1}^{p-1} x_{ij}\beta + \epsilon_i
\] with i.i.d. \(\epsilon_i\sim N(0,\sigma^2)\)
- \(n\) observations \((\mathbf{x}_1,y_1) \ldots (\mathbf{x}_n,y_n)\)
- Regression in matrix notation \[\mathbf{Y}=\mathbf{X\beta} + \boldsymbol{\epsilon}\] with \(\mathbf{Y}=\left[\begin{array}{c}y_1\\ \vdots\\y_n\end{array}\right]\), \(\mathbf{X}=\left[\begin{array}{cccc} 1&x_{11}&\ldots&x_{1p-1}\\ \vdots&\vdots&&\vdots\\ 1&x_{n1}&\ldots&x_{np-1} \end{array}\right]\), \(\boldsymbol{\beta}=\left[\begin{array}{c}\beta_0\\ \vdots\\ \beta_{p-1}\end{array}\right]\) and \(\boldsymbol{\epsilon}=\left[\begin{array}{c} \epsilon_1 \\ \vdots \\ \epsilon_n\end{array}\right]\)
Least Squares (LS)
Minimize the residual sum of squares \[\begin{eqnarray*}
RSS(\boldsymbol{\beta})&=&\sum\limits_{i=1}^n e^2_i\\
&=&\sum\limits_{i=1}^n \left(y_i-\beta_0-\sum\limits_{j=1}^p x_{ij}\beta_j\right)^2
\end{eqnarray*}\]
or in matrix notation \[\begin{eqnarray*}
RSS(\boldsymbol{\beta})&=&(\mathbf{Y}-\mathbf{X\beta})^T(\mathbf{Y}-\mathbf{X\beta})\\
&=&\Vert \mathbf{Y}-\mathbf{X\beta}\Vert^2
\end{eqnarray*}\] with the \(L_2\)-norm of a \(p\)-dim. vector \(v\) \(\Vert \mathbf{v} \Vert=\sqrt{v_1^2+\ldots+v_p^2}\)
\(\rightarrow\) \(\hat{\boldsymbol{\beta}}=\text{argmin}_\beta \Vert \mathbf{Y}-\mathbf{X\beta}\Vert^2\)}
Variance Estimator?
\[
\begin{array}{ccl}
\hat{\boldsymbol{\Sigma}}_{\hat{\boldsymbol{\beta}}}
&=&\text{var}\left[(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{Y}\right]\\\\
&=&(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\text{var}\left[\mathbf{Y}\right]\mathbf{X}(\mathbf{X}^T\mathbf{X})^{-1}\\\\
&=&(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T(\mathbf{I}\sigma^2)\mathbf{X}(\mathbf{X}^T\mathbf{X})^{-1}
\\\\
&=&(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{I}\quad\mathbf{X}(\mathbf{X}^T\mathbf{X})^{-1}\sigma^2\\\\
%\hat{\boldmath{\Sigma}}_{\hat{\boldsymbol{\beta}}}&=&(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\var\left[\mathbf{Y}\right](\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}\\
&=&(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{X}(\mathbf{X}^T\mathbf{X})^{-1}\sigma^2\\\\
&=&(\mathbf{X}^T\mathbf{X})^{-1}\sigma^2
\end{array}
\]
heart example
summary(fit)$cov.unscaled * sigma(fit)^2
## (Intercept) locationR tissueV patient4
## (Intercept) 0.3938774 -2.625849e-01 -2.625849e-01 -1.969387e-01
## locationR -0.2625849 5.251699e-01 2.625849e-01 1.145024e-16
## tissueV -0.2625849 2.625849e-01 5.251699e-01 7.663178e-17
## patient4 -0.1969387 1.145024e-16 7.663178e-17 3.938774e-01
## patient8 -0.1969387 1.868024e-16 1.489318e-16 1.969387e-01
## locationR:tissueV 0.2625849 -5.251699e-01 -5.251699e-01 -5.227534e-17
## patient8 locationR:tissueV
## (Intercept) -1.969387e-01 2.625849e-01
## locationR 1.868024e-16 -5.251699e-01
## tissueV 1.489318e-16 -5.251699e-01
## patient4 1.969387e-01 -5.227534e-17
## patient8 3.938774e-01 -2.473696e-16
## locationR:tissueV -2.473696e-16 1.050340e+00
n <- nrow(X)
p <- ncol(X)
mse <- sum((y-X%*%betas)^2)/(n-p)
SigmaBeta <- solve(t(X)%*%X) * mse
SigmaBeta
## (Intercept) locationR tissueV patient4 patient8
## (Intercept) 0.3938774 -0.2625849 -0.2625849 -0.1969387 -0.1969387
## locationR -0.2625849 0.5251699 0.2625849 0.0000000 0.0000000
## tissueV -0.2625849 0.2625849 0.5251699 0.0000000 0.0000000
## patient4 -0.1969387 0.0000000 0.0000000 0.3938774 0.1969387
## patient8 -0.1969387 0.0000000 0.0000000 0.1969387 0.3938774
## locationR:tissueV 0.2625849 -0.5251699 -0.5251699 0.0000000 0.0000000
## locationR:tissueV
## (Intercept) 0.2625849
## locationR -0.5251699
## tissueV -0.5251699
## patient4 0.0000000
## patient8 0.0000000
## locationR:tissueV 1.0503398
range(SigmaBeta - summary(fit)$cov.unscaled * sigma(fit)^2)
## [1] -4.773959e-15 9.103829e-15
data.frame(summary(fit)$coef[,1:2], betas = betas, seBetas = diag(SigmaBeta)^.5)
Contrasts
When we assess a contrast we assess a linear combination of model parameters:
\[ H_0: \mathbf{L^T\beta} = 0 \text{ vs } H_1: \mathbf{L^T\beta} \neq 0 \]
Estimator of Contrast?
\[\mathbf{L}^T\hat{\boldsymbol{\beta}}\]
Variance?
\[
\boldsymbol{\Sigma}_{\mathbf{L}\hat{\boldsymbol{\beta}}}=\mathbf{L}^T\boldsymbol{\Sigma}_{\hat{\boldsymbol{\beta}}}\mathbf{L}
\]
heart example
L <- makeContrast(
c(
"tissueV = 0",
"tissueV + locationR:tissueV = 0",
"tissueV + 0.5*locationR:tissueV = 0","locationR:tissueV = 0"),
parameterNames =
rowData(pe[["proteinRobust"]])$msqrobModels[[2]] %>%
getCoef %>%
names
)
L
## tissueV tissueV + locationR:tissueV
## (Intercept) 0 0
## locationR 0 0
## tissueV 1 1
## patient4 0 0
## patient8 0 0
## locationR:tissueV 0 1
## tissueV + 0.5 * locationR:tissueV locationR:tissueV
## (Intercept) 0.0 0
## locationR 0.0 0
## tissueV 1.0 0
## patient4 0.0 0
## patient8 0.0 0
## locationR:tissueV 0.5 1
contrasts <- t(L) %*% betas
SigmaContrasts <- t(L) %*% SigmaBeta %*% L
seContrasts <- SigmaContrasts %>%
diag %>%
sqrt
Comparison with lm and glht results
## Loading required package: mvtnorm
## Loading required package: survival
## Loading required package: TH.data
## Loading required package: MASS
##
## Attaching package: 'MASS'
## The following object is masked from 'package:dplyr':
##
## select
##
## Attaching package: 'TH.data'
## The following object is masked from 'package:MASS':
##
## geyser
fitGlht <- glht(fit, linfct = t(L))
summary(fitGlht, test = adjusted("none"))
##
## Simultaneous Tests for General Linear Hypotheses
##
## Fit: lm(formula = y ~ location * tissue + patient, data = colData(pe),
## x = TRUE)
##
## Linear Hypotheses:
## Estimate Std. Error t value Pr(>|t|)
## tissueV == 0 0.12757 0.72469 0.176 0.866
## tissueV + locationR:tissueV == 0 0.08626 0.72469 0.119 0.909
## tissueV + 0.5 * locationR:tissueV == 0 0.10691 0.51243 0.209 0.842
## locationR:tissueV == 0 -0.04131 1.02486 -0.040 0.969
## (Adjusted p values reported -- none method)
data.frame(contrasts, seContrasts)
Note, that the power for assessing \(\log_2\) FC between ventriculum and atrium left and right is the same. Indeed, the standard errors are equal for both effects.
Note, that the power for assessing \(\log_2\) FC between ventriculum and atrium over both heart regions is higher than when assessing the effect left or right.
- Indeed, the standard error is a factor \(\sqrt{2}\) smaller for the former effect
- We intuitively can explain this because we can use all samples (double the number of samples) to assess the average effect.
- Hence the variance is a factor two smaller, and the se with a factor \(\sqrt{2}\)
Note, that we have the lowest power to pick up an interaction effect. Indeed, the se is a factor \(\sqrt{2}\) larger than for the ventriculum - atrium effect left or right and a factor 2 larger than for the average effect between ventriculum and atrium.
seContrasts / seContrasts[1]
## tissueV tissueV + locationR:tissueV
## 1.0000000 1.0000000
## tissueV + 0.5 * locationR:tissueV locationR:tissueV
## 0.7071068 1.4142136
## [1] 1.414214
## [1] 0.7071068
t-tests
When the assumptions of the linear model hold \[
\hat{\boldsymbol{\beta}} \sim MVN\left[\boldsymbol{\beta},\left(\mathbf{X}^T\mathbf{X}\right)^{-1}\sigma^2\right]
\]
Hence, \[
\mathbf{L}^T\hat{\boldsymbol{\beta}} \sim MVN\left[\mathbf{L}^T\boldsymbol{\beta},\mathbf{L}^T\left[\left(\mathbf{X}^T\mathbf{X}\right)^{-1}\sigma^2\right]\mathbf{L}\right]
\]
We estimate \(\sigma^2\) by MSE \[\hat{\sigma}^2=\frac{\mathbf{e}^T\mathbf{e}}{n-p} \rightarrow \hat{\boldsymbol{\Sigma}}_{\hat{\boldsymbol{\beta}}}=\left(\mathbf{X}^T\mathbf{X}\right)^{-1}\hat\sigma^2\]
When we test one contrast at the time (e.g. the \(k^\text{th}\) contrast) the statistic reduces to
\[T=\frac{\mathbf{L}_k^T\hat{\boldsymbol{\beta}}}{\sqrt{\left(\mathbf{L}^T_k\hat{\boldsymbol{\Sigma}}_{\hat{\boldsymbol{\beta}}}\mathbf{L}_k\right)}} \underset{H_0}{\sim} t_{n-p}\] follows a t distribution with n-p degrees of freedom under \(H_0: \mathbf{L}^T_k\hat{\boldsymbol{\beta}}=0\)
heart example
tContrasts <- contrasts/seContrasts
pContrasts <- pt(abs(tContrasts),
df = n - p,
lower.tail = FALSE) * 2
Comparison with lm and glht results
summary(fitGlht, test = adjusted("none"))
##
## Simultaneous Tests for General Linear Hypotheses
##
## Fit: lm(formula = y ~ location * tissue + patient, data = colData(pe),
## x = TRUE)
##
## Linear Hypotheses:
## Estimate Std. Error t value Pr(>|t|)
## tissueV == 0 0.12757 0.72469 0.176 0.866
## tissueV + locationR:tissueV == 0 0.08626 0.72469 0.119 0.909
## tissueV + 0.5 * locationR:tissueV == 0 0.10691 0.51243 0.209 0.842
## locationR:tissueV == 0 -0.04131 1.02486 -0.040 0.969
## (Adjusted p values reported -- none method)
data.frame(contrasts, seContrasts, tContrasts, pContrasts)
Omnibus test
We can also assess all contrasts simultaneously with the omnibus null hypothesis: \[H_0: \mathbf{L}^T\hat{\boldsymbol{\beta}}=\mathbf{0}\]
Statistic \[\mathbf{F}=\frac{\hat{\boldsymbol{\beta}}^T\mathbf{L}\left(\mathbf{L}^T\hat{\boldsymbol{\Sigma}}_{\hat{\boldsymbol{\beta}}}\mathbf{L}\right)^{-1}\mathbf{L}^T\hat{\boldsymbol{\beta}}}{n_c} \underset{H_0}{\sim} F_{n_c,n-p}\] follows an F distribution with \(n_c\) and n-p degrees of freedom under the omnibus null hypothesis.
Note, that \(n_c\) equals the number of contrasts, and
\(\mathbf{L}\) is assumed to be full rank
If the matrix is not full rank, but has rank \(r < n_c\)
i.e. some of the contrasts can be written as linear combinations of other contrasts,
the inverse of the variance covariance matrix of the contrasts does not exist
we can then decompose L in \(r\) orthogonal contrasts \(\mathbf{Q}\) with \[\mathbf{Q}_j^T \mathbf{Q}_k^T = \delta_{jk},\]
\(j,k \in 1,\ldots,r\),
\(\delta{jk} = 0\) and if \(j\neq k\) \(\delta{jk} = 1\)
Decomposition can be done using the QR decomposition
We can than assess the omnibus null hypothesis using the statistic: \[\mathbf{F}=\frac{\hat{\boldsymbol{\beta}}^T\mathbf{Q}_r\left(\mathbf{Q}^T_r\hat{\boldsymbol{\Sigma}}_{\hat{\boldsymbol{\beta}}}\mathbf{Q}_r\right)^{-1}\mathbf{Q}^T_r\hat{\boldsymbol{\beta}}}{r} \underset{H_0}{\sim} F_{r,n-p}\]
Heart example
try(solve(SigmaContrasts))
## Error in solve.default(SigmaContrasts) :
## Lapack routine dgesv: system is exactly singular: U[3,3] = 0
- We cannot invert the variance matrix of the contrasts!
- Indeed, the contrasts are linear combinations of two parameters and the contrast matrix \(\mathbf{L}\) will thus have rank 2
- We calculate orthogonal contrasts:
qrL <- qr(L)
r <- qrL$rank
r
## [1] 2
Q <- qr.Q(qrL)[,1:r]
rownames(Q) <- rownames(L)
Q
## [,1] [,2]
## (Intercept) 0 0
## locationR 0 0
## tissueV -1 0
## patient4 0 0
## patient8 0 0
## locationR:tissueV 0 -1
## [,1] [,2]
## [1,] 1 0
## [2,] 0 1
Exploring Q shows that assessing the omnibus hypothesis is thus equivalent to assessing if the null hypothesis that \[H_0: \beta_\text{tissue} = \beta_\text{tissue:location} = 0\]
est <- t(Q) %*% betas
SigmaEst <- t(Q) %*% SigmaBeta %*% Q
Fstat <- t(est) %*% solve(SigmaEst) %*% est / r
pOmnibus <- pf(Fstat, r, p, lower.tail = FALSE)
- Comparison with lm results
- We can assess the omnibus hypothesis also by comparing two models
- model with location, tissue, location - tissue interaction and patient effect
- null model: model with location and patient effect
fit0 <- lm(y ~ location + patient, colData(pe))
anova(fit, fit0)
## [,1]
## [1,] 0.02257724
## [,1]
## [1,] 0.9777584
Robust regression
With msqrob2 we perform robust regression to estimate the model parameters of the regression model
No normality assumption needed
Robust fit minimises the maximal bias of the estimators
CI and statistical tests are based on asymptotic theory
If \(\epsilon\) is normal, the M-estimators have a high efficiency!
ordinary least squares (OLS): minimize loss function \[\sum\limits_{i=1}^n (y_i-\mathbf{x}_i^T\boldsymbol{\beta})^2\]
M-estimation: minimize loss function \[\sum\limits_{i=1}^n \rho\left(y_i-\mathbf{x}_i^T\boldsymbol{\beta}\right)\] with
- \(\rho\) is symmetric, i.e. \(\rho(z)=\rho(-z)\)
- \(\rho\) has a minimum at \(\rho(0)=0\), is positive for all \(z\neq 0\)
- \(\rho(z)\) increases as \(\vert z\vert\) increases
The estimator \(\hat{\mu}\) is also the solution to the equation \[
\sum_{i=1}^n \Psi(y_i - \mathbf{x}_i\boldsymbol{\beta}) =0,
\] where \(\Psi\) is the derivative of \(\rho\). For \(\hat{\beta}\) possessing the robustness property, \(\Psi\) should be bounded.
Example: least squares
\(\rho(z) = z^2\), and thus \(\Psi(z)=2z\) (unbounded!). Not robust!
\(\hat{\boldsymbol{\beta}}\) is the solution of \[
\sum_{i=1}^n 2 \mathbf{x}_i (y_i - \mathbf{x}_i^T\boldsymbol{\beta}) = 0 \text{ or } \hat{\boldsymbol{\beta}} = (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}\mathbf{y}
\] with \(\mathbf{X}=[\mathbf{x}_1 \ldots \mathbf{x}_G]^T\)
When a location and a scale parameter, say \(\sigma\), have to be estimated simultaneously, we write \[
(\hat{\boldsymbol{\beta}},\hat{\sigma}) = \text{ArgMin}_{\boldsymbol{\beta},\sigma} \sum_{i=1}^n \rho\left(\frac{y_i - \mathbf{x}_i^T\boldsymbol{\beta}}{\sigma}\right)
\text{ and } \sum_{i=1}^n \Psi\left(\frac{y_i - \mathbf{x}_i^T\boldsymbol{\beta}}{\sigma}\right) =0.
\]
Define \(u_i = \frac{y_i - \mathbf{x}_i^T\boldsymbol{\beta}}{\sigma}\). The last estimation equation is equivalent to \[
\sum_{i=1}^n w(u_i) u_i = 0 ,
\] with weight function \(w(u)=\Psi(u)/u\). This is the typical form that appears when solving the iteratively reweighted least squares problem, \[
(\hat{\boldsymbol{\beta}},\hat{\sigma}) = \text{ArgMin}_{\mu,\sigma} \sum_{i=1}^n w(u_i^{(k-1)}) \left(u_i^{(k)}\right)^2 ,
\] where \(k\) represents the iteration number.
Some Examples of Robust Functions
PhD thesis Bolstad 2004
The \(\rho\) functions
PhD thesis Bolstad 2004
Common \(\Psi\)-Functions
PhD thesis Bolstad 2004
Corresponding Weight Functions
PhD thesis Bolstad 2004
library("MASS")
rfit <- rlm(y ~ location * tissue + patient, colData(pe), maxit=1)
## Warning in rlm.default(x, y, weights, method = method, wt.method = wt.method, :
## 'rlm' failed to converge in 1 steps
qplot(fit$coefficient[-1],
rfit$coefficient[-1],
xlab="fit",
ylab="robust fit") +
geom_abline() +
xlim(range(c(fit$coefficient[-1],rfit$coefficient[-1]))) +
ylim(range(c(fit$coefficient[-1],rfit$coefficient[-1])))
## [1] 0.9516397 1.0000000 0.6628477 1.0000000 1.0000000 1.0000000 1.0000000
## [8] 1.0000000 1.0000000 0.4805187 1.0000000 0.4344049
plot(
rfit$fitted,
rfit$res,
cex=rfit$w,
pch=19,col=2,
cex.lab=1.5,
cex.axis=1.5,
ylab="residuals",
xlab="fit")
points(rfit$fitted, rfit$res , cex= 1.5)
##
## Call:
## lm(formula = y ~ location * tissue + patient, data = colData(pe),
## x = TRUE)
##
## Residuals:
## Min 1Q Median 3Q Max
## -1.29698 -0.32767 0.04041 0.24905 1.17251
##
## Coefficients:
## Estimate Std. Error t value Pr(>|t|)
## (Intercept) 26.57559 0.62760 42.345 1.16e-08 ***
## locationR 0.20636 0.72469 0.285 0.785
## tissueV 0.12757 0.72469 0.176 0.866
## patient4 0.30592 0.62760 0.487 0.643
## patient8 -0.33433 0.62760 -0.533 0.613
## locationR:tissueV -0.04131 1.02486 -0.040 0.969
## ---
## Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
##
## Residual standard error: 0.8876 on 6 degrees of freedom
## Multiple R-squared: 0.1687, Adjusted R-squared: -0.524
## F-statistic: 0.2436 on 5 and 6 DF, p-value: 0.9286
##
## Call: rlm(formula = y ~ location * tissue + patient, data = colData(pe),
## maxit = 1)
## Residuals:
## Min 1Q Median 3Q Max
## -1.51703 -0.22326 0.05909 0.16009 1.26070
##
## Coefficients:
## Value Std. Error t value
## (Intercept) 26.3378 0.5391 48.8585
## locationR 0.2883 0.6225 0.4631
## tissueV 0.2095 0.6225 0.3365
## patient4 0.4654 0.5391 0.8633
## patient8 -0.0261 0.5391 -0.0484
## locationR:tissueV -0.0555 0.8803 -0.0630
##
## Residual standard error: 0.4189 on 6 degrees of freedom
rowData(pe[["proteinRobust"]])$msqrobModels[[2]] %>% getCoef
## (Intercept) locationR tissueV patient4
## 26.33779939 0.28826213 0.20946392 0.46536955
## patient8 locationR:tissueV
## -0.02608046 -0.05550111
Understanding implementation of robust regression
Simulate 20 observations from a linear model with errors that follow a normal distribution
set.seed <- 112358
nobs <- 20
sdy <- 1
xsim <- seq(0, 1, length.out = nobs)
ysim <- 10 + 5*xsim + rnorm(nobs, sd = sdy)
add outlier at high leverage point
fit robust linear model
library(MASS)
mEst <- rlm(ysim ~ xsim)
plot results
plot(xsim, ysim)
abline(ols, lwd = 2)
abline(mEst, col = "red", lwd = 2)
legend("topleft",
legend = c("OLS", "M-estimation"),
lwd = 2,
col = 1:2)
## [1] 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000
## [13] 0.746 1.000 1.000 1.000 1.000 1.000 1.000 0.279
The plot clearly shows that the outlier has a high impact on the slope estimate. This is because the outlier is at a high leverage point, i.e. far from the average covariate pattern.
Implement it yourself
Use robust variance estimator to calculate the z
res <- lmMod$res
stdev <- mad(res)
stdev
## [1] 1.286879
median(abs(res-median(res)))*1.4826
## [1] 1.286879
Calculate weights use psi.huber function
w <- psi.huber(z)
plot(xsim, ysim)
plot(xsim, lmMod$res, cex = w, pch = 19, col = "red")
points(xsim,lmMod$res, cex = 1.5)
Plot results
plot(xsim, ysim)
abline(ols, lwd = 2)
abline(mEst, col = "red", lwd = 2)
abline(lmMod, col = "blue", lwd = 2)
legend("topleft",
legend = c("OLS","M-estimation","Our Impl"),
lwd = 2,
col = c("black", "red", "blue"))
Repeat this many times
lmMod <- ols
for (k in 1:3)
{
######repeat this part several times until convergence
#use robust variance estimator to calculate the z
res <- lmMod$res
stdev <- mad(res)
median(abs(res-median(res)))*1.4826
z <- res/stdev
#calculate weights
#use psi.huber function
w <- psi.huber(z)
#perform a weighted regression use lm with weights=w
lmMod <- lm(ysim ~ xsim, weights = w)
#plot results
plot(xsim,ysim)
abline(ols, lwd = 2)
abline(mEst, col = "red", lwd = 2)
abline(lmMod, col = "blue", lwd = 2)
legend("topleft",
legend = c("OLS","M-estimation","Our Impl"),
lwd = 2,
col = c("black", "red", "blue")
)
####################################
}
Empirical Bayes/Moderated \(t\)-test.
A general class of moderated test statistics is given by
\[\tilde{T}_p = \frac{\mathbf{L}_k \hat{ \boldsymbol{\beta_p}}}{\mathbf{L}_k^T(\mathbf{X}^T\mathbf{WX})^{-1}\mathbf{L}_k^T \tilde{s}_p^2}\]
where \(\tilde{s}_p\) is a moderated variance estimator.
Simple approach: set \(\tilde{s}_p=s_p + s_0\): simply add a small positive constant to the denominator of the t-statistic
theory provides formal framework for borrowing strength across genes or proteins, e.g. popular bioconductor package \[\tilde{s}_g=\sqrt{\frac{d_ps_p^2+d_0s_0^2}{d_g+d_0}},\] and the moderated t-statistic is t-distributed with \(d_0+d_g\) degrees of freedom under the null hypothesis \(H_0: \mathbf{L}\boldsymbol{\beta}=0\).
- Note, that the degrees of freedom increase by borrowing strength across proteins.
Intermezzo: Bayesian Methods
Frequentists consider data as random and population parameters as fixed but unknown
In Bayesian viewpoint a person has prior beliefs about the population parameters and the uncertainty on this prior beliefs are represented by a probability distribution placed on this parameter.
- This distribution reflects the person’s subjective prior opinion about plausible values of the parameter.
- And is referred to as the prior \(g(\boldsymbol{\theta})\).
Bayesian thinking will update the prior information on the population parameters by confronting the model to data (\(\mathbf{Y}\)).
By using Bayes Theorem this results in a posterior distribution on the model parameters.
\[
g(\boldsymbol{\theta}\vert\mathbf{Y})=\frac{f(Y\vert \boldsymbol{\theta})g(\boldsymbol{\theta})}{\int f(Y\vert \boldsymbol{\theta}) g(\boldsymbol{\theta}) d\boldsymbol{\theta}} \text{ }\left(\text{ posterior}=\frac{\text{prior} \times \text{ likelihood}}{\text{Marginal distribution}}\right)
\]
Limma approach
Developed for gene expression analysis with micro arrays. Let g be the index for gene g. \[
\begin{array}{cc}
&\beta_{gk}\vert \sigma^2_g,\beta_{gk}\neq 0 \sim N(0,v_{0k}\sigma_g^2)\\\\
\text{Prior}\\
&\frac{1}{\sigma^2_g}\sim s^2_0\frac{\chi^2_{d_0}}{d_0}\\\\\\\\
&\hat \beta_{gk} | \beta_{gk} , \sigma_g^2 \sim N( \beta_{gk} , v_{gk}\sigma_g^2)\\\\
\text{Data}\\
&s_g^2\sim \sigma^2_g\frac{\chi^2_{d_g}}{d_g}\\\\
\end{array}
\]
Limma approach
Under this assumption, it can be shown that
Posterior Mean for the variance parameter: \[\tilde{s}^2_p = \text{E}\left[\sigma^2_p\vert s_p^2\right]=\frac{d_0 s_0^2+d_ps_p^2}{d_0+d_p}\]
\[\tilde{T}_p=\frac{\mathbf{L}_k \hat{ \boldsymbol{\beta_p}}}{\mathbf{L}_k^T(\mathbf{X}^T\mathbf{WX})^{-1}\mathbf{L}_k^T \tilde{s}_p^2}\]
is t-distributed under \(H_0: \mathbf{L}_j\boldsymbol{\beta} = 0\)
\[\tilde{T}_p \vert H_0 \sim t(d_0 + d_p)\]
Empirical Bayes
- A fully Bayesian
- would define the prior distribution by carefully choosing the prior parameters based on prior knowledge on the process
- would confront the prior to the data and performs inference using the posterior distribution of the model parameters.
- In an empirical Bayesian approach one estimates the prior parameters based on the data.
- In Limma moment estimators for \(s_0\) and \(d_0\) are derived using the information on the gene (protein) wise variances of all genes (proteins).
- In Limma one also does not work with the full posterior distribution for the variances, but with the maximum a-posterior estimate.
Illustration
We borrow strength across proteins by
- placing a scaled \(\chi^2\) prior: \(\chi^2(s_o,d_0)\) on the precisions (\(1/\sigma^2_p\))
- estimating the prior parameters \(s_0\) and \(df_0\)
- replacing the estimated protein-wise variances (\(s_p^2\)) with the maximum a-posteriori variance \[\tilde{s}_p = \frac{d_p s^2_p + d_0 s_0^2}{d_p+d_0}\]
sd <- sapply(
rowData(pe[["proteinRobust"]])$msqrobModels,
getSigma) %>%
na.exclude
sdPost <- sapply(
rowData(pe[["proteinRobust"]])$msqrobModels,
getSigmaPosterior) %>%
na.exclude
p1 <- qplot(sd,sdPost) +
geom_abline()
p1
How do we get to the posterior standard deviation?
hlp <- limma::squeezeVar(
var = sapply(rowData(pe[["proteinRobust"]])$msqrobModels, getVar),
df = sapply(rowData(pe[["proteinRobust"]])$msqrobModels, getDF)
)
Degrees of freedom of prior
## [1] 3.385413
model <- rowData(pe[["proteinRobust"]])$msqrobModels[[2]]
getDfPosterior(model) - getDF(model)
## [1] 3.385413
posterior variance
\[\tilde s_p=\sqrt{\frac{d_p\times s^2_p + d_0 s_0^2}{d_p+d_0}} \]
## [1] 0.2489859
varPost <- (getVar(model) * getDF(model) + hlp$df.prior * hlp$var.prior)/(getDF(model)+hlp$df.prior)
sqrt(varPost)
## [1] 0.6607153
## [1] 0.6607153
Hence, standard deviations are shrunken towards prior standard deviation! Large standard deviations become smaller and smaller standard deviations become larger!
p1 +
geom_hline(yintercept = hlp$var.prior^.5)
Illustration via Simulation
Suppose that the standard deviations for all proteins are the same and are equal to 1. We simulate proteins with the same mean as the fitted mean in the experiment but with standard deviation of 1.
nCoefs <- getCoef(rowData(pe[["proteinRobust"]])$msqrobModels[[2]]) %>% length
coefs <-
sapply(rowData(pe[["proteinRobust"]])$msqrobModels,
function(x) getCoef(x)[1:nCoefs]
) %>%
t %>%
na.exclude
p <- nrow(coefs)
n <- ncol(pe[[1]])
f0_equalVar <- sapply(1:p,
FUN=function(i, n, betas, sd, design) {
rnorm(n, mean = design %*% betas[i,], sd = sd)},
n = n,
betas = coefs,
sd = 1,
design = X
) %>%
t
colnames(f0_equalVar) <- colnames(pe[[1]])
sims <- readQFeatures(f0_equalVar %>% as.data.frame, ecol = 1:n, name = "sim_equalVar")
colData(sims) <- colData(pe)
sims <- msqrob(object = sims, i = "sim_equalVar", formula = ~ location*tissue + patient)
sd0 <- sapply(
rowData(sims[["sim_equalVar"]])$msqrobModels,
getSigma) %>%
na.exclude
sdPost0 <- sapply(
rowData(sims[["sim_equalVar"]])$msqrobModels,
getSigmaPosterior) %>%
na.exclude
qplot(sd0,sdPost0) +
geom_abline() +
ylim(range(sd0))
- We observe a large variability in the individual protein level standard deviation estimates.
- We simulated proteins with standard deviation of 1, but the protein estimates vary from 0.14, … , 1.98.
- Large uncertainty on the estimation of variances in small samples
- The empirical Bayes method, however, recognises that all proteins are simulated with the same variance.
- Hence, it can borrow tremendous strength across proteins to stabilize the variance estimation
- Here, it shrinks all protein variance to the prior variance, which is indeed very close to 1, the value we have adopted in the simulation.
Note, that the prior degree of freedom also is set to infinity:
getDF(rowData(sims[["sim_equalVar"]])$msqrobModels[[1]])
## [1] 5.739512
getDfPosterior(rowData(sims[["sim_equalVar"]])$msqrobModels[[1]])
## [1] Inf
which imposes shrinkage to the prior standard deviation!
The empirical Bayes method can thus indeed recognise the common variance that is shared across proteins!
P-values
Simulation under H_0.
- Mean log2 protein intensity for atrium equals mean log2 protein intensity for ventriculum in the left heart region.
- sd equals the sd for the protein.
- Extract \(\hat \sigma\) and \(\beta\)’s
sd <- sapply(
rowData(pe[["proteinRobust"]])$msqrobModels,
getSigma) %>%
na.exclude
coefs <-
sapply(rowData(pe[["proteinRobust"]])$msqrobModels,
function(x) getCoef(x)[1:nCoefs]
) %>%
t %>%
na.exclude
- Set \(\beta_\text{tissue}\) equal to 0. No FC between atrium and ventriculum left.
coefs0 <- coefs
coefs0[,3] <- 0
- Simulate protein expressions for each protein from a Normal distribution under \(H_0\) for left heart region (no FC between atrium and ventriculum left) and sd the sd for the protein.
set.seed(104)
f0 <- sapply(1:p,
function(i, betas, sd, design)
rnorm(n, mean = design %*% betas[i,], sd = sd[i]),
betas = coefs0,
sd = sd,
design = X
) %>%
t
colnames(f0) <- colnames(pe[[1]])
- Setup QFeatures object and perform MSqRob analysis
sims <- readQFeatures(f0 %>% as.data.frame, ecol = 1:n, name = "sim0")
colData(sims) <- colData(pe)
sims <- msqrob(object = sims, i = "sim0", formula = ~ location*tissue + patient)
sims <- hypothesisTest(object = sims, i = "sim0", contrast = L)
Evaluate pvalues under H_0
volcano <- ggplot(rowData(sims[["sim0"]])$tissueV,
aes(x = logFC, y = -log10(pval), color = pval < 0.05)) +
geom_point(cex = 2.5) +
scale_color_manual(values = alpha(c("black", "red"), 0.5)) + theme_minimal()
volcano
Number of false positives without multiple testing?
rowData(sims[["sim0"]])$tissueV %>%
filter(pval <0.05) %>%
nrow
## [1] 115
mean(rowData(sims[["sim0"]])$tissueV$pval < 0.05)
## [1] 0.05665025
hist(rowData(sims[["sim0"]])$tissueV$pval,main = "simulation H0")
- The p-values are uniform!
- All p-values under the null are equally likely.
- Statistical hypthesis testing leads to a uniform test strategy under \(H_0\)
- If use p-value cutoff at 0.05 we expect to return 5% of the non-DE proteins as differentially expressed: many false positives can be expected!
Pvalue distribution in real experiment
hist(rowData(pe[["proteinRobust"]])$tissueV$pval, main = "realData")
- A mixture of null proteins (non-DE): uniform, and, DE proteins: enrichment of p-values at low p-values
Correction for multiple testing
- We can adjust the p-values for multiple testing.
Family wise error rate correction:
A list of returned proteins is considered to be in error as soon as it contains at most one false positive protein.
\(\text{FWER} = P(FP \leq 1)\)
FWER: probability of making at least one false positive decision or probability to declare at least one protein differentially abundant which is truly non differentially abundant
Bonferroni method
- Simple method
- \(m\) tests are performed at the level \(\alpha/m\)
- FWER\(\leq\sum\limits_{p=1}^{m}P(reject H_{0p}\vert H_{0p}\text{ is true})=m \alpha/m=\alpha\)
- Provides strong control
- Bonferroni is very conservative
- Works for dependent tests
- Adjusted p-value: \(\tilde{p}_p=\min(m\ p_p,1)\)
Bonferroni in practise
Via R functions
padj <- p.adjust(
rowData(pe[["proteinRobust"]])$tissueV$pval,
method = "bonferroni")
Own Implementation: adjust and make sure that p-value is smaller than 1.
m <- sum(!is.na(rowData(pe[["proteinRobust"]])$tissueV$pval))
padjSelf <- rowData(pe[["proteinRobust"]])$tissueV$pval * m
padjSelf[padjSelf > 1] <- 1
range(padj - padjSelf, na.rm = TRUE)
## [1] 0 0
Illustration in simulation under \(H_0\) and heart case study
volcano <- ggplot(rowData(sims[["sim0"]])$tissueV,
aes(x = logFC, y = -log10(pval), color = p.adjust(pval,"bonferroni") < 0.05)) +
geom_point(cex = 2.5) +
scale_color_manual(values = alpha(c("black", "red"), 0.5)) +
theme_minimal() +
ggtitle("simulated heart data under H0")
volcano
- No false positives are returned for simulation under H_0. List is correct according to FWER.
volcano <- ggplot(rowData(pe[["proteinRobust"]])$tissueV,
aes(x = logFC, y = -log10(pval), color = p.adjust(pval,"bonferroni") < 0.05)) +
geom_point(cex = 2.5) +
scale_color_manual(values = alpha(c("black", "red"), 0.5)) +
theme_minimal() +
ggtitle("real heart data")
volcano
## Warning: Removed 1263 rows containing missing values (geom_point).
- Very few proteins are returned for real data. Very conservative!
FWER: step down method of Holm
- Compare smallest p-value with \(\alpha/m\)
- If you can reject the smallest p-value at \(\alpha/m\) level
- asses second smallest p-value at the \(\alpha/(m-1)\)
- If you can reject the second smallest p-value at \(\alpha/(m-1)\) level
- asses third smallest p-value at the \(\alpha/(m-2)\)
- …
- If you can reject the k-1 smallest p-value at \(\alpha/(m-k+2)\) level
- asses k smallest p-value at the \(\alpha/(m-k+1)\) level
- continu as long as you can reject.
The Holm is a step down method (from more to less significant) that corrects in each step for the number of null hypothesis that you still can falsely reject.
Adjusted p-values:
- Order p-values with \((k)\) the \(k^{th}\) smallest p-value
- \(\tilde{p}_{(k)}=\min(p_{(k)}(m-k+1),1)\)
Suppose 2 tests: \(p_{(1)}=0.001\), \(p_{(2)}=0.0015\) \(\rightarrow\) \(\tilde{p}_{(1)}=0.002\), \(\tilde{p}_{(2)}=0.0015\)
- Problem: Monotonicity is not the same as for original p-values!
- Enforce monotonicity: \(\tilde{p}_{(k)}=\max\limits_{h=1,\ldots,k}\min(p_{(h)}(m-h+1),1)\)
Holm example
With R functions:
padj <- p.adjust(
rowData(pe[["proteinRobust"]])$tissueV$pval,
method = "holm")
Own implementation
- Order p-values
padjSelf <- rowData(pe[["proteinRobust"]])$tissueV$pval
ord <- order(padjSelf)
pOrd <- padjSelf[ord]
m <- sum(!is.na(padjSelf))
- Adjust ordered p-values and ensure that value is not larger than 1
pOrd[1:m] <- pOrd[1:m]*(m - (1:m) + 1)
pOrd[pOrd>1] <- 1
- Monotonicity
pmax <- pOrd[1]
for (i in 2:m)
{
if (pOrd[i] > pmax)
pmax <- pOrd[i] else
pOrd[i] <- pmax
}
- Put adjusted p-values in original order
padjSelf[ord] <- pOrd
range(padj - padjSelf, na.rm = TRUE)
## [1] 0 0
Illustration in simulation under \(H_0\) and heart case study
volcano <- ggplot(rowData(sims[["sim0"]])$tissueV,
aes(x = logFC, y = -log10(pval), color = p.adjust(pval,"holm") < 0.05)) +
geom_point(cex = 2.5) +
scale_color_manual(values = alpha(c("black", "red"), 0.5)) +
theme_minimal() +
ggtitle("simulated heart data under H0")
volcano
- No false positives are returned for simulation under H_0. List is correct according to FWER.
volcano <- ggplot(rowData(pe[["proteinRobust"]])$tissueV,
aes(x = logFC, y = -log10(pval), color = p.adjust(pval,"holm") < 0.05)) +
geom_point(cex = 2.5) +
scale_color_manual(values = alpha(c("black", "red"), 0.5)) +
theme_minimal() +
ggtitle("real heart data")
volcano
## Warning: Removed 1263 rows containing missing values (geom_point).
- Very few proteins are returned for real data. Still very conservative!
False discovery rate
- Adjusted P-values with the Benjamini Hochberg correction correspond to the estimated FDR of the set that is returned when the significance level is set at this threshold. \[\begin{eqnarray}
FDR(p_0) &=& \text{E}\left[\frac{FP}{(FP + TP)}\right]\\
&\approx&\frac{p_0 \times m}{\#p_p \leq p_0}\\
\end{eqnarray}\]
So adjusted p-value for protein j equals \[\tilde p_j = \frac{p_{0,j} \times m}{\#p_p \leq p_{0,j}}\]
However, the FDR always has to be between 0 and 1 so:
\[\tilde p_j = \min\left[\frac{p_{0,j} \times m}{\#p_p \leq p_{0,j}},1\right]\]
and the adjusted p-values should remain in the same order as the original p-values.
\[\tilde p_j = \min\limits_{\forall k: p_k > p_j} \min\left[\frac{p_{0,k} \times m}{\#p_p \leq p_{0,k}},1\right]\]
- Order pvalues
pvals <- rowData(pe[["proteinRobust"]])$tissueV$pval
naInd <- is.na(pvals)
pHlp <- pvals[!naInd]
ord <- pHlp %>% order
pHlp <- pHlp[ord]
- Adjust ordered p-values
pHlp <- pHlp*length(pHlp)/(1:length(pHlp))
- Ensure adjust p-values are smaller are equal than 1
- Monotonicity constraint
pmin <- pHlp[length(pHlp)]
for (j in (length(pHlp)-1):1)
{
if (pHlp[j] < pmin)
pmin <- pHlp[j] else
pHlp[j] <- pmin
}
- Put p-values back in original order
pHlp[ord] <- pHlp
pAdj <- pvals
pAdj[!naInd] <- pHlp
head(pAdj)
## [1] NA 0.8351039 NA NA 0.9062353 NA
head(rowData(pe[["proteinRobust"]])$tissueV)
range(rowData(pe[["proteinRobust"]])$tissueV$adjPval - pAdj,na.rm=TRUE)
## [1] -2.220446e-16 2.220446e-16
Illustration in simulation under \(H_0\) and heart case study
volcano <- ggplot(rowData(sims[["sim0"]])$tissueV,
aes(x = logFC, y = -log10(pval), color = adjPval < 0.05)) +
geom_point(cex = 2.5) +
scale_color_manual(values = alpha(c("black", "red"), 0.5)) +
theme_minimal() +
ggtitle("simulated heart data under H0")
volcano
- No false positives are returned for simulation under H_0. List is correct according to FWER.
- It can be shown that the FDR-method controls the FWER when \(H_0\) is true for all features.
volcano <- ggplot(rowData(pe[["proteinRobust"]])$tissueV,
aes(x = logFC, y = -log10(pval), color = adjPval < 0.05)) +
geom_point(cex = 2.5) +
scale_color_manual(values = alpha(c("black", "red"), 0.5)) +
theme_minimal() +
ggtitle("real heart data")
volcano
## Warning: Removed 1263 rows containing missing values (geom_point).
The FDR method allows us to return much longer DA protein lists at the expense of a few false positives. The FDR controls the fraction of false positives in the list that you return on average on the significance level that is adopted. So if you use \(\alpha=0.05\) we expect on average 5% of false positives in the list that we return.
LS0tCnRpdGxlOiAiVGVjaG5pY2FsIGRldGFpbHMgb24gbGluZWFyIHJlZ3Jlc3Npb24gZm9yIHByb3Rlb21pY3Mgd2hlbiBzdGFydGluZyBmcm9tIHN1bW1hcml6ZWQgcHJvdGVpbiBleHByZXNzaW9uIHZhbHVlcyIKYXV0aG9yOiAiTGlldmVuIENsZW1lbnQiCmRhdGU6ICJzdGF0T21pY3MsIEdoZW50IFVuaXZlcnNpdHkgKGh0dHBzOi8vc3RhdG9taWNzLmdpdGh1Yi5pbykiCm91dHB1dDoKICAgIGh0bWxfZG9jdW1lbnQ6CiAgICAgIGNvZGVfZG93bmxvYWQ6IHRydWUKICAgICAgdGhlbWU6IGNvc21vCiAgICAgIHRvYzogdHJ1ZQogICAgICB0b2NfZmxvYXQ6IHRydWUKICAgICAgaGlnaGxpZ2h0OiB0YW5nbwogICAgICBudW1iZXJfc2VjdGlvbnM6IHRydWUKLS0tCgojIFByZWFtYmxlCgpSZWFkIHN0b3JlZCByZXN1bHRzIGZvciBoZWFydCBkYXRhCgpgYGB7ciwgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkobGltbWEpCmxpYnJhcnkoUUZlYXR1cmVzKQpsaWJyYXJ5KG1zcXJvYjIpCnBlIDwtIHJlYWRSRFMoCiAgdXJsKAogICAgImh0dHBzOi8vcmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbS9zdGF0T21pY3MvU0dBMjAyMC9naC1wYWdlcy9hc3NldHMvcGVIZWFydC5yZHMiLAogICAgInJiIikKICApCmBgYAoKIyBMaW5lYXIgcmVncmVzc2lvbgoKLSBDb25zaWRlciBhIHZlY3RvciBvZiBwcmVkaWN0b3JzICRcbWF0aGJme3h9X2k9KHhfMSxcbGRvdHMseF97cC0xfSkkIGFuZAotIGEgcmVhbC12YWx1ZWQgcmVzcG9uc2UgJFlfaSQKLSB3aXRoICRpID0gMSwgXGxkb3RzLCBuJAotIHRoZW4gdGhlIGxpbmVhciByZWdyZXNzaW9uIG1vZGVsIGNhbiBiZSB3cml0dGVuIGFzClxbCllfaT1mKFxtYXRoYmZ7eH0pICtcZXBzaWxvbj1cYmV0YV8wK1xzdW1cbGltaXRzX3tqPTF9XntwLTF9IHhfe2lqfVxiZXRhICsgXGVwc2lsb25faQpcXQp3aXRoIGkuaS5kLiAkXGVwc2lsb25faVxzaW0gTigwLFxzaWdtYV4yKSQKCi0tLQoKLSAkbiQgb2JzZXJ2YXRpb25zICQoXG1hdGhiZnt4fV8xLHlfMSkgXGxkb3RzIChcbWF0aGJme3h9X24seV9uKSQKLSBSZWdyZXNzaW9uIGluIG1hdHJpeCBub3RhdGlvbgpcW1xtYXRoYmZ7WX09XG1hdGhiZntYXGJldGF9ICsgXGJvbGRzeW1ib2x7XGVwc2lsb259XF0Kd2l0aCAkXG1hdGhiZntZfT1cbGVmdFtcYmVnaW57YXJyYXl9e2N9eV8xXFwgXHZkb3RzXFx5X25cZW5ke2FycmF5fVxyaWdodF0kLAokXG1hdGhiZntYfT1cbGVmdFtcYmVnaW57YXJyYXl9e2NjY2N9IDEmeF97MTF9JlxsZG90cyZ4X3sxcC0xfVxcClx2ZG90cyZcdmRvdHMmJlx2ZG90c1xcCjEmeF97bjF9JlxsZG90cyZ4X3tucC0xfQpcZW5ke2FycmF5fVxyaWdodF0kLAokXGJvbGRzeW1ib2x7XGJldGF9PVxsZWZ0W1xiZWdpbnthcnJheX17Y31cYmV0YV8wXFwgXHZkb3RzXFwgXGJldGFfe3AtMX1cZW5ke2FycmF5fVxyaWdodF0kIGFuZAokXGJvbGRzeW1ib2x7XGVwc2lsb259PVxsZWZ0W1xiZWdpbnthcnJheX17Y30gXGVwc2lsb25fMSBcXCBcdmRvdHMgXFwgXGVwc2lsb25fblxlbmR7YXJyYXl9XHJpZ2h0XSQKCi0tLQoKIyMgTGVhc3QgU3F1YXJlcyAoTFMpCgotIE1pbmltaXplIHRoZSByZXNpZHVhbCBzdW0gb2Ygc3F1YXJlcwpcYmVnaW57ZXFuYXJyYXkqfQpSU1MoXGJvbGRzeW1ib2x7XGJldGF9KSY9JlxzdW1cbGltaXRzX3tpPTF9Xm4gZV4yX2lcXAomPSZcc3VtXGxpbWl0c197aT0xfV5uIFxsZWZ0KHlfaS1cYmV0YV8wLVxzdW1cbGltaXRzX3tqPTF9XnAgeF97aWp9XGJldGFfalxyaWdodCleMgpcZW5ke2VxbmFycmF5Kn0KLSBvciBpbiBtYXRyaXggbm90YXRpb24KXGJlZ2lue2VxbmFycmF5Kn0KUlNTKFxib2xkc3ltYm9se1xiZXRhfSkmPSYoXG1hdGhiZntZfS1cbWF0aGJme1hcYmV0YX0pXlQoXG1hdGhiZntZfS1cbWF0aGJme1hcYmV0YX0pXFwKJj0mXFZlcnQgXG1hdGhiZntZfS1cbWF0aGJme1hcYmV0YX1cVmVydF4yClxlbmR7ZXFuYXJyYXkqfQp3aXRoIHRoZSAkTF8yJC1ub3JtIG9mIGEgJHAkLWRpbS4gdmVjdG9yICR2JCAkXFZlcnQgXG1hdGhiZnt2fSBcVmVydD1cc3FydHt2XzFeMitcbGRvdHMrdl9wXjJ9JAoKLSAkXHJpZ2h0YXJyb3ckICRcaGF0e1xib2xkc3ltYm9se1xiZXRhfX09XHRleHR7YXJnbWlufV9cYmV0YSBcVmVydCBcbWF0aGJme1l9LVxtYXRoYmZ7WFxiZXRhfVxWZXJ0XjIkfQoKCi0tLQoKIyMjIE1pbmltaXplIFJTUwpcWwpcYmVnaW57YXJyYXl9e2NjY30KXGZyYWN7XHBhcnRpYWwgUlNTfXtccGFydGlhbCBcYm9sZHN5bWJvbHtcYmV0YX19Jj0mXG1hdGhiZnswfVxcXFwKXGZyYWN7KFxtYXRoYmZ7WX0tXG1hdGhiZntYXGJldGF9KV5UKFxtYXRoYmZ7WX0tXG1hdGhiZntYXGJldGF9KX17XHBhcnRpYWwgXGJvbGRzeW1ib2x7XGJldGF9fSY9JlxtYXRoYmZ7MH1cXFxcCi0yXG1hdGhiZntYfV5UKFxtYXRoYmZ7WX0tXG1hdGhiZntYXGJldGF9KSY9JlxtYXRoYmZ7MH1cXFxcClxtYXRoYmZ7WH1eVFxtYXRoYmZ7WFxiZXRhfSY9JlxtYXRoYmZ7WH1eVFxtYXRoYmZ7WX1cXFxcClxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fSY9JihcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9XG1hdGhiZntYfV5UXG1hdGhiZntZfQpcZW5ke2FycmF5fQpcXQoKLS0tCgojIyMjIEhlYXJ0IGV4YW1wbGUKCmBgYHtyfQp5IDwtIGFzc2F5KHBlW1sicHJvdGVpblJvYnVzdCJdXSlbMixdCmZpdCA8LSBsbSh5IH4gbG9jYXRpb24qdGlzc3VlICsgcGF0aWVudCwgZGF0YSA9IGNvbERhdGEocGUpLCB4ID0gVFJVRSkKaGVhZChmaXQkeCw0KQpgYGAKClRoZSBtb2RlbCBtYXRyaXggY2FuIGFsc28gYmUgb2J0YWluZWQgd2l0aG91dCBmaXR0aW5nIHRoZSBtb2RlbDoKCmBgYHtyfQpYIDwtIG1vZGVsLm1hdHJpeCh+IGxvY2F0aW9uICogdGlzc3VlICsgcGF0aWVudCwgY29sRGF0YShwZSkpCmhlYWQoWCw0KQpgYGAKCkxlYXN0IHNxdWFyZXM6CmBgYHtyfQpiZXRhcyA8LSBzb2x2ZSh0KFgpJSolWCkgJSolIHQoWCkgJSolIHkKY2JpbmQoZml0JGNvZWYsIGJldGFzKQpgYGAKCi0tLQoKIyMjIFZhcmlhbmNlIEVzdGltYXRvcj8KXFsKXGJlZ2lue2FycmF5fXtjY2x9ClxoYXR7XGJvbGRzeW1ib2x7XFNpZ21hfX1fe1xoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX0KJj0mXHRleHR7dmFyfVxsZWZ0WyhcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9XG1hdGhiZntYfV5UXG1hdGhiZntZfVxyaWdodF1cXFxcCiY9JihcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9XG1hdGhiZntYfV5UXHRleHR7dmFyfVxsZWZ0W1xtYXRoYmZ7WX1ccmlnaHRdXG1hdGhiZntYfShcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9XFxcXAomPSYoXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxtYXRoYmZ7WH1eVChcbWF0aGJme0l9XHNpZ21hXjIpXG1hdGhiZntYfShcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9ClxcXFwKJj0mKFxtYXRoYmZ7WH1eVFxtYXRoYmZ7WH0pXnstMX1cbWF0aGJme1h9XlRcbWF0aGJme0l9XHF1YWRcbWF0aGJme1h9KFxtYXRoYmZ7WH1eVFxtYXRoYmZ7WH0pXnstMX1cc2lnbWFeMlxcXFwKJVxoYXR7XGJvbGRtYXRoe1xTaWdtYX19X3tcaGF0e1xib2xkc3ltYm9se1xiZXRhfX19Jj0mKFxtYXRoYmZ7WH1eVFxtYXRoYmZ7WH0pXnstMX1cbWF0aGJme1h9XlRcdmFyXGxlZnRbXG1hdGhiZntZfVxyaWdodF0oXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxtYXRoYmZ7WH1cXAomPSYoXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxtYXRoYmZ7WH1eVFxtYXRoYmZ7WH0oXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxzaWdtYV4yXFxcXAomPSYoXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxzaWdtYV4yClxlbmR7YXJyYXl9ClxdCgotLS0KCiMjIyMgaGVhcnQgZXhhbXBsZQoKCmBgYHtyfQpzdW1tYXJ5KGZpdCkkY292LnVuc2NhbGVkICogc2lnbWEoZml0KV4yCmBgYAoKYGBge3J9Cm4gPC0gbnJvdyhYKQpwIDwtIG5jb2woWCkKbXNlIDwtIHN1bSgoeS1YJSolYmV0YXMpXjIpLyhuLXApClNpZ21hQmV0YSA8LSBzb2x2ZSh0KFgpJSolWCkgKiBtc2UgICAKU2lnbWFCZXRhCnJhbmdlKFNpZ21hQmV0YSAtIHN1bW1hcnkoZml0KSRjb3YudW5zY2FsZWQgKiBzaWdtYShmaXQpXjIpCmBgYAoKYGBge3J9CmRhdGEuZnJhbWUoc3VtbWFyeShmaXQpJGNvZWZbLDE6Ml0sIGJldGFzID0gYmV0YXMsIHNlQmV0YXMgPSBkaWFnKFNpZ21hQmV0YSleLjUpCmBgYAoKIyMgQ29udHJhc3RzCgpXaGVuIHdlIGFzc2VzcyBhIGNvbnRyYXN0IHdlIGFzc2VzcyBhIGxpbmVhciBjb21iaW5hdGlvbiBvZiBtb2RlbCBwYXJhbWV0ZXJzOgoKXFsgSF8wOiBcbWF0aGJme0xeVFxiZXRhfSA9IDAgXHRleHR7IHZzIH0gSF8xOiBcbWF0aGJme0xeVFxiZXRhfSBcbmVxIDAgXF0KCkVzdGltYXRvciBvZiBDb250cmFzdD8KClxbXG1hdGhiZntMfV5UXGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19XF0KCgpWYXJpYW5jZT8KClxbClxib2xkc3ltYm9se1xTaWdtYX1fe1xtYXRoYmZ7TH1caGF0e1xib2xkc3ltYm9se1xiZXRhfX19PVxtYXRoYmZ7TH1eVFxib2xkc3ltYm9se1xTaWdtYX1fe1xoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX1cbWF0aGJme0x9ClxdCgotLS0KCiMjIyBoZWFydCBleGFtcGxlCgpgYGB7cn0KTCA8LSBtYWtlQ29udHJhc3QoCiAgYygKICAgICJ0aXNzdWVWID0gMCIsCiAgICAidGlzc3VlViArIGxvY2F0aW9uUjp0aXNzdWVWID0gMCIsCiAgICAidGlzc3VlViArIDAuNSpsb2NhdGlvblI6dGlzc3VlViA9IDAiLCJsb2NhdGlvblI6dGlzc3VlViA9IDAiKSwKICBwYXJhbWV0ZXJOYW1lcyA9CiAgICByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkbXNxcm9iTW9kZWxzW1syXV0gJT4lCiAgICBnZXRDb2VmICU+JQogICAgbmFtZXMKICApCkwKYGBgCgpgYGB7cn0KY29udHJhc3RzIDwtIHQoTCkgJSolIGJldGFzClNpZ21hQ29udHJhc3RzIDwtIHQoTCkgJSolIFNpZ21hQmV0YSAlKiUgTApzZUNvbnRyYXN0cyA8LSBTaWdtYUNvbnRyYXN0cyAlPiUKICBkaWFnICU+JQogIHNxcnQKYGBgCgpDb21wYXJpc29uIHdpdGggbG0gYW5kIGdsaHQgcmVzdWx0cwoKYGBge3J9CmxpYnJhcnkobXVsdGNvbXApCmZpdEdsaHQgPC0gZ2xodChmaXQsIGxpbmZjdCA9IHQoTCkpCnN1bW1hcnkoZml0R2xodCwgdGVzdCA9IGFkanVzdGVkKCJub25lIikpCmRhdGEuZnJhbWUoY29udHJhc3RzLCBzZUNvbnRyYXN0cykKYGBgCgotIE5vdGUsIHRoYXQgdGhlIHBvd2VyIGZvciBhc3Nlc3NpbmcgJFxsb2dfMiQgRkMgYmV0d2VlbiB2ZW50cmljdWx1bSBhbmQgYXRyaXVtICBsZWZ0IGFuZCByaWdodCBpcyB0aGUgc2FtZS4gSW5kZWVkLCB0aGUgc3RhbmRhcmQgZXJyb3JzIGFyZSBlcXVhbCBmb3IgYm90aCBlZmZlY3RzLgoKCi0gTm90ZSwgdGhhdCB0aGUgcG93ZXIgZm9yIGFzc2Vzc2luZyAkXGxvZ18yJCBGQyBiZXR3ZWVuIHZlbnRyaWN1bHVtIGFuZCBhdHJpdW0gb3ZlciBib3RoIGhlYXJ0IHJlZ2lvbnMgaXMgaGlnaGVyIHRoYW4gd2hlbiBhc3Nlc3NpbmcgdGhlIGVmZmVjdCBsZWZ0IG9yIHJpZ2h0LgoKICAtIEluZGVlZCwgdGhlIHN0YW5kYXJkIGVycm9yIGlzIGEgZmFjdG9yICRcc3FydHsyfSQgc21hbGxlciBmb3IgdGhlIGZvcm1lciBlZmZlY3QKICAtIFdlIGludHVpdGl2ZWx5IGNhbiBleHBsYWluIHRoaXMgYmVjYXVzZSB3ZSBjYW4gdXNlIGFsbCBzYW1wbGVzIChkb3VibGUgdGhlIG51bWJlciBvZiBzYW1wbGVzKSB0byBhc3Nlc3MgdGhlIGF2ZXJhZ2UgZWZmZWN0LgogIC0gSGVuY2UgdGhlIHZhcmlhbmNlIGlzIGEgZmFjdG9yIHR3byBzbWFsbGVyLCBhbmQgdGhlIHNlIHdpdGggYSBmYWN0b3IgJFxzcXJ0ezJ9JAoKLSBOb3RlLCB0aGF0IHdlIGhhdmUgdGhlIGxvd2VzdCBwb3dlciB0byBwaWNrIHVwIGFuIGludGVyYWN0aW9uIGVmZmVjdC4gSW5kZWVkLCB0aGUgc2UgaXMgYSBmYWN0b3IgJFxzcXJ0ezJ9JCBsYXJnZXIgdGhhbiBmb3IgdGhlIHZlbnRyaWN1bHVtIC0gYXRyaXVtIGVmZmVjdCBsZWZ0IG9yIHJpZ2h0IGFuZCBhIGZhY3RvciAyIGxhcmdlciB0aGFuIGZvciB0aGUgYXZlcmFnZSBlZmZlY3QgYmV0d2VlbiB2ZW50cmljdWx1bSBhbmQgYXRyaXVtLgoKYGBge3J9CnNlQ29udHJhc3RzIC8gc2VDb250cmFzdHNbMV0Kc3FydCgyKQoxL3NxcnQoMikKYGBgCgojIyMgdC10ZXN0cwoKIC0gV2hlbiB0aGUgYXNzdW1wdGlvbnMgb2YgdGhlIGxpbmVhciBtb2RlbCBob2xkClxbClxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fSBcc2ltIE1WTlxsZWZ0W1xib2xkc3ltYm9se1xiZXRhfSxcbGVmdChcbWF0aGJme1h9XlRcbWF0aGJme1h9XHJpZ2h0KV57LTF9XHNpZ21hXjJccmlnaHRdClxdCi0gSGVuY2UsClxbClxtYXRoYmZ7TH1eVFxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fSBcc2ltIE1WTlxsZWZ0W1xtYXRoYmZ7TH1eVFxib2xkc3ltYm9se1xiZXRhfSxcbWF0aGJme0x9XlRcbGVmdFtcbGVmdChcbWF0aGJme1h9XlRcbWF0aGJme1h9XHJpZ2h0KV57LTF9XHNpZ21hXjJccmlnaHRdXG1hdGhiZntMfVxyaWdodF0KXF0KLSBXZSBlc3RpbWF0ZSAkXHNpZ21hXjIkIGJ5IE1TRQokJFxoYXR7XHNpZ21hfV4yPVxmcmFje1xtYXRoYmZ7ZX1eVFxtYXRoYmZ7ZX19e24tcH0gXHJpZ2h0YXJyb3cgXGhhdHtcYm9sZHN5bWJvbHtcU2lnbWF9fV97XGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19fT1cbGVmdChcbWF0aGJme1h9XlRcbWF0aGJme1h9XHJpZ2h0KV57LTF9XGhhdFxzaWdtYV4yJCQKCi0gV2hlbiB3ZSB0ZXN0IG9uZSBjb250cmFzdCBhdCB0aGUgdGltZSAoZS5nLiB0aGUgJGteXHRleHR7dGh9JCBjb250cmFzdCkgdGhlIHN0YXRpc3RpYyByZWR1Y2VzIHRvCgokJFQ9XGZyYWN7XG1hdGhiZntMfV9rXlRcaGF0e1xib2xkc3ltYm9se1xiZXRhfX19e1xzcXJ0e1xsZWZ0KFxtYXRoYmZ7TH1eVF9rXGhhdHtcYm9sZHN5bWJvbHtcU2lnbWF9fV97XGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19fVxtYXRoYmZ7TH1fa1xyaWdodCl9fSBcdW5kZXJzZXR7SF8wfXtcc2ltfSB0X3tuLXB9JCQKZm9sbG93cyBhIHQgZGlzdHJpYnV0aW9uIHdpdGggbi1wIGRlZ3JlZXMgb2YgZnJlZWRvbSB1bmRlciAkSF8wOiBcbWF0aGJme0x9XlRfa1xoYXR7XGJvbGRzeW1ib2x7XGJldGF9fT0wJAoKLS0tCgojIyMjIGhlYXJ0IGV4YW1wbGUKCmBgYHtyfQp0Q29udHJhc3RzIDwtIGNvbnRyYXN0cy9zZUNvbnRyYXN0cwpwQ29udHJhc3RzIDwtIHB0KGFicyh0Q29udHJhc3RzKSwKICBkZiA9IG4gLSBwLAogIGxvd2VyLnRhaWwgPSBGQUxTRSkgKiAyCmBgYAoKQ29tcGFyaXNvbiB3aXRoIGxtIGFuZCBnbGh0IHJlc3VsdHMKCmBgYHtyfQpzdW1tYXJ5KGZpdEdsaHQsIHRlc3QgPSBhZGp1c3RlZCgibm9uZSIpKQpkYXRhLmZyYW1lKGNvbnRyYXN0cywgc2VDb250cmFzdHMsIHRDb250cmFzdHMsIHBDb250cmFzdHMpCmBgYAoKCi0tLQoKIyMjIE9tbmlidXMgdGVzdAoKLSBXZSBjYW4gYWxzbyBhc3Nlc3MgYWxsIGNvbnRyYXN0cyBzaW11bHRhbmVvdXNseSB3aXRoIHRoZSBvbW5pYnVzIG51bGwgaHlwb3RoZXNpczoKXFtIXzA6IFxtYXRoYmZ7TH1eVFxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fT1cbWF0aGJmezB9XF0KCi0gU3RhdGlzdGljCiQkXG1hdGhiZntGfT1cZnJhY3tcaGF0e1xib2xkc3ltYm9se1xiZXRhfX1eVFxtYXRoYmZ7TH1cbGVmdChcbWF0aGJme0x9XlRcaGF0e1xib2xkc3ltYm9se1xTaWdtYX19X3tcaGF0e1xib2xkc3ltYm9se1xiZXRhfX19XG1hdGhiZntMfVxyaWdodCleey0xfVxtYXRoYmZ7TH1eVFxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX17bl9jfSBcdW5kZXJzZXR7SF8wfXtcc2ltfSBGX3tuX2Msbi1wfSQkCmZvbGxvd3MgYW4gRiBkaXN0cmlidXRpb24gd2l0aCAkbl9jJCBhbmQgbi1wIGRlZ3JlZXMgb2YgZnJlZWRvbSB1bmRlciB0aGUgb21uaWJ1cyBudWxsIGh5cG90aGVzaXMuCi0gTm90ZSwgdGhhdCAkbl9jJCBlcXVhbHMgdGhlIG51bWJlciBvZiBjb250cmFzdHMsIGFuZAotICRcbWF0aGJme0x9JCBpcyBhc3N1bWVkIHRvIGJlIGZ1bGwgcmFuawoKLS0tCgoKSWYgdGhlIG1hdHJpeCBcbWF0aGJme0x9IGlzIG5vdCBmdWxsIHJhbmssIGJ1dCBoYXMgcmFuayAkciA8IG5fYyQKCi0gaS5lLiBzb21lIG9mIHRoZSBjb250cmFzdHMgY2FuIGJlIHdyaXR0ZW4gYXMgbGluZWFyIGNvbWJpbmF0aW9ucyBvZiBvdGhlciBjb250cmFzdHMsCi0gdGhlIGludmVyc2Ugb2YgdGhlIHZhcmlhbmNlIGNvdmFyaWFuY2UgbWF0cml4IG9mIHRoZSBjb250cmFzdHMgZG9lcyBub3QgZXhpc3QKLSB3ZSBjYW4gdGhlbiBkZWNvbXBvc2UgTCBpbiAkciQgb3J0aG9nb25hbCBjb250cmFzdHMgJFxtYXRoYmZ7UX0kIHdpdGgKXFtcbWF0aGJme1F9X2peVCBcbWF0aGJme1F9X2teVCA9IFxkZWx0YV97amt9LFxdCgotICRqLGsgXGluIDEsXGxkb3RzLHIkLAoKLSAkXGRlbHRhe2prfSA9IDAkIGFuZCBpZiAkalxuZXEgayQgJFxkZWx0YXtqa30gPSAxJAoKLSBEZWNvbXBvc2l0aW9uIGNhbiBiZSBkb25lIHVzaW5nIHRoZSBRUiBkZWNvbXBvc2l0aW9uICAKCi0gV2UgY2FuIHRoYW4gYXNzZXNzIHRoZSBvbW5pYnVzIG51bGwgaHlwb3RoZXNpcyB1c2luZyB0aGUgc3RhdGlzdGljOgokJFxtYXRoYmZ7Rn09XGZyYWN7XGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19XlRcbWF0aGJme1F9X3JcbGVmdChcbWF0aGJme1F9XlRfclxoYXR7XGJvbGRzeW1ib2x7XFNpZ21hfX1fe1xoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX1cbWF0aGJme1F9X3JccmlnaHQpXnstMX1cbWF0aGJme1F9XlRfclxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX17cn0gXHVuZGVyc2V0e0hfMH17XHNpbX0gRl97cixuLXB9JCQKCi0tLQoKIyMjIyBIZWFydCBleGFtcGxlCgpgYGB7cn0KdHJ5KHNvbHZlKFNpZ21hQ29udHJhc3RzKSkKYGBgCgotIFdlIGNhbm5vdCBpbnZlcnQgdGhlIHZhcmlhbmNlIG1hdHJpeCBvZiB0aGUgY29udHJhc3RzIQotIEluZGVlZCwgdGhlIGNvbnRyYXN0cyBhcmUgbGluZWFyIGNvbWJpbmF0aW9ucyBvZiB0d28gcGFyYW1ldGVycyBhbmQgdGhlIGNvbnRyYXN0IG1hdHJpeCAkXG1hdGhiZntMfSQgd2lsbCB0aHVzIGhhdmUgcmFuayAyCi0gV2UgY2FsY3VsYXRlIG9ydGhvZ29uYWwgY29udHJhc3RzOgoKYGBge3J9CnFyTCA8LSBxcihMKQpyIDwtIHFyTCRyYW5rCnIKUSA8LSBxci5RKHFyTClbLDE6cl0Kcm93bmFtZXMoUSkgPC0gcm93bmFtZXMoTCkKUQpgYGAKCi0gUSBpcyBvcnRob25vcm1hbAoKYGBge3J9CnQoUSklKiVRCmBgYAoKRXhwbG9yaW5nIFEgc2hvd3MgdGhhdCBhc3Nlc3NpbmcgdGhlIG9tbmlidXMgaHlwb3RoZXNpcyBpcyB0aHVzIGVxdWl2YWxlbnQgdG8gYXNzZXNzaW5nIGlmIHRoZSBudWxsIGh5cG90aGVzaXMgdGhhdApcW0hfMDogXGJldGFfXHRleHR7dGlzc3VlfSA9IFxiZXRhX1x0ZXh0e3Rpc3N1ZTpsb2NhdGlvbn0gPSAwXF0KCmBgYHtyfQplc3QgPC0gdChRKSAlKiUgYmV0YXMKU2lnbWFFc3QgPC0gdChRKSAlKiUgU2lnbWFCZXRhICUqJSBRCkZzdGF0IDwtIHQoZXN0KSAlKiUgc29sdmUoU2lnbWFFc3QpICUqJSBlc3QgLyByCnBPbW5pYnVzIDwtIHBmKEZzdGF0LCByLCBwLCBsb3dlci50YWlsID0gRkFMU0UpCmBgYAoKLSBDb21wYXJpc29uIHdpdGggbG0gcmVzdWx0cwotIFdlIGNhbiBhc3Nlc3MgdGhlIG9tbmlidXMgaHlwb3RoZXNpcyBhbHNvIGJ5IGNvbXBhcmluZyB0d28gbW9kZWxzCiAgICAtIG1vZGVsIHdpdGggbG9jYXRpb24sIHRpc3N1ZSwgbG9jYXRpb24gLSB0aXNzdWUgaW50ZXJhY3Rpb24gYW5kIHBhdGllbnQgZWZmZWN0CiAgICAtIG51bGwgbW9kZWw6IG1vZGVsIHdpdGggbG9jYXRpb24gYW5kIHBhdGllbnQgZWZmZWN0CgpgYGB7cn0KZml0MCA8LSBsbSh5IH4gbG9jYXRpb24gKyBwYXRpZW50LCBjb2xEYXRhKHBlKSkKYW5vdmEoZml0LCBmaXQwKQpGc3RhdApwT21uaWJ1cwpgYGAKCiMgUm9idXN0IHJlZ3Jlc3Npb24KCi0gV2l0aCBtc3Fyb2IyIHdlIHBlcmZvcm0gcm9idXN0IHJlZ3Jlc3Npb24gdG8gZXN0aW1hdGUgdGhlIG1vZGVsIHBhcmFtZXRlcnMgb2YgdGhlIHJlZ3Jlc3Npb24gbW9kZWwKCi0gTm8gbm9ybWFsaXR5IGFzc3VtcHRpb24gbmVlZGVkCi0gUm9idXN0IGZpdCBtaW5pbWlzZXMgdGhlIG1heGltYWwgYmlhcyBvZiB0aGUgZXN0aW1hdG9ycwotIENJIGFuZCBzdGF0aXN0aWNhbCB0ZXN0cyBhcmUgYmFzZWQgb24gYXN5bXB0b3RpYyB0aGVvcnkKLSBJZiAkXGVwc2lsb24kIGlzIG5vcm1hbCwgdGhlIE0tZXN0aW1hdG9ycyBoYXZlIGEgaGlnaCBlZmZpY2llbmN5IQotIG9yZGluYXJ5IGxlYXN0IHNxdWFyZXMgKE9MUyk6IG1pbmltaXplIGxvc3MgZnVuY3Rpb24gXFtcc3VtXGxpbWl0c197aT0xfV5uICh5X2ktXG1hdGhiZnt4fV9pXlRcYm9sZHN5bWJvbHtcYmV0YX0pXjJcXQoKLSBNLWVzdGltYXRpb246IG1pbmltaXplIGxvc3MgZnVuY3Rpb24KXFtcc3VtXGxpbWl0c197aT0xfV5uICBccmhvXGxlZnQoeV9pLVxtYXRoYmZ7eH1faV5UXGJvbGRzeW1ib2x7XGJldGF9XHJpZ2h0KVxdCndpdGgKCiAgLSAkXHJobyQgaXMgc3ltbWV0cmljLCBpLmUuICRccmhvKHopPVxyaG8oLXopJAogIC0gJFxyaG8kIGhhcyBhIG1pbmltdW0gYXQgJFxyaG8oMCk9MCQsIGlzIHBvc2l0aXZlIGZvciBhbGwgJHpcbmVxIDAkCiAgLSAkXHJobyh6KSQgaW5jcmVhc2VzIGFzICRcdmVydCB6XHZlcnQkIGluY3JlYXNlcwoKLS0tCgogVGhlIGVzdGltYXRvciAkXGhhdHtcbXV9JCBpcyBhbHNvIHRoZSBzb2x1dGlvbiB0byB0aGUgZXF1YXRpb24KIFxbCiAgIFxzdW1fe2k9MX1ebiBcUHNpKHlfaSAtIFxtYXRoYmZ7eH1faVxib2xkc3ltYm9se1xiZXRhfSkgPTAsCiBcXQogd2hlcmUgJFxQc2kkIGlzIHRoZSBkZXJpdmF0aXZlIG9mICRccmhvJC4gRm9yICRcaGF0e1xiZXRhfSQgcG9zc2Vzc2luZyB0aGUgcm9idXN0bmVzcyBwcm9wZXJ0eSwgJFxQc2kkIHNob3VsZCBiZSBib3VuZGVkLgoKLS0tCgogRXhhbXBsZTogbGVhc3Qgc3F1YXJlcwoKIC0gJFxyaG8oeikgPSB6XjIkLCBhbmQgdGh1cyAkXFBzaSh6KT0yeiQgKHVuYm91bmRlZCEpLiBOb3Qgcm9idXN0IQoKLSAkXGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19JCBpcyB0aGUgc29sdXRpb24gb2YKIFxbCiAgIFxzdW1fe2k9MX1ebiAyIFxtYXRoYmZ7eH1faSAoeV9pIC0gXG1hdGhiZnt4fV9pXlRcYm9sZHN5bWJvbHtcYmV0YX0pID0gMCBcdGV4dHsgb3IgfSBcaGF0e1xib2xkc3ltYm9se1xiZXRhfX0gPSAoXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxtYXRoYmZ7WH1cbWF0aGJme3l9CiBcXQogd2l0aCAkXG1hdGhiZntYfT1bXG1hdGhiZnt4fV8xIFxsZG90cyBcbWF0aGJme3h9X0ddXlQkCgotLS0KCiBXaGVuIGEgbG9jYXRpb24gYW5kIGEgc2NhbGUgcGFyYW1ldGVyLCBzYXkgJFxzaWdtYSQsIGhhdmUgdG8gYmUgZXN0aW1hdGVkIHNpbXVsdGFuZW91c2x5LCB3ZSB3cml0ZQogXFsKICAgKFxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fSxcaGF0e1xzaWdtYX0pID0gXHRleHR7QXJnTWlufV97XGJvbGRzeW1ib2x7XGJldGF9LFxzaWdtYX0gXHN1bV97aT0xfV5uIFxyaG9cbGVmdChcZnJhY3t5X2kgLSBcbWF0aGJme3h9X2leVFxib2xkc3ltYm9se1xiZXRhfX17XHNpZ21hfVxyaWdodCkKICAgXHRleHR7IGFuZCB9IFxzdW1fe2k9MX1ebiBcUHNpXGxlZnQoXGZyYWN7eV9pIC0gXG1hdGhiZnt4fV9pXlRcYm9sZHN5bWJvbHtcYmV0YX19e1xzaWdtYX1ccmlnaHQpID0wLgogXF0KCiBEZWZpbmUgJHVfaSA9IFxmcmFje3lfaSAtIFxtYXRoYmZ7eH1faV5UXGJvbGRzeW1ib2x7XGJldGF9fXtcc2lnbWF9JC4gVGhlIGxhc3QgZXN0aW1hdGlvbiBlcXVhdGlvbiBpcyBlcXVpdmFsZW50IHRvCiBcWwogICBcc3VtX3tpPTF9Xm4gdyh1X2kpIHVfaSA9IDAgLAogXF0KIHdpdGggd2VpZ2h0IGZ1bmN0aW9uICR3KHUpPVxQc2kodSkvdSQuIFRoaXMgaXMgdGhlIHR5cGljYWwgZm9ybSB0aGF0IGFwcGVhcnMgd2hlbiBzb2x2aW5nIHRoZQogKml0ZXJhdGl2ZWx5IHJld2VpZ2h0ZWQgbGVhc3Qgc3F1YXJlcyBwcm9ibGVtKiwKIFxbCiAgIChcaGF0e1xib2xkc3ltYm9se1xiZXRhfX0sXGhhdHtcc2lnbWF9KSA9IFx0ZXh0e0FyZ01pbn1fe1xtdSxcc2lnbWF9IFxzdW1fe2k9MX1ebiB3KHVfaV57KGstMSl9KSBcbGVmdCh1X2leeyhrKX1ccmlnaHQpXjIgLAogXF0KIHdoZXJlICRrJCByZXByZXNlbnRzIHRoZSBpdGVyYXRpb24gbnVtYmVyLgoKLS0tCgojIyBTb21lIEV4YW1wbGVzIG9mIFJvYnVzdCBGdW5jdGlvbnMKCiFbXShodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vc3RhdE9taWNzL1NHQTIwMjAvZ2gtcGFnZXMvYXNzZXRzL1RhYmxlUm9idXN0LlBORykKClBoRCB0aGVzaXMgQm9sc3RhZCAyMDA0CgotLS0KCiMjIFRoZSAkXHJobyQgZnVuY3Rpb25zCgohW10oaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL3N0YXRPbWljcy9TR0EyMDIwL2doLXBhZ2VzL2Fzc2V0cy9SaG9Sb2J1c3QuUE5HKQoKUGhEIHRoZXNpcyBCb2xzdGFkIDIwMDQKCi0tLQoKIyMjIENvbW1vbiAkXFBzaSQtRnVuY3Rpb25zCiFbXShodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vc3RhdE9taWNzL1NHQTIwMjAvZ2gtcGFnZXMvYXNzZXRzL3JvYnVzdFJlZ3Jlc3Npb25Qc2kucG5nKQoKUGhEIHRoZXNpcyBCb2xzdGFkIDIwMDQKCi0tLQoKIyMjIENvcnJlc3BvbmRpbmcgV2VpZ2h0IEZ1bmN0aW9ucwohW10oaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL3N0YXRPbWljcy9TR0EyMDIwL2doLXBhZ2VzL2Fzc2V0cy9yb2J1c3RSZWdyZXNzaW9uV2VpZ2h0cy5wbmcpCgpQaEQgdGhlc2lzIEJvbHN0YWQgMjAwNAoKLS0tCgpgYGB7cn0KbGlicmFyeSgiTUFTUyIpCnJmaXQgPC0gcmxtKHkgfiBsb2NhdGlvbiAqIHRpc3N1ZSArIHBhdGllbnQsIGNvbERhdGEocGUpLCBtYXhpdD0xKQpxcGxvdChmaXQkY29lZmZpY2llbnRbLTFdLAogIHJmaXQkY29lZmZpY2llbnRbLTFdLAogIHhsYWI9ImZpdCIsCiAgeWxhYj0icm9idXN0IGZpdCIpICsKICBnZW9tX2FibGluZSgpICsKICB4bGltKHJhbmdlKGMoZml0JGNvZWZmaWNpZW50Wy0xXSxyZml0JGNvZWZmaWNpZW50Wy0xXSkpKSArCiAgeWxpbShyYW5nZShjKGZpdCRjb2VmZmljaWVudFstMV0scmZpdCRjb2VmZmljaWVudFstMV0pKSkKYGBgCgotLS0KCmBgYHtyfQpyZml0JHcKcGxvdCgKICByZml0JGZpdHRlZCwKICByZml0JHJlcywKICBjZXg9cmZpdCR3LAogIHBjaD0xOSxjb2w9MiwKICBjZXgubGFiPTEuNSwKICBjZXguYXhpcz0xLjUsCiAgeWxhYj0icmVzaWR1YWxzIiwKICB4bGFiPSJmaXQiKQpwb2ludHMocmZpdCRmaXR0ZWQsIHJmaXQkcmVzICwgY2V4PSAxLjUpCmBgYAoKLS0tCgpgYGB7cn0Kc3VtbWFyeShmaXQpCnN1bW1hcnkocmZpdCkKcm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJG1zcXJvYk1vZGVsc1tbMl1dICU+JSBnZXRDb2VmCmBgYAoKLS0tCgojIyBVbmRlcnN0YW5kaW5nIGltcGxlbWVudGF0aW9uIG9mIHJvYnVzdCByZWdyZXNzaW9uCgojIyMgU2ltdWxhdGUgMjAgb2JzZXJ2YXRpb25zIGZyb20gYSBsaW5lYXIgbW9kZWwgd2l0aCBlcnJvcnMgdGhhdCBmb2xsb3cgYSBub3JtYWwgZGlzdHJpYnV0aW9uCgpgYGB7cn0Kc2V0LnNlZWQgPC0gMTEyMzU4Cm5vYnMgPC0gMjAKc2R5IDwtIDEKeHNpbSA8LSBzZXEoMCwgMSwgbGVuZ3RoLm91dCA9IG5vYnMpCnlzaW0gPC0gMTAgKyA1KnhzaW0gKyBybm9ybShub2JzLCBzZCA9IHNkeSkKYGBgCgojIyMgYWRkIG91dGxpZXIgYXQgaGlnaCBsZXZlcmFnZSBwb2ludAoKYGBge3J9CnlzaW1bbm9ic10gPC0gNwpgYGAKCiMjIyBmaXQgbGluZWFyIG1vZGVsCgpgYGB7cn0Kb2xzIDwtIGxtKHlzaW0gfiB4c2ltKQpgYGAKCiMjIyBmaXQgcm9idXN0IGxpbmVhciBtb2RlbAoKYGBge3J9CmxpYnJhcnkoTUFTUykKbUVzdCA8LSBybG0oeXNpbSB+IHhzaW0pCmBgYAoKIyMjIyBwbG90IHJlc3VsdHMKCmBgYHtyfQpwbG90KHhzaW0sIHlzaW0pCmFibGluZShvbHMsIGx3ZCA9IDIpCmFibGluZShtRXN0LCBjb2wgPSAicmVkIiwgbHdkID0gMikKbGVnZW5kKCJ0b3BsZWZ0IiwKICBsZWdlbmQgPSBjKCJPTFMiLCAiTS1lc3RpbWF0aW9uIiksCiAgbHdkID0gMiwKICBjb2wgPSAxOjIpCnJvdW5kKG1Fc3QkdywzKQpgYGAKClRoZSBwbG90IGNsZWFybHkgc2hvd3MgdGhhdCB0aGUgb3V0bGllciBoYXMgYSBoaWdoIGltcGFjdCBvbiB0aGUgc2xvcGUgZXN0aW1hdGUuClRoaXMgaXMgYmVjYXVzZSB0aGUgb3V0bGllciBpcyBhdCBhIGhpZ2ggbGV2ZXJhZ2UgcG9pbnQsIGkuZS4gZmFyIGZyb20gdGhlIGF2ZXJhZ2UgY292YXJpYXRlIHBhdHRlcm4uCgojIyMgSW1wbGVtZW50IGl0IHlvdXJzZWxmCiMjIyMgc3RhcnQgZnJvbSBvbHMgZml0CgpgYGB7cn0KbG1Nb2QgPC0gb2xzCmBgYAoKIyMjIyBVc2Ugcm9idXN0IHZhcmlhbmNlIGVzdGltYXRvciB0byBjYWxjdWxhdGUgdGhlIHoKCmBgYHtyfQpyZXMgPC0gbG1Nb2QkcmVzCnN0ZGV2IDwtIG1hZChyZXMpCnN0ZGV2Cm1lZGlhbihhYnMocmVzLW1lZGlhbihyZXMpKSkqMS40ODI2CnogPC0gcmVzL3N0ZGV2CmBgYAoKIyMjIyBDYWxjdWxhdGUgd2VpZ2h0cyB1c2UgcHNpLmh1YmVyIGZ1bmN0aW9uCgpgYGB7cn0KdyA8LSBwc2kuaHViZXIoeikKcGxvdCh4c2ltLCB5c2ltKQpwbG90KHhzaW0sIGxtTW9kJHJlcywgY2V4ID0gdywgcGNoID0gMTksIGNvbCA9ICJyZWQiKQpwb2ludHMoeHNpbSxsbU1vZCRyZXMsIGNleCA9IDEuNSkKYGBgCgojIyMjIFBlcmZvcm0gYSB3ZWlnaHRlZCByZWdyZXNzaW9uIHVzZSBsbSB3aXRoIHdlaWdodHM9dwoKYGBge3J9CmxtTW9kIDwtIGxtKHlzaW1+eHNpbSwgd2VpZ2h0cyA9IHcpCmBgYAoKIyMjIyBQbG90IHJlc3VsdHMKCmBgYHtyfQpwbG90KHhzaW0sIHlzaW0pCmFibGluZShvbHMsIGx3ZCA9IDIpCmFibGluZShtRXN0LCBjb2wgPSAicmVkIiwgbHdkID0gMikKYWJsaW5lKGxtTW9kLCBjb2wgPSAiYmx1ZSIsIGx3ZCA9IDIpCmxlZ2VuZCgidG9wbGVmdCIsCiAgbGVnZW5kID0gYygiT0xTIiwiTS1lc3RpbWF0aW9uIiwiT3VyIEltcGwiKSwKICBsd2QgPSAyLAogIGNvbCA9IGMoImJsYWNrIiwgInJlZCIsICJibHVlIikpCmBgYAoKIyMjIyBSZXBlYXQgdGhpcyBtYW55IHRpbWVzCmBgYHtyfQpsbU1vZCA8LSBvbHMKZm9yIChrIGluIDE6MykKewojIyMjIyNyZXBlYXQgdGhpcyBwYXJ0IHNldmVyYWwgdGltZXMgdW50aWwgY29udmVyZ2VuY2UKI3VzZSByb2J1c3QgdmFyaWFuY2UgZXN0aW1hdG9yIHRvIGNhbGN1bGF0ZSB0aGUgegpyZXMgPC0gbG1Nb2QkcmVzCnN0ZGV2IDwtIG1hZChyZXMpCm1lZGlhbihhYnMocmVzLW1lZGlhbihyZXMpKSkqMS40ODI2Cgp6IDwtIHJlcy9zdGRldgoKI2NhbGN1bGF0ZSB3ZWlnaHRzCiN1c2UgcHNpLmh1YmVyIGZ1bmN0aW9uCncgPC0gcHNpLmh1YmVyKHopCgojcGVyZm9ybSBhIHdlaWdodGVkIHJlZ3Jlc3Npb24gdXNlIGxtIHdpdGggd2VpZ2h0cz13CmxtTW9kIDwtIGxtKHlzaW0gfiB4c2ltLCB3ZWlnaHRzID0gdykKCiNwbG90IHJlc3VsdHMKcGxvdCh4c2ltLHlzaW0pCmFibGluZShvbHMsIGx3ZCA9IDIpCmFibGluZShtRXN0LCBjb2wgPSAicmVkIiwgbHdkID0gMikKYWJsaW5lKGxtTW9kLCBjb2wgPSAiYmx1ZSIsIGx3ZCA9IDIpCmxlZ2VuZCgidG9wbGVmdCIsCiAgbGVnZW5kID0gYygiT0xTIiwiTS1lc3RpbWF0aW9uIiwiT3VyIEltcGwiKSwKICBsd2QgPSAyLAogIGNvbCA9IGMoImJsYWNrIiwgInJlZCIsICJibHVlIikKICApCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwp9CmBgYAoKIyBFbXBpcmljYWwgQmF5ZXMvTW9kZXJhdGVkICR0JC10ZXN0LgoKIEEgZ2VuZXJhbCBjbGFzcyBvZiBtb2RlcmF0ZWQgdGVzdCBzdGF0aXN0aWNzIGlzIGdpdmVuIGJ5CgogXFtcdGlsZGV7VH1fcCA9IFxmcmFje1xtYXRoYmZ7TH1fayBcaGF0eyBcYm9sZHN5bWJvbHtcYmV0YV9wfX19e1xtYXRoYmZ7TH1fa15UKFxtYXRoYmZ7WH1eVFxtYXRoYmZ7V1h9KV57LTF9XG1hdGhiZntMfV9rXlQgXHRpbGRle3N9X3BeMn1cXQoKIHdoZXJlICRcdGlsZGV7c31fcCQgaXMgYSBtb2RlcmF0ZWQgdmFyaWFuY2UgZXN0aW1hdG9yLgoKU2ltcGxlIGFwcHJvYWNoOiBzZXQgJFx0aWxkZXtzfV9wPXNfcCArIHNfMCQ6IHNpbXBseSBhZGQgYSBzbWFsbCBwb3NpdGl2ZSBjb25zdGFudCB0byB0aGUgZGVub21pbmF0b3Igb2YgdGhlIHQtc3RhdGlzdGljCgpcdGV4dGJme2VtcGlyaWNhbCBCYXllc30gdGhlb3J5IHByb3ZpZGVzIGZvcm1hbCBmcmFtZXdvcmsgZm9yIGJvcnJvd2luZyBzdHJlbmd0aCBhY3Jvc3MgZ2VuZXMgb3IgcHJvdGVpbnMsCmUuZy4gcG9wdWxhciBiaW9jb25kdWN0b3IgcGFja2FnZSBcdGV4dGJme2xpbW1hfQpcW1x0aWxkZXtzfV9nPVxzcXJ0e1xmcmFje2RfcHNfcF4yK2RfMHNfMF4yfXtkX2crZF8wfX0sXF0KYW5kIHRoZSBtb2RlcmF0ZWQgdC1zdGF0aXN0aWMgaXMgdC1kaXN0cmlidXRlZCB3aXRoICRkXzArZF9nJCBkZWdyZWVzIG9mIGZyZWVkb20gdW5kZXIgdGhlIG51bGwgaHlwb3RoZXNpcyAkSF8wOiBcbWF0aGJme0x9XGJvbGRzeW1ib2x7XGJldGF9PTAkLgoKLSBOb3RlLCB0aGF0IHRoZSBkZWdyZWVzIG9mIGZyZWVkb20gaW5jcmVhc2UgYnkgYm9ycm93aW5nIHN0cmVuZ3RoIGFjcm9zcyBwcm90ZWlucy4KCi0tLQoKIyMgSW50ZXJtZXp6bzogQmF5ZXNpYW4gTWV0aG9kcwoKLSBGcmVxdWVudGlzdHMgY29uc2lkZXIgZGF0YSBhcyByYW5kb20gYW5kIHBvcHVsYXRpb24gcGFyYW1ldGVycyBhcyBmaXhlZCBidXQgdW5rbm93bgotIEluIEJheWVzaWFuIHZpZXdwb2ludCBhIHBlcnNvbiBoYXMgcHJpb3IgYmVsaWVmcyBhYm91dCB0aGUgcG9wdWxhdGlvbiBwYXJhbWV0ZXJzIGFuZCB0aGUgdW5jZXJ0YWludHkgb24gdGhpcyBwcmlvciBiZWxpZWZzIGFyZSByZXByZXNlbnRlZCBieSBhIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiBwbGFjZWQgb24gdGhpcyBwYXJhbWV0ZXIuCgogIC0gVGhpcyBkaXN0cmlidXRpb24gcmVmbGVjdHMgdGhlIHBlcnNvbidzIHN1YmplY3RpdmUgcHJpb3Igb3BpbmlvbiBhYm91dCBwbGF1c2libGUgdmFsdWVzIG9mIHRoZSBwYXJhbWV0ZXIuCiAgLSBBbmQgaXMgcmVmZXJyZWQgdG8gYXMgdGhlIHByaW9yICRnKFxib2xkc3ltYm9se1x0aGV0YX0pJC4KCi0gQmF5ZXNpYW4gdGhpbmtpbmcgd2lsbCB1cGRhdGUgdGhlIHByaW9yIGluZm9ybWF0aW9uIG9uIHRoZSBwb3B1bGF0aW9uIHBhcmFtZXRlcnMgYnkgY29uZnJvbnRpbmcgdGhlIG1vZGVsIHRvIGRhdGEgKCRcbWF0aGJme1l9JCkuCgotIEJ5IHVzaW5nIEJheWVzIFRoZW9yZW0gdGhpcyByZXN1bHRzIGluIGEgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBvbiB0aGUgbW9kZWwgcGFyYW1ldGVycy4gIApcWwpnKFxib2xkc3ltYm9se1x0aGV0YX1cdmVydFxtYXRoYmZ7WX0pPVxmcmFje2YoWVx2ZXJ0IFxib2xkc3ltYm9se1x0aGV0YX0pZyhcYm9sZHN5bWJvbHtcdGhldGF9KX17XGludCBmKFlcdmVydCBcYm9sZHN5bWJvbHtcdGhldGF9KSBnKFxib2xkc3ltYm9se1x0aGV0YX0pIGRcYm9sZHN5bWJvbHtcdGhldGF9fSBcdGV4dHsgICAgIH1cbGVmdChcdGV4dHsgcG9zdGVyaW9yfT1cZnJhY3tcdGV4dHtwcmlvcn0gXHRpbWVzIFx0ZXh0eyBsaWtlbGlob29kfX17XHRleHR7TWFyZ2luYWwgZGlzdHJpYnV0aW9ufX1ccmlnaHQpClxdCgotLS0KCiMjIExpbW1hICBhcHByb2FjaAoKRGV2ZWxvcGVkIGZvciBnZW5lIGV4cHJlc3Npb24gYW5hbHlzaXMgd2l0aCBtaWNybyBhcnJheXMuCkxldCBnIGJlIHRoZSBpbmRleCBmb3IgZ2VuZSBnLgpcWwpcYmVnaW57YXJyYXl9e2NjfQomXGJldGFfe2drfVx2ZXJ0IFxzaWdtYV4yX2csXGJldGFfe2drfVxuZXEgMCBcc2ltIE4oMCx2X3swa31cc2lnbWFfZ14yKVxcXFwKXHRleHR7UHJpb3J9XFwKJlxmcmFjezF9e1xzaWdtYV4yX2d9XHNpbSBzXjJfMFxmcmFje1xjaGleMl97ZF8wfX17ZF8wfVxcXFxcXFxcCiZcaGF0IFxiZXRhX3tna30gfCBcYmV0YV97Z2t9ICwgXHNpZ21hX2deMiBcc2ltIE4oIFxiZXRhX3tna30gLCB2X3tna31cc2lnbWFfZ14yKVxcXFwKXHRleHR7RGF0YX1cXAomc19nXjJcc2ltIFxzaWdtYV4yX2dcZnJhY3tcY2hpXjJfe2RfZ319e2RfZ31cXFxcClxlbmR7YXJyYXl9ClxdCgotLS0KCiMjIExpbW1hICBhcHByb2FjaAoKVW5kZXIgdGhpcyBhc3N1bXB0aW9uLCBpdCBjYW4gYmUgc2hvd24gdGhhdAoKLSBQb3N0ZXJpb3IgTWVhbiBmb3IgdGhlIHZhcmlhbmNlIHBhcmFtZXRlcjogXFtcdGlsZGV7c31eMl9wID0gXHRleHR7RX1cbGVmdFtcc2lnbWFeMl9wXHZlcnQgc19wXjJccmlnaHRdPVxmcmFje2RfMCBzXzBeMitkX3BzX3BeMn17ZF8wK2RfcH1cXQoKLSBcW1x0aWxkZXtUfV9wPVxmcmFje1xtYXRoYmZ7TH1fayBcaGF0eyBcYm9sZHN5bWJvbHtcYmV0YV9wfX19e1xtYXRoYmZ7TH1fa15UKFxtYXRoYmZ7WH1eVFxtYXRoYmZ7V1h9KV57LTF9XG1hdGhiZntMfV9rXlQgXHRpbGRle3N9X3BeMn1cXQoKaXMgdC1kaXN0cmlidXRlZCB1bmRlciAkSF8wOiBcbWF0aGJme0x9X2pcYm9sZHN5bWJvbHtcYmV0YX0gPSAwJAoKXFtcdGlsZGV7VH1fcCBcdmVydCBIXzAgXHNpbSB0KGRfMCArIGRfcClcXQoKLS0tCgojIyBFbXBpcmljYWwgQmF5ZXMKLSBBIGZ1bGx5IEJheWVzaWFuCiAgLSB3b3VsZCBkZWZpbmUgdGhlIHByaW9yIGRpc3RyaWJ1dGlvbiBieSBjYXJlZnVsbHkgY2hvb3NpbmcgdGhlIHByaW9yIHBhcmFtZXRlcnMgYmFzZWQgb24gcHJpb3Iga25vd2xlZGdlIG9uIHRoZSBwcm9jZXNzCiAgLSB3b3VsZCBjb25mcm9udCB0aGUgcHJpb3IgdG8gdGhlIGRhdGEgYW5kIHBlcmZvcm1zIGluZmVyZW5jZSB1c2luZyB0aGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBvZiB0aGUgbW9kZWwgcGFyYW1ldGVycy4KLSBJbiBhbiBlbXBpcmljYWwgQmF5ZXNpYW4gYXBwcm9hY2ggb25lIGVzdGltYXRlcyB0aGUgcHJpb3IgcGFyYW1ldGVycyBiYXNlZCBvbiB0aGUgZGF0YS4KLSBJbiAqKkxpbW1hKiogbW9tZW50IGVzdGltYXRvcnMgZm9yICRzXzAkIGFuZCAkZF8wJCBhcmUgZGVyaXZlZCB1c2luZyB0aGUgaW5mb3JtYXRpb24gb24gdGhlIGdlbmUgKHByb3RlaW4pIHdpc2UgdmFyaWFuY2VzIG9mIGFsbCBnZW5lcyAocHJvdGVpbnMpLgotIEluICoqTGltbWEqKiBvbmUgYWxzbyBkb2VzIG5vdCB3b3JrIHdpdGggdGhlIGZ1bGwgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBmb3IgdGhlIHZhcmlhbmNlcywgYnV0IHdpdGggdGhlIG1heGltdW0gYS1wb3N0ZXJpb3IgZXN0aW1hdGUuCgotLS0KCiMjIElsbHVzdHJhdGlvbgoKV2UgYm9ycm93IHN0cmVuZ3RoIGFjcm9zcyBwcm90ZWlucyBieQoKMS4gcGxhY2luZyBhIHNjYWxlZCAkXGNoaV4yJCBwcmlvcjogJFxjaGleMihzX28sZF8wKSQgb24gdGhlIHByZWNpc2lvbnMgKCQxL1xzaWdtYV4yX3AkKQoyLiBlc3RpbWF0aW5nIHRoZSBwcmlvciBwYXJhbWV0ZXJzICRzXzAkIGFuZCAkZGZfMCQKMy4gcmVwbGFjaW5nIHRoZSBlc3RpbWF0ZWQgcHJvdGVpbi13aXNlIHZhcmlhbmNlcyAoJHNfcF4yJCkgd2l0aCB0aGUgbWF4aW11bSBhLXBvc3RlcmlvcmkgdmFyaWFuY2UKXFtcdGlsZGV7c31fcCA9IFxmcmFje2RfcCBzXjJfcCArIGRfMCBzXzBeMn17ZF9wK2RfMH1cXQoKCmBgYHtyfQpzZCA8LSBzYXBwbHkoCiAgcm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJG1zcXJvYk1vZGVscywKICBnZXRTaWdtYSkgJT4lCiAgbmEuZXhjbHVkZQpzZFBvc3QgPC0gc2FwcGx5KAogIHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSRtc3Fyb2JNb2RlbHMsCiAgZ2V0U2lnbWFQb3N0ZXJpb3IpICU+JQogIG5hLmV4Y2x1ZGUKCnAxIDwtIHFwbG90KHNkLHNkUG9zdCkgKwogIGdlb21fYWJsaW5lKCkKcDEKYGBgCgojIyMgSG93IGRvIHdlIGdldCB0byB0aGUgcG9zdGVyaW9yIHN0YW5kYXJkIGRldmlhdGlvbj8KCmBgYHtyfQpobHAgPC0gbGltbWE6OnNxdWVlemVWYXIoCiAgdmFyID0gc2FwcGx5KHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSRtc3Fyb2JNb2RlbHMsIGdldFZhciksCiAgZGYgPSBzYXBwbHkocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJG1zcXJvYk1vZGVscywgZ2V0REYpCiAgKQpgYGAKCiMjIyMgRGVncmVlcyBvZiBmcmVlZG9tIG9mIHByaW9yCgpgYGB7cn0KaGxwJGRmLnByaW9yCgptb2RlbCA8LSByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkbXNxcm9iTW9kZWxzW1syXV0KZ2V0RGZQb3N0ZXJpb3IobW9kZWwpIC0gZ2V0REYobW9kZWwpCmBgYAoKIyMjIyBwb3N0ZXJpb3IgdmFyaWFuY2UKCiQkXHRpbGRlIHNfcD1cc3FydHtcZnJhY3tkX3BcdGltZXMgc14yX3AgKyBkXzAgc18wXjJ9e2RfcCtkXzB9fSAkJAoKYGBge3J9CmhscCR2YXIucHJpb3IKCnZhclBvc3QgPC0gKGdldFZhcihtb2RlbCkgKiBnZXRERihtb2RlbCkgKyBobHAkZGYucHJpb3IgKiBobHAkdmFyLnByaW9yKS8oZ2V0REYobW9kZWwpK2hscCRkZi5wcmlvcikKc3FydCh2YXJQb3N0KQpnZXRTaWdtYVBvc3Rlcmlvcihtb2RlbCkKYGBgCgpIZW5jZSwgc3RhbmRhcmQgZGV2aWF0aW9ucyBhcmUgc2hydW5rZW4gdG93YXJkcyBwcmlvciBzdGFuZGFyZCBkZXZpYXRpb24hCkxhcmdlIHN0YW5kYXJkIGRldmlhdGlvbnMgYmVjb21lIHNtYWxsZXIgYW5kIHNtYWxsZXIgc3RhbmRhcmQgZGV2aWF0aW9ucyBiZWNvbWUgbGFyZ2VyIQoKYGBge3J9CnAxICsKICBnZW9tX2hsaW5lKHlpbnRlcmNlcHQgPSBobHAkdmFyLnByaW9yXi41KQpgYGAKCgoKIyMjIElsbHVzdHJhdGlvbiB2aWEgU2ltdWxhdGlvbgoKU3VwcG9zZSB0aGF0IHRoZSBzdGFuZGFyZCBkZXZpYXRpb25zIGZvciBhbGwgcHJvdGVpbnMgYXJlIHRoZSBzYW1lIGFuZCBhcmUgZXF1YWwgdG8gMS4KV2Ugc2ltdWxhdGUgcHJvdGVpbnMgd2l0aCB0aGUgc2FtZSBtZWFuIGFzIHRoZSBmaXR0ZWQgbWVhbiBpbiB0aGUgZXhwZXJpbWVudCBidXQgd2l0aCBzdGFuZGFyZCBkZXZpYXRpb24gb2YgMS4KCmBgYHtyIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0V9Cm5Db2VmcyA8LSBnZXRDb2VmKHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSRtc3Fyb2JNb2RlbHNbWzJdXSkgJT4lIGxlbmd0aApjb2VmcyA8LQpzYXBwbHkocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJG1zcXJvYk1vZGVscywKICAgIGZ1bmN0aW9uKHgpIGdldENvZWYoeClbMTpuQ29lZnNdCiAgKSAlPiUKICB0ICU+JQogIG5hLmV4Y2x1ZGUKCgpwIDwtIG5yb3coY29lZnMpCm4gPC0gbmNvbChwZVtbMV1dKQpmMF9lcXVhbFZhciA8LSBzYXBwbHkoMTpwLAogIEZVTj1mdW5jdGlvbihpLCBuLCBiZXRhcywgc2QsIGRlc2lnbikgewogIHJub3JtKG4sIG1lYW4gPSBkZXNpZ24gJSolIGJldGFzW2ksXSwgc2QgPSBzZCl9LAogIG4gPSBuLAogIGJldGFzID0gY29lZnMsCiAgc2QgPSAxLAogIGRlc2lnbiA9IFgKICApICU+JQogIHQKY29sbmFtZXMoZjBfZXF1YWxWYXIpIDwtIGNvbG5hbWVzKHBlW1sxXV0pCnNpbXMgPC0gcmVhZFFGZWF0dXJlcyhmMF9lcXVhbFZhciAlPiUgYXMuZGF0YS5mcmFtZSwgZWNvbCA9IDE6biwgbmFtZSA9ICJzaW1fZXF1YWxWYXIiKQpjb2xEYXRhKHNpbXMpIDwtIGNvbERhdGEocGUpCnNpbXMgPC0gbXNxcm9iKG9iamVjdCA9IHNpbXMsIGkgPSAic2ltX2VxdWFsVmFyIiwgZm9ybXVsYSA9IH4gbG9jYXRpb24qdGlzc3VlICsgcGF0aWVudCkKCnNkMCA8LSBzYXBwbHkoCiAgcm93RGF0YShzaW1zW1sic2ltX2VxdWFsVmFyIl1dKSRtc3Fyb2JNb2RlbHMsCiAgZ2V0U2lnbWEpICU+JQogIG5hLmV4Y2x1ZGUKc2RQb3N0MCA8LSBzYXBwbHkoCiAgcm93RGF0YShzaW1zW1sic2ltX2VxdWFsVmFyIl1dKSRtc3Fyb2JNb2RlbHMsCiAgZ2V0U2lnbWFQb3N0ZXJpb3IpICU+JQogIG5hLmV4Y2x1ZGUKCnFwbG90KHNkMCxzZFBvc3QwKSArCiAgZ2VvbV9hYmxpbmUoKSArCiAgeWxpbShyYW5nZShzZDApKQpgYGAKCi0gV2Ugb2JzZXJ2ZSBhIGxhcmdlIHZhcmlhYmlsaXR5IGluIHRoZSBpbmRpdmlkdWFsIHByb3RlaW4gbGV2ZWwgc3RhbmRhcmQgZGV2aWF0aW9uIGVzdGltYXRlcy4KLSBXZSBzaW11bGF0ZWQgcHJvdGVpbnMgd2l0aCBzdGFuZGFyZCBkZXZpYXRpb24gb2YgMSwgYnV0IHRoZSBwcm90ZWluIGVzdGltYXRlcyB2YXJ5IGZyb20gYHIgcGFzdGUocm91bmQocmFuZ2Uoc2QwKSwyKSxjb2xsYXBzZT0iLCAuLi4gLCAiKWAuCi0gTGFyZ2UgdW5jZXJ0YWludHkgb24gdGhlIGVzdGltYXRpb24gb2YgdmFyaWFuY2VzIGluIHNtYWxsIHNhbXBsZXMKLSBUaGUgZW1waXJpY2FsIEJheWVzIG1ldGhvZCwgaG93ZXZlciwgcmVjb2duaXNlcyB0aGF0IGFsbCBwcm90ZWlucyBhcmUgc2ltdWxhdGVkIHdpdGggdGhlIHNhbWUgdmFyaWFuY2UuCi0gSGVuY2UsIGl0IGNhbiBib3Jyb3cgdHJlbWVuZG91cyBzdHJlbmd0aCBhY3Jvc3MgcHJvdGVpbnMgdG8gc3RhYmlsaXplIHRoZSB2YXJpYW5jZSBlc3RpbWF0aW9uCi0gSGVyZSwgaXQgc2hyaW5rcyBhbGwgcHJvdGVpbiB2YXJpYW5jZSB0byB0aGUgcHJpb3IgdmFyaWFuY2UsIHdoaWNoIGlzIGluZGVlZCB2ZXJ5IGNsb3NlIHRvIDEsIHRoZSB2YWx1ZSB3ZSBoYXZlIGFkb3B0ZWQgaW4gdGhlIHNpbXVsYXRpb24uCgpOb3RlLCB0aGF0IHRoZSBwcmlvciBkZWdyZWUgb2YgZnJlZWRvbSBhbHNvIGlzIHNldCB0byBpbmZpbml0eToKYGBge3J9CmdldERGKHJvd0RhdGEoc2ltc1tbInNpbV9lcXVhbFZhciJdXSkkbXNxcm9iTW9kZWxzW1sxXV0pCmdldERmUG9zdGVyaW9yKHJvd0RhdGEoc2ltc1tbInNpbV9lcXVhbFZhciJdXSkkbXNxcm9iTW9kZWxzW1sxXV0pCmBgYAoKd2hpY2ggaW1wb3NlcyBzaHJpbmthZ2UgdG8gdGhlIHByaW9yIHN0YW5kYXJkIGRldmlhdGlvbiEKClRoZSBlbXBpcmljYWwgQmF5ZXMgbWV0aG9kIGNhbiB0aHVzIGluZGVlZCByZWNvZ25pc2UgdGhlIGNvbW1vbiB2YXJpYW5jZSB0aGF0IGlzIHNoYXJlZCBhY3Jvc3MgcHJvdGVpbnMhCgojIFAtdmFsdWVzCgojIyBTaW11bGF0aW9uIHVuZGVyIEhfMC4KCi0gTWVhbiBsb2cyIHByb3RlaW4gaW50ZW5zaXR5IGZvciBhdHJpdW0gZXF1YWxzIG1lYW4gbG9nMiBwcm90ZWluIGludGVuc2l0eSBmb3IgdmVudHJpY3VsdW0gaW4gdGhlIGxlZnQgaGVhcnQgcmVnaW9uLgotIHNkIGVxdWFscyB0aGUgc2QgZm9yIHRoZSBwcm90ZWluLgoKCjEuIEV4dHJhY3QgJFxoYXQgXHNpZ21hJCBhbmQgJFxiZXRhJCdzICAKYGBge3J9CnNkIDwtIHNhcHBseSgKICByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkbXNxcm9iTW9kZWxzLAogIGdldFNpZ21hKSAlPiUKICBuYS5leGNsdWRlCgpjb2VmcyA8LQpzYXBwbHkocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJG1zcXJvYk1vZGVscywKICAgIGZ1bmN0aW9uKHgpIGdldENvZWYoeClbMTpuQ29lZnNdCiAgKSAlPiUKICB0ICU+JQogIG5hLmV4Y2x1ZGUKYGBgCgoyLiBTZXQgJFxiZXRhX1x0ZXh0e3Rpc3N1ZX0kIGVxdWFsIHRvIDAuIE5vIEZDIGJldHdlZW4gYXRyaXVtIGFuZCB2ZW50cmljdWx1bSBsZWZ0LgoKYGBge3J9CmNvZWZzMCA8LSBjb2Vmcwpjb2VmczBbLDNdIDwtIDAKYGBgCgozLiBTaW11bGF0ZSBwcm90ZWluIGV4cHJlc3Npb25zIGZvciBlYWNoIHByb3RlaW4gZnJvbSBhIE5vcm1hbCBkaXN0cmlidXRpb24gdW5kZXIgJEhfMCQgZm9yIGxlZnQgaGVhcnQgcmVnaW9uIChubyBGQyBiZXR3ZWVuIGF0cml1bSBhbmQgdmVudHJpY3VsdW0gbGVmdCkgYW5kIHNkIHRoZSBzZCBmb3IgdGhlIHByb3RlaW4uCmBgYHtyfQpzZXQuc2VlZCgxMDQpCmYwIDwtIHNhcHBseSgxOnAsCiAgZnVuY3Rpb24oaSwgYmV0YXMsIHNkLCBkZXNpZ24pCiAgcm5vcm0obiwgbWVhbiA9IGRlc2lnbiAlKiUgYmV0YXNbaSxdLCBzZCA9IHNkW2ldKSwKICBiZXRhcyA9IGNvZWZzMCwKICBzZCA9IHNkLAogIGRlc2lnbiA9IFgKICApICU+JQogIHQKY29sbmFtZXMoZjApIDwtIGNvbG5hbWVzKHBlW1sxXV0pCmBgYAoKNC4gU2V0dXAgUUZlYXR1cmVzIG9iamVjdCBhbmQgcGVyZm9ybSBNU3FSb2IgYW5hbHlzaXMKCmBgYHtyIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpzaW1zIDwtIHJlYWRRRmVhdHVyZXMoZjAgJT4lIGFzLmRhdGEuZnJhbWUsIGVjb2wgPSAxOm4sIG5hbWUgPSAic2ltMCIpCmNvbERhdGEoc2ltcykgPC0gY29sRGF0YShwZSkKc2ltcyA8LSBtc3Fyb2Iob2JqZWN0ID0gc2ltcywgaSA9ICJzaW0wIiwgZm9ybXVsYSA9IH4gbG9jYXRpb24qdGlzc3VlICsgcGF0aWVudCkKc2ltcyA8LSBoeXBvdGhlc2lzVGVzdChvYmplY3QgPSBzaW1zLCBpID0gInNpbTAiLCBjb250cmFzdCA9IEwpCmBgYAoKIyMjIEV2YWx1YXRlICBwdmFsdWVzICB1bmRlciBIXzAKCmBgYHtyfQp2b2xjYW5vIDwtIGdncGxvdChyb3dEYXRhKHNpbXNbWyJzaW0wIl1dKSR0aXNzdWVWLAogICAgICAgICAgICAgICAgIGFlcyh4ID0gbG9nRkMsIHkgPSAtbG9nMTAocHZhbCksIGNvbG9yID0gcHZhbCA8IDAuMDUpKSArCiBnZW9tX3BvaW50KGNleCA9IDIuNSkgKwogc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGFscGhhKGMoImJsYWNrIiwgInJlZCIpLCAwLjUpKSArIHRoZW1lX21pbmltYWwoKQp2b2xjYW5vCmBgYAoKTnVtYmVyIG9mIGZhbHNlIHBvc2l0aXZlcyB3aXRob3V0IG11bHRpcGxlIHRlc3Rpbmc/CgpgYGB7cn0Kcm93RGF0YShzaW1zW1sic2ltMCJdXSkkdGlzc3VlViAlPiUKICBmaWx0ZXIocHZhbCA8MC4wNSkgJT4lCiAgbnJvdwptZWFuKHJvd0RhdGEoc2ltc1tbInNpbTAiXV0pJHRpc3N1ZVYkcHZhbCA8IDAuMDUpICAgIApoaXN0KHJvd0RhdGEoc2ltc1tbInNpbTAiXV0pJHRpc3N1ZVYkcHZhbCxtYWluID0gInNpbXVsYXRpb24gSDAiKQpgYGAKCgotIFRoZSBwLXZhbHVlcyBhcmUgdW5pZm9ybSEKLSBBbGwgcC12YWx1ZXMgdW5kZXIgdGhlIG51bGwgYXJlIGVxdWFsbHkgbGlrZWx5LgotIFN0YXRpc3RpY2FsIGh5cHRoZXNpcyB0ZXN0aW5nIGxlYWRzIHRvIGEgdW5pZm9ybSB0ZXN0IHN0cmF0ZWd5IHVuZGVyICRIXzAkCi0gSWYgdXNlIHAtdmFsdWUgY3V0b2ZmIGF0IDAuMDUgd2UgZXhwZWN0IHRvIHJldHVybiA1JSBvZiB0aGUgbm9uLURFIHByb3RlaW5zICBhcyBkaWZmZXJlbnRpYWxseSBleHByZXNzZWQ6IG1hbnkgZmFsc2UgcG9zaXRpdmVzIGNhbiBiZSBleHBlY3RlZCEKCgojIyBQdmFsdWUgZGlzdHJpYnV0aW9uIGluIHJlYWwgZXhwZXJpbWVudAoKYGBge3J9Cmhpc3Qocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJHRpc3N1ZVYkcHZhbCwgbWFpbiA9ICJyZWFsRGF0YSIpCmBgYAoKLSBBIG1peHR1cmUgb2YgbnVsbCBwcm90ZWlucyAobm9uLURFKTogdW5pZm9ybSwgYW5kLCBERSBwcm90ZWluczogZW5yaWNobWVudCBvZiBwLXZhbHVlcyBhdCBsb3cgcC12YWx1ZXMKCgojIENvcnJlY3Rpb24gZm9yIG11bHRpcGxlIHRlc3RpbmcKCi0gV2UgY2FuIGFkanVzdCB0aGUgcC12YWx1ZXMgZm9yIG11bHRpcGxlIHRlc3RpbmcuCgojIyBGYW1pbHkgd2lzZSBlcnJvciByYXRlIGNvcnJlY3Rpb246CgotIEEgbGlzdCBvZiByZXR1cm5lZCBwcm90ZWlucyBpcyBjb25zaWRlcmVkIHRvIGJlIGluIGVycm9yIGFzIHNvb24gYXMgaXQgY29udGFpbnMgYXQgbW9zdCBvbmUgZmFsc2UgcG9zaXRpdmUgcHJvdGVpbi4KCi0gJFx0ZXh0e0ZXRVJ9ID0gUChGUCBcbGVxIDEpJAoKLSBGV0VSOiBwcm9iYWJpbGl0eSBvZiBtYWtpbmcgYXQgbGVhc3Qgb25lIGZhbHNlIHBvc2l0aXZlIGRlY2lzaW9uIG9yCnByb2JhYmlsaXR5IHRvIGRlY2xhcmUgYXQgbGVhc3Qgb25lIHByb3RlaW4gZGlmZmVyZW50aWFsbHkgYWJ1bmRhbnQgd2hpY2ggaXMgdHJ1bHkgbm9uIGRpZmZlcmVudGlhbGx5IGFidW5kYW50CgojIyMgQm9uZmVycm9uaSBtZXRob2QKCi0gU2ltcGxlIG1ldGhvZAotICRtJCB0ZXN0cyBhcmUgcGVyZm9ybWVkIGF0IHRoZSBsZXZlbCAkXGFscGhhL20kCi0gRldFUiRcbGVxXHN1bVxsaW1pdHNfe3A9MX1ee219UChyZWplY3QgSF97MHB9XHZlcnQgSF97MHB9XHRleHR7IGlzIHRydWV9KT1tIFxhbHBoYS9tPVxhbHBoYSQKLSBQcm92aWRlcyBzdHJvbmcgY29udHJvbAotIEJvbmZlcnJvbmkgaXMgdmVyeSBjb25zZXJ2YXRpdmUKLSBXb3JrcyBmb3IgZGVwZW5kZW50IHRlc3RzCi0gQWRqdXN0ZWQgcC12YWx1ZTogJFx0aWxkZXtwfV9wPVxtaW4obVwgcF9wLDEpJAoKLS0tCgojIyMjIEJvbmZlcnJvbmkgaW4gcHJhY3Rpc2UKClZpYSBSIGZ1bmN0aW9ucwoKYGBge3J9CnBhZGogPC0gcC5hZGp1c3QoCiAgcm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJHRpc3N1ZVYkcHZhbCwKICBtZXRob2QgPSAiYm9uZmVycm9uaSIpCmBgYAoKT3duIEltcGxlbWVudGF0aW9uOiBhZGp1c3QgYW5kIG1ha2Ugc3VyZSB0aGF0IHAtdmFsdWUgaXMgc21hbGxlciB0aGFuIDEuCgpgYGB7cn0KbSA8LSBzdW0oIWlzLm5hKHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSR0aXNzdWVWJHB2YWwpKQpwYWRqU2VsZiA8LSAgcm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJHRpc3N1ZVYkcHZhbCAqIG0KcGFkalNlbGZbcGFkalNlbGYgPiAxXSA8LSAxCgpyYW5nZShwYWRqIC0gcGFkalNlbGYsIG5hLnJtID0gVFJVRSkKYGBgCiMjIyMgSWxsdXN0cmF0aW9uIGluIHNpbXVsYXRpb24gdW5kZXIgJEhfMCQgYW5kIGhlYXJ0IGNhc2Ugc3R1ZHkKCmBgYHtyfQp2b2xjYW5vIDwtIGdncGxvdChyb3dEYXRhKHNpbXNbWyJzaW0wIl1dKSR0aXNzdWVWLAogICAgICAgICAgICAgICAgIGFlcyh4ID0gbG9nRkMsIHkgPSAtbG9nMTAocHZhbCksIGNvbG9yID0gcC5hZGp1c3QocHZhbCwiYm9uZmVycm9uaSIpIDwgMC4wNSkpICsKIGdlb21fcG9pbnQoY2V4ID0gMi41KSArCiBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gYWxwaGEoYygiYmxhY2siLCAicmVkIiksIDAuNSkpICsKIHRoZW1lX21pbmltYWwoKSArCiBnZ3RpdGxlKCJzaW11bGF0ZWQgaGVhcnQgZGF0YSB1bmRlciBIMCIpCnZvbGNhbm8KYGBgCgotIE5vIGZhbHNlIHBvc2l0aXZlcyBhcmUgcmV0dXJuZWQgZm9yIHNpbXVsYXRpb24gdW5kZXIgSF8wLiBMaXN0IGlzIGNvcnJlY3QgYWNjb3JkaW5nIHRvIEZXRVIuCgpgYGB7cn0Kdm9sY2FubyA8LSBnZ3Bsb3Qocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJHRpc3N1ZVYsCiAgICAgICAgICAgICAgICAgYWVzKHggPSBsb2dGQywgeSA9IC1sb2cxMChwdmFsKSwgY29sb3IgPSBwLmFkanVzdChwdmFsLCJib25mZXJyb25pIikgPCAwLjA1KSkgKwogZ2VvbV9wb2ludChjZXggPSAyLjUpICsKIHNjYWxlX2NvbG9yX21hbnVhbCh2YWx1ZXMgPSBhbHBoYShjKCJibGFjayIsICJyZWQiKSwgMC41KSkgKwogdGhlbWVfbWluaW1hbCgpICsKIGdndGl0bGUoInJlYWwgaGVhcnQgZGF0YSIpCnZvbGNhbm8KYGBgCgotIFZlcnkgZmV3IHByb3RlaW5zIGFyZSByZXR1cm5lZCBmb3IgcmVhbCBkYXRhLiBWZXJ5IGNvbnNlcnZhdGl2ZSEKCiMjIyBGV0VSOiBzdGVwIGRvd24gbWV0aG9kIG9mIEhvbG0KCi0gQ29tcGFyZSBzbWFsbGVzdCBwLXZhbHVlIHdpdGggJFxhbHBoYS9tJAotIElmIHlvdSBjYW4gcmVqZWN0IHRoZSBzbWFsbGVzdCBwLXZhbHVlIGF0ICRcYWxwaGEvbSQgbGV2ZWwKICAtIGFzc2VzIHNlY29uZCBzbWFsbGVzdCBwLXZhbHVlIGF0IHRoZSAkXGFscGhhLyhtLTEpJAotIElmIHlvdSBjYW4gcmVqZWN0IHRoZSBzZWNvbmQgc21hbGxlc3QgcC12YWx1ZSBhdCAkXGFscGhhLyhtLTEpJCBsZXZlbAogICAgLSBhc3NlcyB0aGlyZCBzbWFsbGVzdCBwLXZhbHVlIGF0IHRoZSAkXGFscGhhLyhtLTIpJAotIC4uLgotIElmIHlvdSBjYW4gcmVqZWN0IHRoZSBrLTEgc21hbGxlc3QgcC12YWx1ZSBhdCAkXGFscGhhLyhtLWsrMikkIGxldmVsCiAgLSBhc3NlcyBrIHNtYWxsZXN0IHAtdmFsdWUgYXQgdGhlICRcYWxwaGEvKG0taysxKSQgbGV2ZWwKLSBjb250aW51IGFzIGxvbmcgYXMgeW91IGNhbiByZWplY3QuCgpUaGUgSG9sbSBpcyBhIHN0ZXAgZG93biBtZXRob2QgKGZyb20gbW9yZSB0byBsZXNzIHNpZ25pZmljYW50KSB0aGF0IGNvcnJlY3RzIGluIGVhY2ggc3RlcCBmb3IgdGhlIG51bWJlciBvZiBudWxsIGh5cG90aGVzaXMgdGhhdCB5b3Ugc3RpbGwgY2FuIGZhbHNlbHkgcmVqZWN0LgoKLS0tCgpBZGp1c3RlZCBwLXZhbHVlczoKCi0gT3JkZXIgcC12YWx1ZXMgd2l0aCAkKGspJCB0aGUgJGtee3RofSQgc21hbGxlc3QgcC12YWx1ZSAgCi0gJFx0aWxkZXtwfV97KGspfT1cbWluKHBfeyhrKX0obS1rKzEpLDEpJAoKU3VwcG9zZSAyIHRlc3RzOiAkcF97KDEpfT0wLjAwMSQsICRwX3soMil9PTAuMDAxNSQKJFxyaWdodGFycm93JCAkXHRpbGRle3B9X3soMSl9PTAuMDAyJCwgJFx0aWxkZXtwfV97KDIpfT0wLjAwMTUkCgotIFByb2JsZW06IE1vbm90b25pY2l0eSBpcyBub3QgdGhlIHNhbWUgYXMgZm9yIG9yaWdpbmFsIHAtdmFsdWVzIQotIEVuZm9yY2UgbW9ub3RvbmljaXR5OgokXHRpbGRle3B9X3soayl9PVxtYXhcbGltaXRzX3toPTEsXGxkb3RzLGt9XG1pbihwX3soaCl9KG0taCsxKSwxKSQKCi0tLQoKIyMjIyBIb2xtIGV4YW1wbGUgIAoKV2l0aCBSIGZ1bmN0aW9uczoKCmBgYHtyfQpwYWRqIDwtIHAuYWRqdXN0KAogIHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSR0aXNzdWVWJHB2YWwsCiAgbWV0aG9kID0gImhvbG0iKQpgYGAKCk93biBpbXBsZW1lbnRhdGlvbgoKMS4gT3JkZXIgcC12YWx1ZXMKYGBge3J9CnBhZGpTZWxmIDwtICByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkdGlzc3VlViRwdmFsCm9yZCA8LSBvcmRlcihwYWRqU2VsZikKcE9yZCA8LSBwYWRqU2VsZltvcmRdCm0gPC0gc3VtKCFpcy5uYShwYWRqU2VsZikpCmBgYAoKMi4gQWRqdXN0IG9yZGVyZWQgcC12YWx1ZXMgYW5kIGVuc3VyZSB0aGF0IHZhbHVlIGlzIG5vdCBsYXJnZXIgdGhhbiAxCmBgYHtyfQpwT3JkWzE6bV0gPC0gcE9yZFsxOm1dKihtIC0gKDE6bSkgKyAxKQpwT3JkW3BPcmQ+MV0gPC0gMQpgYGAKCjMuIE1vbm90b25pY2l0eQpgYGB7cn0KcG1heCA8LSBwT3JkWzFdCmZvciAoaSBpbiAyOm0pCnsKICBpZiAocE9yZFtpXSA+IHBtYXgpCiAgICBwbWF4IDwtIHBPcmRbaV0gZWxzZQogICAgcE9yZFtpXSA8LSBwbWF4Cn0KYGBgCgo0LiBQdXQgYWRqdXN0ZWQgcC12YWx1ZXMgaW4gb3JpZ2luYWwgb3JkZXIKYGBge3J9CnBhZGpTZWxmW29yZF0gPC0gcE9yZApyYW5nZShwYWRqIC0gcGFkalNlbGYsIG5hLnJtID0gVFJVRSkKYGBgCgojIyMjIElsbHVzdHJhdGlvbiBpbiBzaW11bGF0aW9uIHVuZGVyICRIXzAkIGFuZCBoZWFydCBjYXNlIHN0dWR5CgpgYGB7cn0Kdm9sY2FubyA8LSBnZ3Bsb3Qocm93RGF0YShzaW1zW1sic2ltMCJdXSkkdGlzc3VlViwKICAgICAgICAgICAgICAgICBhZXMoeCA9IGxvZ0ZDLCB5ID0gLWxvZzEwKHB2YWwpLCBjb2xvciA9IHAuYWRqdXN0KHB2YWwsImhvbG0iKSA8IDAuMDUpKSArCiBnZW9tX3BvaW50KGNleCA9IDIuNSkgKwogc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGFscGhhKGMoImJsYWNrIiwgInJlZCIpLCAwLjUpKSArCiB0aGVtZV9taW5pbWFsKCkgKwogZ2d0aXRsZSgic2ltdWxhdGVkIGhlYXJ0IGRhdGEgdW5kZXIgSDAiKQp2b2xjYW5vCmBgYAoKLSBObyBmYWxzZSBwb3NpdGl2ZXMgYXJlIHJldHVybmVkIGZvciBzaW11bGF0aW9uIHVuZGVyIEhfMC4gTGlzdCBpcyBjb3JyZWN0IGFjY29yZGluZyB0byBGV0VSLgoKYGBge3J9CnZvbGNhbm8gPC0gZ2dwbG90KHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSR0aXNzdWVWLAogICAgICAgICAgICAgICAgIGFlcyh4ID0gbG9nRkMsIHkgPSAtbG9nMTAocHZhbCksIGNvbG9yID0gcC5hZGp1c3QocHZhbCwiaG9sbSIpIDwgMC4wNSkpICsKIGdlb21fcG9pbnQoY2V4ID0gMi41KSArCiBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gYWxwaGEoYygiYmxhY2siLCAicmVkIiksIDAuNSkpICsKIHRoZW1lX21pbmltYWwoKSArCiBnZ3RpdGxlKCJyZWFsIGhlYXJ0IGRhdGEiKQp2b2xjYW5vCmBgYAoKLSBWZXJ5IGZldyBwcm90ZWlucyBhcmUgcmV0dXJuZWQgZm9yIHJlYWwgZGF0YS4gU3RpbGwgdmVyeSBjb25zZXJ2YXRpdmUhCgoKIyMgRmFsc2UgZGlzY292ZXJ5IHJhdGUKCi0gQWRqdXN0ZWQgUC12YWx1ZXMgd2l0aCB0aGUgQmVuamFtaW5pIEhvY2hiZXJnIGNvcnJlY3Rpb24gY29ycmVzcG9uZCB0byB0aGUgZXN0aW1hdGVkIEZEUiBvZiB0aGUgc2V0IHRoYXQgaXMgcmV0dXJuZWQgd2hlbiB0aGUgc2lnbmlmaWNhbmNlIGxldmVsIGlzIHNldCBhdCB0aGlzIHRocmVzaG9sZC4KXGJlZ2lue2VxbmFycmF5fQpGRFIocF8wKSAmPSYgXHRleHR7RX1cbGVmdFtcZnJhY3tGUH17KEZQICsgVFApfVxyaWdodF1cXAomXGFwcHJveCZcZnJhY3twXzAgXHRpbWVzIG19e1wjcF9wIFxsZXEgcF8wfVxcClxlbmR7ZXFuYXJyYXl9CgpTbyBhZGp1c3RlZCBwLXZhbHVlIGZvciBwcm90ZWluIGogZXF1YWxzClxbXHRpbGRlIHBfaiA9IFxmcmFje3BfezAsan0gXHRpbWVzIG19e1wjcF9wIFxsZXEgcF97MCxqfX1cXQoKSG93ZXZlciwgdGhlIEZEUiBhbHdheXMgaGFzIHRvIGJlIGJldHdlZW4gMCBhbmQgMSBzbzoKClxbXHRpbGRlIHBfaiA9IFxtaW5cbGVmdFtcZnJhY3twX3swLGp9IFx0aW1lcyBtfXtcI3BfcCBcbGVxIHBfezAsan19LDFccmlnaHRdXF0KCmFuZCB0aGUgYWRqdXN0ZWQgcC12YWx1ZXMgc2hvdWxkIHJlbWFpbiBpbiB0aGUgc2FtZSBvcmRlciBhcyB0aGUgb3JpZ2luYWwgcC12YWx1ZXMuCgpcW1x0aWxkZSBwX2ogPSAgXG1pblxsaW1pdHNfe1xmb3JhbGwgazogcF9rID4gcF9qfSBcbWluXGxlZnRbXGZyYWN7cF97MCxrfSBcdGltZXMgbX17XCNwX3AgXGxlcSBwX3swLGt9fSwxXHJpZ2h0XVxdCgoxLiBPcmRlciBwdmFsdWVzCmBgYHtyfQpwdmFscyA8LSByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkdGlzc3VlViRwdmFsCm5hSW5kIDwtIGlzLm5hKHB2YWxzKQpwSGxwIDwtIHB2YWxzWyFuYUluZF0Kb3JkIDwtIHBIbHAgJT4lIG9yZGVyCnBIbHAgPC0gcEhscFtvcmRdCmBgYAoKMi4gQWRqdXN0IG9yZGVyZWQgcC12YWx1ZXMKYGBge3J9CnBIbHAgPC0gcEhscCpsZW5ndGgocEhscCkvKDE6bGVuZ3RoKHBIbHApKQpgYGAKCjMuIEVuc3VyZSBhZGp1c3QgcC12YWx1ZXMgYXJlIHNtYWxsZXIgYXJlIGVxdWFsIHRoYW4gMQpgYGB7cn0KcEhscFtwSGxwPjFdIDwtIDEKYGBgCgo0LiBNb25vdG9uaWNpdHkgY29uc3RyYWludApgYGB7cn0KcG1pbiA8LSBwSGxwW2xlbmd0aChwSGxwKV0KZm9yIChqIGluIChsZW5ndGgocEhscCktMSk6MSkKewogIGlmIChwSGxwW2pdIDwgcG1pbikKICAgIHBtaW4gPC0gcEhscFtqXSBlbHNlCiAgICBwSGxwW2pdIDwtIHBtaW4gICAKfQpgYGAKCjUuIFB1dCBwLXZhbHVlcyBiYWNrIGluIG9yaWdpbmFsIG9yZGVyCgpgYGB7cn0KcEhscFtvcmRdIDwtIHBIbHAKcEFkaiA8LSBwdmFscwpwQWRqWyFuYUluZF0gPC0gcEhscAoKaGVhZChwQWRqKQpoZWFkKHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSR0aXNzdWVWKQpyYW5nZShyb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkdGlzc3VlViRhZGpQdmFsIC0gcEFkaixuYS5ybT1UUlVFKQpgYGAKCiMjIyMgSWxsdXN0cmF0aW9uIGluIHNpbXVsYXRpb24gdW5kZXIgJEhfMCQgYW5kIGhlYXJ0IGNhc2Ugc3R1ZHkKCmBgYHtyfQp2b2xjYW5vIDwtIGdncGxvdChyb3dEYXRhKHNpbXNbWyJzaW0wIl1dKSR0aXNzdWVWLAogICAgICAgICAgICAgICAgIGFlcyh4ID0gbG9nRkMsIHkgPSAtbG9nMTAocHZhbCksIGNvbG9yID0gYWRqUHZhbCA8IDAuMDUpKSArCiBnZW9tX3BvaW50KGNleCA9IDIuNSkgKwogc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGFscGhhKGMoImJsYWNrIiwgInJlZCIpLCAwLjUpKSArCiB0aGVtZV9taW5pbWFsKCkgKwogZ2d0aXRsZSgic2ltdWxhdGVkIGhlYXJ0IGRhdGEgdW5kZXIgSDAiKQp2b2xjYW5vCmBgYAoKLSBObyBmYWxzZSBwb3NpdGl2ZXMgYXJlIHJldHVybmVkIGZvciBzaW11bGF0aW9uIHVuZGVyIEhfMC4gTGlzdCBpcyBjb3JyZWN0IGFjY29yZGluZyB0byBGV0VSLgotIEl0IGNhbiBiZSBzaG93biB0aGF0IHRoZSBGRFItbWV0aG9kIGNvbnRyb2xzIHRoZSBGV0VSIHdoZW4gJEhfMCQgaXMgdHJ1ZSBmb3IgYWxsIGZlYXR1cmVzLiAgIAoKCmBgYHtyfQp2b2xjYW5vIDwtIGdncGxvdChyb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkdGlzc3VlViwKICAgICAgICAgICAgICAgICBhZXMoeCA9IGxvZ0ZDLCB5ID0gLWxvZzEwKHB2YWwpLCBjb2xvciA9IGFkalB2YWwgPCAwLjA1KSkgKwogZ2VvbV9wb2ludChjZXggPSAyLjUpICsKIHNjYWxlX2NvbG9yX21hbnVhbCh2YWx1ZXMgPSBhbHBoYShjKCJibGFjayIsICJyZWQiKSwgMC41KSkgKwogdGhlbWVfbWluaW1hbCgpICsKIGdndGl0bGUoInJlYWwgaGVhcnQgZGF0YSIpCnZvbGNhbm8KYGBgCgpUaGUgRkRSIG1ldGhvZCBhbGxvd3MgdXMgdG8gcmV0dXJuIG11Y2ggbG9uZ2VyIERBIHByb3RlaW4gbGlzdHMgYXQgdGhlIGV4cGVuc2Ugb2YgYSBmZXcgZmFsc2UgcG9zaXRpdmVzLgpUaGUgRkRSIGNvbnRyb2xzIHRoZSBmcmFjdGlvbiBvZiBmYWxzZSBwb3NpdGl2ZXMgaW4gdGhlIGxpc3QgdGhhdCB5b3UgcmV0dXJuIG9uIGF2ZXJhZ2Ugb24gdGhlIHNpZ25pZmljYW5jZSBsZXZlbCB0aGF0IGlzIGFkb3B0ZWQuClNvIGlmIHlvdSB1c2UgJFxhbHBoYT0wLjA1JCB3ZSBleHBlY3Qgb24gYXZlcmFnZSA1JSBvZiBmYWxzZSBwb3NpdGl2ZXMgaW4gdGhlIGxpc3QgdGhhdCB3ZSByZXR1cm4uCg==