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