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==