Session 3: Introduction to MCMC in R (Computing Practical)

Example 1: sampling from an exponential distribution using MCMC

Exercises: use the function easyMCMC to explore the following:

A Bimodal Target

Example 2: Estimating an allele frequency

Have fun exploring!

Example 3: Estimating an allele frequency and inbreeding coefficient

Exercise: write a short MCMC routine to sample from the joint distribution of $f$ and $p$ .

Session Info

Example 1: sampling from an exponential distribution using MCMC

Plot the exponential distribution:

x <- seq(from = 0, to = 10, length=20)

Warning message:
In scan(file = file, what = what, sep = sep, quote = quote, dec = dec,  :
  EOF within quoted string

y <- exp(-x)
plot(x,y)
lines(x,y) #lines adds lines to an existing plot

Now: set up a target function we want to sample from In this case we are going to use the density of the exponential distribution

target <- function(x){
  if (x < 0) {
    return(0)
  } else {
    return(exp(-x))
  }
}

Try computing a couple of values

target(3)

[1] 0.04978707

target(-1)

[1] 0

Next, we will program a Metropolis–Hastings scheme to sample from a distribution proportional to the target

x <- rep(0, 1000)
x[1] <- 3     # this is just a starting value, which I’ve set arbitrarily to 3
for (i in 2:1000) {
  currentx <- x[i - 1]
  proposedx <- currentx + rnorm(1, mean = 0, sd = 1)
  A <- target(proposedx) / target(currentx)
  if (runif(1) < A) {
    x[i] <- proposedx
  } else {
    x[i] <- currentx
  }
}

Note that x is a realisation of a Markov Chain. We can make a few plots of x:

plot(x)

hist(x)

We can wrap this up in a function to make things a bit neater, and make it easy to try changing starting values and proposal distributions

easyMCMC <- function(niter, startval, proposalsd) {
  x <- rep(0, niter)
  x[1] <- startval
  for (i in 2:niter) {
    currentx <- x[i - 1]
    proposedx <- rnorm(1, mean = currentx, sd = proposalsd)
    A <- target(proposedx) / target(currentx)
    if (runif(1) < A) {
      x[i] <- proposedx
    } else {
      x[i] <- currentx
    }
  }
  return(x)
}

Now we’ll run the MCMC scheme 3 times, and look to see how similar the results are

z1 <- easyMCMC(1000,3,1)
z2 <- easyMCMC(1000,3,1)
z3 <- easyMCMC(1000,3,1)
plot(z1, type = "l")
lines(z2, col = 2)

lines(z3, col = 3)

par(mfcol = c(3, 1)) # rather odd command tells R to put 3 graphs on a single page
hist(z1)
hist(z2)

hist(z3)

Exercises: use the function easyMCMC to explore the following:

1a) how do different starting values affect the MCMC scheme?

sv <- seq(1, 50, 1)
z1 <- list()
for (i in 1:length(sv)) {
    z1[[i]] <- easyMCMC(1000, sv[i], 1)
}
par(mfrow = c(1, 2))
plot(sv, as.numeric(lapply(z1, mean)), xlab = "starting value", ylab = "posterior mean")
plot(sv, as.numeric(lapply(z1, var)), xlab = "starting value", ylab = "posterior variance")

par(mfrow = c(1, 3))
hist(z1[[1]])
hist(z1[[25]])

hist(z1[[50]])

par(mfrow = c(1, 3))
plot(z1[[1]], type = "l")
plot(z1[[20]], type = "l")

plot(z1[[50]], type = "l")

1b) what is the effect of having a bigger/smaller proposal standard deviation?

prop_sd <- seq(1,100,1)
z2 <- list()
for (i in 1:length(prop_sd)) {
    z2[[i]] <- easyMCMC(1000, 3, prop_sd[i])
}
par(mfrow = c(1, 2))
plot(prop_sd, as.numeric(lapply(z2,mean)), xlab = "proposal_sd", ylab = "posterior mean")
plot(prop_sd, as.numeric(lapply(z2,var)), xlab = "proposal_sd", ylab = "posterior variance")

par(mfrow = c(1, 3))
hist(z2[[1]])
hist(z2[[25]])

hist(z2[[50]])

par(mfrow = c(1, 3))
plot(z2[[1]], type = "l")
plot(z2[[20]], type = "l")

plot(z2[[50]], type = "l")

A Bimodal Target

Try changing the target function to the following

target <- function(x){
return((x > 0 & x < 1) + (x > 2 & x < 3))
}

What does this target look like? BIMODAL

x <- seq(-1,6,0.01)
plot(x, target(x), type = "l")

There is positive probability only for values between 0 and 1 and between 2 and 3.

z1 <- easyMCMC(1000, 2.5, 1)
z2 <- easyMCMC(1000, 0.7, 1)
z3 <- easyMCMC(1000, 0.5, 1)
par(mfrow = c(1, 3))
hist(z1)
hist(z2)

hist(z3)

And look at the points visited

par(mfrow = c(1, 3))
plot(z1)
plot(z2)

plot(z3)

What happens if the proposal sd is too small here? (try eg 1 and 0.1) values within the two groups work

z1 <- easyMCMC(1000, 2.5, 0.1)
z2 <- easyMCMC(1000, 0.5, 0.1)
par(mfrow = c(1, 3))
hist(z1, xlim = c(0, 3))
hist(z2, xlim = c(0, 3))

plot(z1, type = "l", ylim = c(0, 3))
points(z2, type = "l", col = "dark grey")

Try starting it on a value that is not in (0,1) nor (2,3). It fails. Why?

z1 <- easyMCMC(1000, 1.5, 0.1)
hist(z1)
plot(1:1000, z1)

Example 2: Estimating an allele frequency

A standard assumption when modelling genotypes of bi-allelic loci (eg loci with alleles $A$ and $a$ ) is that the population is “randomly mating”. From this assumption it follows that the population will be in “Hardy Weinberg Equilibrium” (HWE), which means that if $p$ is the frequency of the allele $A$ then the genotypes $AA$ , $Aa$ and $aa$ will have frequencies $p^2$ , $2p(1-p)$ , and $(1-p)^2$ .

A simple prior for $p$ is to assume it is uniform on $(0,1)$ . Suppose that we sample $n$ individuals, and observe $n_{AA}$ with genotype $AA$ , $n_{Aa}$ with genotype $Aa$ and $n_{aa}$ with genotype $aa$ .

