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. 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 know 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\).
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. 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\).
Lab 7
You will be performing another set of simulations this week to
compare coalescence times in two scenarios:
- A finite island model of migration.
- 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}\).
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:
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.
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?
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 frame 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.
## 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)
}
LS0tCnRpdGxlOiAiRXhwbG9yaW5nIHRoZSBjb2FsZXNjZW50IgpvdXRwdXQ6IAogIGh0bWxfbm90ZWJvb2s6CiAgICB0b2M6IHllcwogICAgdG9jX2Zsb2F0OiB0cnVlCi0tLQoKV2UgdXNlIGBtcygpYCBmcm9tIGBwaHljbHVzdGAgdG8gc2ltdWxhdGUgc2FtcGxlcyBmcm9tIHRoZSBjb2FsZXNjZW50IGFuZCB2YXJpb3VzIGZ1bmN0aW9ucyBmcm9tIGBhcGVgIHRvIGRpc3BsYXkgdGhlIGNvYWxlc2NlbnQgdHJlZSBhbmQgY2FsY3VsYXRlIHN0YXRpc3RpY3MgZnJvbSBpdC4gTGV0J3Mgc3RhcnQgd2l0aCBhIHJlYWxseSBzaW1wbGUgZXhhbXBsZSBvZiBjb25zdHJ1Y3RpbmcgYSBjb2FsZXNjZW50IHNhbXBsZSBvZiBzaXplIDEwLiBUaGUgYG5zYW1gIGFyZ3VtZW50IGlzIHRoZSBudW1iZXIgb2Ygc2FtcGxlcywgYW5kIHRoZSBgb3B0cyA9ICItVCJgIGFyZ3VtZW50IHRlbGwgYG1zKClgIHRvIHJldHVybiBhIGNvYWxlc2NlbnQgdHJlZS4gV2UgdGhlbiBjb252ZXJ0IGl0LCB1c2luZyBgcmVhZC50cmVlKClgIHRvIGEgZm9ybWF0IHRoYXQgd2UgY2FuIGBwbG90KClgICAKCiMjIFRoZSBjb2FsZXNjZW50IGluIGBSYAoKYGBge3J9CmxpYnJhcnkoYXBlKQpsaWJyYXJ5KHBoeWNsdXN0KQoKcm0obGlzdCA9IGxzKCkpCgojIyBzZXQgcmFuZG9tIG51bWJlciBzZWVkIHNvIHRoYXQgc2FtZSB0cmVlIGlzIHByb2R1Y2VkIGV2ZXJ5IHRpbWUgdGhpcyBjb2RlCiMjIGlzIHJ1bgojIwpzZXQuc2VlZCgxMjM0KQoKbXNfb3V0IDwtIG1zKG5zYW0gPSAxMCwgb3B0cyA9ICItVCIpCm1zX3RyZWVfMSA8LSByZWFkLnRyZWUodGV4dCA9IG1zX291dCkKcGxvdChtc190cmVlXzEpCmBgYApZb3UnbGwgbm90aWNlIHRoYXQgdGhlIHRpcCBsYWJlbHMgcnVuIGZyb20gYHMxYCB0aHJvdWdoIGBzMTBgLiBFYWNoIGNvcnJlc3BvbmRzIHRvIGEgZGlmZmVyZW50IGFsbGVsZS4gVGhhdCB3YXMgcHJldHR5IGVhc3ksIGJ1dCB3ZSBjYW4gZG8gYSBiaXQgbW9yZS4gV2UgY2FuIGFzayBob3cgImRlZXAiIHRoZSB0cmVlIGlzLCBpLmUuLCBob3cgZmFyIGJhY2sgaW4gdGltZSB3ZSBoYXZlIHRvIGdvIHRvIGZpbmQgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3RvciBvZiBhbGwgdGhlIGFsbGVsZXMgaW4gb3VyIHNhbXBsZS4KCiMjIyBCcmFuY2hpbmcgdGltZXMKCmBgYHtyfQpicmFuY2hpbmcudGltZXMobXNfdHJlZV8xKVsxXQpgYGAKCllvdSdyZSBwcm9iYWJseSB3b25kZXJpbmcgYWJvdXQgdGhlIGBbMV1gIGFmdGVyIGBicmFuY2hpbmcudGltZXMoKWAuIFdlbGwsIGBicmFuY2hpbmcudGltZXMoKWAgcmV0dXJucyBhIHZlY3RvciBvZiAqYWxsKiBvZiB0aGUgYnJhbmNoaW5nIHRpbWVzIGluIHRoZSB0cmVlLgoKYGBge3J9CmJyYW5jaGluZy50aW1lcyhtc190cmVlXzEpCmBgYAoKVGhlIG51bWJlcnMgMTEtMTkgYXJlIHRoZSBub2RlIG51bWJlcnMgaW4gdGhlIHRyZWUgYWJvdmUuCgpgYGB7cn0KcGxvdChtc190cmVlXzEpCm5vZGVsYWJlbHMoKQpgYGAKCkFzIHlvdSBjYW4gc2VlLCBub2RlIDExICh3aGljaCBpcyB0aGUgZmlyc3Qgb25lIGluIHRoZSBsaXN0KSwgaXMgdGhlIGRlZXBlc3Qgbm9kZSwgaS5lLiwgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3RvciBvZiBhbGwgb2YgdGhlIGFsbGVsZXMgaW4gb3VyIHNhbXBsZS4gCgojIyMgU2NhbGluZyBvZiBicmFuY2hpbmcgdGltZXMKClRoZSBvdGhlciB0aGluZyB5b3UgbWF5IGJlIHdvbmRlcmluZyBpcyBob3cgdG8gaW50ZXJwcmV0IHRoZSBudW1iZXIgYHIgYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWVfMSlbMV1gIHRoYXQgY29ycmVzcG9uZHMgdG8gdGhlIHRpbWUgb2YgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3Rvci5eW1JlbWVtYmVyIHRoYXQgd2hlbiB1c2luZyB0aGUgY29hbGVzY2VudCwgdGltZSBydW5zIGJhY2t3YXJkcy4gU28gdGhlIHRpbWUgb2YgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3RvciBpcyBhIHRpbWUgaW4gdGhlIHBhc3QuXSBUbyBleHBsYWluIHRoYXQgSSBoYXZlIHRvIHBvaW50IG91dCBzb21ldGhpbmcgdGhhdCB5b3UgbWF5IGhhdmUgbWlzc2VkIHdoZW4gd2UgY2FsbGVkIGBtcygpYDogV2UgZGlkbid0IHNwZWNpZnkgYSBwb3B1bGF0aW9uIHNpemUuIEhvdyBjYW4gd2UgZ2V0IGF3YXkgd2l0aCB0aGF0LCBzaW5jZSBJIHRvbGQgeW91IHRoYXQgZHJpZnQgKmFsd2F5cyogZGVwZW5kcyBvbiB0aGUgcG9wdWxhdGlvbiBzaXplPwoKV2VsbCwgcmVtZW1iZXIgd2hhdCB5b3Uga25vd15bb3Igd2hhdCBJIHRvbGQgeW91XSBhYm91dCB0aGUgY29hbGVzZW50IHByb2Nlc3MuIFRoZSBleHBlY3RlZCB0aW1lIHRvIGNvYWxlc2NlbmNlIG9mIGFsbCBhbGxlbGVzIGlzICQ0Tl9lJC4gYG1zKClgIHJlcG9ydHMgYnJhbmNoaW5nIHRpbWUgaW4gImNvYWxlc2NlbnQgdW5pdHMiIHdoZXJlIDEgdW5pdCBlcXVhbHMgJDROX2UkLiBTbyBpZiBgYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWVfMSlbMV1gIGlzIGByIGJyYW5jaGluZy50aW1lcyhtc190cmVlXzEpWzFdYCBhbmQgdGhlIGVmZmVjdGl2ZSBzaXplIG9mIG91ciBwb3B1bGF0aW9uIGlzIDI1LCB0aGVuIHRoZSB0aW1lIChudW1iZXIgb2YgZ2VuZXJhdGlvbnMgYmVmb3JlIHRoZSBwcmVzZW50KSB0byB0aGUgbW9zdCByZWNlbnQgY29tbW9uIGFuY2VzdG9yIGlzIGByIDQqMjUqYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWVfMSlbMV1gLiBOb3RpY2UgdGhhdCB0aGUgdGltZSBpc24ndCBhbiBpbnRlZ2VyIHRoZSB3YXkgeW91J2QgZXhwZWN0IGl0IHRvIGJlLiBUaGF0J3MgYmVjYXVzZSBvZiBhbiBhcHByb3hpbWF0aW9uIHRoYXQgaXMgZ2VuZXJhbGx5IHVzZWQgaW4gaW1wbGVtZW50aW5nIHRoZSBjb2FsZXNjZW50IGluIHNvZnR3YXJlLiBJZiB5b3Ugd2FudCB0byB0dXJuIGl0IGludG8gYW4gaW50ZWdlciwgeW91IGNhbiBkbyB0aGlzOgoKYGBge3J9CnJvdW5kKDQqMjUqYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWVfMSlbMV0pCmBgYAoKV2hldGhlciB5b3Ugcm91bmQgaXQgb3Igbm90LCB5b3UnbGwgc2VlIHRoYXQgdGhlIG1vc3QgcmVjZW50IGNvbW1vbiBhbmNlc3RvciBvZiB0aGUgYWxsZWxlcyBpbiBvdXIgc2FtcGxlIGRpZG4ndCBvY2N1ciBleGFjdGx5IDEwMCBnZW5lcmF0aW9ucyBhZ28gYXMgd2UnZCBleHBlY3QuIElmLCBob3dldmVyLCB3ZSByZXBlYXQgdGhhdCBzaW11bGF0aW9uIGEgYnVuY2ggb2YgdGltZXMsIHlvdSBjYW4gc2VlIHRoYXQgd2UgY29tZSBwcmV0dHkgY2xvc2UgLSBvbiBhdmVyYWdlLgoKYGBge3J9CmxpYnJhcnkoZ2dwbG90MikKCk5fZSA9IDI1CgpjX3RpbWUgPC0gbnVtZXJpYygwKQpmb3IgKGkgaW4gMToxMDAwKSB7CiAgbXNfb3V0IDwtIG1zKG5zYW0gPSBOX2UsIG9wdHMgPSAiLVQiKQogIG1zX3RyZWUgPC0gcmVhZC50cmVlKHRleHQgPSBtc19vdXQpCiAgY190aW1lW2ldIDwtIDQqTl9lKmJyYW5jaGluZy50aW1lcyhtc190cmVlKVsxXQp9CnAgPC0gZ2dwbG90KGRhdGEuZnJhbWUodCA9IGNfdGltZSksIGFlcyh4ID0gdCkpICsKICBnZW9tX2hpc3RvZ3JhbShiaW5zID0gNTAsIGFscGhhID0gMC42KSArCiAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ID0gNCpOX2UsIGxpbmV0eXBlID0gImRhc2hlZCIsIGNvbG9yID0gInJlZCIpICsgCiAgdGhlbWVfYncoKQpwCmBgYAoKV2UgZXhwZWN0IGEgY29hbGVzY2VuY2UgdGltZSBvZiBgciA0Kk5fZWAgYW5kIG91ciBvYnNlcnZlZCBhdmVyYWdlIGNvYWxlc2NlbmNlIHRpbWUgaXMgYHIgbWVhbihjX3RpbWUpYC4gTm90IHRvbyBiYWQuIE5vdGljZSB0aGF0IHRoZSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgdGhlIGNvYWxlc2NlbmNlIHRpbWUgaXMgYHIgc2QoY190aW1lKWAuIFRoYXQncyBhIGxvdCBvZiB2YXJpYWJpbGl0eSBpbiBjb2FsZXNjZW5jZSB0aW1lLCB3aGljaCByZS1lbXBoYXNpemVzIGEgcG9pbnQgSSd2ZSBtYWRlIG1hbnkgdGltZXM6IFRoZXJlIGlzIGEgKioqbG90KioqIG9mIHZhcmlhYmlsaXR5IGFzc29jaWF0ZWQgd2l0aCBkcmlmdC4gV2hpbGUgdGhlIGV4cGVjdGF0aW9ucyB3ZSBmb2N1cyBvbiBwcm92aWRlIGEgdXNlZnVsIHBvaW50IG9mIGNvbXBhcmlzb24sIHRoZXkgY2FuIGRlbHVkZSB1cyBpbnRvIHRoaW5raW5nIHRoYXQgd2Uga25vdyBtb3JlIHRoYW4gd2UgYWN0dWFsbHkgZG8uCgojIyMgVGhlIGNvYWxlc2NlbnQgd2l0aCBtaWdyYXRpb24KCldoYXQgaGFwcGVucyB3aGVuIHdlIGhhdmUgYSBzdWJkaXZpZGVkIHBvcHVsYXRpb24gc28gdGhhdCB3ZSBoYXZlIHNldmVyYWwgcG9wdWxhdGlvbnMgZXhjaGFuZ2luZyBnZW5lcz8gSGVyZSdzIGhvdyB3ZSBzaW11bGF0ZSBhIGZpbml0ZSBpc2xhbmQgbW9kZWwgd2l0aCB0aHJlZSBwb3B1bGF0aW9ucywgbG9jYWwgcG9wdWxhdGlvbiBzaXplcyBvZiAxMCBpbiBlYWNoIHBvcHVsYXRpb24sIGFuZCAkTl9lbSA9IDIkLl5bTm90ZTogWW91J2xsIG5lZWQgdG8gaW5zdGFsbCBgUkNvbG9yQnJld2VyYCBpZiB5b3Ugd2FudCB0byBydW4gdGhpcyBjb2RlLl0KCmBgYHtyfQpvcHRpb25zKHRpZHl2ZXJzZS5xdWlldCA9IFRSVUUpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KFJDb2xvckJyZXdlcikKCmdldF9wb3AgPC0gZnVuY3Rpb24odHJlZSwgc2FtcGxlX3NpemVzLCBrKSB7CiAgaWR4IDwtIGFzLm51bWVyaWMoZ3N1YigiXnMoLiopJCIsICJcXDEiLCB0cmVlJHRpcC5sYWJlbCkpCiAgY3VtIDwtIDAKICBmb3IgKGkgaW4gMTpsZW5ndGgoc2FtcGxlX3NpemVzKSkgewogICAgaWYgKGlkeFtrXSA8IGN1bSArIHNhbXBsZV9zaXplc1tpXSArIDEpIHsKICAgICAgcmV0dmFsIDwtIGkKICAgICAgYnJlYWsKICAgIH0gZWxzZSB7CiAgICAgIGN1bSA8LSBjdW0gKyBzYW1wbGVfc2l6ZXNbaV0KICAgIH0KICB9CiAgcmV0dXJuKGkpCn0KCnRpcGNvbG9ycyA8LSBmdW5jdGlvbih0cmVlLCBzYW1wbGVfc2l6ZXMpIHsKICBteV9jb2xvcnMgPC0gYnJld2VyLnBhbChsZW5ndGgoc2FtcGxlX3NpemVzKSwgIlNldDEiKQogIGNvbG9ycyA8LSBudW1lcmljKGxlbmd0aChzYW1wbGVfc2l6ZXMpKQogIGZvciAoaSBpbiAxOnN1bShzYW1wbGVfc2l6ZXMpKSB7CiAgICBjb2xvcnNbaV0gPC0gbXlfY29sb3JzW2dldF9wb3AodHJlZSwgc2FtcGxlX3NpemVzLCBpKV0KICB9CiAgcmV0dXJuKGNvbG9ycykKfQoKIyMgTm90ZTogc2FtcGxlIHNpemVzIHNob3VsZCBiZSBtdWx0aXBsaWVkIGJ5IDIgYmVmb3JlIGNhbGxpbmcKIyMgaXNsYW5kIGZvciBkaXBsb2lkIHNhbXBsZXMKIyMKaXNsYW5kIDwtIGZ1bmN0aW9uKHNhbXBsZV9zaXplcywgbmVfbSkgewogIG9wdF9zdHJpbmcgPC0gcGFzdGUoIi1UIC1JICIsIGxlbmd0aChzYW1wbGVfc2l6ZXMpLCAiICIsIHNlcCA9ICIiKQogIGZvciAoaSBpbiAxOmxlbmd0aChzYW1wbGVfc2l6ZXMpKSB7CiAgICBvcHRfc3RyaW5nIDwtIHBhc3RlKG9wdF9zdHJpbmcsIHNhbXBsZV9zaXplc1tpXSwgIiAiLCBzZXAgPSAiIikKICB9CiAgb3B0X3N0cmluZyA8LSBwYXN0ZShvcHRfc3RyaW5nLCBuZV9tLCAiXG4iLCBzZXAgPSAiIikKICBtc19vdXQgPC0gbXMobnNhbSA9IHN1bShzYW1wbGVfc2l6ZXMpLCBucmVwcyA9IDEsIG9wdHMgPSBvcHRfc3RyaW5nKQogIHJldHVybihtc19vdXQpICAKfQoKcGxvdF9pc2xhbmQgPC0gZnVuY3Rpb24oc2FtcGxlX3NpemVzLCBuZV9tKSB7CiAgbXNfb3V0IDwtIGlzbGFuZCgyKnNhbXBsZV9zaXplcywgbmVfbSkKICBtc190cmVlIDwtIHJlYWQudHJlZSh0ZXh0ID0gbXNfb3V0KQogIHBsb3QobXNfdHJlZSwgCiAgICAgICBzaG93LnRpcC5sYWJlbCA9IEZBTFNFKQogIHRpcGxhYmVscyhwY2ggPSAxOSwgY2V4ID0gMC43NSwgCiAgICAgICAgICAgIGNvbCA9IHRpcGNvbG9ycyhtc190cmVlLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgIDIqc2FtcGxlX3NpemVzKSkKICByZXR1cm4oYnJhbmNoaW5nLnRpbWVzKG1zX3RyZWUpWzFdKQp9Cgp0aW1lIDwtIHBsb3RfaXNsYW5kKHNhbXBsZV9zaXplcyA9IGMoNSwgNSwgNSksIG5lX20gPSAxMCkKYGBgClRoZSBjb2xvcnMgY29ycmVzcG9uZCB0byB0aGUgcG9wdWxhdGlvbiBmcm9tIHdoaWNoIGVhY2ggc2FtcGxlIHdhcyBjb2xsZWN0ZWQuIGBwbG90X2lzbGFuZCgpYCByZXR1cm5zIHRoZSBzY2FsZWQgdGltZSB0byB0aGUgbW9zdCByZWNlbnQgY29tbW9uIGFuY2VzdG9yLCBgciB0aW1lYC4gV2UgYXJlIGltcGxpY2l0bHkgYXNzdW1pbmcgdGhhdCB0aGUgZWZmZWN0aXZlIHBvcHVsYXRpb24gc2l6ZSBpcyB0aGUgc2FtZSBpbiBlYWNoIGxvY2FsIHBvcHVsYXRpb24uXltUaGVyZSBpcyBhIHdheSB0byByZWxheCB0aGlzIGFzc3VtcHRpb24sIGJ1dCB3ZSB3b24ndCB0YWtlIGFkdmFudGFnZSBvZiBpdCBoZXJlLl0gVGhlIHNjYWxpbmcgaXMgaW4gdGVybXMgb2YgdGhlIHByb2R1Y3Qgb2YgdGhlIGxvY2FsIGVmZmVjdGl2ZSBwb3B1bGF0aW9uIHNpemUgYW5kIHRoZSBudW1iZXIgb2YgcG9wdWxhdGlvbnMsIGkuZS4sIDEgY29hbGVzY2VudCB1bml0ID0gJDROX2VrJCwgd2hlcmUgJGskIGlzIHRoZSBudW1iZXIgb2YgcG9wdWxhdGlvbnMuCgpOb3RpY2UgaG93IGRpZmZlcmVudCB0aGUgcmVzdWx0IGlzIGlmIEkgc2V0ICROX2VtID0gMC41JCBpbnN0ZWFkIG9mICROX2VtID0gMiQuCgpgYGB7cn0KdGltZSA8LSBwbG90X2lzbGFuZChzYW1wbGVfc2l6ZXMgPSBjKDUsIDUsIDUpLCBuZV9tID0gMC4xKQpgYGAKVGhlIGFsbGVsZXMgYXJlIG5vdyBuaWNlbHkgYXJyYW5nZWQgaW50byBwb3B1bGF0aW9ucy4gRG9lcyBpdCBzdXJwcmlzZSB5b3UgdGhhdCB0aGUgcG9wdWxhdGlvbnMgaW4gd2hpY2ggYWxsZWxlcyBvY2N1ciBmb3JtIG1vbm9waHlsZXRpYyBncm91cHMgd2hlbiAkTl9lbSBcbGwgMSQgYW5kIHRoYXQgdGhleSBkb24ndCB3aGVuICROX2VtIFxnZyAxJC5eW05vdGU6IFJlYWQgJFxsbCQgYXMgIm11Y2ggbGVzcyB0aGFuIiBhbmQgJFxnZyQgYXMgIm11Y2ggZ3JlYXRlciB0aGFuLiJdCgoKIyMgTGFiIDcKCllvdSB3aWxsIGJlIHBlcmZvcm1pbmcgYW5vdGhlciBzZXQgb2Ygc2ltdWxhdGlvbnMgdGhpcyB3ZWVrIHRvIGNvbXBhcmUgY29hbGVzY2VuY2UgdGltZXMgaW4gdHdvIHNjZW5hcmlvczoKCjEuIEEgZmluaXRlIGlzbGFuZCBtb2RlbCBvZiBtaWdyYXRpb24uCjIuIEEgb25lLWRpbWVuc2lvbmFsIHN0ZXBwaW5nIHN0b25lIG1vZGVsIG9mIG1pZ3JhdGlvbi4KCllvdSBzYXcgYm90aCB0aGUgZmluaXRlIGlzbGFuZCBtb2RlbCBhbmQgdGhlIG9uZS1kaW1lbnNpb25hbCBzdGVwcGluZyBzdG9uZSBtb2RlbCBsYXN0IHdlZWsuIEFzIGEgcmVtaW5kZXIsIGluIGEgb25lLWRpbWVuc2lvbmFsIHN0ZXBwaW5nIHN0b25lIG1vZGVsIHRoZSBwb3B1bGF0aW9ucyBhcmUgYXJyYW5nZWQgaW4gYSBsaW5lYXJ5IGFycmF5IGFuZCBvbmx5IHRob3NlIHBvcHVsYXRpb25zIHRoYXQgYXJlIGFkamFjZW50IHRvIG9uZSBhbm90aGVyIGNhbiBleGNoYW5nZSBtaWdyYW50cy4gSWYgJG0kIGlzIHRoZSBtaWdyYXRpb24gcmF0ZSwgaS5lLiwgdGhlIGZyYWN0aW9uIG9mIGEgcG9wdWxhdGlvbiBjb21wb3NlZCBvZiBtaWdyYW50cyB0aGVuIHRoZSBmcmFjdGlvbiBvZiBwb3B1bGF0aW9uICRpJCBkZXJpdmVkIGZyb20gcG9wdWxhdGlvbiAkaS0xJCBpcyAkXGZyYWN7bX17Mn0kIGFuZCB0aGUgZnJhY3Rpb24gb2YgcG9wdWxhdGlvbiAkaSQgZGVyaXZlZCBmcm9tIHBvcHVsYXRpb24gJGkrMSQgaXMgJFxmcmFje219ezJ9JC5eW05vdGU6IEZvciB0aGUgZmlyc3QgcG9wdWxhdGlvbiBpbiB0aGUgYXJyYXksIGkuZS4sIHBvcHVsYXRpb24gMSwgdGhlIGZyYWN0aW9uIG9mIHRoZSBwb3B1bGF0aW9uIGRlcml2ZWQgZnJvbSBwb3B1bGF0aW9uIDIgaXMgJG0kLiBTaW1pbGFybHksIGlmIHRoZXJlIGFyZSAkayQgcG9wdWxhdGlvbnMgaW4gdGhlIGFycnksIHRoZSBmcmFjdGlvbiBvZiBwb3B1bGF0aW9uICRrJCB0aGF0IGlzIGRlcml2ZWQgZnJvbSBwb3B1bGF0aW9uICRrLTEkIGlzICRtJC5dCgpVc2UgdGhlIGZ1bmN0aW9ucyBiZWxvdyB0byBleHBsb3JlIHRoZSBkaWZmZXJlbmNlIGluIGNvYWxlc2NlbmNlIHRpbWVzIGZvciBmaW5pdGUgaXNsYW5kIG1vZGVscyBhbmQgb25lLWRpbWVuc2lvbmFsIHN0ZXBwaW5nIHN0b25lIG1vZGVscyBvZiBtaWdyYXRpb24sIGFuZCBhbnN3ZXIgdGhlIGZvbGxvd2luZyBxdWVzdGlvbnM6CgoxLiBIb3cgZG9lcyB0aGUgbnVtYmVyIG9mIHBvcHVsYXRpb25zIGluY2x1ZGVkIGFmZmVjdCB0aGUgYXZlYXJnZSB0aW1lIHRvIGNvYWxlc2NlbmNlIG9mIGFsbCBhbGxlbGVzPyBUcnkgYXQgbGVhc3Qgb25lIGNhc2UgaW4gd2hpY2ggdGhlIG51bWJlciBvZiBwb3B1bGF0aW9ucyBpcyByZWxhdGl2ZWx5IHNtYWxsLCBpLmUuLCAxMCBvciBmZXdlciwgYW5kIG9uZSBpbiB3aGljaCBpdCBpcyBtb2RlcmF0ZWx5IGxhcmdlLCBpLmUuLCAyNSBvciBtb3JlLgoKMi4gSG93IGRvZXMgdGhlIG1pZ3JhdGlvbiByYXRlIGFmZmVjdCB0aGUgYXZlcmFnZSB0aW1lIHRvIGNvYWxlc2NlbmNlIG9mIGFsbCBhbGxlbGVzPyBEb2VzIGl0IGRlcGVuZCBvbiB3aGV0aGVyIG1pZ3JhdGlvbiBpcyBiZXR0ZXIgYXBwcm94aW1hdGVkIGJ5IGEgZmluaXRlIGlzbGFuZCBtb2RlbCBvciBhIG9uZS1kaW1lbnNpb25hbCBzdGVwcGluZyBzdG9uZSBtb2RlbD8KCjMuIEFyZSB0aGVyZSBjb25zaXN0ZW50IGRpZmZlcmVuY2VzIGJldHdlZW4gdGhlIGF2ZXJhZ2UgdGltZSB0byBjb2FsZXNjZW5jZSBpbiBhIGZpbml0ZSBpc2xhbmQgbW9kZWwgYW5kIGEgb25lLWRpbWVuc2lvbmFsIHN0ZXBwaW5nIHN0b25lIG1vZGVsPyBJZiB0aGVyZSBhcmUsIHdoYXQgbWlnaHQgZXhwbGFpbiB0aGUgZGlmZmVyZW5jZXMgdGhhdCB5b3Ugc2VlPwoKIyMjIEhpbnRzCgpgcnVuX3NpbXVsYXRpb25zKClgIHdpbGwgYXV0b21hdGljYWxseSBrZWVwIHRoZSBudW1iZXIgb2YgcG9wdWxhdGlvbnMgaW4gYm90aCBtb2RlbHMgdGhlIHNhbWUgdG8gZW5zdXJlIHRoYXQgeW91IGNhbiBhbHdheXMgbWFrZSBhcHByb3ByaWF0ZSBjb21wYXJpc29ucyBvZiB0aGUgbW9kZWxzLiBJdCB3aWxsIGFsc28gc2V0IHRoZSBsb2NhbCBlZmZlY3RpdmUgcG9wdWxhdGlvbiBzaXplIHRvIDI1LCBhbmQgaXQgc2V0cyB0aGUgbnVtYmVyIG9mIHJlcGxpY2F0aW9ucyB0byAxMDAwIGJ5IGRlZmF1bHQuIFlvdSBtaWdodCB3YW50IHRvIHJ1biB0aGUgZnVuY3Rpb24gb25jZSB3aXRoIGBuX3JlcHMgPSAxMDBgIHRvIGdldCBhIGZlZWwgZm9yIGhvdyBsb25nIGl0IHdpbGwgdGFrZSB0aGUgc2ltdWxhdGlvbiB0byBydW4gb24geW91ciBjb21wdXRlciBiZWZvcmUgeW91IGJlZ2luIHRoZSBmdWxsLXNjYWxlIHNpbXVsYXRpb25zIAoKYHJ1bl9zaW11bGF0aW9ucygpYCByZXR1cm5zIGEgZGF0YSBmcmFtZV5bV2VsbCwgYWN0dWFsbHkgYSB0aWJibGVdIHdpdGggdHdvIGNvbHVtbnM6IGBNb2RlbGAgYW5kIGBUaW1lYC4gSWYgeW91J3JlIGludGVyZXN0ZWQsIHlvdSBjYW4gdXNlIHRoYXQgdG8gZXhhbWluZSB0aGUgbWVkaWFuIHRpbWUgdG8gY29hbGVzY2VuY2UgKHJhdGhlciB0aGFuIHRoZSBtZWFuKSBhbmQgdGhlIHZhcmlhbmNlIChvciBzdGFuZGFyZCBkZXZpYXRpb24pIGluIGNvYWxlc2NlbmNlIHRpbWVzLiBZb3UnbGwgbm90aWNlIHRoYXQgYHJ1bl9zaW11bGF0aW9uKClgIGF1dG9tYXRpY2FsbHkgcHJpbnRzIG91dCB0aGUgbWVhbiBjb2FsZXNlbmNlIHRpbWVzIGZvciB5b3UuCgpJbiBhbnN3ZXJpbmcgcXVlc3Rpb24gIzMga2VlcCBpbiBtaW5kIHRoYXQgeW91ciBhbnN3ZXIgbWlnaHQgZGVwZW5kIG9uIGhvdyBtYW55IHBvcHVsYXRpb25zIHRoZXJlIGFyZS5eW1doeSBlbHNlIHdvdWxkIEkgaGF2ZSBhc2tlZCB5b3UgdG8gbG9vayBib3RoIGF0IG9uZSBleGFtcGxlIGluIHdoaWNoIHRuZSBudW1iZXIgb2YgcG9wdWxhdGlvbnMgaXMgMTAgb3IgZmV3ZXIgYW5kIGFub3RoZXIgaW4gd2hpY2ggdGhlIG51bWJlciBvZiBwb3B1bGF0aW9ucyBpcyAyNSBvciBtb3JlP10KCmBgYHtyfQojIyBvbmUtZGltZW5zaW9uYWwgc3RlcHBpbmcgc3RvbmUKIyMKb25lX2Rfc3RlcHBpbmdfc3RvbmUgPC0gZnVuY3Rpb24obl9lLCBtLCBuX3BvcHMpIHsKICBzdG9waWZub3QoKG0gPiAwKSAmJiAobSA8IDEpKQogIG1fbWF0cml4IDwtIGRpYWcoMSAtIG0sIG5yb3cgPSBuX3BvcHMpCiAgbV9tYXRyaXhbMSwgMl0gPC0gbQogIG1fbWF0cml4W25fcG9wcywgbl9wb3BzIC0gMV0gPC0gbQogIGZvciAoaSBpbiAyOihuX3BvcHMgLSAxKSkgewogICAgbV9tYXRyaXhbaSwgaSAtIDFdIDwtIG0vMgogICAgbV9tYXRyaXhbaSwgaSArIDFdIDwtIG0vMgogIH0KICBvcHRfc3RyaW5nIDwtIHBhc3RlKCItVCAtSSAiLCBuX3BvcHMsICIgIiwgc2VwID0gIiIpCiAgZm9yIChpIGluIDE6bl9wb3BzKSB7CiAgICBvcHRfc3RyaW5nIDwtIHBhc3RlKG9wdF9zdHJpbmcsIDIqbl9lLCAiICIsIHNlcCA9ICIiKQogIH0KICBvcHRfc3RyaW5nIDwtIHBhc3RlKG9wdF9zdHJpbmcsICItbWEiLCBzZXAgPSAiIikKICAjIyB0cmFuc3Bvc2UgbV9tYXRyaXggYmVmb3JlIGNvbnZlcnRpbmcgdG8gdmVjdG9yIHRvIGdldCB2ZWN0b3IgZnJvbSBtYXRyaXgKICAjIyBieSByb3cgaW5zdGVhZCBvZiBieSBjb2x1bW4KICAjIwogIG1fdmVjdG9yIDwtIDQqbl9lKmModChtX21hdHJpeCkpCiAgZm9yICggaSBpbiAxOmxlbmd0aChtX3ZlY3RvcikpIHsKICAgIG9wdF9zdHJpbmcgPC0gcGFzdGUob3B0X3N0cmluZywgIiAiLCBtX3ZlY3RvcltpXSwgc2VwID0gIiIpCiAgfQogIG1zX291dCA8LSBtcyhuc2FtID0gMipuX2Uqbl9wb3BzLCBucmVwcyA9IDEsIG9wdHMgPSBvcHRfc3RyaW5nKQogIHJldHVybihtc19vdXQpCn0KCnJ1bl9zaW11bGF0aW9uIDwtIGZ1bmN0aW9uKG5fcG9wcywgbSwgbl9yZXBzID0gMTAwMCkgewogIE5fZSA9IDI1CiAgcG9wX3NpemVzIDwtIHJlcChOX2UsIG5fcG9wcykKICBkZiA8LSB0aWJibGUoTW9kZWwgPSBOQSwgVGltZSA9IE5BKQogIGZvciAoaSBpbiAxOm5fcmVwcykgewogICAgbXNfb3V0IDwtIGlzbGFuZChwb3Bfc2l6ZXMsIE5fZSptKQogICAgbXNfdHJlZSA8LSByZWFkLnRyZWUodGV4dCA9IG1zX291dCkKICAgIGRmIDwtIGFkZF9yb3coZGYsCiAgICAgICAgICAgICAgICAgIE1vZGVsID0gIklzbGFuZCIsCiAgICAgICAgICAgICAgICAgIFRpbWUgPSAoNCpOX2Uqbl9wb3BzKSpicmFuY2hpbmcudGltZXMobXNfdHJlZSlbMV0pCiAgICBtc19vdXQgPC0gb25lX2Rfc3RlcHBpbmdfc3RvbmUoTl9lLCBtLCBuX3BvcHMpCiAgICBtc190cmVlIDwtIHJlYWQudHJlZSh0ZXh0ID0gbXNfb3V0KQogICAgZGYgPC0gYWRkX3JvdyhkZiwKICAgICAgICAgICAgICAgICAgTW9kZWwgPSAiMS1kIiwKICAgICAgICAgICAgICAgICAgVGltZSA9ICg0Kk5fZSpuX3BvcHMpKmJyYW5jaGluZy50aW1lcyhtc190cmVlKVsxXSkKICB9CiAgZGYgPC0gZmlsdGVyKGRmLCAhaXMubmEoTW9kZWwpKQogIHAgPC0gZ2dwbG90KGRmLCBhZXMoeCA9IFRpbWUsIGZpbGwgPSBNb2RlbCkpICsKICAgIGdlb21faGlzdG9ncmFtKHBvc2l0aW9uID0gImlkZW50aXR5IiwgYmlucyA9IG5fcmVwcy8xMCwgYWxwaGEgPSAwLjQpICsKICAgIGdndGl0bGUocGFzdGUoIm5fcG9wcyA9ICIsIG5fcG9wcywgIiwgbSA9ICIsIG0pKSArCiAgICB0aGVtZV9idygpCiAgcHJpbnQocCkKICBzdW0gPC0gZGYgJT4lIGdyb3VwX2J5KE1vZGVsKSAlPiUKICAgIHN1bW1hcml6ZShNZWFuX1RpbWUgPSBtZWFuKFRpbWUpKQogIHByaW50KHN1bSkKICByZXR1cm4oZGYpCn0KYGBgCg==