Apresentação
Bugs
Bayesian inference Using Gibbs Sampler ou ‘Inferência Bayesina utilizando o amostrador de Gibbs’, dorovante BUGS, é um projeto concebido na criação de um software flexível para análise de modelos estatísticos de alta complexidade, utilizando Markov Chain Monte Carlo como método. O projeto começou em 1989 sob a tutela de Spiegelhalter et al, na MCR Biostatistics Unit, em Camdribge, resultando o programa inicial denominado de BUGS. Furthermore, em um projeto conjunto com a Imperial College, Londres, foi desenvolvido o WinBugs, uma versão compatível com o R.
Posteriormente, foi apresentado ao público o OpenBUgs, uma versão acessível ao público geral e igualmente compatível com o R, assim como a versão anterior. Howerver, a produção de seu conteúdo foi encerrada em 2011, embora haja versões disponíveis até o presente dia. Atualmente, conta com mais de 30 mil downloas de usuários e uma interface gráfica única.
Em 2018, Goudie el at desenvolveram o projeto MultiBugs, que oferece um algoritmo em computação parelala, objetivando a compilação rápida de modelos mais robustos.
Jags
Just Another Gibbs Sampler (JAGS), ou Apenas Outro amostra de Gibbs, é um software ao moldes do GIBS, apresentado anteriormente, criado sob as mesmas premissas e com o mesmo objetivo, Inferência Bayesiana via MCMC. Para além das similaridades mencionadas, o JAGS é mais flexível, se comparado com o GIBS, no que tange a interconectividade com outros softwares estatísticos, em especial, o R.
Desenvolvido por Martyn Plummer, é consideravelmente mais recente que o projeto anterior e sua última atualização data de 2017. Embora, assim como o BUGS, é necessário que o compilador esteja atuando em concomitância com o R, ou seja, não há independência. O JAGS é de uso livre e licensiado sob a GNU General Public License.
Stan
Stan é pacote estatístico com o objetivo de realizar inferência bayesiana sob a ótica do MCMC. Desenvolvido por Gelman, Carpenter e um time de 34 pesquisados, o programa é uma homenagem ao pinoeiro do método de Monte Carlo e físico responsável pela descoberta da fissão atômica, Stanislaw Ulam, um dos membros do projeto Manhattam. É licensiado pela New BDS License, sendo de origem recente, produzido em 2012, conta com atualização e feedback de sua equipe até o presente dia.
Em suma, as diferenças para o JAGS e o BUGS consta na compilação do modelo, os primeiros, mais simples, seguem o mesmo padrão. O Stan, por sua vez, adotou uma linguagem C++ para a escrita da modelagem. O seu diferencial está em seus algoritmos, sendo o Hamiltonian Monte Carlo (HMC) (default) e o No U turner sampler (NUTS), alternativo ao primeiro.
Nimble
O nimble é sistema integrado ao R, em formato de pacote, desenvolvido por uma pesquisa colaborativa entre P de Valpine, C Paciorek e D Temple Lang. Tem como objetivo principal a difusão da análise e cômputo de modelos de alta dimensionalidade, ou computacionalmente intensivos, em especial os modelos hierárquicos. O compilador utiliza-se da linguagem do BUGS, já bem definida pela comunidade, ademias, seus rotinas internas são integradas em C++ para ganhos de velocidade.
Embora seja considerado um compilador User Friendly para MCMC, o Nimble possui outras ferramentas. Há a possiblidade também de escrever modelos Bayesianos Não Paramétricos (BNP) de modelos de mistura e estimação de densidade não paramétrica via processo de mistura Dirichlet.
Dados
######################################################################################
# SIMULAÇÃO DOS DADOS #
######################################################################################
set.seed(123)
#Parâmetros verdadeiros
beta0=-2
beta1=2
beta2=10
sigma2=5
n=100
tau=1/sigma2
#Geração
x1=rnorm(n,0,1)
x2=rnorm(n,2,10)
e=rnorm(n,0, sd = sqrt(sigma2))
y=beta0+beta1*x1+beta2*x2+e
BUGS
Código
######################################################################################
# BUGS #
######################################################################################
#Modelo do tipo BUGS
sink("mod1.txt")
cat("
MODEL LR1 {
#Verossimilhança
for(i in 1:N) {
y[i] ~ dnorm(mu[i], tau)
mu[i] <- beta0 + beta1*x1[i] + beta2*x2[i]
}
#Proris
beta0 ~ dnorm(0,0.1)
beta1 ~ dnorm(0,0.1)
beta2 ~ dnorm(0,0.1)
tau ~ dgamma(1,0.1)
#Transformação para variância
sigma2 <- 1/tau
} ", fill = TRUE)
sink()
#Obeservação: A dist normal no bugs está definido para a precisão.
#Tamanho amostral
N = length(y)
#Conjunto de dados observados
data = list("N","y","x1","x2")
#Parâmetros estudados
params = c("beta0", "beta1","beta2","tau","sigma2")
#Valores iniciais
inits <- function () {list(beta0 = rnorm(1),
beta1 = rnorm(1),
beta2 = rnorm(1),
tau = 1)
sigma2 = 1}
#Modelo final
tic()
result <- bugs(data = data, inits = inits, parameters.to.save = params,
model.file = "mod1.txt", n.chains = 3, n.iter = 10000,
n.burnin = 1000, n.thin=9, bugs.directory = "C:\\Program Files\\WinBUGS14",
debug = TRUE, save.history = TRUE, DIC = FALSE)
toc()
Resultados
| |
mean |
sd |
2.5% |
25% |
50% |
75% |
97.5% |
Rhat |
n.eff |
| beta0 |
-1.7017525 |
0.2174842 |
-2.1550000 |
-1.84525 |
-1.70400 |
-1.554000 |
-1.279975 |
1.002923 |
830 |
| beta1 |
1.6939550 |
0.2304004 |
1.2440000 |
1.53975 |
1.69900 |
1.845000 |
2.144000 |
1.001317 |
2400 |
| beta2 |
10.0042037 |
0.0220753 |
9.9620000 |
9.98900 |
10.00000 |
10.020000 |
10.050000 |
1.000688 |
3000 |
| tau |
0.2250701 |
0.0327324 |
0.1658975 |
0.20160 |
0.22385 |
0.246025 |
0.293710 |
1.000817 |
3000 |
| sigma2 |
4.5387863 |
0.6724222 |
3.4048749 |
4.06400 |
4.46750 |
4.959250 |
6.026150 |
1.000817 |
3000 |


JAGS
Código
######################################################################################
# JAGS #
######################################################################################
model_code = 'model{
#Verossimilhança
for(i in 1:N) {
y[i] ~ dnorm(mu[i], tau)
mu[i] <- beta0 + beta1*x1[i] + beta2*x2[i]
}
#Proris
beta0 ~ dnorm(0,0.1)
beta1 ~ dnorm(0,0.1)
beta2 ~ dnorm(0,0.1)
tau ~ dgamma(1,0.1)
#Transformação para variância
sigma2 <- 1/tau}'
N = length(y)
model_data = list(N = N, y = y, x1 = x1, x2 = x2)
model_parameters = c("beta0", "beta1","beta2", "sigma2","tau")
tic()
model_run = jags(data = model_data,
parameters.to.save = model_parameters,
model.file=textConnection(model_code),
n.chains=3, # Number of different starting positions
n.iter=10000, # Number of iterations
n.burnin=1000, # Number of iterations to remove at start
n.thin=9,# Amount of thinning
DIC=FALSE)
toc()
Resultados
| |
mean |
sd |
2.5% |
25% |
50% |
75% |
97.5% |
Rhat |
n.eff |
| beta0 |
-1.6860944 |
0.2105909 |
-2.0879681 |
-1.8296104 |
-1.687723 |
-1.5483238 |
-1.266608 |
1.000977 |
3000 |
| beta1 |
1.6909286 |
0.2311049 |
1.2313686 |
1.5387469 |
1.688274 |
1.8493560 |
2.144819 |
1.000647 |
3000 |
| beta2 |
10.0052898 |
0.0219353 |
9.9620366 |
9.9905397 |
10.005205 |
10.0198417 |
10.048766 |
1.001766 |
1600 |
| sigma2 |
4.5186170 |
0.6587993 |
3.4324159 |
4.0422921 |
4.452478 |
4.9056101 |
5.975496 |
1.000686 |
3000 |
| tau |
0.2258834 |
0.0320833 |
0.1673501 |
0.2038482 |
0.224594 |
0.2473844 |
0.291340 |
1.000686 |
3000 |