The following R code gives a short MCMC routine to sample from the posterior distribution of $p$ . Try to go through the code to see how it works.

Note that this is very similar to the example at the end of Session 2, but it is interesting in that the likelihood is given in terms of $n_{AA}$ , $n_{Aa}$ , and $n_{aa}$ rather than simply in terms of the number of $A$ and $a$ alleles found in the sample.

prior <- function(p){
  if((p < 0) || (p > 1)){ # || here means "or"
    return(0)
  } else{ 
    return(1)
  } 
}
likelihood <- function(p, nAA, nAa, naa) {
    return(p ^ (2 * nAA) * (2 * p * (1-p)) ^ nAa * (1 - p) ^ (2 * naa))
}
psampler <- function(nAA, nAa, naa, niter, pstartval, pproposalsd) {
  p <- rep(0, niter)
  p[1] <- pstartval
  for (i in 2:niter) {
    currentp <- p[i - 1]
    newp <- currentp + rnorm(1, 0, pproposalsd)
    A <- prior(newp) * likelihood(newp, nAA, nAa, naa) / (prior(currentp) * likelihood(currentp, nAA, nAa, naa))
    if (runif(1) < A){
      p[i] <- newp
    } else {
      p[i] <- currentp
    }
  }
  return(p)
}

Now run this sample for $nAA = 50$ , $nAa = 21$ , $naa=29$ .

z <- psampler(50,21,29,10000,0.5,0.01)

