Importance sampling with Normal distribution as a proposal for Bioassay model

ggplot2, grid, and gridExtra are used for plotting, tidyr for manipulating data frames

library(ggplot2)
theme_set(theme_minimal())
library(gridExtra)
library(grid)
library(tidyr)
library(MASS)
library(loo)

Bioassay data, (BDA3 page 86)

df1 <- data.frame(
  x = c(-0.86, -0.30, -0.05, 0.73),
  n = c(5, 5, 5, 5),
  y = c(0, 1, 3, 5)
)

Grid sampling for Bioassay model.

Compute the posterior density in a grid

  • usually should be computed in logarithms!
  • with alternative prior, check that range and spacing of A and B are sensible
A = seq(-1.5, 7, length.out = 100)
B = seq(-5, 35, length.out = 100)
# make vectors that contain all pairwise combinations of A and B
cA <- rep(A, each = length(B))
cB <- rep(B, length(A))

Make a helper function to calculate the log likelihood given a dataframe with x, y, and n and evaluation points a and b. For the likelihood see BDA3 p. 75

logl <- function(df, a, b)
  df['y']*(a + b*df['x']) - df['n']*log1p(exp(a + b*df['x']))
# calculate likelihoods: apply logl function for each observation
# ie. each row of data frame of x, n and y
p <- apply(df1, 1, logl, cA, cB) %>%
  # sum the log likelihoods of observations
  # and exponentiate to get the joint likelihood
  rowSums() %>% exp()

Sample from the grid (with replacement)

nsamp <- 1000
samp_indices <- sample(length(p), size = nsamp,
                       replace = T, prob = p/sum(p))
samp_A <- cA[samp_indices[1:nsamp]]
samp_B <- cB[samp_indices[1:nsamp]]
# add random jitter, see BDA3 p. 76
samp_A <- samp_A + runif(nsamp, (A[1] - A[2])/2, (A[2] - A[1])/2)
samp_B <- samp_B + runif(nsamp, (B[1] - B[2])/2, (B[2] - B[1])/2)

Compute LD50 for all draws

samp_ld50 <- -samp_A/samp_B

Create a plot of the posterior density

# limits for the plots
xl <- c(-2, 7)
yl <- c(-2, 35)
pos <- ggplot(data = data.frame(cA ,cB, p), aes(x = cA, y = cB)) +
  geom_raster(aes(fill = p, alpha = p), interpolate = T) +
  geom_contour(aes(z = p), colour = 'black', size = 0.2) +
  coord_cartesian(xlim = xl, ylim = yl) +
  labs(x = 'alpha', y = 'beta') +
  scale_fill_gradient(low = 'yellow', high = 'red', guide = F) +
  scale_alpha(range = c(0, 1), guide = F)
pos
## Warning: It is deprecated to specify `guide = FALSE` to remove a guide. Please use `guide = "none"` instead.
## It is deprecated to specify `guide = FALSE` to remove a guide. Please use `guide = "none"` instead.

Plot of the samples

sam <- ggplot(data = data.frame(samp_A, samp_B)) +
  geom_point(aes(samp_A, samp_B), color = 'blue', size = 0.3) +
  coord_cartesian(xlim = xl, ylim = yl) +
  labs(x = 'alpha', y = 'beta')
sam

Plot of the histogram of LD50

his <- ggplot() +
  geom_histogram(aes(samp_ld50), binwidth = 0.05,
                 fill = 'steelblue', color = 'black') +
  coord_cartesian(xlim = c(-0.8, 0.8)) +
  labs(x = 'LD50 = -alpha/beta')
his

Normal approximation for Bioassay model.

Define the function to be optimized

bioassayfun <- function(w, df) {
  z <- w[1] + w[2]*df$x
  -sum(df$y*(z) - df$n*log1p(exp(z)))
}

Optimize

w0 <- c(0,0)
optim_res <- optim(w0, bioassayfun, gr = NULL, df1, hessian = T)
w <- optim_res$par
S <- solve(optim_res$hessian)

Multivariate normal probability density function

dmvnorm <- function(x, mu, sig)
  exp(-0.5*(length(x)*log(2*pi) + log(det(sig)) + (x-mu)%*%solve(sig, x-mu)))

