We use ms() from phyclust to simulate samples from the coalescent and various functions from ape to display the coalescent tree and calculate statistics from it. Let’s start with a really simple example of constructing a coalescent sample of size 10. The nsam argument is the number of samples, and the opts = "-T" argument tell ms() to return a coalescent tree. We then convert it, using read.tree() to a format that we can plot()

The coalescent in R

library(ape)
library(phyclust)

rm(list = ls())

## set random number seed so that same tree is produced every time this code
## is run
##
set.seed(1234)

ms_out <- ms(nsam = 10, opts = "-T")
ms_tree_1 <- read.tree(text = ms_out)
plot(ms_tree_1)

You’ll notice that the tip labels run from s1 through s10. Each corresponds to a different allele. That was pretty easy, but we can do a bit more. We can ask how “deep” the tree is, i.e., how far back in time we have to go to find the most recent common ancestor of all the alleles in our sample.

Branching times

branching.times(ms_tree_1)[1]
      11 
1.112965 

You’re probably wondering about the [1] after branching.times(). Well, branching.times() returns a vector of all of the branching times in the tree.

branching.times(ms_tree_1)
        11         12         13         14         15         16         17         18         19 
1.11296475 0.79145014 0.25495386 0.03760511 0.15911412 0.03034905 0.09305522 0.05205787 0.02415735 

The numbers 11-19 are the node numbers in the tree above.

plot(ms_tree_1)
nodelabels()

As you can see, node 11 (which is the first one in the list), is the deepest node, i.e., the most recent common ancestor of all of the alleles in our sample.

Scaling of branching times

The other thing you may be wondering is how to interpret the number 1.1129647 that corresponds to the time of the most recent common ancestor.1 To explain that I have to point out something that you may have missed when we called ms(): We didn’t specify a population size. How can we get away with that, since I told you that drift always depends on the population size?

Well, remember what you know2 about the coalesent process. The expected time to coalescence of all alleles is \(4N_e\). ms() reports branching time in “coalescent units” where 1 unit equals \(4N_e\). So if branching.times(ms_tree_1)[1] is 1.1129647 and the effective size of our population is 25, then the time (number of generations before the present) to the most recent common ancestor is 111.2964749. Notice that the time isn’t an integer the way you’d expect it to be. That’s because of an approximation that is generally used in implementing the coalescent in software. If you want to turn it into an integer, you can do this:

round(4*25*branching.times(ms_tree_1)[1])
 11 
111 

Whether you round it or not, you’ll see that the most recent common ancestor of the alleles in our sample didn’t occur exactly 100 generations ago as we’d expect. If, however, we repeat that simulation a bunch of times, you can see that we come pretty close - on average.

library(ggplot2)

N_e = 25

c_time <- numeric(0)
for (i in 1:1000) {
  ms_out <- ms(nsam = N_e, opts = "-T")
  ms_tree <- read.tree(text = ms_out)
  c_time[i] <- 4*N_e*branching.times(ms_tree)[1]
}
p <- ggplot(data.frame(t = c_time), aes(x = t)) +
  geom_histogram(bins = 50, alpha = 0.6) +
  geom_vline(xintercept = 4*N_e, linetype = "dashed", color = "red") + 
  theme_bw()
p

We expect a coalescence time of 100 and our observed average coalescence time is 95.2170163. Not too bad. Notice that the standard deviation of the coalescence time is 50.9947031. That’s a lot of variability in coalescence time, which re-emphasizes a point I’ve made many times: There is a lot of variability associated with drift. While the expectations we focus on provide a useful point of comparison, they can delude us into thinking that we know more than we actually do.

The coalescent with migration

What happens when we have a subdivided population so that we have several populations exchanging genes? Here’s how we simulate a finite island model with three populations, local population sizes of 10 in each population, and \(N_em = 2\).3

options(tidyverse.quiet = TRUE)
library(tidyverse)
library(RColorBrewer)

get_pop <- function(tree, sample_sizes, k) {
  idx <- as.numeric(gsub("^s(.*)$", "\\1", tree$tip.label))
  cum <- 0
  for (i in 1:length(sample_sizes)) {
    if (idx[k] < cum + sample_sizes[i] + 1) {
      retval <- i
      break
    } else {
      cum <- cum + sample_sizes[i]
    }
  }
  return(i)
}

tipcolors <- function(tree, sample_sizes) {
  my_colors <- brewer.pal(length(sample_sizes), "Set1")
  colors <- numeric(length(sample_sizes))
  for (i in 1:sum(sample_sizes)) {
    colors[i] <- my_colors[get_pop(tree, sample_sizes, i)]
  }
  return(colors)
}

## Note: sample sizes should be multiplied by 2 before calling
## island for diploid samples
##
island <- function(sample_sizes, ne_m) {
  opt_string <- paste("-T -I ", length(sample_sizes), " ", sep = "")
  for (i in 1:length(sample_sizes)) {
    opt_string <- paste(opt_string, sample_sizes[i], " ", sep = "")
  }
  opt_string <- paste(opt_string, ne_m, "\n", sep = "")
  ms_out <- ms(nsam = sum(sample_sizes), nreps = 1, opts = opt_string)
  return(ms_out)  
}

plot_island <- function(sample_sizes, ne_m) {
  ms_out <- island(2*sample_sizes, ne_m)
  ms_tree <- read.tree(text = ms_out)
  plot(ms_tree, 
       show.tip.label = FALSE)
  tiplabels(pch = 19, cex = 0.75, 
            col = tipcolors(ms_tree, 
                            2*sample_sizes))
  return(branching.times(ms_tree)[1])
}

time <- plot_island(sample_sizes = c(5, 5, 5), ne_m = 10)

The colors correspond to the population from which each sample was collected. plot_island() returns the scaled time to the most recent common ancestor, 10.5703715. We are implicitly assuming that the effective population size is the same in each local population.4 The scaling is in terms of the product of the local effective population size and the number of populations, i.e., 1 coalescent unit = \(4N_ek\), where \(k\) is the number of populations.

