Overview

This R notebook may be a simpler way to follow along with the lecture notes that introduce the idea of genomic prediction (HTML, PDF). Much of the code is taken directly from http://darwin.eeb.uconn.edu/eeb348-resources/genomic-prediction.R with some minor modifications to reflect things I’ve learned about coding in R in the last two and a half years. The final part (Comparing one-locus GWAS and genomic predictions) includes some new code.

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.

  1. 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.

  2. Generate a genotype at random for an individual based on the genotype frequencies at each locus from #1

  3. Generate a phenotype for this individual.

    1. 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.
    2. 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().
    3. Sum the phenotypic contribution across all of the loci.1
  4. 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.2

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.3 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..


  1. Since we’re assuming that only loci 1-5 influence the phenotype, we only do this sum across loci 1-5.↩︎

  2. Since the individuals were generated randomly, they are equally unrelated to one another.↩︎

  3. That’s why we used brms instead of rstanarm in lab. rstanarm doesn’t have a way to include relatedness.↩︎

LS0tCnRpdGxlOiAiRXhwbG9yaW5nIGdlbm9taWMgcHJlZGljdGlvbiIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOgogICAgdG9jOiB5ZXMKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgY3NzOiAiUi1ub3RlYm9vay5jc3MiCi0tLQoKIyBPdmVydmlldwoKVGhpcyBgUmAgbm90ZWJvb2sgbWF5IGJlIGEgc2ltcGxlciB3YXkgdG8gZm9sbG93IGFsb25nIHdpdGggdGhlIGxlY3R1cmUgbm90ZXMgdGhhdCBpbnRyb2R1Y2UgdGhlIGlkZWEgb2YgZ2Vub21pYyBwcmVkaWN0aW9uIChbSFRNTF0oaHR0cDovL2Rhcndpbi5lZWIudWNvbm4uZWR1L2VlYjM0OC1ub3Rlcy9nZW5vbWljLXByZWRpY3Rpb24uaHRtbCksIFtQREZdKGh0dHA6Ly9kYXJ3aW4uZWViLnVjb25uLmVkdS9lZWIzNDgtbm90ZXMvZ2Vub21pYy1wcmVkaWN0aW9uLnBkZikpLiBNdWNoIG9mIHRoZSBjb2RlIGlzIHRha2VuIGRpcmVjdGx5IGZyb20gW2h0dHA6Ly9kYXJ3aW4uZWViLnVjb25uLmVkdS9lZWIzNDgtcmVzb3VyY2VzL2dlbm9taWMtcHJlZGljdGlvbi5SXShodHRwOi8vZGFyd2luLmVlYi51Y29ubi5lZHUvZWViMzQ4LXJlc291cmNlcy9nZW5vbWljLXByZWRpY3Rpb24uUikgd2l0aCBzb21lIG1pbm9yIG1vZGlmaWNhdGlvbnMgdG8gcmVmbGVjdCB0aGluZ3MgSSd2ZSBsZWFybmVkIGFib3V0IGNvZGluZyBpbiBgUmAgaW4gdGhlIGxhc3QgdHdvIGFuZCBhIGhhbGYgeWVhcnMuIFRoZSBmaW5hbCBwYXJ0IChbQ29tcGFyaW5nIG9uZS1sb2N1cyBHV0FTIGFuZCBnZW5vbWljIHByZWRpY3Rpb25zXSgjY29tcGFyaW5nLW9uZS1sb2N1cy1nd2FzLWFuZC1nZW5vbWljLXByZWRpY3Rpb25zKSkgaW5jbHVkZXMgc29tZSBuZXcgY29kZS4KCiMgR2VuZXJhdGluZyB0aGUgZGF0YSBmb3IgYW5hbHlzaXMKClRoZSBmaXJzdCBzdGVwIGluIGV4cGxvcmluZyBnZW5vbWljIHByZWRpY3Rpb24gaXMgdG8gZ2VuZXJhdGUgZGF0YSB3aGVyZSB3ZSBrbm93IHRoZSBhbnN3ZXIgc28gdGhhdCB3ZSBjYW4gY29tcGFyZSBvdXIgZXN0aW1hdGUgZnJvbSB0aGUgZGF0YSB3aXRoIHRoZSB0cnV0aC4gYGdlbmVyYXRlX2RhdGEoKWAgZG9lcyB0aGlzIGJ5IGZvbGxvd2luZyB0aGVzZSBzdGVwcy4KCjEuIEdlbmVyYXRlIGdlbm90eXBlIGZyZXF1ZW5jaWVzIGF0IGVhY2ggbG9jdXMuIEJ5IGRlZmF1bHQsIGBnZW5lcmF0ZV9kYXRhKClgIGdlbmVyYXRlcyBnZW5vdHlwZXMgYXQgMjAgbG9jaSwgYnV0IHlvdSBjYW4gY2hhbmdlIHRoYXQgd2hlbiB5b3UgY2FsbCBpdCBieSBjaGFuZ2luZyBgbl9sb2NpX3RvdGFsYCBpbiB0aGUgY2FsbC4gV2UgZ2VuZXJhdGUgdGhlIGdlbm90eXBlcyBpbiBzdWNoIGEgd2F5IHRoYXQgdGhleSBhcmUgY29ycmVsYXRlZCB3aXRoIG9uZSBhbm90aGVyLl5bSGVyZSBhcmUgdGhlIGRldGFpbHMsIGlmIHlvdSdyZSBpbnRlcmVzdGVkOiAoYSkgR2VuZXJhdGUgYSBzYW1wbGUgZnJvbSBhIG11bHRpdmFyaWF0ZSBub3JtYWwgZGlzdHJpYnV0aW9uIHdpdGggYSBtZWFuIHZlY3RvciBvZiB6ZXJvIGFuZCBhIGNvdmFyaWFuY2UgbWF0cml4IHdoZXJlIGFsbCBvZiB0aGUgdmFyaWFuY2VzIGFyZSAxIGFuZCB0aGUgY29ycmVsYXRpb24gb2YgZWFjaCBlbGVtZW50IG9mIHRoZSB2ZWN0b3IgaXMgJFxyaG8vMiQgd2l0aCB0aGUgZWxlbWVudCBqdXN0IGJlZm9yZSBpdCBhbmQgdGhlIGVsZW1lbnQganVzdCBhZnRlciBpdC4gQ2FsbCB0aGUgYG5fbG9jaWAgcmFuZG9tbHkgZ2VuZXJhdGVkIG51bWJlcnMgYGxvZ2l0X3BgLiAoYikgQ29udmVydCB0aGUgdGhlIGBsb2dpdF9wYCB0byBmcmVxdWVuY2llcyB1c2luZyAkcCA9IFxmcmFje1xtYm94e2V4cH0oXG1ib3h7bG9naXRfcH0pfXsxICsgXG1ib3h7ZXhwfShcbWJveHtsb2dpdF9wfSl9JC4gKGMpIEdlbmVyYXRlIGEgbWF0cml4IG9mIGdlbm90eXBlIGZyZXF1ZW5jaWVzIGF0IGVhY2ggbG9jdXMgYXNzdW1pbmcgZ2Vub3R5cGVzIGFyZSBpbiBIYXJkeS1XZWluYmVyZyBhdCBldmVyeSBsb2N1cy4gCjIuIEdlbmVyYXRlIGEgZ2Vub3R5cGUgYXQgcmFuZG9tIGZvciBhbiBpbmRpdmlkdWFsIGJhc2VkIG9uIHRoZSBnZW5vdHlwZSBmcmVxdWVuY2llcyBhdCBlYWNoIGxvY3VzIGZyb20gIzEKCjMuIEdlbmVyYXRlIGEgcGhlbm90eXBlIGZvciB0aGlzIGluZGl2aWR1YWwuCgogICAgYS4gQ2FsY3VsYXRlIHRoZSBnZW5vdHlwaWMgbWVhbiBhdCBlYWNoIGxvY3VzIGZyb20gdGhlIHNwZWNpZmllZCBhbGxlbGljIGVmZmVjdCBhbmQgdGhlIGdlbm90eXBlIGF0IHRoYXQgbG9jdXMuIEJ5IGRlZmF1bHQgdGhlIGFsbGVsaWMgZWZmZWN0cyBhcmUgMS4wLCAtMS4wLCAwLjUsIC0wLjUsIGFuZCAwLjI1IGF0IGxvY2kgMS01IGFuZCAwLjAgYXQgdGhlIHJlbWFpbmluZyAxNSBsb2NpLiBZb3UgY2FuIGNoYW5nZSB0aGF0IGJ5IGNoYW5naW5nIGBlZmZlY3RgIHdoZW4geW91IGNhbGwgYGdlbmVyYXRlX2RhdGEoKWAuIFRoZSBhbGxlbGljIGFmZmVjdCBpcyB0aGUgZWZmZWN0IG9mIGhhdmluZyAwLCAxLCBvciAyIGNvcGllcyBvZiB0aGUgYWxsZWxlLCBhbmQgdGhlcmUgaXMgbm8gZG9taW5hbmNlLgogICAgYi4gR2VuZXJhdGUgYSBwaGVub3R5cGljIGNvbnRyaWJ1dGlvbiBhdCBlYWNoIGxvY3VzIGFzIGEgcmFuZG9tIHZhcmlhYmxlIGhhdmluZyBhIG5vcm1hbCBkaXN0cmlidXRpb24gd2l0aCB0aGUgZ2Vub3R5cGljIG1lYW4gYW5kIGEgc3BlY2lmaWVkIHN0YW5kYXJkIGRldmlhdGlvbi4gQnkgZGVmYXVsdCB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIGlzIDAuMi4gWW91IGNhbiBjaGFuZ2UgdGhhdCBieSBjaGFuZ2luZyBgc19kZXZgIHdoZW4geW91IGNhbGwgYGdlbmVyYXRlX2RhdGEoKWAuCiAgICBjLiBTdW0gdGhlIHBoZW5vdHlwaWMgY29udHJpYnV0aW9uIGFjcm9zcyBhbGwgb2YgdGhlIGxvY2kuXltTaW5jZSB3ZSdyZSBhc3N1bWluZyB0aGF0IG9ubHkgbG9jaSAxLTUgaW5mbHVlbmNlIHRoZSBwaGVub3R5cGUsIHdlIG9ubHkgZG8gdGhpcyBzdW0gYWNyb3NzIGxvY2kgMS01Ll0KICAKNC4gUmVwZWF0ICMyIGFuZCAjMyB1bnRpbCB5b3UgaGF2ZSB0aGUgbnVtYmVyIG9mIGluZGl2aWR1YWxzIGluIHRoZSBzYW1wbGUgZGF0YSBzZXQgdGhhdCB5b3Ugd2FudC4gQnkgZGVmYXVsdCB0aGF0J3MgMTAwLCBidXQgeW91IGNhbiBjaGFuZ2UgdGhhdCBieSBjaGFuZ2luZyBgbl9pbmRpdmAgd2hlbiB5b3UgY2FsbCBgZ2VuZXJhdGVfZGF0YWAuCgpgZ2VuZXJhdGVfZGF0YSgpYCByZXR1cm5zIHRoZSByZXN1bHRzIG9mIHRoZSBzaW11bGF0aW9uIGFzIGEgZGF0YSBmcmFtZSB3aXRoIGVhY2ggaW5kaXZpZHVhbCBvbiBhIHJvdyBhbmQgd2l0aCB0aGUgcGhlbm90eXBlIGluIHRoZSBmaXJzdCBjb2x1bW4gYW5kIHRoZSBnZW5vdHlwZXMgYXQgZWFjaCBsb2N1cyBpbiB0aGUgcmVtYWluaW5nIGNvbHVtbnMuCgpOT1RFOiBJJ20gdXNpbmcgYHNldC5zZWVkKClgIHRvIGVuc3VyZSB0aGF0IHlvdSBnZXQgdGhlIHNhbWUgc2VxdWVuY2Ugb2YgcmFuZG9tIG51bWJlcnMgdGhhdCBJIGRvIGlmIHlvdSBydW4gdGhpcyBjb2RlIG9uIHlvdXIgb3duLiBZb3UgY2FuIGRlbGV0ZSB0aGF0IGxpbmUgb3IgY29tbWVudCBpdCBvdXQgaWYgeW91IHdhbnQgdG8gc2VlIHdoYXQgaGFwcGVucyB3aXRoIGRpZmZlcmVudCByYW5kb21seSBnZW5lcmF0ZWQgZGF0YSBzZXRzLgoKYGBge3IgbWVzc2FnZSA9IEZBTFNFfQpsaWJyYXJ5KE1BU1MpCgpybShsaXN0ID0gbHMoKSkKCnNldC5zZWVkKDEyMzQ1KQoKZ2VuZXJhdGVfZnJlcXVlbmNpZXMgPC0gZnVuY3Rpb24obl9sb2NpLCByaG8pIHsKICBTaWdtYSA8LSBkaWFnKDEsIG5fbG9jaSkKICBTaWdtYVsxLDJdIDwtIHJobwogIGZvciAoaSBpbiAyOihuX2xvY2kgLSAxKSkgewogICAgU2lnbWFbaSwgaSAtIDFdIDwtIHJoby8yCiAgICBTaWdtYVtpLCBpICsgMV0gPC0gcmhvLzIKICB9CiAgU2lnbWFbbl9sb2NpLCBuX2xvY2kgLSAxXSA8LSByaG8KICBsb2dpdF9wIDwtIG12cm5vcm0obl9sb2NpLCByZXAoMCwgbl9sb2NpKSwgU2lnbWEpCiAgcCA8LSBleHAobG9naXRfcCkvKDEgKyBleHAobG9naXRfcCkpCiAgeCA8LSBtYXRyaXgobnJvdyA9IG5fbG9jaSwgbmNvbCA9IDMpCiAgZm9yIChpIGluIDE6bl9sb2NpKSB7CiAgICB4W2ksIF0gPC0gYyhwW2ldXjIsIDIqcFtpXSooMS1wW2ldKSwgKDEtcFtpXSleMikKICB9CiAgcmV0dXJuKHgpCn0KCmdlbmVyYXRlX2dlbm90eXBlcyA8LSBmdW5jdGlvbihmcmVxcykgewogIHggPC0gbnVtZXJpYyhucm93KGZyZXFzKSkKICBuX2xvY2kgPC0gbnJvdyhmcmVxcykKICBmb3IgKGkgaW4gMTpuX2xvY2kpIHsKICAgIHhbaV0gPC0gd2hpY2gocm11bHRpbm9tKDEsIDEsIGZyZXFzW2ksIF0pID09IDEpIC0gMQogIH0KICByZXR1cm4oeCkKfQoKZ2VuZXJhdGVfZGF0YSA8LSBmdW5jdGlvbihuX2luZGl2ID0gMTAwLAogICAgICAgICAgICAgICAgICAgICAgICAgIG5fbG9jaV90b3RhbCA9IDIwLAogICAgICAgICAgICAgICAgICAgICAgICAgIGVmZmVjdCA9IGMoMSwgLTEsIDAuNSwgLTAuNSwgMC4yNSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgc19kZXYgPSAwLjIpCnsKICBwaGVubyA8LSBudW1lcmljKG5faW5kaXYpCiAgZ2VubyA8LSBtYXRyaXgobnJvdyA9IG5faW5kaXYsIG5jb2wgPSBuX2xvY2lfdG90YWwpCiAgZnJlcXMgPC0gZ2VuZXJhdGVfZnJlcXVlbmNpZXMobl9sb2NpX3RvdGFsLCAwLjIpCiAgZm9yIChpIGluIDE6bl9pbmRpdikgewogICAgZm9yIChqIGluIDE6bl9sb2NpX3RvdGFsKSB7CiAgICAgIHggPC0gZ2VuZXJhdGVfZ2Vub3R5cGVzKGZyZXFzKQogICAgfQogICAgZ2Vub1tpLCBdIDwtIHgKICAgIHBoZW5vW2ldIDwtIDAuMAogICAgbl9sb2NpX2Fzc29jIDwtIGxlbmd0aChlZmZlY3QpCiAgICBmb3IgKGogaW4gMTpuX2xvY2lfYXNzb2MpIHsKICAgICAgcGhlbm9baV0gPC0gcGhlbm9baV0gKyBybm9ybSgxLCBlZmZlY3Rbal0qZ2Vub1tpLGpdLCBzX2RldikKICAgIH0KICB9CiAgZGF0IDwtIGNiaW5kKHBoZW5vLCBnZW5vKQogICMjIHJlbW92ZSBhbnkgbG9jaSB0aGF0IGhhcHBlbiB0byBiZSBtb25vbW9ycGhpYwogICMjCiAgY291bnRzIDwtIGFwcGx5KGRhdFssIC0xXSwgMiwgc3VtKQogIHJlbW92ZSA8LSAoY291bnRzID09IDIqbnJvdyhkYXQpKSB8IChjb3VudHMgPT0gMCkKICBkYXQgPC0gZGF0WywgYyhUUlVFLCAhcmVtb3ZlKV0KICBjb2xuYW1lcyhkYXQpIDwtIGMoInBoZW5vIiwgcGFzdGUoImxvY3VzXyIsIDE6bGVuZ3RoKGNvdW50cyksIHNlcCA9ICIiKSkKICByZXR1cm4oYXMuZGF0YS5mcmFtZShkYXQpKQp9CgpkYXQgPC0gZ2VuZXJhdGVfZGF0YSgpCmxvY2kgPC0gY29sbmFtZXMoZGF0KVstMV0Kbl9sb2NpIDwtIGxlbmd0aChsb2NpKQpgYGAKCiMgUnVubmluZyB0aGUgYW5hbHlzaXMKCldlIGdlbmVyYXRlZCB0aGUgZGF0YSBhc3N1bWluZyB0aGF0IHRoZSBpbmRpdmlkdWFscyBhcmUgYWxsIHBhcnQgb2Ygb25lLCB2ZXJ5IGxhcmdlLCB3ZWxsLW1peGVkIHBvcHVsYXRpb24uIEFzIGEgcmVzdWx0LCB3ZSBkb24ndCBuZWVkIHRvIHdvcnJ5IGFib3V0IHJlbGF0ZWRuZXNzIGFzIHdlIGRpZCBpbiBbTGFiIDEzXShodHRwOi8vZGFyd2luLmVlYi51Y29ubi5lZHUvZWViMzQ4LXJlc291cmNlcy9MYWIxMy5uYi5odG1sKS4gV2UnbGwgdXNlIGBzdGFuX2xtKClgIGZvciB0aGUgYW5hbHlzaXMuIEl0IGRvZXMgYSBzaW1wbGUgbGluZWFyIHJlZ3Jlc3Npb24gb2YgcGhlbm90eXBlIG9uIGdlbm90eXBlLCBidXQgYXMgeW91IGNhbiBwcm9iYWJseSBndWVzcyBmcm9tIHRoZSAic3RhbiIgaW4gaXRzIG5hbWUsIGl0IHVzZXMgYFN0YW5gIGFzIGEgYmFja2VuZCB0byBnaXZlIGlzIG5vdCBvbmx5IGEgcG9zdGVyaW9yIG1lYW4sIGJ1dCBhbHNvIGNyZWRpYmxlIGludGVydmFscy4KCiMjIExvY3VzLWJ5LWxvY3VzIEdXQVMKCldlJ2xsIHN0YXJ0IHdpdGggYSBsb2N1cy1ieS1sb2N1cyBHV0FTIGxpa2UgdGhlIG9uZSBpbiBsYWIsIGV4Y2VwdCB0aGF0IHdlJ2xsIHVzZSBgcnN0YW5hcm1gIGluc3RlYWQgb2YgYGJybXNgIGFuZCB3ZSdsbCBpZ25vcmUgcmVsYXRlZG5lc3MuXltTaW5jZSB0aGUgaW5kaXZpZHVhbHMgd2VyZSBnZW5lcmF0ZWQgcmFuZG9tbHksIHRoZXkgYXJlIGVxdWFsbHkgdW5yZWxhdGVkIHRvIG9uZSBhbm90aGVyLl0gCgpgYGB7ciBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0Kb3B0aW9ucyh0aWR5dmVyc2UucXVpZXQgPSBUUlVFKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShyc3RhbmFybSkKCm9wdGlvbnMobWMuY29yZXMgPSBwYXJhbGxlbDo6ZGV0ZWN0Q29yZXMoKSkKCnJlc3VsdHMgPC0gdGliYmxlKExvY3VzID0gTkEsCiAgICAgICAgICAgICAgICAgIE1lYW4gPSBOQSwKICAgICAgICAgICAgICAgICAgYDIuNSVgID0gTkEsCiAgICAgICAgICAgICAgICAgIGA5Ny41JWAgPSBOQSkKZm9yIChsb2N1cyBpbiAxOm5fbG9jaSkgewogIGNhdCgiTG9jdXMgIiwgbG9jdXMsICJcbiIsIHNlcCA9ICIiKQogIGZpdCA8LSBzdGFuX2xtKHBhc3RlKCJwaGVubyB+ICIsIGxvY2lbbG9jdXNdLCBzZXA9IiIpLAogICAgICAgICAgICAgICAgIHByaW9yID0gUjIoMC41LCB3aGF0ID0gIm1lYW4iKSwKICAgICAgICAgICAgICAgICBkYXRhID0gZGF0LAogICAgICAgICAgICAgICAgIHJlZnJlc2ggPSAwKQogIHRtcCA8LSBkYXRhLmZyYW1lKGZpdCkKICBlZmZlY3QgPC0gdG1wW1tsb2NpW2xvY3VzXV1dCiAgY29uZiA8LSBxdWFudGlsZShlZmZlY3QsIGMoMC4wMjUsIDAuOTc1KSkKICByZXN1bHRzIDwtIGFkZF9yb3cocmVzdWx0cywKICAgICAgICAgICAgICAgICAgICAgTG9jdXMgPSBsb2N1cywKICAgICAgICAgICAgICAgICAgICAgTWVhbiA9IHJvdW5kKG1lYW4oZWZmZWN0KSwgMyksCiAgICAgICAgICAgICAgICAgICAgIGAyLjUlYCA9IHJvdW5kKGNvbmZbMV0sIDMpLAogICAgICAgICAgICAgICAgICAgICBgOTcuNSVgID0gcm91bmQoY29uZlsyXSwgMykpCn0KcmVzdWx0cyAlPiUKICBmaWx0ZXIoIWlzLm5hKE1lYW4pKSAlPiUKICBhcnJhbmdlKGRlc2MoYWJzKE1lYW4pKSkKYGBgCgpXaGlsZSB0aGUgZml2ZSBsb2NpIHRoYXQgd2Uga25vdyBoYXZlIGFuIGVmZmVjdCBjYW1lIG91dCB3aXRoIHRoZSBmaXZlIGxhcmdlc3QgZXN0aW1hdGVkIGVmZmVjdHMgaW4gdGhpcyBhbmFseXNpcywgbG9jdXMgMyBoYXMgYSBjcmVkaWJsZSBpbnRlcnZhbCB0aGF0IGRvZXMgbm90IG92ZXJsYXAgemVybywgbG9jdXMgMjAgaXMgdmVyeSBjbG9zZSB0byBub3Qgb3ZlcmxhcHBpbmcgemVybywgYW5kIGFsbCBvZiB0aGUgZmlyc3QgdGVuIGxvY2kgaGF2ZSBhbiBlc3RpbWF0ZWQgZWZmZWN0IGF0IGxlYXN0IGhhbGYgYXMgbGFyZ2UgYXMgbG9jdXMgNS4gQmFzZWQgb24gdGhpcyBhbmFseXNpcywgaXQgd291bGQgYmUgdGVtcHRpbmcgdG8gY29uY2x1ZGUgdGhhdCB0aGVyZSBhcmUgc2V2ZW4gbG9jaSB3aXRoIGEgbm90aWNlYWJsZSBlZmZlY3Qgb24gdGhlIHRyYWl0LgoKIyMgR2Vub21pYyBwcmVkaWN0aW9uCgpHZW5vbWljIHByZWRpY3Rpb24gaXMgdmVyeSBzaW1pbGFyIHRvIHdoYXQgd2UndmUganVzdCBzZWVuLiBXZSBzaW1wbHkgZG8gb25lIG11bHRpcGxlIHJlZ3Jlc3Npb24gaW4gd2hpY2ggYWxsIG9mIHRoZSBnZW5vdHlwZXMgYXJlIGluY2x1ZGVkIHJhdGhlciB0aGFuIGRvaW5nIGEgc2VyaWVzIG9mIHJlZ3Jlc3Npb25zIHNlcGFyYXRlbHkgZm9yIGVhY2ggbG9jdXMuIFdlIHN0YXJ0IGJ5IGNvbnN0cnVjdGluZyB0aGUgYHJlZ3Jlc3Npb25fZm9ybXVsYWAsIHdoaWNoIGxvb2tzIHByZXR0eSBzdHJhbmdlLiBXZSB3b3VsZG4ndCBoYXZlIHRvIGRvIHRoaXMsIGJ1dCBpdCdzIGVhc2llciB0aGFuIGNvbnN0cnVjdGluZyB0aGUgbXVsdGlwbGUgcmVncmVzc2lvbiBmb3JtdWxhIGJ5IHR5cGluZyBldmVyeSBsb2N1cyBpbnRvIHRoZSBmb3JtdWxhLgoKYGBge3J9CnJlZ3Jlc3Npb25fZm9ybXVsYSA8LSBwYXN0ZSgicGhlbm8gfiAiLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBhc3RlKCJsb2N1c18iLCAxOm5fbG9jaSwgc2VwID0gIiIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb2xsYXBzZSA9ICIgKyAiKSkKcmVncmVzc2lvbl9mb3JtdWxhCmBgYApOb3cgd2UncmUgcmVhZHkgdG8gcnVuIHRoZSBhbmFseXNpcyBhbmQgZGlzcGxheSB0aGUgcmVzdWx0cy4gV2UncmUgZ29pbmcgdG8gdXNlIGBzdGFuX2dsbSgpYCB3aXRoIGEgYGdhdXNzaWFuKClgIGZhbWlseSBpbnN0ZWFkIG9mIGBzdGFuX2xtKClgLCBiZWNhdXNlIHdlIHdhbnQgdG8gdXNlIHdoYXQncyBrbm93biBhcyBhICJzaHJpbmthZ2UgcHJpb3IiLiBUaGF0J3MgYSBwcmlvciB3aXRoIHRoZSBpbnRlcmVzdGluZyBwcm9wZXJ0eSB0aGF0IGVpdGhlciBhIGNvdmFyaWF0ZSBpcyBpbmNsdWRlZCBpbiB0aGUgcmVncmVzc2lvbiBhbmQgdGhlIHByaW9yIGlzIGZhaXJseSB2YWd1ZSBvciBpdCdzIG5vdCBpbmNsdWRlZCBhbmQgdGhlIHByaW9yIGlzIHRpZ2h0bHkgY29uc3RyYWluZWQgYXJvdW5kIHplcm8uIEl0J3MgYSB3YXkgb2YgbGV0dGluZyB0aGUgZGF0YSB0ZWxsIHVzIHdoaWNoIGNvdmFyaWF0ZXMgaGF2ZSBzdHJvbmcgYXNzb2NpYXRpb25zIGFuZCB3aGljaCBkb24ndCBhbmQgc2ltdWx0YW5lb3VzbHkgbGltaXRpbmcgdGhlIGluZmx1ZW5jZSBvZiB0aG9zZSB0aGF0IGRvbid0IGhhdmUgc3Ryb25nIGFzc29jaWF0aW9ucyBvbiB0aGUgcmVzdWx0cy4gQnV0IGl0IGRvZXMgdGhpcyB3aXRob3V0IGZvcmNpbmcgdXMgdG8gcGljayBwYXJ0aWN1bGFyIGNvdmFyaWF0ZXMgZm9yIHRoZSBhbmFseXNpcy4KClRoZSBwYXJ0aWN1bGFyIHRvb2wgd2UgdXNlIGlzIHdoYXQncyBjYWxsZWQgYSAiaG9yc2VzaG9lIHByaW9yIi4gV2Ugb25seSBuZWVkIHRvIHRlbGwgaXQgb25lIHRoaW5nOiBIb3cgbWFueSBjb2VmZmljaWVudHMgd2UgdGhpbmsgbWlnaHQgYmUgaW1wb3J0YW50LiBUaGUgZGF0YSB3aWxsIHRlbGwgdXMgaG93IG1hbnkgYWN0dWFsbHkgYXJlLiBgcDBgLCB3aGljaCBJIHNldCB0byAxMCBpbiB0aGlzIGV4YW1wbGUgaXMgbWVyZWx5IG91ciBiZXN0IGd1ZXNzIGJlZm9yZSB3ZSBzdGFydCB0aGUgYW5hbHlzaXMuCgpgYGB7cn0KbiA8LSBucm93KGRhdCkKRCA8LSBuY29sKGRhdCkgLSAxCnAwIDwtIDEwCnRhdTAgPC0gcDAvKEQgLSBwMCkgKiAxL3NxcnQobikKcHJpb3JfY29lZmYgPC0gaHMoZ2xvYmFsX3NjYWxlID0gdGF1MCwgc2xhYl9zY2FsZSA9IDEpCgpmaXQgPC0gc3Rhbl9nbG0oYXMuZm9ybXVsYShyZWdyZXNzaW9uX2Zvcm11bGEpLAogICAgICAgICAgICAgICAgZmFtaWx5ID0gZ2F1c3NpYW4oKSwKICAgICAgICAgICAgICAgIHByaW9yID0gcHJpb3JfY29lZmYsCiAgICAgICAgICAgICAgICBkYXRhID0gZGF0LAogICAgICAgICAgICAgICAgcmVmcmVzaCA9IDApCmZpdF9kZiA8LSBhcy5kYXRhLmZyYW1lKGZpdCkKCnJlc3VsdHNfZ3AgPC0gdGliYmxlKExvY3VzID0gTkEsCiAgICAgICAgICAgICAgICAgICAgIE1lYW4gPSBOQSwKICAgICAgICAgICAgICAgICAgICAgYDIuNSVgID0gTkEsCiAgICAgICAgICAgICAgICAgICAgIGA5Ny41JWAgPSBOQSkKZm9yIChsb2N1cyBpbiAxOm5fbG9jaSkgewogIHRtcCA8LSBkYXRhLmZyYW1lKGZpdCkKICBlZmZlY3QgPC0gdG1wW1tsb2NpW2xvY3VzXV1dCiAgY29uZiA8LSBxdWFudGlsZShlZmZlY3QsIGMoMC4wMjUsIDAuOTc1KSkKICByZXN1bHRzX2dwIDwtIGFkZF9yb3cocmVzdWx0c19ncCwKICAgICAgICAgICAgICAgICAgICAgICAgTG9jdXMgPSBsb2N1cywKICAgICAgICAgICAgICAgICAgICAgICAgTWVhbiA9IHJvdW5kKG1lYW4oZWZmZWN0KSwgMyksCiAgICAgICAgICAgICAgICAgICAgICAgYDIuNSVgID0gcm91bmQoY29uZlsxXSwgMyksCiAgICAgICAgICAgICAgICAgICAgICAgYDk3LjUlYCA9IHJvdW5kKGNvbmZbMl0sIDMpKQp9CnJlc3VsdHNfZ3AgJT4lCiAgZmlsdGVyKCFpcy5uYShNZWFuKSkgJT4lCiAgYXJyYW5nZShkZXNjKGFicyhNZWFuKSkpCmBgYAoKTm90aWNlIHRoYXQgd2l0aCB0aGUgZ2Vub21pYyBwcmVkaWN0aW9uIGFwcHJvYWNoIHdlIGdldCB0aGUgZXN0aW1hdGVkIGFsbGVsaWMgZWZmZWN0cyBpbiB0aGUgcmlnaHQgb3JkZXIgYW5kIHJvdWdobHkgcmlnaHQgaW4gbWFnbml0dWRlLiBJbiBhZGRpdGlvbiwgYWxsIG9mIHRoZSBvdGhlciBsb2NpIGhhdmUgZXN0aW1hdGVkIGFsbGVsaWMgZWZmZWN0cyBjbG9zZSB0byB6ZXJvIGFzIHRoZXkgc2hvdWxkLiBUaGlzIGlzIG9ubHkgb25lIGV4YW1wbGUsIGFuZCBpdCBpcyBkYW5nZXJvdXMgdG8gZXh0cmFwb2xhdGUgZnJvbSBvbmUgZXhhbXBsZSwgYnV0IGlmIHlvdSdyZSBmYW1pbGlhciB3aXRoIG11bHRpcGxlIHJlZ3Jlc3Npb24gYW5kIGl0cyBhZHZhbnRhZ2VzLCB5b3UncmUgcHJvYmFibHkgd29uZGVyaW5nLCAiV2h5IGRpZG4ndCB3ZSBqdXN0IGdvIGRpcmVjdGx5IHdpdGggZ2Vub21pYyBwcmVkaWN0aW9uIGluIHRoZSBsYWIgZXhlcmNpc2U/IiBXZWxsLCB3ZSBjb3VsZCBoYXZlLCBidXQgaXQncyB1c2VmdWwgdG8gdW5kZXJzdGFuZCB3aGF0IEdXQVMgaXMgZG9pbmcgZmlyc3QsIGFuZCBpdCdzIHVzZWZ1bCB0byBzZWUgaG93IHRvIGluY2x1ZGUgdGhlIGVmZmVjdCBvZiByZWxhdGVkbmVzcyB3aGVuIG1ha2luZyB0aGUgZXN0aW1hdGVzLl5bVGhhdCdzIHdoeSB3ZSB1c2VkIGBicm1zYCBpbnN0ZWFkIG9mIGByc3RhbmFybWAgaW4gbGFiLiBgcnN0YW5hcm1gIGRvZXNuJ3QgaGF2ZSBhIHdheSB0byBpbmNsdWRlIHJlbGF0ZWRuZXNzLl0gSW4gYWRkaXRpb24sIEdXQVMgYWxsb3dzIHVzIHRvIGlkZW50aWZ5IGxvY2kgdGhhdCAqKiptYXkqKiogYmUgYXNzb2NpYXRlZCB3aXRoIHBoZW5vdHlwaWMgcHJlZGljdGlvbnMuIFRoaXMgcG90ZW50aWFsbHkgYWxsb3dzIHVzIHRvIGV4YW1pbmUgdGhlIGdlbmV0aWMgYXJjaGl0ZWN0dXJlIG9mIGEgdHJhaXQsIGUuZy4sIHRoZSBudW1iZXIgb2YgbG9jaSwgZGlzdHJpYnV0aW9uIG9mIGFsbGVsaWMgZWZmZWN0cyBhY3Jvc3MgbG9jaSwgYW5kIGludGVyYWN0aW9ucyBhbW9uZyBsb2NpLiBJdCBtYXkgYWxzbyBhbGxvdyB1cyB0byBpZGVudGlmeSBsb2NpIHRoYXQgaGF2ZSBhbiBpbXBvcnRhbnQgaW5mbHVlbmNlIG9uIG1vcmUgdGhhbiBvbmUgdHJhaXQuIAoKQWxsIHRoYXQgYmVpbmcgc2FpZCwgaW4gYSByZWFsIEdXQVMgYW5hbHlzaXMsIHlvdSB3b3VsZCB3YW50IHRvIGluY2x1ZGUgYWxsIG9mIHRoZSBsb2NpIGluIGEgbXVsdGlwbGUgcmVncmVzc2lvbiBhbmFseXNpcy4gVGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGVzZSByZXN1bHRzIGFuZCB0aG9zZSBvZiB0aGUgc2luZ2xlIGxvY3VzIGFuYWx5c2lzIGFyaXNlIGJlY2F1c2UgSSBzZXQgdXAgdGhlIHNpbXVsYXRlZCBwb3B1bGF0aW9uIGluIHN1Y2ggYSB3YXkgdGhhdCB0aGUgZ2Vub3R5cGVzIGFyZSBjb3JybGVhdGVkIGFjcm9zcyBsb2NpLgoKIyBDb21wYXJpbmcgb25lLWxvY3VzIEdXQVMgYW5kIGdlbm9taWMgcHJlZGljdGlvbnMKCkxldCdzIGZpcnN0IGxvb2sgYXQgdGhlIGxvY3VzLWJ5LWxvY3VzIGVzdGltYXRlcyBvZiBhbGxlbGljIGVmZmVjdHMuCgpgYGB7cn0KZm9yX3Bsb3QgPC0gdGliYmxlKEdXQVMgPSByZXN1bHRzJE1lYW4sCiAgICAgICAgICAgICAgICAgICBHUCA9IHJlc3VsdHNfZ3AkTWVhbikgJT4lCiAgZmlsdGVyKCFpcy5uYShHV0FTKSkKcCA8LSBnZ3Bsb3QoZm9yX3Bsb3QsIGFlcyh4ID0gR1dBUywgeSA9IEdQKSkgKwogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9hYmxpbmUoc2xvcGUgPSAxLCBpbnRlcmNlcHQgPSAwLCBjb2xvciA9ICJzYWxtb24iLAogICAgICAgICAgICAgIGxpbmV0eXBlID0gImRhc2hlZCIpICsKICB0aGVtZV9idygpCnAKZ2dzYXZlKCJnd2FzLXZzLWdwLmVwcyIpCmBgYApUaGV5IGFyZSBicm9hZGx5IHNpbWlsYXIsIGJ1dCB0aGVyZSBhcmUgYWxzbyBjbGVhcmx5IHNvbWUgZGlmZmVyZW5jZXMuIE5vdyBsZXQncyBzZWUgaG93IHdlbGwgd2UgY2FuIHByZWRpY3QgdGhlIHBoZW5vdHlwZXMuCgpgYGB7cn0KcHJlZGljdGlvbnMgPC0gdGliYmxlKE9ic2VydmVkID0gTkEsCiAgICAgICAgICAgICAgICAgICAgICBNb2RlbCA9IE5BLAogICAgICAgICAgICAgICAgICAgICAgUHJlZGljdGVkID0gTkEsCiAgICAgICAgICAgICAgICAgICAgICBFcnJvciA9IE5BKQpmb3IgKGkgaW4gMTpucm93KGRhdCkpIHsKICBwcmVkaWN0ZWQgPC0wLjAKICBmb3IgKGogaW4gMTpuX2xvY2kpIHsKICAgIHByZWRpY3RlZCA8LSBwcmVkaWN0ZWQgKyByZXN1bHRzJE1lYW5baV0qZGF0W2ksIGorMV0KICB9CiAgcHJlZGljdGlvbnMgPC0gYWRkX3JvdyhwcmVkaWN0aW9ucywKICAgICAgICAgICAgICAgICAgICAgICAgIE9ic2VydmVkID0gZGF0JHBoZW5vW2ldLAogICAgICAgICAgICAgICAgICAgICAgICAgTW9kZWwgPSAiR1dBUyIsCiAgICAgICAgICAgICAgICAgICAgICAgICBQcmVkaWN0ZWQgPSBwcmVkaWN0ZWQsCiAgICAgICAgICAgICAgICAgICAgICAgICBFcnJvciA9IFByZWRpY3RlZCAtIE9ic2VydmVkKQogIHByZWRpY3RlZCA8LTAuMAogIGZvciAoaiBpbiAxOm5fbG9jaSkgewogICAgcHJlZGljdGVkIDwtIHByZWRpY3RlZCArIHJlc3VsdHNfZ3AkTWVhbltpXSpkYXRbaSwgaisxXQogIH0KICBwcmVkaWN0aW9ucyA8LSBhZGRfcm93KHByZWRpY3Rpb25zLAogICAgICAgICAgICAgICAgICAgICAgICAgT2JzZXJ2ZWQgPSBkYXQkcGhlbm9baV0sCiAgICAgICAgICAgICAgICAgICAgICAgICBNb2RlbCA9ICJHUCIsCiAgICAgICAgICAgICAgICAgICAgICAgICBQcmVkaWN0ZWQgPSBwcmVkaWN0ZWQsCiAgICAgICAgICAgICAgICAgICAgICAgICBFcnJvciA9IFByZWRpY3RlZCAtIE9ic2VydmVkKQp9CnByZWRpY3Rpb25zIDwtIGZpbHRlcihwcmVkaWN0aW9ucywgIWlzLm5hKFByZWRpY3RlZCkpCnAgPC0gZ2dwbG90KHByZWRpY3Rpb25zLCBhZXMoeCA9IE9ic2VydmVkLCB5ID0gUHJlZGljdGVkKSkgKwogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9hYmxpbmUoc2xvcGUgPSAxLCBpbnRlcmNlcHQgPSAwLCBjb2xvciA9ICJzYWxtb24iLCAKICAgICAgICAgICAgICBsaW5ldHlwZSA9ICJkYXNoZWQiKSArCiAgZmFjZXRfd3JhcCh+IE1vZGVsKSArCiAgdGhlbWVfYncoKQpwCmdnc2F2ZSgiZ3dhcy1vYnMtdnMtcHJlZGljdGVkLmVwcyIpCmBgYAoKYGBge3J9CmNhdCgiTWVhbiBzcXVhcmVkIGVycm9yOlxuIiwKICAgICIgICBHV0FTOiAiLCByb3VuZChzdW0oc3Vic2V0KHByZWRpY3Rpb25zLCBNb2RlbCA9PSAiR1dBUyIpJEVycm9yXjIpLAogICAgICAgICAgICAgICAgICAgICAgIDMpL25yb3coZGF0KSwgIlxuIiwKICAgICIgICAgIEdQOiAiLCByb3VuZChzdW0oc3Vic2V0KHByZWRpY3Rpb25zLCBNb2RlbCA9PSAiR1AiKSRFcnJvcl4yKSwKICAgICAgICAgICAgICAgICAgICAgICAzKS9ucm93KGRhdCksICJcbiIsCiAgICBzZXAgPSAiIikKYGBgCgpBZ2FpbiwgdGhpcyBpcyBvbmx5IG9uZSBleGFtcGxlLCBidXQgeW91IGNhbiBzZWUgdGhhdCB0aGUgZ2Vub21pYyBwcmVkaWN0aW9uIChtdWx0aXBsZSByZWdyZXNzaW9uKSBhcHByb2FjaCBnaXZlcyB1cyBhIHNtYWxsZXIgbWVhbiBlcnJvciB0aGFuIHRoZSBzaW5nbGUgbG9jdXMgR1dBUyBhcHByb2FjaC4uCg==