Background

Although it is very simple, Sewall Wright’s infinite island model of migration is a useful way to explore how drift, migration, and mutation interact to influence the genetic structure of populations that are divided into subpopulations. In this model we assume that

  1. Every allele introduced into a population differs from any of the resident alleles.

  2. Every population receives the same fraction, \(m\), of migrants.1

Given those assumptions and assuming an infinite alleles model of mutation, we showed that2

\[ F_{ST} = \frac{1}{4N_e(m + \mu) + 1} \quad . \]

A more realistic model of migration is the finite island model of migration.3 It’s still very simple, but it adds one thing that makes it a bit more realistic:

It assumes that there are a finite number of populations exchanging migrants with one another. Every population still receives the same fraction of migrants, \(m\), but we now also specify that the fraction of migrants coming from any one population into this one is \(m/(k - 1)\), where \(k\) is the number of popuations.

The formula for \(F_{ST}\) under the finite island model is a lot more complicated than the one above. If you’re interested, you can look in the R code below.4 Let’s compare the predictions for a few values of \(m\) and \(k\) with \(N_e = 100\) and \(\mu = 10^{-3}\).

Comparing the predictions

rm(list = ls())

infinite_island <- function(n_e, m, mu) {
  return(1/(4*n_e*(m + mu) + 1))
}

lambda <- function(mu, m, k) {
  m_prime <- m*k/(k - 1)
  l <- (1/2)*((1 - mu)^(-2)*(1- m_prime)^(-2) - 1)
  return(l)
}

gamma <- function(mu, m, k) {
  m_prime <- m*k/(k - 1)
  g <- (1 + m_prime*(2 - m_prime)/(k*mu*(2 - mu)*(1 - m_prime)^2))^(-1)
  return(g)
}

finite_island <- function(n_e, m, mu, n_islands) {
  l <- lambda(mu, m, n_islands)
  g <- gamma(mu, m, n_islands)
  h_s <- 4*n_e*l*g/(4*n_e*l*g + 1)
  h_b <- h_s*(1 + 4*n_e*l)/(4*n_e*l)
  h_t <- ((n_islands - 1)/n_islands)*h_b + (1/n_islands)*h_s
  f_st <- (h_t - h_s)/h_t
  return(f_st)
}

n_e <- 100
mu <- 10^(-4)
k_vals <- rep(c(5, 25, 250, 2500), 2)
m_vals <- c(rep(0.01, 4), rep(0.05, 4))
dat <- data.frame(k = k_vals,
                  m = m_vals,
                  Infinite = rep(NA, length(k_vals)),
                  Finite = rep(NA, length(m_vals)),
                  Ratio = rep(NA, length(k_vals)))
for (i in 1:nrow(dat)) {
  dat$Infinite[i] <- infinite_island(n_e, dat$m[i], mu)
  dat$Finite[i] <- finite_island(n_e, dat$m[i], mu, dat$k[i])
  dat$Ratio[i] <- dat$Infinite[i]/dat$Finite[i]
}
round(dat, 3)

Comparing predictions to simulations

From the table above, it’s apparent that predictions of the infinite island and finite island models are rather different when the number of islands is small. Let’s run a simulation of the finite island model and see how well the simulation results match up to each prediction.

library(tidyverse)
Registered S3 methods overwritten by 'dbplyr':
  method         from
  print.tbl_lazy     
  print.tbl_sql      
── Attaching packages ───────────────────────────── tidyverse 1.3.1 ──
✓ ggplot2 3.3.5     ✓ purrr   0.3.4
✓ tibble  3.1.4     ✓ dplyr   1.0.7
✓ tidyr   1.1.3     ✓ stringr 1.4.0
✓ readr   2.0.1     ✓ forcats 0.5.1
── Conflicts ──────────────────────────────── tidyverse_conflicts() ──
x dplyr::filter() masks stats::filter()
x dplyr::lag()    masks stats::lag()
library(hierfstat)

initialize <- function(k, n_loci) {
  p <- array(dim = c(n_loci, k, 2))
  for (j in 1:n_loci) {
    for (i in 1:k) {
      p[j, i, 1] <- runif(n = 1, min = 0, max = 1)
      p[j, i, 2] <- 1 - p[j, i, 1]
    }
  }
  return(p)
}

make_symmetric_matrix <- function(m, k) {
  M <- diag(x = 1 - m, nrow = k)
  for (i in 1:(k - 1)) {
    for (j in (i+1):k) {
      M[i, j] <- m/(k-1)
      M[j, i] <- M[i, j]
    }
  }
  return(M)
}

sample_two_alleles <- function(p) {
  allele_1 <- ((runif(1) < p) + 1)*10
  allele_2 <- (runif(1) < p) + 1
  return(allele_1 + allele_2)
}

make_sample <- function(p, n_sample) {
  n_pops <- dim(p)[2]
  n_loci <- dim(p)[1]
  names <- paste("Locus", seq(1:n_loci), sep = "")
  pops <- numeric(n_pops*n_sample)
  ct <- 1
  for (k in 1:n_pops) {
    population <- paste("Population", k, sep = "")
    for (i in 1:n_sample) {
      pops[ct] <- population
      ct <- ct + 1
    }
  }
  locus_data <- matrix(nrow = n_pops*n_sample, ncol = n_loci)
  for (i in 1:n_loci) {
   ct <- 1
    for (k in 1:n_pops) {
      for (n in 1:n_sample) {
        locus_data[ct, i] <- sample_two_alleles(p[i, k, 1])
        ct <- ct + 1
      }
    }
  }
  df <- data.frame(locus_data)
  colnames(df) <- paste("Locus", seq(1:n_loci), sep = "")
  df$Population <- pops
  df <- relocate(df, Population)
  return(df)
}

simulate <- function(n_e, m, mu, n_islands, n_loci, n_gen, n_sample) {
  p <- initialize(n_islands, n_loci)
  M <- make_symmetric_matrix(m, n_islands)
  V <- make_symmetric_matrix(mu, 2)
  g_st <- numeric(n_loci)
  p_star <- array(dim = c(n_loci, n_islands, 2))
  for (i in 1:n_gen) {
    for (k in 1:n_loci) {
      p_star[k, , ] <- M %*% p[k, , ] %*% V
      for (j in 1:n_islands) {
        p[k, j, ] <- rmultinom(1, 2*n_e, p_star[k, j, ])/(2*n_e)
      }
      mu_p <- mean(p[k, , 1])
      g_st[k] <- ((n_islands - 1)/n_islands)*var(p[k, , 1])/(mu_p*(1 - mu_p))
    }
  }
  df <- make_sample(p, n_sample)
  return(wc(df)$FST)
}