Notice how different the result is if I set \(N_em = 0.5\) instead of \(N_em = 2\).

time <- plot_island(sample_sizes = c(5, 5, 5), ne_m = 0.1)

The alleles are now nicely arranged into populations. Does it surprise you that the populations in which alleles occur form monophyletic groups when \(N_em \ll 1\) and that they don’t when \(N_em \gg 1\).5

Lab 7

You will be performing another set of simulations this week to compare coalescence times in two scenarios:

  1. A finite island model of migration.
  2. A one-dimensional stepping stone model of migration.

You saw both the finite island model and the one-dimensional stepping stone model last week. As a reminder, in a one-dimensional stepping stone model the populations are arranged in a lineary array and only those populations that are adjacent to one another can exchange migrants. If \(m\) is the migration rate, i.e., the fraction of a population composed of migrants then the fraction of population \(i\) derived from population \(i-1\) is \(\frac{m}{2}\) and the fraction of population \(i\) derived from population \(i+1\) is \(\frac{m}{2}\).6

Use the functions below to explore the difference in coalescence times for finite island models and one-dimensional stepping stone models of migration, and answer the following questions:

  1. How does the number of populations included affect the avearge time to coalescence of all alleles? Try at least one case in which the number of populations is relatively small, i.e., 10 or fewer, and one in which it is moderately large, i.e., 25 or more.

  2. How does the migration rate affect the average time to coalescence of all alleles? Does it depend on whether migration is better approximated by a finite island model or a one-dimensional stepping stone model?

  3. Are there consistent differences between the average time to coalescence in a finite island model and a one-dimensional stepping stone model? If there are, what might explain the differences that you see?

Hints

run_simulations() will automatically keep the number of populations in both models the same to ensure that you can always make appropriate comparisons of the models. It will also set the local effective population size to 25, and it sets the number of replications to 1000 by default. You might want to run the function once with n_reps = 100 to get a feel for how long it will take the simulation to run on your computer before you begin the full-scale simulations

run_simulations() returns a data frame7 with two columns: Model and Time. If you’re interested, you can use that to examine the median time to coalescence (rather than the mean) and the variance (or standard deviation) in coalescence times. You’ll notice that run_simulation() automatically prints out the mean coalesence times for you.

In answering question #3 keep in mind that your answer might depend on how many populations there are.8

## one-dimensional stepping stone
##
one_d_stepping_stone <- function(n_e, m, n_pops) {
  stopifnot((m > 0) && (m < 1))
  m_matrix <- diag(1 - m, nrow = n_pops)
  m_matrix[1, 2] <- m
  m_matrix[n_pops, n_pops - 1] <- m
  for (i in 2:(n_pops - 1)) {
    m_matrix[i, i - 1] <- m/2
    m_matrix[i, i + 1] <- m/2
  }
  opt_string <- paste("-T -I ", n_pops, " ", sep = "")
  for (i in 1:n_pops) {
    opt_string <- paste(opt_string, 2*n_e, " ", sep = "")
  }
  opt_string <- paste(opt_string, "-ma", sep = "")
  ## transpose m_matrix before converting to vector to get vector from matrix
  ## by row instead of by column
  ##
  m_vector <- 4*n_e*c(t(m_matrix))
  for ( i in 1:length(m_vector)) {
    opt_string <- paste(opt_string, " ", m_vector[i], sep = "")
  }
  ms_out <- ms(nsam = 2*n_e*n_pops, nreps = 1, opts = opt_string)
  return(ms_out)
}

run_simulation <- function(n_pops, m, n_reps = 1000) {
  N_e = 25
  pop_sizes <- rep(N_e, n_pops)
  df <- tibble(Model = NA, Time = NA)
  for (i in 1:n_reps) {
    ms_out <- island(pop_sizes, N_e*m)
    ms_tree <- read.tree(text = ms_out)
    df <- add_row(df,
                  Model = "Island",
                  Time = (4*N_e*n_pops)*branching.times(ms_tree)[1])
    ms_out <- one_d_stepping_stone(N_e, m, n_pops)
    ms_tree <- read.tree(text = ms_out)
    df <- add_row(df,
                  Model = "1-d",
                  Time = (4*N_e*n_pops)*branching.times(ms_tree)[1])
  }
  df <- filter(df, !is.na(Model))
  p <- ggplot(df, aes(x = Time, fill = Model)) +
    geom_histogram(position = "identity", bins = n_reps/10, alpha = 0.4) +
    ggtitle(paste("n_pops = ", n_pops, ", m = ", m)) +
    theme_bw()
  print(p)
  sum <- df %>% group_by(Model) %>%
    summarize(Mean_Time = mean(Time))
  print(sum)
  return(df)
}

  1. Remember that when using the coalescent, time runs backwards. So the time of the most recent common ancestor is a time in the past.↩︎

  2. or what I told you↩︎

  3. Note: You’ll need to install RColorBrewer if you want to run this code.↩︎

  4. There is a way to relax this assumption, but we won’t take advantage of it here.↩︎

  5. Note: Read \(\ll\) as “much less than” and \(\gg\) as “much greater than.”↩︎

  6. Note: For the first population in the array, i.e., population 1, the fraction of the population derived from population 2 is \(m\). Similarly, if there are \(k\) populations in the arry, the fraction of population \(k\) that is derived from population \(k-1\) is \(m\).↩︎

  7. Well, actually a tibble↩︎

  8. Why else would I have asked you to look both at one example in which tne number of populations is 10 or fewer and another in which the number of populations is 25 or more?↩︎