STAN
Código
######################################################################################
# STAN #
######################################################################################
model = "data {
int<lower=1> N;
vector[N] y;
vector[N] x1;
vector[N] x2;
}
parameters {
real alpha;
real beta1;
real beta2;
real<lower=0> sigma2;
}
model {
alpha ~ normal(0, 10);
beta1 ~ normal(0, 10);
beta2 ~ normal(0, 10);
sigma2 ~ inv_gamma(3,20);
y ~ normal(alpha + beta1 * x1 + beta2*x2, sqrt(sigma2));
}
generated quantities {
vector[N] y_rep;
for(n in 1:N) {
y_rep[n] = normal_rng(alpha + beta1 * x1[n] + beta2*x2[n], sqrt(sigma2));
}
}"
data <- list(y = y, x1 = x1, x2 = x2 , N = 100)
tic()
fit <- stan(model_code = model,
data = data, iter = 10000, warmup = 1000, chains = 3)
stan = extract(fit)
toc()
Resultados
| |
mean |
se_mean |
sd |
2.5% |
25% |
50% |
75% |
97.5% |
n_eff |
Rhat |
| alpha |
-1.705771 |
0.0013234 |
0.2187635 |
-2.138415 |
-1.851237 |
-1.704914 |
-1.559763 |
-1.276514 |
27325.03 |
0.9999686 |
| beta1 |
1.699761 |
0.0014114 |
0.2395953 |
1.228784 |
1.540529 |
1.698885 |
1.861845 |
2.168289 |
28818.32 |
0.9999350 |
| beta2 |
10.005224 |
0.0001332 |
0.0225257 |
9.961374 |
9.990201 |
10.005070 |
10.020402 |
10.049088 |
28582.34 |
0.9999602 |
| sigma2 |
4.745150 |
0.0041508 |
0.6696007 |
3.614317 |
4.275004 |
4.679747 |
5.153950 |
6.223051 |
26024.15 |
1.0000428 |
|
| |
mean.chain:1 |
sd.chain:1 |
2.5%.chain:1 |
25%.chain:1 |
50%.chain:1 |
75%.chain:1 |
97.5%.chain:1 |
mean.chain:2 |
sd.chain:2 |
2.5%.chain:2 |
25%.chain:2 |
50%.chain:2 |
75%.chain:2 |
97.5%.chain:2 |
mean.chain:3 |
sd.chain:3 |
2.5%.chain:3 |
25%.chain:3 |
50%.chain:3 |
75%.chain:3 |
97.5%.chain:3 |
| alpha |
-1.704459 |
0.2182247 |
-2.134405 |
-1.845417 |
-1.702805 |
-1.560221 |
-1.272177 |
-1.708991 |
0.2205426 |
-2.143654 |
-1.856214 |
-1.707929 |
-1.561689 |
-1.281975 |
-1.703863 |
0.2175001 |
-2.132866 |
-1.852140 |
-1.704202 |
-1.557887 |
-1.279405 |
| beta1 |
1.698571 |
0.2366761 |
1.234933 |
1.541722 |
1.696640 |
1.857513 |
2.164830 |
1.701441 |
0.2444538 |
1.217817 |
1.537478 |
1.701037 |
1.868434 |
2.175044 |
1.699270 |
0.2375979 |
1.229826 |
1.541493 |
1.699162 |
1.860382 |
2.159939 |
| beta2 |
10.005271 |
0.0223819 |
9.961223 |
9.990564 |
10.005212 |
10.020494 |
10.048512 |
10.005315 |
0.0224908 |
9.961959 |
9.990279 |
10.004997 |
10.020309 |
10.049125 |
10.005086 |
0.0227050 |
9.960872 |
9.989856 |
10.004952 |
10.020399 |
10.049404 |
| sigma2 |
4.739498 |
0.6709983 |
3.616892 |
4.267374 |
4.665881 |
5.148719 |
6.239155 |
4.746080 |
0.6703198 |
3.616933 |
4.276826 |
4.680797 |
5.153938 |
6.220253 |
4.749871 |
0.6675122 |
3.603574 |
4.279996 |
4.692062 |
5.159586 |
6.208506 |
|


