First, we need the following packages:
Required packages
# Load in libraries
library(tidyverse)
library(RColorBrewer)
library(MetBrewer)
library(plotly)
library(reshape2)
While we don’t actually need the raw data, it might be nice to have
it and check. So, here it is entered manually.
Data
Scores from two tests taken by 22 students, mechanics
and vectors
.
student <- 1:22
m <- mechanics <- c(7, 44, 49, 59, 34, 46, 0, 32, 49, 52, 44, 36, 42, 5, 22, 18, 41, 48, 31, 42, 46, 63)
v <- vectors <- c(51, 69, 41, 70, 42, 40, 40, 45, 57, 64, 61, 59, 60, 30, 58, 51, 63, 38, 42, 69, 49, 63)
# Combine into a data frame
(data <- data.frame(Student = student, Mechanics = mechanics, Vectors = vectors))
# correlation coefficient
(cor_mv <- cor(mechanics, vectors))
## [1] 0.4978075
Plotting the data and fitting both linear (red) and lowess (blue)
regression lines.
p1 <- ggplot(data, aes(x=Mechanics, y=Vectors))+geom_point(size=3)+
geom_smooth(method = "lm", colour="red", size=2, se=FALSE)+
geom_smooth(method = "loess", colour="blue", size=2, se=FALSE, span=0.85)+
theme_minimal()
ggplotly(p1)
We can take Equation 3.10,\[\hat{\theta} =
\frac{\sum_{i=1}^{22} (m_i - \bar{m})(v_i -
\bar{v})}{\left[\sum_{i=1}^{22} (m_i - \bar{m})^2 \sum_{i=1}^{22} (v_i -
\bar{v})^2\right]^{1/2}}\], and make it into an R function. The
stats::cor()
, of course, is sufficient, but just for
fun…
Defining the Sample Correlation Function
# Define function
samp_cor <- function(m, v) {
# Compute the means of m and v
m_mean <- mean(m)
v_mean <- mean(v)
# Compute the numerator and denominator for the Pearson correlation formula
numerator <- sum((m - m_mean) * (v - v_mean))
denominator <- sqrt(sum((m - m_mean)^2) * sum((v - v_mean)^2))
# Compute the sample correlation coefficient (theta_hat)
numerator / denominator
}
# trying to see that it works
samp_cor(mechanics, vectors)
## [1] 0.4978075
all.equal(cor(mechanics, vectors), samp_cor(mechanics, vectors)) # Alright...
## [1] TRUE
Example 2 is great, but it skips over the stuff happening “under the
hood.” Because it’s not high-dimensional (so no need for fancy MCMC),
why don’t we try to do reproduce the example and results with a (mostly)
“home-baked” code.
While the next part is not really Bayesian, it still might be fun to
try to do it “by hand.”
Likelihood Function (and MLE “by hand”)
Efron and Hastie (Brad and Trev) chose a \(\sigma^2=1\) for the unidimensional normal
density function in Eq 3.2 (p. 22), but I will use a smaller value,
\(\sigma=.1\) (so that the graph later
on would look nicer).
The following likelihood function does not actually need the data,
only the estimate, \(\hat{\theta}\), so
it doesn’t include the iterative multiplication for each observation and
the constant, just the exponential piece. Here it is:
\[\exp\left(- \frac{(\hat{\theta} -
\theta)^2}{2\sigma^2}\right)\]
And, as a function in R:
# Likelihood function for MLE with variance you can modify,
likelihood <- function(theta, m, v, sigma = 0.01) {
# Compute sample correlation coefficient using samp_cor
theta_hat <- samp_cor(m, v)
# Likelihood function complete
likelihood <- exp(- (theta_hat - theta)^2 / (2 * sigma^2))
return(likelihood)
}
Before we try it out or continue, we should make some possible
parameter values that theta can take, from -1 to 1:
\[\theta \in [-1, 1]\]
# possible values theta can take, from
theta <- seq(-1,1, length.out=1000)
OK, if we want to find the maximum-likelihood estimate (MLE), as in
Figure 3.2 (p. 27), better to take the log of the function so that we
don’t deal with very, very small values. Because the likelihood function
was an \(e^{term}\), the log of it is
then just the \(term\). That is, \[- \frac{(\hat{\theta} -
\theta)^2}{2\sigma^2}\]
# Log-likelihood function for MLE
LL <- function(theta, m, v, sigma=0.01) {
# Compute sample correlation coefficient using the samp_cor function
theta_hat <- samp_cor(m, v)
# Log-likelihood function: log of the likelihood.
log_likelihood <- -(theta_hat - theta)^2 / (2 * sigma^2)
return(log_likelihood)
}
We can find the parameter value that produces the highest
(log-)likelihood by optimization. I’m sure it can be done with DYI code,
but I will just use the optimize
function, if ya’ll don’t
mind.
# find MLE with optimizations...
optimize(LL, interval = c(-1, 1), m = m, v = v, sigma = 0.01, maximum = TRUE) # Same as cor, surprise surprise ;)
## $maximum
## [1] 0.4978075
##
## $objective
## [1] 0
optimize(likelihood, interval = c(-1, 1), m = m, v = v, sigma = 0.01, maximum = TRUE)
## $maximum
## [1] 0.4978122
##
## $objective
## [1] 0.9999999
We can also plot this. Note, however, that this is not the same as in
Figure 3.2 where it is the posterior from a flat prior. Here, we plot
the log-likelihood function and the MLE location.
#Calculate log-likelihood for each theta
LL_values <- sapply(theta, function(theta) LL(theta, m, v))
# Find the MLE using the log-likelihood function
mle_res <- optimize(LL, interval = c(-1, 1), m = m, v = v, sigma = 0.1, maximum = TRUE)
(mle_theta <- mle_res$maximum) # estimate of theta
## [1] 0.4978075
# Prepare data for plotting
plot_data <- data.frame(
theta = theta,
log_likelihood = LL_values
)
# Plot log-likelihood using ggplot
mle_plot <- ggplot(plot_data, aes(x = theta)) +
geom_line(aes(y = log_likelihood), color = "red", size = 2) +
geom_vline(xintercept = mle_theta, color = "black", linetype = "dotted", size = 1.2) +
labs(title = "Log-Likelihood function and MLE",
x = "theta",
y = "Value") +
theme_minimal() +
theme(
plot.title = element_text(hjust = 0.5),
legend.position = "none"
)+annotate("text", x = mle_theta-0.2, y = -11000, label = paste("MLE =", round(mle_theta, 3)),
hjust = -.95, vjust = 10, color = "black", size = 5) # Adding MLE annotation
ggplotly(mle_plot)
We can go back to Example 2. Specifically, to Equation 3.11
Correlation Coefficient Density
Assuming that the joint \((m, v)\)
distribution is bivariate normal – p. 26.
Side note, here’s a details of the note in p. 26:
“Formula (3.11) for the correlation coefficient density was R. A.
Fisher’s debut contribution to the statistics literature.”
\[
f_{\theta}(\hat{\theta}) = \frac{(n - 2)(1 - \theta^2)^{(n - 1)/2}
\left(1 - \hat{\theta}^2\right)^{(n - 4)/2}}{\pi} \int_0^{\infty}
\frac{dw}{\left(\cosh(w) - \theta \hat{\theta}\right)^{n-1}}
\]
Let’s define this as a function in R. But, I’ll try to break it down
into smaller pieces, because it’s a lot…
We start with the right-hand-side of the density function, the
integrand, the hyperbolic cosine that should be integrated.
The integrand uses hyperbolic cosine, and theta, the parameter of
interest:
\[
\int_0^{\infty} \frac{dw}{\left(\cosh(w) - \theta
\hat{\theta}\right)^{n-1}}
\]
In R:
integrand <- function(w, theta, theta_hat, n) {
return(1 / (cosh(w) - theta * theta_hat)^(n - 1))
}
Next, the numerator of the left-hand-side of the density function
(the pre-calculus part…):
\[
(n - 2)(1 - \theta^2)^{(n - 1)/2} \left(1 - \hat{\theta}^2\right)^{(n -
4)/2}
\]
non_calc_part <- function(theta, theta_hat, n) {
left <- (n - 2) * (1 - theta^2)^((n - 1) / 2)
right <- (1 - theta_hat^2)^((n - 4) / 2)
return(left*right)
}
Putting this all together for the full density function:
lik_dens <- function(theta, theta_hat, n) {
left_side_res <- non_calc_part(theta, theta_hat, n)
integral_result <- integrate(integrand, lower = -1, upper = 1,
theta = theta, theta_hat = theta_hat, n = n)
# The final likelihood is the product of the two parts, and the integral result, all divided by pi to normalize it according to the equation.
return((left_side_res/pi) * integral_result$value)
}
Let’s plot the density function of \(\hat{\theta}\) as a function of \(\theta\):
theta_hat <- samp_cor(m,v) # Correlation coefficient from the data
n <- length(m) # Sample size
# Compute the likelihood for each theta value
likelihood_values <- sapply(theta, function(theta) {
lik_dens(theta, theta_hat, n)
})
# Create a data frame for plotting
likelihood_df <- data.frame(
theta = theta,
Likelihood = likelihood_values
)
lik_dens_plot <- ggplot(likelihood_df, aes(x = theta, y = Likelihood)) +
geom_line( size = 2, colour="red") +
geom_vline(xintercept = mle_theta, color = "black", linetype = "dotted", size = 1.2) +
labs(title = "Density Function of the Observed Sample Correlation", x = "theta", y = "Density") +
theme_minimal()+annotate("text", x = mle_theta-0.2, y = 0.25, label = paste("MLE =", round(mle_theta, 3)),
hjust = -.95, vjust = 10, color = "black", size = 5) # Adding MLE annotation
ggplotly(lik_dens_plot)
Alright, now that we have the likelihood down, we can move on to
priors.
Priors
These represent our prior beliefs or knowledge about theta, before
seeing the data (even though we did calculate \(\hat{\theta}\) before, but let’s pretend we
didn’t). The prior will update based on the new evidence (data) to form
the posterior.
Let’s define the priors as specified in Chapter 3. But, for the sake
of demonstration and comparison, I will add another prior of different
“type,” not uninformative or weakly-informative.
Instead, I’ll define an informative prior.
Shrinkage/Triangular Prior
This is a prior that is less “ignorant” of the state of affairs, but
still not very informative. It reflects a belief that \(\theta\) is likely to be close to 0 with
decreasing probability as it moves toward -1 or 1.
In R:
shrink_prior <- function(theta) {
ifelse(theta >= -1 & theta <= 1, 1 - abs(theta), 0)
}
Jeffery’s Prior
Again, not completely “ignorant,” but, in away, this prior is a
little like the complement, or the opposite of Jeffery’s prior because
it “penalizes” parameter values which are closer to 0. Note that at -1
and 1, this function is undefined.
\[g^{Jeff}(\theta)=\frac{1}{1-\theta^2}\]
jeff_prior <- function(theta) {
ifelse(theta > -1 & theta < 1, 1 / (1 - theta^2), 0)
}
Finally, the added, informative prior.
Plotting the Priors
First, we compute the values of each prior across the range of \(\theta s\)
uniform_values <- sapply(theta, flat_prior)
jeffreys_values <- sapply(theta, jeff_prior)
shrinkage_values <- sapply(theta, shrink_prior)
informative_values <- sapply(theta, informative_prior)
And, plotting…
# Create a data frame to hold the prior values for plotting
prior_data <- data.frame(
theta = rep(theta, 4),
prior_value = c(uniform_values, jeffreys_values, shrinkage_values, informative_values),
prior_type = factor(rep(c("Uniform/Flat", "Jeffrey's", "Shrinkage/Triangular", "Informative"), each = length(theta)))
)
# Plot the priors using ggplot
p2 <- ggplot(prior_data, aes(x = theta, y = prior_value, color = prior_type)) +
geom_line(size = 2, alpha=.85) +
labs(title = "Prior Types",
x = "theta",
y = "Prior Density",
color = "Prior Type") +
theme_minimal() +
theme(
plot.title = element_text(hjust = 0.5)
)+ylim(0,4.5)+scale_color_manual(values=met.brewer("Peru1", 4))
ggplotly(p2)
Posteriors
In Bayesian inference, the posterior is proportional to the product
of the likelihood and the prior,
\[P(\theta|data) \propto P(\theta) \cdot
P(data|\theta)\]
To get the posteriors, we need the product of each prior with the
likelihood density function. But, for the posterior to be a proper
probability density function (PDF), we have to normalize it
(standardize, make sure it sums up to 1) so that we can work with
probabilities instead of some unintuitive value system.
To normalize it, we need to know the area under the curve, which,
with continuous variables, is harder to get - So, we need to use
calculus!
With integration we can compute the total “unnormalized” area under
the posterior curve, and then the posterior values are divided by this
area to ensure that the area under the normalized posterior is 1.
I’m sure there are more elegant ways of doing this, or ways that rely
less on support functions like I used here (e.g.,
integrate()
, approxfun()
). Nonetheless, this
should work.
I start with building a “one-size-fits-most-priors” function that
basically multiplies the likelihood with the prior…so, no normalization
just yet.
# Posterior function calculation using Bayes' Rule(s!) - some of it, at least
posterior <- function(theta, lik_dens, prior_fn, theta_hat, n) {
posterior_values <- lik_dens(theta, theta_hat, n) * prior_fn(theta)
return(posterior_values)
}
Next, let’s build another function that would do the normalization
(the integration piece). The integrate()
function is using
a quadrature approach.
# Normalization function for posterior (using integration)
normalize_posterior <- function(posterior_values, theta) {
# Approximate the area under the curve
integral_value <- integrate(approxfun(theta, posterior_values), lower=-1, upper=1)$value
# Normalize the posterior by dividing by the integral value - should sum up to 1-ish
normalized_posterior <- posterior_values / integral_value
return(normalized_posterior)
}
OK, now let’s apply these functions together to get the posteriors
associated with each prior.
# Compute posteriors values for each prior
# Jeffery's
post_jeff <- sapply(theta, function(theta) posterior(theta, lik_dens, jeff_prior, theta_hat, n))
# Shrinkage/triangular
post_shrink <- sapply(theta, function(theta) posterior(theta, lik_dens, shrink_prior, theta_hat, n))
# flat/uniform/uninformative
post_uniform <- sapply(theta, function(theta) posterior(theta, lik_dens, flat_prior, theta_hat, n))
# Udi's added prior!
post_inform <- sapply(theta, function(theta) posterior(theta, lik_dens, informative_prior, theta_hat, n))
# Normalize the posterior values.
post_jeff_proper <- normalize_posterior(post_jeff, theta)
post_shrink_proper <- normalize_posterior(post_shrink, theta)
post_uniform_proper <- normalize_posterior(post_uniform, theta)
post_inform_proper <- normalize_posterior(post_inform, theta)
# We can also add the likelihood density function and normalize it so it can be added to the plot...
lik_dens_proper <- normalize_posterior(likelihood_df$Likelihood, theta)
We can check the the integration part was done well. We are looking
for the area to be 1 or very close…
integrate(approxfun(theta, post_jeff_proper), -1, 1) # nice...
## 1 with absolute error < 6.6e-05
integrate(approxfun(theta, post_shrink_proper), -1, 1) # great...
## 1 with absolute error < 1.5e-05
integrate(approxfun(theta, post_uniform_proper), -1, 1) # alright...
## 1 with absolute error < 2.5e-05
integrate(approxfun(theta, post_inform_proper), -1, 1) # cool...
## 1 with absolute error < 2.4e-05
integrate(approxfun(theta, lik_dens_proper), -1, 1) # good job...
## 1 with absolute error < 2.5e-05
Now, for the fun part…Let’s try to reproduce Figure 3.2.
Plotting the Posteriors
# Create a data frame to contain all the posterior info
posterior_dat <- data.frame(
theta = rep(theta, 5),
posterior_value = c(post_jeff_proper, post_shrink_proper, post_uniform_proper, post_inform_proper, lik_dens_proper),
prior_type = factor(rep(c("Jeffrey's", "Shrinkage/Triangular", "Uniform/Flat", "Informative (Udi's)", "Likelihood PDF (MLE)"), each = length(theta)))
)
# Plot posterior distributions
p3 <- ggplot(posterior_dat, aes(x = theta, y = round(posterior_value/100,5), color = prior_type, linetype = prior_type)) +
geom_line(size = 1.2, alpha=.9) +
labs(title = "Posterior Distributions with Different Priors",
x = "theta",
y = "Posterior Density",
color = "Prior Type") +
theme_minimal() +
theme(
plot.title = element_text(hjust = 0.5),
legend.position = "bottom"
)+xlim(-0.35,1)+scale_color_manual(values=met.brewer("Lakota", 5))
ggplotly(p3)
LS0tCnRpdGxlOiAiQ0FTSSBDaC4zOiBCYXllc2lhbiBJbmZlcmVuY2UiCnN1YnRpdGxlOiB8IAogICAgU0NTIFNob3cgJiBUZWxsIEV4YW1wbGUgMiBESVkKICAgIAogICAgXG5ld2xpbmUhW10oL1VzZXJzL3VkaWFsdGVyL0xpYnJhcnkvQ2xvdWRTdG9yYWdlL0dvb2dsZURyaXZlLXVkaS5hbHRlckBnbWFpbC5jb20vTXkgRHJpdmUvQmF5ZXMucG5nKXt3aWR0aD0yNSV9ICAKYXV0aG9yOiAiVWRpIEFsdGVyIgpkYXRlOiAiMjcgU2VwdGVtYmVyLCAyMDI0IgpvdXRwdXQ6CiAgaHRtbF9kb2N1bWVudDoKICAgIGZpZ193aWR0aDogMTAKICAgIGZpZ19oZWlnaHQ6IDgKICAgIGRmX3ByaW50OiBwYWdlZAogICAgY29kZV9mb2xkaW5nOiBzaG93CiAgICB0aGVtZTogam91cm5hbAogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDMKICAgIHRvY19mbG9hdDoKICAgICAgY29sbGFwc2VkOiB0cnVlCiAgICAgIHNtb290aF9zY3JvbGw6IHRydWUKICAgIHNlbGZfY29udGFpbmVkOiB5ZXMKICAgIGxpZ2h0Ym94OiB5ZXMKICAgIGdhbGxlcnk6IHllcwogICAgY29kZV9kb3dubG9hZDogeWVzCi0tLQoKCmBgYHtjc3Mgc2lkZW5vdGUsIGVjaG8gPSBGQUxTRX0KLnNpZGVub3RlLCAubWFyZ2lubm90ZSB7IAogIGZsb2F0OiByaWdodDsKICBtYXJnaW4tcmlnaHQ6IC0xMCU7CiAgd2lkdGg6IDEwMCU7ICAgICAgICAgIyBiZXN0IGJldHdlZW4gNTAlIGFuZCA2MCUKICBtYXJnaW4tYm90dG9tOiAwOwogIGZvbnQtc2l6ZTogM3JlbTsKICBsaW5lLWhlaWdodDogMS4yOwogIH0KYGBgCgoKYGBge2NzcywgZWNobz1GQUxTRX0KaDEsIGgyLCBoMywgaDQgewogIHRleHQtYWxpZ246IGNlbnRlcjsKICBmb250LXdlaWdodDogYm9sZDsKICBmb250LXNpemU6IDMwcHg7Cn0KYm9keSB7CiAgZm9udC1zaXplOiAyMHB4Owp9CgpgYGAKCgoKCkZpcnN0LCB3ZSBuZWVkIHRoZSBmb2xsb3dpbmcgcGFja2FnZXM6CgojIyMgUmVxdWlyZWQgcGFja2FnZXMKCmBgYHtyLCB3YXJuaW5nPUYsIG1lc3NhZ2U9RkFMU0V9CiMgTG9hZCBpbiBsaWJyYXJpZXMKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoUkNvbG9yQnJld2VyKQpsaWJyYXJ5KE1ldEJyZXdlcikKbGlicmFyeShwbG90bHkpCmxpYnJhcnkocmVzaGFwZTIpCmBgYAoKCldoaWxlIHdlIGRvbid0IGFjdHVhbGx5IG5lZWQgdGhlIHJhdyBkYXRhLCBpdCBtaWdodCBiZSBuaWNlIHRvIGhhdmUgaXQgYW5kIGNoZWNrLiBTbywgaGVyZSBpdCBpcyBlbnRlcmVkIG1hbnVhbGx5LgoKIyBEYXRhCgpTY29yZXMgZnJvbSB0d28gdGVzdHMgdGFrZW4gYnkgMjIgc3R1ZGVudHMsIGBtZWNoYW5pY3NgIGFuZCBgdmVjdG9yc2AuCgpgYGB7cn0Kc3R1ZGVudCA8LSAxOjIyCm0gPC0gbWVjaGFuaWNzIDwtIGMoNywgNDQsIDQ5LCA1OSwgMzQsIDQ2LCAwLCAzMiwgNDksIDUyLCA0NCwgMzYsIDQyLCA1LCAyMiwgMTgsIDQxLCA0OCwgMzEsIDQyLCA0NiwgNjMpCnYgPC0gdmVjdG9ycyA8LSBjKDUxLCA2OSwgNDEsIDcwLCA0MiwgNDAsIDQwLCA0NSwgNTcsIDY0LCA2MSwgNTksIDYwLCAzMCwgNTgsIDUxLCA2MywgMzgsIDQyLCA2OSwgNDksIDYzKQoKIyBDb21iaW5lIGludG8gYSBkYXRhIGZyYW1lCihkYXRhIDwtIGRhdGEuZnJhbWUoU3R1ZGVudCA9IHN0dWRlbnQsIE1lY2hhbmljcyA9IG1lY2hhbmljcywgVmVjdG9ycyA9IHZlY3RvcnMpKQoKIyBjb3JyZWxhdGlvbiBjb2VmZmljaWVudCAKKGNvcl9tdiA8LSBjb3IobWVjaGFuaWNzLCB2ZWN0b3JzKSkKYGBgCgoKClBsb3R0aW5nIHRoZSBkYXRhIGFuZCBmaXR0aW5nIGJvdGggbGluZWFyIChyZWQpIGFuZCBsb3dlc3MgKGJsdWUpIHJlZ3Jlc3Npb24gbGluZXMuCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpwMSA8LSBnZ3Bsb3QoZGF0YSwgYWVzKHg9TWVjaGFuaWNzLCB5PVZlY3RvcnMpKStnZW9tX3BvaW50KHNpemU9MykrCiAgZ2VvbV9zbW9vdGgobWV0aG9kID0gImxtIiwgY29sb3VyPSJyZWQiLCBzaXplPTIsIHNlPUZBTFNFKSsKICBnZW9tX3Ntb290aChtZXRob2QgPSAibG9lc3MiLCBjb2xvdXI9ImJsdWUiLCBzaXplPTIsICBzZT1GQUxTRSwgc3Bhbj0wLjg1KSsKICB0aGVtZV9taW5pbWFsKCkKCmdncGxvdGx5KHAxKQpgYGAKCgpXZSBjYW4gdGFrZSBFcXVhdGlvbiAzLjEwLCQkXGhhdHtcdGhldGF9ID0gXGZyYWN7XHN1bV97aT0xfV57MjJ9IChtX2kgLSBcYmFye219KSh2X2kgLSBcYmFye3Z9KX17XGxlZnRbXHN1bV97aT0xfV57MjJ9IChtX2kgLSBcYmFye219KV4yIFxzdW1fe2k9MX1eezIyfSAodl9pIC0gXGJhcnt2fSleMlxyaWdodF1eezEvMn19JCQsIGFuZCBtYWtlIGl0IGludG8gYW4gUiBmdW5jdGlvbi4gVGhlIGBzdGF0czo6Y29yKClgLCBvZiBjb3Vyc2UsIGlzIHN1ZmZpY2llbnQsIGJ1dCBqdXN0IGZvciBmdW4uLi4gCgojIERlZmluaW5nIHRoZSBTYW1wbGUgQ29ycmVsYXRpb24gRnVuY3Rpb24KCmBgYHtyfQoKIyBEZWZpbmUgZnVuY3Rpb24Kc2FtcF9jb3IgPC0gZnVuY3Rpb24obSwgdikgewogIAogICMgQ29tcHV0ZSB0aGUgbWVhbnMgb2YgbSBhbmQgdgogIG1fbWVhbiA8LSBtZWFuKG0pCiAgdl9tZWFuIDwtIG1lYW4odikKICAKICAjIENvbXB1dGUgdGhlIG51bWVyYXRvciBhbmQgZGVub21pbmF0b3IgZm9yIHRoZSBQZWFyc29uIGNvcnJlbGF0aW9uIGZvcm11bGEKICBudW1lcmF0b3IgPC0gc3VtKChtIC0gbV9tZWFuKSAqICh2IC0gdl9tZWFuKSkKICBkZW5vbWluYXRvciA8LSBzcXJ0KHN1bSgobSAtIG1fbWVhbileMikgKiBzdW0oKHYgLSB2X21lYW4pXjIpKQogIAogICMgQ29tcHV0ZSB0aGUgc2FtcGxlIGNvcnJlbGF0aW9uIGNvZWZmaWNpZW50ICh0aGV0YV9oYXQpCiAgbnVtZXJhdG9yIC8gZGVub21pbmF0b3IKICAKfQoKIyB0cnlpbmcgdG8gc2VlIHRoYXQgaXQgd29ya3MKc2FtcF9jb3IobWVjaGFuaWNzLCB2ZWN0b3JzKQphbGwuZXF1YWwoY29yKG1lY2hhbmljcywgdmVjdG9ycyksIHNhbXBfY29yKG1lY2hhbmljcywgdmVjdG9ycykpICMgQWxyaWdodC4uLgoKYGBgCgoKRXhhbXBsZSAyIGlzIGdyZWF0LCBidXQgaXQgc2tpcHMgb3ZlciB0aGUgc3R1ZmYgaGFwcGVuaW5nICJ1bmRlciB0aGUgaG9vZC4iIEJlY2F1c2UgaXQncyBub3QgaGlnaC1kaW1lbnNpb25hbCAoc28gbm8gbmVlZCBmb3IgZmFuY3kgTUNNQyksIHdoeSBkb24ndCB3ZSB0cnkgdG8gZG8gcmVwcm9kdWNlIHRoZSBleGFtcGxlIGFuZCByZXN1bHRzIHdpdGggYSAobW9zdGx5KSAiaG9tZS1iYWtlZCIgY29kZS4KCgpXaGlsZSB0aGUgbmV4dCBwYXJ0IGlzIG5vdCByZWFsbHkgQmF5ZXNpYW4sIGl0IHN0aWxsIG1pZ2h0IGJlIGZ1biB0byB0cnkgdG8gZG8gaXQgImJ5IGhhbmQuIgoKIyBMaWtlbGlob29kIEZ1bmN0aW9uIChhbmQgTUxFICJieSBoYW5kIikKCkVmcm9uIGFuZCBIYXN0aWUgKEJyYWQgYW5kIFRyZXYpIGNob3NlIGEgJFxzaWdtYV4yPTEkIGZvciB0aGUgdW5pZGltZW5zaW9uYWwgbm9ybWFsIGRlbnNpdHkgZnVuY3Rpb24gaW4gRXEgMy4yIChwLiAyMiksIGJ1dCBJIHdpbGwgdXNlIGEgc21hbGxlciB2YWx1ZSwgJFxzaWdtYT0uMSQgKHNvIHRoYXQgdGhlIGdyYXBoIGxhdGVyIG9uIHdvdWxkIGxvb2sgbmljZXIpLiAKClRoZSBmb2xsb3dpbmcgbGlrZWxpaG9vZCBmdW5jdGlvbiBkb2VzIG5vdCBhY3R1YWxseSBuZWVkIHRoZSBkYXRhLCBvbmx5IHRoZSBlc3RpbWF0ZSwgJFxoYXR7XHRoZXRhfSQsIHNvIGl0IGRvZXNuJ3QgaW5jbHVkZSB0aGUgaXRlcmF0aXZlIG11bHRpcGxpY2F0aW9uIGZvciBlYWNoIG9ic2VydmF0aW9uIGFuZCB0aGUgY29uc3RhbnQsIGp1c3QgdGhlIGV4cG9uZW50aWFsIHBpZWNlLiBIZXJlIGl0IGlzOgoKJCRcZXhwXGxlZnQoLSBcZnJhY3soXGhhdHtcdGhldGF9IC0gXHRoZXRhKV4yfXsyXHNpZ21hXjJ9XHJpZ2h0KSQkCgpBbmQsIGFzIGEgZnVuY3Rpb24gaW4gUjoKCmBgYHtyfQojIExpa2VsaWhvb2QgZnVuY3Rpb24gZm9yIE1MRSB3aXRoIHZhcmlhbmNlIHlvdSBjYW4gbW9kaWZ5LCAKbGlrZWxpaG9vZCA8LSBmdW5jdGlvbih0aGV0YSwgbSwgdiwgc2lnbWEgPSAwLjAxKSB7CiAgIyBDb21wdXRlIHNhbXBsZSBjb3JyZWxhdGlvbiBjb2VmZmljaWVudCB1c2luZyBzYW1wX2NvcgogIHRoZXRhX2hhdCA8LSBzYW1wX2NvcihtLCB2KQogICMgTGlrZWxpaG9vZCBmdW5jdGlvbiBjb21wbGV0ZSAKICBsaWtlbGlob29kIDwtIGV4cCgtICh0aGV0YV9oYXQgLSB0aGV0YSleMiAvICgyICogc2lnbWFeMikpCiAgcmV0dXJuKGxpa2VsaWhvb2QpCn0KYGBgCgpCZWZvcmUgd2UgdHJ5IGl0IG91dCBvciBjb250aW51ZSwgd2Ugc2hvdWxkIG1ha2Ugc29tZSBwb3NzaWJsZSBwYXJhbWV0ZXIgdmFsdWVzIHRoYXQgdGhldGEgY2FuIHRha2UsIGZyb20gLTEgdG8gMToKCiQkXHRoZXRhIFxpbiBbLTEsIDFdJCQKCmBgYHtyfQojIHBvc3NpYmxlIHZhbHVlcyB0aGV0YSBjYW4gdGFrZSwgZnJvbQp0aGV0YSA8LSBzZXEoLTEsMSwgbGVuZ3RoLm91dD0xMDAwKQpgYGAKCgpPSywgaWYgd2Ugd2FudCB0byBmaW5kIHRoZSBtYXhpbXVtLWxpa2VsaWhvb2QgZXN0aW1hdGUgKE1MRSksIGFzIGluIEZpZ3VyZSAzLjIgKHAuIDI3KSwgYmV0dGVyIHRvIHRha2UgdGhlIGxvZyBvZiB0aGUgZnVuY3Rpb24gc28gdGhhdCB3ZSBkb24ndCBkZWFsIHdpdGggdmVyeSwgdmVyeSBzbWFsbCB2YWx1ZXMuIEJlY2F1c2UgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gd2FzIGFuICRlXnt0ZXJtfSQsIHRoZSBsb2cgb2YgaXQgaXMgdGhlbiBqdXN0IHRoZSAkdGVybSQuIFRoYXQgaXMsICQkLSBcZnJhY3soXGhhdHtcdGhldGF9IC0gXHRoZXRhKV4yfXsyXHNpZ21hXjJ9JCQKCmBgYHtyfQojIExvZy1saWtlbGlob29kIGZ1bmN0aW9uIGZvciBNTEUKTEwgPC0gZnVuY3Rpb24odGhldGEsIG0sIHYsIHNpZ21hPTAuMDEpIHsKICAjIENvbXB1dGUgc2FtcGxlIGNvcnJlbGF0aW9uIGNvZWZmaWNpZW50IHVzaW5nIHRoZSBzYW1wX2NvciBmdW5jdGlvbgogIHRoZXRhX2hhdCA8LSBzYW1wX2NvcihtLCB2KQogICMgTG9nLWxpa2VsaWhvb2QgZnVuY3Rpb246IGxvZyBvZiB0aGUgbGlrZWxpaG9vZC4gCiAgbG9nX2xpa2VsaWhvb2QgPC0gLSh0aGV0YV9oYXQgLSB0aGV0YSleMiAvICgyICogc2lnbWFeMikKICByZXR1cm4obG9nX2xpa2VsaWhvb2QpCn0KYGBgCgpXZSBjYW4gZmluZCB0aGUgcGFyYW1ldGVyIHZhbHVlIHRoYXQgcHJvZHVjZXMgdGhlIGhpZ2hlc3QgKGxvZy0pbGlrZWxpaG9vZCBieSBvcHRpbWl6YXRpb24uIEknbSBzdXJlIGl0IGNhbiBiZSBkb25lIHdpdGggRFlJIGNvZGUsIGJ1dCBJIHdpbGwganVzdCB1c2UgdGhlIGBvcHRpbWl6ZWAgZnVuY3Rpb24sIGlmIHlhJ2xsIGRvbid0IG1pbmQuCgpgYGB7cn0KCiMgZmluZCBNTEUgd2l0aCBvcHRpbWl6YXRpb25zLi4uCm9wdGltaXplKExMLCBpbnRlcnZhbCA9IGMoLTEsIDEpLCBtID0gbSwgdiA9IHYsIHNpZ21hID0gMC4wMSwgbWF4aW11bSA9IFRSVUUpICMgU2FtZSBhcyBjb3IsIHN1cnByaXNlIHN1cnByaXNlIDspCgoKb3B0aW1pemUobGlrZWxpaG9vZCwgaW50ZXJ2YWwgPSBjKC0xLCAxKSwgbSA9IG0sIHYgPSB2LCBzaWdtYSA9IDAuMDEsIG1heGltdW0gPSBUUlVFKQoKYGBgCgoKCldlIGNhbiBhbHNvIHBsb3QgdGhpcy4gTm90ZSwgaG93ZXZlciwgdGhhdCB0aGlzIGlzIG5vdCB0aGUgc2FtZSBhcyBpbiBGaWd1cmUgMy4yIHdoZXJlIGl0IGlzIHRoZSBwb3N0ZXJpb3IgZnJvbSBhIGZsYXQgcHJpb3IuIEhlcmUsIHdlIHBsb3QgdGhlIGxvZy1saWtlbGlob29kIGZ1bmN0aW9uIGFuZCB0aGUgTUxFIGxvY2F0aW9uLgoKYGBge3J9CiNDYWxjdWxhdGUgbG9nLWxpa2VsaWhvb2QgZm9yIGVhY2ggdGhldGEKTExfdmFsdWVzIDwtIHNhcHBseSh0aGV0YSwgZnVuY3Rpb24odGhldGEpIExMKHRoZXRhLCBtLCB2KSkKCiMgRmluZCB0aGUgTUxFIHVzaW5nIHRoZSBsb2ctbGlrZWxpaG9vZCBmdW5jdGlvbgptbGVfcmVzIDwtIG9wdGltaXplKExMLCBpbnRlcnZhbCA9IGMoLTEsIDEpLCBtID0gbSwgdiA9IHYsIHNpZ21hID0gMC4xLCBtYXhpbXVtID0gVFJVRSkKKG1sZV90aGV0YSA8LSBtbGVfcmVzJG1heGltdW0pICAjIGVzdGltYXRlIG9mIHRoZXRhCgojIFByZXBhcmUgZGF0YSBmb3IgcGxvdHRpbmcKcGxvdF9kYXRhIDwtIGRhdGEuZnJhbWUoCiAgdGhldGEgPSB0aGV0YSwKICBsb2dfbGlrZWxpaG9vZCA9IExMX3ZhbHVlcwopCgojIFBsb3QgIGxvZy1saWtlbGlob29kIHVzaW5nIGdncGxvdAptbGVfcGxvdCA8LSBnZ3Bsb3QocGxvdF9kYXRhLCBhZXMoeCA9IHRoZXRhKSkgKwogIGdlb21fbGluZShhZXMoeSA9IGxvZ19saWtlbGlob29kKSwgY29sb3IgPSAicmVkIiwgc2l6ZSA9IDIpICsKICBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQgPSBtbGVfdGhldGEsIGNvbG9yID0gImJsYWNrIiwgbGluZXR5cGUgPSAiZG90dGVkIiwgc2l6ZSA9IDEuMikgKwogIGxhYnModGl0bGUgPSAiTG9nLUxpa2VsaWhvb2QgZnVuY3Rpb24gYW5kIE1MRSIsCiAgICAgICB4ID0gInRoZXRhIiwKICAgICAgIHkgPSAiVmFsdWUiKSArCiAgdGhlbWVfbWluaW1hbCgpICsKICB0aGVtZSgKICAgIHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpLAogICAgbGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiCiAgKSthbm5vdGF0ZSgidGV4dCIsIHggPSBtbGVfdGhldGEtMC4yLCB5ID0gLTExMDAwLCBsYWJlbCA9IHBhc3RlKCJNTEUgPSIsIHJvdW5kKG1sZV90aGV0YSwgMykpLAogICAgICAgICAgIGhqdXN0ID0gLS45NSwgdmp1c3QgPSAxMCwgY29sb3IgPSAiYmxhY2siLCBzaXplID0gNSkgICMgQWRkaW5nIE1MRSBhbm5vdGF0aW9uCgpnZ3Bsb3RseShtbGVfcGxvdCkKYGBgCgoKCldlIGNhbiBnbyBiYWNrIHRvIEV4YW1wbGUgMi4gU3BlY2lmaWNhbGx5LCB0byBFcXVhdGlvbiAzLjExCgojIENvcnJlbGF0aW9uIENvZWZmaWNpZW50IERlbnNpdHkKCkFzc3VtaW5nIHRoYXQgdGhlIGpvaW50ICQobSwgdikkIGRpc3RyaWJ1dGlvbiBpcyBiaXZhcmlhdGUgbm9ybWFsIC0tIHAuIDI2LgoKU2lkZSBub3RlLCBoZXJlJ3MgYSBkZXRhaWxzIG9mIHRoZSBub3RlIGluIHAuIDI2OgoKPiAiRm9ybXVsYSAoMy4xMSkgZm9yIHRoZSBjb3JyZWxhdGlvbiBjb2VmZmljaWVudCBkZW5zaXR5IHdhcyAKPiAgUi4gQS4gRmlzaGVy4oCZcyBkZWJ1dCBjb250cmlidXRpb24gdG8gdGhlIHN0YXRpc3RpY3MgbGl0ZXJhdHVyZS4iCj4KPiBgciB0dWZ0ZTo6cXVvdGVfZm9vdGVyKCctLS0gRWZmcm9uICYgSGFzdGllJylgCgoKCiQkCmZfe1x0aGV0YX0oXGhhdHtcdGhldGF9KSA9IFxmcmFjeyhuIC0gMikoMSAtIFx0aGV0YV4yKV57KG4gLSAxKS8yfSBcbGVmdCgxIC0gXGhhdHtcdGhldGF9XjJccmlnaHQpXnsobiAtIDQpLzJ9fXtccGl9IFxpbnRfMF57XGluZnR5fSBcZnJhY3tkd317XGxlZnQoXGNvc2godykgLSBcdGhldGEgXGhhdHtcdGhldGF9XHJpZ2h0KV57bi0xfX0KJCQKCgpMZXTigJlzIGRlZmluZSB0aGlzIGFzIGEgZnVuY3Rpb24gaW4gUi4gQnV0LCBJ4oCZbGwgdHJ5IHRvIGJyZWFrIGl0IGRvd24gaW50byBzbWFsbGVyIHBpZWNlcywgYmVjYXVzZSBpdOKAmXMgYSBsb3TigKYKCldlIHN0YXJ0IHdpdGggdGhlIHJpZ2h0LWhhbmQtc2lkZSBvZiB0aGUgZGVuc2l0eSBmdW5jdGlvbiwgdGhlICppbnRlZ3JhbmQqLCB0aGUgaHlwZXJib2xpYyBjb3NpbmUgdGhhdCBzaG91bGQgYmUgaW50ZWdyYXRlZC4KClRoZSBpbnRlZ3JhbmQgdXNlcyBoeXBlcmJvbGljIGNvc2luZSwgYW5kIHRoZXRhLCB0aGUgcGFyYW1ldGVyIG9mIGludGVyZXN0OgoKJCQKXGludF8wXntcaW5mdHl9IFxmcmFje2R3fXtcbGVmdChcY29zaCh3KSAtIFx0aGV0YSBcaGF0e1x0aGV0YX1ccmlnaHQpXntuLTF9fQokJAoKSW4gUjoKCmBgYHtyfQppbnRlZ3JhbmQgPC0gZnVuY3Rpb24odywgdGhldGEsIHRoZXRhX2hhdCwgbikgewogIHJldHVybigxIC8gKGNvc2godykgLSB0aGV0YSAqIHRoZXRhX2hhdCleKG4gLSAxKSkKfQoKYGBgCgoKTmV4dCwgdGhlIG51bWVyYXRvciBvZiB0aGUgbGVmdC1oYW5kLXNpZGUgb2YgdGhlIGRlbnNpdHkgZnVuY3Rpb24gKHRoZSBwcmUtY2FsY3VsdXMgcGFydOKApik6CgokJAoobiAtIDIpKDEgLSBcdGhldGFeMileeyhuIC0gMSkvMn0gXGxlZnQoMSAtIFxoYXR7XHRoZXRhfV4yXHJpZ2h0KV57KG4gLSA0KS8yfQokJAoKYGBge3J9Cm5vbl9jYWxjX3BhcnQgPC0gZnVuY3Rpb24odGhldGEsIHRoZXRhX2hhdCwgbikgewogIGxlZnQgPC0gKG4gLSAyKSAqICgxIC0gdGhldGFeMileKChuIC0gMSkgLyAyKSAgCiAgcmlnaHQgPC0gKDEgLSB0aGV0YV9oYXReMileKChuIC0gNCkgLyAyKQogIHJldHVybihsZWZ0KnJpZ2h0KQp9CmBgYAoKClB1dHRpbmcgdGhpcyBhbGwgdG9nZXRoZXIgZm9yIHRoZSBmdWxsIGRlbnNpdHkgZnVuY3Rpb246CgpgYGB7cn0KbGlrX2RlbnMgPC0gZnVuY3Rpb24odGhldGEsIHRoZXRhX2hhdCwgbikgewogICAgICAgICAgICAgIGxlZnRfc2lkZV9yZXMgPC0gbm9uX2NhbGNfcGFydCh0aGV0YSwgdGhldGFfaGF0LCBuKQogIAogICAgICAgICAgICAgIGludGVncmFsX3Jlc3VsdCA8LSBpbnRlZ3JhdGUoaW50ZWdyYW5kLCBsb3dlciA9IC0xLCB1cHBlciA9IDEsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdGhldGEgPSB0aGV0YSwgdGhldGFfaGF0ID0gdGhldGFfaGF0LCBuID0gbikKICAjIFRoZSBmaW5hbCBsaWtlbGlob29kIGlzIHRoZSBwcm9kdWN0IG9mIHRoZSB0d28gcGFydHMsIGFuZCB0aGUgaW50ZWdyYWwgcmVzdWx0LCBhbGwgZGl2aWRlZCBieSBwaSB0byBub3JtYWxpemUgaXQgYWNjb3JkaW5nIHRvIHRoZSBlcXVhdGlvbi4KICByZXR1cm4oKGxlZnRfc2lkZV9yZXMvcGkpICogaW50ZWdyYWxfcmVzdWx0JHZhbHVlKQp9CmBgYAoKCkxldOKAmXMgcGxvdCB0aGUgZGVuc2l0eSBmdW5jdGlvbiBvZiAkXGhhdHtcdGhldGF9JCBhcyBhIGZ1bmN0aW9uIG9mICRcdGhldGEkOgoKYGBge3J9CnRoZXRhX2hhdCA8LSBzYW1wX2NvcihtLHYpICAjIENvcnJlbGF0aW9uIGNvZWZmaWNpZW50IGZyb20gdGhlIGRhdGEKbiA8LSBsZW5ndGgobSkgICMgU2FtcGxlIHNpemUKCiMgQ29tcHV0ZSB0aGUgbGlrZWxpaG9vZCBmb3IgZWFjaCB0aGV0YSB2YWx1ZQpsaWtlbGlob29kX3ZhbHVlcyA8LSBzYXBwbHkodGhldGEsIGZ1bmN0aW9uKHRoZXRhKSB7CiAgbGlrX2RlbnModGhldGEsIHRoZXRhX2hhdCwgbikKfSkKCiMgQ3JlYXRlIGEgZGF0YSBmcmFtZSBmb3IgcGxvdHRpbmcKbGlrZWxpaG9vZF9kZiA8LSBkYXRhLmZyYW1lKAogIHRoZXRhID0gdGhldGEsCiAgTGlrZWxpaG9vZCA9IGxpa2VsaWhvb2RfdmFsdWVzCikKCgpsaWtfZGVuc19wbG90IDwtIGdncGxvdChsaWtlbGlob29kX2RmLCBhZXMoeCA9IHRoZXRhLCB5ID0gTGlrZWxpaG9vZCkpICsKICBnZW9tX2xpbmUoIHNpemUgPSAyLCBjb2xvdXI9InJlZCIpICsKICAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ID0gbWxlX3RoZXRhLCBjb2xvciA9ICJibGFjayIsIGxpbmV0eXBlID0gImRvdHRlZCIsIHNpemUgPSAxLjIpICsKICBsYWJzKHRpdGxlID0gIkRlbnNpdHkgRnVuY3Rpb24gb2YgdGhlIE9ic2VydmVkIFNhbXBsZSBDb3JyZWxhdGlvbiIsIHggPSAidGhldGEiLCB5ID0gIkRlbnNpdHkiKSArCiAgdGhlbWVfbWluaW1hbCgpK2Fubm90YXRlKCJ0ZXh0IiwgeCA9IG1sZV90aGV0YS0wLjIsIHkgPSAwLjI1LCBsYWJlbCA9IHBhc3RlKCJNTEUgPSIsIHJvdW5kKG1sZV90aGV0YSwgMykpLAogICAgICAgICAgIGhqdXN0ID0gLS45NSwgdmp1c3QgPSAxMCwgY29sb3IgPSAiYmxhY2siLCBzaXplID0gNSkgICMgQWRkaW5nIE1MRSBhbm5vdGF0aW9uCgoKZ2dwbG90bHkobGlrX2RlbnNfcGxvdCkKCmBgYAoKCkFscmlnaHQsIG5vdyB0aGF0IHdlIGhhdmUgdGhlIGxpa2VsaWhvb2QgZG93biwgd2UgY2FuIG1vdmUgb24gdG8gcHJpb3JzLgoKCiMgUHJpb3JzCgpUaGVzZSByZXByZXNlbnQgb3VyIHByaW9yIGJlbGllZnMgb3Iga25vd2xlZGdlIGFib3V0IHRoZXRhLCBiZWZvcmUgc2VlaW5nIHRoZSBkYXRhIChldmVuIHRob3VnaCB3ZSBkaWQgY2FsY3VsYXRlICRcaGF0e1x0aGV0YX0kIGJlZm9yZSwgYnV0IGxldCdzIHByZXRlbmQgd2UgZGlkbid0KS4gVGhlIHByaW9yIHdpbGwgdXBkYXRlIGJhc2VkIG9uIHRoZSBuZXcgZXZpZGVuY2UgKGRhdGEpIHRvIGZvcm0gdGhlIHBvc3Rlcmlvci4KCkxldOKAmXMgZGVmaW5lIHRoZSBwcmlvcnMgYXMgc3BlY2lmaWVkIGluIENoYXB0ZXIgMy4gQnV0LCBmb3IgdGhlIHNha2Ugb2YgZGVtb25zdHJhdGlvbiBhbmQgY29tcGFyaXNvbiwgSSB3aWxsIGFkZCBhbm90aGVyIHByaW9yIG9mIGRpZmZlcmVudCAidHlwZSwiIG5vdCAqdW5pbmZvcm1hdGl2ZSogb3IgKndlYWtseS1pbmZvcm1hdGl2ZSouIEluc3RlYWQsIEknbGwgZGVmaW5lIGFuICoqaW5mb3JtYXRpdmUqKiBwcmlvci4KCgoKIyMjIFVuaWZvcm0vRmxhdC9VbmluZm9ybWF0aXZlIFByaW9yCgokJGcoXHRoZXRhKT0gMS8yLCBcIGZvciAtMVxsZXEgXHRoZXRhICBcbGVxIDEgJCQKClRoaXMgaXMgYW4gdW5pbmZvcm1hdGl2ZSBwcmlvciB0aGF0IHRyZWF0cyBhbGwgdmFsdWVzIG9mICRcdGhldGEkIGJldHdlZW4gLTEgYW5kIDEgYXMgZXF1YWxseSBsaWtlbHkuCgpBcyBhIGZ1bmN0aW9uIGluIFI6CgpgYGB7cn0KZmxhdF9wcmlvciA8LSBmdW5jdGlvbih0aGV0YSkgewogICBpZmVsc2UodGhldGEgPj0gLTEgJiB0aGV0YSA8PSAxLCAxLzIsIDApICMgaWYgdGhldGEgaXMgYmV0d2VlbiAtMSBhbmQgMSwgdGhlbiAwLjUsIGVsc2UgMAp9ICAKYGBgCgoKCiMjIyBTaHJpbmthZ2UvVHJpYW5ndWxhciBQcmlvcgoKVGhpcyBpcyBhIHByaW9yIHRoYXQgaXMgbGVzcyAiaWdub3JhbnQiIG9mIHRoZSBzdGF0ZSBvZiBhZmZhaXJzLCBidXQgc3RpbGwgbm90IHZlcnkgaW5mb3JtYXRpdmUuIEl0IHJlZmxlY3RzIGEgYmVsaWVmIHRoYXQgJFx0aGV0YSQgaXMgbGlrZWx5IHRvIGJlIGNsb3NlIHRvIDAgd2l0aCBkZWNyZWFzaW5nIHByb2JhYmlsaXR5IGFzIGl0IG1vdmVzIHRvd2FyZCAtMSBvciAxLgoKCkluIFI6CgpgYGB7cn0KCnNocmlua19wcmlvciA8LSBmdW5jdGlvbih0aGV0YSkgewogIGlmZWxzZSh0aGV0YSA+PSAtMSAmIHRoZXRhIDw9IDEsIDEgLSBhYnModGhldGEpLCAwKQp9CgpgYGAKCgoKIyMjIEplZmZlcnkncyBQcmlvcgoKQWdhaW4sIG5vdCBjb21wbGV0ZWx5ICJpZ25vcmFudCwiIGJ1dCwgaW4gYXdheSwgdGhpcyBwcmlvciBpcyBhIGxpdHRsZSBsaWtlIHRoZSBjb21wbGVtZW50LCBvciB0aGUgb3Bwb3NpdGUgb2YgSmVmZmVyeSdzIHByaW9yIGJlY2F1c2UgaXQgInBlbmFsaXplcyIgcGFyYW1ldGVyIHZhbHVlcyB3aGljaCBhcmUgY2xvc2VyIHRvIDAuIE5vdGUgdGhhdCBhdCAtMSBhbmQgMSwgdGhpcyBmdW5jdGlvbiBpcyB1bmRlZmluZWQuCgoKJCRnXntKZWZmfShcdGhldGEpPVxmcmFjezF9ezEtXHRoZXRhXjJ9JCQKCgoKYGBge3J9CmplZmZfcHJpb3IgPC0gZnVuY3Rpb24odGhldGEpIHsKICBpZmVsc2UodGhldGEgPiAtMSAmIHRoZXRhIDwgMSwgMSAvICgxIC0gdGhldGFeMiksIDApCn0KYGBgCgoKRmluYWxseSwgdGhlIGFkZGVkLCBpbmZvcm1hdGl2ZSBwcmlvci4KCiMjIyBJbmZvcm1hdGl2ZSBQcmlvcgoKU2F5IHdlIGhhdmUgYSBnb29kIHJlYXNvbiB0byBiZWxpZXZlIHRoYXQgdGhlIGNvcnJlbGF0aW9uIGNvZWZmaWNpZW50IHZhcmlhYmxlIGlzIGNsb3NlIHRvICRcdGhldGE9MC44JAoKYGBge3J9CiMgVGhpcyBpcyBhIG5vcm1hbGx5IGRpc3RyaWJ1dGVkIHByaW9yIGNlbnRyZWQgYXJvdW5kIDAuOCB3aXRoIGEgdmFyaWFuY2Ugb2YgMC4yNV4yLgppbmZvcm1hdGl2ZV9wcmlvciA8LSBmdW5jdGlvbih0aGV0YSwgc2lnbWE9MC4yNSkgewogIGRub3JtKHRoZXRhLCBtZWFuID0gMC44LCBzZCA9IHNpZ21hKSAgCn0KCmBgYAoKCiMjIFBsb3R0aW5nIHRoZSBQcmlvcnMKCgoKRmlyc3QsIHdlIGNvbXB1dGUgdGhlIHZhbHVlcyBvZiBlYWNoIHByaW9yIGFjcm9zcyB0aGUgcmFuZ2Ugb2YgJFx0aGV0YSBzJAoKYGBge3J9CnVuaWZvcm1fdmFsdWVzIDwtIHNhcHBseSh0aGV0YSwgZmxhdF9wcmlvcikKamVmZnJleXNfdmFsdWVzIDwtIHNhcHBseSh0aGV0YSwgamVmZl9wcmlvcikKc2hyaW5rYWdlX3ZhbHVlcyA8LSBzYXBwbHkodGhldGEsIHNocmlua19wcmlvcikKaW5mb3JtYXRpdmVfdmFsdWVzIDwtIHNhcHBseSh0aGV0YSwgaW5mb3JtYXRpdmVfcHJpb3IpCmBgYAoKCkFuZCwgcGxvdHRpbmcuLi4KCmBgYHtyfQojIENyZWF0ZSBhIGRhdGEgZnJhbWUgdG8gaG9sZCB0aGUgcHJpb3IgdmFsdWVzIGZvciBwbG90dGluZwpwcmlvcl9kYXRhIDwtIGRhdGEuZnJhbWUoCiAgdGhldGEgPSByZXAodGhldGEsIDQpLAogIHByaW9yX3ZhbHVlID0gYyh1bmlmb3JtX3ZhbHVlcywgamVmZnJleXNfdmFsdWVzLCBzaHJpbmthZ2VfdmFsdWVzLCBpbmZvcm1hdGl2ZV92YWx1ZXMpLAogIHByaW9yX3R5cGUgPSBmYWN0b3IocmVwKGMoIlVuaWZvcm0vRmxhdCIsICJKZWZmcmV5J3MiLCAiU2hyaW5rYWdlL1RyaWFuZ3VsYXIiLCAiSW5mb3JtYXRpdmUiKSwgZWFjaCA9IGxlbmd0aCh0aGV0YSkpKQopCgojIFBsb3QgdGhlIHByaW9ycyB1c2luZyBnZ3Bsb3QKcDIgPC0gZ2dwbG90KHByaW9yX2RhdGEsIGFlcyh4ID0gdGhldGEsIHkgPSBwcmlvcl92YWx1ZSwgY29sb3IgPSBwcmlvcl90eXBlKSkgKwogIGdlb21fbGluZShzaXplID0gMiwgYWxwaGE9Ljg1KSArCiAgbGFicyh0aXRsZSA9ICJQcmlvciBUeXBlcyIsCiAgICAgICB4ID0gInRoZXRhIiwKICAgICAgIHkgPSAiUHJpb3IgRGVuc2l0eSIsCiAgICAgICBjb2xvciA9ICJQcmlvciBUeXBlIikgKwogIHRoZW1lX21pbmltYWwoKSArCiAgdGhlbWUoCiAgICBwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KQogICkreWxpbSgwLDQuNSkrc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcz1tZXQuYnJld2VyKCJQZXJ1MSIsIDQpKQoKZ2dwbG90bHkocDIpCmBgYAoKCiMgUG9zdGVyaW9ycwoKSW4gQmF5ZXNpYW4gaW5mZXJlbmNlLCB0aGUgcG9zdGVyaW9yIGlzIHByb3BvcnRpb25hbCB0byB0aGUgcHJvZHVjdCBvZiB0aGUgbGlrZWxpaG9vZCBhbmQgdGhlIHByaW9yLAoKCiQkUChcdGhldGF8ZGF0YSkgXHByb3B0byBQKFx0aGV0YSkgXGNkb3QgUChkYXRhfFx0aGV0YSkkJAoKVG8gZ2V0IHRoZSBwb3N0ZXJpb3JzLCB3ZSBuZWVkIHRoZSBwcm9kdWN0IG9mIGVhY2ggcHJpb3Igd2l0aCB0aGUgbGlrZWxpaG9vZCBkZW5zaXR5IGZ1bmN0aW9uLiBCdXQsIGZvciB0aGUgcG9zdGVyaW9yIHRvIGJlIGEgcHJvcGVyIHByb2JhYmlsaXR5IGRlbnNpdHkgZnVuY3Rpb24gKFBERiksIHdlIGhhdmUgdG8gbm9ybWFsaXplIGl0IChzdGFuZGFyZGl6ZSwgbWFrZSBzdXJlIGl0IHN1bXMgdXAgdG8gMSkgc28gdGhhdCB3ZSBjYW4gd29yayB3aXRoIHByb2JhYmlsaXRpZXMgaW5zdGVhZCBvZiBzb21lIHVuaW50dWl0aXZlIHZhbHVlIHN5c3RlbS4KClRvIG5vcm1hbGl6ZSBpdCwgd2UgbmVlZCB0byBrbm93IHRoZSBhcmVhIHVuZGVyIHRoZSBjdXJ2ZSwgd2hpY2gsIHdpdGggY29udGludW91cyB2YXJpYWJsZXMsIGlzIGhhcmRlciB0byBnZXQgLSBTbywgd2UgbmVlZCB0byB1c2UgY2FsY3VsdXMhIAoKCldpdGggaW50ZWdyYXRpb24gd2UgY2FuIGNvbXB1dGUgdGhlIHRvdGFsIOKAnHVubm9ybWFsaXplZOKAnSBhcmVhIHVuZGVyIHRoZSBwb3N0ZXJpb3IgY3VydmUsIGFuZCB0aGVuIHRoZSBwb3N0ZXJpb3IgdmFsdWVzIGFyZSBkaXZpZGVkIGJ5IHRoaXMgYXJlYSB0byBlbnN1cmUgdGhhdCB0aGUgYXJlYSB1bmRlciB0aGUgbm9ybWFsaXplZCBwb3N0ZXJpb3IgaXMgMS4KCgpJJ20gc3VyZSB0aGVyZSBhcmUgbW9yZSBlbGVnYW50IHdheXMgb2YgZG9pbmcgdGhpcywgb3Igd2F5cyB0aGF0IHJlbHkgbGVzcyBvbiBzdXBwb3J0IGZ1bmN0aW9ucyBsaWtlIEkgdXNlZCBoZXJlIChlLmcuLCBgaW50ZWdyYXRlKClgLCBgYXBwcm94ZnVuKClgKS4gTm9uZXRoZWxlc3MsIHRoaXMgc2hvdWxkIHdvcmsuCgoKSSBzdGFydCB3aXRoIGJ1aWxkaW5nIGEgIm9uZS1zaXplLWZpdHMtbW9zdC1wcmlvcnMiIGZ1bmN0aW9uIHRoYXQgYmFzaWNhbGx5IG11bHRpcGxpZXMgdGhlIGxpa2VsaWhvb2Qgd2l0aCB0aGUgcHJpb3IuLi5zbywgbm8gbm9ybWFsaXphdGlvbiBqdXN0IHlldC4KCmBgYHtyfQojIFBvc3RlcmlvciBmdW5jdGlvbiBjYWxjdWxhdGlvbiB1c2luZyBCYXllcycgUnVsZShzISkgLSBzb21lIG9mIGl0LCBhdCBsZWFzdApwb3N0ZXJpb3IgPC0gZnVuY3Rpb24odGhldGEsIGxpa19kZW5zLCBwcmlvcl9mbiwgdGhldGFfaGF0LCBuKSB7CiAgcG9zdGVyaW9yX3ZhbHVlcyA8LSBsaWtfZGVucyh0aGV0YSwgdGhldGFfaGF0LCBuKSAqIHByaW9yX2ZuKHRoZXRhKQogIHJldHVybihwb3N0ZXJpb3JfdmFsdWVzKQp9CmBgYAoKCk5leHQsIGxldCdzIGJ1aWxkIGFub3RoZXIgZnVuY3Rpb24gdGhhdCB3b3VsZCBkbyB0aGUgbm9ybWFsaXphdGlvbiAodGhlIGludGVncmF0aW9uIHBpZWNlKS4gVGhlIGBpbnRlZ3JhdGUoKWAgZnVuY3Rpb24gaXMgdXNpbmcgYSBxdWFkcmF0dXJlIGFwcHJvYWNoLgoKCmBgYHtyfQojIE5vcm1hbGl6YXRpb24gZnVuY3Rpb24gZm9yIHBvc3RlcmlvciAodXNpbmcgaW50ZWdyYXRpb24pCm5vcm1hbGl6ZV9wb3N0ZXJpb3IgPC0gZnVuY3Rpb24ocG9zdGVyaW9yX3ZhbHVlcywgdGhldGEpIHsKICAjIEFwcHJveGltYXRlIHRoZSBhcmVhIHVuZGVyIHRoZSBjdXJ2ZQogIGludGVncmFsX3ZhbHVlIDwtIGludGVncmF0ZShhcHByb3hmdW4odGhldGEsIHBvc3Rlcmlvcl92YWx1ZXMpLCBsb3dlcj0tMSwgdXBwZXI9MSkkdmFsdWUKICAjIE5vcm1hbGl6ZSB0aGUgcG9zdGVyaW9yIGJ5IGRpdmlkaW5nIGJ5IHRoZSBpbnRlZ3JhbCB2YWx1ZSAtIHNob3VsZCBzdW0gdXAgdG8gMS1pc2gKICBub3JtYWxpemVkX3Bvc3RlcmlvciA8LSBwb3N0ZXJpb3JfdmFsdWVzIC8gaW50ZWdyYWxfdmFsdWUKICByZXR1cm4obm9ybWFsaXplZF9wb3N0ZXJpb3IpCn0KYGBgCgpPSywgbm93IGxldCdzIGFwcGx5IHRoZXNlIGZ1bmN0aW9ucyB0b2dldGhlciB0byBnZXQgdGhlIHBvc3RlcmlvcnMgYXNzb2NpYXRlZCB3aXRoIGVhY2ggcHJpb3IuCgoKYGBge3J9CiMgQ29tcHV0ZSBwb3N0ZXJpb3JzIHZhbHVlcyBmb3IgZWFjaCBwcmlvcgoKIyBKZWZmZXJ5J3MKcG9zdF9qZWZmIDwtIHNhcHBseSh0aGV0YSwgZnVuY3Rpb24odGhldGEpIHBvc3Rlcmlvcih0aGV0YSwgbGlrX2RlbnMsIGplZmZfcHJpb3IsIHRoZXRhX2hhdCwgbikpCgojIFNocmlua2FnZS90cmlhbmd1bGFyCnBvc3Rfc2hyaW5rIDwtIHNhcHBseSh0aGV0YSwgZnVuY3Rpb24odGhldGEpIHBvc3Rlcmlvcih0aGV0YSwgbGlrX2RlbnMsIHNocmlua19wcmlvciwgdGhldGFfaGF0LCBuKSkKCiMgZmxhdC91bmlmb3JtL3VuaW5mb3JtYXRpdmUKcG9zdF91bmlmb3JtIDwtIHNhcHBseSh0aGV0YSwgZnVuY3Rpb24odGhldGEpIHBvc3Rlcmlvcih0aGV0YSwgbGlrX2RlbnMsIGZsYXRfcHJpb3IsIHRoZXRhX2hhdCwgbikpCgojIFVkaSdzIGFkZGVkIHByaW9yIQpwb3N0X2luZm9ybSA8LSBzYXBwbHkodGhldGEsIGZ1bmN0aW9uKHRoZXRhKSBwb3N0ZXJpb3IodGhldGEsIGxpa19kZW5zLCBpbmZvcm1hdGl2ZV9wcmlvciwgdGhldGFfaGF0LCBuKSkKCiMgTm9ybWFsaXplIHRoZSBwb3N0ZXJpb3IgdmFsdWVzLgpwb3N0X2plZmZfcHJvcGVyIDwtIG5vcm1hbGl6ZV9wb3N0ZXJpb3IocG9zdF9qZWZmLCB0aGV0YSkKcG9zdF9zaHJpbmtfcHJvcGVyIDwtIG5vcm1hbGl6ZV9wb3N0ZXJpb3IocG9zdF9zaHJpbmssIHRoZXRhKQpwb3N0X3VuaWZvcm1fcHJvcGVyIDwtIG5vcm1hbGl6ZV9wb3N0ZXJpb3IocG9zdF91bmlmb3JtLCB0aGV0YSkKcG9zdF9pbmZvcm1fcHJvcGVyIDwtIG5vcm1hbGl6ZV9wb3N0ZXJpb3IocG9zdF9pbmZvcm0sIHRoZXRhKQoKCgojIFdlIGNhbiBhbHNvIGFkZCB0aGUgbGlrZWxpaG9vZCBkZW5zaXR5IGZ1bmN0aW9uIGFuZCBub3JtYWxpemUgaXQgc28gaXQgY2FuIGJlIGFkZGVkIHRvIHRoZSBwbG90Li4uCmxpa19kZW5zX3Byb3BlciA8LSBub3JtYWxpemVfcG9zdGVyaW9yKGxpa2VsaWhvb2RfZGYkTGlrZWxpaG9vZCwgdGhldGEpCgpgYGAKCgpXZSBjYW4gY2hlY2sgdGhlIHRoZSBpbnRlZ3JhdGlvbiBwYXJ0IHdhcyBkb25lIHdlbGwuIFdlIGFyZSBsb29raW5nIGZvciB0aGUgYXJlYSB0byBiZSAxIG9yIHZlcnkgY2xvc2UuLi4KCmBgYHtyfQppbnRlZ3JhdGUoYXBwcm94ZnVuKHRoZXRhLCBwb3N0X2plZmZfcHJvcGVyKSwgLTEsIDEpICMgbmljZS4uLgoKaW50ZWdyYXRlKGFwcHJveGZ1bih0aGV0YSwgcG9zdF9zaHJpbmtfcHJvcGVyKSwgLTEsIDEpICMgZ3JlYXQuLi4KCmludGVncmF0ZShhcHByb3hmdW4odGhldGEsIHBvc3RfdW5pZm9ybV9wcm9wZXIpLCAtMSwgMSkgIyBhbHJpZ2h0Li4uCgppbnRlZ3JhdGUoYXBwcm94ZnVuKHRoZXRhLCBwb3N0X2luZm9ybV9wcm9wZXIpLCAtMSwgMSkgIyBjb29sLi4uCgppbnRlZ3JhdGUoYXBwcm94ZnVuKHRoZXRhLCBsaWtfZGVuc19wcm9wZXIpLCAtMSwgMSkgIyBnb29kIGpvYi4uLgpgYGAKCgpOb3csIGZvciB0aGUgZnVuIHBhcnQuLi5MZXQncyB0cnkgdG8gcmVwcm9kdWNlIEZpZ3VyZSAzLjIuCgoKIyMgUGxvdHRpbmcgdGhlIFBvc3RlcmlvcnMKCmBgYHtyfQojIENyZWF0ZSBhIGRhdGEgZnJhbWUgdG8gY29udGFpbiBhbGwgdGhlIHBvc3RlcmlvciBpbmZvCnBvc3Rlcmlvcl9kYXQgPC0gZGF0YS5mcmFtZSgKICB0aGV0YSA9IHJlcCh0aGV0YSwgNSksCiAgcG9zdGVyaW9yX3ZhbHVlID0gYyhwb3N0X2plZmZfcHJvcGVyLCBwb3N0X3Nocmlua19wcm9wZXIsIHBvc3RfdW5pZm9ybV9wcm9wZXIsIHBvc3RfaW5mb3JtX3Byb3BlciwgbGlrX2RlbnNfcHJvcGVyKSwKICBwcmlvcl90eXBlID0gZmFjdG9yKHJlcChjKCJKZWZmcmV5J3MiLCAiU2hyaW5rYWdlL1RyaWFuZ3VsYXIiLCAiVW5pZm9ybS9GbGF0IiwgIkluZm9ybWF0aXZlIChVZGkncykiLCAiTGlrZWxpaG9vZCBQREYgKE1MRSkiKSwgZWFjaCA9IGxlbmd0aCh0aGV0YSkpKQopCgoKIyBQbG90IHBvc3RlcmlvciBkaXN0cmlidXRpb25zCnAzIDwtIGdncGxvdChwb3N0ZXJpb3JfZGF0LCBhZXMoeCA9IHRoZXRhLCB5ID0gcm91bmQocG9zdGVyaW9yX3ZhbHVlLzEwMCw1KSwgY29sb3IgPSBwcmlvcl90eXBlLCBsaW5ldHlwZSA9IHByaW9yX3R5cGUpKSArCiAgZ2VvbV9saW5lKHNpemUgPSAxLjIsIGFscGhhPS45KSArCiAgbGFicyh0aXRsZSA9ICJQb3N0ZXJpb3IgRGlzdHJpYnV0aW9ucyB3aXRoIERpZmZlcmVudCBQcmlvcnMiLAogICAgICAgeCA9ICJ0aGV0YSIsCiAgICAgICB5ID0gIlBvc3RlcmlvciBEZW5zaXR5IiwKICAgICAgIGNvbG9yID0gIlByaW9yIFR5cGUiKSArCiAgdGhlbWVfbWluaW1hbCgpICsKICB0aGVtZSgKICAgIHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpLAogICAgbGVnZW5kLnBvc2l0aW9uID0gImJvdHRvbSIKICApK3hsaW0oLTAuMzUsMSkrc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcz1tZXQuYnJld2VyKCJMYWtvdGEiLCA1KSkKCmdncGxvdGx5KHAzKQpgYGAKCgoKCg==