run_simulation <- function(n_e, m, mu, n_islands, n_loci, n_gen, 
                           n_sample, n_repetitions)
{
  f_st <- numeric(n_repetitions)
  for (i in 1:n_repetitions) {
    if (n_repetitions > 50) {
      cat(".", sep="")
      if ((i %% 50) == 0) {
        cat(i, "\n", sep ="")
      }
    }
    f_st[i] <-simulate(n_e, m, mu, n_islands, n_loci, n_gen, n_sample)
  }
  return(f_st)
}

plot_simulation <- function(f_st, n_e, m, mu, n_islands) {
  df <- data.frame(F_st = f_st)
  p <- ggplot(df, aes(x = F_st)) +
    geom_histogram(bins = 20, alpha = 0.4) +
    geom_vline(xintercept = infinite_island(n_e, m, mu),
               linetype = "dashed",
               color = "red") +
    geom_vline(xintercept = finite_island(n_e, m, mu, n_islands),
               linetype = "dashed",
               color = "blue") +
    ggtitle(paste("N_e = ", n_e, ", m = ", m, ", mu = ", mu, 
                  ", n_islands = ", n_islands, sep = "")) +
    theme_bw()
  return(p)
}

f_st <- run_simulation(100, 0.05, 1e-4, 5, 10, 1000, 25, 100)
..................................................50
..................................................100
plot_simulation(f_st, 100, 0.05, 1e-4, 5)

The dashed red line is the prediction from the infinite island model. The dashed blue line is the prediction from the finite island model.

Exercise 6

The last plot shows that neither the infinite island nor the finite island prediction captures the results of this particular simulation very well, it only does so on average and there’s a lot of variation from one replicate to the next. This outcome reflects the “evolutionary” or “genetic” sampling we discussed when comparing Nei’s \(G_{ST}\) with Weir and Cockerham’s \(\theta\). This weeks lab exercise will explore that variability a bit further and explore condidtions that affect the amount of variability and how useful the infinite island approximation is. To do so, you’ll want to use the following code.5 You’ll be changing some or all of

  • n_loci - The number of loci included in the genetic sample,
  • n_sample - The number of (diploid) individuals sampled in each population,
  • n_gen - The number of generations for which to run the simulation, and
  • n_repetitions - The number of times to repeat the simulation for any set of the first three choices. This item corresponds to the number of evolutionary or genetic sampling events included in your simulation.

For each choice of these four parameters, the simulation will run through all combinations of N_e = (25, 200, 250, 500), m = (0.05, 0.01, 0.005, 0.001), mu = (0.001, 0.0001), and n_islands = (10, 25, 50).

n_loci <- 10
n_sample <- 25
n_gen <- 1000
n_repetitions <- 10

df <- data.frame(N_e = NA, m = NA, mu = NA, n_islands = NA, Observed = NA,
                 Infinite = NA, Finite = NA)
for (n_e in c(25, 100, 250, 500)) {
  for (m in c(0.05, 0.01, 0.005, 0.001)) {
    for (mu in c(0.001, 1e-4)) {
      for (n_islands in c(10, 25, 50)) {
        cat("N_e = ", n_e, ", m = ", m, ", mu = ", mu, 
            "n_islands = ", n_islands, "\n" )
        f_st <- run_simulation(n_e, m, mu, n_islands, n_loci, n_gen, 
                               n_sample, n_repetitions)
        df <- add_row(df, 
                      N_e = rep(n_e, n_repetitions),
                      m = rep(m, n_repetitions), 
                      mu = rep(mu, n_repetitions), 
                      n_islands = rep(n_islands, n_repetitions),
                      Observed = f_st,
                      Infinite = infinite_island(n_e, m, mu),
                      Finite = finite_island(n_e, m, mu, n_islands))
      }
    }
  }
}
df <- filter(df, !is.na(N_e))

Running one set of simulations for a particular choice of n_loci, n_sample, n_gen, and n_repetitions takes close to half an hour on my MacBook. You’ll get a printout periodically that lets you know what the current set of parameters being simulated is, and you’ll see the set or parameters that’s already been completed. Because running the simulation for one set of parameters takes so long, you can’t possibly explore all of the combinations of those parameters you might be interested in, but I’d like you to explore at least five and address the following questions:6

  1. Are there conditions under which the predictions of the infinite island and finite island model are similar enough that we don’t need to worry about the added mathematical complexity of the finite island model?

  2. How close is the relationship between observed estimates of \(F_{ST}\) from the simulations and those predicted from the infinite island model? from the finite island model?

  3. Under what conditions is the observed variation in \(F_{ST}\) relatively small?

A few hints

The easiest way to run different combinations of parameters is to copy the code block above and replace n_loci, n_sample, n_gen, and n_repetitions with new choices. To keep track of what you’re doing, I recommend doing that for one combination of parameters, examining the results as described below, and moving on to a new set of parameter (with a new code block) after that.

You can plot the observed \(F_{ST}\) versus the \(F_{ST}\) predicted from either model using the code below.7 In addition to showing how well the simulations match the predictions, you can get a feel for how much variabiity there is among the simulations by seeing how scatterd the points are.

## for the infinite island model
##
p <- ggplot(df, aes(x = Infinite, y = Observed)) +
  geom_point() +
  geom_abline(intercept = 0, slope = 1, linetype = "dashed", 
              color = "red") + theme_bw()
p
## for the finite island model
##
p <- ggplot(df, aes(x = Finite, y = Observed)) +
  geom_point() +
  geom_abline(intercept = 0, slope = 1, linetype = "dashed", 
              color = "red") + theme_bw()
p

If you’d like a more quantitative way to compare the models,8 a simple way is to run linear regressions of Observed on Infinite and Expected like this:

summary(lm(Observed ~ Infinite, data = df))
summary(lm(Observed ~ Finite, data = df))

If predictions were perfect the (Intercept) term in the regression would be 0, and the other term (Infinite in the first regression and Finite in the second) would be 1. Given the variability of the simulations, you won’t see numbers that are exactly 0 or 1. You can judge whether they are “close” by noticing whether the number in the Estimate column is more than two standard errors away from what you predict.

The residual standard error below the table measures how much error there is around the regression, i.e., it gives you a way to compare quantitatively how much variation there is in \(F_{ST}\).


  1. Notice that \(m\) is the backwards migration rate, i.e., the fraction of a population composed of migrants that come from another population, not the fraction of residents that migrate to another population.↩︎

  2. Actually, we didn’t show what happens with both migration and mutation, but from what we saw you can probably guess where this came from.↩︎

  3. Latter, B.D.H. 1973. The island model of population differentiation: a general solution. Genetics 73:147-157 doi: 10.1093/genetics/73.1.147↩︎

  4. You won’t find the formula for \(F_{ST}\) in Latter, but the formulas in the R code follow from the results there.↩︎

  5. Notice that in order to run this code, you’ll also need to run the code above so that the relevant functions are loaded in R’s memory.↩︎

  6. Keep in mind that you’ll only be able to answer these questions for the set of simulations that you complete. I’ll be grading your responses on the simulation results that you show, not on what an exhaustive examination of all possibilities might be.↩︎

  7. The diagonal red dashed line is the 1:1 line. Every point should fall on this line if observed exactly matches the prediction.↩︎

  8. And I’d encourage you to take a more quantitative approach↩︎

