Generating the data for analysis
The first step in exploring genomic prediction is to generate data
where we know the answer so that we can compare our estimate from the
data with the truth. generate_data()
does this by following
these steps.
Generate genotype frequencies at each locus. By default,
generate_data()
generates genotypes at 20 loci, but you can
change that when you call it by changing n_loci_total
in
the call. We generate the genotypes in such a way that they are
correlated with one another.^[Here are the details, if you’re
interested: (a) Generate a sample from a multivariate normal
distribution with a mean vector of zero and a covariance matrix where
all of the variances are 1 and the correlation of each element of the
vector is \(\rho/2\) with the element
just before it and the element just after it. Call the
n_loci
randomly generated numbers logit_p
. (b)
Convert the the logit_p
to frequencies using \(p = \frac{\mbox{exp}(\mbox{logit_p})}{1 +
\mbox{exp}(\mbox{logit_p})}\). (c) Generate a matrix of genotype
frequencies at each locus assuming genotypes are in Hardy-Weinberg at
every locus.
Generate a genotype at random for an individual based on the
genotype frequencies at each locus from #1
Generate a phenotype for this individual.
- Calculate the genotypic mean at each locus from the specified
allelic effect and the genotype at that locus. By default the allelic
effects are 1.0, -1.0, 0.5, -0.5, and 0.25 at loci 1-5 and 0.0 at the
remaining 15 loci. You can change that by changing
effect
when you call generate_data()
. The allelic affect is the
effect of having 0, 1, or 2 copies of the allele, and there is no
dominance.
- Generate a phenotypic contribution at each locus as a random
variable having a normal distribution with the genotypic mean and a
specified standard deviation. By default the standard deviation is 0.2.
You can change that by changing
s_dev
when you call
generate_data()
.
- Sum the phenotypic contribution across all of the loci.
Repeat #2 and #3 until you have the number of individuals in the
sample data set that you want. By default that’s 100, but you can change
that by changing n_indiv
when you call
generate_data
.
generate_data()
returns the results of the simulation as
a data frame with each individual on a row and with the phenotype in the
first column and the genotypes at each locus in the remaining
columns.
NOTE: I’m using set.seed()
to ensure that you get the
same sequence of random numbers that I do if you run this code on your
own. You can delete that line or comment it out if you want to see what
happens with different randomly generated data sets.
library(MASS)
rm(list = ls())
set.seed(12345)
generate_frequencies <- function(n_loci, rho) {
Sigma <- diag(1, n_loci)
Sigma[1,2] <- rho
for (i in 2:(n_loci - 1)) {
Sigma[i, i - 1] <- rho/2
Sigma[i, i + 1] <- rho/2
}
Sigma[n_loci, n_loci - 1] <- rho
logit_p <- mvrnorm(n_loci, rep(0, n_loci), Sigma)
p <- exp(logit_p)/(1 + exp(logit_p))
x <- matrix(nrow = n_loci, ncol = 3)
for (i in 1:n_loci) {
x[i, ] <- c(p[i]^2, 2*p[i]*(1-p[i]), (1-p[i])^2)
}
return(x)
}
generate_genotypes <- function(freqs) {
x <- numeric(nrow(freqs))
n_loci <- nrow(freqs)
for (i in 1:n_loci) {
x[i] <- which(rmultinom(1, 1, freqs[i, ]) == 1) - 1
}
return(x)
}
generate_data <- function(n_indiv = 100,
n_loci_total = 20,
effect = c(1, -1, 0.5, -0.5, 0.25),
s_dev = 0.2)
{
pheno <- numeric(n_indiv)
geno <- matrix(nrow = n_indiv, ncol = n_loci_total)
freqs <- generate_frequencies(n_loci_total, 0.2)
for (i in 1:n_indiv) {
for (j in 1:n_loci_total) {
x <- generate_genotypes(freqs)
}
geno[i, ] <- x
pheno[i] <- 0.0
n_loci_assoc <- length(effect)
for (j in 1:n_loci_assoc) {
pheno[i] <- pheno[i] + rnorm(1, effect[j]*geno[i,j], s_dev)
}
}
dat <- cbind(pheno, geno)
## remove any loci that happen to be monomorphic
##
counts <- apply(dat[, -1], 2, sum)
remove <- (counts == 2*nrow(dat)) | (counts == 0)
dat <- dat[, c(TRUE, !remove)]
colnames(dat) <- c("pheno", paste("locus_", 1:length(counts), sep = ""))
return(as.data.frame(dat))
}
dat <- generate_data()
loci <- colnames(dat)[-1]
n_loci <- length(loci)
Running the analysis
We generated the data assuming that the individuals are all part of
one, very large, well-mixed population. As a result, we don’t need to
worry about relatedness as we did in Lab
13. We’ll use stan_lm()
for the analysis. It does a
simple linear regression of phenotype on genotype, but as you can
probably guess from the “stan” in its name, it uses Stan
as
a backend to give is not only a posterior mean, but also credible
intervals.
Locus-by-locus GWAS
We’ll start with a locus-by-locus GWAS like the one in lab, except
that we’ll use rstanarm
instead of brms
and
we’ll ignore relatedness.
options(tidyverse.quiet = TRUE)
library(tidyverse)
library(rstanarm)
options(mc.cores = parallel::detectCores())
results <- tibble(Locus = NA,
Mean = NA,
`2.5%` = NA,
`97.5%` = NA)
for (locus in 1:n_loci) {
cat("Locus ", locus, "\n", sep = "")
fit <- stan_lm(paste("pheno ~ ", loci[locus], sep=""),
prior = R2(0.5, what = "mean"),
data = dat,
refresh = 0)
tmp <- data.frame(fit)
effect <- tmp[[loci[locus]]]
conf <- quantile(effect, c(0.025, 0.975))
results <- add_row(results,
Locus = locus,
Mean = round(mean(effect), 3),
`2.5%` = round(conf[1], 3),
`97.5%` = round(conf[2], 3))
}
Locus 1
Locus 2
Locus 3
Locus 4
Locus 5
Locus 6
Locus 7
Locus 8
Locus 9
Locus 10
Locus 11
Locus 12
Locus 13
Locus 14
Locus 15
Locus 16
Locus 17
Locus 18
Locus 19
Locus 20
results %>%
filter(!is.na(Mean)) %>%
arrange(desc(abs(Mean)))
While the five loci that we know have an effect came out with the
five largest estimated effects in this analysis, locus 3 has a credible
interval that does not overlap zero, locus 20 is very close to not
overlapping zero, and all of the first ten loci have an estimated effect
at least half as large as locus 5. Based on this analysis, it would be
tempting to conclude that there are seven loci with a noticeable effect
on the trait.
Genomic prediction
Genomic prediction is very similar to what we’ve just seen. We simply
do one multiple regression in which all of the genotypes are included
rather than doing a series of regressions separately for each locus. We
start by constructing the regression_formula
, which looks
pretty strange. We wouldn’t have to do this, but it’s easier than
constructing the multiple regression formula by typing every locus into
the formula.
regression_formula <- paste("pheno ~ ",
paste("locus_", 1:n_loci, sep = "",
collapse = " + "))
regression_formula
[1] "pheno ~ locus_1 + locus_2 + locus_3 + locus_4 + locus_5 + locus_6 + locus_7 + locus_8 + locus_9 + locus_10 + locus_11 + locus_12 + locus_13 + locus_14 + locus_15 + locus_16 + locus_17 + locus_18 + locus_19 + locus_20"
Now we’re ready to run the analysis and display the results. We’re
going to use stan_glm()
with a gaussian()
family instead of stan_lm()
, because we want to use what’s
known as a “shrinkage prior”. That’s a prior with the interesting
property that either a covariate is included in the regression and the
prior is fairly vague or it’s not included and the prior is tightly
constrained around zero. It’s a way of letting the data tell us which
covariates have strong associations and which don’t and simultaneously
limiting the influence of those that don’t have strong associations on
the results. But it does this without forcing us to pick particular
covariates for the analysis.
The particular tool we use is what’s called a “horseshoe prior”. We
only need to tell it one thing: How many coefficients we think might be
important. The data will tell us how many actually are. p0
,
which I set to 10 in this example is merely our best guess before we
start the analysis.
n <- nrow(dat)
D <- ncol(dat) - 1
p0 <- 10
tau0 <- p0/(D - p0) * 1/sqrt(n)
prior_coeff <- hs(global_scale = tau0, slab_scale = 1)
fit <- stan_glm(as.formula(regression_formula),
family = gaussian(),
prior = prior_coeff,
data = dat,
refresh = 0)
fit_df <- as.data.frame(fit)
results_gp <- tibble(Locus = NA,
Mean = NA,
`2.5%` = NA,
`97.5%` = NA)
for (locus in 1:n_loci) {
tmp <- data.frame(fit)
effect <- tmp[[loci[locus]]]
conf <- quantile(effect, c(0.025, 0.975))
results_gp <- add_row(results_gp,
Locus = locus,
Mean = round(mean(effect), 3),
`2.5%` = round(conf[1], 3),
`97.5%` = round(conf[2], 3))
}
results_gp %>%
filter(!is.na(Mean)) %>%
arrange(desc(abs(Mean)))
Notice that with the genomic prediction approach we get the estimated
allelic effects in the right order and roughly right in magnitude. In
addition, all of the other loci have estimated allelic effects close to
zero as they should. This is only one example, and it is dangerous to
extrapolate from one example, but if you’re familiar with multiple
regression and its advantages, you’re probably wondering, “Why didn’t we
just go directly with genomic prediction in the lab exercise?” Well, we
could have, but it’s useful to understand what GWAS is doing first, and
it’s useful to see how to include the effect of relatedness when making
the estimates. In addition, GWAS allows us to identify
loci that may be associated with phenotypic
predictions. This potentially allows us to examine the genetic
architecture of a trait, e.g., the number of loci, distribution of
allelic effects across loci, and interactions among loci. It may also
allow us to identify loci that have an important influence on more than
one trait.
All that being said, in a real GWAS analysis, you would want to
include all of the loci in a multiple regression analysis. The
difference between these results and those of the single locus analysis
arise because I set up the simulated population in such a way that the
genotypes are corrleated across loci.
Comparing one-locus GWAS and genomic predictions
Let’s first look at the locus-by-locus estimates of allelic
effects.
for_plot <- tibble(GWAS = results$Mean,
GP = results_gp$Mean) %>%
filter(!is.na(GWAS))
p <- ggplot(for_plot, aes(x = GWAS, y = GP)) +
geom_point() +
geom_abline(slope = 1, intercept = 0, color = "salmon",
linetype = "dashed") +
theme_bw()
p
ggsave("gwas-vs-gp.eps")
Saving 7.29 x 4.51 in image

They are broadly similar, but there are also clearly some
differences. Now let’s see how well we can predict the phenotypes.
predictions <- tibble(Observed = NA,
Model = NA,
Predicted = NA,
Error = NA)
for (i in 1:nrow(dat)) {
predicted <-0.0
for (j in 1:n_loci) {
predicted <- predicted + results$Mean[i]*dat[i, j+1]
}
predictions <- add_row(predictions,
Observed = dat$pheno[i],
Model = "GWAS",
Predicted = predicted,
Error = Predicted - Observed)
predicted <-0.0
for (j in 1:n_loci) {
predicted <- predicted + results_gp$Mean[i]*dat[i, j+1]
}
predictions <- add_row(predictions,
Observed = dat$pheno[i],
Model = "GP",
Predicted = predicted,
Error = Predicted - Observed)
}
predictions <- filter(predictions, !is.na(Predicted))
p <- ggplot(predictions, aes(x = Observed, y = Predicted)) +
geom_point() +
geom_abline(slope = 1, intercept = 0, color = "salmon",
linetype = "dashed") +
facet_wrap(~ Model) +
theme_bw()
p
ggsave("gwas-obs-vs-predicted.eps")
Saving 7.29 x 4.51 in image

cat("Mean squared error:\n",
" GWAS: ", round(sum(subset(predictions, Model == "GWAS")$Error^2),
3)/nrow(dat), "\n",
" GP: ", round(sum(subset(predictions, Model == "GP")$Error^2),
3)/nrow(dat), "\n",
sep = "")
Mean squared error:
GWAS: 14.21563
GP: 11.06387
Again, this is only one example, but you can see that the genomic
prediction (multiple regression) approach gives us a smaller mean error
than the single locus GWAS approach..
LS0tCnRpdGxlOiAiRXhwbG9yaW5nIGdlbm9taWMgcHJlZGljdGlvbiIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOgogICAgdG9jOiB5ZXMKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgY3NzOiAiUi1ub3RlYm9vay5jc3MiCi0tLQoKIyBPdmVydmlldwoKVGhpcyBgUmAgbm90ZWJvb2sgbWF5IGJlIGEgc2ltcGxlciB3YXkgdG8gZm9sbG93IGFsb25nIHdpdGggdGhlIGxlY3R1cmUgbm90ZXMgdGhhdCBpbnRyb2R1Y2UgdGhlIGlkZWEgb2YgZ2Vub21pYyBwcmVkaWN0aW9uIChbSFRNTF0oaHR0cDovL2Rhcndpbi5lZWIudWNvbm4uZWR1L2VlYjM0OC1ub3Rlcy9nZW5vbWljLXByZWRpY3Rpb24uaHRtbCksIFtQREZdKGh0dHA6Ly9kYXJ3aW4uZWViLnVjb25uLmVkdS9lZWIzNDgtbm90ZXMvZ2Vub21pYy1wcmVkaWN0aW9uLnBkZikpLiBNdWNoIG9mIHRoZSBjb2RlIGlzIHRha2VuIGRpcmVjdGx5IGZyb20gW2h0dHA6Ly9kYXJ3aW4uZWViLnVjb25uLmVkdS9lZWIzNDgtcmVzb3VyY2VzL2dlbm9taWMtcHJlZGljdGlvbi5SXShodHRwOi8vZGFyd2luLmVlYi51Y29ubi5lZHUvZWViMzQ4LXJlc291cmNlcy9nZW5vbWljLXByZWRpY3Rpb24uUikgd2l0aCBzb21lIG1pbm9yIG1vZGlmaWNhdGlvbnMgdG8gcmVmbGVjdCB0aGluZ3MgSSd2ZSBsZWFybmVkIGFib3V0IGNvZGluZyBpbiBgUmAgaW4gdGhlIGxhc3QgdHdvIGFuZCBhIGhhbGYgeWVhcnMuIFRoZSBmaW5hbCBwYXJ0IChbQ29tcGFyaW5nIG9uZS1sb2N1cyBHV0FTIGFuZCBnZW5vbWljIHByZWRpY3Rpb25zXSgjY29tcGFyaW5nLW9uZS1sb2N1cy1nd2FzLWFuZC1nZW5vbWljLXByZWRpY3Rpb25zKSkgaW5jbHVkZXMgc29tZSBuZXcgY29kZS4KCiMgR2VuZXJhdGluZyB0aGUgZGF0YSBmb3IgYW5hbHlzaXMKClRoZSBmaXJzdCBzdGVwIGluIGV4cGxvcmluZyBnZW5vbWljIHByZWRpY3Rpb24gaXMgdG8gZ2VuZXJhdGUgZGF0YSB3aGVyZSB3ZSBrbm93IHRoZSBhbnN3ZXIgc28gdGhhdCB3ZSBjYW4gY29tcGFyZSBvdXIgZXN0aW1hdGUgZnJvbSB0aGUgZGF0YSB3aXRoIHRoZSB0cnV0aC4gYGdlbmVyYXRlX2RhdGEoKWAgZG9lcyB0aGlzIGJ5IGZvbGxvd2luZyB0aGVzZSBzdGVwcy4KCjEuIEdlbmVyYXRlIGdlbm90eXBlIGZyZXF1ZW5jaWVzIGF0IGVhY2ggbG9jdXMuIEJ5IGRlZmF1bHQsIGBnZW5lcmF0ZV9kYXRhKClgIGdlbmVyYXRlcyBnZW5vdHlwZXMgYXQgMjAgbG9jaSwgYnV0IHlvdSBjYW4gY2hhbmdlIHRoYXQgd2hlbiB5b3UgY2FsbCBpdCBieSBjaGFuZ2luZyBgbl9sb2NpX3RvdGFsYCBpbiB0aGUgY2FsbC4gV2UgZ2VuZXJhdGUgdGhlIGdlbm90eXBlcyBpbiBzdWNoIGEgd2F5IHRoYXQgdGhleSBhcmUgY29ycmVsYXRlZCB3aXRoIG9uZSBhbm90aGVyLl5bSGVyZSBhcmUgdGhlIGRldGFpbHMsIGlmIHlvdSdyZSBpbnRlcmVzdGVkOiAoYSkgR2VuZXJhdGUgYSBzYW1wbGUgZnJvbSBhIG11bHRpdmFyaWF0ZSBub3JtYWwgZGlzdHJpYnV0aW9uIHdpdGggYSBtZWFuIHZlY3RvciBvZiB6ZXJvIGFuZCBhIGNvdmFyaWFuY2UgbWF0cml4IHdoZXJlIGFsbCBvZiB0aGUgdmFyaWFuY2VzIGFyZSAxIGFuZCB0aGUgY29ycmVsYXRpb24gb2YgZWFjaCBlbGVtZW50IG9mIHRoZSB2ZWN0b3IgaXMgJFxyaG8vMiQgd2l0aCB0aGUgZWxlbWVudCBqdXN0IGJlZm9yZSBpdCBhbmQgdGhlIGVsZW1lbnQganVzdCBhZnRlciBpdC4gQ2FsbCB0aGUgYG5fbG9jaWAgcmFuZG9tbHkgZ2VuZXJhdGVkIG51bWJlcnMgYGxvZ2l0X3BgLiAoYikgQ29udmVydCB0aGUgdGhlIGBsb2dpdF9wYCB0byBmcmVxdWVuY2llcyB1c2luZyAkcCA9IFxmcmFje1xtYm94e2V4cH0oXG1ib3h7bG9naXRfcH0pfXsxICsgXG1ib3h7ZXhwfShcbWJveHtsb2dpdF9wfSl9JC4gKGMpIEdlbmVyYXRlIGEgbWF0cml4IG9mIGdlbm90eXBlIGZyZXF1ZW5jaWVzIGF0IGVhY2ggbG9jdXMgYXNzdW1pbmcgZ2Vub3R5cGVzIGFyZSBpbiBIYXJkeS1XZWluYmVyZyBhdCBldmVyeSBsb2N1cy4gCjIuIEdlbmVyYXRlIGEgZ2Vub3R5cGUgYXQgcmFuZG9tIGZvciBhbiBpbmRpdmlkdWFsIGJhc2VkIG9uIHRoZSBnZW5vdHlwZSBmcmVxdWVuY2llcyBhdCBlYWNoIGxvY3VzIGZyb20gIzEKCjMuIEdlbmVyYXRlIGEgcGhlbm90eXBlIGZvciB0aGlzIGluZGl2aWR1YWwuCgogICAgYS4gQ2FsY3VsYXRlIHRoZSBnZW5vdHlwaWMgbWVhbiBhdCBlYWNoIGxvY3VzIGZyb20gdGhlIHNwZWNpZmllZCBhbGxlbGljIGVmZmVjdCBhbmQgdGhlIGdlbm90eXBlIGF0IHRoYXQgbG9jdXMuIEJ5IGRlZmF1bHQgdGhlIGFsbGVsaWMgZWZmZWN0cyBhcmUgMS4wLCAtMS4wLCAwLjUsIC0wLjUsIGFuZCAwLjI1IGF0IGxvY2kgMS01IGFuZCAwLjAgYXQgdGhlIHJlbWFpbmluZyAxNSBsb2NpLiBZb3UgY2FuIGNoYW5nZSB0aGF0IGJ5IGNoYW5naW5nIGBlZmZlY3RgIHdoZW4geW91IGNhbGwgYGdlbmVyYXRlX2RhdGEoKWAuIFRoZSBhbGxlbGljIGFmZmVjdCBpcyB0aGUgZWZmZWN0IG9mIGhhdmluZyAwLCAxLCBvciAyIGNvcGllcyBvZiB0aGUgYWxsZWxlLCBhbmQgdGhlcmUgaXMgbm8gZG9taW5hbmNlLgogICAgYi4gR2VuZXJhdGUgYSBwaGVub3R5cGljIGNvbnRyaWJ1dGlvbiBhdCBlYWNoIGxvY3VzIGFzIGEgcmFuZG9tIHZhcmlhYmxlIGhhdmluZyBhIG5vcm1hbCBkaXN0cmlidXRpb24gd2l0aCB0aGUgZ2Vub3R5cGljIG1lYW4gYW5kIGEgc3BlY2lmaWVkIHN0YW5kYXJkIGRldmlhdGlvbi4gQnkgZGVmYXVsdCB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIGlzIDAuMi4gWW91IGNhbiBjaGFuZ2UgdGhhdCBieSBjaGFuZ2luZyBgc19kZXZgIHdoZW4geW91IGNhbGwgYGdlbmVyYXRlX2RhdGEoKWAuCiAgICBjLiBTdW0gdGhlIHBoZW5vdHlwaWMgY29udHJpYnV0aW9uIGFjcm9zcyBhbGwgb2YgdGhlIGxvY2kuXltTaW5jZSB3ZSdyZSBhc3N1bWluZyB0aGF0IG9ubHkgbG9jaSAxLTUgaW5mbHVlbmNlIHRoZSBwaGVub3R5cGUsIHdlIG9ubHkgZG8gdGhpcyBzdW0gYWNyb3NzIGxvY2kgMS01Ll0KICAKNC4gUmVwZWF0ICMyIGFuZCAjMyB1bnRpbCB5b3UgaGF2ZSB0aGUgbnVtYmVyIG9mIGluZGl2aWR1YWxzIGluIHRoZSBzYW1wbGUgZGF0YSBzZXQgdGhhdCB5b3Ugd2FudC4gQnkgZGVmYXVsdCB0aGF0J3MgMTAwLCBidXQgeW91IGNhbiBjaGFuZ2UgdGhhdCBieSBjaGFuZ2luZyBgbl9pbmRpdmAgd2hlbiB5b3UgY2FsbCBgZ2VuZXJhdGVfZGF0YWAuCgpgZ2VuZXJhdGVfZGF0YSgpYCByZXR1cm5zIHRoZSByZXN1bHRzIG9mIHRoZSBzaW11bGF0aW9uIGFzIGEgZGF0YSBmcmFtZSB3aXRoIGVhY2ggaW5kaXZpZHVhbCBvbiBhIHJvdyBhbmQgd2l0aCB0aGUgcGhlbm90eXBlIGluIHRoZSBmaXJzdCBjb2x1bW4gYW5kIHRoZSBnZW5vdHlwZXMgYXQgZWFjaCBsb2N1cyBpbiB0aGUgcmVtYWluaW5nIGNvbHVtbnMuCgpOT1RFOiBJJ20gdXNpbmcgYHNldC5zZWVkKClgIHRvIGVuc3VyZSB0aGF0IHlvdSBnZXQgdGhlIHNhbWUgc2VxdWVuY2Ugb2YgcmFuZG9tIG51bWJlcnMgdGhhdCBJIGRvIGlmIHlvdSBydW4gdGhpcyBjb2RlIG9uIHlvdXIgb3duLiBZb3UgY2FuIGRlbGV0ZSB0aGF0IGxpbmUgb3IgY29tbWVudCBpdCBvdXQgaWYgeW91IHdhbnQgdG8gc2VlIHdoYXQgaGFwcGVucyB3aXRoIGRpZmZlcmVudCByYW5kb21seSBnZW5lcmF0ZWQgZGF0YSBzZXRzLgoKYGBge3IgbWVzc2FnZSA9IEZBTFNFfQpsaWJyYXJ5KE1BU1MpCgpybShsaXN0ID0gbHMoKSkKCnNldC5zZWVkKDEyMzQ1KQoKZ2VuZXJhdGVfZnJlcXVlbmNpZXMgPC0gZnVuY3Rpb24obl9sb2NpLCByaG8pIHsKICBTaWdtYSA8LSBkaWFnKDEsIG5fbG9jaSkKICBTaWdtYVsxLDJdIDwtIHJobwogIGZvciAoaSBpbiAyOihuX2xvY2kgLSAxKSkgewogICAgU2lnbWFbaSwgaSAtIDFdIDwtIHJoby8yCiAgICBTaWdtYVtpLCBpICsgMV0gPC0gcmhvLzIKICB9CiAgU2lnbWFbbl9sb2NpLCBuX2xvY2kgLSAxXSA8LSByaG8KICBsb2dpdF9wIDwtIG12cm5vcm0obl9sb2NpLCByZXAoMCwgbl9sb2NpKSwgU2lnbWEpCiAgcCA8LSBleHAobG9naXRfcCkvKDEgKyBleHAobG9naXRfcCkpCiAgeCA8LSBtYXRyaXgobnJvdyA9IG5fbG9jaSwgbmNvbCA9IDMpCiAgZm9yIChpIGluIDE6bl9sb2NpKSB7CiAgICB4W2ksIF0gPC0gYyhwW2ldXjIsIDIqcFtpXSooMS1wW2ldKSwgKDEtcFtpXSleMikKICB9CiAgcmV0dXJuKHgpCn0KCmdlbmVyYXRlX2dlbm90eXBlcyA8LSBmdW5jdGlvbihmcmVxcykgewogIHggPC0gbnVtZXJpYyhucm93KGZyZXFzKSkKICBuX2xvY2kgPC0gbnJvdyhmcmVxcykKICBmb3IgKGkgaW4gMTpuX2xvY2kpIHsKICAgIHhbaV0gPC0gd2hpY2gocm11bHRpbm9tKDEsIDEsIGZyZXFzW2ksIF0pID09IDEpIC0gMQogIH0KICByZXR1cm4oeCkKfQoKZ2VuZXJhdGVfZGF0YSA8LSBmdW5jdGlvbihuX2luZGl2ID0gMTAwLAogICAgICAgICAgICAgICAgICAgICAgICAgIG5fbG9jaV90b3RhbCA9IDIwLAogICAgICAgICAgICAgICAgICAgICAgICAgIGVmZmVjdCA9IGMoMSwgLTEsIDAuNSwgLTAuNSwgMC4yNSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgc19kZXYgPSAwLjIpCnsKICBwaGVubyA8LSBudW1lcmljKG5faW5kaXYpCiAgZ2VubyA8LSBtYXRyaXgobnJvdyA9IG5faW5kaXYsIG5jb2wgPSBuX2xvY2lfdG90YWwpCiAgZnJlcXMgPC0gZ2VuZXJhdGVfZnJlcXVlbmNpZXMobl9sb2NpX3RvdGFsLCAwLjIpCiAgZm9yIChpIGluIDE6bl9pbmRpdikgewogICAgZm9yIChqIGluIDE6bl9sb2NpX3RvdGFsKSB7CiAgICAgIHggPC0gZ2VuZXJhdGVfZ2Vub3R5cGVzKGZyZXFzKQogICAgfQogICAgZ2Vub1tpLCBdIDwtIHgKICAgIHBoZW5vW2ldIDwtIDAuMAogICAgbl9sb2NpX2Fzc29jIDwtIGxlbmd0aChlZmZlY3QpCiAgICBmb3IgKGogaW4gMTpuX2xvY2lfYXNzb2MpIHsKICAgICAgcGhlbm9baV0gPC0gcGhlbm9baV0gKyBybm9ybSgxLCBlZmZlY3Rbal0qZ2Vub1tpLGpdLCBzX2RldikKICAgIH0KICB9CiAgZGF0IDwtIGNiaW5kKHBoZW5vLCBnZW5vKQogICMjIHJlbW92ZSBhbnkgbG9jaSB0aGF0IGhhcHBlbiB0byBiZSBtb25vbW9ycGhpYwogICMjCiAgY291bnRzIDwtIGFwcGx5KGRhdFssIC0xXSwgMiwgc3VtKQogIHJlbW92ZSA8LSAoY291bnRzID09IDIqbnJvdyhkYXQpKSB8IChjb3VudHMgPT0gMCkKICBkYXQgPC0gZGF0WywgYyhUUlVFLCAhcmVtb3ZlKV0KICBjb2xuYW1lcyhkYXQpIDwtIGMoInBoZW5vIiwgcGFzdGUoImxvY3VzXyIsIDE6bGVuZ3RoKGNvdW50cyksIHNlcCA9ICIiKSkKICByZXR1cm4oYXMuZGF0YS5mcmFtZShkYXQpKQp9CgpkYXQgPC0gZ2VuZXJhdGVfZGF0YSgpCmxvY2kgPC0gY29sbmFtZXMoZGF0KVstMV0Kbl9sb2NpIDwtIGxlbmd0aChsb2NpKQpgYGAKCiMgUnVubmluZyB0aGUgYW5hbHlzaXMKCldlIGdlbmVyYXRlZCB0aGUgZGF0YSBhc3N1bWluZyB0aGF0IHRoZSBpbmRpdmlkdWFscyBhcmUgYWxsIHBhcnQgb2Ygb25lLCB2ZXJ5IGxhcmdlLCB3ZWxsLW1peGVkIHBvcHVsYXRpb24uIEFzIGEgcmVzdWx0LCB3ZSBkb24ndCBuZWVkIHRvIHdvcnJ5IGFib3V0IHJlbGF0ZWRuZXNzIGFzIHdlIGRpZCBpbiBbTGFiIDEzXShodHRwOi8vZGFyd2luLmVlYi51Y29ubi5lZHUvZWViMzQ4LXJlc291cmNlcy9MYWIxMy5uYi5odG1sKS4gV2UnbGwgdXNlIGBzdGFuX2xtKClgIGZvciB0aGUgYW5hbHlzaXMuIEl0IGRvZXMgYSBzaW1wbGUgbGluZWFyIHJlZ3Jlc3Npb24gb2YgcGhlbm90eXBlIG9uIGdlbm90eXBlLCBidXQgYXMgeW91IGNhbiBwcm9iYWJseSBndWVzcyBmcm9tIHRoZSAic3RhbiIgaW4gaXRzIG5hbWUsIGl0IHVzZXMgYFN0YW5gIGFzIGEgYmFja2VuZCB0byBnaXZlIGlzIG5vdCBvbmx5IGEgcG9zdGVyaW9yIG1lYW4sIGJ1dCBhbHNvIGNyZWRpYmxlIGludGVydmFscy4KCiMjIExvY3VzLWJ5LWxvY3VzIEdXQVMKCldlJ2xsIHN0YXJ0IHdpdGggYSBsb2N1cy1ieS1sb2N1cyBHV0FTIGxpa2UgdGhlIG9uZSBpbiBsYWIsIGV4Y2VwdCB0aGF0IHdlJ2xsIHVzZSBgcnN0YW5hcm1gIGluc3RlYWQgb2YgYGJybXNgIGFuZCB3ZSdsbCBpZ25vcmUgcmVsYXRlZG5lc3MuXltTaW5jZSB0aGUgaW5kaXZpZHVhbHMgd2VyZSBnZW5lcmF0ZWQgcmFuZG9tbHksIHRoZXkgYXJlIGVxdWFsbHkgdW5yZWxhdGVkIHRvIG9uZSBhbm90aGVyLl0gCgpgYGB7ciBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0Kb3B0aW9ucyh0aWR5dmVyc2UucXVpZXQgPSBUUlVFKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShyc3RhbmFybSkKCm9wdGlvbnMobWMuY29yZXMgPSBwYXJhbGxlbDo6ZGV0ZWN0Q29yZXMoKSkKCnJlc3VsdHMgPC0gdGliYmxlKExvY3VzID0gTkEsCiAgICAgICAgICAgICAgICAgIE1lYW4gPSBOQSwKICAgICAgICAgICAgICAgICAgYDIuNSVgID0gTkEsCiAgICAgICAgICAgICAgICAgIGA5Ny41JWAgPSBOQSkKZm9yIChsb2N1cyBpbiAxOm5fbG9jaSkgewogIGNhdCgiTG9jdXMgIiwgbG9jdXMsICJcbiIsIHNlcCA9ICIiKQogIGZpdCA8LSBzdGFuX2xtKHBhc3RlKCJwaGVubyB+ICIsIGxvY2lbbG9jdXNdLCBzZXA9IiIpLAogICAgICAgICAgICAgICAgIHByaW9yID0gUjIoMC41LCB3aGF0ID0gIm1lYW4iKSwKICAgICAgICAgICAgICAgICBkYXRhID0gZGF0LAogICAgICAgICAgICAgICAgIHJlZnJlc2ggPSAwKQogIHRtcCA8LSBkYXRhLmZyYW1lKGZpdCkKICBlZmZlY3QgPC0gdG1wW1tsb2NpW2xvY3VzXV1dCiAgY29uZiA8LSBxdWFudGlsZShlZmZlY3QsIGMoMC4wMjUsIDAuOTc1KSkKICByZXN1bHRzIDwtIGFkZF9yb3cocmVzdWx0cywKICAgICAgICAgICAgICAgICAgICAgTG9jdXMgPSBsb2N1cywKICAgICAgICAgICAgICAgICAgICAgTWVhbiA9IHJvdW5kKG1lYW4oZWZmZWN0KSwgMyksCiAgICAgICAgICAgICAgICAgICAgIGAyLjUlYCA9IHJvdW5kKGNvbmZbMV0sIDMpLAogICAgICAgICAgICAgICAgICAgICBgOTcuNSVgID0gcm91bmQoY29uZlsyXSwgMykpCn0KcmVzdWx0cyAlPiUKICBmaWx0ZXIoIWlzLm5hKE1lYW4pKSAlPiUKICBhcnJhbmdlKGRlc2MoYWJzKE1lYW4pKSkKYGBgCgpXaGlsZSB0aGUgZml2ZSBsb2NpIHRoYXQgd2Uga25vdyBoYXZlIGFuIGVmZmVjdCBjYW1lIG91dCB3aXRoIHRoZSBmaXZlIGxhcmdlc3QgZXN0aW1hdGVkIGVmZmVjdHMgaW4gdGhpcyBhbmFseXNpcywgbG9jdXMgMyBoYXMgYSBjcmVkaWJsZSBpbnRlcnZhbCB0aGF0IGRvZXMgbm90IG92ZXJsYXAgemVybywgbG9jdXMgMjAgaXMgdmVyeSBjbG9zZSB0byBub3Qgb3ZlcmxhcHBpbmcgemVybywgYW5kIGFsbCBvZiB0aGUgZmlyc3QgdGVuIGxvY2kgaGF2ZSBhbiBlc3RpbWF0ZWQgZWZmZWN0IGF0IGxlYXN0IGhhbGYgYXMgbGFyZ2UgYXMgbG9jdXMgNS4gQmFzZWQgb24gdGhpcyBhbmFseXNpcywgaXQgd291bGQgYmUgdGVtcHRpbmcgdG8gY29uY2x1ZGUgdGhhdCB0aGVyZSBhcmUgc2V2ZW4gbG9jaSB3aXRoIGEgbm90aWNlYWJsZSBlZmZlY3Qgb24gdGhlIHRyYWl0LgoKIyMgR2Vub21pYyBwcmVkaWN0aW9uCgpHZW5vbWljIHByZWRpY3Rpb24gaXMgdmVyeSBzaW1pbGFyIHRvIHdoYXQgd2UndmUganVzdCBzZWVuLiBXZSBzaW1wbHkgZG8gb25lIG11bHRpcGxlIHJlZ3Jlc3Npb24gaW4gd2hpY2ggYWxsIG9mIHRoZSBnZW5vdHlwZXMgYXJlIGluY2x1ZGVkIHJhdGhlciB0aGFuIGRvaW5nIGEgc2VyaWVzIG9mIHJlZ3Jlc3Npb25zIHNlcGFyYXRlbHkgZm9yIGVhY2ggbG9jdXMuIFdlIHN0YXJ0IGJ5IGNvbnN0cnVjdGluZyB0aGUgYHJlZ3Jlc3Npb25fZm9ybXVsYWAsIHdoaWNoIGxvb2tzIHByZXR0eSBzdHJhbmdlLiBXZSB3b3VsZG4ndCBoYXZlIHRvIGRvIHRoaXMsIGJ1dCBpdCdzIGVhc2llciB0aGFuIGNvbnN0cnVjdGluZyB0aGUgbXVsdGlwbGUgcmVncmVzc2lvbiBmb3JtdWxhIGJ5IHR5cGluZyBldmVyeSBsb2N1cyBpbnRvIHRoZSBmb3JtdWxhLgoKYGBge3J9CnJlZ3Jlc3Npb25fZm9ybXVsYSA8LSBwYXN0ZSgicGhlbm8gfiAiLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBhc3RlKCJsb2N1c18iLCAxOm5fbG9jaSwgc2VwID0gIiIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb2xsYXBzZSA9ICIgKyAiKSkKcmVncmVzc2lvbl9mb3JtdWxhCmBgYApOb3cgd2UncmUgcmVhZHkgdG8gcnVuIHRoZSBhbmFseXNpcyBhbmQgZGlzcGxheSB0aGUgcmVzdWx0cy4gV2UncmUgZ29pbmcgdG8gdXNlIGBzdGFuX2dsbSgpYCB3aXRoIGEgYGdhdXNzaWFuKClgIGZhbWlseSBpbnN0ZWFkIG9mIGBzdGFuX2xtKClgLCBiZWNhdXNlIHdlIHdhbnQgdG8gdXNlIHdoYXQncyBrbm93biBhcyBhICJzaHJpbmthZ2UgcHJpb3IiLiBUaGF0J3MgYSBwcmlvciB3aXRoIHRoZSBpbnRlcmVzdGluZyBwcm9wZXJ0eSB0aGF0IGVpdGhlciBhIGNvdmFyaWF0ZSBpcyBpbmNsdWRlZCBpbiB0aGUgcmVncmVzc2lvbiBhbmQgdGhlIHByaW9yIGlzIGZhaXJseSB2YWd1ZSBvciBpdCdzIG5vdCBpbmNsdWRlZCBhbmQgdGhlIHByaW9yIGlzIHRpZ2h0bHkgY29uc3RyYWluZWQgYXJvdW5kIHplcm8uIEl0J3MgYSB3YXkgb2YgbGV0dGluZyB0aGUgZGF0YSB0ZWxsIHVzIHdoaWNoIGNvdmFyaWF0ZXMgaGF2ZSBzdHJvbmcgYXNzb2NpYXRpb25zIGFuZCB3aGljaCBkb24ndCBhbmQgc2ltdWx0YW5lb3VzbHkgbGltaXRpbmcgdGhlIGluZmx1ZW5jZSBvZiB0aG9zZSB0aGF0IGRvbid0IGhhdmUgc3Ryb25nIGFzc29jaWF0aW9ucyBvbiB0aGUgcmVzdWx0cy4gQnV0IGl0IGRvZXMgdGhpcyB3aXRob3V0IGZvcmNpbmcgdXMgdG8gcGljayBwYXJ0aWN1bGFyIGNvdmFyaWF0ZXMgZm9yIHRoZSBhbmFseXNpcy4KClRoZSBwYXJ0aWN1bGFyIHRvb2wgd2UgdXNlIGlzIHdoYXQncyBjYWxsZWQgYSAiaG9yc2VzaG9lIHByaW9yIi4gV2Ugb25seSBuZWVkIHRvIHRlbGwgaXQgb25lIHRoaW5nOiBIb3cgbWFueSBjb2VmZmljaWVudHMgd2UgdGhpbmsgbWlnaHQgYmUgaW1wb3J0YW50LiBUaGUgZGF0YSB3aWxsIHRlbGwgdXMgaG93IG1hbnkgYWN0dWFsbHkgYXJlLiBgcDBgLCB3aGljaCBJIHNldCB0byAxMCBpbiB0aGlzIGV4YW1wbGUgaXMgbWVyZWx5IG91ciBiZXN0IGd1ZXNzIGJlZm9yZSB3ZSBzdGFydCB0aGUgYW5hbHlzaXMuCgpgYGB7cn0KbiA8LSBucm93KGRhdCkKRCA8LSBuY29sKGRhdCkgLSAxCnAwIDwtIDEwCnRhdTAgPC0gcDAvKEQgLSBwMCkgKiAxL3NxcnQobikKcHJpb3JfY29lZmYgPC0gaHMoZ2xvYmFsX3NjYWxlID0gdGF1MCwgc2xhYl9zY2FsZSA9IDEpCgpmaXQgPC0gc3Rhbl9nbG0oYXMuZm9ybXVsYShyZWdyZXNzaW9uX2Zvcm11bGEpLAogICAgICAgICAgICAgICAgZmFtaWx5ID0gZ2F1c3NpYW4oKSwKICAgICAgICAgICAgICAgIHByaW9yID0gcHJpb3JfY29lZmYsCiAgICAgICAgICAgICAgICBkYXRhID0gZGF0LAogICAgICAgICAgICAgICAgcmVmcmVzaCA9IDApCmZpdF9kZiA8LSBhcy5kYXRhLmZyYW1lKGZpdCkKCnJlc3VsdHNfZ3AgPC0gdGliYmxlKExvY3VzID0gTkEsCiAgICAgICAgICAgICAgICAgICAgIE1lYW4gPSBOQSwKICAgICAgICAgICAgICAgICAgICAgYDIuNSVgID0gTkEsCiAgICAgICAgICAgICAgICAgICAgIGA5Ny41JWAgPSBOQSkKZm9yIChsb2N1cyBpbiAxOm5fbG9jaSkgewogIHRtcCA8LSBkYXRhLmZyYW1lKGZpdCkKICBlZmZlY3QgPC0gdG1wW1tsb2NpW2xvY3VzXV1dCiAgY29uZiA8LSBxdWFudGlsZShlZmZlY3QsIGMoMC4wMjUsIDAuOTc1KSkKICByZXN1bHRzX2dwIDwtIGFkZF9yb3cocmVzdWx0c19ncCwKICAgICAgICAgICAgICAgICAgICAgICAgTG9jdXMgPSBsb2N1cywKICAgICAgICAgICAgICAgICAgICAgICAgTWVhbiA9IHJvdW5kKG1lYW4oZWZmZWN0KSwgMyksCiAgICAgICAgICAgICAgICAgICAgICAgYDIuNSVgID0gcm91bmQoY29uZlsxXSwgMyksCiAgICAgICAgICAgICAgICAgICAgICAgYDk3LjUlYCA9IHJvdW5kKGNvbmZbMl0sIDMpKQp9CnJlc3VsdHNfZ3AgJT4lCiAgZmlsdGVyKCFpcy5uYShNZWFuKSkgJT4lCiAgYXJyYW5nZShkZXNjKGFicyhNZWFuKSkpCmBgYAoKTm90aWNlIHRoYXQgd2l0aCB0aGUgZ2Vub21pYyBwcmVkaWN0aW9uIGFwcHJvYWNoIHdlIGdldCB0aGUgZXN0aW1hdGVkIGFsbGVsaWMgZWZmZWN0cyBpbiB0aGUgcmlnaHQgb3JkZXIgYW5kIHJvdWdobHkgcmlnaHQgaW4gbWFnbml0dWRlLiBJbiBhZGRpdGlvbiwgYWxsIG9mIHRoZSBvdGhlciBsb2NpIGhhdmUgZXN0aW1hdGVkIGFsbGVsaWMgZWZmZWN0cyBjbG9zZSB0byB6ZXJvIGFzIHRoZXkgc2hvdWxkLiBUaGlzIGlzIG9ubHkgb25lIGV4YW1wbGUsIGFuZCBpdCBpcyBkYW5nZXJvdXMgdG8gZXh0cmFwb2xhdGUgZnJvbSBvbmUgZXhhbXBsZSwgYnV0IGlmIHlvdSdyZSBmYW1pbGlhciB3aXRoIG11bHRpcGxlIHJlZ3Jlc3Npb24gYW5kIGl0cyBhZHZhbnRhZ2VzLCB5b3UncmUgcHJvYmFibHkgd29uZGVyaW5nLCAiV2h5IGRpZG4ndCB3ZSBqdXN0IGdvIGRpcmVjdGx5IHdpdGggZ2Vub21pYyBwcmVkaWN0aW9uIGluIHRoZSBsYWIgZXhlcmNpc2U/IiBXZWxsLCB3ZSBjb3VsZCBoYXZlLCBidXQgaXQncyB1c2VmdWwgdG8gdW5kZXJzdGFuZCB3aGF0IEdXQVMgaXMgZG9pbmcgZmlyc3QsIGFuZCBpdCdzIHVzZWZ1bCB0byBzZWUgaG93IHRvIGluY2x1ZGUgdGhlIGVmZmVjdCBvZiByZWxhdGVkbmVzcyB3aGVuIG1ha2luZyB0aGUgZXN0aW1hdGVzLl5bVGhhdCdzIHdoeSB3ZSB1c2VkIGBicm1zYCBpbnN0ZWFkIG9mIGByc3RhbmFybWAgaW4gbGFiLiBgcnN0YW5hcm1gIGRvZXNuJ3QgaGF2ZSBhIHdheSB0byBpbmNsdWRlIHJlbGF0ZWRuZXNzLl0gSW4gYWRkaXRpb24sIEdXQVMgYWxsb3dzIHVzIHRvIGlkZW50aWZ5IGxvY2kgdGhhdCAqKiptYXkqKiogYmUgYXNzb2NpYXRlZCB3aXRoIHBoZW5vdHlwaWMgcHJlZGljdGlvbnMuIFRoaXMgcG90ZW50aWFsbHkgYWxsb3dzIHVzIHRvIGV4YW1pbmUgdGhlIGdlbmV0aWMgYXJjaGl0ZWN0dXJlIG9mIGEgdHJhaXQsIGUuZy4sIHRoZSBudW1iZXIgb2YgbG9jaSwgZGlzdHJpYnV0aW9uIG9mIGFsbGVsaWMgZWZmZWN0cyBhY3Jvc3MgbG9jaSwgYW5kIGludGVyYWN0aW9ucyBhbW9uZyBsb2NpLiBJdCBtYXkgYWxzbyBhbGxvdyB1cyB0byBpZGVudGlmeSBsb2NpIHRoYXQgaGF2ZSBhbiBpbXBvcnRhbnQgaW5mbHVlbmNlIG9uIG1vcmUgdGhhbiBvbmUgdHJhaXQuIAoKQWxsIHRoYXQgYmVpbmcgc2FpZCwgaW4gYSByZWFsIEdXQVMgYW5hbHlzaXMsIHlvdSB3b3VsZCB3YW50IHRvIGluY2x1ZGUgYWxsIG9mIHRoZSBsb2NpIGluIGEgbXVsdGlwbGUgcmVncmVzc2lvbiBhbmFseXNpcy4gVGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGVzZSByZXN1bHRzIGFuZCB0aG9zZSBvZiB0aGUgc2luZ2xlIGxvY3VzIGFuYWx5c2lzIGFyaXNlIGJlY2F1c2UgSSBzZXQgdXAgdGhlIHNpbXVsYXRlZCBwb3B1bGF0aW9uIGluIHN1Y2ggYSB3YXkgdGhhdCB0aGUgZ2Vub3R5cGVzIGFyZSBjb3JybGVhdGVkIGFjcm9zcyBsb2NpLgoKIyBDb21wYXJpbmcgb25lLWxvY3VzIEdXQVMgYW5kIGdlbm9taWMgcHJlZGljdGlvbnMKCkxldCdzIGZpcnN0IGxvb2sgYXQgdGhlIGxvY3VzLWJ5LWxvY3VzIGVzdGltYXRlcyBvZiBhbGxlbGljIGVmZmVjdHMuCgpgYGB7cn0KZm9yX3Bsb3QgPC0gdGliYmxlKEdXQVMgPSByZXN1bHRzJE1lYW4sCiAgICAgICAgICAgICAgICAgICBHUCA9IHJlc3VsdHNfZ3AkTWVhbikgJT4lCiAgZmlsdGVyKCFpcy5uYShHV0FTKSkKcCA8LSBnZ3Bsb3QoZm9yX3Bsb3QsIGFlcyh4ID0gR1dBUywgeSA9IEdQKSkgKwogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9hYmxpbmUoc2xvcGUgPSAxLCBpbnRlcmNlcHQgPSAwLCBjb2xvciA9ICJzYWxtb24iLAogICAgICAgICAgICAgIGxpbmV0eXBlID0gImRhc2hlZCIpICsKICB0aGVtZV9idygpCnAKZ2dzYXZlKCJnd2FzLXZzLWdwLmVwcyIpCmBgYApUaGV5IGFyZSBicm9hZGx5IHNpbWlsYXIsIGJ1dCB0aGVyZSBhcmUgYWxzbyBjbGVhcmx5IHNvbWUgZGlmZmVyZW5jZXMuIE5vdyBsZXQncyBzZWUgaG93IHdlbGwgd2UgY2FuIHByZWRpY3QgdGhlIHBoZW5vdHlwZXMuCgpgYGB7cn0KcHJlZGljdGlvbnMgPC0gdGliYmxlKE9ic2VydmVkID0gTkEsCiAgICAgICAgICAgICAgICAgICAgICBNb2RlbCA9IE5BLAogICAgICAgICAgICAgICAgICAgICAgUHJlZGljdGVkID0gTkEsCiAgICAgICAgICAgICAgICAgICAgICBFcnJvciA9IE5BKQpmb3IgKGkgaW4gMTpucm93KGRhdCkpIHsKICBwcmVkaWN0ZWQgPC0wLjAKICBmb3IgKGogaW4gMTpuX2xvY2kpIHsKICAgIHByZWRpY3RlZCA8LSBwcmVkaWN0ZWQgKyByZXN1bHRzJE1lYW5baV0qZGF0W2ksIGorMV0KICB9CiAgcHJlZGljdGlvbnMgPC0gYWRkX3JvdyhwcmVkaWN0aW9ucywKICAgICAgICAgICAgICAgICAgICAgICAgIE9ic2VydmVkID0gZGF0JHBoZW5vW2ldLAogICAgICAgICAgICAgICAgICAgICAgICAgTW9kZWwgPSAiR1dBUyIsCiAgICAgICAgICAgICAgICAgICAgICAgICBQcmVkaWN0ZWQgPSBwcmVkaWN0ZWQsCiAgICAgICAgICAgICAgICAgICAgICAgICBFcnJvciA9IFByZWRpY3RlZCAtIE9ic2VydmVkKQogIHByZWRpY3RlZCA8LTAuMAogIGZvciAoaiBpbiAxOm5fbG9jaSkgewogICAgcHJlZGljdGVkIDwtIHByZWRpY3RlZCArIHJlc3VsdHNfZ3AkTWVhbltpXSpkYXRbaSwgaisxXQogIH0KICBwcmVkaWN0aW9ucyA8LSBhZGRfcm93KHByZWRpY3Rpb25zLAogICAgICAgICAgICAgICAgICAgICAgICAgT2JzZXJ2ZWQgPSBkYXQkcGhlbm9baV0sCiAgICAgICAgICAgICAgICAgICAgICAgICBNb2RlbCA9ICJHUCIsCiAgICAgICAgICAgICAgICAgICAgICAgICBQcmVkaWN0ZWQgPSBwcmVkaWN0ZWQsCiAgICAgICAgICAgICAgICAgICAgICAgICBFcnJvciA9IFByZWRpY3RlZCAtIE9ic2VydmVkKQp9CnByZWRpY3Rpb25zIDwtIGZpbHRlcihwcmVkaWN0aW9ucywgIWlzLm5hKFByZWRpY3RlZCkpCnAgPC0gZ2dwbG90KHByZWRpY3Rpb25zLCBhZXMoeCA9IE9ic2VydmVkLCB5ID0gUHJlZGljdGVkKSkgKwogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9hYmxpbmUoc2xvcGUgPSAxLCBpbnRlcmNlcHQgPSAwLCBjb2xvciA9ICJzYWxtb24iLCAKICAgICAgICAgICAgICBsaW5ldHlwZSA9ICJkYXNoZWQiKSArCiAgZmFjZXRfd3JhcCh+IE1vZGVsKSArCiAgdGhlbWVfYncoKQpwCmdnc2F2ZSgiZ3dhcy1vYnMtdnMtcHJlZGljdGVkLmVwcyIpCmBgYAoKYGBge3J9CmNhdCgiTWVhbiBzcXVhcmVkIGVycm9yOlxuIiwKICAgICIgICBHV0FTOiAiLCByb3VuZChzdW0oc3Vic2V0KHByZWRpY3Rpb25zLCBNb2RlbCA9PSAiR1dBUyIpJEVycm9yXjIpLAogICAgICAgICAgICAgICAgICAgICAgIDMpL25yb3coZGF0KSwgIlxuIiwKICAgICIgICAgIEdQOiAiLCByb3VuZChzdW0oc3Vic2V0KHByZWRpY3Rpb25zLCBNb2RlbCA9PSAiR1AiKSRFcnJvcl4yKSwKICAgICAgICAgICAgICAgICAgICAgICAzKS9ucm93KGRhdCksICJcbiIsCiAgICBzZXAgPSAiIikKYGBgCgpBZ2FpbiwgdGhpcyBpcyBvbmx5IG9uZSBleGFtcGxlLCBidXQgeW91IGNhbiBzZWUgdGhhdCB0aGUgZ2Vub21pYyBwcmVkaWN0aW9uIChtdWx0aXBsZSByZWdyZXNzaW9uKSBhcHByb2FjaCBnaXZlcyB1cyBhIHNtYWxsZXIgbWVhbiBlcnJvciB0aGFuIHRoZSBzaW5nbGUgbG9jdXMgR1dBUyBhcHByb2FjaC4uCg==