Now some R code to compare the sample from the posterior with the theoretical posterior (which in this case is available analytically; from lecture 1, since we observed 121 $A$ ’s, and 79 $a$ ’s, out of 200, the posterior for $p$ is $\mathrm{Beta}(121+1,79+1)$ . See notes from Session 1.

par(mfcol = c(1, 2))
x <- seq(0,1,length = 1000)
hist(z, prob = T, xlim = c(0.4, 0.8), col = "dark grey", ylim = c(0, 20), main = "No Burn in")
lines(x,dbeta(x,122, 80))  # overlays beta density on histogram

# You might also like to discard the first 5000 z’s as "burnin"
# here’s one way in R to select only the last 5000 zs:
hist(z[5001:10000], prob = T, col = "light grey",  xlim = c(0.4, 0.8), ylim = c(0, 20), main = "With Burn in")
lines(x, dbeta(x, 122, 80))  # overlays beta density on histogram

Have fun exploring!

Some things to try: how do the starting point and proposal sd affect things?

Example 3: Estimating an allele frequency and inbreeding coefficient

(If time allows!)

A slightly more complex alternative than HWE is to assume that there is a tendency for people to mate with others who are slightly more closely-related than “random” (as might happen in a geographically-structured population, for example). This will result in an excess of homozygotes compared with HWE. A simple way to capture this is to introduce an extra parameter, the “inbreeding coefficient” $f$ , and assume that the genotypes $AA$ , $Aa$ and $aa$ have frequencies $fp + (1-f)p^2$ , $(1-f) 2p(1-p)$ , and $f(1-p) + (1-f)(1-p)^2$ .

In most cases it would be natural to treat $f$ as a feature of the population, and therefore assume f is constant across loci. For simplicity we will consider just a single locus. Note that both $f$ and $p$ are constrained to lie between 0 and 1 (inclusive). A simple prior for each of these two parameters is to assume that they are independent, uniform on [0,1]. Suppose that we sample $n$ individuals, and observe $n_{AA}$ with genotype $AA$ , $n_{Aa}$ with genotype $Aa$ and $n_{aa}$ with genotype $aa$ .

Exercise: write a short MCMC routine to sample from the joint distribution of $f$ and $p$ .

Here is what it looks like.

prior <- function(p) {
  if ((p < 0) || (p > 1)) { # || here means "or"
    return(0)
  } else { 
    return(1)
  } 
}
likelihood <- function(p, f, nAA, nAa, naa) {
    return(((f * p) + ((1 - f) * (p ^ 2)))^nAA * 
             ((1 - f) * 2 * p * (1 - p)) ^ nAa * 
             (f * (1 - p) + (1 - f) * ((1 - p) * (1 - p))) ^ naa
           )
}
fpsampler <- function(nAA, nAa, naa, niter, 
                      fstartval, pstartval,
                      fproposalsd, pproposalsd) {
    f <- rep(0,niter)
    p <- rep(0,niter)
    f[1] <- fstartval
    p[1] <- pstartval
    for (i in 2:niter) {
        currentp <- p[i - 1]
        currentf <- f[i - 1]
        newp <- currentp + rnorm(1, 0, pproposalsd)
        A <- prior(newp) * likelihood(newp,currentf,nAA,nAa,naa) /
          (prior(currentp) * likelihood(currentp,currentf,nAA,nAa,naa))
        
        if (runif(1) < A) {
          p[i] <- newp
        } else {
          p[i] <- currentp
        }
        newf <- currentf + rnorm(1, 0, fproposalsd)
        
        A <- prior(newf) * likelihood(p[i],newf,nAA,nAa,naa) / 
          (prior(currentf) * likelihood(p[i],currentf,nAA,nAa,naa))
        
        
        if (runif(1) < A) {
          f[i] <- newf
        } else {
          f[i] <- currentf
        }
    }
    
    return(list(f = f,p = p)) # return a "list" with two elements named f and p
}

Then run it for a sample with $n_{AA} = 45$ , $n_{Aa} = 10$ , and $n_{aa} = 45$ , which clearly is a case where there are far fewer heterozygotes than one would expect under Hardy-Weinberg equilibrium.

z <- fpsampler(45, 10, 45, 10000, 0.8, 0.5, 0.01, 0.01)

Let’s plot those results:

x <- seq(0, 1, length = 1000)
par(mfrow = c(1,2))
hist(z$f[5000:10000],prob = T, xlim = c(0, 1), col = "dark grey", ylim = c(0, 10), 
     main = "f sample", xlab = "posterior estimate")
hist(z$p[5000:10000], prob = T, xlim = c(0, 1), col = "dark grey", ylim = c(0, 10), 
     main = "p sample", xlab = "posterior estimate")

And look at some trace plots:

par(mfrow = c(1, 2))
plot(z$f, type = "l")
plot(z$p, type = "l")

If we want to summarize those samples to a single point for $p$ and for $f$ a good choice is the posterior mean, which is just the mean from the sample from the Markov chain.

# mean for p
p_mean <- mean(z$p)
# mean for f
f_mean <- mean(z$f)

And it is always a good idea to simulate new data from the an estimated model, or look at the expected value of data from an estimated model, to see if it looks anything like the data that went into it.

We can do that by finding the expected number of the three genotypes given the posterior mean estimates of $f$ and $p$ :

N <- 100
c(nAA = ((p_mean ^ 2) + (f_mean * (1 - p_mean) * p_mean)) * N,
  nAa = ((1 - f_mean) * 2 * p_mean * (1 - p_mean)) * N,
  naa = ((f_mean * (1 - p_mean) * p_mean) + ((1 - p_mean)^2)) * N)

     nAA      nAa      naa 
44.23173 10.97835 44.78992

Yep…that looks like our observed data…

Session Info

sessionInfo()

R version 3.4.3 (2017-11-30)
Platform: x86_64-apple-darwin15.6.0 (64-bit)
Running under: macOS Sierra 10.12.6

Matrix products: default
BLAS: /System/Library/Frameworks/Accelerate.framework/Versions/A/Frameworks/vecLib.framework/Versions/A/libBLAS.dylib
LAPACK: /Library/Frameworks/R.framework/Versions/3.4/Resources/lib/libRlapack.dylib

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

loaded via a namespace (and not attached):
 [1] compiler_3.4.3  backports_1.1.2 magrittr_1.5    rprojroot_1.3-2
 [5] htmltools_0.3.6 tools_3.4.3     base64enc_0.1-3 yaml_2.1.16    
 [9] Rcpp_0.12.16    stringi_1.1.7   rmarkdown_1.8   knitr_1.18     
[13] jsonlite_1.5    stringr_1.3.0   digest_0.6.15   evaluate_0.10.1

LS0tCnRpdGxlOiAiU2Vzc2lvbiAzOiBJbnRyb2R1Y3Rpb24gdG8gTUNNQyBpbiBSIChDb21wdXRpbmcgUHJhY3RpY2FsKSIKZGVzY3JpcHRpb246IFRoaXMgaXMgdGhlIHNlc3Npb24gY29kZSBpbiBub3RlYm9vayBmb3JtYXQuCm91dHB1dDogCiAgaHRtbF9ub3RlYm9vazoKICAgIHRvYzogdHJ1ZQogICAgdG9jX2Zsb2F0OiB0cnVlCi0tLQoKCiMjIEV4YW1wbGUgMTogc2FtcGxpbmcgZnJvbSBhbiBleHBvbmVudGlhbCBkaXN0cmlidXRpb24gdXNpbmcgTUNNQwoKUGxvdCB0aGUgZXhwb25lbnRpYWwgZGlzdHJpYnV0aW9uOgpgYGB7cn0KeCA8LSBzZXEoZnJvbSA9IDAsIHRvID0gMTAsIGxlbmd0aD0yMCkKeSA8LSBleHAoLXgpCnBsb3QoeCx5KQpsaW5lcyh4LHkpICNsaW5lcyBhZGRzIGxpbmVzIHRvIGFuIGV4aXN0aW5nIHBsb3QKYGBgCgpOb3c6IHNldCB1cCBhIHRhcmdldCBmdW5jdGlvbiB3ZSB3YW50IHRvIHNhbXBsZSBmcm9tCkluIHRoaXMgY2FzZSB3ZSBhcmUgZ29pbmcgdG8gdXNlIHRoZSBkZW5zaXR5IG9mIHRoZSBleHBvbmVudGlhbCBkaXN0cmlidXRpb24KCmBgYHtyfQp0YXJnZXQgPC0gZnVuY3Rpb24oeCl7CiAgaWYgKHggPCAwKSB7CiAgICByZXR1cm4oMCkKICB9IGVsc2UgewogICAgcmV0dXJuKGV4cCgteCkpCiAgfQp9CmBgYAoKVHJ5IGNvbXB1dGluZyBhIGNvdXBsZSBvZiB2YWx1ZXMKYGBge3J9CnRhcmdldCgzKQp0YXJnZXQoLTEpCmBgYAoKTmV4dCwgd2Ugd2lsbCBwcm9ncmFtIGEgTWV0cm9wb2xpcy0tSGFzdGluZ3Mgc2NoZW1lIHRvIHNhbXBsZQpmcm9tIGEgZGlzdHJpYnV0aW9uIHByb3BvcnRpb25hbCB0byB0aGUgdGFyZ2V0CmBgYHtyfQp4IDwtIHJlcCgwLCAxMDAwKQp4WzFdIDwtIDMgICAgICMgdGhpcyBpcyBqdXN0IGEgc3RhcnRpbmcgdmFsdWUsIHdoaWNoIEnigJl2ZSBzZXQgYXJiaXRyYXJpbHkgdG8gMwoKZm9yIChpIGluIDI6MTAwMCkgewogIGN1cnJlbnR4IDwtIHhbaSAtIDFdCiAgcHJvcG9zZWR4IDwtIGN1cnJlbnR4ICsgcm5vcm0oMSwgbWVhbiA9IDAsIHNkID0gMSkKICBBIDwtIHRhcmdldChwcm9wb3NlZHgpIC8gdGFyZ2V0KGN1cnJlbnR4KQogIGlmIChydW5pZigxKSA8IEEpIHsKICAgIHhbaV0gPC0gcHJvcG9zZWR4CiAgfSBlbHNlIHsKICAgIHhbaV0gPC0gY3VycmVudHgKICB9Cn0KYGBgCgpOb3RlIHRoYXQgeCBpcyBhIHJlYWxpc2F0aW9uIG9mIGEgTWFya292IENoYWluLgpXZSBjYW4gbWFrZSBhIGZldyBwbG90cyBvZiB4OgpgYGB7cn0KcGxvdCh4KQpoaXN0KHgpCmBgYAoKV2UgY2FuIHdyYXAgdGhpcyB1cCBpbiBhIGZ1bmN0aW9uIHRvIG1ha2UgdGhpbmdzIGEgYml0IG5lYXRlciwKYW5kIG1ha2UgaXQgZWFzeSB0byB0cnkgY2hhbmdpbmcgc3RhcnRpbmcgdmFsdWVzIGFuZCBwcm9wb3NhbCBkaXN0cmlidXRpb25zCmBgYHtyfQplYXN5TUNNQyA8LSBmdW5jdGlvbihuaXRlciwgc3RhcnR2YWwsIHByb3Bvc2Fsc2QpIHsKICB4IDwtIHJlcCgwLCBuaXRlcikKICB4WzFdIDwtIHN0YXJ0dmFsCiAgZm9yIChpIGluIDI6bml0ZXIpIHsKICAgIGN1cnJlbnR4IDwtIHhbaSAtIDFdCiAgICBwcm9wb3NlZHggPC0gcm5vcm0oMSwgbWVhbiA9IGN1cnJlbnR4LCBzZCA9IHByb3Bvc2Fsc2QpCiAgICBBIDwtIHRhcmdldChwcm9wb3NlZHgpIC8gdGFyZ2V0KGN1cnJlbnR4KQogICAgaWYgKHJ1bmlmKDEpIDwgQSkgewogICAgICB4W2ldIDwtIHByb3Bvc2VkeAogICAgfSBlbHNlIHsKICAgICAgeFtpXSA8LSBjdXJyZW50eAogICAgfQogIH0KICByZXR1cm4oeCkKfQpgYGAKCk5vdyB3ZeKAmWxsIHJ1biB0aGUgTUNNQyBzY2hlbWUgMyB0aW1lcywKYW5kIGxvb2sgdG8gc2VlIGhvdyBzaW1pbGFyIHRoZSByZXN1bHRzIGFyZQpgYGB7cn0KejEgPC0gZWFzeU1DTUMoMTAwMCwzLDEpCnoyIDwtIGVhc3lNQ01DKDEwMDAsMywxKQp6MyA8LSBlYXN5TUNNQygxMDAwLDMsMSkKcGxvdCh6MSwgdHlwZSA9ICJsIikKbGluZXMoejIsIGNvbCA9IDIpCmxpbmVzKHozLCBjb2wgPSAzKQpgYGAKCmBgYHtyfQpwYXIobWZjb2wgPSBjKDMsIDEpKSAjIHJhdGhlciBvZGQgY29tbWFuZCB0ZWxscyBSIHRvIHB1dCAzIGdyYXBocyBvbiBhIHNpbmdsZSBwYWdlCmhpc3QoejEpCmhpc3QoejIpCmhpc3QoejMpCmBgYAoKIyMjIEV4ZXJjaXNlczogdXNlIHRoZSBmdW5jdGlvbiBlYXN5TUNNQyB0byBleHBsb3JlIHRoZSBmb2xsb3dpbmc6CgojIyMjIDFhKSBob3cgZG8gZGlmZmVyZW50IHN0YXJ0aW5nIHZhbHVlcyBhZmZlY3QgdGhlIE1DTUMgc2NoZW1lPwpgYGB7cn0Kc3YgPC0gc2VxKDEsIDUwLCAxKQp6MSA8LSBsaXN0KCkKZm9yIChpIGluIDE6bGVuZ3RoKHN2KSkgewoJejFbW2ldXSA8LSBlYXN5TUNNQygxMDAwLCBzdltpXSwgMSkKfQpwYXIobWZyb3cgPSBjKDEsIDIpKQpwbG90KHN2LCBhcy5udW1lcmljKGxhcHBseSh6MSwgbWVhbikpLCB4bGFiID0gInN0YXJ0aW5nIHZhbHVlIiwgeWxhYiA9ICJwb3N0ZXJpb3IgbWVhbiIpCnBsb3Qoc3YsIGFzLm51bWVyaWMobGFwcGx5KHoxLCB2YXIpKSwgeGxhYiA9ICJzdGFydGluZyB2YWx1ZSIsIHlsYWIgPSAicG9zdGVyaW9yIHZhcmlhbmNlIikKYGBgCmBgYHtyfQpwYXIobWZyb3cgPSBjKDEsIDMpKQpoaXN0KHoxW1sxXV0pCmhpc3QoejFbWzI1XV0pCmhpc3QoejFbWzUwXV0pCmBgYAoKYGBge3J9CnBhcihtZnJvdyA9IGMoMSwgMykpCnBsb3QoejFbWzFdXSwgdHlwZSA9ICJsIikKcGxvdCh6MVtbMjBdXSwgdHlwZSA9ICJsIikKcGxvdCh6MVtbNTBdXSwgdHlwZSA9ICJsIikKYGBgCgoKIyMjIyAxYikgd2hhdCBpcyB0aGUgZWZmZWN0IG9mIGhhdmluZyBhIGJpZ2dlci9zbWFsbGVyIHByb3Bvc2FsIHN0YW5kYXJkIGRldmlhdGlvbj8KYGBge3J9CnByb3Bfc2QgPC0gc2VxKDEsMTAwLDEpCnoyIDwtIGxpc3QoKQpmb3IgKGkgaW4gMTpsZW5ndGgocHJvcF9zZCkpIHsKCXoyW1tpXV0gPC0gZWFzeU1DTUMoMTAwMCwgMywgcHJvcF9zZFtpXSkKfQpwYXIobWZyb3cgPSBjKDEsIDIpKQpwbG90KHByb3Bfc2QsIGFzLm51bWVyaWMobGFwcGx5KHoyLG1lYW4pKSwgeGxhYiA9ICJwcm9wb3NhbF9zZCIsIHlsYWIgPSAicG9zdGVyaW9yIG1lYW4iKQpwbG90KHByb3Bfc2QsIGFzLm51bWVyaWMobGFwcGx5KHoyLHZhcikpLCB4bGFiID0gInByb3Bvc2FsX3NkIiwgeWxhYiA9ICJwb3N0ZXJpb3IgdmFyaWFuY2UiKQpgYGAKYGBge3J9CnBhcihtZnJvdyA9IGMoMSwgMykpCmhpc3QoejJbWzFdXSkKaGlzdCh6MltbMjVdXSkKaGlzdCh6MltbNTBdXSkKYGBgCgpgYGB7cn0KcGFyKG1mcm93ID0gYygxLCAzKSkKcGxvdCh6MltbMV1dLCB0eXBlID0gImwiKQpwbG90KHoyW1syMF1dLCB0eXBlID0gImwiKQpwbG90KHoyW1s1MF1dLCB0eXBlID0gImwiKQpgYGAKCiMjIEEgQmltb2RhbCBUYXJnZXQKVHJ5IGNoYW5naW5nIHRoZSB0YXJnZXQgZnVuY3Rpb24gdG8gdGhlIGZvbGxvd2luZwpgYGB7cn0KdGFyZ2V0IDwtIGZ1bmN0aW9uKHgpewpyZXR1cm4oKHggPiAwICYgeCA8IDEpICsgKHggPiAyICYgeCA8IDMpKQp9CmBgYApXaGF0IGRvZXMgdGhpcyB0YXJnZXQgbG9vayBsaWtlPyBCSU1PREFMCmBgYHtyfQp4IDwtIHNlcSgtMSw2LDAuMDEpCnBsb3QoeCwgdGFyZ2V0KHgpLCB0eXBlID0gImwiKQpgYGAKVGhlcmUgaXMgcG9zaXRpdmUgcHJvYmFiaWxpdHkgb25seSBmb3IgdmFsdWVzIGJldHdlZW4gMCBhbmQgMSBhbmQgYmV0d2VlbiAyIGFuZCAzLgpgYGB7cn0KejEgPC0gZWFzeU1DTUMoMTAwMCwgMi41LCAxKQp6MiA8LSBlYXN5TUNNQygxMDAwLCAwLjcsIDEpCnozIDwtIGVhc3lNQ01DKDEwMDAsIDAuNSwgMSkKcGFyKG1mcm93ID0gYygxLCAzKSkKaGlzdCh6MSkKaGlzdCh6MikKaGlzdCh6MykKYGBgCkFuZCBsb29rIGF0IHRoZSBwb2ludHMgdmlzaXRlZApgYGB7cn0KcGFyKG1mcm93ID0gYygxLCAzKSkKcGxvdCh6MSkKcGxvdCh6MikKcGxvdCh6MykKYGBgCgoKV2hhdCBoYXBwZW5zIGlmIHRoZSBwcm9wb3NhbCBzZCBpcyB0b28gc21hbGwgaGVyZT8gKHRyeSBlZyAxIGFuZCAwLjEpCnZhbHVlcyB3aXRoaW4gdGhlIHR3byBncm91cHMgd29yayAKYGBge3J9CnoxIDwtIGVhc3lNQ01DKDEwMDAsIDIuNSwgMC4xKQp6MiA8LSBlYXN5TUNNQygxMDAwLCAwLjUsIDAuMSkKcGFyKG1mcm93ID0gYygxLCAzKSkKaGlzdCh6MSwgeGxpbSA9IGMoMCwgMykpCmhpc3QoejIsIHhsaW0gPSBjKDAsIDMpKQpwbG90KHoxLCB0eXBlID0gImwiLCB5bGltID0gYygwLCAzKSkKcG9pbnRzKHoyLCB0eXBlID0gImwiLCBjb2wgPSAiZGFyayBncmV5IikKYGBgCgpUcnkgc3RhcnRpbmcgaXQgb24gYSB2YWx1ZSB0aGF0IGlzIG5vdCBpbiAoMCwxKSBub3IgKDIsMykuICBJdCBmYWlscy4gV2h5PwpgYGB7ciwgZXZhbD1GQUxTRX0KejEgPC0gZWFzeU1DTUMoMTAwMCwgMS41LCAwLjEpCmhpc3QoejEpCnBsb3QoMToxMDAwLCB6MSkKYGBgCgoKCgoKCgoKIyMgRXhhbXBsZSAyOiBFc3RpbWF0aW5nIGFuIGFsbGVsZSBmcmVxdWVuY3kKCkEgc3RhbmRhcmQgYXNzdW1wdGlvbiB3aGVuIG1vZGVsbGluZyBnZW5vdHlwZXMgb2YKYmktYWxsZWxpYyBsb2NpIChlZyBsb2NpIHdpdGggYWxsZWxlcyAkQSQgYW5kICRhJCkgaXMKdGhhdCB0aGUgcG9wdWxhdGlvbiBpcyAicmFuZG9tbHkgbWF0aW5nIi4gRnJvbSB0aGlzIGFzc3VtcHRpb24KaXQgZm9sbG93cyB0aGF0IHRoZSBwb3B1bGF0aW9uIHdpbGwgYmUgaW4KIkhhcmR5IFdlaW5iZXJnIEVxdWlsaWJyaXVtIiAoSFdFKSwgd2hpY2ggbWVhbnMgdGhhdAppZiAkcCQgaXMgdGhlIGZyZXF1ZW5jeSBvZiB0aGUgYWxsZWxlICRBJCB0aGVuIHRoZQpnZW5vdHlwZXMgJEFBJCwgJEFhJCBhbmQgJGFhJCB3aWxsIGhhdmUgZnJlcXVlbmNpZXMKJHBeMiQsICQycCgxLXApJCwgYW5kICQoMS1wKV4yJC4KCkEgc2ltcGxlIHByaW9yIGZvciAkcCQgaXMgdG8gYXNzdW1lIGl0IGlzIHVuaWZvcm0gb24gJCgwLDEpJC4KU3VwcG9zZSB0aGF0IHdlIHNhbXBsZSAkbiQgaW5kaXZpZHVhbHMsIGFuZCBvYnNlcnZlICRuX3tBQX0kIHdpdGggZ2Vub3R5cGUgJEFBJCwKJG5fe0FhfSQgd2l0aCBnZW5vdHlwZSAkQWEkIGFuZCAkbl97YWF9JCB3aXRoIGdlbm90eXBlICRhYSQuCgpUaGUgZm9sbG93aW5nIFIgY29kZSBnaXZlcyBhIHNob3J0IE1DTUMgcm91dGluZSB0byBzYW1wbGUgZnJvbSB0aGUgcG9zdGVyaW9yCmRpc3RyaWJ1dGlvbiBvZiAkcCQuIFRyeSB0byBnbyB0aHJvdWdoIHRoZSBjb2RlIHRvIHNlZSBob3cgaXQgd29ya3MuCgpOb3RlIHRoYXQgdGhpcyBpcyB2ZXJ5IHNpbWlsYXIgdG8gdGhlIGV4YW1wbGUgYXQgdGhlIGVuZCBvZiBTZXNzaW9uIDIsIGJ1dCBpdCAKaXMgaW50ZXJlc3RpbmcgaW4gdGhhdCB0aGUgbGlrZWxpaG9vZCBpcyBnaXZlbiBpbiB0ZXJtcyBvZiAkbl97QUF9JCwgJG5fe0FhfSQsCmFuZCAkbl97YWF9JCByYXRoZXIgdGhhbiBzaW1wbHkgaW4gdGVybXMgb2YgdGhlIG51bWJlciBvZiAkQSQgYW5kICRhJCBhbGxlbGVzIGZvdW5kCmluIHRoZSBzYW1wbGUuCmBgYHtyfQpwcmlvciA8LSBmdW5jdGlvbihwKXsKICBpZigocCA8IDApIHx8IChwID4gMSkpeyAjIHx8IGhlcmUgbWVhbnMgIm9yIgogICAgcmV0dXJuKDApCiAgfSBlbHNleyAKICAgIHJldHVybigxKQogIH0gCn0KCmxpa2VsaWhvb2QgPC0gZnVuY3Rpb24ocCwgbkFBLCBuQWEsIG5hYSkgewoJcmV0dXJuKHAgXiAoMiAqIG5BQSkgKiAoMiAqIHAgKiAoMS1wKSkgXiBuQWEgKiAoMSAtIHApIF4gKDIgKiBuYWEpKQp9Cgpwc2FtcGxlciA8LSBmdW5jdGlvbihuQUEsIG5BYSwgbmFhLCBuaXRlciwgcHN0YXJ0dmFsLCBwcHJvcG9zYWxzZCkgewogIHAgPC0gcmVwKDAsIG5pdGVyKQogIHBbMV0gPC0gcHN0YXJ0dmFsCiAgZm9yIChpIGluIDI6bml0ZXIpIHsKICAgIGN1cnJlbnRwIDwtIHBbaSAtIDFdCiAgICBuZXdwIDwtIGN1cnJlbnRwICsgcm5vcm0oMSwgMCwgcHByb3Bvc2Fsc2QpCiAgICBBIDwtIHByaW9yKG5ld3ApICogbGlrZWxpaG9vZChuZXdwLCBuQUEsIG5BYSwgbmFhKSAvIChwcmlvcihjdXJyZW50cCkgKiBsaWtlbGlob29kKGN1cnJlbnRwLCBuQUEsIG5BYSwgbmFhKSkKICAgIGlmIChydW5pZigxKSA8IEEpewogICAgICBwW2ldIDwtIG5ld3AKICAgIH0gZWxzZSB7CiAgICAgIHBbaV0gPC0gY3VycmVudHAKICAgIH0KICB9CiAgcmV0dXJuKHApCn0KYGBgCgoKTm93IHJ1biB0aGlzIHNhbXBsZSBmb3IgJG5BQSA9IDUwJCwgJG5BYSA9IDIxJCwgICRuYWE9MjkkLgpgYGB7cn0KeiA8LSBwc2FtcGxlcig1MCwyMSwyOSwxMDAwMCwwLjUsMC4wMSkKYGBgCgpOb3cgc29tZSBSIGNvZGUgdG8gY29tcGFyZSB0aGUgc2FtcGxlIGZyb20gdGhlIHBvc3Rlcmlvcgp3aXRoIHRoZSB0aGVvcmV0aWNhbCBwb3N0ZXJpb3IgKHdoaWNoIGluIHRoaXMgY2FzZSBpcyBhdmFpbGFibGUgYW5hbHl0aWNhbGx5Owpmcm9tIGxlY3R1cmUgMSwgc2luY2Ugd2Ugb2JzZXJ2ZWQgMTIxICRBJCdzLCBhbmQgNzkgJGEkJ3MsIG91dCBvZiAyMDAsIHRoZSBwb3N0ZXJpb3IKZm9yICRwJCBpcyAkXG1hdGhybXtCZXRhfSgxMjErMSw3OSsxKSQuIFNlZSBub3RlcyBmcm9tIFNlc3Npb24gMS4KCmBgYHtyfQpwYXIobWZjb2wgPSBjKDEsIDIpKQp4IDwtIHNlcSgwLDEsbGVuZ3RoID0gMTAwMCkKaGlzdCh6LCBwcm9iID0gVCwgeGxpbSA9IGMoMC40LCAwLjgpLCBjb2wgPSAiZGFyayBncmV5IiwgeWxpbSA9IGMoMCwgMjApLCBtYWluID0gIk5vIEJ1cm4gaW4iKQpsaW5lcyh4LGRiZXRhKHgsMTIyLCA4MCkpICAjIG92ZXJsYXlzIGJldGEgZGVuc2l0eSBvbiBoaXN0b2dyYW0KCiMgWW91IG1pZ2h0IGFsc28gbGlrZSB0byBkaXNjYXJkIHRoZSBmaXJzdCA1MDAwIHrigJlzIGFzICJidXJuaW4iCiMgaGVyZeKAmXMgb25lIHdheSBpbiBSIHRvIHNlbGVjdCBvbmx5IHRoZSBsYXN0IDUwMDAgenM6Cmhpc3Qoels1MDAxOjEwMDAwXSwgcHJvYiA9IFQsIGNvbCA9ICJsaWdodCBncmV5IiwgIHhsaW0gPSBjKDAuNCwgMC44KSwgeWxpbSA9IGMoMCwgMjApLCBtYWluID0gIldpdGggQnVybiBpbiIpCmxpbmVzKHgsIGRiZXRhKHgsIDEyMiwgODApKSAgIyBvdmVybGF5cyBiZXRhIGRlbnNpdHkgb24gaGlzdG9ncmFtCmBgYAoKCiMjIEhhdmUgZnVuIGV4cGxvcmluZyEKClNvbWUgdGhpbmdzIHRvIHRyeTogaG93IGRvIHRoZSBzdGFydGluZyBwb2ludCBhbmQgcHJvcG9zYWwgc2QgYWZmZWN0IHRoaW5ncz8KCgoKCiMjIEV4YW1wbGUgMzogRXN0aW1hdGluZyBhbiBhbGxlbGUgZnJlcXVlbmN5IGFuZCBpbmJyZWVkaW5nIGNvZWZmaWNpZW50CgooSWYgdGltZSBhbGxvd3MhKQoKQSBzbGlnaHRseSBtb3JlIGNvbXBsZXggYWx0ZXJuYXRpdmUgdGhhbiBIV0UgaXMgdG8gYXNzdW1lIHRoYXQKdGhlcmUgaXMgYSB0ZW5kZW5jeSBmb3IgcGVvcGxlIHRvIG1hdGUgd2l0aCBvdGhlcnMgd2hvIGFyZQpzbGlnaHRseSBtb3JlIGNsb3NlbHktcmVsYXRlZCB0aGFuICJyYW5kb20iIChhcyBtaWdodApoYXBwZW4gaW4gYSBnZW9ncmFwaGljYWxseS1zdHJ1Y3R1cmVkIHBvcHVsYXRpb24sIGZvciBleGFtcGxlKS4KVGhpcyB3aWxsIHJlc3VsdCBpbiBhbiBleGNlc3Mgb2YgaG9tb3p5Z290ZXMgY29tcGFyZWQgd2l0aApIV0UuIEEgc2ltcGxlIHdheSB0byBjYXB0dXJlIHRoaXMgaXMgdG8gaW50cm9kdWNlIGFuIGV4dHJhIHBhcmFtZXRlciwKdGhlICJpbmJyZWVkaW5nIGNvZWZmaWNpZW50IiAkZiQsIGFuZCBhc3N1bWUgdGhhdCB0aGUgZ2Vub3R5cGVzCiRBQSQsICRBYSQgYW5kICRhYSQgaGF2ZSBmcmVxdWVuY2llcyAkZnAgKyAoMS1mKXBeMiQsICQoMS1mKSAycCgxLXApJCwKYW5kICRmKDEtcCkgKyAoMS1mKSgxLXApXjIkLgoKSW4gbW9zdCBjYXNlcyBpdCB3b3VsZCBiZSBuYXR1cmFsIHRvIHRyZWF0ICRmJCBhcyBhIGZlYXR1cmUgb2YKdGhlIHBvcHVsYXRpb24sIGFuZCB0aGVyZWZvcmUgYXNzdW1lIGYgaXMgY29uc3RhbnQgYWNyb3NzIGxvY2kuCkZvciBzaW1wbGljaXR5IHdlIHdpbGwgY29uc2lkZXIganVzdCBhIHNpbmdsZSBsb2N1cy4KTm90ZSB0aGF0IGJvdGggJGYkIGFuZCAkcCQgYXJlIGNvbnN0cmFpbmVkIHRvIGxpZSBiZXR3ZWVuIDAgYW5kIDEKKGluY2x1c2l2ZSkuIEEgc2ltcGxlIHByaW9yIGZvciBlYWNoIG9mIHRoZXNlIHR3byBwYXJhbWV0ZXJzIGlzIHRvIGFzc3VtZQp0aGF0IHRoZXkgYXJlIGluZGVwZW5kZW50LCB1bmlmb3JtIG9uIFswLDFdLiBTdXBwb3NlCnRoYXQgd2Ugc2FtcGxlICRuJCBpbmRpdmlkdWFscywgYW5kIG9ic2VydmUgJG5fe0FBfSQgd2l0aCBnZW5vdHlwZSAkQUEkLAokbl97QWF9JCB3aXRoIGdlbm90eXBlICRBYSQgYW5kICRuX3thYX0kIHdpdGggZ2Vub3R5cGUgJGFhJC4KCiMjIyBFeGVyY2lzZTogd3JpdGUgYSBzaG9ydCBNQ01DIHJvdXRpbmUgdG8gc2FtcGxlIGZyb20gdGhlIGpvaW50IGRpc3RyaWJ1dGlvbiBvZiAkZiQgYW5kICRwJC4KCkhlcmUgaXMgd2hhdCBpdCBsb29rcyBsaWtlLgpgYGB7cn0KcHJpb3IgPC0gZnVuY3Rpb24ocCkgewogIGlmICgocCA8IDApIHx8IChwID4gMSkpIHsgIyB8fCBoZXJlIG1lYW5zICJvciIKICAgIHJldHVybigwKQogIH0gZWxzZSB7IAogICAgcmV0dXJuKDEpCiAgfSAKfQoKCmxpa2VsaWhvb2QgPC0gZnVuY3Rpb24ocCwgZiwgbkFBLCBuQWEsIG5hYSkgewoJcmV0dXJuKCgoZiAqIHApICsgKCgxIC0gZikgKiAocCBeIDIpKSlebkFBICogCgkgICAgICAgICAoKDEgLSBmKSAqIDIgKiBwICogKDEgLSBwKSkgXiBuQWEgKiAKCSAgICAgICAgIChmICogKDEgLSBwKSArICgxIC0gZikgKiAoKDEgLSBwKSAqICgxIC0gcCkpKSBeIG5hYQoJICAgICAgICkKfQoKCmZwc2FtcGxlciA8LSBmdW5jdGlvbihuQUEsIG5BYSwgbmFhLCBuaXRlciwgCiAgICAgICAgICAgICAgICAgICAgICBmc3RhcnR2YWwsIHBzdGFydHZhbCwKICAgICAgICAgICAgICAgICAgICAgIGZwcm9wb3NhbHNkLCBwcHJvcG9zYWxzZCkgewoJZiA8LSByZXAoMCxuaXRlcikKCXAgPC0gcmVwKDAsbml0ZXIpCglmWzFdIDwtIGZzdGFydHZhbAoJcFsxXSA8LSBwc3RhcnR2YWwKCWZvciAoaSBpbiAyOm5pdGVyKSB7CgkJY3VycmVudHAgPC0gcFtpIC0gMV0KCQljdXJyZW50ZiA8LSBmW2kgLSAxXQoJCW5ld3AgPC0gY3VycmVudHAgKyBybm9ybSgxLCAwLCBwcHJvcG9zYWxzZCkKCQlBIDwtIHByaW9yKG5ld3ApICogbGlrZWxpaG9vZChuZXdwLGN1cnJlbnRmLG5BQSxuQWEsbmFhKSAvCgkJICAocHJpb3IoY3VycmVudHApICogbGlrZWxpaG9vZChjdXJyZW50cCxjdXJyZW50ZixuQUEsbkFhLG5hYSkpCgkJCgkJaWYgKHJ1bmlmKDEpIDwgQSkgewoJCSAgcFtpXSA8LSBuZXdwCgkJfSBlbHNlIHsKCQkgIHBbaV0gPC0gY3VycmVudHAKCQl9CgkJbmV3ZiA8LSBjdXJyZW50ZiArIHJub3JtKDEsIDAsIGZwcm9wb3NhbHNkKQoJCQoJCUEgPC0gcHJpb3IobmV3ZikgKiBsaWtlbGlob29kKHBbaV0sbmV3ZixuQUEsbkFhLG5hYSkgLyAKCQkgIChwcmlvcihjdXJyZW50ZikgKiBsaWtlbGlob29kKHBbaV0sY3VycmVudGYsbkFBLG5BYSxuYWEpKQoJCQoJCQoJCWlmIChydW5pZigxKSA8IEEpIHsKCQkgIGZbaV0gPC0gbmV3ZgoJCX0gZWxzZSB7CgkJICBmW2ldIDwtIGN1cnJlbnRmCgkJfQoJfQoJCglyZXR1cm4obGlzdChmID0gZixwID0gcCkpICMgcmV0dXJuIGEgImxpc3QiIHdpdGggdHdvIGVsZW1lbnRzIG5hbWVkIGYgYW5kIHAKfQpgYGAKClRoZW4gcnVuIGl0IGZvciBhIHNhbXBsZSB3aXRoICRuX3tBQX0gPSA0NSQsICRuX3tBYX0gPSAxMCQsIGFuZCAkbl97YWF9ID0gNDUkLCB3aGljaCBjbGVhcmx5IGlzIGEgCmNhc2Ugd2hlcmUgdGhlcmUgYXJlIGZhciBmZXdlciBoZXRlcm96eWdvdGVzIHRoYW4gb25lIHdvdWxkIGV4cGVjdCB1bmRlcgpIYXJkeS1XZWluYmVyZyBlcXVpbGlicml1bS4KYGBge3J9CnogPC0gZnBzYW1wbGVyKDQ1LCAxMCwgNDUsIDEwMDAwLCAwLjgsIDAuNSwgMC4wMSwgMC4wMSkKYGBgCkxldCdzIHBsb3QgdGhvc2UgcmVzdWx0czoKYGBge3J9CnggPC0gc2VxKDAsIDEsIGxlbmd0aCA9IDEwMDApCnBhcihtZnJvdyA9IGMoMSwyKSkKaGlzdCh6JGZbNTAwMDoxMDAwMF0scHJvYiA9IFQsIHhsaW0gPSBjKDAsIDEpLCBjb2wgPSAiZGFyayBncmV5IiwgeWxpbSA9IGMoMCwgMTApLCAKICAgICBtYWluID0gImYgc2FtcGxlIiwgeGxhYiA9ICJwb3N0ZXJpb3IgZXN0aW1hdGUiKQpoaXN0KHokcFs1MDAwOjEwMDAwXSwgcHJvYiA9IFQsIHhsaW0gPSBjKDAsIDEpLCBjb2wgPSAiZGFyayBncmV5IiwgeWxpbSA9IGMoMCwgMTApLCAKICAgICBtYWluID0gInAgc2FtcGxlIiwgeGxhYiA9ICJwb3N0ZXJpb3IgZXN0aW1hdGUiKQpgYGAKQW5kIGxvb2sgYXQgc29tZSB0cmFjZSBwbG90czoKYGBge3J9CnBhcihtZnJvdyA9IGMoMSwgMikpCnBsb3QoeiRmLCB0eXBlID0gImwiKQpwbG90KHokcCwgdHlwZSA9ICJsIikKYGBgCgpJZiB3ZSB3YW50IHRvIHN1bW1hcml6ZSB0aG9zZSBzYW1wbGVzIHRvIGEgc2luZ2xlIHBvaW50IGZvciAkcCQgYW5kIGZvciAkZiQKYSBnb29kIGNob2ljZSBpcyB0aGUgcG9zdGVyaW9yIG1lYW4sIHdoaWNoIGlzIGp1c3QgdGhlIG1lYW4gZnJvbSB0aGUgc2FtcGxlCmZyb20gdGhlIE1hcmtvdiBjaGFpbi4KYGBge3J9CiMgbWVhbiBmb3IgcApwX21lYW4gPC0gbWVhbih6JHApCgojIG1lYW4gZm9yIGYKZl9tZWFuIDwtIG1lYW4oeiRmKQpgYGAKCkFuZCBpdCBpcyBhbHdheXMgYSBnb29kIGlkZWEgdG8gc2ltdWxhdGUgbmV3IGRhdGEgZnJvbSB0aGUgYW4gZXN0aW1hdGVkCm1vZGVsLCBvciBsb29rIGF0IHRoZSBleHBlY3RlZCB2YWx1ZSBvZiBkYXRhIGZyb20gYW4gZXN0aW1hdGVkIG1vZGVsLAp0byBzZWUgaWYgaXQgbG9va3MgYW55dGhpbmcgbGlrZSB0aGUgZGF0YSB0aGF0IHdlbnQgaW50byBpdC4gCgpXZSBjYW4gZG8gdGhhdCBieSBmaW5kaW5nIHRoZSBleHBlY3RlZCBudW1iZXIgb2YgdGhlIHRocmVlIGdlbm90eXBlcwpnaXZlbiB0aGUgcG9zdGVyaW9yIG1lYW4gZXN0aW1hdGVzIG9mICRmJCBhbmQgJHAkOgpgYGB7cn0KTiA8LSAxMDAKYyhuQUEgPSAoKHBfbWVhbiBeIDIpICsgKGZfbWVhbiAqICgxIC0gcF9tZWFuKSAqIHBfbWVhbikpICogTiwKICBuQWEgPSAoKDEgLSBmX21lYW4pICogMiAqIHBfbWVhbiAqICgxIC0gcF9tZWFuKSkgKiBOLAogIG5hYSA9ICgoZl9tZWFuICogKDEgLSBwX21lYW4pICogcF9tZWFuKSArICgoMSAtIHBfbWVhbileMikpICogTikKCmBgYAoKWWVwLi4udGhhdCBsb29rcyBsaWtlIG91ciBvYnNlcnZlZCBkYXRhLi4uCgojIyBTZXNzaW9uIEluZm8KYGBge3J9CnNlc3Npb25JbmZvKCkKYGBgCgo=