NIMBLE
Código
######################################################################################
# NIMBLE #
######################################################################################
simpleCode1 <- nimbleCode({
beta0 ~ dnorm(0,0.1)
beta1 ~ dnorm(0,0.1)
beta2 ~ dnorm(0,0.1)
tau ~ dgamma(1, 0.1)
sigma2 <- 1/tau
for(i in 1:N) {
Ypred[i] <- beta0 + beta1 * x1[i] + beta2*x2[i]
Y[i] ~ dnorm(Ypred[i], tau)
}
})
simpleModel1 <- nimbleModel(simpleCode1,
data = list(Y = y, x1 = x1,x2=x2),
constants = list(N = N),
inits = list(beta0 = 0, beta1 = 0,beta2=0, tau = 2 ))
tic()
mcmc.out <- nimbleMCMC(code = simpleModel1,
data = list(Y = y, x1 = x1,x2=x2),
inits = list(beta0 = 0, beta1 = 0,beta2=0, tau = 2),
monitors=c("beta0","beta1","beta2","tau","sigma2"),
nchains = 3,
niter = 10000,
thin = 9,
nburnin = 1000,
summary = TRUE,
progressBar = TRUE)
toc()
Resultados
| |
Mean |
Median |
St.Dev. |
95%CI_low |
95%CI_upp |
| beta0 |
-1.7041573 |
-1.7083052 |
0.2091917 |
-2.1043706 |
-1.2794896 |
| beta1 |
1.6974375 |
1.7005161 |
0.2272487 |
1.2548992 |
2.1237661 |
| beta2 |
10.0050927 |
10.0049245 |
0.0223281 |
9.9638410 |
10.0516948 |
| sigma2 |
4.5113108 |
4.4523352 |
0.6241347 |
3.4605394 |
5.9630216 |
| tau |
0.2258069 |
0.2246013 |
0.0304566 |
0.1677002 |
0.2889724 |
|
| |
Mean |
Median |
St.Dev. |
95%CI_low |
95%CI_upp |
| beta0 |
-1.6968087 |
-1.6944266 |
0.2076834 |
-2.0947722 |
-1.2962685 |
| beta1 |
1.6877346 |
1.6932318 |
0.2321149 |
1.2386992 |
2.1394175 |
| beta2 |
10.0043223 |
10.0043528 |
0.0223773 |
9.9611573 |
10.0475828 |
| sigma2 |
4.4939257 |
4.4264768 |
0.6632215 |
3.4387254 |
5.9387300 |
| tau |
0.2272029 |
0.2259133 |
0.0323686 |
0.1683862 |
0.2908054 |
|
| |
Mean |
Median |
St.Dev. |
95%CI_low |
95%CI_upp |
| beta0 |
-1.6928879 |
-1.6885632 |
0.2167004 |
-2.102350 |
-1.270194 |
| beta1 |
1.6852116 |
1.6877019 |
0.2381134 |
1.216738 |
2.150423 |
| beta2 |
10.0055725 |
10.0063789 |
0.0221097 |
9.962371 |
10.049552 |
| sigma2 |
4.5020546 |
4.4327260 |
0.6709563 |
3.398402 |
6.061527 |
| tau |
0.2268949 |
0.2255948 |
0.0327657 |
0.164975 |
0.294256 |
|
| |
Mean |
Median |
St.Dev. |
95%CI_low |
95%CI_upp |
| beta0 |
-1.6979513 |
-1.6964828 |
0.2112099 |
-2.1021654 |
-1.2796220 |
| beta1 |
1.6901279 |
1.6935095 |
0.2325170 |
1.2372259 |
2.1414415 |
| beta2 |
10.0049958 |
10.0049545 |
0.0222705 |
9.9622690 |
10.0492859 |
| sigma2 |
4.5024303 |
4.4367283 |
0.6529133 |
3.4376043 |
5.9920623 |
| tau |
0.2266349 |
0.2253913 |
0.0318745 |
0.1668875 |
0.2909003 |
|


