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 9.179357e-17
## tissueV -0.2625849 2.625849e-01 5.251699e-01 6.475378e-17
## patient4 -0.1969387 9.179357e-17 6.475378e-17 3.938774e-01
## patient8 -0.1969387 1.372344e-16 1.337955e-16 1.969387e-01
## locationR:tissueV 0.2625849 -5.251699e-01 -5.251699e-01 3.121582e-17
## patient8 locationR:tissueV
## (Intercept) -1.969387e-01 2.625849e-01
## locationR 1.372344e-16 -5.251699e-01
## tissueV 1.337955e-16 -5.251699e-01
## patient4 1.969387e-01 3.121582e-17
## patient8 3.938774e-01 -1.321146e-16
## locationR:tissueV -1.321146e-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 -2.625849e-01 -2.625849e-01 -0.1969387 -0.1969387
## locationR -0.2625849 5.251699e-01 2.625849e-01 0.0000000 0.0000000
## tissueV -0.2625849 2.625849e-01 5.251699e-01 0.0000000 0.0000000
## patient4 -0.1969387 -4.372918e-17 -4.372918e-17 0.3938774 0.1969387
## patient8 -0.1969387 -4.372918e-17 -4.372918e-17 0.1969387 0.3938774
## locationR:tissueV 0.2625849 -5.251699e-01 -5.251699e-01 0.0000000 0.0000000
## locationR:tissueV
## (Intercept) 2.625849e-01
## locationR -5.251699e-01
## tissueV -5.251699e-01
## patient4 4.372918e-17
## patient8 4.372918e-17
## locationR:tissueV 1.050340e+00
range(SigmaBeta - summary(fit)$cov.unscaled * sigma(fit)^2)
## [1] -1.998401e-15 3.774758e-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
## Warning: package 'mvtnorm' was built under R version 4.4.1
## 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)
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])))
## Warning: `qplot()` was deprecated in ggplot2 3.4.0.
## This warning is displayed once every 8 hours.
## Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
## generated.
## [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 0.552 1.000 1.000 1.000 1.000 0.762 1.000 1.000 1.000
## [13] 1.000 1.000 1.000 1.000 0.793 1.000 1.000 0.122
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] 0.7675072
median(abs(res-median(res)))*1.4826
## [1] 0.7675072
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.2, … , 1.93.
- 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 degrees of freedom are also set to infinity:
getDF(rowData(sims[["sim_equalVar"]])$msqrobModels[[1]])
## [1] 5.832087
getDfPosterior(rowData(sims[["sim_equalVar"]])$msqrobModels[[1]])
## [1] Inf
which imposes shrinkage to the prior standard deviation!
The empirical Bayes method can thus indeed recognize the common
variance that is shared across all simulated 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 or values outside the scale range
## (`geom_point()`).
- Very few proteins are returned for real data. 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 or values outside the scale range
## (`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+IGxvY2F0aW9uICogdGlzc3VlICsgcGF0aWVudCwgY29sRGF0YShwZSkpCmhlYWQoWCw0KQpgYGAKCkxlYXN0IHNxdWFyZXM6CmBgYHtyfQpiZXRhcyA8LSBzb2x2ZSh0KFgpJSolWCkgJSolIHQoWCkgJSolIHkKY2JpbmQoZml0JGNvZWYsIGJldGFzKQpgYGAKCi0tLQoKIyMjIFZhcmlhbmNlIEVzdGltYXRvcj8KXFsKXGJlZ2lue2FycmF5fXtjY2x9ClxoYXR7XGJvbGRzeW1ib2x7XFNpZ21hfX1fe1xoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX0KJj0mXHRleHR7dmFyfVxsZWZ0WyhcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9XG1hdGhiZntYfV5UXG1hdGhiZntZfVxyaWdodF1cXFxcCiY9JihcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9XG1hdGhiZntYfV5UXHRleHR7dmFyfVxsZWZ0W1xtYXRoYmZ7WX1ccmlnaHRdXG1hdGhiZntYfShcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9XFxcXAomPSYoXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxtYXRoYmZ7WH1eVChcbWF0aGJme0l9XHNpZ21hXjIpXG1hdGhiZntYfShcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9ClxcXFwKJj0mKFxtYXRoYmZ7WH1eVFxtYXRoYmZ7WH0pXnstMX1cbWF0aGJme1h9XlRcbWF0aGJme0l9XHF1YWRcbWF0aGJme1h9KFxtYXRoYmZ7WH1eVFxtYXRoYmZ7WH0pXnstMX1cc2lnbWFeMlxcXFwKJVxoYXR7XGJvbGRtYXRoe1xTaWdtYX19X3tcaGF0e1xib2xkc3ltYm9se1xiZXRhfX19Jj0mKFxtYXRoYmZ7WH1eVFxtYXRoYmZ7WH0pXnstMX1cbWF0aGJme1h9XlRcdmFyXGxlZnRbXG1hdGhiZntZfVxyaWdodF0oXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxtYXRoYmZ7WH1cXAomPSYoXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxtYXRoYmZ7WH1eVFxtYXRoYmZ7WH0oXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxzaWdtYV4yXFxcXAomPSYoXG1hdGhiZntYfV5UXG1hdGhiZntYfSleey0xfVxzaWdtYV4yClxlbmR7YXJyYXl9ClxdCgotLS0KCiMjIyMgSGVhcnQgZXhhbXBsZQoKCmBgYHtyfQpzdW1tYXJ5KGZpdCkkY292LnVuc2NhbGVkICogc2lnbWEoZml0KV4yCmBgYAoKYGBge3J9Cm4gPC0gbnJvdyhYKQpwIDwtIG5jb2woWCkKbXNlIDwtIHN1bSgoeS1YJSolYmV0YXMpXjIpLyhuLXApClNpZ21hQmV0YSA8LSBzb2x2ZSh0KFgpJSolWCkgKiBtc2UgICAKU2lnbWFCZXRhCnJhbmdlKFNpZ21hQmV0YSAtIHN1bW1hcnkoZml0KSRjb3YudW5zY2FsZWQgKiBzaWdtYShmaXQpXjIpCmBgYAoKYGBge3J9CmRhdGEuZnJhbWUoc3VtbWFyeShmaXQpJGNvZWZbLDE6Ml0sIGJldGFzID0gYmV0YXMsIHNlQmV0YXMgPSBkaWFnKFNpZ21hQmV0YSleLjUpCmBgYAoKIyMgQ29udHJhc3RzCgpXaGVuIHdlIGFzc2VzcyBhIGNvbnRyYXN0IHdlIGFzc2VzcyBhIGxpbmVhciBjb21iaW5hdGlvbiBvZiBtb2RlbCBwYXJhbWV0ZXJzOgoKXFsgSF8wOiBcbWF0aGJme0xeVFxiZXRhfSA9IDAgXHRleHR7IHZzIH0gSF8xOiBcbWF0aGJme0xeVFxiZXRhfSBcbmVxIDAgXF0KCkVzdGltYXRvciBvZiBDb250cmFzdD8KClxbXG1hdGhiZntMfV5UXGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19XF0KCgpWYXJpYW5jZT8KClxbClxib2xkc3ltYm9se1xTaWdtYX1fe1xtYXRoYmZ7TH1caGF0e1xib2xkc3ltYm9se1xiZXRhfX19PVxtYXRoYmZ7TH1eVFxib2xkc3ltYm9se1xTaWdtYX1fe1xoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX1cbWF0aGJme0x9ClxdCgotLS0KCiMjIyBIZWFydCBleGFtcGxlCgpgYGB7cn0KTCA8LSBtYWtlQ29udHJhc3QoCiAgYygKICAgICJ0aXNzdWVWID0gMCIsCiAgICAidGlzc3VlViArIGxvY2F0aW9uUjp0aXNzdWVWID0gMCIsCiAgICAidGlzc3VlViArIDAuNSpsb2NhdGlvblI6dGlzc3VlViA9IDAiLCJsb2NhdGlvblI6dGlzc3VlViA9IDAiKSwKICBwYXJhbWV0ZXJOYW1lcyA9CiAgICByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkbXNxcm9iTW9kZWxzW1syXV0gJT4lCiAgICBnZXRDb2VmICU+JQogICAgbmFtZXMKICApCkwKYGBgCgpgYGB7cn0KY29udHJhc3RzIDwtIHQoTCkgJSolIGJldGFzClNpZ21hQ29udHJhc3RzIDwtIHQoTCkgJSolIFNpZ21hQmV0YSAlKiUgTApzZUNvbnRyYXN0cyA8LSBTaWdtYUNvbnRyYXN0cyAlPiUKICBkaWFnICU+JQogIHNxcnQKYGBgCgpDb21wYXJpc29uIHdpdGggbG0gYW5kIGdsaHQgcmVzdWx0cwoKYGBge3J9CmxpYnJhcnkobXVsdGNvbXApCmZpdEdsaHQgPC0gZ2xodChmaXQsIGxpbmZjdCA9IHQoTCkpCnN1bW1hcnkoZml0R2xodCwgdGVzdCA9IGFkanVzdGVkKCJub25lIikpCmRhdGEuZnJhbWUoY29udHJhc3RzLCBzZUNvbnRyYXN0cykKYGBgCgotIE5vdGUsIHRoYXQgdGhlIHBvd2VyIGZvciBhc3Nlc3NpbmcgJFxsb2dfMiQgRkMgYmV0d2VlbiB2ZW50cmljdWx1bSBhbmQgYXRyaXVtICBsZWZ0IGFuZCByaWdodCBpcyB0aGUgc2FtZS4gSW5kZWVkLCB0aGUgc3RhbmRhcmQgZXJyb3JzIGFyZSBlcXVhbCBmb3IgYm90aCBlZmZlY3RzLgoKCi0gTm90ZSwgdGhhdCB0aGUgcG93ZXIgZm9yIGFzc2Vzc2luZyAkXGxvZ18yJCBGQyBiZXR3ZWVuIHZlbnRyaWN1bHVtIGFuZCBhdHJpdW0gb3ZlciBib3RoIGhlYXJ0IHJlZ2lvbnMgaXMgaGlnaGVyIHRoYW4gd2hlbiBhc3Nlc3NpbmcgdGhlIGVmZmVjdCBsZWZ0IG9yIHJpZ2h0LgoKICAtIEluZGVlZCwgdGhlIHN0YW5kYXJkIGVycm9yIGlzIGEgZmFjdG9yICRcc3FydHsyfSQgc21hbGxlciBmb3IgdGhlIGZvcm1lciBlZmZlY3QKICAtIFdlIGludHVpdGl2ZWx5IGNhbiBleHBsYWluIHRoaXMgYmVjYXVzZSB3ZSBjYW4gdXNlIGFsbCBzYW1wbGVzIChkb3VibGUgdGhlIG51bWJlciBvZiBzYW1wbGVzKSB0byBhc3Nlc3MgdGhlIGF2ZXJhZ2UgZWZmZWN0LgogIC0gSGVuY2UgdGhlIHZhcmlhbmNlIGlzIGEgZmFjdG9yIHR3byBzbWFsbGVyLCBhbmQgdGhlIHNlIHdpdGggYSBmYWN0b3IgJFxzcXJ0ezJ9JAoKLSBOb3RlLCB0aGF0IHdlIGhhdmUgdGhlIGxvd2VzdCBwb3dlciB0byBwaWNrIHVwIGFuIGludGVyYWN0aW9uIGVmZmVjdC4gSW5kZWVkLCB0aGUgc2UgaXMgYSBmYWN0b3IgJFxzcXJ0ezJ9JCBsYXJnZXIgdGhhbiBmb3IgdGhlIHZlbnRyaWN1bHVtIC0gYXRyaXVtIGVmZmVjdCBsZWZ0IG9yIHJpZ2h0IGFuZCBhIGZhY3RvciAyIGxhcmdlciB0aGFuIGZvciB0aGUgYXZlcmFnZSBlZmZlY3QgYmV0d2VlbiB2ZW50cmljdWx1bSBhbmQgYXRyaXVtLgoKYGBge3J9CnNlQ29udHJhc3RzIC8gc2VDb250cmFzdHNbMV0Kc3FydCgyKQoxL3NxcnQoMikKYGBgCgojIyMgdC10ZXN0cwoKIC0gV2hlbiB0aGUgYXNzdW1wdGlvbnMgb2YgdGhlIGxpbmVhciBtb2RlbCBob2xkClxbClxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fSBcc2ltIE1WTlxsZWZ0W1xib2xkc3ltYm9se1xiZXRhfSxcbGVmdChcbWF0aGJme1h9XlRcbWF0aGJme1h9XHJpZ2h0KV57LTF9XHNpZ21hXjJccmlnaHRdClxdCi0gSGVuY2UsClxbClxtYXRoYmZ7TH1eVFxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fSBcc2ltIE1WTlxsZWZ0W1xtYXRoYmZ7TH1eVFxib2xkc3ltYm9se1xiZXRhfSxcbWF0aGJme0x9XlRcbGVmdFtcbGVmdChcbWF0aGJme1h9XlRcbWF0aGJme1h9XHJpZ2h0KV57LTF9XHNpZ21hXjJccmlnaHRdXG1hdGhiZntMfVxyaWdodF0KXF0KLSBXZSBlc3RpbWF0ZSAkXHNpZ21hXjIkIGJ5IE1TRQokJFxoYXR7XHNpZ21hfV4yPVxmcmFje1xtYXRoYmZ7ZX1eVFxtYXRoYmZ7ZX19e24tcH0gXHJpZ2h0YXJyb3cgXGhhdHtcYm9sZHN5bWJvbHtcU2lnbWF9fV97XGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19fT1cbGVmdChcbWF0aGJme1h9XlRcbWF0aGJme1h9XHJpZ2h0KV57LTF9XGhhdFxzaWdtYV4yJCQKCi0gV2hlbiB3ZSB0ZXN0IG9uZSBjb250cmFzdCBhdCB0aGUgdGltZSAoZS5nLiB0aGUgJGteXHRleHR7dGh9JCBjb250cmFzdCkgdGhlIHN0YXRpc3RpYyByZWR1Y2VzIHRvCgokJFQ9XGZyYWN7XG1hdGhiZntMfV9rXlRcaGF0e1xib2xkc3ltYm9se1xiZXRhfX19e1xzcXJ0e1xsZWZ0KFxtYXRoYmZ7TH1eVF9rXGhhdHtcYm9sZHN5bWJvbHtcU2lnbWF9fV97XGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19fVxtYXRoYmZ7TH1fa1xyaWdodCl9fSBcdW5kZXJzZXR7SF8wfXtcc2ltfSB0X3tuLXB9JCQKZm9sbG93cyBhIHQgZGlzdHJpYnV0aW9uIHdpdGggbi1wIGRlZ3JlZXMgb2YgZnJlZWRvbSB1bmRlciAkSF8wOiBcbWF0aGJme0x9XlRfa1xoYXR7XGJvbGRzeW1ib2x7XGJldGF9fT0wJAoKLS0tCgojIyMjIEhlYXJ0IGV4YW1wbGUKCmBgYHtyfQp0Q29udHJhc3RzIDwtIGNvbnRyYXN0cy9zZUNvbnRyYXN0cwpwQ29udHJhc3RzIDwtIHB0KGFicyh0Q29udHJhc3RzKSwKICBkZiA9IG4gLSBwLAogIGxvd2VyLnRhaWwgPSBGQUxTRSkgKiAyCmBgYAoKQ29tcGFyaXNvbiB3aXRoIGxtIGFuZCBnbGh0IHJlc3VsdHMKCmBgYHtyfQpzdW1tYXJ5KGZpdEdsaHQsIHRlc3QgPSBhZGp1c3RlZCgibm9uZSIpKQpkYXRhLmZyYW1lKGNvbnRyYXN0cywgc2VDb250cmFzdHMsIHRDb250cmFzdHMsIHBDb250cmFzdHMpCmBgYAoKCi0tLQoKIyBSb2J1c3QgcmVncmVzc2lvbgoKLSBXaXRoIG1zcXJvYjIgd2UgcGVyZm9ybSByb2J1c3QgcmVncmVzc2lvbiB0byBlc3RpbWF0ZSB0aGUgbW9kZWwgcGFyYW1ldGVycyBvZiB0aGUgcmVncmVzc2lvbiBtb2RlbAoKLSBObyBub3JtYWxpdHkgYXNzdW1wdGlvbiBuZWVkZWQKLSBSb2J1c3QgZml0IG1pbmltaXNlcyB0aGUgbWF4aW1hbCBiaWFzIG9mIHRoZSBlc3RpbWF0b3JzCi0gQ0kgYW5kIHN0YXRpc3RpY2FsIHRlc3RzIGFyZSBiYXNlZCBvbiBhc3ltcHRvdGljIHRoZW9yeQotIElmICRcZXBzaWxvbiQgaXMgbm9ybWFsLCB0aGUgTS1lc3RpbWF0b3JzIGhhdmUgYSBoaWdoIGVmZmljaWVuY3khCi0gb3JkaW5hcnkgbGVhc3Qgc3F1YXJlcyAoT0xTKTogbWluaW1pemUgbG9zcyBmdW5jdGlvbiBcW1xzdW1cbGltaXRzX3tpPTF9Xm4gKHlfaS1cbWF0aGJme3h9X2leVFxib2xkc3ltYm9se1xiZXRhfSleMlxdCgotIE0tZXN0aW1hdGlvbjogbWluaW1pemUgbG9zcyBmdW5jdGlvbgpcW1xzdW1cbGltaXRzX3tpPTF9Xm4gIFxyaG9cbGVmdCh5X2ktXG1hdGhiZnt4fV9pXlRcYm9sZHN5bWJvbHtcYmV0YX1ccmlnaHQpXF0Kd2l0aAoKICAtICRccmhvJCBpcyBzeW1tZXRyaWMsIGkuZS4gJFxyaG8oeik9XHJobygteikkCiAgLSAkXHJobyQgaGFzIGEgbWluaW11bSBhdCAkXHJobygwKT0wJCwgaXMgcG9zaXRpdmUgZm9yIGFsbCAkelxuZXEgMCQKICAtICRccmhvKHopJCBpbmNyZWFzZXMgYXMgJFx2ZXJ0IHpcdmVydCQgaW5jcmVhc2VzCgotLS0KCiBUaGUgZXN0aW1hdG9yICRcaGF0e1xtdX0kIGlzIGFsc28gdGhlIHNvbHV0aW9uIHRvIHRoZSBlcXVhdGlvbgogXFsKICAgXHN1bV97aT0xfV5uIFxQc2koeV9pIC0gXG1hdGhiZnt4fV9pXGJvbGRzeW1ib2x7XGJldGF9KSA9MCwKIFxdCiB3aGVyZSAkXFBzaSQgaXMgdGhlIGRlcml2YXRpdmUgb2YgJFxyaG8kLiBGb3IgJFxoYXR7XGJldGF9JCBwb3NzZXNzaW5nIHRoZSByb2J1c3RuZXNzIHByb3BlcnR5LCAkXFBzaSQgc2hvdWxkIGJlIGJvdW5kZWQuCgotLS0KCiBFeGFtcGxlOiBsZWFzdCBzcXVhcmVzCgogLSAkXHJobyh6KSA9IHpeMiQsIGFuZCB0aHVzICRcUHNpKHopPTJ6JCAodW5ib3VuZGVkISkuIE5vdCByb2J1c3QhCgotICRcaGF0e1xib2xkc3ltYm9se1xiZXRhfX0kIGlzIHRoZSBzb2x1dGlvbiBvZgogXFsKICAgXHN1bV97aT0xfV5uIDIgXG1hdGhiZnt4fV9pICh5X2kgLSBcbWF0aGJme3h9X2leVFxib2xkc3ltYm9se1xiZXRhfSkgPSAwIFx0ZXh0eyBvciB9IFxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fSA9IChcbWF0aGJme1h9XlRcbWF0aGJme1h9KV57LTF9XG1hdGhiZntYfVxtYXRoYmZ7eX0KIFxdCiB3aXRoICRcbWF0aGJme1h9PVtcbWF0aGJme3h9XzEgXGxkb3RzIFxtYXRoYmZ7eH1fR11eVCQKCi0tLQoKIFdoZW4gYSBsb2NhdGlvbiBhbmQgYSBzY2FsZSBwYXJhbWV0ZXIsIHNheSAkXHNpZ21hJCwgaGF2ZSB0byBiZSBlc3RpbWF0ZWQgc2ltdWx0YW5lb3VzbHksIHdlIHdyaXRlCiBcWwogICAoXGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19LFxoYXR7XHNpZ21hfSkgPSBcdGV4dHtBcmdNaW59X3tcYm9sZHN5bWJvbHtcYmV0YX0sXHNpZ21hfSBcc3VtX3tpPTF9Xm4gXHJob1xsZWZ0KFxmcmFje3lfaSAtIFxtYXRoYmZ7eH1faV5UXGJvbGRzeW1ib2x7XGJldGF9fXtcc2lnbWF9XHJpZ2h0KQogICBcdGV4dHsgYW5kIH0gXHN1bV97aT0xfV5uIFxQc2lcbGVmdChcZnJhY3t5X2kgLSBcbWF0aGJme3h9X2leVFxib2xkc3ltYm9se1xiZXRhfX17XHNpZ21hfVxyaWdodCkgPTAuCiBcXQoKIERlZmluZSAkdV9pID0gXGZyYWN7eV9pIC0gXG1hdGhiZnt4fV9pXlRcYm9sZHN5bWJvbHtcYmV0YX19e1xzaWdtYX0kLiBUaGUgbGFzdCBlc3RpbWF0aW9uIGVxdWF0aW9uIGlzIGVxdWl2YWxlbnQgdG8KIFxbCiAgIFxzdW1fe2k9MX1ebiB3KHVfaSkgdV9pID0gMCAsCiBcXQogd2l0aCB3ZWlnaHQgZnVuY3Rpb24gJHcodSk9XFBzaSh1KS91JC4gVGhpcyBpcyB0aGUgdHlwaWNhbCBmb3JtIHRoYXQgYXBwZWFycyB3aGVuIHNvbHZpbmcgdGhlCiAqaXRlcmF0aXZlbHkgcmV3ZWlnaHRlZCBsZWFzdCBzcXVhcmVzIHByb2JsZW0qLAogXFsKICAgKFxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fSxcaGF0e1xzaWdtYX0pID0gXHRleHR7QXJnTWlufV97XG11LFxzaWdtYX0gXHN1bV97aT0xfV5uIHcodV9pXnsoay0xKX0pIFxsZWZ0KHVfaV57KGspfVxyaWdodCleMiAsCiBcXQogd2hlcmUgJGskIHJlcHJlc2VudHMgdGhlIGl0ZXJhdGlvbiBudW1iZXIuCgotLS0KCiMjIFNvbWUgRXhhbXBsZXMgb2YgUm9idXN0IEZ1bmN0aW9ucwoKIVtdKGh0dHBzOi8vcmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbS9zdGF0T21pY3MvU0dBMjAyMC9naC1wYWdlcy9hc3NldHMvVGFibGVSb2J1c3QuUE5HKQoKUGhEIHRoZXNpcyBCb2xzdGFkIDIwMDQKCi0tLQoKIyMgVGhlICRccmhvJCBmdW5jdGlvbnMKCiFbXShodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vc3RhdE9taWNzL1NHQTIwMjAvZ2gtcGFnZXMvYXNzZXRzL1Job1JvYnVzdC5QTkcpCgpQaEQgdGhlc2lzIEJvbHN0YWQgMjAwNAoKLS0tCgojIyMgQ29tbW9uICRcUHNpJC1GdW5jdGlvbnMKIVtdKGh0dHBzOi8vcmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbS9zdGF0T21pY3MvU0dBMjAyMC9naC1wYWdlcy9hc3NldHMvcm9idXN0UmVncmVzc2lvblBzaS5wbmcpCgpQaEQgdGhlc2lzIEJvbHN0YWQgMjAwNAoKLS0tCgojIyMgQ29ycmVzcG9uZGluZyBXZWlnaHQgRnVuY3Rpb25zCiFbXShodHRwczovL3Jhdy5naXRodWJ1c2VyY29udGVudC5jb20vc3RhdE9taWNzL1NHQTIwMjAvZ2gtcGFnZXMvYXNzZXRzL3JvYnVzdFJlZ3Jlc3Npb25XZWlnaHRzLnBuZykKClBoRCB0aGVzaXMgQm9sc3RhZCAyMDA0CgotLS0KCmBgYHtyfQpsaWJyYXJ5KCJNQVNTIikKcmZpdCA8LSBybG0oeSB+IGxvY2F0aW9uICogdGlzc3VlICsgcGF0aWVudCwgY29sRGF0YShwZSksIG1heGl0PTEpCnFwbG90KGZpdCRjb2VmZmljaWVudFstMV0sCiAgcmZpdCRjb2VmZmljaWVudFstMV0sCiAgeGxhYj0iZml0IiwKICB5bGFiPSJyb2J1c3QgZml0IikgKwogIGdlb21fYWJsaW5lKCkgKwogIHhsaW0ocmFuZ2UoYyhmaXQkY29lZmZpY2llbnRbLTFdLHJmaXQkY29lZmZpY2llbnRbLTFdKSkpICsKICB5bGltKHJhbmdlKGMoZml0JGNvZWZmaWNpZW50Wy0xXSxyZml0JGNvZWZmaWNpZW50Wy0xXSkpKQpgYGAKCi0tLQoKYGBge3J9CnJmaXQkdwpwbG90KAogIHJmaXQkZml0dGVkLAogIHJmaXQkcmVzLAogIGNleD1yZml0JHcsCiAgcGNoPTE5LGNvbD0yLAogIGNleC5sYWI9MS41LAogIGNleC5heGlzPTEuNSwKICB5bGFiPSJyZXNpZHVhbHMiLAogIHhsYWI9ImZpdCIpCnBvaW50cyhyZml0JGZpdHRlZCwgcmZpdCRyZXMgLCBjZXg9IDEuNSkKYGBgCgotLS0KCmBgYHtyfQpzdW1tYXJ5KGZpdCkKc3VtbWFyeShyZml0KQpyb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkbXNxcm9iTW9kZWxzW1syXV0gJT4lIGdldENvZWYKYGBgCgotLS0KCiMjIFVuZGVyc3RhbmRpbmcgaW1wbGVtZW50YXRpb24gb2Ygcm9idXN0IHJlZ3Jlc3Npb24KCiMjIyBTaW11bGF0ZSAyMCBvYnNlcnZhdGlvbnMgZnJvbSBhIGxpbmVhciBtb2RlbCB3aXRoIGVycm9ycyB0aGF0IGZvbGxvdyBhIG5vcm1hbCBkaXN0cmlidXRpb24KCmBgYHtyfQpzZXQuc2VlZCA8LSAxMTIzNTgKbm9icyA8LSAyMApzZHkgPC0gMQp4c2ltIDwtIHNlcSgwLCAxLCBsZW5ndGgub3V0ID0gbm9icykKeXNpbSA8LSAxMCArIDUqeHNpbSArIHJub3JtKG5vYnMsIHNkID0gc2R5KQpgYGAKCiMjIyBhZGQgb3V0bGllciBhdCBoaWdoIGxldmVyYWdlIHBvaW50CgpgYGB7cn0KeXNpbVtub2JzXSA8LSA3CmBgYAoKIyMjIGZpdCBsaW5lYXIgbW9kZWwKCmBgYHtyfQpvbHMgPC0gbG0oeXNpbSB+IHhzaW0pCmBgYAoKIyMjIGZpdCByb2J1c3QgbGluZWFyIG1vZGVsCgpgYGB7cn0KbGlicmFyeShNQVNTKQptRXN0IDwtIHJsbSh5c2ltIH4geHNpbSkKYGBgCgojIyMjIHBsb3QgcmVzdWx0cwoKYGBge3J9CnBsb3QoeHNpbSwgeXNpbSkKYWJsaW5lKG9scywgbHdkID0gMikKYWJsaW5lKG1Fc3QsIGNvbCA9ICJyZWQiLCBsd2QgPSAyKQpsZWdlbmQoInRvcGxlZnQiLAogIGxlZ2VuZCA9IGMoIk9MUyIsICJNLWVzdGltYXRpb24iKSwKICBsd2QgPSAyLAogIGNvbCA9IDE6MikKcm91bmQobUVzdCR3LDMpCmBgYAoKVGhlIHBsb3QgY2xlYXJseSBzaG93cyB0aGF0IHRoZSBvdXRsaWVyIGhhcyBhIGhpZ2ggaW1wYWN0IG9uIHRoZSBzbG9wZSBlc3RpbWF0ZS4KVGhpcyBpcyBiZWNhdXNlIHRoZSBvdXRsaWVyIGlzIGF0IGEgaGlnaCBsZXZlcmFnZSBwb2ludCwgaS5lLiBmYXIgZnJvbSB0aGUgYXZlcmFnZSBjb3ZhcmlhdGUgcGF0dGVybi4KCiMjIyBJbXBsZW1lbnQgaXQgeW91cnNlbGYKIyMjIyBzdGFydCBmcm9tIG9scyBmaXQKCmBgYHtyfQpsbU1vZCA8LSBvbHMKYGBgCgojIyMjIFVzZSByb2J1c3QgdmFyaWFuY2UgZXN0aW1hdG9yIHRvIGNhbGN1bGF0ZSB0aGUgegoKYGBge3J9CnJlcyA8LSBsbU1vZCRyZXMKc3RkZXYgPC0gbWFkKHJlcykKc3RkZXYKbWVkaWFuKGFicyhyZXMtbWVkaWFuKHJlcykpKSoxLjQ4MjYKeiA8LSByZXMvc3RkZXYKYGBgCgojIyMjIENhbGN1bGF0ZSB3ZWlnaHRzIHVzZSBwc2kuaHViZXIgZnVuY3Rpb24KCmBgYHtyfQp3IDwtIHBzaS5odWJlcih6KQpwbG90KHhzaW0sIHlzaW0pCnBsb3QoeHNpbSwgbG1Nb2QkcmVzLCBjZXggPSB3LCBwY2ggPSAxOSwgY29sID0gInJlZCIpCnBvaW50cyh4c2ltLGxtTW9kJHJlcywgY2V4ID0gMS41KQpgYGAKCiMjIyMgUGVyZm9ybSBhIHdlaWdodGVkIHJlZ3Jlc3Npb24gdXNlIGxtIHdpdGggd2VpZ2h0cz13CgpgYGB7cn0KbG1Nb2QgPC0gbG0oeXNpbX54c2ltLCB3ZWlnaHRzID0gdykKYGBgCgojIyMjIFBsb3QgcmVzdWx0cwoKYGBge3J9CnBsb3QoeHNpbSwgeXNpbSkKYWJsaW5lKG9scywgbHdkID0gMikKYWJsaW5lKG1Fc3QsIGNvbCA9ICJyZWQiLCBsd2QgPSAyKQphYmxpbmUobG1Nb2QsIGNvbCA9ICJibHVlIiwgbHdkID0gMikKbGVnZW5kKCJ0b3BsZWZ0IiwKICBsZWdlbmQgPSBjKCJPTFMiLCJNLWVzdGltYXRpb24iLCJPdXIgSW1wbCIpLAogIGx3ZCA9IDIsCiAgY29sID0gYygiYmxhY2siLCAicmVkIiwgImJsdWUiKSkKYGBgCgojIyMjIFJlcGVhdCB0aGlzIG1hbnkgdGltZXMKYGBge3J9CmxtTW9kIDwtIG9scwpmb3IgKGsgaW4gMTozKQp7CiMjIyMjI3JlcGVhdCB0aGlzIHBhcnQgc2V2ZXJhbCB0aW1lcyB1bnRpbCBjb252ZXJnZW5jZQojdXNlIHJvYnVzdCB2YXJpYW5jZSBlc3RpbWF0b3IgdG8gY2FsY3VsYXRlIHRoZSB6CnJlcyA8LSBsbU1vZCRyZXMKc3RkZXYgPC0gbWFkKHJlcykKbWVkaWFuKGFicyhyZXMtbWVkaWFuKHJlcykpKSoxLjQ4MjYKCnogPC0gcmVzL3N0ZGV2CgojY2FsY3VsYXRlIHdlaWdodHMKI3VzZSBwc2kuaHViZXIgZnVuY3Rpb24KdyA8LSBwc2kuaHViZXIoeikKCiNwZXJmb3JtIGEgd2VpZ2h0ZWQgcmVncmVzc2lvbiB1c2UgbG0gd2l0aCB3ZWlnaHRzPXcKbG1Nb2QgPC0gbG0oeXNpbSB+IHhzaW0sIHdlaWdodHMgPSB3KQoKI3Bsb3QgcmVzdWx0cwpwbG90KHhzaW0seXNpbSkKYWJsaW5lKG9scywgbHdkID0gMikKYWJsaW5lKG1Fc3QsIGNvbCA9ICJyZWQiLCBsd2QgPSAyKQphYmxpbmUobG1Nb2QsIGNvbCA9ICJibHVlIiwgbHdkID0gMikKbGVnZW5kKCJ0b3BsZWZ0IiwKICBsZWdlbmQgPSBjKCJPTFMiLCJNLWVzdGltYXRpb24iLCJPdXIgSW1wbCIpLAogIGx3ZCA9IDIsCiAgY29sID0gYygiYmxhY2siLCAicmVkIiwgImJsdWUiKQogICkKIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCn0KYGBgCgojIEVtcGlyaWNhbCBCYXllcy9Nb2RlcmF0ZWQgJHQkLXRlc3QuCgogQSBnZW5lcmFsIGNsYXNzIG9mIG1vZGVyYXRlZCB0ZXN0IHN0YXRpc3RpY3MgaXMgZ2l2ZW4gYnkKCiBcW1x0aWxkZXtUfV9wID0gXGZyYWN7XG1hdGhiZntMfV9rIFxoYXR7IFxib2xkc3ltYm9se1xiZXRhX3B9fX17XG1hdGhiZntMfV9rXlQoXG1hdGhiZntYfV5UXG1hdGhiZntXWH0pXnstMX1cbWF0aGJme0x9X2teVCBcdGlsZGV7c31fcF4yfVxdCgogd2hlcmUgJFx0aWxkZXtzfV9wJCBpcyBhIG1vZGVyYXRlZCB2YXJpYW5jZSBlc3RpbWF0b3IuCgpTaW1wbGUgYXBwcm9hY2g6IHNldCAkXHRpbGRle3N9X3A9c19wICsgc18wJDogc2ltcGx5IGFkZCBhIHNtYWxsIHBvc2l0aXZlIGNvbnN0YW50IHRvIHRoZSBkZW5vbWluYXRvciBvZiB0aGUgdC1zdGF0aXN0aWMKClx0ZXh0YmZ7ZW1waXJpY2FsIEJheWVzfSB0aGVvcnkgcHJvdmlkZXMgZm9ybWFsIGZyYW1ld29yayBmb3IgYm9ycm93aW5nIHN0cmVuZ3RoIGFjcm9zcyBnZW5lcyBvciBwcm90ZWlucywKZS5nLiBwb3B1bGFyIGJpb2NvbmR1Y3RvciBwYWNrYWdlIFx0ZXh0YmZ7bGltbWF9ClxbXHRpbGRle3N9X2c9XHNxcnR7XGZyYWN7ZF9wc19wXjIrZF8wc18wXjJ9e2RfZytkXzB9fSxcXQphbmQgdGhlIG1vZGVyYXRlZCB0LXN0YXRpc3RpYyBpcyB0LWRpc3RyaWJ1dGVkIHdpdGggJGRfMCtkX2ckIGRlZ3JlZXMgb2YgZnJlZWRvbSB1bmRlciB0aGUgbnVsbCBoeXBvdGhlc2lzICRIXzA6IFxtYXRoYmZ7TH1cYm9sZHN5bWJvbHtcYmV0YX09MCQuCgotIE5vdGUsIHRoYXQgdGhlIGRlZ3JlZXMgb2YgZnJlZWRvbSBpbmNyZWFzZSBieSBib3Jyb3dpbmcgc3RyZW5ndGggYWNyb3NzIHByb3RlaW5zLgoKLS0tCgojIyBJbnRlcm1lenpvOiBCYXllc2lhbiBNZXRob2RzCgotIEZyZXF1ZW50aXN0cyBjb25zaWRlciBkYXRhIGFzIHJhbmRvbSBhbmQgcG9wdWxhdGlvbiBwYXJhbWV0ZXJzIGFzIGZpeGVkIGJ1dCB1bmtub3duCi0gSW4gQmF5ZXNpYW4gdmlld3BvaW50IGEgcGVyc29uIGhhcyBwcmlvciBiZWxpZWZzIGFib3V0IHRoZSBwb3B1bGF0aW9uIHBhcmFtZXRlcnMgYW5kIHRoZSB1bmNlcnRhaW50eSBvbiB0aGlzIHByaW9yIGJlbGllZnMgYXJlIHJlcHJlc2VudGVkIGJ5IGEgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIHBsYWNlZCBvbiB0aGlzIHBhcmFtZXRlci4KCiAgLSBUaGlzIGRpc3RyaWJ1dGlvbiByZWZsZWN0cyB0aGUgcGVyc29uJ3Mgc3ViamVjdGl2ZSBwcmlvciBvcGluaW9uIGFib3V0IHBsYXVzaWJsZSB2YWx1ZXMgb2YgdGhlIHBhcmFtZXRlci4KICAtIEFuZCBpcyByZWZlcnJlZCB0byBhcyB0aGUgcHJpb3IgJGcoXGJvbGRzeW1ib2x7XHRoZXRhfSkkLgoKLSBCYXllc2lhbiB0aGlua2luZyB3aWxsIHVwZGF0ZSB0aGUgcHJpb3IgaW5mb3JtYXRpb24gb24gdGhlIHBvcHVsYXRpb24gcGFyYW1ldGVycyBieSBjb25mcm9udGluZyB0aGUgbW9kZWwgdG8gZGF0YSAoJFxtYXRoYmZ7WX0kKS4KCi0gQnkgdXNpbmcgQmF5ZXMgVGhlb3JlbSB0aGlzIHJlc3VsdHMgaW4gYSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIG9uIHRoZSBtb2RlbCBwYXJhbWV0ZXJzLiAgClxbCmcoXGJvbGRzeW1ib2x7XHRoZXRhfVx2ZXJ0XG1hdGhiZntZfSk9XGZyYWN7ZihZXHZlcnQgXGJvbGRzeW1ib2x7XHRoZXRhfSlnKFxib2xkc3ltYm9se1x0aGV0YX0pfXtcaW50IGYoWVx2ZXJ0IFxib2xkc3ltYm9se1x0aGV0YX0pIGcoXGJvbGRzeW1ib2x7XHRoZXRhfSkgZFxib2xkc3ltYm9se1x0aGV0YX19IFx0ZXh0eyAgICAgfVxsZWZ0KFx0ZXh0eyBwb3N0ZXJpb3J9PVxmcmFje1x0ZXh0e3ByaW9yfSBcdGltZXMgXHRleHR7IGxpa2VsaWhvb2R9fXtcdGV4dHtNYXJnaW5hbCBkaXN0cmlidXRpb259fVxyaWdodCkKXF0KCi0tLQoKIyMgTGltbWEgIGFwcHJvYWNoCgpEZXZlbG9wZWQgZm9yIGdlbmUgZXhwcmVzc2lvbiBhbmFseXNpcyB3aXRoIG1pY3JvIGFycmF5cy4KTGV0IGcgYmUgdGhlIGluZGV4IGZvciBnZW5lIGcuClxbClxiZWdpbnthcnJheX17Y2N9CiZcYmV0YV97Z2t9XHZlcnQgXHNpZ21hXjJfZyxcYmV0YV97Z2t9XG5lcSAwIFxzaW0gTigwLHZfezBrfVxzaWdtYV9nXjIpXFxcXApcdGV4dHtQcmlvcn1cXAomXGZyYWN7MX17XHNpZ21hXjJfZ31cc2ltIHNeMl8wXGZyYWN7XGNoaV4yX3tkXzB9fXtkXzB9XFxcXFxcXFwKJlxoYXQgXGJldGFfe2drfSB8IFxiZXRhX3tna30gLCBcc2lnbWFfZ14yIFxzaW0gTiggXGJldGFfe2drfSAsIHZfe2drfVxzaWdtYV9nXjIpXFxcXApcdGV4dHtEYXRhfVxcCiZzX2deMlxzaW0gXHNpZ21hXjJfZ1xmcmFje1xjaGleMl97ZF9nfX17ZF9nfVxcXFwKXGVuZHthcnJheX0KXF0KCi0tLQoKIyMgTGltbWEgIGFwcHJvYWNoCgpVbmRlciB0aGlzIGFzc3VtcHRpb24sIGl0IGNhbiBiZSBzaG93biB0aGF0CgotIFBvc3RlcmlvciBNZWFuIGZvciB0aGUgdmFyaWFuY2UgcGFyYW1ldGVyOiBcW1x0aWxkZXtzfV4yX3AgPSBcdGV4dHtFfVxsZWZ0W1xzaWdtYV4yX3BcdmVydCBzX3BeMlxyaWdodF09XGZyYWN7ZF8wIHNfMF4yK2RfcHNfcF4yfXtkXzArZF9wfVxdCgotIFxbXHRpbGRle1R9X3A9XGZyYWN7XG1hdGhiZntMfV9rIFxoYXR7IFxib2xkc3ltYm9se1xiZXRhX3B9fX17XG1hdGhiZntMfV9rXlQoXG1hdGhiZntYfV5UXG1hdGhiZntXWH0pXnstMX1cbWF0aGJme0x9X2teVCBcdGlsZGV7c31fcF4yfVxdCgppcyB0LWRpc3RyaWJ1dGVkIHVuZGVyICRIXzA6IFxtYXRoYmZ7TH1falxib2xkc3ltYm9se1xiZXRhfSA9IDAkCgpcW1x0aWxkZXtUfV9wIFx2ZXJ0IEhfMCBcc2ltIHQoZF8wICsgZF9wKVxdCgotLS0KCiMjIEVtcGlyaWNhbCBCYXllcwotIEEgZnVsbHkgQmF5ZXNpYW4KICAtIHdvdWxkIGRlZmluZSB0aGUgcHJpb3IgZGlzdHJpYnV0aW9uIGJ5IGNhcmVmdWxseSBjaG9vc2luZyB0aGUgcHJpb3IgcGFyYW1ldGVycyBiYXNlZCBvbiBwcmlvciBrbm93bGVkZ2Ugb24gdGhlIHByb2Nlc3MKICAtIHdvdWxkIGNvbmZyb250IHRoZSBwcmlvciB0byB0aGUgZGF0YSBhbmQgcGVyZm9ybXMgaW5mZXJlbmNlIHVzaW5nIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIG9mIHRoZSBtb2RlbCBwYXJhbWV0ZXJzLgotIEluIGFuIGVtcGlyaWNhbCBCYXllc2lhbiBhcHByb2FjaCBvbmUgZXN0aW1hdGVzIHRoZSBwcmlvciBwYXJhbWV0ZXJzIGJhc2VkIG9uIHRoZSBkYXRhLgotIEluICoqTGltbWEqKiBtb21lbnQgZXN0aW1hdG9ycyBmb3IgJHNfMCQgYW5kICRkXzAkIGFyZSBkZXJpdmVkIHVzaW5nIHRoZSBpbmZvcm1hdGlvbiBvbiB0aGUgZ2VuZSAocHJvdGVpbikgd2lzZSB2YXJpYW5jZXMgb2YgYWxsIGdlbmVzIChwcm90ZWlucykuCi0gSW4gKipMaW1tYSoqIG9uZSBhbHNvIGRvZXMgbm90IHdvcmsgd2l0aCB0aGUgZnVsbCBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIGZvciB0aGUgdmFyaWFuY2VzLCBidXQgd2l0aCB0aGUgbWF4aW11bSBhLXBvc3RlcmlvciBlc3RpbWF0ZS4KCi0tLQoKIyMgSWxsdXN0cmF0aW9uCgpXZSBib3Jyb3cgc3RyZW5ndGggYWNyb3NzIHByb3RlaW5zIGJ5CgoxLiBwbGFjaW5nIGEgc2NhbGVkICRcY2hpXjIkIHByaW9yOiAkXGNoaV4yKHNfbyxkXzApJCBvbiB0aGUgcHJlY2lzaW9ucyAoJDEvXHNpZ21hXjJfcCQpCjIuIGVzdGltYXRpbmcgdGhlIHByaW9yIHBhcmFtZXRlcnMgJHNfMCQgYW5kICRkZl8wJAozLiByZXBsYWNpbmcgdGhlIGVzdGltYXRlZCBwcm90ZWluLXdpc2UgdmFyaWFuY2VzICgkc19wXjIkKSB3aXRoIHRoZSBtYXhpbXVtIGEtcG9zdGVyaW9yaSB2YXJpYW5jZQpcW1x0aWxkZXtzfV9wID0gXGZyYWN7ZF9wIHNeMl9wICsgZF8wIHNfMF4yfXtkX3ArZF8wfVxdCgoKYGBge3J9CnNkIDwtIHNhcHBseSgKICByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkbXNxcm9iTW9kZWxzLAogIGdldFNpZ21hKSAlPiUKICBuYS5leGNsdWRlCnNkUG9zdCA8LSBzYXBwbHkoCiAgcm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJG1zcXJvYk1vZGVscywKICBnZXRTaWdtYVBvc3RlcmlvcikgJT4lCiAgbmEuZXhjbHVkZQoKcDEgPC0gcXBsb3Qoc2Qsc2RQb3N0KSArCiAgZ2VvbV9hYmxpbmUoKQpwMQpgYGAKCiMjIyBIb3cgZG8gd2UgZ2V0IHRvIHRoZSBwb3N0ZXJpb3Igc3RhbmRhcmQgZGV2aWF0aW9uPwoKYGBge3J9CmhscCA8LSBsaW1tYTo6c3F1ZWV6ZVZhcigKICB2YXIgPSBzYXBwbHkocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJG1zcXJvYk1vZGVscywgZ2V0VmFyKSwKICBkZiA9IHNhcHBseShyb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkbXNxcm9iTW9kZWxzLCBnZXRERikKICApCmBgYAoKIyMjIyBEZWdyZWVzIG9mIGZyZWVkb20gb2YgcHJpb3IKCmBgYHtyfQpobHAkZGYucHJpb3IKCm1vZGVsIDwtIHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSRtc3Fyb2JNb2RlbHNbWzJdXQpnZXREZlBvc3Rlcmlvcihtb2RlbCkgLSBnZXRERihtb2RlbCkKYGBgCgojIyMjIHBvc3RlcmlvciB2YXJpYW5jZQoKJCRcdGlsZGUgc19wPVxzcXJ0e1xmcmFje2RfcFx0aW1lcyBzXjJfcCArIGRfMCBzXzBeMn17ZF9wK2RfMH19ICQkCgpgYGB7cn0KaGxwJHZhci5wcmlvcgoKdmFyUG9zdCA8LSAoZ2V0VmFyKG1vZGVsKSAqIGdldERGKG1vZGVsKSArIGhscCRkZi5wcmlvciAqIGhscCR2YXIucHJpb3IpLyhnZXRERihtb2RlbCkraGxwJGRmLnByaW9yKQpzcXJ0KHZhclBvc3QpCmdldFNpZ21hUG9zdGVyaW9yKG1vZGVsKQpgYGAKCkhlbmNlLCBzdGFuZGFyZCBkZXZpYXRpb25zIGFyZSBzaHJ1bmtlbiB0b3dhcmRzIHByaW9yIHN0YW5kYXJkIGRldmlhdGlvbiEKTGFyZ2Ugc3RhbmRhcmQgZGV2aWF0aW9ucyBiZWNvbWUgc21hbGxlciBhbmQgc21hbGxlciBzdGFuZGFyZCBkZXZpYXRpb25zIGJlY29tZSBsYXJnZXIhCgpgYGB7cn0KcDEgKwogIGdlb21faGxpbmUoeWludGVyY2VwdCA9IGhscCR2YXIucHJpb3JeLjUpCmBgYAoKCgojIyMgSWxsdXN0cmF0aW9uIHZpYSBTaW11bGF0aW9uCgpTdXBwb3NlIHRoYXQgdGhlIHN0YW5kYXJkIGRldmlhdGlvbnMgZm9yIGFsbCBwcm90ZWlucyBhcmUgdGhlIHNhbWUgYW5kIGFyZSBlcXVhbCB0byAxLgpXZSBzaW11bGF0ZSBwcm90ZWlucyB3aXRoIHRoZSBzYW1lIG1lYW4gYXMgdGhlIGZpdHRlZCBtZWFuIGluIHRoZSBleHBlcmltZW50IGJ1dCB3aXRoIHN0YW5kYXJkIGRldmlhdGlvbiBvZiAxLgoKYGBge3Igd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KbkNvZWZzIDwtIGdldENvZWYocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJG1zcXJvYk1vZGVsc1tbMl1dKSAlPiUgbGVuZ3RoCmNvZWZzIDwtCnNhcHBseShyb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkbXNxcm9iTW9kZWxzLAogICAgZnVuY3Rpb24oeCkgZ2V0Q29lZih4KVsxOm5Db2Vmc10KICApICU+JQogIHQgJT4lCiAgbmEuZXhjbHVkZQoKCnAgPC0gbnJvdyhjb2VmcykKbiA8LSBuY29sKHBlW1sxXV0pCmYwX2VxdWFsVmFyIDwtIHNhcHBseSgxOnAsCiAgRlVOPWZ1bmN0aW9uKGksIG4sIGJldGFzLCBzZCwgZGVzaWduKSB7CiAgcm5vcm0obiwgbWVhbiA9IGRlc2lnbiAlKiUgYmV0YXNbaSxdLCBzZCA9IHNkKX0sCiAgbiA9IG4sCiAgYmV0YXMgPSBjb2VmcywKICBzZCA9IDEsCiAgZGVzaWduID0gWAogICkgJT4lCiAgdApjb2xuYW1lcyhmMF9lcXVhbFZhcikgPC0gY29sbmFtZXMocGVbWzFdXSkKc2ltcyA8LSByZWFkUUZlYXR1cmVzKGYwX2VxdWFsVmFyICU+JSBhcy5kYXRhLmZyYW1lLCBlY29sID0gMTpuLCBuYW1lID0gInNpbV9lcXVhbFZhciIpCmNvbERhdGEoc2ltcykgPC0gY29sRGF0YShwZSkKc2ltcyA8LSBtc3Fyb2Iob2JqZWN0ID0gc2ltcywgaSA9ICJzaW1fZXF1YWxWYXIiLCBmb3JtdWxhID0gfiBsb2NhdGlvbip0aXNzdWUgKyBwYXRpZW50KQoKc2QwIDwtIHNhcHBseSgKICByb3dEYXRhKHNpbXNbWyJzaW1fZXF1YWxWYXIiXV0pJG1zcXJvYk1vZGVscywKICBnZXRTaWdtYSkgJT4lCiAgbmEuZXhjbHVkZQpzZFBvc3QwIDwtIHNhcHBseSgKICByb3dEYXRhKHNpbXNbWyJzaW1fZXF1YWxWYXIiXV0pJG1zcXJvYk1vZGVscywKICBnZXRTaWdtYVBvc3RlcmlvcikgJT4lCiAgbmEuZXhjbHVkZQoKcXBsb3Qoc2QwLHNkUG9zdDApICsKICBnZW9tX2FibGluZSgpICsKICB5bGltKHJhbmdlKHNkMCkpCmBgYAoKLSBXZSBvYnNlcnZlIGEgbGFyZ2UgdmFyaWFiaWxpdHkgaW4gdGhlIGluZGl2aWR1YWwgcHJvdGVpbiBsZXZlbCBzdGFuZGFyZCBkZXZpYXRpb24gZXN0aW1hdGVzLgotIFdlIHNpbXVsYXRlZCBwcm90ZWlucyB3aXRoIHN0YW5kYXJkIGRldmlhdGlvbiBvZiAxLCBidXQgdGhlIHByb3RlaW4gZXN0aW1hdGVzIHZhcnkgZnJvbSBgciBwYXN0ZShyb3VuZChyYW5nZShzZDApLDIpLGNvbGxhcHNlPSIsIC4uLiAsICIpYC4KLSBMYXJnZSB1bmNlcnRhaW50eSBvbiB0aGUgZXN0aW1hdGlvbiBvZiB2YXJpYW5jZXMgaW4gc21hbGwgc2FtcGxlcwotIFRoZSBlbXBpcmljYWwgQmF5ZXMgbWV0aG9kLCBob3dldmVyLCByZWNvZ25pc2VzIHRoYXQgYWxsIHByb3RlaW5zIGFyZSBzaW11bGF0ZWQgd2l0aCB0aGUgc2FtZSB2YXJpYW5jZS4KLSBIZW5jZSwgaXQgY2FuIGJvcnJvdyB0cmVtZW5kb3VzIHN0cmVuZ3RoIGFjcm9zcyBwcm90ZWlucyB0byBzdGFiaWxpemUgdGhlIHZhcmlhbmNlIGVzdGltYXRpb24KLSBIZXJlLCBpdCBzaHJpbmtzIGFsbCBwcm90ZWluIHZhcmlhbmNlIHRvIHRoZSBwcmlvciB2YXJpYW5jZSwgd2hpY2ggaXMgaW5kZWVkIHZlcnkgY2xvc2UgdG8gMSwgdGhlIHZhbHVlIHdlIGhhdmUgYWRvcHRlZCBpbiB0aGUgc2ltdWxhdGlvbi4KCk5vdGUsIHRoYXQgdGhlIHByaW9yIGRlZ3JlZXMgb2YgZnJlZWRvbSBhcmUgYWxzbyBzZXQgdG8gaW5maW5pdHk6CmBgYHtyfQpnZXRERihyb3dEYXRhKHNpbXNbWyJzaW1fZXF1YWxWYXIiXV0pJG1zcXJvYk1vZGVsc1tbMV1dKQpnZXREZlBvc3Rlcmlvcihyb3dEYXRhKHNpbXNbWyJzaW1fZXF1YWxWYXIiXV0pJG1zcXJvYk1vZGVsc1tbMV1dKQpgYGAKCndoaWNoIGltcG9zZXMgc2hyaW5rYWdlIHRvIHRoZSBwcmlvciBzdGFuZGFyZCBkZXZpYXRpb24hCgpUaGUgZW1waXJpY2FsIEJheWVzIG1ldGhvZCBjYW4gdGh1cyBpbmRlZWQgcmVjb2duaXplIHRoZSBjb21tb24gdmFyaWFuY2UgdGhhdCBpcyBzaGFyZWQgYWNyb3NzIGFsbCBzaW11bGF0ZWQgcHJvdGVpbnMhCgojIFAtdmFsdWVzCgojIyBTaW11bGF0aW9uIHVuZGVyIEhfMC4KCi0gTWVhbiBsb2cyIHByb3RlaW4gaW50ZW5zaXR5IGZvciBhdHJpdW0gZXF1YWxzIG1lYW4gbG9nMiBwcm90ZWluIGludGVuc2l0eSBmb3IgdmVudHJpY3VsdW0gaW4gdGhlIGxlZnQgaGVhcnQgcmVnaW9uLgotIHNkIGVxdWFscyB0aGUgc2QgZm9yIHRoZSBwcm90ZWluLgoKCjEuIEV4dHJhY3QgJFxoYXQgXHNpZ21hJCBhbmQgJFxiZXRhJCdzICAKYGBge3J9CnNkIDwtIHNhcHBseSgKICByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkbXNxcm9iTW9kZWxzLAogIGdldFNpZ21hKSAlPiUKICBuYS5leGNsdWRlCgpjb2VmcyA8LQpzYXBwbHkocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJG1zcXJvYk1vZGVscywKICAgIGZ1bmN0aW9uKHgpIGdldENvZWYoeClbMTpuQ29lZnNdCiAgKSAlPiUKICB0ICU+JQogIG5hLmV4Y2x1ZGUKYGBgCgoyLiBTZXQgJFxiZXRhX1x0ZXh0e3Rpc3N1ZX0kIGVxdWFsIHRvIDAuIE5vIEZDIGJldHdlZW4gYXRyaXVtIGFuZCB2ZW50cmljdWx1bSBsZWZ0LgoKYGBge3J9CmNvZWZzMCA8LSBjb2Vmcwpjb2VmczBbLDNdIDwtIDAKYGBgCgozLiBTaW11bGF0ZSBwcm90ZWluIGV4cHJlc3Npb25zIGZvciBlYWNoIHByb3RlaW4gZnJvbSBhIE5vcm1hbCBkaXN0cmlidXRpb24gdW5kZXIgJEhfMCQgZm9yIGxlZnQgaGVhcnQgcmVnaW9uIChubyBGQyBiZXR3ZWVuIGF0cml1bSBhbmQgdmVudHJpY3VsdW0gbGVmdCkgYW5kIHNkIHRoZSBzZCBmb3IgdGhlIHByb3RlaW4uCmBgYHtyfQpzZXQuc2VlZCgxMDQpCmYwIDwtIHNhcHBseSgxOnAsCiAgZnVuY3Rpb24oaSwgYmV0YXMsIHNkLCBkZXNpZ24pCiAgcm5vcm0obiwgbWVhbiA9IGRlc2lnbiAlKiUgYmV0YXNbaSxdLCBzZCA9IHNkW2ldKSwKICBiZXRhcyA9IGNvZWZzMCwKICBzZCA9IHNkLAogIGRlc2lnbiA9IFgKICApICU+JQogIHQKY29sbmFtZXMoZjApIDwtIGNvbG5hbWVzKHBlW1sxXV0pCmBgYAoKNC4gU2V0dXAgUUZlYXR1cmVzIG9iamVjdCBhbmQgcGVyZm9ybSBNU3FSb2IgYW5hbHlzaXMKCmBgYHtyIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpzaW1zIDwtIHJlYWRRRmVhdHVyZXMoZjAgJT4lIGFzLmRhdGEuZnJhbWUsIGVjb2wgPSAxOm4sIG5hbWUgPSAic2ltMCIpCmNvbERhdGEoc2ltcykgPC0gY29sRGF0YShwZSkKc2ltcyA8LSBtc3Fyb2Iob2JqZWN0ID0gc2ltcywgaSA9ICJzaW0wIiwgZm9ybXVsYSA9IH4gbG9jYXRpb24qdGlzc3VlICsgcGF0aWVudCkKc2ltcyA8LSBoeXBvdGhlc2lzVGVzdChvYmplY3QgPSBzaW1zLCBpID0gInNpbTAiLCBjb250cmFzdCA9IEwpCmBgYAoKIyMjIEV2YWx1YXRlICBwdmFsdWVzICB1bmRlciBIXzAKCmBgYHtyfQp2b2xjYW5vIDwtIGdncGxvdChyb3dEYXRhKHNpbXNbWyJzaW0wIl1dKSR0aXNzdWVWLAogICAgICAgICAgICAgICAgIGFlcyh4ID0gbG9nRkMsIHkgPSAtbG9nMTAocHZhbCksIGNvbG9yID0gcHZhbCA8IDAuMDUpKSArCiBnZW9tX3BvaW50KGNleCA9IDIuNSkgKwogc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGFscGhhKGMoImJsYWNrIiwgInJlZCIpLCAwLjUpKSArIHRoZW1lX21pbmltYWwoKQp2b2xjYW5vCmBgYAoKTnVtYmVyIG9mIGZhbHNlIHBvc2l0aXZlcyB3aXRob3V0IG11bHRpcGxlIHRlc3Rpbmc/CgpgYGB7cn0Kcm93RGF0YShzaW1zW1sic2ltMCJdXSkkdGlzc3VlViAlPiUKICBmaWx0ZXIocHZhbCA8MC4wNSkgJT4lCiAgbnJvdwptZWFuKHJvd0RhdGEoc2ltc1tbInNpbTAiXV0pJHRpc3N1ZVYkcHZhbCA8IDAuMDUpICAgIApoaXN0KHJvd0RhdGEoc2ltc1tbInNpbTAiXV0pJHRpc3N1ZVYkcHZhbCxtYWluID0gInNpbXVsYXRpb24gSDAiKQpgYGAKCgotIFRoZSBwLXZhbHVlcyBhcmUgdW5pZm9ybSEKLSBBbGwgcC12YWx1ZXMgdW5kZXIgdGhlIG51bGwgYXJlIGVxdWFsbHkgbGlrZWx5LgotIFN0YXRpc3RpY2FsIGh5cHRoZXNpcyB0ZXN0aW5nIGxlYWRzIHRvIGEgdW5pZm9ybSB0ZXN0IHN0cmF0ZWd5IHVuZGVyICRIXzAkCi0gSWYgdXNlIHAtdmFsdWUgY3V0b2ZmIGF0IDAuMDUgd2UgZXhwZWN0IHRvIHJldHVybiA1JSBvZiB0aGUgbm9uLURFIHByb3RlaW5zICBhcyBkaWZmZXJlbnRpYWxseSBleHByZXNzZWQ6IG1hbnkgZmFsc2UgcG9zaXRpdmVzIGNhbiBiZSBleHBlY3RlZCEKCgojIyBQdmFsdWUgZGlzdHJpYnV0aW9uIGluIHJlYWwgZXhwZXJpbWVudAoKYGBge3J9Cmhpc3Qocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJHRpc3N1ZVYkcHZhbCwgbWFpbiA9ICJyZWFsRGF0YSIpCmBgYAoKLSBBIG1peHR1cmUgb2YgbnVsbCBwcm90ZWlucyAobm9uLURFKTogdW5pZm9ybSwgYW5kLCBERSBwcm90ZWluczogZW5yaWNobWVudCBvZiBwLXZhbHVlcyBhdCBsb3cgcC12YWx1ZXMKCgojIENvcnJlY3Rpb24gZm9yIG11bHRpcGxlIHRlc3RpbmcKCi0gV2UgY2FuIGFkanVzdCB0aGUgcC12YWx1ZXMgZm9yIG11bHRpcGxlIHRlc3RpbmcuCgojIyBGYW1pbHkgd2lzZSBlcnJvciByYXRlIGNvcnJlY3Rpb246CgotIEEgbGlzdCBvZiByZXR1cm5lZCBwcm90ZWlucyBpcyBjb25zaWRlcmVkIHRvIGJlIGluIGVycm9yIGFzIHNvb24gYXMgaXQgY29udGFpbnMgYXQgbW9zdCBvbmUgZmFsc2UgcG9zaXRpdmUgcHJvdGVpbi4KCi0gJFx0ZXh0e0ZXRVJ9ID0gUChGUCBcbGVxIDEpJAoKLSBGV0VSOiBwcm9iYWJpbGl0eSBvZiBtYWtpbmcgYXQgbGVhc3Qgb25lIGZhbHNlIHBvc2l0aXZlIGRlY2lzaW9uIG9yCnByb2JhYmlsaXR5IHRvIGRlY2xhcmUgYXQgbGVhc3Qgb25lIHByb3RlaW4gZGlmZmVyZW50aWFsbHkgYWJ1bmRhbnQgd2hpY2ggaXMgdHJ1bHkgbm9uIGRpZmZlcmVudGlhbGx5IGFidW5kYW50CgojIyMgQm9uZmVycm9uaSBtZXRob2QKCi0gU2ltcGxlIG1ldGhvZAotICRtJCB0ZXN0cyBhcmUgcGVyZm9ybWVkIGF0IHRoZSBsZXZlbCAkXGFscGhhL20kCi0gRldFUiRcbGVxXHN1bVxsaW1pdHNfe3A9MX1ee219UChyZWplY3QgSF97MHB9XHZlcnQgSF97MHB9XHRleHR7IGlzIHRydWV9KT1tIFxhbHBoYS9tPVxhbHBoYSQKLSBQcm92aWRlcyBzdHJvbmcgY29udHJvbAotIEJvbmZlcnJvbmkgaXMgdmVyeSBjb25zZXJ2YXRpdmUKLSBXb3JrcyBmb3IgZGVwZW5kZW50IHRlc3RzCi0gQWRqdXN0ZWQgcC12YWx1ZTogJFx0aWxkZXtwfV9wPVxtaW4obVwgcF9wLDEpJAoKLS0tCgojIyMgQm9uZmVycm9uaSBpbiBwcmFjdGlzZQoKVmlhIFIgZnVuY3Rpb25zCgpgYGB7cn0KcGFkaiA8LSBwLmFkanVzdCgKICByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkdGlzc3VlViRwdmFsLAogIG1ldGhvZCA9ICJib25mZXJyb25pIikKYGBgCgpPd24gSW1wbGVtZW50YXRpb246IGFkanVzdCBhbmQgbWFrZSBzdXJlIHRoYXQgcC12YWx1ZSBpcyBzbWFsbGVyIHRoYW4gMS4KCmBgYHtyfQptIDwtIHN1bSghaXMubmEocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJHRpc3N1ZVYkcHZhbCkpCnBhZGpTZWxmIDwtICByb3dEYXRhKHBlW1sicHJvdGVpblJvYnVzdCJdXSkkdGlzc3VlViRwdmFsICogbQpwYWRqU2VsZltwYWRqU2VsZiA+IDFdIDwtIDEKCnJhbmdlKHBhZGogLSBwYWRqU2VsZiwgbmEucm0gPSBUUlVFKQpgYGAKIyMjIElsbHVzdHJhdGlvbiBpbiBzaW11bGF0aW9uIHVuZGVyICRIXzAkIGFuZCBoZWFydCBjYXNlIHN0dWR5CgpgYGB7cn0Kdm9sY2FubyA8LSBnZ3Bsb3Qocm93RGF0YShzaW1zW1sic2ltMCJdXSkkdGlzc3VlViwKICAgICAgICAgICAgICAgICBhZXMoeCA9IGxvZ0ZDLCB5ID0gLWxvZzEwKHB2YWwpLCBjb2xvciA9IHAuYWRqdXN0KHB2YWwsImJvbmZlcnJvbmkiKSA8IDAuMDUpKSArCiBnZW9tX3BvaW50KGNleCA9IDIuNSkgKwogc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGFscGhhKGMoImJsYWNrIiwgInJlZCIpLCAwLjUpKSArCiB0aGVtZV9taW5pbWFsKCkgKwogZ2d0aXRsZSgic2ltdWxhdGVkIGhlYXJ0IGRhdGEgdW5kZXIgSDAiKQp2b2xjYW5vCmBgYAoKLSBObyBmYWxzZSBwb3NpdGl2ZXMgYXJlIHJldHVybmVkIGZvciBzaW11bGF0aW9uIHVuZGVyIEhfMC4gTGlzdCBpcyBjb3JyZWN0IGFjY29yZGluZyB0byBGV0VSLgoKYGBge3J9CnZvbGNhbm8gPC0gZ2dwbG90KHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSR0aXNzdWVWLAogICAgICAgICAgICAgICAgIGFlcyh4ID0gbG9nRkMsIHkgPSAtbG9nMTAocHZhbCksIGNvbG9yID0gcC5hZGp1c3QocHZhbCwiYm9uZmVycm9uaSIpIDwgMC4wNSkpICsKIGdlb21fcG9pbnQoY2V4ID0gMi41KSArCiBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gYWxwaGEoYygiYmxhY2siLCAicmVkIiksIDAuNSkpICsKIHRoZW1lX21pbmltYWwoKSArCiBnZ3RpdGxlKCJyZWFsIGhlYXJ0IGRhdGEiKQp2b2xjYW5vCmBgYAoKLSBWZXJ5IGZldyBwcm90ZWlucyBhcmUgcmV0dXJuZWQgZm9yIHJlYWwgZGF0YS4gVmVyeSBjb25zZXJ2YXRpdmUhCgojIyBGYWxzZSBkaXNjb3ZlcnkgcmF0ZQoKLSBBZGp1c3RlZCBQLXZhbHVlcyB3aXRoIHRoZSBCZW5qYW1pbmkgSG9jaGJlcmcgY29ycmVjdGlvbiBjb3JyZXNwb25kIHRvIHRoZSBlc3RpbWF0ZWQgRkRSIG9mIHRoZSBzZXQgdGhhdCBpcyByZXR1cm5lZCB3aGVuIHRoZSBzaWduaWZpY2FuY2UgbGV2ZWwgaXMgc2V0IGF0IHRoaXMgdGhyZXNob2xkLgpcYmVnaW57ZXFuYXJyYXl9CkZEUihwXzApICY9JiBcdGV4dHtFfVxsZWZ0W1xmcmFje0ZQfXsoRlAgKyBUUCl9XHJpZ2h0XVxcCiZcYXBwcm94JlxmcmFje3BfMCBcdGltZXMgbX17XCNwX3AgXGxlcSBwXzB9XFwKXGVuZHtlcW5hcnJheX0KClNvIGFkanVzdGVkIHAtdmFsdWUgZm9yIHByb3RlaW4gaiBlcXVhbHMKXFtcdGlsZGUgcF9qID0gXGZyYWN7cF97MCxqfSBcdGltZXMgbX17XCNwX3AgXGxlcSBwX3swLGp9fVxdCgpIb3dldmVyLCB0aGUgRkRSIGFsd2F5cyBoYXMgdG8gYmUgYmV0d2VlbiAwIGFuZCAxIHNvOgoKXFtcdGlsZGUgcF9qID0gXG1pblxsZWZ0W1xmcmFje3BfezAsan0gXHRpbWVzIG19e1wjcF9wIFxsZXEgcF97MCxqfX0sMVxyaWdodF1cXQoKYW5kIHRoZSBhZGp1c3RlZCBwLXZhbHVlcyBzaG91bGQgcmVtYWluIGluIHRoZSBzYW1lIG9yZGVyIGFzIHRoZSBvcmlnaW5hbCBwLXZhbHVlcy4KClxbXHRpbGRlIHBfaiA9ICBcbWluXGxpbWl0c197XGZvcmFsbCBrOiBwX2sgPiBwX2p9IFxtaW5cbGVmdFtcZnJhY3twX3swLGt9IFx0aW1lcyBtfXtcI3BfcCBcbGVxIHBfezAsa319LDFccmlnaHRdXF0KCjEuIE9yZGVyIHB2YWx1ZXMKYGBge3J9CnB2YWxzIDwtIHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSR0aXNzdWVWJHB2YWwKbmFJbmQgPC0gaXMubmEocHZhbHMpCnBIbHAgPC0gcHZhbHNbIW5hSW5kXQpvcmQgPC0gcEhscCAlPiUgb3JkZXIKcEhscCA8LSBwSGxwW29yZF0KYGBgCgoyLiBBZGp1c3Qgb3JkZXJlZCBwLXZhbHVlcwpgYGB7cn0KcEhscCA8LSBwSGxwKmxlbmd0aChwSGxwKS8oMTpsZW5ndGgocEhscCkpCmBgYAoKMy4gRW5zdXJlIGFkanVzdCBwLXZhbHVlcyBhcmUgc21hbGxlciBhcmUgZXF1YWwgdGhhbiAxCmBgYHtyfQpwSGxwW3BIbHA+MV0gPC0gMQpgYGAKCjQuIE1vbm90b25pY2l0eSBjb25zdHJhaW50CmBgYHtyfQpwbWluIDwtIHBIbHBbbGVuZ3RoKHBIbHApXQpmb3IgKGogaW4gKGxlbmd0aChwSGxwKS0xKToxKQp7CiAgaWYgKHBIbHBbal0gPCBwbWluKQogICAgcG1pbiA8LSBwSGxwW2pdIGVsc2UKICAgIHBIbHBbal0gPC0gcG1pbiAgIAp9CmBgYAoKNS4gUHV0IHAtdmFsdWVzIGJhY2sgaW4gb3JpZ2luYWwgb3JkZXIKCmBgYHtyfQpwSGxwW29yZF0gPC0gcEhscApwQWRqIDwtIHB2YWxzCnBBZGpbIW5hSW5kXSA8LSBwSGxwCgpoZWFkKHBBZGopCmhlYWQocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJHRpc3N1ZVYpCnJhbmdlKHJvd0RhdGEocGVbWyJwcm90ZWluUm9idXN0Il1dKSR0aXNzdWVWJGFkalB2YWwgLSBwQWRqLG5hLnJtPVRSVUUpCmBgYAoKIyMjIElsbHVzdHJhdGlvbiBpbiBzaW11bGF0aW9uIHVuZGVyICRIXzAkIGFuZCBoZWFydCBjYXNlIHN0dWR5CgpgYGB7cn0Kdm9sY2FubyA8LSBnZ3Bsb3Qocm93RGF0YShzaW1zW1sic2ltMCJdXSkkdGlzc3VlViwKICAgICAgICAgICAgICAgICBhZXMoeCA9IGxvZ0ZDLCB5ID0gLWxvZzEwKHB2YWwpLCBjb2xvciA9IGFkalB2YWwgPCAwLjA1KSkgKwogZ2VvbV9wb2ludChjZXggPSAyLjUpICsKIHNjYWxlX2NvbG9yX21hbnVhbCh2YWx1ZXMgPSBhbHBoYShjKCJibGFjayIsICJyZWQiKSwgMC41KSkgKwogdGhlbWVfbWluaW1hbCgpICsKIGdndGl0bGUoInNpbXVsYXRlZCBoZWFydCBkYXRhIHVuZGVyIEgwIikKdm9sY2FubwpgYGAKCi0gTm8gZmFsc2UgcG9zaXRpdmVzIGFyZSByZXR1cm5lZCBmb3Igc2ltdWxhdGlvbiB1bmRlciBIXzAuIExpc3QgaXMgY29ycmVjdCBhY2NvcmRpbmcgdG8gRldFUi4KLSBJdCBjYW4gYmUgc2hvd24gdGhhdCB0aGUgRkRSLW1ldGhvZCBjb250cm9scyB0aGUgRldFUiB3aGVuICRIXzAkIGlzIHRydWUgZm9yIGFsbCBmZWF0dXJlcy4gICAKCgpgYGB7cn0Kdm9sY2FubyA8LSBnZ3Bsb3Qocm93RGF0YShwZVtbInByb3RlaW5Sb2J1c3QiXV0pJHRpc3N1ZVYsCiAgICAgICAgICAgICAgICAgYWVzKHggPSBsb2dGQywgeSA9IC1sb2cxMChwdmFsKSwgY29sb3IgPSBhZGpQdmFsIDwgMC4wNSkpICsKIGdlb21fcG9pbnQoY2V4ID0gMi41KSArCiBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gYWxwaGEoYygiYmxhY2siLCAicmVkIiksIDAuNSkpICsKIHRoZW1lX21pbmltYWwoKSArCiBnZ3RpdGxlKCJyZWFsIGhlYXJ0IGRhdGEiKQp2b2xjYW5vCmBgYAoKVGhlIEZEUiBtZXRob2QgYWxsb3dzIHVzIHRvIHJldHVybiBtdWNoIGxvbmdlciBEQSBwcm90ZWluIGxpc3RzIGF0IHRoZSBleHBlbnNlIG9mIGEgZmV3IGZhbHNlIHBvc2l0aXZlcy4KVGhlIEZEUiBjb250cm9scyB0aGUgZnJhY3Rpb24gb2YgZmFsc2UgcG9zaXRpdmVzIGluIHRoZSBsaXN0IHRoYXQgeW91IHJldHVybiBvbiBhdmVyYWdlIG9uIHRoZSBzaWduaWZpY2FuY2UgbGV2ZWwgdGhhdCBpcyBhZG9wdGVkLgpTbyBpZiB5b3UgdXNlICRcYWxwaGE9MC4wNSQgd2UgZXhwZWN0IG9uIGF2ZXJhZ2UgNSUgb2YgZmFsc2UgcG9zaXRpdmVzIGluIHRoZSBsaXN0IHRoYXQgd2UgcmV0dXJuLgo=