1. loading the dataset & create the dataframe
setwd("~/Desktop/MSc Project/rstan/pigs")
library(rstan)
Loading required package: StanHeaders
Loading required package: ggplot2
rstan (Version 2.21.2, GitRev: 2e1f913d3ca3)
For execution on a local, multicore CPU with excess RAM we recommend calling
options(mc.cores = parallel::detectCores()).
To avoid recompilation of unchanged Stan programs, we recommend calling
rstan_options(auto_write = TRUE)
library(gsubfn)
Loading required package: proto
library(pracma)
library(scales)
pigs <- read.csv("~/Desktop/MSc Project/rstan/pigs/pigs.csv")
df = data.frame(pigs)
summary(df)
survivors..y. number..n. dose..x.
Min. : 0.000 Min. :10.00 Min. :0.730
1st Qu.: 1.000 1st Qu.:19.00 1st Qu.:1.185
Median : 4.000 Median :20.00 Median :1.300
Mean : 6.183 Mean :24.49 Mean :1.276
3rd Qu.: 7.500 3rd Qu.:22.50 3rd Qu.:1.380
Max. :45.000 Max. :52.00 Max. :1.890
print(df)
2. Creating the Data List
E
: number of experiments
x
: dosage vector
N
: total number of pigs
n
: number of cured pigs
d = list(
E = nrow(df),
x = df[[3]],
N = df[[2]],
n = df[[1]]
)
sprintf('the data list has %s enteries' , d[1])
[1] "the data list has 71 enteries"
3. Creating the Stan Models
in order to avoid having to write the stan codes for all 21 models, run the cell bellow and replace dist_a
and dist_b
with the proper distributions for alpha and beta
m = '
data {
int<lower=1> E;
vector[E] x;
int<lower=1> N[E];
int<lower=0> n [E];
}
parameters {
real alpha;
real beta;
}
model {
alpha ~ dist_a;
beta ~ dist_b;
n ~ binomial_logit(N, alpha + beta * x);
}
'
4. Automating the Results with Functions
create a results
dataframe to store the results and automatically populate it by invoking the get_results
function
# initialize the results dataframe
results = data.frame('Model' = 1:21,
'PriorType' = c(rep('beta', 4), rep('logistic', 3), rep('normal', 5), rep('uniform', 8), rep('weibull', 1)),
'RunTime' = rep(0,21),
'alpha_mean' = rep(0,21),
'alpha_sd' = rep(0,21),
'beta_mean' = rep(0,21),
'beta_sd' = rep(0,21),
'n_eff_alpha' = rep(0,21),
'Rhat_alpha' = rep(0,21),
'n_eff_beta' = rep(0,21),
'Rhat_beta' = rep(0,21),
'lp' = rep(0,21))
# a function to insert the results from each model into the results df
get_results = function(i, fit_i){
r = summary(fit_i, pars = c('alpha', 'beta', 'lp__'))$summary
results['RunTime'][[1]][i] = sum(get_elapsed_time(fit_i))
results['alpha_mean'][[1]][i] = r['alpha', 'mean']
results['beta_mean'][[1]][i] = r['beta', 'mean']
results['alpha_sd'][[1]][i] = r['alpha', 'sd']
results['beta_sd'][[1]][i] = r['beta', 'sd']
results['lp'][[1]][i] = r['lp__', 'mean']
results['n_eff_alpha'][[1]][i] = r['alpha', 'n_eff']
results['Rhat_alpha'][[1]][i] = r['alpha', 'Rhat']
results['n_eff_beta'][[1]][i] = r['beta', 'n_eff']
results['Rhat_beta'][[1]][i] = r['beta', 'Rhat']
return(results)
}
# a function to plot the posterior densities of a model
prior_posterior_vis = function(fit, type, p1, p2, a="alpha", b="beta", m='default', l='default'){
if(toString(m) == 'default'){
m = paste('a, b', '~', type, '(', p1, ',', p2, ')')
}
if(toString(l) == 'default'){
l = c(expression(alpha['prior'], beta['prior'], alpha['posterior'], beta['posterior']))
}
a_den = density(fit@sim[["samples"]][[1]][[a]])
b_den = density(fit@sim[["samples"]][[1]][[b]])
x0 = -25
x1 = 30
x_range = c(-20, 25)
y_range = c(0, 0.8)
plot(a_den, xlim=x_range, ylim=y_range, col="purple", lwd = 3, xlab='', ylab='Probability Density', main=m, cex.main=1, font.main = 1)
xlabel <- seq(-20, 25, by = 5)
axis(1, at = xlabel, las = 1)
par(new=TRUE)
plot(b_den, xlim=x_range, ylim=y_range, col="violet", lwd = 3, xlab='', ylab='Probability Density', main='')
par(new=TRUE)
abline(xlim=x_range, ylim=y_range, v=-14.03, col=alpha("purple", 0.5), lwd=2)
par(new=TRUE)
abline(xlim=x_range, ylim=y_range, v=9.39, col=alpha("violet", 0.5), lwd=2)
if (type == 'logistic'){
curve((0.25/p2)*(sech(0.5*(x-p1)/p2)^2), x0, x1, ylim=y_range, add=TRUE, col=alpha("pink", 0.6), lwd = 3)
}
if (type == 'normal'){
curve(exp(-0.5*((x-p1)/p2)^2)/(p2*sqrt(2*pi)), x0, x1, ylim=y_range, add=TRUE, col=alpha("pink", 0.6), lwd = 3)
}
if (type == 'uniform'){
curve((x^0)/(p2-p1), x0, x1, ylim=y_range, add=TRUE, col=alpha("pink", 0.6), lwd = 3)
}
legend("bottomright", legend = l, col = c("pink", "pink", "purple", "violet"), pch = c("____ "), bty = "n", pt.cex = 3, cex = 1, text.col = "black", horiz = F , inset = c(0.01, 0.1))
}
# a function to implement different prior distributions
priorize = function(prior_a, prior_b){
model_code = gsub('dist_a', prior_a, gsub('dist_b', prior_b, m))
return(model_code)
}
5. Running the Stan Files
m0 = '
data {
int<lower=1> E; // number of experiments
vector[E] x; // dosage vector
int<lower=1> N[E]; // total number of pigs
int<lower=0> n[E]; // number of cured pigs
}
parameters {
real alpha;
real beta;
}
model {
n ~ binomial_logit(N, alpha + beta * x);
}
'
5.1. Beta Priors
Cab’t be used since the beta distribution in=s defined in range [0,1] running the cells below will cause the simulation to hang
m1 = priorize('beta(0.5, 0.5)', 'beta(-100, 100)')
s1= stan(model_code = m1, data = d, chains = 4, iter = 3750, algorithm = 'HMC', refresh=0)
results = get_results(1, s1)
m2 = priorize('beta(0.5, 0.5)', 'beta(-20, 20)')
s2 = stan(model_code = m2, data = d, chains = 4, iter = 3800, algorithm = 'HMC', refresh=0)
results = get_results(2, s2)
m3 = priorize('beta(1, 1)', 'beta(-20, 20)')
s3 = stan(model_code = m3, data = d, chains = 4, iter = 3800, algorithm = 'HMC', refresh=0)
results = get_results(3, s3)
m4 = priorize('beta(100, 100)', 'beta(-20, 20)')
s4 = stan(model_code = m4, data = d, chains = 4, iter = 3800, algorithm = 'HMC', refresh=0)
results = get_results(4, s4)
5.2. Logistic Priors
m5 = priorize('logistic(0, 1)', 'logistic(0, 1)')
s5 = stan(model_code = m5, data = d, chains = 4, iter = 3800, algorithm = 'HMC', refresh=0)
results = get_results(5, s5)
m6 = gsub('dist_a', 'logistic(0, 10)', gsub('dist_b', 'logistic(0, 10)', m))
s6 = stan(model_code = m6, data = d, chains = 4, iter = 3800, algorithm = 'HMC', refresh=0)
results = get_results(6, s6)
m7 = gsub('dist_a', 'logistic(10, 10)', gsub('dist_b', 'logistic(10, 10)', m))
s7 = stan(model_code = m7, data = d, chains = 4, iter = 3800, algorithm = 'HMC', refresh=0)
results = get_results(7, s7)
5.3. Normal Priors
m8 = gsub('dist_a', 'normal(0, 20)', gsub('dist_b', 'normal(0, 30)', m))
s8 = stan(model_code = m8, data = d, chains = 4, iter = 4000, algorithm = 'HMC', refresh=0)
results = get_results(8, s8)
m9 = gsub('dist_a', 'normal(0, 1)', gsub('dist_b', 'normal(0, 1)', m))
s9 = stan(model_code = m9, data = d, chains = 4, iter = 4200, algorithm ='HMC', refresh=0)
results = get_results(9, s9)
m10 = gsub('dist_a', 'normal(0, 100)', gsub('dist_b', 'normal(0, 100)', m))
s10 = stan(model_code = m10, data = d, chains = 4, iter = 4000, algorithm ='HMC', refresh=0)
results = get_results(10, s10)
m11 = gsub('dist_a', 'normal(0, 10000)', gsub('dist_b', 'normal(0, 10000)', m))
s11 = stan(model_code = m11, data = d, chains = 4, iter = 4200, algorithm = 'HMC', refresh=0)
results = get_results(11, s11)
m12 = gsub('dist_a', 'normal(-100, 100)', gsub('dist_b', 'normal(-100, 100)', m))
s12 = stan(model_code = m12, data = d, chains = 4, iter = 3850, algorithm ='HMC', refresh=0)
results = get_results(12, s12)
5.4. Uniform Priors
m13 = gsub('dist_a', 'uniform(-100, 100)', gsub('dist_b', 'uniform(-100, 100)', m))
s13 = stan(model_code = m13, data = d, chains = 4, iter = 3850, algorithm = 'HMC', refresh=0)
m14 = priorize('uniform(-1000, 1000)', 'uniform(-1000, 1000)')
s14 = stan(model_code = m14, data = d, chains = 4, iter = 4000, algorithm = 'HMC', refresh=0)
results = get_results(14, s14)
since uniform priors assign a (non-zero) uniform probability in a defined range, and a zero probability outside od=f that range, they should be used with caution: * if the target value is in the zero-probability are, the simulation hangs. This happens in models m15 to m19 as they assign zero probabilities to negative values including the target \[\alpha\] which has most of its density in the negative region.
m15 = priorize('uniform(0, 10)', 'uniform(0, 10)')
s15_agg= stan(model_code = m15, data = d_agg, chains = 4, iter = 3750, algorithm = 'HMC', refresh=0)
results =get_results(15, s15_agg)
m16 = priorize('uniform(0, 20)', 'uniform(0, 20)')
s16 = stan(model_code = m16, data = d, chains = 4, iter = 3750, algorithm = 'HMC', refresh=0)
results = get_results(16, s16)
m17 = priorize('uniform(0, 50)', 'uniform(0, 50)')
s17_agg= stan(model_code = m17, data = d_agg, chains = 4, iter = 3750, algorithm = 'HMC', refresh=0)
results =get_results(17, s17_agg)
m18 = priorize('uniform(0, 100)', 'uniform(0, 100)')
s18 = stan(model_code = m18, data = d, chains = 4, iter = 3750, algorithm = 'HMC', refresh=0)
results = get_results(18, s18)
m19 = priorize('uniform(0, inf)', 'uniform(0, inf)')
s19 = stan(model_code = m19, data = d, chains = 4, iter = 3800, algorithm = 'HMC', refresh=0)
results = get_results(19, s19)
by default, when no prior distribution is defined, stan assumes a uniform distribution: uniform(-inf, inf)
s20 = stan(model_code = m0, data = d, chains = 4, iter = 3800, algorithm = 'HMC', refresh=0)
results = get_results(20, s20)
the weibull prior
m21 = priorize('weibull(1,1)', 'weibull(1,1)')
s21 = stan(model_code = m21, data = d, chains = 4, iter = 3800, algorithm = 'HMC', refresh=0)
results = get_results(20, s20)
6. Sampling Results
samples = s5 # substitute with any other samples
# sampling results
print(samples)
Inference for Stan model: bb58ee27227bdc908ff0d1cea60167a8.
4 chains, each with iter=3800; warmup=1900; thin=1;
post-warmup draws per chain=1900, total post-warmup draws=7600.
mean se_mean sd 2.5% 25% 50% 75% 97.5% n_eff Rhat
alpha -13.13 0.01 0.71 -14.54 -13.60 -13.11 -12.65 -11.80 2713 1
beta 8.75 0.01 0.51 7.78 8.40 8.73 9.09 9.76 2711 1
lp__ -669.99 0.03 1.02 -672.70 -670.38 -669.69 -669.26 -668.99 1210 1
Samples were drawn using HMC(diag_e) at Tue Sep 1 02:21:55 2020.
For each parameter, n_eff is a crude measure of effective sample size,
and Rhat is the potential scale reduction factor on split chains (at
convergence, Rhat=1).
plot(samples)
ci_level: 0.8 (80% intervals)
outer_level: 0.95 (95% intervals)
# chain diagnostics
traceplot(samples)
#density histograms
stan_hist(samples, binwidth = 0.1)
7. Hierarchical Modeling
# Hierarchical Model without NCP
mH = '
data {
int<lower=1> E;
vector[E] x;
int<lower=1> N[E];
int<lower=0> n[E];
}
parameters {
vector[E] alpha;
vector[E] beta;
real mu_a;
real mu_b;
real<lower=0> sigma_a;
real<lower=0> sigma_b;
}
model {
mu_a ~ normal(0,20);
mu_b ~ normal(0,20);
sigma_a ~ normal(0,5);
sigma_b ~ normal(0,5);
alpha ~ normal(mu_a, sigma_a);
beta ~ normal(mu_b, sigma_b);
n ~ binomial_logit(N, alpha + beta .* x);
}
'
# Hierarchical Model with NCP
m_H = '
data {
int<lower=1> E;
vector[E] x;
int<lower=1> N[E];
int<lower=0> n[E];
}
parameters {
vector[E] a_raw;
vector[E] b_raw;
real mu_a;
real mu_b;
real<lower=0> sigma_a;
real<lower=0> sigma_b;
}
transformed parameters {
vector[E] alpha = mu_a + sigma_a * a_raw;
vector[E] beta = mu_b + sigma_b * b_raw;
}
model {
mu_a ~ normal(0,20);
mu_b ~ normal(0,20);
sigma_a ~ normal(0,2);
sigma_b ~ normal(0,2);
a_raw ~ std_normal();
b_raw ~ std_normal();
n ~ binomial_logit(N, alpha + beta .* x);
}
'
s_hh = stan(model_code = m_H, data = d, chains = 4, iter = 50000, algorithm = 'HMC')
8. Hierarchical Resuls
plot(s_hh, pars = c('mu_a', 'mu_b', 'sigma_a', 'sigma_b'))
ci_level: 0.8 (80% intervals)
outer_level: 0.95 (95% intervals)
print(s_hh, pars = c('mu_a', 'mu_b', 'sigma_a', 'sigma_b'))
Inference for Stan model: c6804e8b978a3e25868d36b131c0d591.
4 chains, each with iter=50000; warmup=25000; thin=1;
post-warmup draws per chain=25000, total post-warmup draws=1e+05.
mean se_mean sd 2.5% 25% 50% 75% 97.5% n_eff Rhat
mu_a -14.03 0.01 0.76 -15.56 -14.53 -14.01 -13.51 -12.60 3202 1
mu_b 9.39 0.01 0.54 8.36 9.02 9.38 9.75 10.49 3195 1
sigma_a 0.06 0.00 0.05 0.00 0.02 0.05 0.09 0.17 43070 1
sigma_b 0.04 0.00 0.03 0.00 0.02 0.04 0.06 0.13 40065 1
Samples were drawn using HMC(diag_e) at Sat Aug 29 01:29:02 2020.
For each parameter, n_eff is a crude measure of effective sample size,
and Rhat is the potential scale reduction factor on split chains (at
convergence, Rhat=1).
print(sum(get_elapsed_time(s_hh)))
[1] 280.804
stan_hist(s_hh, pars=c('mu_a', 'mu_b', 'sigma_a', 'sigma_b'), bins=50)
9. Comparison of Models
p <- read.csv("~/Desktop/MSc Project/survival.csv")
df1 = data.frame(p)
# Experimental Data points
plot(p, pch=16, cex=1.5, col=alpha("#69b3a2",0.6), xlab="Dosage", ylab=expression('P'['survival']), cex.lab=1.3, cex.axis=1.2)
# Hill Model
curve(0.9782/(1+(1.51/x)^13.6140), 0.730, 1.890, add=TRUE, col="orange", lwd = 3)
# Hierarchical Model without NCP
curve(exp(-14.09+9.40*x)/(1+exp(-14.09+9.40*x)), 0.730, 1.890, add=TRUE, col="purple", lwd = 3)
# Hierarchical Model with NCP
curve(exp(-14.03+9.39*x)/(1+exp(-14.03+9.39*x)), 0.730, 1.890, add=TRUE, col="red", lwd = 3)
legend("topleft", legend = c('Exprerimental Data'), col = c('#69b3a2'), pch =16, bty = "n", pt.cex = 2, cex = 1, text.col = "black", horiz = F , inset = c(0.03, 0.1))
legend("topleft", legend = c(' Hill', ' Hierarchical LR'), col = c('orange', 'red'), pch =c('-'), bty = "n", pt.cex = 5, cex = 1, text.col = "black", horiz = F , inset = c(0.025, 0.18))
10. Prior and Posterior Densities in Non-Hierarchical Models
prior_posterior_vis(s5, 'logistic', 0, 1, m = expression(paste(alpha, ' , ', beta, ' ~ logistic (0 , 1)')))
prior_posterior_vis(s7, 'logistic', 10, 10, m = expression(paste(alpha, ' , ', beta, ' ~ logistic (10 , 10)')))
prior_posterior_vis(s8, 'normal', 0, 20, m = expression(paste(alpha, ' , ', beta, ' ~ normal (0 , 20)')))
prior_posterior_vis(s13, 'uniform', -100, 100, m = expression(paste(alpha, ' , ', beta, ' ~ uniform (-100 , 100)')))
prior_posterior_vis(s_hh, 'normal', 0, 20, a="mu_a", b="mu_b",
m = expression(paste(mu[alpha], ' , ', mu[beta], ' ~ normal (0 , 20)')),
l = c(expression(mu[alpha][' prior'], mu[beta][' prior'], mu[alpha][' posterior'], mu[beta][' posterior'])))
8. Comparison with AgenaRisk
# MU
xa <- seq(-20, 0, length=1000)
rstan_mua = dnorm(xa, -14.03, 0.76)
agena_mua = dnorm(xa, -15.555, 0.2548)
xb <- seq(0, 15, length=1000)
rstan_mub = dnorm(xb, 9.39, 0.54)
agena_mub = dnorm(xb, 10.48, 0.18485)
par(mfrow=c(2,2))
plot(xa, agena_mua, type="l", xlim=c(-20, -10), ylim=c(0, 2.5), col="green", lwd = 3, xlab='', main=expression(mu[alpha]), ylab='Probability Density', cex.main=1.5, font.main = 1)
xlabel <- seq(-30, 30, by = 2)
axis(1, at = xlabel, las = 1)
par(new=TRUE)
plot(xa, rstan_mua, type='l', xlim=c(-20, -10), ylim=c(0, 2.5), col="#42e0f5", lwd = 3, xlab='', ylab='', main='')
legend("topright", legend = c(' Rstan', ' AgenaRisk'), col = c("#42e0f5", "green"), pch = c("____ "), bty = "n", pt.cex = 3, cex = 0.9, text.col = "black", horiz = F , inset = c(0.01, 0.1))
par(new=TRUE)
abline(xlim=c(-20, -10), ylim=c(0, 2.5), v=-14.03, col=alpha("#42e0f5", 0.5), lwd=2)
par(new=TRUE)
abline(xlim=c(-20, -10), ylim=c(0, 2.5), v=-15.555, col=alpha("green", 0.5), lwd=2)
plot(xb, agena_mub, type="l", xlim=c(5, 15), ylim=c(0, 2.5), col="green", lwd = 3, xlab='', main=expression(mu[beta]), ylab='', cex.main=1.5, font.main = 1)
xlabel <- seq(-30, 30, by = 2)
axis(1, at = xlabel, las = 1)
par(new=TRUE)
plot(xb, rstan_mub, type='l', xlim=c(5, 15), ylim=c(0, 2.5), col="#42e0f5", lwd = 3, xlab='', ylab='', main='')
par(new=TRUE)
abline(xlim=c(5, 15), ylim=c(0, 2.5), v=9.39, col=alpha("#42e0f5", 0.5), lwd=2)
par(new=TRUE)
abline(xlim=c(5, 15), ylim=c(0, 2.5), v=10.48, col=alpha("green", 0.5), lwd=2)
# SIGMA
sa <- seq(0, 2, length=1000)
rstan_siga = dnorm(sa, 0.06, 0.05)
agena_siga = dnorm(sa, 0.02, 0.01)
sb <- seq(0, 2, length=1000)
rstan_sigb = dnorm(sb, 0.04, 0.03)
agena_sigb = dnorm(sb, 0.01, 0.01)
plot(sa, agena_siga, type="l", xlim=c(0, 0.4), ylim=c(0, 45), col="green", lwd = 3, xlab='', main=expression(sigma[alpha]), ylab='Probability Density', cex.main=1.5, font.main = 1)
xlabel <- seq(-2, 2, by = 0.1)
axis(1, at = xlabel, las = 0.2)
par(new=TRUE)
plot(sa, rstan_siga, type='l', xlim=c(0, 0.4), ylim=c(0, 45), col="#42e0f5", lwd = 3, xlab='', ylab='', main='')
par(new=TRUE)
abline(xlim=c(0, 0.4), ylim=c(0, 20), v=0.06, col=alpha("#42e0f5", 0.5), lwd=2)
par(new=TRUE)
abline(xlim=c(0, 0.4), ylim=c(0, 20), v=0.02, col=alpha("green", 0.5), lwd=2)
plot(sb, agena_sigb, type="l", xlim=c(0, 0.4), ylim=c(0, 45), col="green", lwd = 3, xlab='', main=expression(sigma[beta]), ylab='', cex.main=1.5, font.main = 1)
xlabel <- seq(-2, 2, by = 0.2)
axis(1, at = xlabel, las = 0.2)
par(new=TRUE)
plot(sb, rstan_sigb, type='l', xlim=c(0, 0.4), ylim=c(0, 45), col="#42e0f5", lwd = 3, xlab='', ylab='', main='')
par(new=TRUE)
abline(xlim=c(0, 0.4), ylim=c(0, 20), v=0.04, col=alpha("#42e0f5", 0.5), lwd=2)
par(new=TRUE)
abline(xlim=c(0, 0.4), ylim=c(0, 20), v=0.01, col=alpha("green", 0.5), lwd=2)
LS0tCnRpdGxlOiAiQmF5ZXNpYW4gSGllcmFyY2hpY2FsIE1vZGVsaW5nIHdpdGggUlN0YW4iCm91dHB1dDogaHRtbF9ub3RlYm9vawphdXRob3I6ICJbRG9yc2EgTS4gQXJlem9vamldKGh0dHBzOi8vRG9yc2EtQXJlem9vamkuZ2l0aHViLmlvKSIKLS0tCgoqKioKCiMjIDEuIGxvYWRpbmcgdGhlIGRhdGFzZXQgJiBjcmVhdGUgdGhlIGRhdGFmcmFtZQpgYGB7cn0Kc2V0d2QoIn4vRGVza3RvcC9NU2MgUHJvamVjdC9yc3Rhbi9waWdzIikKbGlicmFyeShyc3RhbikKbGlicmFyeShnc3ViZm4pCmxpYnJhcnkocHJhY21hKQpsaWJyYXJ5KHNjYWxlcykKYGBgCgpgYGB7cn0KcGlncyA8LSByZWFkLmNzdigifi9EZXNrdG9wL01TYyBQcm9qZWN0L3JzdGFuL3BpZ3MvcGlncy5jc3YiKQpkZiA9IGRhdGEuZnJhbWUocGlncykKc3VtbWFyeShkZikKcHJpbnQoZGYpCmBgYAojIyAyLiBDcmVhdGluZyB0aGUgRGF0YSBMaXN0CgpgRWAgOiBudW1iZXIgb2YgZXhwZXJpbWVudHMgIApgeGAgOiBkb3NhZ2UgdmVjdG9yICAKYE5gIDogdG90YWwgbnVtYmVyIG9mIHBpZ3MgIApgbmAgOiBudW1iZXIgb2YgY3VyZWQgcGlncwpgYGB7cn0KZCA9IGxpc3QoCiAgRSA9IG5yb3coZGYpLAogIHggPSBkZltbM11dLAogIE4gPSBkZltbMl1dLAogIG4gPSBkZltbMV1dCikKc3ByaW50ZigndGhlIGRhdGEgbGlzdCBoYXMgJXMgZW50ZXJpZXMnICwgZFsxXSkKYGBgCiMjIDMuIENyZWF0aW5nIHRoZSBTdGFuIE1vZGVscwppbiBvcmRlciB0byBhdm9pZCBoYXZpbmcgdG8gd3JpdGUgdGhlIHN0YW4gY29kZXMgZm9yIGFsbCAyMSBtb2RlbHMsIHJ1biB0aGUgY2VsbCBiZWxsb3cgYW5kIHJlcGxhY2UgYGRpc3RfYWAgYW5kIGBkaXN0X2JgIHdpdGggdGhlIHByb3BlciBkaXN0cmlidXRpb25zIGZvciBhbHBoYSBhbmQgYmV0YQpgYGB7cn0KbSA9ICcKZGF0YSB7CiAgaW50PGxvd2VyPTE+IEU7CiAgdmVjdG9yW0VdIHg7CiAgaW50PGxvd2VyPTE+IE5bRV07CiAgaW50PGxvd2VyPTA+IG4gW0VdOwp9CiAgCnBhcmFtZXRlcnMgewogIHJlYWwgYWxwaGE7CiAgcmVhbCBiZXRhOwp9Cgptb2RlbCB7CiAgYWxwaGEgfiBkaXN0X2E7CiAgYmV0YSB+IGRpc3RfYjsKICBuIH4gYmlub21pYWxfbG9naXQoTiwgYWxwaGEgKyBiZXRhICogeCk7Cn0KJwoKbTAgPSAnCmRhdGEgewogIGludDxsb3dlcj0xPiBFOwogIHZlY3RvcltFXSB4OwogIGludDxsb3dlcj0xPiBOW0VdOwogIGludDxsb3dlcj0wPiBuIFtFXTsKfQogIApwYXJhbWV0ZXJzIHsKICByZWFsIGFscGhhOwogIHJlYWwgYmV0YTsKfQoKbW9kZWwgewogIG4gfiBiaW5vbWlhbF9sb2dpdChOLCBhbHBoYSArIGJldGEgKiB4KTsKfQonCmBgYAojIyA0LiBBdXRvbWF0aW5nIHRoZSBSZXN1bHRzIHdpdGggRnVuY3Rpb25zCmNyZWF0ZSBhIGByZXN1bHRzYCBkYXRhZnJhbWUgdG8gc3RvcmUgdGhlIHJlc3VsdHMgYW5kIGF1dG9tYXRpY2FsbHkgcG9wdWxhdGUgaXQgYnkgaW52b2tpbmcgdGhlIGBnZXRfcmVzdWx0c2AgZnVuY3Rpb24KYGBge3J9CiMgaW5pdGlhbGl6ZSB0aGUgcmVzdWx0cyBkYXRhZnJhbWUKcmVzdWx0cyA9IGRhdGEuZnJhbWUoJ01vZGVsJyA9IDE6MjEsIAogICAgICAgICAgICAgICAgICAgICAnUHJpb3JUeXBlJyA9IGMocmVwKCdiZXRhJywgNCksIHJlcCgnbG9naXN0aWMnLCAzKSwgcmVwKCdub3JtYWwnLCA1KSwgcmVwKCd1bmlmb3JtJywgOCksIHJlcCgnd2VpYnVsbCcsIDEpKSwgCiAgICAgICAgICAgICAgICAgICAgICdSdW5UaW1lJyA9IHJlcCgwLDIxKSwgCiAgICAgICAgICAgICAgICAgICAgICdhbHBoYV9tZWFuJyA9IHJlcCgwLDIxKSwgCiAgICAgICAgICAgICAgICAgICAgICdhbHBoYV9zZCcgPSByZXAoMCwyMSksIAogICAgICAgICAgICAgICAgICAgICAnYmV0YV9tZWFuJyA9IHJlcCgwLDIxKSwgCiAgICAgICAgICAgICAgICAgICAgICdiZXRhX3NkJyA9IHJlcCgwLDIxKSwgCiAgICAgICAgICAgICAgICAgICAgICduX2VmZl9hbHBoYScgPSByZXAoMCwyMSksIAogICAgICAgICAgICAgICAgICAgICAnUmhhdF9hbHBoYScgPSByZXAoMCwyMSksIAogICAgICAgICAgICAgICAgICAgICAnbl9lZmZfYmV0YScgPSByZXAoMCwyMSksIAogICAgICAgICAgICAgICAgICAgICAnUmhhdF9iZXRhJyA9IHJlcCgwLDIxKSwKICAgICAgICAgICAgICAgICAgICAgJ2xwJyA9IHJlcCgwLDIxKSkKCgojIGEgZnVuY3Rpb24gdG8gaW5zZXJ0IHRoZSByZXN1bHRzIGZyb20gZWFjaCBtb2RlbCBpbnRvIHRoZSByZXN1bHRzIGRmCgpnZXRfcmVzdWx0cyA9IGZ1bmN0aW9uKGksIGZpdF9pKXsKICByID0gc3VtbWFyeShmaXRfaSwgcGFycyA9IGMoJ2FscGhhJywgJ2JldGEnLCAnbHBfXycpKSRzdW1tYXJ5CiAgcmVzdWx0c1snUnVuVGltZSddW1sxXV1baV0gPSBzdW0oZ2V0X2VsYXBzZWRfdGltZShmaXRfaSkpCiAgcmVzdWx0c1snYWxwaGFfbWVhbiddW1sxXV1baV0gPSByWydhbHBoYScsICdtZWFuJ10KICByZXN1bHRzWydiZXRhX21lYW4nXVtbMV1dW2ldID0gclsnYmV0YScsICdtZWFuJ10KICByZXN1bHRzWydhbHBoYV9zZCddW1sxXV1baV0gPSByWydhbHBoYScsICdzZCddCiAgcmVzdWx0c1snYmV0YV9zZCddW1sxXV1baV0gPSByWydiZXRhJywgJ3NkJ10KICByZXN1bHRzWydscCddW1sxXV1baV0gPSByWydscF9fJywgJ21lYW4nXQogIHJlc3VsdHNbJ25fZWZmX2FscGhhJ11bWzFdXVtpXSA9IHJbJ2FscGhhJywgJ25fZWZmJ10KICByZXN1bHRzWydSaGF0X2FscGhhJ11bWzFdXVtpXSA9IHJbJ2FscGhhJywgJ1JoYXQnXQogIHJlc3VsdHNbJ25fZWZmX2JldGEnXVtbMV1dW2ldID0gclsnYmV0YScsICduX2VmZiddCiAgcmVzdWx0c1snUmhhdF9iZXRhJ11bWzFdXVtpXSA9IHJbJ2JldGEnLCAnUmhhdCddCiAgcmV0dXJuKHJlc3VsdHMpCn0KCiMgYSBmdW5jdGlvbiB0byBwbG90IHRoZSBwb3N0ZXJpb3IgZGVuc2l0aWVzIG9mIGEgbW9kZWwKCnByaW9yX3Bvc3Rlcmlvcl92aXMgPSBmdW5jdGlvbihmaXQsIHR5cGUsIHAxLCBwMiwgYT0iYWxwaGEiLCBiPSJiZXRhIiwgbT0nZGVmYXVsdCcsIGw9J2RlZmF1bHQnKXsKICBpZih0b1N0cmluZyhtKSA9PSAnZGVmYXVsdCcpewogICAgbSA9IHBhc3RlKCdhLCBiJywgJ34nLCB0eXBlLCAnKCcsIHAxLCAnLCcsIHAyLCAnKScpCiAgfQogIGlmKHRvU3RyaW5nKGwpID09ICdkZWZhdWx0Jyl7CiAgICBsID0gYyhleHByZXNzaW9uKGFscGhhWydwcmlvciddLCBiZXRhWydwcmlvciddLCBhbHBoYVsncG9zdGVyaW9yJ10sIGJldGFbJ3Bvc3RlcmlvciddKSkKICB9CiAgYV9kZW4gPSBkZW5zaXR5KGZpdEBzaW1bWyJzYW1wbGVzIl1dW1sxXV1bW2FdXSkKICBiX2RlbiA9IGRlbnNpdHkoZml0QHNpbVtbInNhbXBsZXMiXV1bWzFdXVtbYl1dKQogIHgwID0gLTI1CiAgeDEgPSAzMAogIHhfcmFuZ2UgPSBjKC0yMCwgMjUpCiAgeV9yYW5nZSA9IGMoMCwgMC44KQogIHBsb3QoYV9kZW4sIHhsaW09eF9yYW5nZSwgeWxpbT15X3JhbmdlLCBjb2w9InB1cnBsZSIsIGx3ZCA9IDMsIHhsYWI9JycsIHlsYWI9J1Byb2JhYmlsaXR5IERlbnNpdHknLCBtYWluPW0sIGNleC5tYWluPTEsIGZvbnQubWFpbiA9IDEpCiAgeGxhYmVsIDwtIHNlcSgtMjAsIDI1LCBieSA9IDUpCiAgYXhpcygxLCBhdCA9IHhsYWJlbCwgbGFzID0gMSkKICBwYXIobmV3PVRSVUUpCiAgcGxvdChiX2RlbiwgeGxpbT14X3JhbmdlLCB5bGltPXlfcmFuZ2UsIGNvbD0idmlvbGV0IiwgbHdkID0gMywgeGxhYj0nJywgeWxhYj0nUHJvYmFiaWxpdHkgRGVuc2l0eScsIG1haW49JycpCiAgcGFyKG5ldz1UUlVFKQogIGFibGluZSh4bGltPXhfcmFuZ2UsIHlsaW09eV9yYW5nZSwgdj0tMTQuMDMsIGNvbD1hbHBoYSgicHVycGxlIiwgMC41KSwgbHdkPTIpCiAgcGFyKG5ldz1UUlVFKQogIGFibGluZSh4bGltPXhfcmFuZ2UsIHlsaW09eV9yYW5nZSwgdj05LjM5LCBjb2w9YWxwaGEoInZpb2xldCIsIDAuNSksIGx3ZD0yKQogIGlmICh0eXBlID09ICdsb2dpc3RpYycpewogICAgY3VydmUoKDAuMjUvcDIpKihzZWNoKDAuNSooeC1wMSkvcDIpXjIpLCB4MCwgeDEsIHlsaW09eV9yYW5nZSwgYWRkPVRSVUUsIGNvbD1hbHBoYSgicGluayIsIDAuNiksIGx3ZCA9IDMpCiAgfQogIGlmICh0eXBlID09ICdub3JtYWwnKXsKICAgIGN1cnZlKGV4cCgtMC41KigoeC1wMSkvcDIpXjIpLyhwMipzcXJ0KDIqcGkpKSwgeDAsIHgxLCB5bGltPXlfcmFuZ2UsIGFkZD1UUlVFLCBjb2w9YWxwaGEoInBpbmsiLCAwLjYpLCBsd2QgPSAzKQogIH0KICAgIGlmICh0eXBlID09ICd1bmlmb3JtJyl7CiAgICBjdXJ2ZSgoeF4wKS8ocDItcDEpLCB4MCwgeDEsIHlsaW09eV9yYW5nZSwgYWRkPVRSVUUsIGNvbD1hbHBoYSgicGluayIsIDAuNiksIGx3ZCA9IDMpCiAgfQogIGxlZ2VuZCgiYm90dG9tcmlnaHQiLCBsZWdlbmQgPSBsLCBjb2wgPSBjKCJwaW5rIiwgInBpbmsiLCAicHVycGxlIiwgInZpb2xldCIpLCBwY2ggPSBjKCJfX19fICIpLCBidHkgPSAibiIsIHB0LmNleCA9IDMsIGNleCA9IDEsIHRleHQuY29sID0gImJsYWNrIiwgaG9yaXogPSBGICwgaW5zZXQgPSBjKDAuMDEsIDAuMSkpCn0KCiMgYSBmdW5jdGlvbiB0byBpbXBsZW1lbnQgZGlmZmVyZW50IHByaW9yIGRpc3RyaWJ1dGlvbnMKCnByaW9yaXplID0gZnVuY3Rpb24ocHJpb3JfYSwgcHJpb3JfYil7CiAgbW9kZWxfY29kZSA9IGdzdWIoJ2Rpc3RfYScsIHByaW9yX2EsIGdzdWIoJ2Rpc3RfYicsIHByaW9yX2IsIG0pKQogIHJldHVybihtb2RlbF9jb2RlKQp9CmBgYAojIyA1LiBSdW5uaW5nIHRoZSBTdGFuIEZpbGVzCmBgYHtyfQptMCA9ICcKZGF0YSB7CiAgaW50PGxvd2VyPTE+IEU7IC8vIG51bWJlciBvZiBleHBlcmltZW50cwogIHZlY3RvcltFXSB4OyAvLyBkb3NhZ2UgdmVjdG9yCiAgaW50PGxvd2VyPTE+IE5bRV07IC8vIHRvdGFsIG51bWJlciBvZiBwaWdzCiAgaW50PGxvd2VyPTA+IG5bRV07IC8vIG51bWJlciBvZiBjdXJlZCBwaWdzCn0KICAKcGFyYW1ldGVycyB7CiAgcmVhbCBhbHBoYTsKICByZWFsIGJldGE7Cn0KCm1vZGVsIHsKICBuIH4gYmlub21pYWxfbG9naXQoTiwgYWxwaGEgKyBiZXRhICogeCk7Cn0KJwpgYGAKIyMjIDUuMS4gQmV0YSBQcmlvcnMKQ2FiJ3QgYmUgdXNlZCBzaW5jZSB0aGUgYmV0YSBkaXN0cmlidXRpb24gaW49cyBkZWZpbmVkIGluIHJhbmdlIFswLDFdCioqcnVubmluZyB0aGUgY2VsbHMgYmVsb3cgd2lsbCBjYXVzZSB0aGUgc2ltdWxhdGlvbiB0byBoYW5nKioKYGBge3J9Cm0xID0gcHJpb3JpemUoJ2JldGEoMC41LCAwLjUpJywgJ2JldGEoLTEwMCwgMTAwKScpCnMxPSBzdGFuKG1vZGVsX2NvZGUgPSBtMSwgZGF0YSA9IGQsIGNoYWlucyA9IDQsIGl0ZXIgPSAzNzUwLCBhbGdvcml0aG0gPSAnSE1DJywgcmVmcmVzaD0wKQpyZXN1bHRzID0gZ2V0X3Jlc3VsdHMoMSwgczEpCmBgYAoKYGBge3J9Cm0yID0gcHJpb3JpemUoJ2JldGEoMC41LCAwLjUpJywgJ2JldGEoLTIwLCAyMCknKQpzMiA9IHN0YW4obW9kZWxfY29kZSA9IG0yLCBkYXRhID0gZCwgY2hhaW5zID0gNCwgaXRlciA9IDM4MDAsIGFsZ29yaXRobSA9ICdITUMnLCByZWZyZXNoPTApCnJlc3VsdHMgPSBnZXRfcmVzdWx0cygyLCBzMikKYGBgCgpgYGB7cn0KbTMgPSBwcmlvcml6ZSgnYmV0YSgxLCAxKScsICdiZXRhKC0yMCwgMjApJykKczMgPSBzdGFuKG1vZGVsX2NvZGUgPSBtMywgZGF0YSA9IGQsIGNoYWlucyA9IDQsIGl0ZXIgPSAzODAwLCBhbGdvcml0aG0gPSAnSE1DJywgcmVmcmVzaD0wKQpyZXN1bHRzID0gZ2V0X3Jlc3VsdHMoMywgczMpCmBgYAoKYGBge3J9Cm00ID0gcHJpb3JpemUoJ2JldGEoMTAwLCAxMDApJywgJ2JldGEoLTIwLCAyMCknKQpzNCA9IHN0YW4obW9kZWxfY29kZSA9IG00LCBkYXRhID0gZCwgY2hhaW5zID0gNCwgaXRlciA9IDM4MDAsIGFsZ29yaXRobSA9ICdITUMnLCByZWZyZXNoPTApCnJlc3VsdHMgPSBnZXRfcmVzdWx0cyg0LCBzNCkKYGBgCiMjIyA1LjIuIExvZ2lzdGljIFByaW9ycwpgYGB7cn0KbTUgPSBwcmlvcml6ZSgnbG9naXN0aWMoMCwgMSknLCAnbG9naXN0aWMoMCwgMSknKQpzNSA9IHN0YW4obW9kZWxfY29kZSA9IG01LCBkYXRhID0gZCwgY2hhaW5zID0gNCwgaXRlciA9IDM4MDAsIGFsZ29yaXRobSA9ICdITUMnLCByZWZyZXNoPTApCnJlc3VsdHMgPSBnZXRfcmVzdWx0cyg1LCBzNSkKYGBgCgpgYGB7cn0KbTYgPSBwcmlvcml6ZSgnbG9naXN0aWMoMCwgMTApJywgJ2xvZ2lzdGljKDAsIDEwKScpCnM2ID0gc3Rhbihtb2RlbF9jb2RlID0gbTYsIGRhdGEgPSBkLCBjaGFpbnMgPSA0LCBpdGVyID0gMzgwMCwgYWxnb3JpdGhtID0gJ0hNQycsIHJlZnJlc2g9MCkKcmVzdWx0cyA9IGdldF9yZXN1bHRzKDYsIHM2KQpgYGAKCmBgYHtyfQptNyA9IHByaW9yaXplKCdsb2dpc3RpYygxMCwgMTApJywgJ2xvZ2lzdGljKDEwLCAxMCknKQpzNyA9IHN0YW4obW9kZWxfY29kZSA9IG03LCBkYXRhID0gZCwgY2hhaW5zID0gNCwgaXRlciA9IDM4MDAsIGFsZ29yaXRobSA9ICdITUMnLCByZWZyZXNoPTApCnJlc3VsdHMgPSBnZXRfcmVzdWx0cyg3LCBzNykKYGBgCiMjIyA1LjMuIE5vcm1hbCBQcmlvcnMKYGBge3J9Cm04ID0gcHJpb3JpemUoJ25vcm1hbCgwLCAyMCknLCAnbm9ybWFsKDAsIDMwKScpCnM4ID0gc3Rhbihtb2RlbF9jb2RlID0gbTgsIGRhdGEgPSBkLCBjaGFpbnMgPSA0LCBpdGVyID0gNDAwMCwgYWxnb3JpdGhtID0gJ0hNQycsIHJlZnJlc2g9MCkKcmVzdWx0cyA9IGdldF9yZXN1bHRzKDgsIHM4KQpgYGAKCmBgYHtyfQptOSA9IHByaW9yaXplKCdub3JtYWwoMCwgMSknLCAnbm9ybWFsKDAsIDEpJykKczkgPSBzdGFuKG1vZGVsX2NvZGUgPSBtOSwgZGF0YSA9IGQsIGNoYWlucyA9IDQsIGl0ZXIgPSA0MjAwLCBhbGdvcml0aG0gPSdITUMnLCByZWZyZXNoPTApCnJlc3VsdHMgPSBnZXRfcmVzdWx0cyg5LCBzOSkKYGBgCgpgYGB7cn0KbTEwID0gcHJpb3JpemUoJ25vcm1hbCgwLCAxMDApJywgJ25vcm1hbCgwLCAxMDApJykKczEwID0gc3Rhbihtb2RlbF9jb2RlID0gbTEwLCBkYXRhID0gZCwgY2hhaW5zID0gNCwgaXRlciA9IDQwMDAsIGFsZ29yaXRobSA9J0hNQycsIHJlZnJlc2g9MCkKcmVzdWx0cyA9IGdldF9yZXN1bHRzKDEwLCBzMTApCmBgYAoKYGBge3J9Cm0xMSA9IHByaW9yaXplKCdub3JtYWwoMCwgMTAwMDApJywgJ25vcm1hbCgwLCAxMDAwMCknKQpzMTEgPSBzdGFuKG1vZGVsX2NvZGUgPSBtMTEsIGRhdGEgPSBkLCBjaGFpbnMgPSA0LCBpdGVyID0gNDIwMCwgYWxnb3JpdGhtID0gJ0hNQycsIHJlZnJlc2g9MCkKcmVzdWx0cyA9IGdldF9yZXN1bHRzKDExLCBzMTEpCmBgYAoKYGBge3J9Cm0xMiA9IHByaW9yaXplKCdub3JtYWwoLTEwMCwgMTAwKScsICdub3JtYWwoLTEwMCwgMTAwKScpCnMxMiA9IHN0YW4obW9kZWxfY29kZSA9IG0xMiwgZGF0YSA9IGQsIGNoYWlucyA9IDQsIGl0ZXIgPSAzODUwLCBhbGdvcml0aG0gPSdITUMnLCByZWZyZXNoPTApCnJlc3VsdHMgPSBnZXRfcmVzdWx0cygxMiwgczEyKQpgYGAKIyMjIDUuNC4gVW5pZm9ybSBQcmlvcnMKYGBge3J9Cm0xMyA9IHByaW9yaXplKCd1bmlmb3JtKC0xMDAsIDEwMCknLCAndW5pZm9ybSgtMTAwLCAxMDApJykKczEzID0gc3Rhbihtb2RlbF9jb2RlID0gbTEzLCBkYXRhID0gZCwgY2hhaW5zID0gNCwgaXRlciA9IDM4NTAsIGFsZ29yaXRobSA9ICdITUMnLCByZWZyZXNoPTApCnJlc3VsdHMgPSBnZXRfcmVzdWx0cygxMywgczEzKQpgYGAKCmBgYHtyfQptMTQgPSBwcmlvcml6ZSgndW5pZm9ybSgtMTAwMCwgMTAwMCknLCAndW5pZm9ybSgtMTAwMCwgMTAwMCknKQpzMTQgPSBzdGFuKG1vZGVsX2NvZGUgPSBtMTQsIGRhdGEgPSBkLCBjaGFpbnMgPSA0LCBpdGVyID0gNDAwMCwgYWxnb3JpdGhtID0gJ0hNQycsIHJlZnJlc2g9MCkKcmVzdWx0cyA9IGdldF9yZXN1bHRzKDE0LCBzMTQpCmBgYApzaW5jZSB1bmlmb3JtIHByaW9ycyBhc3NpZ24gYSAobm9uLXplcm8pIHVuaWZvcm0gcHJvYmFiaWxpdHkgaW4gYSBkZWZpbmVkIHJhbmdlLCBhbmQgYSB6ZXJvIHByb2JhYmlsaXR5IG91dHNpZGUgb2Q9ZiB0aGF0IHJhbmdlLCB0aGV5IHNob3VsZCBiZSB1c2VkIHdpdGggY2F1dGlvbjoKKiBpZiB0aGUgdGFyZ2V0IHZhbHVlIGlzIGluIHRoZSB6ZXJvLXByb2JhYmlsaXR5IGFyZSwgdGhlIHNpbXVsYXRpb24gaGFuZ3MuIFRoaXMgaGFwcGVucyBpbiBtb2RlbHMgbTE1IHRvIG0xOSBhcyB0aGV5IGFzc2lnbiB6ZXJvIHByb2JhYmlsaXRpZXMgdG8gbmVnYXRpdmUgdmFsdWVzIGluY2x1ZGluZyB0aGUgdGFyZ2V0ICQkXGFscGhhJCQgd2hpY2ggaGFzIG1vc3Qgb2YgaXRzIGRlbnNpdHkgaW4gdGhlIG5lZ2F0aXZlIHJlZ2lvbi4KYGBge3J9Cm0xNSA9IHByaW9yaXplKCd1bmlmb3JtKDAsIDEwKScsICd1bmlmb3JtKDAsIDEwKScpCnMxNV9hZ2c9IHN0YW4obW9kZWxfY29kZSA9IG0xNSwgZGF0YSA9IGRfYWdnLCBjaGFpbnMgPSA0LCBpdGVyID0gMzc1MCwgYWxnb3JpdGhtID0gJ0hNQycsIHJlZnJlc2g9MCkKcmVzdWx0cyA9Z2V0X3Jlc3VsdHMoMTUsIHMxNV9hZ2cpCmBgYAoKYGBge3J9Cm0xNiA9IHByaW9yaXplKCd1bmlmb3JtKDAsIDIwKScsICd1bmlmb3JtKDAsIDIwKScpCnMxNiA9IHN0YW4obW9kZWxfY29kZSA9IG0xNiwgZGF0YSA9IGQsIGNoYWlucyA9IDQsIGl0ZXIgPSAzNzUwLCBhbGdvcml0aG0gPSAnSE1DJywgcmVmcmVzaD0wKQpyZXN1bHRzID0gZ2V0X3Jlc3VsdHMoMTYsIHMxNikKYGBgCgpgYGB7cn0KbTE3ID0gcHJpb3JpemUoJ3VuaWZvcm0oMCwgNTApJywgJ3VuaWZvcm0oMCwgNTApJykKczE3X2FnZz0gc3Rhbihtb2RlbF9jb2RlID0gbTE3LCBkYXRhID0gZF9hZ2csIGNoYWlucyA9IDQsIGl0ZXIgPSAzNzUwLCBhbGdvcml0aG0gPSAnSE1DJywgcmVmcmVzaD0wKQpyZXN1bHRzID1nZXRfcmVzdWx0cygxNywgczE3X2FnZykKYGBgCgpgYGB7cn0KbTE4ID0gcHJpb3JpemUoJ3VuaWZvcm0oMCwgMTAwKScsICd1bmlmb3JtKDAsIDEwMCknKQpzMTggPSBzdGFuKG1vZGVsX2NvZGUgPSBtMTgsIGRhdGEgPSBkLCBjaGFpbnMgPSA0LCBpdGVyID0gMzc1MCwgYWxnb3JpdGhtID0gJ0hNQycsIHJlZnJlc2g9MCkKcmVzdWx0cyA9IGdldF9yZXN1bHRzKDE4LCBzMTgpCmBgYAoKYGBge3J9Cm0xOSA9IHByaW9yaXplKCd1bmlmb3JtKDAsIGluZiknLCAndW5pZm9ybSgwLCBpbmYpJykKczE5ID0gc3Rhbihtb2RlbF9jb2RlID0gbTE5LCBkYXRhID0gZCwgY2hhaW5zID0gNCwgaXRlciA9IDM4MDAsIGFsZ29yaXRobSA9ICdITUMnLCByZWZyZXNoPTApCnJlc3VsdHMgPSBnZXRfcmVzdWx0cygxOSwgczE5KQpgYGAKYnkgZGVmYXVsdCwgd2hlbiBubyBwcmlvciBkaXN0cmlidXRpb24gaXMgZGVmaW5lZCwgc3RhbiBhc3N1bWVzIGEgdW5pZm9ybSBkaXN0cmlidXRpb246IHVuaWZvcm0oLWluZiwgaW5mKQpgYGB7cn0KczIwID0gc3Rhbihtb2RlbF9jb2RlID0gbTAsIGRhdGEgPSBkLCBjaGFpbnMgPSA0LCBpdGVyID0gMzgwMCwgYWxnb3JpdGhtID0gJ0hNQycsIHJlZnJlc2g9MCkKcmVzdWx0cyA9IGdldF9yZXN1bHRzKDIwLCBzMjApCmBgYAp0aGUgd2VpYnVsbCBwcmlvciAKYGBge3J9Cm0yMSA9IHByaW9yaXplKCd3ZWlidWxsKDEsMSknLCAnd2VpYnVsbCgxLDEpJykKczIxID0gc3Rhbihtb2RlbF9jb2RlID0gbTIxLCBkYXRhID0gZCwgY2hhaW5zID0gNCwgaXRlciA9IDM4MDAsIGFsZ29yaXRobSA9ICdITUMnLCByZWZyZXNoPTApCnJlc3VsdHMgPSBnZXRfcmVzdWx0cygyMCwgczIwKQpgYGAKIyMgNi4gU2FtcGxpbmcgUmVzdWx0cwpgYGB7cn0Kc2FtcGxlcyA9IHM1ICMgc3Vic3RpdHV0ZSB3aXRoIGFueSBvdGhlciBzYW1wbGVzCgojIHNhbXBsaW5nIHJlc3VsdHMKcHJpbnQoc2FtcGxlcykKcGxvdChzYW1wbGVzKQoKIyBjaGFpbiBkaWFnbm9zdGljcwp0cmFjZXBsb3Qoc2FtcGxlcykKCiNkZW5zaXR5IGhpc3RvZ3JhbXMKc3Rhbl9oaXN0KHNhbXBsZXMsIGJpbndpZHRoID0gMC4xKQpgYGAKIyMgNy4gSGllcmFyY2hpY2FsIE1vZGVsaW5nCmBgYHtyfQojIEhpZXJhcmNoaWNhbCBNb2RlbCB3aXRob3V0IE5DUAptSCA9ICcKZGF0YSB7CiAgaW50PGxvd2VyPTE+IEU7CiAgdmVjdG9yW0VdIHg7CiAgaW50PGxvd2VyPTE+IE5bRV07CiAgaW50PGxvd2VyPTA+IG5bRV07Cn0KCnBhcmFtZXRlcnMgewogIHZlY3RvcltFXSBhbHBoYTsKICB2ZWN0b3JbRV0gYmV0YTsKICByZWFsIG11X2E7CiAgcmVhbCBtdV9iOwogIHJlYWw8bG93ZXI9MD4gc2lnbWFfYTsKICByZWFsPGxvd2VyPTA+IHNpZ21hX2I7Cn0KCm1vZGVsIHsKICBtdV9hIH4gbm9ybWFsKDAsMjApOwogIG11X2IgfiBub3JtYWwoMCwyMCk7CiAgc2lnbWFfYSB+IG5vcm1hbCgwLDUpOwogIHNpZ21hX2IgfiBub3JtYWwoMCw1KTsKICBhbHBoYSB+IG5vcm1hbChtdV9hLCBzaWdtYV9hKTsKICBiZXRhIH4gbm9ybWFsKG11X2IsIHNpZ21hX2IpOwogIG4gfiBiaW5vbWlhbF9sb2dpdChOLCBhbHBoYSArIGJldGEgLiogeCk7Cn0KJwojIEhpZXJhcmNoaWNhbCBNb2RlbCB3aXRoIE5DUAoKbV9IID0gJwpkYXRhIHsKICBpbnQ8bG93ZXI9MT4gRTsKICB2ZWN0b3JbRV0geDsKICBpbnQ8bG93ZXI9MT4gTltFXTsKICBpbnQ8bG93ZXI9MD4gbltFXTsKfQogIApwYXJhbWV0ZXJzIHsKICB2ZWN0b3JbRV0gYV9yYXc7CiAgdmVjdG9yW0VdIGJfcmF3OwogIHJlYWwgbXVfYTsKICByZWFsIG11X2I7CiAgcmVhbDxsb3dlcj0wPiBzaWdtYV9hOwogIHJlYWw8bG93ZXI9MD4gc2lnbWFfYjsKfQoKdHJhbnNmb3JtZWQgcGFyYW1ldGVycyB7CiAgdmVjdG9yW0VdIGFscGhhID0gbXVfYSArIHNpZ21hX2EgKiBhX3JhdzsKICB2ZWN0b3JbRV0gYmV0YSA9IG11X2IgKyBzaWdtYV9iICogYl9yYXc7Cn0KCm1vZGVsIHsKICBtdV9hIH4gbm9ybWFsKDAsMjApOwogIG11X2IgfiBub3JtYWwoMCwyMCk7CiAgc2lnbWFfYSB+IG5vcm1hbCgwLDIpOwogIHNpZ21hX2IgfiBub3JtYWwoMCwyKTsKICBhX3JhdyB+IHN0ZF9ub3JtYWwoKTsKICBiX3JhdyB+IHN0ZF9ub3JtYWwoKTsKICBuIH4gYmlub21pYWxfbG9naXQoTiwgYWxwaGEgKyBiZXRhIC4qIHgpOwp9CicKYGBgCgpgYGB7cn0Kc19oaCA9IHN0YW4obW9kZWxfY29kZSA9IG1fSCwgZGF0YSA9IGQsIGNoYWlucyA9IDQsIGl0ZXIgPSA1MDAwMCwgYWxnb3JpdGhtID0gJ0hNQycpCmBgYAojIyA4LiBIaWVyYXJjaGljYWwgUmVzdWxzCmBgYHtyfQpwbG90KHNfaGgsIHBhcnMgPSBjKCdtdV9hJywgJ211X2InLCAnc2lnbWFfYScsICdzaWdtYV9iJykpCnByaW50KHNfaGgsIHBhcnMgPSBjKCdtdV9hJywgJ211X2InLCAnc2lnbWFfYScsICdzaWdtYV9iJykpCnByaW50KHN1bShnZXRfZWxhcHNlZF90aW1lKHNfaGgpKSkKc3Rhbl9oaXN0KHNfaGgsIHBhcnM9YygnbXVfYScsICdtdV9iJywgJ3NpZ21hX2EnLCAnc2lnbWFfYicpLCBiaW5zPTUwKQpgYGAKIyMgOS4gQ29tcGFyaXNvbiBvZiBNb2RlbHMKYGBge3J9CnAgPSByZWFkLmNzdigifi9EZXNrdG9wL01TYyBQcm9qZWN0L3N1cnZpdmFsLmNzdiIpCmRmMSA9IGRhdGEuZnJhbWUocCkKCiMgRXhwZXJpbWVudGFsIERhdGEgcG9pbnRzCnBsb3QocCwgcGNoPTE2LCBjZXg9MS41LCBjb2w9YWxwaGEoIiM2OWIzYTIiLDAuNiksIHhsYWI9IkRvc2FnZSIsIHlsYWI9ZXhwcmVzc2lvbignUCdbJ3N1cnZpdmFsJ10pLCBjZXgubGFiPTEuMywgY2V4LmF4aXM9MS4yKQoKIyBIaWxsIE1vZGVsCmN1cnZlKDAuOTc4Mi8oMSsoMS41MS94KV4xMy42MTQwKSwgMC43MzAsIDEuODkwLCBhZGQ9VFJVRSwgY29sPSJvcmFuZ2UiLCBsd2QgPSAzKQoKIyBIaWVyYXJjaGljYWwgTW9kZWwgd2l0aG91dCBOQ1AKY3VydmUoZXhwKC0xNC4wOSs5LjQwKngpLygxK2V4cCgtMTQuMDkrOS40MCp4KSksIDAuNzMwLCAxLjg5MCwgYWRkPVRSVUUsIGNvbD0icHVycGxlIiwgbHdkID0gMykKCiMgSGllcmFyY2hpY2FsIE1vZGVsIHdpdGggTkNQCmN1cnZlKGV4cCgtMTQuMDMrOS4zOSp4KS8oMStleHAoLTE0LjAzKzkuMzkqeCkpLCAwLjczMCwgMS44OTAsIGFkZD1UUlVFLCBjb2w9InJlZCIsIGx3ZCA9IDMpCmxlZ2VuZCgidG9wbGVmdCIsIGxlZ2VuZCA9IGMoJ0V4cHJlcmltZW50YWwgRGF0YScpLCBjb2wgPSBjKCcjNjliM2EyJyksIHBjaCA9MTYsIGJ0eSA9ICJuIiwgcHQuY2V4ID0gMiwgY2V4ID0gMSwgIHRleHQuY29sID0gImJsYWNrIiwgaG9yaXogPSBGICwgaW5zZXQgPSBjKDAuMDMsIDAuMSkpCmxlZ2VuZCgidG9wbGVmdCIsIGxlZ2VuZCA9IGMoJyBIaWxsJywgJyBIaWVyYXJjaGljYWwgTFInKSwgY29sID0gYygnb3JhbmdlJywgJ3JlZCcpLCBwY2ggPWMoJy0nKSwgYnR5ID0gIm4iLCBwdC5jZXggPSA1LCBjZXggPSAxLCAgdGV4dC5jb2wgPSAiYmxhY2siLCBob3JpeiA9IEYgLCBpbnNldCA9IGMoMC4wMjUsIDAuMTgpKQpgYGAKIyMgMTAuIFByaW9yIGFuZCBQb3N0ZXJpb3IgRGVuc2l0aWVzIGluIE5vbi1IaWVyYXJjaGljYWwgTW9kZWxzCmBgYHtyfQpwcmlvcl9wb3N0ZXJpb3JfdmlzKHM1LCAnbG9naXN0aWMnLCAwLCAxLCBtID0gZXhwcmVzc2lvbihwYXN0ZShhbHBoYSwgJyAsICcsIGJldGEsICcgfiBsb2dpc3RpYyAoMCAsIDEpJykpKQpwcmlvcl9wb3N0ZXJpb3JfdmlzKHM3LCAnbG9naXN0aWMnLCAxMCwgMTAsIG0gPSBleHByZXNzaW9uKHBhc3RlKGFscGhhLCAnICwgJywgYmV0YSwgJyB+IGxvZ2lzdGljICgxMCAsIDEwKScpKSkKcHJpb3JfcG9zdGVyaW9yX3ZpcyhzOCwgJ25vcm1hbCcsIDAsIDIwLCBtID0gZXhwcmVzc2lvbihwYXN0ZShhbHBoYSwgJyAsICcsIGJldGEsICcgfiBub3JtYWwgKDAgLCAyMCknKSkpCnByaW9yX3Bvc3Rlcmlvcl92aXMoczEzLCAndW5pZm9ybScsIC0xMDAsIDEwMCwgbSA9IGV4cHJlc3Npb24ocGFzdGUoYWxwaGEsICcgLCAnLCBiZXRhLCAnIH4gdW5pZm9ybSAoLTEwMCAsIDEwMCknKSkpCgpwcmlvcl9wb3N0ZXJpb3JfdmlzKHNfaGgsICdub3JtYWwnLCAwLCAyMCwgYT0ibXVfYSIsIGI9Im11X2IiLCAKICAgICAgICAgICAgICAgICAgICBtID0gZXhwcmVzc2lvbihwYXN0ZShtdVthbHBoYV0sICcgLCAnLCBtdVtiZXRhXSwgJyB+IG5vcm1hbCAoMCAsIDIwKScpKSwgCiAgICAgICAgICAgICAgICAgICAgbCA9IGMoZXhwcmVzc2lvbihtdVthbHBoYV1bJyBwcmlvciddLCBtdVtiZXRhXVsnIHByaW9yJ10sIG11W2FscGhhXVsnIHBvc3RlcmlvciddLCBtdVtiZXRhXVsnIHBvc3RlcmlvciddKSkpCmBgYAojIyA4LiBDb21wYXJpc29uIHdpdGggQWdlbmFSaXNrCmBgYHtyfQojIE1VIAoKeGEgPC0gc2VxKC0yMCwgMCwgbGVuZ3RoPTEwMDApCnJzdGFuX211YSA9IGRub3JtKHhhLCAtMTQuMDMsIDAuNzYpCmFnZW5hX211YSA9IGRub3JtKHhhLCAtMTUuNTU1LCAwLjI1NDgpCgp4YiA8LSBzZXEoMCwgMTUsIGxlbmd0aD0xMDAwKQpyc3Rhbl9tdWIgPSBkbm9ybSh4YiwgOS4zOSwgMC41NCkKYWdlbmFfbXViID0gZG5vcm0oeGIsIDEwLjQ4LCAwLjE4NDg1KQoKcGFyKG1mcm93PWMoMiwyKSkKcGxvdCh4YSwgYWdlbmFfbXVhLCB0eXBlPSJsIiwgeGxpbT1jKC0yMCwgLTEwKSwgeWxpbT1jKDAsIDIuNSksIGNvbD0iZ3JlZW4iLCBsd2QgPSAzLCB4bGFiPScnLCBtYWluPWV4cHJlc3Npb24obXVbYWxwaGFdKSwgeWxhYj0nUHJvYmFiaWxpdHkgRGVuc2l0eScsIGNleC5tYWluPTEuNSwgZm9udC5tYWluID0gMSkKeGxhYmVsIDwtIHNlcSgtMzAsIDMwLCBieSA9IDIpCmF4aXMoMSwgYXQgPSB4bGFiZWwsIGxhcyA9IDEpCnBhcihuZXc9VFJVRSkKcGxvdCh4YSwgcnN0YW5fbXVhLCB0eXBlPSdsJywgeGxpbT1jKC0yMCwgLTEwKSwgeWxpbT1jKDAsIDIuNSksIGNvbD0iIzQyZTBmNSIsIGx3ZCA9IDMsIHhsYWI9JycsIHlsYWI9JycsIG1haW49JycpCmxlZ2VuZCgidG9wcmlnaHQiLCBsZWdlbmQgPSBjKCcgUnN0YW4nLCAnIEFnZW5hUmlzaycpLCBjb2wgPSBjKCIjNDJlMGY1IiwgImdyZWVuIiksIHBjaCA9IGMoIl9fX18gIiksIGJ0eSA9ICJuIiwgcHQuY2V4ID0gMywgY2V4ID0gMC45LCB0ZXh0LmNvbCA9ICJibGFjayIsIGhvcml6ID0gRiAsIGluc2V0ID0gYygwLjAxLCAwLjEpKQpwYXIobmV3PVRSVUUpCmFibGluZSh4bGltPWMoLTIwLCAtMTApLCB5bGltPWMoMCwgMi41KSwgdj0tMTQuMDMsIGNvbD1hbHBoYSgiIzQyZTBmNSIsIDAuNSksIGx3ZD0yKQpwYXIobmV3PVRSVUUpCmFibGluZSh4bGltPWMoLTIwLCAtMTApLCB5bGltPWMoMCwgMi41KSwgdj0tMTUuNTU1LCBjb2w9YWxwaGEoImdyZWVuIiwgMC41KSwgbHdkPTIpCgpwbG90KHhiLCBhZ2VuYV9tdWIsIHR5cGU9ImwiLCB4bGltPWMoNSwgMTUpLCB5bGltPWMoMCwgMi41KSwgY29sPSJncmVlbiIsIGx3ZCA9IDMsIHhsYWI9JycsIG1haW49ZXhwcmVzc2lvbihtdVtiZXRhXSksIHlsYWI9JycsIGNleC5tYWluPTEuNSwgZm9udC5tYWluID0gMSkKeGxhYmVsIDwtIHNlcSgtMzAsIDMwLCBieSA9IDIpCmF4aXMoMSwgYXQgPSB4bGFiZWwsIGxhcyA9IDEpCnBhcihuZXc9VFJVRSkKcGxvdCh4YiwgcnN0YW5fbXViLCB0eXBlPSdsJywgeGxpbT1jKDUsIDE1KSwgeWxpbT1jKDAsIDIuNSksIGNvbD0iIzQyZTBmNSIsIGx3ZCA9IDMsIHhsYWI9JycsIHlsYWI9JycsIG1haW49JycpCnBhcihuZXc9VFJVRSkKYWJsaW5lKHhsaW09Yyg1LCAxNSksIHlsaW09YygwLCAyLjUpLCB2PTkuMzksIGNvbD1hbHBoYSgiIzQyZTBmNSIsIDAuNSksIGx3ZD0yKQpwYXIobmV3PVRSVUUpCmFibGluZSh4bGltPWMoNSwgMTUpLCB5bGltPWMoMCwgMi41KSwgdj0xMC40OCwgY29sPWFscGhhKCJncmVlbiIsIDAuNSksIGx3ZD0yKQoKIyBTSUdNQQoKc2EgPC0gc2VxKDAsIDIsIGxlbmd0aD0xMDAwKQpyc3Rhbl9zaWdhID0gZG5vcm0oc2EsIDAuMDYsIDAuMDUpCmFnZW5hX3NpZ2EgPSBkbm9ybShzYSwgMC4wMiwgMC4wMSkKCnNiIDwtIHNlcSgwLCAyLCBsZW5ndGg9MTAwMCkKcnN0YW5fc2lnYiA9IGRub3JtKHNiLCAwLjA0LCAwLjAzKQphZ2VuYV9zaWdiID0gZG5vcm0oc2IsIDAuMDEsIDAuMDEpCgpwbG90KHNhLCBhZ2VuYV9zaWdhLCB0eXBlPSJsIiwgeGxpbT1jKDAsIDAuNCksIHlsaW09YygwLCA0NSksIGNvbD0iZ3JlZW4iLCBsd2QgPSAzLCB4bGFiPScnLCBtYWluPWV4cHJlc3Npb24oc2lnbWFbYWxwaGFdKSwgeWxhYj0nUHJvYmFiaWxpdHkgRGVuc2l0eScsIGNleC5tYWluPTEuNSwgZm9udC5tYWluID0gMSkKeGxhYmVsIDwtIHNlcSgtMiwgMiwgYnkgPSAwLjEpCmF4aXMoMSwgYXQgPSB4bGFiZWwsIGxhcyA9IDAuMikKcGFyKG5ldz1UUlVFKQpwbG90KHNhLCByc3Rhbl9zaWdhLCB0eXBlPSdsJywgeGxpbT1jKDAsIDAuNCksIHlsaW09YygwLCA0NSksIGNvbD0iIzQyZTBmNSIsIGx3ZCA9IDMsIHhsYWI9JycsIHlsYWI9JycsIG1haW49JycpCnBhcihuZXc9VFJVRSkKYWJsaW5lKHhsaW09YygwLCAwLjQpLCB5bGltPWMoMCwgMjApLCB2PTAuMDYsIGNvbD1hbHBoYSgiIzQyZTBmNSIsIDAuNSksIGx3ZD0yKQpwYXIobmV3PVRSVUUpCmFibGluZSh4bGltPWMoMCwgMC40KSwgeWxpbT1jKDAsIDIwKSwgdj0wLjAyLCBjb2w9YWxwaGEoImdyZWVuIiwgMC41KSwgbHdkPTIpCgpwbG90KHNiLCBhZ2VuYV9zaWdiLCB0eXBlPSJsIiwgeGxpbT1jKDAsIDAuNCksIHlsaW09YygwLCA0NSksIGNvbD0iZ3JlZW4iLCBsd2QgPSAzLCB4bGFiPScnLCBtYWluPWV4cHJlc3Npb24oc2lnbWFbYmV0YV0pLCB5bGFiPScnLCBjZXgubWFpbj0xLjUsIGZvbnQubWFpbiA9IDEpCnhsYWJlbCA8LSBzZXEoLTIsIDIsIGJ5ID0gMC4yKQpheGlzKDEsIGF0ID0geGxhYmVsLCBsYXMgPSAwLjIpCnBhcihuZXc9VFJVRSkKcGxvdChzYiwgcnN0YW5fc2lnYiwgdHlwZT0nbCcsIHhsaW09YygwLCAwLjQpLCB5bGltPWMoMCwgNDUpLCBjb2w9IiM0MmUwZjUiLCBsd2QgPSAzLCB4bGFiPScnLCB5bGFiPScnLCBtYWluPScnKQpwYXIobmV3PVRSVUUpCmFibGluZSh4bGltPWMoMCwgMC40KSwgeWxpbT1jKDAsIDIwKSwgdj0wLjA0LCBjb2w9YWxwaGEoIiM0MmUwZjUiLCAwLjUpLCBsd2Q9MikKcGFyKG5ldz1UUlVFKQphYmxpbmUoeGxpbT1jKDAsIDAuNCksIHlsaW09YygwLCAyMCksIHY9MC4wMSwgY29sPWFscGhhKCJncmVlbiIsIDAuNSksIGx3ZD0yKQpgYGAK