Evaluate likelihood at points (cA,cB) this is just for illustration and would not be needed otherwise

p <- apply(cbind(cA, cB), 1, dmvnorm, w, S)

Sample from the multivariate normal

samp_norm <- mvrnorm(nsamp, w, S)

Samples of LD50 conditional beta > 0: Normal approximation does not take into account that the posterior is not symmetric and that there is very low density for negative beta values. Based on the draws from the normal approximation is is estimated that there is about 5% probability that beta is negative!

bpi <- samp_norm[,2] > 0
samp_norm_ld50 <- -samp_norm[bpi,1]/samp_norm[bpi,2]

Create a plot of the normal distribution approximation

pos_norm <- ggplot(data = data.frame(cA ,cB, p), aes(x = cA, y = cB)) +
  geom_raster(aes(fill = p, alpha = p), interpolate = T) +
  geom_contour(aes(z = p), colour = 'black', size = 0.2) +
  coord_cartesian(xlim = xl, ylim = yl) +
  labs(x = 'alpha', y = 'beta') +
  scale_fill_gradient(low = 'yellow', high = 'red', guide = F) +
  scale_alpha(range = c(0, 1), guide = F)
pos_norm
## Warning: It is deprecated to specify `guide = FALSE` to remove a guide. Please use `guide = "none"` instead.
## It is deprecated to specify `guide = FALSE` to remove a guide. Please use `guide = "none"` instead.

Plot of the samples

sam_norm <- ggplot(data = data.frame(samp_A=samp_norm[,1], samp_B=samp_norm[,2])) +
  geom_point(aes(samp_A, samp_B), color = 'blue', size = 0.3) +
  coord_cartesian(xlim = xl, ylim = yl) +
  labs(x = 'alpha', y = 'beta')
sam_norm

Plot of the histogram of LD50

his_norm <- ggplot() +
  geom_histogram(aes(samp_norm_ld50), binwidth = 0.05,
                 fill = 'steelblue', color = 'black') +
  coord_cartesian(xlim = c(-0.8, 0.8)) +
  labs(x = 'LD50 = -alpha/beta, beta > 0')
his_norm

Importance sampling for Bioassay model.

Multivariate normal log probability density function

ldmvnorm <- function(x, mu, sig)
(-0.5*(length(x)*log(2*pi) + log(det(sig)) + (x-mu)%*%solve(sig, x-mu)))

Log importance ratios (working in log scale is numerically more stable)

lg <- apply(samp_norm, 1, ldmvnorm, w, S)
lp <- apply(df1, 1, logl, samp_norm[,1], samp_norm[,2]) %>% rowSums()
lw <- lp-lg

Pareto smoothed importance sampling (Vehtari et al, 2017)

psislw <- psis(lw, r_eff = 1)
## Warning: Some Pareto k diagnostic values are too high. See help('pareto-k-diagnostic') for details.

Pareto diagnostics. k<0.7 is ok. (Vehtari et al, 2017)

print(psislw$diagnostics$pareto_k, digits=2)
## [1] 0.85

Effective sample size estimate (Vehtari et al, 2017)

print(psislw$diagnostics$n_eff, digits=2)
## [1] 257

Pareto smoothed weights

psisw <- exp(psislw$log_weights)

Importance sampling weights could be used to weight different expectations directly, but for visualisation and easy computation of LD50 histogram, we use resampling importance sampling.

samp_indices <- sample(length(psisw), size = nsamp,
                       replace = T, prob = psisw)
rissamp_A <- samp_norm[samp_indices,1]
rissamp_B <- samp_norm[samp_indices,2]
# add random jitter, see BDA3 p. 76
rissamp_A <- rissamp_A + runif(nsamp, (A[1] - A[2])/2, (A[2] - A[1])/2)
rissamp_B <- rissamp_B + runif(nsamp, (B[1] - B[2])/2, (B[2] - B[1])/2)
# samples of LD50 
rissamp_ld50 <- -rissamp_A/rissamp_B

Plot of the samples

sam_ris <- ggplot(data = data.frame(rissamp_A, rissamp_B)) +
  geom_point(aes(rissamp_A, rissamp_B), color = 'blue', size = 0.3) +
  coord_cartesian(xlim = xl, ylim = yl) +
  labs(x = 'alpha', y = 'beta')