Comparativo entre os tempos
Pacote utilizado: tictoc
| |
Tempo em Segundos (Arredondado) |
| Bugs |
6 |
| Jags |
2 |
| Stan |
8 |
| Nimble |
30 |
LS0tDQp0aXRsZTogIkNvbXBhcmHn428gZW50cmUgb3MgcGFjb3RlcyBkZSBNQ01DIg0KYXV0aG9yOiAiUmFmYWVsIENhYnJhbCBGZXJuYW5kZXoiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KPGJyPg0KDQojQXByZXNlbnRh5+NvDQo8YnI+DQo8YnI+DQoNCiMjQnVncw0KQmF5ZXNpYW4gaW5mZXJlbmNlIFVzaW5nIEdpYmJzIFNhbXBsZXIgb3UgJ0luZmVy6m5jaWEgQmF5ZXNpbmEgdXRpbGl6YW5kbyBvIGFtb3N0cmFkb3IgZGUgR2liYnMnLCBkb3JvdmFudGUgQlVHUywg6SB1bSBwcm9qZXRvIGNvbmNlYmlkbyBuYSBjcmlh5+NvIGRlIHVtIHNvZnR3YXJlIGZsZXjtdmVsIHBhcmEgYW7hbGlzZSBkZSBtb2RlbG9zIGVzdGF07XN0aWNvcyBkZSBhbHRhIGNvbXBsZXhpZGFkZSwgdXRpbGl6YW5kbyBNYXJrb3YgQ2hhaW4gTW9udGUgQ2FybG8gY29tbyBt6XRvZG8uIE8gcHJvamV0byBjb21l5291IGVtIDE5ODkgc29iIGEgdHV0ZWxhIGRlIFNwaWVnZWxoYWx0ZXIgZXQgYWwsIG5hIE1DUiBCaW9zdGF0aXN0aWNzIFVuaXQsIGVtIENhbWRyaWJnZSwgcmVzdWx0YW5kbyBvIHByb2dyYW1hIGluaWNpYWwgZGVub21pbmFkbyBkZSBCVUdTLiBGdXJ0aGVybW9yZSwgZW0gdW0gcHJvamV0byBjb25qdW50byBjb20gYSBJbXBlcmlhbCBDb2xsZWdlLCBMb25kcmVzLCBmb2kgZGVzZW52b2x2aWRvIG8gV2luQnVncywgdW1hIHZlcnPjbyBjb21wYXTtdmVsIGNvbSBvIFIuIA0KDQpQb3N0ZXJpb3JtZW50ZSwgZm9pIGFwcmVzZW50YWRvIGFvIHD6YmxpY28gbyBPcGVuQlVncywgdW1hIHZlcnPjbyBhY2Vzc+12ZWwgYW8gcPpibGljbyBnZXJhbCBlIGlndWFsbWVudGUgY29tcGF07XZlbCBjb20gbyBSLCBhc3NpbSBjb21vIGEgdmVyc+NvIGFudGVyaW9yLiBIb3dlcnZlciwgYSBwcm9kdefjbyBkZSBzZXUgY29udGX6ZG8gZm9pICBlbmNlcnJhZGEgZW0gMjAxMSwgZW1ib3JhIGhhamEgdmVyc/VlcyBkaXNwb27tdmVpcyBhdOkgbyBwcmVzZW50ZSBkaWEuIEF0dWFsbWVudGUsIGNvbnRhIGNvbSBtYWlzIGRlIDMwIG1pbCBkb3dubG9hcyBkZSB1c3XhcmlvcyBlIHVtYSBpbnRlcmZhY2UgZ3LhZmljYSD6bmljYS4gDQoNCkVtIDIwMTgsIEdvdWRpZSBlbCBhdCBkZXNlbnZvbHZlcmFtIG8gcHJvamV0byBNdWx0aUJ1Z3MsIHF1ZSBvZmVyZWNlIHVtIGFsZ29yaXRtbyBlbSBjb21wdXRh5+NvIHBhcmVsYWxhLCBvYmpldGl2YW5kbyBhIGNvbXBpbGHn428gcuFwaWRhIGRlIG1vZGVsb3MgbWFpcyByb2J1c3Rvcy4NCjxicj4NCg0KIyNKYWdzDQpKdXN0IEFub3RoZXIgR2liYnMgU2FtcGxlciAoSkFHUyksIG91IEFwZW5hcyBPdXRybyBhbW9zdHJhIGRlIEdpYmJzLCDpIHVtIHNvZnR3YXJlIGFvIG1vbGRlcyBkbyBHSUJTLCBhcHJlc2VudGFkbyBhbnRlcmlvcm1lbnRlLCBjcmlhZG8gc29iIGFzIG1lc21hcyBwcmVtaXNzYXMgZSBjb20gbyBtZXNtbyBvYmpldGl2bywgSW5mZXLqbmNpYSBCYXllc2lhbmEgdmlhIE1DTUMuIFBhcmEgYWzpbSBkYXMgc2ltaWxhcmlkYWRlcyBtZW5jaW9uYWRhcywgbyBKQUdTIOkgbWFpcyBmbGV47XZlbCwgc2UgY29tcGFyYWRvIGNvbSBvIEdJQlMsIG5vIHF1ZSB0YW5nZSBhIGludGVyY29uZWN0aXZpZGFkZSBjb20gb3V0cm9zIHNvZnR3YXJlcyBlc3RhdO1zdGljb3MsIGVtIGVzcGVjaWFsLCBvIFIuDQoNCkRlc2Vudm9sdmlkbyBwb3IgTWFydHluIFBsdW1tZXIsIOkgY29uc2lkZXJhdmVsbWVudGUgbWFpcyByZWNlbnRlIHF1ZSBvIHByb2pldG8gYW50ZXJpb3IgZSBzdWEg+mx0aW1hIGF0dWFsaXph5+NvIGRhdGEgZGUgMjAxNy4gRW1ib3JhLCBhc3NpbSBjb21vIG8gQlVHUywg6SBuZWNlc3PhcmlvIHF1ZSBvIGNvbXBpbGFkb3IgZXN0ZWphIGF0dWFuZG8gZW0gY29uY29taXTibmNpYSBjb20gbyBSLCBvdSBzZWphLCBu428gaOEgaW5kZXBlbmTqbmNpYS4gTyBKQUdTIOkgZGUgdXNvIGxpdnJlIGUgbGljZW5zaWFkbyBzb2IgYSBHTlUgR2VuZXJhbCBQdWJsaWMgTGljZW5zZS4NCjxicj4NCg0KIyNTdGFuDQpTdGFuIOkgcGFjb3RlIGVzdGF07XN0aWNvIGNvbSBvIG9iamV0aXZvIGRlIHJlYWxpemFyIGluZmVy6m5jaWEgYmF5ZXNpYW5hIHNvYiBhIPN0aWNhIGRvIE1DTUMuIERlc2Vudm9sdmlkbyBwb3IgR2VsbWFuLCBDYXJwZW50ZXIgZSB1bSB0aW1lIGRlIDM0IHBlc3F1aXNhZG9zLCBvIHByb2dyYW1hIOkgdW1hIGhvbWVuYWdlbSBhbyBwaW5vZWlybyBkbyBt6XRvZG8gZGUgTW9udGUgQ2FybG8gZSBm7XNpY28gcmVzcG9uc+F2ZWwgcGVsYSBkZXNjb2JlcnRhIGRhIGZpc3PjbyBhdPRtaWNhLCBTdGFuaXNsYXcgVWxhbSwgdW0gZG9zIG1lbWJyb3MgZG8gcHJvamV0byBNYW5oYXR0YW0uIMkgbGljZW5zaWFkbyBwZWxhIE5ldyBCRFMgTGljZW5zZSwgc2VuZG8gZGUgb3JpZ2VtIHJlY2VudGUsIHByb2R1emlkbyBlbSAyMDEyLCBjb250YSBjb20gYXR1YWxpemHn428gZSBmZWVkYmFjayBkZSBzdWEgZXF1aXBlIGF06SBvIHByZXNlbnRlIGRpYS4NCg0KRW0gc3VtYSwgYXMgZGlmZXJlbudhcyBwYXJhIG8gSkFHUyBlIG8gQlVHUyBjb25zdGEgbmEgY29tcGlsYefjbyBkbyBtb2RlbG8sIG9zIHByaW1laXJvcywgbWFpcyBzaW1wbGVzLCBzZWd1ZW0gbyBtZXNtbyBwYWRy428uIE8gU3RhbiwgcG9yIHN1YSB2ZXosIGFkb3RvdSB1bWEgbGluZ3VhZ2VtIEMrKyBwYXJhIGEgZXNjcml0YSBkYSBtb2RlbGFnZW0uIE8gc2V1IGRpZmVyZW5jaWFsIGVzdOEgZW0gc2V1cyBhbGdvcml0bW9zLCBzZW5kbyBvIEhhbWlsdG9uaWFuIE1vbnRlIENhcmxvIChITUMpIChkZWZhdWx0KSBlIG8gTm8gVSB0dXJuZXIgc2FtcGxlciAoTlVUUyksIGFsdGVybmF0aXZvIGFvIHByaW1laXJvLiANCg0KPGJyPg0KDQojI05pbWJsZQ0KDQpPIG5pbWJsZSDpIHNpc3RlbWEgaW50ZWdyYWRvIGFvIFIsIGVtIGZvcm1hdG8gZGUgcGFjb3RlLCBkZXNlbnZvbHZpZG8gcG9yIHVtYSBwZXNxdWlzYSBjb2xhYm9yYXRpdmEgZW50cmUgUCBkZSBWYWxwaW5lLCBDIFBhY2lvcmVrIGUgRCBUZW1wbGUgTGFuZy4gVGVtIGNvbW8gb2JqZXRpdm8gcHJpbmNpcGFsIGEgZGlmdXPjbyBkYSBhbuFsaXNlIGUgY/RtcHV0byBkZSBtb2RlbG9zIGRlIGFsdGEgZGltZW5zaW9uYWxpZGFkZSwgb3UgY29tcHV0YWNpb25hbG1lbnRlIGludGVuc2l2b3MsIGVtIGVzcGVjaWFsIG9zIG1vZGVsb3MgaGllcuFycXVpY29zLiBPIGNvbXBpbGFkb3IgdXRpbGl6YS1zZSBkYSBsaW5ndWFnZW0gZG8gQlVHUywgauEgYmVtIGRlZmluaWRhIHBlbGEgY29tdW5pZGFkZSwgYWRlbWlhcywgc2V1cyByb3RpbmFzIGludGVybmFzIHPjbyBpbnRlZ3JhZGFzIGVtIEMrKyBwYXJhIGdhbmhvcyBkZSB2ZWxvY2lkYWRlLiANCg0KRW1ib3JhIHNlamEgY29uc2lkZXJhZG8gdW0gY29tcGlsYWRvciBVc2VyIEZyaWVuZGx5IHBhcmEgTUNNQywgbyBOaW1ibGUgcG9zc3VpIG91dHJhcyBmZXJyYW1lbnRhcy4gSOEgYSBwb3NzaWJsaWRhZGUgdGFtYultIGRlIGVzY3JldmVyIG1vZGVsb3MgQmF5ZXNpYW5vcyBO428gUGFyYW3pdHJpY29zIChCTlApIGRlIG1vZGVsb3MgZGUgbWlzdHVyYSBlIGVzdGltYefjbyBkZSBkZW5zaWRhZGUgbuNvIHBhcmFt6XRyaWNhIHZpYSBwcm9jZXNzbyBkZSBtaXN0dXJhIERpcmljaGxldC4gDQoNCjxicj4NCjxicj4NCg0KIyNEYWRvcw0KYGBge3J9DQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgU0lNVUxBx8NPIERPUyBEQURPUyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQoNCnNldC5zZWVkKDEyMykNCg0KI1BhcuJtZXRyb3MgdmVyZGFkZWlyb3MNCmJldGEwPS0yDQpiZXRhMT0yDQpiZXRhMj0xMA0Kc2lnbWEyPTUNCm49MTAwDQp0YXU9MS9zaWdtYTINCg0KI0dlcmHn428NCngxPXJub3JtKG4sMCwxKQ0KeDI9cm5vcm0obiwyLDEwKQ0KZT1ybm9ybShuLDAsIHNkID0gc3FydChzaWdtYTIpKQ0KeT1iZXRhMCtiZXRhMSp4MStiZXRhMip4MitlDQoNCg0KYGBgDQo8YnI+DQoNCiNCVUdTDQoNCg0KYGBge3IsIHdhcm5pbmc9IEZBTFNFLCBtZXNzYWdlPSBGQUxTRSxlY2hvPUZBTFNFfQ0KbGlicmFyeSgiUjJXaW5CVUdTIikNCmxpYnJhcnkoIlIyamFncyIpDQpsaWJyYXJ5KCJyc3RhbiIpDQpsaWJyYXJ5KCJuaW1ibGUiKQ0KbGlicmFyeSgiYm9hIikNCmxpYnJhcnkoImNvZGEiKQ0KbGlicmFyeSgieHRhYmxlIikNCmxpYnJhcnkoImthYmxlRXh0cmEiKQ0KbGlicmFyeSgidGljdG9jIikNCmBgYA0KDQojI0PzZGlnbw0KYGBge3IsZXZhbD1GQUxTRSx3YXJuaW5nPUZBTFNFfQ0KDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEJVR1MgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQoNCiNNb2RlbG8gZG8gdGlwbyBCVUdTDQpzaW5rKCJtb2QxLnR4dCIpICAgICAgICANCmNhdCgiDQogICAgTU9ERUwgTFIxIHsNCg0KICAgICNWZXJvc3NpbWlsaGFu52EgDQogICAgZm9yKGkgaW4gMTpOKSB7DQogICAgeVtpXSB+IGRub3JtKG11W2ldLCB0YXUpDQogICAgbXVbaV0gPC0gYmV0YTAgKyBiZXRhMSp4MVtpXSArIGJldGEyKngyW2ldDQogICAgfQ0KDQogICAgI1Byb3Jpcw0KICAgIGJldGEwIH4gZG5vcm0oMCwwLjEpDQogICAgYmV0YTEgfiBkbm9ybSgwLDAuMSkNCiAgICBiZXRhMiB+IGRub3JtKDAsMC4xKQ0KICAgIHRhdSB+IGRnYW1tYSgxLDAuMSkNCiAgICANCiAgICAjVHJhbnNmb3JtYefjbyBwYXJhIHZhcmnibmNpYQ0KICAgIHNpZ21hMiA8LSAxL3RhdQ0KICAgIH0gIiwgZmlsbCA9IFRSVUUpDQpzaW5rKCkNCg0KI09iZXNlcnZh5+NvOiBBIGRpc3Qgbm9ybWFsIG5vIGJ1Z3MgZXN04SBkZWZpbmlkbyBwYXJhIGEgcHJlY2lz428uIA0KDQojVGFtYW5obyBhbW9zdHJhbA0KTiA9IGxlbmd0aCh5KQ0KDQojQ29uanVudG8gZGUgZGFkb3Mgb2JzZXJ2YWRvcw0KZGF0YSA9IGxpc3QoIk4iLCJ5IiwieDEiLCJ4MiIpDQoNCiNQYXLibWV0cm9zIGVzdHVkYWRvcw0KcGFyYW1zID0gYygiYmV0YTAiLCAiYmV0YTEiLCJiZXRhMiIsInRhdSIsInNpZ21hMiIpICANCg0KI1ZhbG9yZXMgaW5pY2lhaXMNCmluaXRzIDwtIGZ1bmN0aW9uICgpIHtsaXN0KGJldGEwID0gcm5vcm0oMSksDQogICAgICAgICAgICAgICAgICAgICAgICAgICBiZXRhMSA9IHJub3JtKDEpLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgYmV0YTIgPSBybm9ybSgxKSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgIHRhdSA9IDEpDQogICAgICAgICAgICAgICAgICAgICAgICAgICBzaWdtYTIgPSAxfQ0KDQojTW9kZWxvIGZpbmFsDQp0aWMoKQ0KcmVzdWx0IDwtIGJ1Z3MoZGF0YSA9IGRhdGEsIGluaXRzID0gaW5pdHMsIHBhcmFtZXRlcnMudG8uc2F2ZSA9IHBhcmFtcywNCiAgICAgICAgICAgICAgIG1vZGVsLmZpbGUgPSAibW9kMS50eHQiLCBuLmNoYWlucyA9IDMsIG4uaXRlciA9IDEwMDAwLA0KICAgICAgICAgICAgICAgbi5idXJuaW4gPSAxMDAwLCBuLnRoaW49OSwgYnVncy5kaXJlY3RvcnkgPSAiQzpcXFByb2dyYW0gRmlsZXNcXFdpbkJVR1MxNCIsDQogICAgICAgICAgICAgICBkZWJ1ZyA9IFRSVUUsIHNhdmUuaGlzdG9yeSA9IFRSVUUsIERJQyA9IEZBTFNFKQ0KdG9jKCkNCg0KYGBgDQo8YnI+DQoNCiMjUmVzdWx0YWRvcw0KYGBge3IsZWNobz1GQUxTRX0NCnJlc3VsdCRzdW1tYXJ5ICU+JQ0KICBrYWJsZSgpICU+JQ0KICBrYWJsZV9zdHlsaW5nKCkNCg0KYnVncyA9IHJlc3VsdCRzaW1zLmxpc3QNCmJ1Z3NfYjAgPSBidWdzJGJldGEwDQpidWdzX2IxID0gYnVncyRiZXRhMQ0KYnVnc19iMiA9IGJ1Z3MkYmV0YTINCmJ1Z3NfczIgPSBidWdzJHNpZ21hMg0KYnVnc190YXUgPSBidWdzJHRhdQ0KcGFyKG1mcm93PWMoMSw1KSkNCnBsb3QoYnVnc19iMCx0eXBlID0gImwiLG1haW49ZXhwcmVzc2lvbihiZXRhWzBdKSx5bGFiPSIiLA0KICAgICB4bGFiPSIiLGNleC5tYWluPTIpDQphYmxpbmUoaD0tMixjb2w9InJlZCIpDQpwbG90KGJ1Z3NfYjEsdHlwZSA9ICJsIixtYWluPWV4cHJlc3Npb24oYmV0YVsxXSkseWxhYj0iIiwNCiAgICAgeGxhYj0iIixjZXgubWFpbj0yKQ0KYWJsaW5lKGg9Mixjb2w9InJlZCIpDQpwbG90KGJ1Z3NfYjIsdHlwZSA9ICJsIixtYWluPWV4cHJlc3Npb24oYmV0YVsyXSkseWxhYj0iIiwNCiAgICAgeGxhYj0iIixjZXgubWFpbj0yKQ0KYWJsaW5lKGg9MTAsY29sPSJyZWQiKQ0KcGxvdChidWdzX3MyLHR5cGUgPSAibCIsbWFpbj1leHByZXNzaW9uKHNpZ21hXjIpLHlsYWI9IiIsDQogICAgIHhsYWI9IiIsY2V4Lm1haW49MikNCmFibGluZShoPTUsY29sPSJyZWQiKQ0KcGxvdChidWdzX3RhdSx0eXBlID0gImwiLG1haW49ZXhwcmVzc2lvbih0YXUpLHlsYWI9IiIsDQogICAgIHhsYWI9IiIsY2V4Lm1haW49MikNCmFibGluZShoPTEvNSxjb2w9InJlZCIpDQpwYXIobWZyb3c9YygxLDUpKQ0KZGVuc3Bsb3QoYXMubWNtYyhidWdzX2IwKSxtYWluPWV4cHJlc3Npb24oYmV0YVswXSkseGxhYj0iIix5bGFiPSIiLGNleC5tYWluPTIpDQpkZW5zcGxvdChhcy5tY21jKGJ1Z3NfYjEpLG1haW49ZXhwcmVzc2lvbihiZXRhWzFdKSx4bGFiPSIiLHlsYWI9IiIsY2V4Lm1haW49MikNCmRlbnNwbG90KGFzLm1jbWMoYnVnc19iMiksbWFpbj1leHByZXNzaW9uKGJldGFbMl0pLHhsYWI9IiIseWxhYj0iIixjZXgubWFpbj0yKQ0KZGVuc3Bsb3QoYXMubWNtYyhidWdzX3MyKSxtYWluPWV4cHJlc3Npb24oc2lnbWFeMikseGxhYj0iIix5bGFiPSIiLGNleC5tYWluPTIpDQpkZW5zcGxvdChhcy5tY21jKGJ1Z3NfdGF1KSxtYWluPWV4cHJlc3Npb24odGF1KSx4bGFiPSIiLHlsYWI9IiIsY2V4Lm1haW49MikNCg0KDQpgYGANCjxicj4NCg0KI0pBR1MNCg0KIyND82RpZ28NCmBgYHtyLGV2YWw9RkFMU0V9DQoNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQojICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgSkFHUyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIw0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCm1vZGVsX2NvZGUgPSAnbW9kZWx7DQogICAgI1Zlcm9zc2ltaWxoYW7nYSANCiAgICBmb3IoaSBpbiAxOk4pIHsNCiAgICB5W2ldIH4gZG5vcm0obXVbaV0sIHRhdSkNCiAgICBtdVtpXSA8LSBiZXRhMCArIGJldGExKngxW2ldICsgYmV0YTIqeDJbaV0NCiAgICB9DQoNCiAgICAjUHJvcmlzDQogICAgYmV0YTAgfiBkbm9ybSgwLDAuMSkNCiAgICBiZXRhMSB+IGRub3JtKDAsMC4xKQ0KICAgIGJldGEyIH4gZG5vcm0oMCwwLjEpDQogICAgdGF1IH4gZGdhbW1hKDEsMC4xKQ0KICAgIA0KICAgICNUcmFuc2Zvcm1h5+NvIHBhcmEgdmFyaeJuY2lhDQogICAgc2lnbWEyIDwtIDEvdGF1fScNCiAgDQpOID0gbGVuZ3RoKHkpDQoNCm1vZGVsX2RhdGEgPSBsaXN0KE4gPSBOLCB5ID0geSwgeDEgPSB4MSwgeDIgPSB4MikNCg0KbW9kZWxfcGFyYW1ldGVycyA9ICBjKCJiZXRhMCIsICJiZXRhMSIsImJldGEyIiwgInNpZ21hMiIsInRhdSIpDQoNCnRpYygpDQptb2RlbF9ydW4gPSBqYWdzKGRhdGEgPSBtb2RlbF9kYXRhLA0KICAgICAgICAgICAgICAgICBwYXJhbWV0ZXJzLnRvLnNhdmUgPSBtb2RlbF9wYXJhbWV0ZXJzLA0KICAgICAgICAgICAgICAgICBtb2RlbC5maWxlPXRleHRDb25uZWN0aW9uKG1vZGVsX2NvZGUpLA0KICAgICAgICAgICAgICAgICBuLmNoYWlucz0zLCAjIE51bWJlciBvZiBkaWZmZXJlbnQgc3RhcnRpbmcgcG9zaXRpb25zDQogICAgICAgICAgICAgICAgIG4uaXRlcj0xMDAwMCwgIyBOdW1iZXIgb2YgaXRlcmF0aW9ucw0KICAgICAgICAgICAgICAgICBuLmJ1cm5pbj0xMDAwLCAjIE51bWJlciBvZiBpdGVyYXRpb25zIHRvIHJlbW92ZSBhdCBzdGFydA0KICAgICAgICAgICAgICAgICBuLnRoaW49OSwjIEFtb3VudCBvZiB0aGlubmluZw0KICAgICAgICAgICAgICAgICBESUM9RkFMU0UpIA0KdG9jKCkNCg0KDQoNCmBgYA0KPGJyPg0KDQojI1Jlc3VsdGFkb3MNCmBgYHtyLGVjaG89RkFMU0V9DQptb2RlbF9ydW4kQlVHU291dHB1dCRzdW1tYXJ5ICU+JQ0KICBrYWJsZSgpICU+JQ0KICBrYWJsZV9zdHlsaW5nKCkNCg0KamFncyA9IG1vZGVsX3J1bltbIkJVR1NvdXRwdXQiXV1bWyJzaW1zLm1hdHJpeCJdXQ0KamFnc19iMCA9IGphZ3NbLDFdDQpqYWdzX2IxID0gamFnc1ssMl0NCmphZ3NfYjIgPSBqYWdzWywzXQ0KamFnc19zMiA9IGphZ3NbLDRdDQpqYWdzX3RhdSA9IGphZ3NbLDVdDQoNCnBhcihtZnJvdz1jKDEsNSkpDQpwbG90KGphZ3NfYjAsdHlwZSA9ICJsIixtYWluPWV4cHJlc3Npb24oYmV0YVswXSkseWxhYj0iIiwNCiAgICAgeGxhYj0iIixjZXgubWFpbj0yKQ0KYWJsaW5lKGg9YmV0YTAsY29sPSJyZWQiKQ0KcGxvdChqYWdzX2IxLHR5cGUgPSAibCIsbWFpbj1leHByZXNzaW9uKGJldGFbMV0pLHlsYWI9IiIsDQogICAgIHhsYWI9IiIsY2V4Lm1haW49MikNCmFibGluZShoPWJldGExLGNvbD0icmVkIikNCnBsb3QoYnVnc19iMix0eXBlID0gImwiLG1haW49ZXhwcmVzc2lvbihiZXRhWzJdKSx5bGFiPSIiLA0KICAgICB4bGFiPSIiLGNleC5tYWluPTIpDQphYmxpbmUoaD0xMCxjb2w9InJlZCIpDQpwbG90KGphZ3NfczIsdHlwZSA9ICJsIixtYWluPWV4cHJlc3Npb24oc2lnbWFeMikseWxhYj0iIiwNCiAgICAgeGxhYj0iIixjZXgubWFpbj0yKQ0KYWJsaW5lKGg9c2lnbWEyLGNvbD0icmVkIikNCnBsb3QoamFnc190YXUsdHlwZSA9ICJsIixtYWluPWV4cHJlc3Npb24odGF1KSx5bGFiPSIiLA0KICAgICB4bGFiPSIiLGNleC5tYWluPTIpDQphYmxpbmUoaD10YXUsY29sPSJyZWQiKQ0KDQoNCnBhcihtZnJvdz1jKDEsNSkpDQpkZW5zcGxvdChhcy5tY21jKGphZ3NfYjApLG1haW49ZXhwcmVzc2lvbihiZXRhWzBdKSx4bGFiPSIiLHlsYWI9IiIsY2V4Lm1haW49MikNCmRlbnNwbG90KGFzLm1jbWMoamFnc19iMSksbWFpbj1leHByZXNzaW9uKGJldGFbMV0pLHhsYWI9IiIseWxhYj0iIixjZXgubWFpbj0yKQ0KZGVuc3Bsb3QoYXMubWNtYyhidWdzX2IyKSxtYWluPWV4cHJlc3Npb24oYmV0YVsyXSkseGxhYj0iIix5bGFiPSIiLGNleC5tYWluPTIpDQpkZW5zcGxvdChhcy5tY21jKGphZ3NfczIpLG1haW49ZXhwcmVzc2lvbihzaWdtYV4yKSx4bGFiPSIiLHlsYWI9IiIsY2V4Lm1haW49MikNCmRlbnNwbG90KGFzLm1jbWMoamFnc190YXUpLG1haW49ZXhwcmVzc2lvbih0YXUpLHhsYWI9IiIseWxhYj0iIixjZXgubWFpbj0yKQ0KDQpgYGANCjxicj4NCg0KI1NUQU4NCg0KIyND82RpZ28NCmBgYHtyLGV2YWw9Rn0NCg0KDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFNUQU4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQoNCm1vZGVsID0gImRhdGEgew0KaW50PGxvd2VyPTE+IE47DQp2ZWN0b3JbTl0geTsNCnZlY3RvcltOXSB4MTsNCnZlY3RvcltOXSB4MjsNCn0NCnBhcmFtZXRlcnMgew0KcmVhbCBhbHBoYTsNCnJlYWwgYmV0YTE7DQpyZWFsIGJldGEyOw0KcmVhbDxsb3dlcj0wPiBzaWdtYTI7DQp9DQptb2RlbCB7DQphbHBoYSB+IG5vcm1hbCgwLCAxMCk7ICAgDQpiZXRhMSB+IG5vcm1hbCgwLCAxMCk7IA0KYmV0YTIgfiBub3JtYWwoMCwgMTApOw0Kc2lnbWEyIH4gaW52X2dhbW1hKDMsMjApOw0KeSB+IG5vcm1hbChhbHBoYSArIGJldGExICogeDEgKyBiZXRhMip4Miwgc3FydChzaWdtYTIpKTsNCn0NCg0KZ2VuZXJhdGVkIHF1YW50aXRpZXMgew0KdmVjdG9yW05dIHlfcmVwOw0KZm9yKG4gaW4gMTpOKSB7DQp5X3JlcFtuXSA9IG5vcm1hbF9ybmcoYWxwaGEgKyBiZXRhMSAqIHgxW25dICsgYmV0YTIqeDJbbl0sIHNxcnQoc2lnbWEyKSk7DQp9DQp9Ig0KDQoNCmRhdGEgPC0gbGlzdCh5ID0geSwgeDEgPSB4MSwgeDIgPSB4MiAsIE4gPSAxMDApDQoNCnRpYygpDQpmaXQgPC0gc3Rhbihtb2RlbF9jb2RlID0gbW9kZWwsDQogICAgICAgICAgICBkYXRhID0gZGF0YSwgaXRlciA9IDEwMDAwLCB3YXJtdXAgPSAxMDAwLCBjaGFpbnMgPSAzKQ0KDQpzdGFuID0gZXh0cmFjdChmaXQpDQp0b2MoKQ0KDQoNCg0KYGBgDQo8YnI+DQoNCiMjUmVzdWx0YWRvcw0KYGBge3IsZWNobz1GQUxTRX0NCnN1bW1hcnkoZml0LHByb2JzID0gYygwLjAyNSwgMC4yNSwgMC41MCwgMC43NSwgMC45NzUpLHBhcnM9YygiYWxwaGEiLCJiZXRhMSIsImJldGEyIiwic2lnbWEyIikpICU+JQ0KICBrYWJsZSgpICU+JQ0KICBrYWJsZV9zdHlsaW5nKCkNCg0Kc3Rhbl9iMCA9IHN0YW4kYWxwaGENCnN0YW5fYjEgPSBzdGFuJGJldGExDQpzdGFuX2IyID0gc3RhbiRiZXRhMg0Kc3Rhbl9zMiA9IHN0YW4kc2lnbWEyDQoNCg0KcGFyKG1mcm93PWMoMSw0KSkNCnBsb3Qoc3Rhbl9iMCx0eXBlID0gImwiLG1haW49ZXhwcmVzc2lvbihiZXRhWzBdKSx5bGFiPSIiLA0KICAgICB4bGFiPSIiLGNleC5tYWluPTIpDQphYmxpbmUoaD0tMixjb2w9InJlZCIpDQpwbG90KHN0YW5fYjEsdHlwZSA9ICJsIixtYWluPWV4cHJlc3Npb24oYmV0YVsxXSkseWxhYj0iIiwNCiAgICAgeGxhYj0iIixjZXgubWFpbj0yKQ0KYWJsaW5lKGg9Mixjb2w9InJlZCIpDQpwbG90KHN0YW5fYjIsdHlwZSA9ICJsIixtYWluPWV4cHJlc3Npb24oYmV0YVsyXSkseWxhYj0iIiwNCiAgICAgeGxhYj0iIixjZXgubWFpbj0yKQ0KYWJsaW5lKGg9MTAsY29sPSJyZWQiKQ0KcGxvdChzdGFuX3MyLHR5cGUgPSAibCIsbWFpbj1leHByZXNzaW9uKHNpZ21hXjIpLHlsYWI9IiIsDQogICAgIHhsYWI9IiIsY2V4Lm1haW49MikNCmFibGluZShoPTUsY29sPSJyZWQiKQ0KDQoNCnBhcihtZnJvdz1jKDEsNCkpDQpwbG90KGRlbnNpdHkoc3Rhbl9iMCksbWFpbj1leHByZXNzaW9uKGJldGFbMF0pLGNleC5tYWluPTIpDQpwbG90KGRlbnNpdHkoc3Rhbl9iMSksbWFpbj1leHByZXNzaW9uKGJldGFbMV0pLGNleC5tYWluPTIpDQpwbG90KGRlbnNpdHkoc3Rhbl9iMiksbWFpbj1leHByZXNzaW9uKGJldGFbMl0pLGNleC5tYWluPTIpDQpwbG90KGRlbnNpdHkoc3Rhbl9zMiksbWFpbj1leHByZXNzaW9uKHNpZ21hXjIpLGNleC5tYWluPTIpDQpgYGANCg0KPGJyPg0KDQojTklNQkxFDQoNCiMjQ/NkaWdvDQpgYGB7cixldmFsPUZBTFNFfQ0KDQoNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQojICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIE5JTUJMRSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KDQpzaW1wbGVDb2RlMSA8LSBuaW1ibGVDb2RlKHsNCiAgYmV0YTAgfiBkbm9ybSgwLDAuMSkNCiAgYmV0YTEgfiBkbm9ybSgwLDAuMSkNCiAgYmV0YTIgfiBkbm9ybSgwLDAuMSkNCiAgdGF1IH4gZGdhbW1hKDEsIDAuMSkNCiAgc2lnbWEyIDwtIDEvdGF1DQogIGZvcihpIGluIDE6Tikgew0KICAgIFlwcmVkW2ldIDwtIGJldGEwICsgYmV0YTEgKiB4MVtpXSArIGJldGEyKngyW2ldDQogICAgWVtpXSB+IGRub3JtKFlwcmVkW2ldLCB0YXUpDQogIH0NCn0pDQoNCg0KDQoNCg0Kc2ltcGxlTW9kZWwxIDwtIG5pbWJsZU1vZGVsKHNpbXBsZUNvZGUxLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRhdGEgPSBsaXN0KFkgPSB5LCB4MSA9IHgxLHgyPXgyKSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb25zdGFudHMgPSBsaXN0KE4gPSBOKSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbml0cyA9IGxpc3QoYmV0YTAgPSAwLCBiZXRhMSA9IDAsYmV0YTI9MCwgdGF1ID0gMiApKQ0KDQp0aWMoKQ0KbWNtYy5vdXQgPC0gbmltYmxlTUNNQyhjb2RlID0gc2ltcGxlTW9kZWwxLCANCiAgICAgICAgICAgICAgICAgICAgICAgZGF0YSA9IGxpc3QoWSA9IHksIHgxID0geDEseDI9eDIpLCANCiAgICAgICAgICAgICAgICAgICAgICAgaW5pdHMgPSBsaXN0KGJldGEwID0gMCwgYmV0YTEgPSAwLGJldGEyPTAsIHRhdSA9IDIpLA0KICAgICAgICAgICAgICAgICAgICAgICBtb25pdG9ycz1jKCJiZXRhMCIsImJldGExIiwiYmV0YTIiLCJ0YXUiLCJzaWdtYTIiKSwNCiAgICAgICAgICAgICAgICAgICAgICAgbmNoYWlucyA9IDMsIA0KICAgICAgICAgICAgICAgICAgICAgICBuaXRlciA9IDEwMDAwLA0KICAgICAgICAgICAgICAgICAgICAgICB0aGluID0gOSwNCiAgICAgICAgICAgICAgICAgICAgICAgbmJ1cm5pbiA9IDEwMDAsDQogICAgICAgICAgICAgICAgICAgICAgIHN1bW1hcnkgPSBUUlVFLCANCiAgICAgICAgICAgICAgICAgICAgICAgcHJvZ3Jlc3NCYXIgPSBUUlVFKQ0KdG9jKCkNCg0KYGBgDQo8YnI+DQoNCiMjUmVzdWx0YWRvcw0KYGBge3IsZWNobz1GQUxTRX0NCm1jbWMub3V0JHN1bW1hcnkgJT4lDQogIGthYmxlKCkgJT4lDQogIGthYmxlX3N0eWxpbmcoKQ0KDQpuaW1ibGVfYjAgPSBtY21jLm91dCRzYW1wbGVzJGNoYWluMVssMV0NCm5pbWJsZV9iMSA9IG1jbWMub3V0JHNhbXBsZXMkY2hhaW4xWywyXQ0KbmltYmxlX2IyID0gbWNtYy5vdXQkc2FtcGxlcyRjaGFpbjFbLDNdDQpudW1ibGVfczIgPSBtY21jLm91dCRzYW1wbGVzJGNoYWluMVssNF0NCm5pbWJsZV90YXUgPSBtY21jLm91dCRzYW1wbGVzJGNoYWluMVssNV0NCg0KDQpwYXIobWZyb3c9YygxLDUpKQ0KcGxvdChuaW1ibGVfYjAsdHlwZSA9ICJsIixtYWluPWV4cHJlc3Npb24oYmV0YVswXSkseWxhYj0iIiwNCiAgICAgeGxhYj0iIixjZXgubWFpbj0yKQ0KYWJsaW5lKGg9LTIsY29sPSJyZWQiKQ0KcGxvdChuaW1ibGVfYjEsdHlwZSA9ICJsIixtYWluPWV4cHJlc3Npb24oYmV0YVsxXSkseWxhYj0iIiwNCiAgICAgeGxhYj0iIixjZXgubWFpbj0yKQ0KYWJsaW5lKGg9Mixjb2w9InJlZCIpDQpwbG90KG5pbWJsZV9iMix0eXBlID0gImwiLG1haW49ZXhwcmVzc2lvbihiZXRhWzJdKSx5bGFiPSIiLA0KICAgICB4bGFiPSIiLGNleC5tYWluPTIpDQphYmxpbmUoaD0xMCxjb2w9InJlZCIpDQpwbG90KG51bWJsZV9zMix0eXBlID0gImwiLG1haW49ZXhwcmVzc2lvbihzaWdtYV4yKSx5bGFiPSIiLA0KICAgICB4bGFiPSIiLGNleC5tYWluPTIpDQphYmxpbmUoaD01LGNvbD0icmVkIikNCnBsb3QobmltYmxlX3RhdSx0eXBlID0gImwiLG1haW49ZXhwcmVzc2lvbih0YXUpLHlsYWI9IiIsDQogICAgIHhsYWI9IiIsY2V4Lm1haW49MikNCmFibGluZShoPTEvNSxjb2w9InJlZCIpDQoNCg0KcGFyKG1mcm93PWMoMSw1KSkNCnBsb3QoZGVuc2l0eShuaW1ibGVfYjApLG1haW49ZXhwcmVzc2lvbihiZXRhWzBdKSxjZXgubWFpbj0yKQ0KcGxvdChkZW5zaXR5KG5pbWJsZV9iMSksbWFpbj1leHByZXNzaW9uKGJldGFbMV0pLGNleC5tYWluPTIpDQpwbG90KGRlbnNpdHkobmltYmxlX2IyKSxtYWluPWV4cHJlc3Npb24oYmV0YVsyXSksY2V4Lm1haW49MikNCnBsb3QoZGVuc2l0eShudW1ibGVfczIpLG1haW49ZXhwcmVzc2lvbihzaWdtYV4yKSxjZXgubWFpbj0yKQ0KcGxvdChkZW5zaXR5KG5pbWJsZV90YXUpLG1haW49ZXhwcmVzc2lvbih0YXUpLGNleC5tYWluPTIpDQoNCmBgYA0KPGJyPg0KDQojI0NvbXBhcmF0aXZvIGVudHJlIG9zIHRlbXBvcw0KIyMjUGFjb3RlIHV0aWxpemFkbzogdGljdG9jDQoNCmBgYHtyLGVjaG89RkFMU0V9DQoNCnRlbXBvID0gcmJpbmQoIjYiLCIyIiwiOCIsIjMwIikNCnJvd25hbWVzKHRlbXBvKSA9IGMoIkJ1Z3MiLCJKYWdzIiwiU3RhbiIsIk5pbWJsZSIpDQpjb2xuYW1lcyh0ZW1wbykgPSBjKCJUZW1wbyBlbSBTZWd1bmRvcyAoQXJyZWRvbmRhZG8pIikNCg0KdGVtcG8gJT4lDQogIGthYmxlKCkgJT4lDQogIGthYmxlX3N0eWxpbmcoKQ0KYGBgDQoNCg0K