LS0tCnRpdGxlOiAiRXhwbG9yaW5nIHRoZSBpbnRlcmFjdGlvbiBvZiBkcmlmdCwgbXV0YXRpb24sIGFuZCBtaWdyYXRpb24iCm91dHB1dDogCiAgaHRtbF9ub3RlYm9vazoKICAgIHRvYzogeWVzCiAgICB0b2NfZmxvYXQ6IHRydWUKLS0tCgojIyBCYWNrZ3JvdW5kCgpBbHRob3VnaCBpdCBpcyB2ZXJ5IHNpbXBsZSwgU2V3YWxsIFdyaWdodCdzIGluZmluaXRlIGlzbGFuZCBtb2RlbCBvZiBtaWdyYXRpb24gaXMgYSB1c2VmdWwgd2F5IHRvIGV4cGxvcmUgaG93IGRyaWZ0LCBtaWdyYXRpb24sIGFuZCBtdXRhdGlvbiBpbnRlcmFjdCB0byBpbmZsdWVuY2UgdGhlIGdlbmV0aWMgc3RydWN0dXJlIG9mIHBvcHVsYXRpb25zIHRoYXQgYXJlIGRpdmlkZWQgaW50byBzdWJwb3B1bGF0aW9ucy4gSW4gdGhpcyBtb2RlbCB3ZSBhc3N1bWUgdGhhdAoKMS4gRXZlcnkgYWxsZWxlIGludHJvZHVjZWQgaW50byBhIHBvcHVsYXRpb24gZGlmZmVycyBmcm9tIGFueSBvZiB0aGUgcmVzaWRlbnQgYWxsZWxlcy4KCjIuIEV2ZXJ5IHBvcHVsYXRpb24gcmVjZWl2ZXMgdGhlIHNhbWUgZnJhY3Rpb24sICRtJCwgb2YgbWlncmFudHMuXltOb3RpY2UgdGhhdCAkbSQgaXMgdGhlICpiYWNrd2FyZHMqIG1pZ3JhdGlvbiByYXRlLCBpLmUuLCB0aGUgZnJhY3Rpb24gb2YgYSBwb3B1bGF0aW9uIGNvbXBvc2VkIG9mIG1pZ3JhbnRzIHRoYXQgY29tZSBmcm9tIGFub3RoZXIgcG9wdWxhdGlvbiwgbm90IHRoZSBmcmFjdGlvbiBvZiByZXNpZGVudHMgdGhhdCBtaWdyYXRlIHRvIGFub3RoZXIgcG9wdWxhdGlvbi5dCgpHaXZlbiB0aG9zZSBhc3N1bXB0aW9ucyBhbmQgYXNzdW1pbmcgYW4gaW5maW5pdGUgYWxsZWxlcyBtb2RlbCBvZiBtdXRhdGlvbiwgd2Ugc2hvd2VkIHRoYXReW0FjdHVhbGx5LCB3ZSBkaWRuJ3Qgc2hvdyB3aGF0IGhhcHBlbnMgd2l0aCAqYm90aCogbWlncmF0aW9uIGFuZCBtdXRhdGlvbiwgYnV0IGZyb20gd2hhdCB3ZSBzYXcgeW91IGNhbiBwcm9iYWJseSBndWVzcyB3aGVyZSB0aGlzIGNhbWUgZnJvbS5dCgokJApGX3tTVH0gPSBcZnJhY3sxfXs0Tl9lKG0gKyBcbXUpICsgMX0gXHF1YWQgLgokJAoKQSBtb3JlIHJlYWxpc3RpYyBtb2RlbCBvZiBtaWdyYXRpb24gaXMgdGhlICoqKmZpbml0ZSoqKiBpc2xhbmQgbW9kZWwgb2YgbWlncmF0aW9uLl5bTGF0dGVyLCBCLkQuSC4gIDE5NzMuICBUaGUgaXNsYW5kIG1vZGVsIG9mIHBvcHVsYXRpb24gZGlmZmVyZW50aWF0aW9uOiBhIGdlbmVyYWwgc29sdXRpb24uICAqR2VuZXRpY3MqICA3MzoxNDctMTU3IGRvaTogWzEwLjEwOTMvZ2VuZXRpY3MvNzMuMS4xNDddKGh0dHBzOi8vZG9pLm9yZy8xMC4xMDkzL2dlbmV0aWNzLzczLjEuMTQ3KV0gIEl0J3Mgc3RpbGwgdmVyeSBzaW1wbGUsIGJ1dCBpdCBhZGRzIG9uZSB0aGluZyB0aGF0IG1ha2VzIGl0IGEgYml0IG1vcmUgcmVhbGlzdGljOgoKPiBJdCBhc3N1bWVzIHRoYXQgdGhlcmUgYXJlIGEgZmluaXRlIG51bWJlciBvZiBwb3B1bGF0aW9ucyBleGNoYW5naW5nIG1pZ3JhbnRzIHdpdGggb25lIGFub3RoZXIuIEV2ZXJ5IHBvcHVsYXRpb24gc3RpbGwgcmVjZWl2ZXMgdGhlIHNhbWUgZnJhY3Rpb24gb2YgbWlncmFudHMsICRtJCwgYnV0IHdlIG5vdyBhbHNvIHNwZWNpZnkgdGhhdCB0aGUgZnJhY3Rpb24gb2YgbWlncmFudHMgY29taW5nIGZyb20gYW55IG9uZSBwb3B1bGF0aW9uIGludG8gdGhpcyBvbmUgaXMgJG0vKGsgLSAxKSQsIHdoZXJlICRrJCBpcyB0aGUgbnVtYmVyIG9mIHBvcHVhdGlvbnMuCgpUaGUgZm9ybXVsYSBmb3IgJEZfe1NUfSQgdW5kZXIgdGhlIGZpbml0ZSBpc2xhbmQgbW9kZWwgaXMgYSBsb3QgbW9yZSBjb21wbGljYXRlZCB0aGFuIHRoZSBvbmUgYWJvdmUuIElmIHlvdSdyZSBpbnRlcmVzdGVkLCB5b3UgY2FuIGxvb2sgaW4gdGhlIGBSYCBjb2RlIGJlbG93Ll5bWW91IHdvbid0IGZpbmQgdGhlIGZvcm11bGEgZm9yICRGX3tTVH0kIGluIExhdHRlciwgYnV0IHRoZSBmb3JtdWxhcyBpbiB0aGUgYFJgIGNvZGUgZm9sbG93IGZyb20gdGhlIHJlc3VsdHMgdGhlcmUuXSBMZXQncyBjb21wYXJlIHRoZSBwcmVkaWN0aW9ucyBmb3IgYSBmZXcgdmFsdWVzIG9mICRtJCBhbmQgJGskIHdpdGggJE5fZSA9IDEwMCQgYW5kICRcbXUgPSAxMF57LTN9JC4KCiMjIyBDb21wYXJpbmcgdGhlIHByZWRpY3Rpb25zCgpgYGB7cn0Kcm0obGlzdCA9IGxzKCkpCgppbmZpbml0ZV9pc2xhbmQgPC0gZnVuY3Rpb24obl9lLCBtLCBtdSkgewogIHJldHVybigxLyg0Km5fZSoobSArIG11KSArIDEpKQp9CgpsYW1iZGEgPC0gZnVuY3Rpb24obXUsIG0sIGspIHsKICBtX3ByaW1lIDwtIG0qay8oayAtIDEpCiAgbCA8LSAoMS8yKSooKDEgLSBtdSleKC0yKSooMS0gbV9wcmltZSleKC0yKSAtIDEpCiAgcmV0dXJuKGwpCn0KCmdhbW1hIDwtIGZ1bmN0aW9uKG11LCBtLCBrKSB7CiAgbV9wcmltZSA8LSBtKmsvKGsgLSAxKQogIGcgPC0gKDEgKyBtX3ByaW1lKigyIC0gbV9wcmltZSkvKGsqbXUqKDIgLSBtdSkqKDEgLSBtX3ByaW1lKV4yKSleKC0xKQogIHJldHVybihnKQp9CgpmaW5pdGVfaXNsYW5kIDwtIGZ1bmN0aW9uKG5fZSwgbSwgbXUsIG5faXNsYW5kcykgewogIGwgPC0gbGFtYmRhKG11LCBtLCBuX2lzbGFuZHMpCiAgZyA8LSBnYW1tYShtdSwgbSwgbl9pc2xhbmRzKQogIGhfcyA8LSA0Km5fZSpsKmcvKDQqbl9lKmwqZyArIDEpCiAgaF9iIDwtIGhfcyooMSArIDQqbl9lKmwpLyg0Km5fZSpsKQogIGhfdCA8LSAoKG5faXNsYW5kcyAtIDEpL25faXNsYW5kcykqaF9iICsgKDEvbl9pc2xhbmRzKSpoX3MKICBmX3N0IDwtIChoX3QgLSBoX3MpL2hfdAogIHJldHVybihmX3N0KQp9CgpuX2UgPC0gMTAwCm11IDwtIDEwXigtNCkKa192YWxzIDwtIHJlcChjKDUsIDI1LCAyNTAsIDI1MDApLCAyKQptX3ZhbHMgPC0gYyhyZXAoMC4wMSwgNCksIHJlcCgwLjA1LCA0KSkKZGF0IDwtIGRhdGEuZnJhbWUoayA9IGtfdmFscywKICAgICAgICAgICAgICAgICAgbSA9IG1fdmFscywKICAgICAgICAgICAgICAgICAgSW5maW5pdGUgPSByZXAoTkEsIGxlbmd0aChrX3ZhbHMpKSwKICAgICAgICAgICAgICAgICAgRmluaXRlID0gcmVwKE5BLCBsZW5ndGgobV92YWxzKSksCiAgICAgICAgICAgICAgICAgIFJhdGlvID0gcmVwKE5BLCBsZW5ndGgoa192YWxzKSkpCmZvciAoaSBpbiAxOm5yb3coZGF0KSkgewogIGRhdCRJbmZpbml0ZVtpXSA8LSBpbmZpbml0ZV9pc2xhbmQobl9lLCBkYXQkbVtpXSwgbXUpCiAgZGF0JEZpbml0ZVtpXSA8LSBmaW5pdGVfaXNsYW5kKG5fZSwgZGF0JG1baV0sIG11LCBkYXQka1tpXSkKICBkYXQkUmF0aW9baV0gPC0gZGF0JEluZmluaXRlW2ldL2RhdCRGaW5pdGVbaV0KfQpyb3VuZChkYXQsIDMpCmBgYAoKIyMjIENvbXBhcmluZyBwcmVkaWN0aW9ucyB0byBzaW11bGF0aW9ucwoKRnJvbSB0aGUgdGFibGUgYWJvdmUsIGl0J3MgYXBwYXJlbnQgdGhhdCBwcmVkaWN0aW9ucyBvZiB0aGUgaW5maW5pdGUgaXNsYW5kIGFuZCBmaW5pdGUgaXNsYW5kIG1vZGVscyBhcmUgcmF0aGVyIGRpZmZlcmVudCB3aGVuIHRoZSBudW1iZXIgb2YgaXNsYW5kcyBpcyBzbWFsbC4gTGV0J3MgcnVuIGEgc2ltdWxhdGlvbiBvZiB0aGUgZmluaXRlIGlzbGFuZCBtb2RlbCBhbmQgc2VlIGhvdyB3ZWxsIHRoZSBzaW11bGF0aW9uIHJlc3VsdHMgbWF0Y2ggdXAgdG8gZWFjaCBwcmVkaWN0aW9uLgoKYGBge3J9CmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGhpZXJmc3RhdCkKCmluaXRpYWxpemUgPC0gZnVuY3Rpb24oaywgbl9sb2NpKSB7CiAgcCA8LSBhcnJheShkaW0gPSBjKG5fbG9jaSwgaywgMikpCiAgZm9yIChqIGluIDE6bl9sb2NpKSB7CiAgICBmb3IgKGkgaW4gMTprKSB7CiAgICAgIHBbaiwgaSwgMV0gPC0gcnVuaWYobiA9IDEsIG1pbiA9IDAsIG1heCA9IDEpCiAgICAgIHBbaiwgaSwgMl0gPC0gMSAtIHBbaiwgaSwgMV0KICAgIH0KICB9CiAgcmV0dXJuKHApCn0KCm1ha2Vfc3ltbWV0cmljX21hdHJpeCA8LSBmdW5jdGlvbihtLCBrKSB7CiAgTSA8LSBkaWFnKHggPSAxIC0gbSwgbnJvdyA9IGspCiAgZm9yIChpIGluIDE6KGsgLSAxKSkgewogICAgZm9yIChqIGluIChpKzEpOmspIHsKICAgICAgTVtpLCBqXSA8LSBtLyhrLTEpCiAgICAgIE1baiwgaV0gPC0gTVtpLCBqXQogICAgfQogIH0KICByZXR1cm4oTSkKfQoKc2FtcGxlX3R3b19hbGxlbGVzIDwtIGZ1bmN0aW9uKHApIHsKICBhbGxlbGVfMSA8LSAoKHJ1bmlmKDEpIDwgcCkgKyAxKSoxMAogIGFsbGVsZV8yIDwtIChydW5pZigxKSA8IHApICsgMQogIHJldHVybihhbGxlbGVfMSArIGFsbGVsZV8yKQp9CgptYWtlX3NhbXBsZSA8LSBmdW5jdGlvbihwLCBuX3NhbXBsZSkgewogIG5fcG9wcyA8LSBkaW0ocClbMl0KICBuX2xvY2kgPC0gZGltKHApWzFdCiAgbmFtZXMgPC0gcGFzdGUoIkxvY3VzIiwgc2VxKDE6bl9sb2NpKSwgc2VwID0gIiIpCiAgcG9wcyA8LSBudW1lcmljKG5fcG9wcypuX3NhbXBsZSkKICBjdCA8LSAxCiAgZm9yIChrIGluIDE6bl9wb3BzKSB7CiAgICBwb3B1bGF0aW9uIDwtIHBhc3RlKCJQb3B1bGF0aW9uIiwgaywgc2VwID0gIiIpCiAgICBmb3IgKGkgaW4gMTpuX3NhbXBsZSkgewogICAgICBwb3BzW2N0XSA8LSBwb3B1bGF0aW9uCiAgICAgIGN0IDwtIGN0ICsgMQogICAgfQogIH0KICBsb2N1c19kYXRhIDwtIG1hdHJpeChucm93ID0gbl9wb3BzKm5fc2FtcGxlLCBuY29sID0gbl9sb2NpKQogIGZvciAoaSBpbiAxOm5fbG9jaSkgewogICBjdCA8LSAxCiAgICBmb3IgKGsgaW4gMTpuX3BvcHMpIHsKICAgICAgZm9yIChuIGluIDE6bl9zYW1wbGUpIHsKICAgICAgICBsb2N1c19kYXRhW2N0LCBpXSA8LSBzYW1wbGVfdHdvX2FsbGVsZXMocFtpLCBrLCAxXSkKICAgICAgICBjdCA8LSBjdCArIDEKICAgICAgfQogICAgfQogIH0KICBkZiA8LSBkYXRhLmZyYW1lKGxvY3VzX2RhdGEpCiAgY29sbmFtZXMoZGYpIDwtIHBhc3RlKCJMb2N1cyIsIHNlcSgxOm5fbG9jaSksIHNlcCA9ICIiKQogIGRmJFBvcHVsYXRpb24gPC0gcG9wcwogIGRmIDwtIHJlbG9jYXRlKGRmLCBQb3B1bGF0aW9uKQogIHJldHVybihkZikKfQoKc2ltdWxhdGUgPC0gZnVuY3Rpb24obl9lLCBtLCBtdSwgbl9pc2xhbmRzLCBuX2xvY2ksIG5fZ2VuLCBuX3NhbXBsZSkgewogIHAgPC0gaW5pdGlhbGl6ZShuX2lzbGFuZHMsIG5fbG9jaSkKICBNIDwtIG1ha2Vfc3ltbWV0cmljX21hdHJpeChtLCBuX2lzbGFuZHMpCiAgViA8LSBtYWtlX3N5bW1ldHJpY19tYXRyaXgobXUsIDIpCiAgZ19zdCA8LSBudW1lcmljKG5fbG9jaSkKICBwX3N0YXIgPC0gYXJyYXkoZGltID0gYyhuX2xvY2ksIG5faXNsYW5kcywgMikpCiAgZm9yIChpIGluIDE6bl9nZW4pIHsKICAgIGZvciAoayBpbiAxOm5fbG9jaSkgewogICAgICBwX3N0YXJbaywgLCBdIDwtIE0gJSolIHBbaywgLCBdICUqJSBWCiAgICAgIGZvciAoaiBpbiAxOm5faXNsYW5kcykgewogICAgICAgIHBbaywgaiwgXSA8LSBybXVsdGlub20oMSwgMipuX2UsIHBfc3RhcltrLCBqLCBdKS8oMipuX2UpCiAgICAgIH0KICAgICAgbXVfcCA8LSBtZWFuKHBbaywgLCAxXSkKICAgICAgZ19zdFtrXSA8LSAoKG5faXNsYW5kcyAtIDEpL25faXNsYW5kcykqdmFyKHBbaywgLCAxXSkvKG11X3AqKDEgLSBtdV9wKSkKICAgIH0KICB9CiAgZGYgPC0gbWFrZV9zYW1wbGUocCwgbl9zYW1wbGUpCiAgcmV0dXJuKHdjKGRmKSRGU1QpCn0KCnJ1bl9zaW11bGF0aW9uIDwtIGZ1bmN0aW9uKG5fZSwgbSwgbXUsIG5faXNsYW5kcywgbl9sb2NpLCBuX2dlbiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgIG5fc2FtcGxlLCBuX3JlcGV0aXRpb25zKQp7CiAgZl9zdCA8LSBudW1lcmljKG5fcmVwZXRpdGlvbnMpCiAgZm9yIChpIGluIDE6bl9yZXBldGl0aW9ucykgewogICAgaWYgKG5fcmVwZXRpdGlvbnMgPiA1MCkgewogICAgICBjYXQoIi4iLCBzZXA9IiIpCiAgICAgIGlmICgoaSAlJSA1MCkgPT0gMCkgewogICAgICAgIGNhdChpLCAiXG4iLCBzZXAgPSIiKQogICAgICB9CiAgICB9CiAgICBmX3N0W2ldIDwtc2ltdWxhdGUobl9lLCBtLCBtdSwgbl9pc2xhbmRzLCBuX2xvY2ksIG5fZ2VuLCBuX3NhbXBsZSkKICB9CiAgcmV0dXJuKGZfc3QpCn0KCnBsb3Rfc2ltdWxhdGlvbiA8LSBmdW5jdGlvbihmX3N0LCBuX2UsIG0sIG11LCBuX2lzbGFuZHMpIHsKICBkZiA8LSBkYXRhLmZyYW1lKEZfc3QgPSBmX3N0KQogIHAgPC0gZ2dwbG90KGRmLCBhZXMoeCA9IEZfc3QpKSArCiAgICBnZW9tX2hpc3RvZ3JhbShiaW5zID0gMjAsIGFscGhhID0gMC40KSArCiAgICBnZW9tX3ZsaW5lKHhpbnRlcmNlcHQgPSBpbmZpbml0ZV9pc2xhbmQobl9lLCBtLCBtdSksCiAgICAgICAgICAgICAgIGxpbmV0eXBlID0gImRhc2hlZCIsCiAgICAgICAgICAgICAgIGNvbG9yID0gInJlZCIpICsKICAgIGdlb21fdmxpbmUoeGludGVyY2VwdCA9IGZpbml0ZV9pc2xhbmQobl9lLCBtLCBtdSwgbl9pc2xhbmRzKSwKICAgICAgICAgICAgICAgbGluZXR5cGUgPSAiZGFzaGVkIiwKICAgICAgICAgICAgICAgY29sb3IgPSAiYmx1ZSIpICsKICAgIGdndGl0bGUocGFzdGUoIk5fZSA9ICIsIG5fZSwgIiwgbSA9ICIsIG0sICIsIG11ID0gIiwgbXUsIAogICAgICAgICAgICAgICAgICAiLCBuX2lzbGFuZHMgPSAiLCBuX2lzbGFuZHMsIHNlcCA9ICIiKSkgKwogICAgdGhlbWVfYncoKQogIHJldHVybihwKQp9CgpmX3N0IDwtIHJ1bl9zaW11bGF0aW9uKDEwMCwgMC4wNSwgMWUtNCwgNSwgMTAsIDEwMDAsIDI1LCAxMDApCnBsb3Rfc2ltdWxhdGlvbihmX3N0LCAxMDAsIDAuMDUsIDFlLTQsIDUpCmBgYAoKVGhlIGRhc2hlZCByZWQgbGluZSBpcyB0aGUgcHJlZGljdGlvbiBmcm9tIHRoZSBpbmZpbml0ZSBpc2xhbmQgbW9kZWwuIFRoZSBkYXNoZWQgYmx1ZSBsaW5lIGlzIHRoZSBwcmVkaWN0aW9uIGZyb20gdGhlIGZpbml0ZSBpc2xhbmQgbW9kZWwuCgojIyBFeGVyY2lzZSA2CgpUaGUgbGFzdCBwbG90IHNob3dzIHRoYXQgbmVpdGhlciB0aGUgaW5maW5pdGUgaXNsYW5kIG5vciB0aGUgZmluaXRlIGlzbGFuZCBwcmVkaWN0aW9uIGNhcHR1cmVzIHRoZSByZXN1bHRzIG9mIHRoaXMgcGFydGljdWxhciBzaW11bGF0aW9uIHZlcnkgd2VsbCwgaXQgb25seSBkb2VzIHNvIG9uIGF2ZXJhZ2UgYW5kIHRoZXJlJ3MgYSBsb3Qgb2YgdmFyaWF0aW9uIGZyb20gb25lIHJlcGxpY2F0ZSB0byB0aGUgbmV4dC4gVGhpcyBvdXRjb21lIHJlZmxlY3RzIHRoZSAiZXZvbHV0aW9uYXJ5IiBvciAiZ2VuZXRpYyIgc2FtcGxpbmcgd2UgZGlzY3Vzc2VkIHdoZW4gY29tcGFyaW5nIE5laSdzICRHX3tTVH0kIHdpdGggV2VpciBhbmQgQ29ja2VyaGFtJ3MgJFx0aGV0YSQuIFRoaXMgd2Vla3MgbGFiIGV4ZXJjaXNlIHdpbGwgZXhwbG9yZSB0aGF0IHZhcmlhYmlsaXR5IGEgYml0IGZ1cnRoZXIgYW5kIGV4cGxvcmUgY29uZGlkdGlvbnMgdGhhdCBhZmZlY3QgdGhlIGFtb3VudCBvZiB2YXJpYWJpbGl0eSBhbmQgaG93IHVzZWZ1bCB0aGUgaW5maW5pdGUgaXNsYW5kIGFwcHJveGltYXRpb24gaXMuIFRvIGRvIHNvLCB5b3UnbGwgd2FudCB0byB1c2UgdGhlIGZvbGxvd2luZyBjb2RlLl5bTm90aWNlIHRoYXQgaW4gb3JkZXIgdG8gcnVuIHRoaXMgY29kZSwgeW91J2xsIGFsc28gbmVlZCB0byBydW4gdGhlIGNvZGUgYWJvdmUgc28gdGhhdCB0aGUgcmVsZXZhbnQgZnVuY3Rpb25zIGFyZSBsb2FkZWQgaW4gYFJgJ3MgbWVtb3J5Ll0gWW91J2xsIGJlIGNoYW5naW5nIHNvbWUgb3IgYWxsIG9mIAoKKiBgbl9sb2NpYCAtIFRoZSBudW1iZXIgb2YgbG9jaSBpbmNsdWRlZCBpbiB0aGUgZ2VuZXRpYyBzYW1wbGUsIAoqIGBuX3NhbXBsZWAgLSBUaGUgbnVtYmVyIG9mIChkaXBsb2lkKSBpbmRpdmlkdWFscyBzYW1wbGVkIGluIGVhY2ggcG9wdWxhdGlvbiwgCiogYG5fZ2VuYCAtIFRoZSBudW1iZXIgb2YgZ2VuZXJhdGlvbnMgZm9yIHdoaWNoIHRvIHJ1biB0aGUgc2ltdWxhdGlvbiwgYW5kCiogYG5fcmVwZXRpdGlvbnNgIC0gVGhlIG51bWJlciBvZiB0aW1lcyB0byByZXBlYXQgdGhlIHNpbXVsYXRpb24gZm9yIGFueSBzZXQgb2YgdGhlIGZpcnN0IHRocmVlIGNob2ljZXMuIFRoaXMgaXRlbSBjb3JyZXNwb25kcyB0byB0aGUgbnVtYmVyIG9mIGV2b2x1dGlvbmFyeSBvciBnZW5ldGljIHNhbXBsaW5nIGV2ZW50cyBpbmNsdWRlZCBpbiB5b3VyIHNpbXVsYXRpb24uCgpGb3IgZWFjaCBjaG9pY2Ugb2YgdGhlc2UgZm91ciBwYXJhbWV0ZXJzLCB0aGUgc2ltdWxhdGlvbiB3aWxsIHJ1biB0aHJvdWdoIGFsbCBjb21iaW5hdGlvbnMgb2YgYE5fZSA9ICgyNSwgMjAwLCAyNTAsIDUwMClgLCBgbSA9ICgwLjA1LCAwLjAxLCAwLjAwNSwgMC4wMDEpYCwgYG11ID0gKDAuMDAxLCAwLjAwMDEpYCwgYW5kIGBuX2lzbGFuZHMgPSAoMTAsIDI1LCA1MClgLgoKYGBge3J9Cm5fbG9jaSA8LSAxMApuX3NhbXBsZSA8LSAyNQpuX2dlbiA8LSAxMDAwCm5fcmVwZXRpdGlvbnMgPC0gMTAKCmRmIDwtIGRhdGEuZnJhbWUoTl9lID0gTkEsIG0gPSBOQSwgbXUgPSBOQSwgbl9pc2xhbmRzID0gTkEsIE9ic2VydmVkID0gTkEsCiAgICAgICAgICAgICAgICAgSW5maW5pdGUgPSBOQSwgRmluaXRlID0gTkEpCmZvciAobl9lIGluIGMoMjUsIDEwMCwgMjUwLCA1MDApKSB7CiAgZm9yIChtIGluIGMoMC4wNSwgMC4wMSwgMC4wMDUsIDAuMDAxKSkgewogICAgZm9yIChtdSBpbiBjKDAuMDAxLCAxZS00KSkgewogICAgICBmb3IgKG5faXNsYW5kcyBpbiBjKDEwLCAyNSwgNTApKSB7CiAgICAgICAgY2F0KCJOX2UgPSAiLCBuX2UsICIsIG0gPSAiLCBtLCAiLCBtdSA9ICIsIG11LCAKICAgICAgICAgICAgIm5faXNsYW5kcyA9ICIsIG5faXNsYW5kcywgIlxuIiApCiAgICAgICAgZl9zdCA8LSBydW5fc2ltdWxhdGlvbihuX2UsIG0sIG11LCBuX2lzbGFuZHMsIG5fbG9jaSwgbl9nZW4sIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbl9zYW1wbGUsIG5fcmVwZXRpdGlvbnMpCiAgICAgICAgZGYgPC0gYWRkX3JvdyhkZiwgCiAgICAgICAgICAgICAgICAgICAgICBOX2UgPSByZXAobl9lLCBuX3JlcGV0aXRpb25zKSwKICAgICAgICAgICAgICAgICAgICAgIG0gPSByZXAobSwgbl9yZXBldGl0aW9ucyksIAogICAgICAgICAgICAgICAgICAgICAgbXUgPSByZXAobXUsIG5fcmVwZXRpdGlvbnMpLCAKICAgICAgICAgICAgICAgICAgICAgIG5faXNsYW5kcyA9IHJlcChuX2lzbGFuZHMsIG5fcmVwZXRpdGlvbnMpLAogICAgICAgICAgICAgICAgICAgICAgT2JzZXJ2ZWQgPSBmX3N0LAogICAgICAgICAgICAgICAgICAgICAgSW5maW5pdGUgPSBpbmZpbml0ZV9pc2xhbmQobl9lLCBtLCBtdSksCiAgICAgICAgICAgICAgICAgICAgICBGaW5pdGUgPSBmaW5pdGVfaXNsYW5kKG5fZSwgbSwgbXUsIG5faXNsYW5kcykpCiAgICAgIH0KICAgIH0KICB9Cn0KZGYgPC0gZmlsdGVyKGRmLCAhaXMubmEoTl9lKSkKYGBgCgogUnVubmluZyBvbmUgc2V0IG9mIHNpbXVsYXRpb25zIGZvciBhIHBhcnRpY3VsYXIgY2hvaWNlIG9mIGBuX2xvY2lgLCBgbl9zYW1wbGVgLCBgbl9nZW5gLCBhbmQgYG5fcmVwZXRpdGlvbnNgIHRha2VzIGNsb3NlIHRvIGhhbGYgYW4gaG91ciBvbiBteSBNYWNCb29rLiBZb3UnbGwgZ2V0IGEgcHJpbnRvdXQgcGVyaW9kaWNhbGx5IHRoYXQgbGV0cyB5b3Uga25vdyB3aGF0IHRoZSBjdXJyZW50IHNldCBvZiBwYXJhbWV0ZXJzIGJlaW5nIHNpbXVsYXRlZCBpcywgYW5kIHlvdSdsbCBzZWUgdGhlIHNldCBvciBwYXJhbWV0ZXJzIHRoYXQncyBhbHJlYWR5IGJlZW4gY29tcGxldGVkLiBCZWNhdXNlIHJ1bm5pbmcgdGhlIHNpbXVsYXRpb24gZm9yIG9uZSBzZXQgb2YgcGFyYW1ldGVycyB0YWtlcyBzbyBsb25nLCB5b3UgY2FuJ3QgcG9zc2libHkgZXhwbG9yZSBhbGwgb2YgdGhlIGNvbWJpbmF0aW9ucyBvZiB0aG9zZSBwYXJhbWV0ZXJzIHlvdSBtaWdodCBiZSBpbnRlcmVzdGVkIGluLCBidXQgSSdkIGxpa2UgeW91IHRvIGV4cGxvcmUgYXQgbGVhc3QgZml2ZSBhbmQgYWRkcmVzcyB0aGUgZm9sbG93aW5nIHF1ZXN0aW9uczpeW0tlZXAgaW4gbWluZCB0aGF0IHlvdSdsbCBvbmx5IGJlIGFibGUgdG8gYW5zd2VyIHRoZXNlIHF1ZXN0aW9ucyBmb3IgdGhlIHNldCBvZiBzaW11bGF0aW9ucyB0aGF0IHlvdSBjb21wbGV0ZS4gSSdsbCBiZSBncmFkaW5nIHlvdXIgcmVzcG9uc2VzIG9uIHRoZSBzaW11bGF0aW9uIHJlc3VsdHMgdGhhdCB5b3Ugc2hvdywgbm90IG9uIHdoYXQgYW4gZXhoYXVzdGl2ZSBleGFtaW5hdGlvbiBvZiBhbGwgcG9zc2liaWxpdGllcyBtaWdodCBiZS5dCiAKMS4gQXJlIHRoZXJlIGNvbmRpdGlvbnMgdW5kZXIgd2hpY2ggdGhlIHByZWRpY3Rpb25zIG9mIHRoZSBpbmZpbml0ZSBpc2xhbmQgYW5kIGZpbml0ZSBpc2xhbmQgbW9kZWwgYXJlIHNpbWlsYXIgZW5vdWdoIHRoYXQgd2UgZG9uJ3QgbmVlZCB0byB3b3JyeSBhYm91dCB0aGUgYWRkZWQgbWF0aGVtYXRpY2FsIGNvbXBsZXhpdHkgb2YgdGhlIGZpbml0ZSBpc2xhbmQgbW9kZWw/CgoyLiBIb3cgY2xvc2UgaXMgdGhlIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIG9ic2VydmVkIGVzdGltYXRlcyBvZiAkRl97U1R9JCBmcm9tIHRoZSBzaW11bGF0aW9ucyBhbmQgdGhvc2UgcHJlZGljdGVkIGZyb20gdGhlIGluZmluaXRlIGlzbGFuZCBtb2RlbD8gZnJvbSB0aGUgZmluaXRlIGlzbGFuZCBtb2RlbD8KCjMuIFVuZGVyIHdoYXQgY29uZGl0aW9ucyBpcyB0aGUgb2JzZXJ2ZWQgdmFyaWF0aW9uIGluICRGX3tTVH0kIHJlbGF0aXZlbHkgc21hbGw/CgojIyMgQSBmZXcgaGludHMKClRoZSBlYXNpZXN0IHdheSB0byBydW4gZGlmZmVyZW50IGNvbWJpbmF0aW9ucyBvZiBwYXJhbWV0ZXJzIGlzIHRvIGNvcHkgdGhlIGNvZGUgYmxvY2sgYWJvdmUgYW5kIHJlcGxhY2UgYG5fbG9jaWAsIGBuX3NhbXBsZWAsIGBuX2dlbmAsIGFuZCBgbl9yZXBldGl0aW9uc2Agd2l0aCBuZXcgY2hvaWNlcy4gVG8ga2VlcCB0cmFjayBvZiB3aGF0IHlvdSdyZSBkb2luZywgSSByZWNvbW1lbmQgZG9pbmcgdGhhdCBmb3Igb25lIGNvbWJpbmF0aW9uIG9mIHBhcmFtZXRlcnMsIGV4YW1pbmluZyB0aGUgcmVzdWx0cyBhcyBkZXNjcmliZWQgYmVsb3csIGFuZCBtb3Zpbmcgb24gdG8gYSBuZXcgc2V0IG9mIHBhcmFtZXRlciAod2l0aCBhIG5ldyBjb2RlIGJsb2NrKSBhZnRlciB0aGF0LgoKWW91IGNhbiBwbG90IHRoZSBvYnNlcnZlZCAkRl97U1R9JCB2ZXJzdXMgdGhlICRGX3tTVH0kIHByZWRpY3RlZCBmcm9tIGVpdGhlciBtb2RlbCB1c2luZyB0aGUgY29kZSBiZWxvdy5eW1RoZSBkaWFnb25hbCByZWQgZGFzaGVkIGxpbmUgaXMgdGhlIDE6MSBsaW5lLiBFdmVyeSBwb2ludCBzaG91bGQgZmFsbCBvbiB0aGlzIGxpbmUgaWYgb2JzZXJ2ZWQgZXhhY3RseSBtYXRjaGVzIHRoZSBwcmVkaWN0aW9uLl0gSW4gYWRkaXRpb24gdG8gc2hvd2luZyBob3cgd2VsbCB0aGUgc2ltdWxhdGlvbnMgbWF0Y2ggdGhlIHByZWRpY3Rpb25zLCB5b3UgY2FuIGdldCBhIGZlZWwgZm9yIGhvdyBtdWNoIHZhcmlhYmlpdHkgdGhlcmUgaXMgYW1vbmcgdGhlIHNpbXVsYXRpb25zIGJ5IHNlZWluZyBob3cgc2NhdHRlcmQgdGhlIHBvaW50cyBhcmUuCgpgYGB7cn0KIyMgZm9yIHRoZSBpbmZpbml0ZSBpc2xhbmQgbW9kZWwKIyMKcCA8LSBnZ3Bsb3QoZGYsIGFlcyh4ID0gSW5maW5pdGUsIHkgPSBPYnNlcnZlZCkpICsKICBnZW9tX3BvaW50KCkgKwogIGdlb21fYWJsaW5lKGludGVyY2VwdCA9IDAsIHNsb3BlID0gMSwgbGluZXR5cGUgPSAiZGFzaGVkIiwgCiAgICAgICAgICAgICAgY29sb3IgPSAicmVkIikgKyB0aGVtZV9idygpCnAKIyMgZm9yIHRoZSBmaW5pdGUgaXNsYW5kIG1vZGVsCiMjCnAgPC0gZ2dwbG90KGRmLCBhZXMoeCA9IEZpbml0ZSwgeSA9IE9ic2VydmVkKSkgKwogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9hYmxpbmUoaW50ZXJjZXB0ID0gMCwgc2xvcGUgPSAxLCBsaW5ldHlwZSA9ICJkYXNoZWQiLCAKICAgICAgICAgICAgICBjb2xvciA9ICJyZWQiKSArIHRoZW1lX2J3KCkKcApgYGAKCklmIHlvdSdkIGxpa2UgYSBtb3JlIHF1YW50aXRhdGl2ZSB3YXkgdG8gY29tcGFyZSB0aGUgbW9kZWxzLF5bQW5kIEknZCBlbmNvdXJhZ2UgeW91IHRvIHRha2UgYSBtb3JlIHF1YW50aXRhdGl2ZSBhcHByb2FjaF0gYSBzaW1wbGUgd2F5IGlzIHRvIHJ1biBsaW5lYXIgcmVncmVzc2lvbnMgb2YgYE9ic2VydmVkYCBvbiBgSW5maW5pdGVgIGFuZCBgRXhwZWN0ZWRgIGxpa2UgdGhpczoKCmBgYHtyfQpzdW1tYXJ5KGxtKE9ic2VydmVkIH4gSW5maW5pdGUsIGRhdGEgPSBkZikpCnN1bW1hcnkobG0oT2JzZXJ2ZWQgfiBGaW5pdGUsIGRhdGEgPSBkZikpCmBgYApJZiBwcmVkaWN0aW9ucyB3ZXJlIHBlcmZlY3QgdGhlIGAoSW50ZXJjZXB0KWAgdGVybSBpbiB0aGUgcmVncmVzc2lvbiB3b3VsZCBiZSAwLCBhbmQgdGhlIG90aGVyIHRlcm0gKGBJbmZpbml0ZWAgaW4gdGhlIGZpcnN0IHJlZ3Jlc3Npb24gYW5kIGBGaW5pdGVgIGluIHRoZSBzZWNvbmQpIHdvdWxkIGJlIDEuIEdpdmVuIHRoZSB2YXJpYWJpbGl0eSBvZiB0aGUgc2ltdWxhdGlvbnMsIHlvdSB3b24ndCBzZWUgbnVtYmVycyB0aGF0IGFyZSBleGFjdGx5IDAgb3IgMS4gWW91IGNhbiBqdWRnZSB3aGV0aGVyIHRoZXkgYXJlICJjbG9zZSIgYnkgbm90aWNpbmcgd2hldGhlciB0aGUgbnVtYmVyIGluIHRoZSBgRXN0aW1hdGVgIGNvbHVtbiBpcyBtb3JlIHRoYW4gdHdvIHN0YW5kYXJkIGVycm9ycyBhd2F5IGZyb20gd2hhdCB5b3UgcHJlZGljdC4KClRoZSBgcmVzaWR1YWwgc3RhbmRhcmQgZXJyb3JgIGJlbG93IHRoZSB0YWJsZSBtZWFzdXJlcyBob3cgbXVjaCBlcnJvciB0aGVyZSBpcyBhcm91bmQgdGhlIHJlZ3Jlc3Npb24sIGkuZS4sIGl0IGdpdmVzIHlvdSBhIHdheSB0byBjb21wYXJlIHF1YW50aXRhdGl2ZWx5IGhvdyBtdWNoIHZhcmlhdGlvbiB0aGVyZSBpcyBpbiAkRl97U1R9JC4=