sam_ris

Plot of the histogram of LD50

his_ris <- ggplot() +
  geom_histogram(aes(rissamp_ld50), binwidth = 0.05,
                 fill = 'steelblue', color = 'black') +
  coord_cartesian(xlim = c(-0.8, 0.8)) +
  labs(x = 'LD50 = -alpha/beta')
his_ris

Combine the plots. Top: grid sampling, middle: normal approximation, bottom: importance sampling.

blank <- grid.rect(gp=gpar(col="white"))
grid.arrange(pos, sam, his, pos_norm, sam_norm, his_norm, blank, sam_ris, his_ris, ncol=3)
## Warning: It is deprecated to specify `guide = FALSE` to remove a guide. Please use `guide = "none"` instead.
## It is deprecated to specify `guide = FALSE` to remove a guide. Please use `guide = "none"` instead.
## It is deprecated to specify `guide = FALSE` to remove a guide. Please use `guide = "none"` instead.
## It is deprecated to specify `guide = FALSE` to remove a guide. Please use `guide = "none"` instead.

LS0tCnRpdGxlOiAiQmF5ZXNpYW4gZGF0YSBhbmFseXNpcyBkZW1vIDEwLjMiCmF1dGhvcjogIkFraSBWZWh0YXJpLCBNYXJrdXMgUGFhc2luaWVtaSIKZGF0ZTogImByIGZvcm1hdChTeXMuRGF0ZSgpKWAiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgdGhlbWU6IHJlYWRhYmxlCiAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCi0tLQojIyBJbXBvcnRhbmNlIHNhbXBsaW5nIHdpdGggTm9ybWFsIGRpc3RyaWJ1dGlvbiBhcyBhIHByb3Bvc2FsIGZvciBCaW9hc3NheSBtb2RlbAoKZ2dwbG90MiwgZ3JpZCwgYW5kIGdyaWRFeHRyYSBhcmUgdXNlZCBmb3IgcGxvdHRpbmcsIHRpZHlyIGZvcgptYW5pcHVsYXRpbmcgZGF0YSBmcmFtZXMKCmBgYHtyIHNldHVwLCBtZXNzYWdlPUZBTFNFLCBlcnJvcj1GQUxTRSwgd2FybmluZz1GQUxTRX0KbGlicmFyeShnZ3Bsb3QyKQp0aGVtZV9zZXQodGhlbWVfbWluaW1hbCgpKQpsaWJyYXJ5KGdyaWRFeHRyYSkKbGlicmFyeShncmlkKQpsaWJyYXJ5KHRpZHlyKQpsaWJyYXJ5KE1BU1MpCmxpYnJhcnkobG9vKQpgYGAKCkJpb2Fzc2F5IGRhdGEsIChCREEzIHBhZ2UgODYpCgpgYGB7ciB9CmRmMSA8LSBkYXRhLmZyYW1lKAogIHggPSBjKC0wLjg2LCAtMC4zMCwgLTAuMDUsIDAuNzMpLAogIG4gPSBjKDUsIDUsIDUsIDUpLAogIHkgPSBjKDAsIDEsIDMsIDUpCikKYGBgCgojIyMgR3JpZCBzYW1wbGluZyBmb3IgQmlvYXNzYXkgbW9kZWwuCkNvbXB1dGUgdGhlIHBvc3RlcmlvciBkZW5zaXR5IGluIGEgZ3JpZAoKLSB1c3VhbGx5IHNob3VsZCBiZSBjb21wdXRlZCBpbiBsb2dhcml0aG1zIQotIHdpdGggYWx0ZXJuYXRpdmUgcHJpb3IsIGNoZWNrIHRoYXQgcmFuZ2UgYW5kIHNwYWNpbmcgb2YgQSBhbmQgQgogIGFyZSBzZW5zaWJsZQoKYGBge3IgfQpBID0gc2VxKC0xLjUsIDcsIGxlbmd0aC5vdXQgPSAxMDApCkIgPSBzZXEoLTUsIDM1LCBsZW5ndGgub3V0ID0gMTAwKQojIG1ha2UgdmVjdG9ycyB0aGF0IGNvbnRhaW4gYWxsIHBhaXJ3aXNlIGNvbWJpbmF0aW9ucyBvZiBBIGFuZCBCCmNBIDwtIHJlcChBLCBlYWNoID0gbGVuZ3RoKEIpKQpjQiA8LSByZXAoQiwgbGVuZ3RoKEEpKQpgYGAKCk1ha2UgYSBoZWxwZXIgZnVuY3Rpb24gdG8gY2FsY3VsYXRlIHRoZSBsb2cgbGlrZWxpaG9vZApnaXZlbiBhIGRhdGFmcmFtZSB3aXRoIHgsIHksIGFuZCBuIGFuZCBldmFsdWF0aW9uCnBvaW50cyBhIGFuZCBiLiBGb3IgdGhlIGxpa2VsaWhvb2Qgc2VlIEJEQTMgcC4gNzUKCmBgYHtyIH0KbG9nbCA8LSBmdW5jdGlvbihkZiwgYSwgYikKICBkZlsneSddKihhICsgYipkZlsneCddKSAtIGRmWyduJ10qbG9nMXAoZXhwKGEgKyBiKmRmWyd4J10pKQojIGNhbGN1bGF0ZSBsaWtlbGlob29kczogYXBwbHkgbG9nbCBmdW5jdGlvbiBmb3IgZWFjaCBvYnNlcnZhdGlvbgojIGllLiBlYWNoIHJvdyBvZiBkYXRhIGZyYW1lIG9mIHgsIG4gYW5kIHkKcCA8LSBhcHBseShkZjEsIDEsIGxvZ2wsIGNBLCBjQikgJT4lCiAgIyBzdW0gdGhlIGxvZyBsaWtlbGlob29kcyBvZiBvYnNlcnZhdGlvbnMKICAjIGFuZCBleHBvbmVudGlhdGUgdG8gZ2V0IHRoZSBqb2ludCBsaWtlbGlob29kCiAgcm93U3VtcygpICU+JSBleHAoKQpgYGAKClNhbXBsZSBmcm9tIHRoZSBncmlkICh3aXRoIHJlcGxhY2VtZW50KQoKYGBge3IgfQpuc2FtcCA8LSAxMDAwCnNhbXBfaW5kaWNlcyA8LSBzYW1wbGUobGVuZ3RoKHApLCBzaXplID0gbnNhbXAsCiAgICAgICAgICAgICAgICAgICAgICAgcmVwbGFjZSA9IFQsIHByb2IgPSBwL3N1bShwKSkKc2FtcF9BIDwtIGNBW3NhbXBfaW5kaWNlc1sxOm5zYW1wXV0Kc2FtcF9CIDwtIGNCW3NhbXBfaW5kaWNlc1sxOm5zYW1wXV0KIyBhZGQgcmFuZG9tIGppdHRlciwgc2VlIEJEQTMgcC4gNzYKc2FtcF9BIDwtIHNhbXBfQSArIHJ1bmlmKG5zYW1wLCAoQVsxXSAtIEFbMl0pLzIsIChBWzJdIC0gQVsxXSkvMikKc2FtcF9CIDwtIHNhbXBfQiArIHJ1bmlmKG5zYW1wLCAoQlsxXSAtIEJbMl0pLzIsIChCWzJdIC0gQlsxXSkvMikKYGBgCgpDb21wdXRlIExENTAgZm9yIGFsbCBkcmF3cwoKYGBge3IgfQpzYW1wX2xkNTAgPC0gLXNhbXBfQS9zYW1wX0IKYGBgCgpDcmVhdGUgYSBwbG90IG9mIHRoZSBwb3N0ZXJpb3IgZGVuc2l0eQoKYGBge3IgfQojIGxpbWl0cyBmb3IgdGhlIHBsb3RzCnhsIDwtIGMoLTIsIDcpCnlsIDwtIGMoLTIsIDM1KQpwb3MgPC0gZ2dwbG90KGRhdGEgPSBkYXRhLmZyYW1lKGNBICxjQiwgcCksIGFlcyh4ID0gY0EsIHkgPSBjQikpICsKICBnZW9tX3Jhc3RlcihhZXMoZmlsbCA9IHAsIGFscGhhID0gcCksIGludGVycG9sYXRlID0gVCkgKwogIGdlb21fY29udG91cihhZXMoeiA9IHApLCBjb2xvdXIgPSAnYmxhY2snLCBzaXplID0gMC4yKSArCiAgY29vcmRfY2FydGVzaWFuKHhsaW0gPSB4bCwgeWxpbSA9IHlsKSArCiAgbGFicyh4ID0gJ2FscGhhJywgeSA9ICdiZXRhJykgKwogIHNjYWxlX2ZpbGxfZ3JhZGllbnQobG93ID0gJ3llbGxvdycsIGhpZ2ggPSAncmVkJywgZ3VpZGUgPSBGKSArCiAgc2NhbGVfYWxwaGEocmFuZ2UgPSBjKDAsIDEpLCBndWlkZSA9IEYpCnBvcwpgYGAKClBsb3Qgb2YgdGhlIHNhbXBsZXMKCmBgYHtyIH0Kc2FtIDwtIGdncGxvdChkYXRhID0gZGF0YS5mcmFtZShzYW1wX0EsIHNhbXBfQikpICsKICBnZW9tX3BvaW50KGFlcyhzYW1wX0EsIHNhbXBfQiksIGNvbG9yID0gJ2JsdWUnLCBzaXplID0gMC4zKSArCiAgY29vcmRfY2FydGVzaWFuKHhsaW0gPSB4bCwgeWxpbSA9IHlsKSArCiAgbGFicyh4ID0gJ2FscGhhJywgeSA9ICdiZXRhJykKc2FtCmBgYAoKUGxvdCBvZiB0aGUgaGlzdG9ncmFtIG9mIExENTAKCmBgYHtyIH0KaGlzIDwtIGdncGxvdCgpICsKICBnZW9tX2hpc3RvZ3JhbShhZXMoc2FtcF9sZDUwKSwgYmlud2lkdGggPSAwLjA1LAogICAgICAgICAgICAgICAgIGZpbGwgPSAnc3RlZWxibHVlJywgY29sb3IgPSAnYmxhY2snKSArCiAgY29vcmRfY2FydGVzaWFuKHhsaW0gPSBjKC0wLjgsIDAuOCkpICsKICBsYWJzKHggPSAnTEQ1MCA9IC1hbHBoYS9iZXRhJykKaGlzCmBgYAoKIyMjIE5vcm1hbCBhcHByb3hpbWF0aW9uIGZvciBCaW9hc3NheSBtb2RlbC4KRGVmaW5lIHRoZSBmdW5jdGlvbiB0byBiZSBvcHRpbWl6ZWQKCmBgYHtyIH0KYmlvYXNzYXlmdW4gPC0gZnVuY3Rpb24odywgZGYpIHsKICB6IDwtIHdbMV0gKyB3WzJdKmRmJHgKICAtc3VtKGRmJHkqKHopIC0gZGYkbipsb2cxcChleHAoeikpKQp9CmBgYAoKT3B0aW1pemUKCmBgYHtyIH0KdzAgPC0gYygwLDApCm9wdGltX3JlcyA8LSBvcHRpbSh3MCwgYmlvYXNzYXlmdW4sIGdyID0gTlVMTCwgZGYxLCBoZXNzaWFuID0gVCkKdyA8LSBvcHRpbV9yZXMkcGFyClMgPC0gc29sdmUob3B0aW1fcmVzJGhlc3NpYW4pCmBgYAoKTXVsdGl2YXJpYXRlIG5vcm1hbCBwcm9iYWJpbGl0eSBkZW5zaXR5IGZ1bmN0aW9uCgpgYGB7ciB9CmRtdm5vcm0gPC0gZnVuY3Rpb24oeCwgbXUsIHNpZykKICBleHAoLTAuNSoobGVuZ3RoKHgpKmxvZygyKnBpKSArIGxvZyhkZXQoc2lnKSkgKyAoeC1tdSklKiVzb2x2ZShzaWcsIHgtbXUpKSkKYGBgCgpFdmFsdWF0ZSBsaWtlbGlob29kIGF0IHBvaW50cyAoY0EsY0IpIAp0aGlzIGlzIGp1c3QgZm9yIGlsbHVzdHJhdGlvbiBhbmQgd291bGQgbm90IGJlIG5lZWRlZCBvdGhlcndpc2UKCmBgYHtyIH0KcCA8LSBhcHBseShjYmluZChjQSwgY0IpLCAxLCBkbXZub3JtLCB3LCBTKQpgYGAKClNhbXBsZSBmcm9tIHRoZSBtdWx0aXZhcmlhdGUgbm9ybWFsIAoKYGBge3IgfQpzYW1wX25vcm0gPC0gbXZybm9ybShuc2FtcCwgdywgUykKYGBgCgpTYW1wbGVzIG9mIExENTAgY29uZGl0aW9uYWwgYmV0YSA+IDA6Ck5vcm1hbCBhcHByb3hpbWF0aW9uIGRvZXMgbm90IHRha2UgaW50byBhY2NvdW50IHRoYXQgdGhlIHBvc3RlcmlvcgppcyBub3Qgc3ltbWV0cmljIGFuZCB0aGF0IHRoZXJlIGlzIHZlcnkgbG93IGRlbnNpdHkgZm9yIG5lZ2F0aXZlCmJldGEgdmFsdWVzLiBCYXNlZCBvbiB0aGUgZHJhd3MgZnJvbSB0aGUgbm9ybWFsIGFwcHJveGltYXRpb24KaXMgaXMgZXN0aW1hdGVkIHRoYXQgdGhlcmUgaXMgYWJvdXQgNSUgcHJvYmFiaWxpdHkgdGhhdCBiZXRhIGlzIG5lZ2F0aXZlIQoKYGBge3IgfQpicGkgPC0gc2FtcF9ub3JtWywyXSA+IDAKc2FtcF9ub3JtX2xkNTAgPC0gLXNhbXBfbm9ybVticGksMV0vc2FtcF9ub3JtW2JwaSwyXQpgYGAKCkNyZWF0ZSBhIHBsb3Qgb2YgdGhlIG5vcm1hbCBkaXN0cmlidXRpb24gYXBwcm94aW1hdGlvbgoKYGBge3IgfQpwb3Nfbm9ybSA8LSBnZ3Bsb3QoZGF0YSA9IGRhdGEuZnJhbWUoY0EgLGNCLCBwKSwgYWVzKHggPSBjQSwgeSA9IGNCKSkgKwogIGdlb21fcmFzdGVyKGFlcyhmaWxsID0gcCwgYWxwaGEgPSBwKSwgaW50ZXJwb2xhdGUgPSBUKSArCiAgZ2VvbV9jb250b3VyKGFlcyh6ID0gcCksIGNvbG91ciA9ICdibGFjaycsIHNpemUgPSAwLjIpICsKICBjb29yZF9jYXJ0ZXNpYW4oeGxpbSA9IHhsLCB5bGltID0geWwpICsKICBsYWJzKHggPSAnYWxwaGEnLCB5ID0gJ2JldGEnKSArCiAgc2NhbGVfZmlsbF9ncmFkaWVudChsb3cgPSAneWVsbG93JywgaGlnaCA9ICdyZWQnLCBndWlkZSA9IEYpICsKICBzY2FsZV9hbHBoYShyYW5nZSA9IGMoMCwgMSksIGd1aWRlID0gRikKcG9zX25vcm0KYGBgCgpQbG90IG9mIHRoZSBzYW1wbGVzCgpgYGB7ciB9CnNhbV9ub3JtIDwtIGdncGxvdChkYXRhID0gZGF0YS5mcmFtZShzYW1wX0E9c2FtcF9ub3JtWywxXSwgc2FtcF9CPXNhbXBfbm9ybVssMl0pKSArCiAgZ2VvbV9wb2ludChhZXMoc2FtcF9BLCBzYW1wX0IpLCBjb2xvciA9ICdibHVlJywgc2l6ZSA9IDAuMykgKwogIGNvb3JkX2NhcnRlc2lhbih4bGltID0geGwsIHlsaW0gPSB5bCkgKwogIGxhYnMoeCA9ICdhbHBoYScsIHkgPSAnYmV0YScpCnNhbV9ub3JtCmBgYAoKUGxvdCBvZiB0aGUgaGlzdG9ncmFtIG9mIExENTAKCmBgYHtyIH0KaGlzX25vcm0gPC0gZ2dwbG90KCkgKwogIGdlb21faGlzdG9ncmFtKGFlcyhzYW1wX25vcm1fbGQ1MCksIGJpbndpZHRoID0gMC4wNSwKICAgICAgICAgICAgICAgICBmaWxsID0gJ3N0ZWVsYmx1ZScsIGNvbG9yID0gJ2JsYWNrJykgKwogIGNvb3JkX2NhcnRlc2lhbih4bGltID0gYygtMC44LCAwLjgpKSArCiAgbGFicyh4ID0gJ0xENTAgPSAtYWxwaGEvYmV0YSwgYmV0YSA+IDAnKQpoaXNfbm9ybQpgYGAKCiMjIyBJbXBvcnRhbmNlIHNhbXBsaW5nIGZvciBCaW9hc3NheSBtb2RlbC4KTXVsdGl2YXJpYXRlIG5vcm1hbCBsb2cgcHJvYmFiaWxpdHkgZGVuc2l0eSBmdW5jdGlvbgoKYGBge3IgfQpsZG12bm9ybSA8LSBmdW5jdGlvbih4LCBtdSwgc2lnKQooLTAuNSoobGVuZ3RoKHgpKmxvZygyKnBpKSArIGxvZyhkZXQoc2lnKSkgKyAoeC1tdSklKiVzb2x2ZShzaWcsIHgtbXUpKSkKYGBgCgpMb2cgaW1wb3J0YW5jZSByYXRpb3MgKHdvcmtpbmcgaW4gbG9nIHNjYWxlIGlzIG51bWVyaWNhbGx5IG1vcmUgc3RhYmxlKQoKYGBge3IgfQpsZyA8LSBhcHBseShzYW1wX25vcm0sIDEsIGxkbXZub3JtLCB3LCBTKQpscCA8LSBhcHBseShkZjEsIDEsIGxvZ2wsIHNhbXBfbm9ybVssMV0sIHNhbXBfbm9ybVssMl0pICU+JSByb3dTdW1zKCkKbHcgPC0gbHAtbGcKYGBgCgpQYXJldG8gc21vb3RoZWQgaW1wb3J0YW5jZSBzYW1wbGluZwpbKFZlaHRhcmkgZXQgYWwsIDIwMTcpXShodHRwczovL2FyeGl2Lm9yZy9hYnMvMTUwNy4wMjY0NikKCmBgYHtyIH0KcHNpc2x3IDwtIHBzaXMobHcsIHJfZWZmID0gMSkKYGBgCgpQYXJldG8gZGlhZ25vc3RpY3MuIGs8MC43IGlzIG9rLgpbKFZlaHRhcmkgZXQgYWwsIDIwMTcpXShodHRwczovL2FyeGl2Lm9yZy9hYnMvMTUwNy4wMjY0NikKCmBgYHtyIH0KcHJpbnQocHNpc2x3JGRpYWdub3N0aWNzJHBhcmV0b19rLCBkaWdpdHM9MikKYGBgCgpFZmZlY3RpdmUgc2FtcGxlIHNpemUgZXN0aW1hdGUKWyhWZWh0YXJpIGV0IGFsLCAyMDE3KV0oaHR0cHM6Ly9hcnhpdi5vcmcvYWJzLzE1MDcuMDI2NDYpCgpgYGB7ciB9CnByaW50KHBzaXNsdyRkaWFnbm9zdGljcyRuX2VmZiwgZGlnaXRzPTIpCmBgYAoKUGFyZXRvIHNtb290aGVkIHdlaWdodHMKCmBgYHtyIH0KcHNpc3cgPC0gZXhwKHBzaXNsdyRsb2dfd2VpZ2h0cykKYGBgCgpJbXBvcnRhbmNlIHNhbXBsaW5nIHdlaWdodHMgY291bGQgYmUgdXNlZCB0byB3ZWlnaHQgZGlmZmVyZW50CmV4cGVjdGF0aW9ucyBkaXJlY3RseSwgYnV0IGZvciB2aXN1YWxpc2F0aW9uIGFuZCBlYXN5IGNvbXB1dGF0aW9uCm9mIExENTAgaGlzdG9ncmFtLCB3ZSB1c2UgcmVzYW1wbGluZyBpbXBvcnRhbmNlIHNhbXBsaW5nLgoKYGBge3IgfQpzYW1wX2luZGljZXMgPC0gc2FtcGxlKGxlbmd0aChwc2lzdyksIHNpemUgPSBuc2FtcCwKICAgICAgICAgICAgICAgICAgICAgICByZXBsYWNlID0gVCwgcHJvYiA9IHBzaXN3KQpyaXNzYW1wX0EgPC0gc2FtcF9ub3JtW3NhbXBfaW5kaWNlcywxXQpyaXNzYW1wX0IgPC0gc2FtcF9ub3JtW3NhbXBfaW5kaWNlcywyXQojIGFkZCByYW5kb20gaml0dGVyLCBzZWUgQkRBMyBwLiA3NgpyaXNzYW1wX0EgPC0gcmlzc2FtcF9BICsgcnVuaWYobnNhbXAsIChBWzFdIC0gQVsyXSkvMiwgKEFbMl0gLSBBWzFdKS8yKQpyaXNzYW1wX0IgPC0gcmlzc2FtcF9CICsgcnVuaWYobnNhbXAsIChCWzFdIC0gQlsyXSkvMiwgKEJbMl0gLSBCWzFdKS8yKQojIHNhbXBsZXMgb2YgTEQ1MCAKcmlzc2FtcF9sZDUwIDwtIC1yaXNzYW1wX0Evcmlzc2FtcF9CCmBgYAoKUGxvdCBvZiB0aGUgc2FtcGxlcwoKYGBge3IgfQpzYW1fcmlzIDwtIGdncGxvdChkYXRhID0gZGF0YS5mcmFtZShyaXNzYW1wX0EsIHJpc3NhbXBfQikpICsKICBnZW9tX3BvaW50KGFlcyhyaXNzYW1wX0EsIHJpc3NhbXBfQiksIGNvbG9yID0gJ2JsdWUnLCBzaXplID0gMC4zKSArCiAgY29vcmRfY2FydGVzaWFuKHhsaW0gPSB4bCwgeWxpbSA9IHlsKSArCiAgbGFicyh4ID0gJ2FscGhhJywgeSA9ICdiZXRhJykKc2FtX3JpcwpgYGAKClBsb3Qgb2YgdGhlIGhpc3RvZ3JhbSBvZiBMRDUwCgpgYGB7ciB9Cmhpc19yaXMgPC0gZ2dwbG90KCkgKwogIGdlb21faGlzdG9ncmFtKGFlcyhyaXNzYW1wX2xkNTApLCBiaW53aWR0aCA9IDAuMDUsCiAgICAgICAgICAgICAgICAgZmlsbCA9ICdzdGVlbGJsdWUnLCBjb2xvciA9ICdibGFjaycpICsKICBjb29yZF9jYXJ0ZXNpYW4oeGxpbSA9IGMoLTAuOCwgMC44KSkgKwogIGxhYnMoeCA9ICdMRDUwID0gLWFscGhhL2JldGEnKQpoaXNfcmlzCmBgYAoKQ29tYmluZSB0aGUgcGxvdHMuIFRvcDogZ3JpZCBzYW1wbGluZywgbWlkZGxlOiBub3JtYWwKYXBwcm94aW1hdGlvbiwgYm90dG9tOiBpbXBvcnRhbmNlIHNhbXBsaW5nLgoKYGBge3IgYmxhbmssIGZpZy5zaG93PSdoaWRlJ30KYmxhbmsgPC0gZ3JpZC5yZWN0KGdwPWdwYXIoY29sPSJ3aGl0ZSIpKQpgYGAKYGBge3IgY29tYmluZWR9CmdyaWQuYXJyYW5nZShwb3MsIHNhbSwgaGlzLCBwb3Nfbm9ybSwgc2FtX25vcm0sIGhpc19ub3JtLCBibGFuaywgc2FtX3JpcywgaGlzX3JpcywgbmNvbD0zKQpgYGAKCg==