LS0tCnRpdGxlOiAiRXhwbG9yaW5nIHRoZSBjb2FsZXNjZW50IgpvdXRwdXQ6IAogIGh0bWxfbm90ZWJvb2s6CiAgICB0b2M6IHllcwogICAgdG9jX2Zsb2F0OiB0cnVlCi0tLQoKV2UgdXNlIGBtcygpYCBmcm9tIGBwaHljbHVzdGAgdG8gc2ltdWxhdGUgc2FtcGxlcyBmcm9tIHRoZSBjb2FsZXNjZW50IGFuZCB2YXJpb3VzIGZ1bmN0aW9ucyBmcm9tIGBhcGVgIHRvIGRpc3BsYXkgdGhlIGNvYWxlc2NlbnQgdHJlZSBhbmQgY2FsY3VsYXRlIHN0YXRpc3RpY3MgZnJvbSBpdC4gTGV0J3Mgc3RhcnQgd2l0aCBhIHJlYWxseSBzaW1wbGUgZXhhbXBsZSBvZiBjb25zdHJ1Y3RpbmcgYSBjb2FsZXNjZW50IHNhbXBsZSBvZiBzaXplIDEwLiBUaGUgYG5zYW1gIGFyZ3VtZW50IGlzIHRoZSBudW1iZXIgb2Ygc2FtcGxlcywgYW5kIHRoZSBgb3B0cyA9ICItVCJgIGFyZ3VtZW50IHRlbGwgYG1zKClgIHRvIHJldHVybiBhIGNvYWxlc2NlbnQgdHJlZS4gV2UgdGhlbiBjb252ZXJ0IGl0LCB1c2luZyBgcmVhZC50cmVlKClgIHRvIGEgZm9ybWF0IHRoYXQgd2UgY2FuIGBwbG90KClgICAKCiMjIFRoZSBjb2FsZXNjZW50IGluIGBSYAoKYGBge3J9CmxpYnJhcnkoYXBlKQpsaWJyYXJ5KHBoeWNsdXN0KQoKcm0obGlzdCA9IGxzKCkpCgojIyBzZXQgcmFuZG9tIG51bWJlciBzZWVkIHNvIHRoYXQgc2FtZSB0cmVlIGlzIHByb2R1Y2VkIGV2ZXJ5IHRpbWUgdGhpcyBjb2RlCiMjIGlzIHJ1bgojIwpzZXQuc2VlZCgxMjM0KQoKbXNfb3V0IDwtIG1zKG5zYW0gPSAxMCwgb3B0cyA9ICItVCIpCm1zX3RyZWVfMSA8LSByZWFkLnRyZWUodGV4dCA9IG1zX291dCkKcGxvdChtc190cmVlXzEpCmBgYApZb3UnbGwgbm90aWNlIHRoYXQgdGhlIHRpcCBsYWJlbHMgcnVuIGZyb20gYHMxYCB0aHJvdWdoIGBzMTBgLiBFYWNoIGNvcnJlc3BvbmRzIHRvIGEgZGlmZmVyZW50IGFsbGVsZS4gVGhhdCB3YXMgcHJldHR5IGVhc3ksIGJ1dCB3ZSBjYW4gZG8gYSBiaXQgbW9yZS4gV2UgY2FuIGFzayBob3cgImRlZXAiIHRoZSB0cmVlIGlzLCBpLmUuLCBob3cgZmFyIGJhY2sgaW4gdGltZSB3ZSBoYXZlIHRvIGdvIHRvIGZpbmQgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3RvciBvZiBhbGwgdGhlIGFsbGVsZXMgaW4gb3VyIHNhbXBsZS4KCiMjIyBCcmFuY2hpbmcgdGltZXMKCmBgYHtyfQpicmFuY2hpbmcudGltZXMobXNfdHJlZV8xKVsxXQpgYGAKCllvdSdyZSBwcm9iYWJseSB3b25kZXJpbmcgYWJvdXQgdGhlIGBbMV1gIGFmdGVyIGBicmFuY2hpbmcudGltZXMoKWAuIFdlbGwsIGBicmFuY2hpbmcudGltZXMoKWAgcmV0dXJucyBhIHZlY3RvciBvZiAqYWxsKiBvZiB0aGUgYnJhbmNoaW5nIHRpbWVzIGluIHRoZSB0cmVlLgoKYGBge3J9CmJyYW5jaGluZy50aW1lcyhtc190cmVlXzEpCmBgYAoKVGhlIG51bWJlcnMgMTEtMTkgYXJlIHRoZSBub2RlIG51bWJlcnMgaW4gdGhlIHRyZWUgYWJvdmUuCgpgYGB7cn0KcGxvdChtc190cmVlXzEpCm5vZGVsYWJlbHMoKQpgYGAKCkFzIHlvdSBjYW4gc2VlLCBub2RlIDExICh3aGljaCBpcyB0aGUgZmlyc3Qgb25lIGluIHRoZSBsaXN0KSwgaXMgdGhlIGRlZXBlc3Qgbm9kZSwgaS5lLiwgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3RvciBvZiBhbGwgb2YgdGhlIGFsbGVsZXMgaW4gb3VyIHNhbXBsZS4gCgojIyMgU2NhbGluZyBvZiBicmFuY2hpbmcgdGltZXMKClRoZSBvdGhlciB0aGluZyB5b3UgbWF5IGJlIHdvbmRlcmluZyBpcyBob3cgdG8gaW50ZXJwcmV0IHRoZSBudW1iZXIgYHIgYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWVfMSlbMV1gIHRoYXQgY29ycmVzcG9uZHMgdG8gdGhlIHRpbWUgb2YgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3Rvci5eW1JlbWVtYmVyIHRoYXQgd2hlbiB1c2luZyB0aGUgY29hbGVzY2VudCwgdGltZSBydW5zIGJhY2t3YXJkcy4gU28gdGhlIHRpbWUgb2YgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3RvciBpcyBhIHRpbWUgaW4gdGhlIHBhc3QuXSBUbyBleHBsYWluIHRoYXQgSSBoYXZlIHRvIHBvaW50IG91dCBzb21ldGhpbmcgdGhhdCB5b3UgbWF5IGhhdmUgbWlzc2VkIHdoZW4gd2UgY2FsbGVkIGBtcygpYDogV2UgZGlkbid0IHNwZWNpZnkgYSBwb3B1bGF0aW9uIHNpemUuIEhvdyBjYW4gd2UgZ2V0IGF3YXkgd2l0aCB0aGF0LCBzaW5jZSBJIHRvbGQgeW91IHRoYXQgZHJpZnQgKmFsd2F5cyogZGVwZW5kcyBvbiB0aGUgcG9wdWxhdGlvbiBzaXplPwoKV2VsbCwgcmVtZW1iZXIgd2hhdCB5b3Uga25vd15bb3Igd2hhdCBJIHRvbGQgeW91XSBhYm91dCB0aGUgY29hbGVzZW50IHByb2Nlc3MuIFRoZSBleHBlY3RlZCB0aW1lIHRvIGNvYWxlc2NlbmNlIG9mIGFsbCBhbGxlbGVzIGlzICQ0Tl9lJC4gYG1zKClgIHJlcG9ydHMgYnJhbmNoaW5nIHRpbWUgaW4gImNvYWxlc2NlbnQgdW5pdHMiIHdoZXJlIDEgdW5pdCBlcXVhbHMgJDROX2UkLiBTbyBpZiBgYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWVfMSlbMV1gIGlzIGByIGJyYW5jaGluZy50aW1lcyhtc190cmVlXzEpWzFdYCBhbmQgdGhlIGVmZmVjdGl2ZSBzaXplIG9mIG91ciBwb3B1bGF0aW9uIGlzIDI1LCB0aGVuIHRoZSB0aW1lIChudW1iZXIgb2YgZ2VuZXJhdGlvbnMgYmVmb3JlIHRoZSBwcmVzZW50KSB0byB0aGUgbW9zdCByZWNlbnQgY29tbW9uIGFuY2VzdG9yIGlzIGByIDQqMjUqYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWVfMSlbMV1gLiBOb3RpY2UgdGhhdCB0aGUgdGltZSBpc24ndCBhbiBpbnRlZ2VyIHRoZSB3YXkgeW91J2QgZXhwZWN0IGl0IHRvIGJlLiBUaGF0J3MgYmVjYXVzZSBvZiBhbiBhcHByb3hpbWF0aW9uIHRoYXQgaXMgZ2VuZXJhbGx5IHVzZWQgaW4gaW1wbGVtZW50aW5nIHRoZSBjb2FsZXNjZW50IGluIHNvZnR3YXJlLiBJZiB5b3Ugd2FudCB0byB0dXJuIGl0IGludG8gYW4gaW50ZWdlciwgeW91IGNhbiBkbyB0aGlzOgoKYGBge3J9CnJvdW5kKDQqMjUqYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWVfMSlbMV0pCmBgYAoKV2hldGhlciB5b3Ugcm91bmQgaXQgb3Igbm90LCB5b3UnbGwgc2VlIHRoYXQgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3RvciBvZiB0aGUgYWxsZWxlcyBpbiBvdXIgc2FtcGxlIGRpZG4ndCBvY2N1ciBleGFjdGx5IDEwMCBnZW5lcmF0aW9ucyBhZ28gYXMgd2UnZCBleHBlY3QuIElmLCBob3dldmVyLCB3ZSByZXBlYXQgdGhhdCBzaW11bGF0aW9uIGEgYnVuY2ggb2YgdGltZXMsIHlvdSBjYW4gc2VlIHRoYXQgd2UgY29tZSBwcmV0dHkgY2xvc2UgLSBvbiBhdmVyYWdlLgoKYGBge3J9CmxpYnJhcnkoZ2dwbG90MikKCk5fZSA9IDI1CgpjX3RpbWUgPC0gbnVtZXJpYygwKQpmb3IgKGkgaW4gMToxMDAwKSB7CiAgbXNfb3V0IDwtIG1zKG5zYW0gPSBOX2UsIG9wdHMgPSAiLVQiKQogIG1zX3RyZWUgPC0gcmVhZC50cmVlKHRleHQgPSBtc19vdXQpCiAgY190aW1lW2ldIDwtIDQqTl9lKmJyYW5jaGluZy50aW1lcyhtc190cmVlKVsxXQp9CnAgPC0gZ2dwbG90KGRhdGEuZnJhbWUodCA9IGNfdGltZSksIGFlcyh4ID0gdCkpICsKICBnZW9tX2hpc3RvZ3JhbShiaW5zID0gNTAsIGFscGhhID0gMC42KSArCiAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ID0gNCpOX2UsIGxpbmV0eXBlID0gImRhc2hlZCIsIGNvbG9yID0gInJlZCIpICsgCiAgdGhlbWVfYncoKQpwCmBgYAoKV2UgZXhwZWN0IGEgY29hbGVzY2VuY2UgdGltZSBvZiBgciA0Kk5fZWAgYW5kIG91ciBvYnNlcnZlZCBhdmVyYWdlIGNvYWxlc2NlbmNlIHRpbWUgaXMgYHIgbWVhbihjX3RpbWUpYC4gTm90IHRvbyBiYWQuIE5vdGljZSB0aGF0IHRoZSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgdGhlIGNvYWxlc2NlbmNlIHRpbWUgaXMgYHIgc2QoY190aW1lKWAuIFRoYXQncyBhIGxvdCBvZiB2YXJpYWJpbGl0eSBpbiBjb2FsZXNjZW5jZSB0aW1lLCB3aGljaCByZS1lbXBoYXNpemVzIGEgcG9pbnQgSSd2ZSBtYWRlIG1hbnkgdGltZXM6IFRoZXJlIGlzIGEgKioqbG90KioqIG9mIHZhcmlhYmlsaXR5IGFzc29jaWF0ZWQgd2l0aCBkcmlmdC4gV2hpbGUgdGhlIGV4cGVjdGF0aW9ucyB3ZSBmb2N1cyBvbiBwcm92aWRlIGEgdXNlZnVsIHBvaW50IG9mIGNvbXBhcmlzb24sIHRoZXkgY2FuIGRlbHVkZSB1cyBpbnRvIHRoaW5raW5nIHRoYXQgd2Uga25vdyBtb3JlIHRoYW4gd2UgYWN0dWFsbHkgZG8uCgojIyMgVGhlIGNvYWxlc2NlbnQgd2l0aCBtaWdyYXRpb24KCldoYXQgaGFwcGVucyB3aGVuIHdlIGhhdmUgYSBzdWJkaXZpZGVkIHBvcHVsYXRpb24gc28gdGhhdCB3ZSBoYXZlIHNldmVyYWwgcG9wdWxhdGlvbnMgZXhjaGFuZ2luZyBnZW5lcz8gSGVyZSdzIGhvdyB3ZSBzaW11bGF0ZSBhIGZpbml0ZSBpc2xhbmQgbW9kZWwgd2l0aCB0aHJlZSBwb3B1bGF0aW9ucywgbG9jYWwgcG9wdWxhdGlvbiBzaXplcyBvZiAxMCBpbiBlYWNoIHBvcHVsYXRpb24sIGFuZCAkTl9lbSA9IDIkLl5bTm90ZTogWW91J2xsIG5lZWQgdG8gaW5zdGFsbCBgUkNvbG9yQnJld2VyYCBpZiB5b3Ugd2FudCB0byBydW4gdGhpcyBjb2RlLl0KCmBgYHtyfQpvcHRpb25zKHRpZHl2ZXJzZS5xdWlldCA9IFRSVUUpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KFJDb2xvckJyZXdlcikKCmdldF9wb3AgPC0gZnVuY3Rpb24odHJlZSwgc2FtcGxlX3NpemVzLCBrKSB7CiAgaWR4IDwtIGFzLm51bWVyaWMoZ3N1YigiXnMoLiopJCIsICJcXDEiLCB0cmVlJHRpcC5sYWJlbCkpCiAgY3VtIDwtIDAKICBmb3IgKGkgaW4gMTpsZW5ndGgoc2FtcGxlX3NpemVzKSkgewogICAgaWYgKGlkeFtrXSA8IGN1bSArIHNhbXBsZV9zaXplc1tpXSArIDEpIHsKICAgICAgcmV0dmFsIDwtIGkKICAgICAgYnJlYWsKICAgIH0gZWxzZSB7CiAgICAgIGN1bSA8LSBjdW0gKyBzYW1wbGVfc2l6ZXNbaV0KICAgIH0KICB9CiAgcmV0dXJuKGkpCn0KCnRpcGNvbG9ycyA8LSBmdW5jdGlvbih0cmVlLCBzYW1wbGVfc2l6ZXMpIHsKICBteV9jb2xvcnMgPC0gYnJld2VyLnBhbChsZW5ndGgoc2FtcGxlX3NpemVzKSwgIlNldDEiKQogIGNvbG9ycyA8LSBudW1lcmljKGxlbmd0aChzYW1wbGVfc2l6ZXMpKQogIGZvciAoaSBpbiAxOnN1bShzYW1wbGVfc2l6ZXMpKSB7CiAgICBjb2xvcnNbaV0gPC0gbXlfY29sb3JzW2dldF9wb3AodHJlZSwgc2FtcGxlX3NpemVzLCBpKV0KICB9CiAgcmV0dXJuKGNvbG9ycykKfQoKIyMgTm90ZTogc2FtcGxlIHNpemVzIHNob3VsZCBiZSBtdWx0aXBsaWVkIGJ5IDIgYmVmb3JlIGNhbGxpbmcKIyMgaXNsYW5kIGZvciBkaXBsb2lkIHNhbXBsZXMKIyMKaXNsYW5kIDwtIGZ1bmN0aW9uKHNhbXBsZV9zaXplcywgbmVfbSkgewogIG9wdF9zdHJpbmcgPC0gcGFzdGUoIi1UIC1JICIsIGxlbmd0aChzYW1wbGVfc2l6ZXMpLCAiICIsIHNlcCA9ICIiKQogIGZvciAoaSBpbiAxOmxlbmd0aChzYW1wbGVfc2l6ZXMpKSB7CiAgICBvcHRfc3RyaW5nIDwtIHBhc3RlKG9wdF9zdHJpbmcsIHNhbXBsZV9zaXplc1tpXSwgIiAiLCBzZXAgPSAiIikKICB9CiAgb3B0X3N0cmluZyA8LSBwYXN0ZShvcHRfc3RyaW5nLCBuZV9tLCAiXG4iLCBzZXAgPSAiIikKICBtc19vdXQgPC0gbXMobnNhbSA9IHN1bShzYW1wbGVfc2l6ZXMpLCBucmVwcyA9IDEsIG9wdHMgPSBvcHRfc3RyaW5nKQogIHJldHVybihtc19vdXQpICAKfQoKcGxvdF9pc2xhbmQgPC0gZnVuY3Rpb24oc2FtcGxlX3NpemVzLCBuZV9tKSB7CiAgbXNfb3V0IDwtIGlzbGFuZCgyKnNhbXBsZV9zaXplcywgbmVfbSkKICBtc190cmVlIDwtIHJlYWQudHJlZSh0ZXh0ID0gbXNfb3V0KQogIHBsb3QobXNfdHJlZSwgCiAgICAgICBzaG93LnRpcC5sYWJlbCA9IEZBTFNFKQogIHRpcGxhYmVscyhwY2ggPSAxOSwgY2V4ID0gMC43NSwgCiAgICAgICAgICAgIGNvbCA9IHRpcGNvbG9ycyhtc190cmVlLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgIDIqc2FtcGxlX3NpemVzKSkKICByZXR1cm4oYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWUpWzFdKQp9Cgp0aW1lIDwtIHBsb3RfaXNsYW5kKHNhbXBsZV9zaXplcyA9IGMoNSwgNSwgNSksIG5lX20gPSAxMCkKYGBgClRoZSBjb2xvcnMgY29ycmVzcG9uZCB0byB0aGUgcG9wdWxhdGlvbiBmcm9tIHdoaWNoIGVhY2ggc2FtcGxlIHdhcyBjb2xsZWN0ZWQuIGBwbG90X2lzbGFuZCgpYCByZXR1cm5zIHRoZSBzY2FsZWQgdGltZSB0byB0aGUgbW9zdCByZWNlbnQgY29tbW9uIGFuY2VzdG9yLCBgciB0aW1lYC4gV2UgYXJlIGltcGxpY2l0bHkgYXNzdW1pbmcgdGhhdCB0aGUgZWZmZWN0aXZlIHBvcHVsYXRpb24gc2l6ZSBpcyB0aGUgc2FtZSBpbiBlYWNoIGxvY2FsIHBvcHVsYXRpb24uXltUaGVyZSBpcyBhIHdheSB0byByZWxheCB0aGlzIGFzc3VtcHRpb24sIGJ1dCB3ZSB3b24ndCB0YWtlIGFkdmFudGFnZSBvZiBpdCBoZXJlLl0gVGhlIHNjYWxpbmcgaXMgaW4gdGVybXMgb2YgdGhlIHByb2R1Y3Qgb2YgdGhlIGxvY2FsIGVmZmVjdGl2ZSBwb3B1bGF0aW9uIHNpemUgYW5kIHRoZSBudW1iZXIgb2YgcG9wdWxhdGlvbnMsIGkuZS4sIDEgY29hbGVzY2VudCB1bml0ID0gJDROX2VrJCwgd2hlcmUgJGskIGlzIHRoZSBudW1iZXIgb2YgcG9wdWxhdGlvbnMuCgpOb3RpY2UgaG93IGRpZmZlcmVudCB0aGUgcmVzdWx0IGlzIGlmIEkgc2V0ICROX2VtID0gMC41JCBpbnN0ZWFkIG9mICROX2VtID0gMiQuCgpgYGB7cn0KdGltZSA8LSBwbG90X2lzbGFuZChzYW1wbGVfc2l6ZXMgPSBjKDUsIDUsIDUpLCBuZV9tID0gMC4xKQpgYGAKVGhlIGFsbGVsZXMgYXJlIG5vdyBuaWNlbHkgYXJyYW5nZWQgaW50byBwb3B1bGF0aW9ucy4gRG9lcyBpdCBzdXJwcmlzZSB5b3UgdGhhdCB0aGUgcG9wdWxhdGlvbnMgaW4gd2hpY2ggYWxsZWxlcyBvY2N1ciBmb3JtIG1vbm9waHlsZXRpYyBncm91cHMgd2hlbiAkTl9lbSBcbGwgMSQgYW5kIHRoYXQgdGhleSBkb24ndCB3aGVuICROX2VtIFxnZyAxJC5eW05vdGU6IFJlYWQgJFxsbCQgYXMgIm11Y2ggbGVzcyB0aGFuIiBhbmQgJFxnZyQgYXMgIm11Y2ggZ3JlYXRlciB0aGFuLiJdCgoKIyMgTGFiIDcKCllvdSB3aWxsIGJlIHBlcmZvcm1pbmcgYW5vdGhlciBzZXQgb2Ygc2ltdWxhdGlvbnMgdGhpcyB3ZWVrIHRvIGNvbXBhcmUgY29hbGVzY2VuY2UgdGltZXMgaW4gdHdvIHNjZW5hcmlvczoKCjEuIEEgZmluaXRlIGlzbGFuZCBtb2RlbCBvZiBtaWdyYXRpb24uCjIuIEEgb25lLWRpbWVuc2lvbmFsIHN0ZXBwaW5nIHN0b25lIG1vZGVsIG9mIG1pZ3JhdGlvbi4KCllvdSBzYXcgYm90aCB0aGUgZmluaXRlIGlzbGFuZCBtb2RlbCBhbmQgdGhlIG9uZS1kaW1lbnNpb25hbCBzdGVwcGluZyBzdG9uZSBtb2RlbCBsYXN0IHdlZWsuIEFzIGEgcmVtaW5kZXIsIGluIGEgb25lLWRpbWVuc2lvbmFsIHN0ZXBwaW5nIHN0b25lIG1vZGVsIHRoZSBwb3B1bGF0aW9ucyBhcmUgYXJyYW5nZWQgaW4gYSBsaW5lYXJ5IGFycmF5IGFuZCBvbmx5IHRob3NlIHBvcHVsYXRpb25zIHRoYXQgYXJlIGFkamFjZW50IHRvIG9uZSBhbm90aGVyIGNhbiBleGNoYW5nZSBtaWdyYW50cy4gSWYgJG0kIGlzIHRoZSBtaWdyYXRpb24gcmF0ZSwgaS5lLiwgdGhlIGZyYWN0aW9uIG9mIGEgcG9wdWxhdGlvbiBjb21wb3NlZCBvZiBtaWdyYW50cyB0aGVuIHRoZSBmcmFjdGlvbiBvZiBwb3B1bGF0aW9uICRpJCBkZXJpdmVkIGZyb20gcG9wdWxhdGlvbiAkaS0xJCBpcyAkXGZyYWN7bX17Mn0kIGFuZCB0aGUgZnJhY3Rpb24gb2YgcG9wdWxhdGlvbiAkaSQgZGVyaXZlZCBmcm9tIHBvcHVsYXRpb24gJGkrMSQgaXMgJFxmcmFje219ezJ9JC5eW05vdGU6IEZvciB0aGUgZmlyc3QgcG9wdWxhdGlvbiBpbiB0aGUgYXJyYXksIGkuZS4sIHBvcHVsYXRpb24gMSwgdGhlIGZyYWN0aW9uIG9mIHRoZSBwb3B1bGF0aW9uIGRlcml2ZWQgZnJvbSBwb3B1bGF0aW9uIDIgaXMgJG0kLiBTaW1pbGFybHksIGlmIHRoZXJlIGFyZSAkayQgcG9wdWxhdGlvbnMgaW4gdGhlIGFycnksIHRoZSBmcmFjdGlvbiBvZiBwb3B1bGF0aW9uICRrJCB0aGF0IGlzIGRlcml2ZWQgZnJvbSBwb3B1bGF0aW9uICRrLTEkIGlzICRtJC5dCgpVc2UgdGhlIGZ1bmN0aW9ucyBiZWxvdyB0byBleHBsb3JlIHRoZSBkaWZmZXJlbmNlIGluIGNvYWxlc2NlbmNlIHRpbWVzIGZvciBmaW5pdGUgaXNsYW5kIG1vZGVscyBhbmQgb25lLWRpbWVuc2lvbmFsIHN0ZXBwaW5nIHN0b25lIG1vZGVscyBvZiBtaWdyYXRpb24sIGFuZCBhbnN3ZXIgdGhlIGZvbGxvd2luZyBxdWVzdGlvbnM6CgoxLiBIb3cgZG9lcyB0aGUgbnVtYmVyIG9mIHBvcHVsYXRpb25zIGluY2x1ZGVkIGFmZmVjdCB0aGUgYXZlYXJnZSB0aW1lIHRvIGNvYWxlc2NlbmNlIG9mIGFsbCBhbGxlbGVzPyBUcnkgYXQgbGVhc3Qgb25lIGNhc2UgaW4gd2hpY2ggdGhlIG51bWJlciBvZiBwb3B1bGF0aW9ucyBpcyByZWxhdGl2ZWx5IHNtYWxsLCBpLmUuLCAxMCBvciBmZXdlciwgYW5kIG9uZSBpbiB3aGljaCBpdCBpcyBtb2RlcmF0ZWx5IGxhcmdlLCBpLmUuLCAyNSBvciBtb3JlLgoKMi4gSG93IGRvZXMgdGhlIG1pZ3JhdGlvbiByYXRlIGFmZmVjdCB0aGUgYXZlcmFnZSB0aW1lIHRvIGNvYWxlc2NlbmNlIG9mIGFsbCBhbGxlbGVzPyBEb2VzIGl0IGRlcGVuZCBvbiB3aGV0aGVyIG1pZ3JhdGlvbiBpcyBiZXR0ZXIgYXBwcm94aW1hdGVkIGJ5IGEgZmluaXRlIGlzbGFuZCBtb2RlbCBvciBhIG9uZS1kaW1lbnNpb25hbCBzdGVwcGluZyBzdG9uZSBtb2RlbD8KCjMuIEFyZSB0aGVyZSBjb25zaXN0ZW50IGRpZmZlcmVuY2VzIGJldHdlZW4gdGhlIGF2ZXJhZ2UgdGltZSB0byBjb2FsZXNjZW5jZSBpbiBhIGZpbml0ZSBpc2xhbmQgbW9kZWwgYW5kIGEgb25lLWRpbWVuc2lvbmFsIHN0ZXBwaW5nIHN0b25lIG1vZGVsPyBJZiB0aGVyZSBhcmUsIHdoYXQgbWlnaHQgZXhwbGFpbiB0aGUgZGlmZmVyZW5jZXMgdGhhdCB5b3Ugc2VlPwoKIyMjIEhpbnRzCgpgcnVuX3NpbXVsYXRpb25zKClgIHdpbGwgYXV0b21hdGljYWxseSBrZWVwIHRoZSBudW1iZXIgb2YgcG9wdWxhdGlvbnMgaW4gYm90aCBtb2RlbHMgdGhlIHNhbWUgdG8gZW5zdXJlIHRoYXQgeW91IGNhbiBhbHdheXMgbWFrZSBhcHByb3ByaWF0ZSBjb21wYXJpc29ucyBvZiB0aGUgbW9kZWxzLiBJdCB3aWxsIGFsc28gc2V0IHRoZSBsb2NhbCBlZmZlY3RpdmUgcG9wdWxhdGlvbiBzaXplIHRvIDI1LCBhbmQgaXQgc2V0cyB0aGUgbnVtYmVyIG9mIHJlcGxpY2F0aW9ucyB0byAxMDAwIGJ5IGRlZmF1bHQuIFlvdSBtaWdodCB3YW50IHRvIHJ1biB0aGUgZnVuY3Rpb24gb25jZSB3aXRoIGBuX3JlcHMgPSAxMDBgIHRvIGdldCBhIGZlZWwgZm9yIGhvdyBsb25nIGl0IHdpbGwgdGFrZSB0aGUgc2ltdWxhdGlvbiB0byBydW4gb24geW91ciBjb21wdXRlciBiZWZvcmUgeW91IGJlZ2luIHRoZSBmdWxsLXNjYWxlIHNpbXVsYXRpb25zIAoKYHJ1bl9zaW11bGF0aW9ucygpYCByZXR1cm5zIGEgZGF0YSBmcmFtZV5bV2VsbCwgYWN0dWFsbHkgYSB0aWJibGVdIHdpdGggdHdvIGNvbHVtbnM6IGBNb2RlbGAgYW5kIGBUaW1lYC4gSWYgeW91J3JlIGludGVyZXN0ZWQsIHlvdSBjYW4gdXNlIHRoYXQgdG8gZXhhbWluZSB0aGUgbWVkaWFuIHRpbWUgdG8gY29hbGVzY2VuY2UgKHJhdGhlciB0aGFuIHRoZSBtZWFuKSBhbmQgdGhlIHZhcmlhbmNlIChvciBzdGFuZGFyZCBkZXZpYXRpb24pIGluIGNvYWxlc2NlbmNlIHRpbWVzLiBZb3UnbGwgbm90aWNlIHRoYXQgYHJ1bl9zaW11bGF0aW9uKClgIGF1dG9tYXRpY2FsbHkgcHJpbnRzIG91dCB0aGUgbWVhbiBjb2FsZXNlbmNlIHRpbWVzIGZvciB5b3UuCgpJbiBhbnN3ZXJpbmcgcXVlc3Rpb24gIzMga2VlcCBpbiBtaW5kIHRoYXQgeW91ciBhbnN3ZXIgbWlnaHQgZGVwZW5kIG9uIGhvdyBtYW55IHBvcHVsYXRpb25zIHRoZXJlIGFyZS5eW1doeSBlbHNlIHdvdWxkIEkgaGF2ZSBhc2tlZCB5b3UgdG8gbG9vayBib3RoIGF0IG9uZSBleGFtcGxlIGluIHdoaWNoIHRuZSBudW1iZXIgb2YgcG9wdWxhdGlvbnMgaXMgMTAgb3IgZmV3ZXIgYW5kIGFub3RoZXIgaW4gd2hpY2ggdGhlIG51bWJlciBvZiBwb3B1bGF0aW9ucyBpcyAyNSBvciBtb3JlP10KCmBgYHtyfQojIyBvbmUtZGltZW5zaW9uYWwgc3RlcHBpbmcgc3RvbmUKIyMKb25lX2Rfc3RlcHBpbmdfc3RvbmUgPC0gZnVuY3Rpb24obl9lLCBtLCBuX3BvcHMpIHsKICBzdG9waWZub3QoKG0gPiAwKSAmJiAobSA8IDEpKQogIG1fbWF0cml4IDwtIGRpYWcoMSAtIG0sIG5yb3cgPSBuX3BvcHMpCiAgbV9tYXRyaXhbMSwgMl0gPC0gbQogIG1fbWF0cml4W25fcG9wcywgbl9wb3BzIC0gMV0gPC0gbQogIGZvciAoaSBpbiAyOihuX3BvcHMgLSAxKSkgewogICAgbV9tYXRyaXhbaSwgaSAtIDFdIDwtIG0vMgogICAgbV9tYXRyaXhbaSwgaSArIDFdIDwtIG0vMgogIH0KICBvcHRfc3RyaW5nIDwtIHBhc3RlKCItVCAtSSAiLCBuX3BvcHMsICIgIiwgc2VwID0gIiIpCiAgZm9yIChpIGluIDE6bl9wb3BzKSB7CiAgICBvcHRfc3RyaW5nIDwtIHBhc3RlKG9wdF9zdHJpbmcsIDIqbl9lLCAiICIsIHNlcCA9ICIiKQogIH0KICBvcHRfc3RyaW5nIDwtIHBhc3RlKG9wdF9zdHJpbmcsICItbWEiLCBzZXAgPSAiIikKICAjIyB0cmFuc3Bvc2UgbV9tYXRyaXggYmVmb3JlIGNvbnZlcnRpbmcgdG8gdmVjdG9yIHRvIGdldCB2ZWN0b3IgZnJvbSBtYXRyaXgKICAjIyBieSByb3cgaW5zdGVhZCBvZiBieSBjb2x1bW4KICAjIwogIG1fdmVjdG9yIDwtIDQqbl9lKmModChtX21hdHJpeCkpCiAgZm9yICggaSBpbiAxOmxlbmd0aChtX3ZlY3RvcikpIHsKICAgIG9wdF9zdHJpbmcgPC0gcGFzdGUob3B0X3N0cmluZywgIiAiLCBtX3ZlY3RvcltpXSwgc2VwID0gIiIpCiAgfQogIG1zX291dCA8LSBtcyhuc2FtID0gMipuX2Uqbl9wb3BzLCBucmVwcyA9IDEsIG9wdHMgPSBvcHRfc3RyaW5nKQogIHJldHVybihtc19vdXQpCn0KCnJ1bl9zaW11bGF0aW9uIDwtIGZ1bmN0aW9uKG5fcG9wcywgbSwgbl9yZXBzID0gMTAwMCkgewogIE5fZSA9IDI1CiAgcG9wX3NpemVzIDwtIHJlcChOX2UsIG5fcG9wcykKICBkZiA8LSB0aWJibGUoTW9kZWwgPSBOQSwgVGltZSA9IE5BKQogIGZvciAoaSBpbiAxOm5fcmVwcykgewogICAgbXNfb3V0IDwtIGlzbGFuZChwb3Bfc2l6ZXMsIE5fZSptKQogICAgbXNfdHJlZSA8LSByZWFkLnRyZWUodGV4dCA9IG1zX291dCkKICAgIGRmIDwtIGFkZF9yb3coZGYsCiAgICAgICAgICAgICAgICAgIE1vZGVsID0gIklzbGFuZCIsCiAgICAgICAgICAgICAgICAgIFRpbWUgPSAoNCpOX2Uqbl9wb3BzKSpicmFuY2hpbmcudGltZXMobXNfdHJlZSlbMV0pCiAgICBtc19vdXQgPC0gb25lX2Rfc3RlcHBpbmdfc3RvbmUoTl9lLCBtLCBuX3BvcHMpCiAgICBtc190cmVlIDwtIHJlYWQudHJlZSh0ZXh0ID0gbXNfb3V0KQogICAgZGYgPC0gYWRkX3JvdyhkZiwKICAgICAgICAgICAgICAgICAgTW9kZWwgPSAiMS1kIiwKICAgICAgICAgICAgICAgICAgVGltZSA9ICg0Kk5fZSpuX3BvcHMpKmJyYW5jaGluZy50aW1lcyhtc190cmVlKVsxXSkKICB9CiAgZGYgPC0gZmlsdGVyKGRmLCAhaXMubmEoTW9kZWwpKQogIHAgPC0gZ2dwbG90KGRmLCBhZXMoeCA9IFRpbWUsIGZpbGwgPSBNb2RlbCkpICsKICAgIGdlb21faGlzdG9ncmFtKHBvc2l0aW9uID0gImlkZW50aXR5IiwgYmlucyA9IG5fcmVwcy8xMCwgYWxwaGEgPSAwLjQpICsKICAgIGdndGl0bGUocGFzdGUoIm5fcG9wcyA9ICIsIG5fcG9wcywgIiwgbSA9ICIsIG0pKSArCiAgICB0aGVtZV9idygpCiAgcHJpbnQocCkKICBzdW0gPC0gZGYgJT4lIGdyb3VwX2J5KE1vZGVsKSAlPiUKICAgIHN1bW1hcml6ZShNZWFuX1RpbWUgPSBtZWFuKFRpbWUpKQogIHByaW50KHN1bSkKICByZXR1cm4oZGYpCn0KYGBgCg==