1 The dataset

The following pieces of explanatory text were taken from Jim Albert’s github page at https://bayesball.github.io/BOOK/bayesian-hierarchical-modeling.html. Particularly, Section 10.3 on Hierarchical Beta-Binomial Modeling, and Section 10.3.1 Example: Deaths after heart attack.

The New York State (NYS) Department of Health collects and releases data on mortality after Acute Myocardial Infarction (AMI), commonly known as a heart attack. Their 2015 report was the initial public data release by the NYS Department of Health on risk- adjusted mortality outcomes for AMI patients at hospitals across the state. We focus on 13 hospitals in Manhattan, New York City - Manhattan in 2015, with the goal of learning about the percentages of resulted deaths from heart attack for hospitals in this sample. Below we have the records for each hospital the number of heart attack cases, the corresponding number of resulted deaths, and their computed percentage of resulted deaths. NYP stands for New York Presbyterian.

y = c(4,1,18,7,24,16,6,19,15,13,25,11,4)
n = c(129,35,228,84,291,270,46,293,241,105,353,250,41)
K = length(y)
phat = y/n


par(mfrow=c(1,1))
plot(y/n,ylim=c(0,0.13),xlab="Number of cases per hospital",ylab="Proportion of death",pch=16,cex=1.5,axes=FALSE)
axis(2);axis(1,at=1:13,label=n);box()
text(1:13,rep(0,13),y)
abline(h=sum(y)/sum(n),col=6)

Treating “cases” as trials and “deaths” as successes, the Binomial sampling model is a natural choice for this data, and the objective is to learn about the death probability \(p\) of the hospitals. If one looks at the actual death percentages, some hospitals have much higher death rates than other hospitals. For example, the highest death rate belongs to Mount Sinai Roosevelt, at 13.043% which is more than four times the rate of Harlem Hospital Center at 2.857%.

  1. Pooling the data from the 13 hospitals: If one assumes a common probability p for all 13 hospitals, this model does not allow for possible differences between the death rates among these hospitals.

  2. Analysing each hospital separately: If one creates 13 separate Binomial sampling models, one for each hospital, and conducts separate inferences, one loses the ability to use potential information about the death rate from hospital \(j\) when making inference about that of a different hospital \(i\). Since these are all hospitals in Manhattan, New York City, they may share attributes in common related to death rates from heart attack. The separate modeling approach does not allow for the sharing of information across hospitals.

  3. Hierarchical modeling A hierarchical model provides a compromise between the combined and separate modeling approaches. In this setting, one builds a hierarchical model by assuming the hospital death rate parameters a priori come from a common distribution. Specifically, one builds a hierarchical model based on a common Beta distribution that generalizes the Beta-Binomial conjugate model. This modeling setup provides posterior estimates that partially pool information among hospitals.

2 The STAN file

Save the following chunck of code into a stan file named, for instance, “hierarchical-beta-binomial.stan”.

data {
  int<lower=1> K;               // number of observations
  int<lower=0> y[K];            // successes
  int<lower=0> n[K];            // trials
  real<lower=0> n1;             // fixed constant for eta prior
}

parameters {
  real<lower=0,upper=1> mu;     // mean parameter of Beta
  real<lower=0> eta;            // precision parameter (a+b)
  vector<lower=0,upper=1>[K] p; // individual probabilities
}

model {
  // ---- Prior for mu ----
  // mu ~ Uniform(0,1) is implicit since Stan parameters are uniform
  // on bounded intervals unless otherwise specified

  // ---- Prior for eta ----
  // p(eta) ∝ n1 / (n1 + eta)^2
  target += log(n1) - 2 * log(n1 + eta);

  // ---- Hierarchical model ----
  // p[i] ~ Beta(mu * eta, (1 - mu) * eta)
  p ~ beta(mu * eta, (1 - mu) * eta);

  // y[i] ~ Binomial(n[i], p[i])
  y ~ binomial(n, p);
}

3 MCMC via STAN

#install.packages("rstan")
library("rstan")
options(mc.cores=4)

stan_data = list(
  K = K,
  n = n,
  y = y,
  n1 = 10   
)

# Running stan code
model = stan_model("hierarchical-beta-binomial.stan")

fit = sampling(model,data=stan_data,seed=31415,iter=15000,warmup=10000,thin=1,chains=4)

params = extract(fit)

mu  = params$mu
eta = params$eta
a = mu*eta
b = (1-mu)*eta
sd = sqrt(a*b/((a+b)^2*(a+b+1)))

4 Posterior summary

print(fit)
## Inference for Stan model: anon_model.
## 4 chains, each with iter=15000; warmup=10000; thin=1; 
## post-warmup draws per chain=5000, total post-warmup draws=20000.
## 
##          mean se_mean      sd    2.5%     25%     50%     75%   97.5% n_eff
## mu       0.07    0.00    0.01    0.06    0.07    0.07    0.08    0.09  7980
## eta    555.72   36.42 1008.17   37.56  114.55  225.74  516.44 3943.77   766
## p[1]     0.06    0.00    0.01    0.03    0.05    0.06    0.07    0.08  6140
## p[2]     0.06    0.00    0.02    0.03    0.05    0.07    0.07    0.10 15146
## p[3]     0.07    0.00    0.01    0.05    0.07    0.07    0.08    0.10 14375
## p[4]     0.07    0.00    0.02    0.05    0.06    0.07    0.08    0.11 14691
## p[5]     0.08    0.00    0.01    0.06    0.07    0.08    0.08    0.10 10353
## p[6]     0.06    0.00    0.01    0.04    0.06    0.06    0.07    0.09 12927
## p[7]     0.08    0.00    0.02    0.05    0.07    0.08    0.09    0.14  7696
## p[8]     0.07    0.00    0.01    0.05    0.06    0.07    0.07    0.09 17380
## p[9]     0.07    0.00    0.01    0.04    0.06    0.07    0.07    0.09 14623
## p[10]    0.09    0.00    0.02    0.06    0.07    0.09    0.10    0.14  5308
## p[11]    0.07    0.00    0.01    0.05    0.06    0.07    0.08    0.09 13859
## p[12]    0.06    0.00    0.01    0.03    0.05    0.06    0.07    0.08  6272
## p[13]    0.08    0.00    0.02    0.04    0.06    0.07    0.09    0.13 13754
## lp__  -597.18    0.15    5.49 -607.04 -600.86 -597.60 -594.00 -584.58  1260
##       Rhat
## mu       1
## eta      1
## p[1]     1
## p[2]     1
## p[3]     1
## p[4]     1
## p[5]     1
## p[6]     1
## p[7]     1
## p[8]     1
## p[9]     1
## p[10]    1
## p[11]    1
## p[12]    1
## p[13]    1
## lp__     1
## 
## Samples were drawn using NUTS(diag_e) at Thu Oct 30 17:58:17 2025.
## 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).

5 MCMC chains and marginal posteriors

par(mfrow=c(2,3))
ts.plot(mu)
ts.plot(eta)
ts.plot(sd)
hist(mu,prob=TRUE,main=expression(mu))
hist(eta,prob=TRUE,main=expression(eta))
hist(sd,prob=TRUE,main="Standard deviation")

6 Marginal posterior summaries

tab = apply(cbind(mu,eta,sd),2,quantile,c(0.05,0.5,0.95))
colnames(tab) = c("mu","eta","sd")
rownames(tab) = c("5%","50%","95%")
tab
##             mu        eta          sd
## 5%  0.05951586   49.21486 0.005366085
## 50% 0.07151268  225.73636 0.017042285
## 95% 0.08742623 2234.30645 0.038096447

7 Posterior for death proportions

p = params$p

pmean = apply(p,2,mean)

par(mfrow=c(1,1))
boxplot(p,outline=FALSE,ylim=c(0,0.15))
points(1:13,phat,col=2,pch=16)
abline(h=mean(phat),col=2,lwd=2)

8 Borrowing strength and shrinkage effect

plot(rep(0.1,K),phat,xlim=c(0,0.3),axes=FALSE,xlab="",ylab="",pch=16,ylim=c(0,0.14))
points(rep(0.2,K),pmean,col=2,pch=16)
for (i in 1:K)
  segments(0.1,phat[i],0.2,pmean[i],col=gray(0.8),lwd=2)
points(rep(0.1,K),phat,pch=16)
points(rep(0.2,K),pmean,col=2,pch=16)
text(0.1,0.01,"y/n")
text(0.2,0.01,"E(p)")
box()

LS0tCnRpdGxlOiAiQmF5ZXNpYW4gSGllcmFyY2hpY2FsIE1vZGVsaW5nIHZpYSBTVEFOIgpzdWJ0aXRsZTogIkRlYXRocyBhZnRlciBoZWFydCBhdHRhY2siCmF1dGhvcjogIkhlZGliZXJ0IEZyZWl0YXMgTG9wZXMiCmRhdGU6ICIzMC8xMC8yMDI1IgpvdXRwdXQ6CiAgaHRtbF9kb2N1bWVudDoKICAgIHRvYzogdHJ1ZQogICAgdG9jX2RlcHRoOiAzCiAgICB0b2NfY29sbGFwc2VkOiB0cnVlCiAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCiAgICBudW1iZXJfc2VjdGlvbnM6IHRydWUKICBwZGZfZG9jdW1lbnQ6CiAgICB0b2M6IHRydWUKICAgIHRvY19kZXB0aDogJzMnCi0tLQoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSkKYGBgCgoKIyBUaGUgZGF0YXNldCAKClRoZSBmb2xsb3dpbmcgcGllY2VzIG9mIGV4cGxhbmF0b3J5IHRleHQgd2VyZSB0YWtlbiBmcm9tIEppbSBBbGJlcnQncyBnaXRodWIgcGFnZSBhdCAKaHR0cHM6Ly9iYXllc2JhbGwuZ2l0aHViLmlvL0JPT0svYmF5ZXNpYW4taGllcmFyY2hpY2FsLW1vZGVsaW5nLmh0bWwuICBQYXJ0aWN1bGFybHksIApTZWN0aW9uIDEwLjMgb24gSGllcmFyY2hpY2FsIEJldGEtQmlub21pYWwgTW9kZWxpbmcsIGFuZCAgU2VjdGlvbiAgMTAuMy4xIEV4YW1wbGU6IERlYXRocyBhZnRlciBoZWFydCBhdHRhY2suCgpUaGUgTmV3IFlvcmsgU3RhdGUgKE5ZUykgRGVwYXJ0bWVudCBvZiBIZWFsdGggY29sbGVjdHMgYW5kIHJlbGVhc2VzIGRhdGEgb24gbW9ydGFsaXR5IGFmdGVyIEFjdXRlIE15b2NhcmRpYWwgSW5mYXJjdGlvbiAoQU1JKSwgY29tbW9ubHkga25vd24gYXMgYSBoZWFydCBhdHRhY2suIFRoZWlyIDIwMTUgCnJlcG9ydCB3YXMgdGhlIGluaXRpYWwgcHVibGljIGRhdGEgcmVsZWFzZSBieSB0aGUgTllTIERlcGFydG1lbnQgb2YgSGVhbHRoIG9uIHJpc2stCmFkanVzdGVkIG1vcnRhbGl0eSBvdXRjb21lcyBmb3IgQU1JIHBhdGllbnRzIGF0IGhvc3BpdGFscyBhY3Jvc3MgdGhlIHN0YXRlLiAKV2UgZm9jdXMgb24gMTMgaG9zcGl0YWxzIGluIE1hbmhhdHRhbiwgTmV3IFlvcmsgQ2l0eSAtIE1hbmhhdHRhbiBpbiAyMDE1LCB3aXRoIHRoZSAKZ29hbCBvZiBsZWFybmluZyBhYm91dCB0aGUgcGVyY2VudGFnZXMgb2YgcmVzdWx0ZWQgZGVhdGhzIGZyb20gaGVhcnQgYXR0YWNrIGZvciBob3NwaXRhbHMgaW4gdGhpcyBzYW1wbGUuIEJlbG93IHdlIGhhdmUgdGhlIHJlY29yZHMgZm9yIGVhY2ggaG9zcGl0YWwgdGhlIG51bWJlciBvZiBoZWFydCBhdHRhY2sgY2FzZXMsIHRoZSBjb3JyZXNwb25kaW5nIG51bWJlciBvZiByZXN1bHRlZCBkZWF0aHMsIGFuZCB0aGVpciBjb21wdXRlZCBwZXJjZW50YWdlIG9mIHJlc3VsdGVkIGRlYXRocy4gIE5ZUCBzdGFuZHMgZm9yIE5ldyBZb3JrIFByZXNieXRlcmlhbi4KCiogQmVsbGV2dWUgSG9zcGl0YWwgQ2VudGVyCiogSGFybGVtIEhvc3BpdGFsIENlbnRlcgoqIExlbm94IEhpbGwgSG9zcGl0YWwKKiBNZXRyb3BvbGl0YW4gSG9zcGl0YWwgQ2VudGVyCiogTW91bnQgU2luYWkgQmV0aCBJc3JhZWwKKiBNb3VudCBTaW5haSBIb3NwaXRhbAoqIE1vdW50IFNpbmFpIFJvb3NldmVsdAoqIE1vdW50IFNpbmFpIFN0LiBMdWtl4oCZcwoqIE5ZVSBIb3NwaXRhbHMgQ2VudGVyCiogTllQIEhvc3BpdGFsIC0gQWxsZW4gSG9zcGl0YWwKKiBOWVAgSG9zcGl0YWwgLSBDb2x1bWJpYSBQcmVzYnl0ZXJpYW4gQ2VudGVyCiogTllQIEhvc3BpdGFsIC0gTmV3IFlvcmsgV2VpbGwgQ29ybmVsbCBDZW50ZXIKKiBOWVAvTG93ZXIgTWFuaGF0dGFuIEhvc3BpdGFsCgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTZ9CnkgPSBjKDQsMSwxOCw3LDI0LDE2LDYsMTksMTUsMTMsMjUsMTEsNCkKbiA9IGMoMTI5LDM1LDIyOCw4NCwyOTEsMjcwLDQ2LDI5MywyNDEsMTA1LDM1MywyNTAsNDEpCksgPSBsZW5ndGgoeSkKcGhhdCA9IHkvbgoKCnBhcihtZnJvdz1jKDEsMSkpCnBsb3QoeS9uLHlsaW09YygwLDAuMTMpLHhsYWI9Ik51bWJlciBvZiBjYXNlcyBwZXIgaG9zcGl0YWwiLHlsYWI9IlByb3BvcnRpb24gb2YgZGVhdGgiLHBjaD0xNixjZXg9MS41LGF4ZXM9RkFMU0UpCmF4aXMoMik7YXhpcygxLGF0PTE6MTMsbGFiZWw9bik7Ym94KCkKdGV4dCgxOjEzLHJlcCgwLDEzKSx5KQphYmxpbmUoaD1zdW0oeSkvc3VtKG4pLGNvbD02KQpgYGAKClRyZWF0aW5nIOKAnGNhc2Vz4oCdIGFzIHRyaWFscyBhbmQg4oCcZGVhdGhz4oCdIGFzIHN1Y2Nlc3NlcywgdGhlIEJpbm9taWFsIHNhbXBsaW5nIG1vZGVsIGlzIGEgbmF0dXJhbCBjaG9pY2UgZm9yIHRoaXMgZGF0YSwgYW5kIHRoZSBvYmplY3RpdmUgaXMgdG8gbGVhcm4gYWJvdXQgdGhlIGRlYXRoIHByb2JhYmlsaXR5ICRwJCBvZiB0aGUgaG9zcGl0YWxzLiBJZiBvbmUgbG9va3MgYXQgdGhlIGFjdHVhbCBkZWF0aCBwZXJjZW50YWdlcywgc29tZSBob3NwaXRhbHMgaGF2ZSBtdWNoIGhpZ2hlciBkZWF0aCByYXRlcyB0aGFuIG90aGVyIGhvc3BpdGFscy4gRm9yIGV4YW1wbGUsIHRoZSBoaWdoZXN0IGRlYXRoIHJhdGUgYmVsb25ncyB0byBNb3VudCBTaW5haSBSb29zZXZlbHQsIGF0IDEzLjA0MyUgd2hpY2ggaXMgbW9yZSB0aGFuIGZvdXIgdGltZXMgdGhlIHJhdGUgb2YgSGFybGVtIEhvc3BpdGFsIENlbnRlciBhdCAyLjg1N1wlLiAKCkEpICoqUG9vbGluZyB0aGUgZGF0YSBmcm9tIHRoZSAxMyBob3NwaXRhbHMqKjogSWYgb25lIGFzc3VtZXMgYSBjb21tb24gcHJvYmFiaWxpdHkgcCBmb3IgYWxsIDEzIGhvc3BpdGFscywgdGhpcyBtb2RlbCBkb2VzIG5vdCBhbGxvdyBmb3IgcG9zc2libGUgZGlmZmVyZW5jZXMgYmV0d2VlbiB0aGUgZGVhdGggcmF0ZXMgYW1vbmcgdGhlc2UgaG9zcGl0YWxzLgoKQikgKipBbmFseXNpbmcgZWFjaCBob3NwaXRhbCBzZXBhcmF0ZWx5Kio6IElmIG9uZSBjcmVhdGVzIDEzIHNlcGFyYXRlIEJpbm9taWFsIHNhbXBsaW5nIG1vZGVscywgb25lIGZvciBlYWNoIGhvc3BpdGFsLCBhbmQgY29uZHVjdHMgc2VwYXJhdGUgaW5mZXJlbmNlcywgb25lIGxvc2VzIHRoZSBhYmlsaXR5IHRvIHVzZSBwb3RlbnRpYWwgaW5mb3JtYXRpb24gYWJvdXQgdGhlIGRlYXRoIHJhdGUgZnJvbSBob3NwaXRhbCAkaiQgd2hlbiBtYWtpbmcgaW5mZXJlbmNlIGFib3V0IHRoYXQgb2YgYSBkaWZmZXJlbnQgaG9zcGl0YWwgJGkkLiAgU2luY2UgdGhlc2UgYXJlIGFsbCBob3NwaXRhbHMgaW4gTWFuaGF0dGFuLCBOZXcgWW9yayBDaXR5LCB0aGV5IG1heSBzaGFyZSBhdHRyaWJ1dGVzIGluIGNvbW1vbiByZWxhdGVkIHRvIGRlYXRoIHJhdGVzIGZyb20gaGVhcnQgYXR0YWNrLiBUaGUgc2VwYXJhdGUgbW9kZWxpbmcgYXBwcm9hY2ggZG9lcyBub3QgYWxsb3cgZm9yIHRoZSBzaGFyaW5nIG9mIGluZm9ybWF0aW9uIGFjcm9zcyBob3NwaXRhbHMuCgpDKSAqKkhpZXJhcmNoaWNhbCBtb2RlbGluZyoqIEEgaGllcmFyY2hpY2FsIG1vZGVsIHByb3ZpZGVzIGEgY29tcHJvbWlzZSBiZXR3ZWVuIHRoZSBjb21iaW5lZCBhbmQgc2VwYXJhdGUgbW9kZWxpbmcgYXBwcm9hY2hlcy4gIEluIHRoaXMgc2V0dGluZywgb25lIGJ1aWxkcyBhIGhpZXJhcmNoaWNhbCBtb2RlbCBieSBhc3N1bWluZyB0aGUgaG9zcGl0YWwgZGVhdGggcmF0ZSBwYXJhbWV0ZXJzIGEgcHJpb3JpIGNvbWUgZnJvbSBhIGNvbW1vbiBkaXN0cmlidXRpb24uIFNwZWNpZmljYWxseSwgb25lIGJ1aWxkcyBhIGhpZXJhcmNoaWNhbCBtb2RlbCBiYXNlZCBvbiBhIGNvbW1vbiBCZXRhIGRpc3RyaWJ1dGlvbiB0aGF0IGdlbmVyYWxpemVzIHRoZSBCZXRhLUJpbm9taWFsIGNvbmp1Z2F0ZSBtb2RlbC4gVGhpcyBtb2RlbGluZyBzZXR1cCBwcm92aWRlcyBwb3N0ZXJpb3IgZXN0aW1hdGVzIHRoYXQgcGFydGlhbGx5IHBvb2wgaW5mb3JtYXRpb24gYW1vbmcgaG9zcGl0YWxzLgoKIyBUaGUgU1RBTiBmaWxlClNhdmUgdGhlIGZvbGxvd2luZyBjaHVuY2sgb2YgY29kZSBpbnRvIGEgKipzdGFuKiogZmlsZSBuYW1lZCwgZm9yIGluc3RhbmNlLCAKImhpZXJhcmNoaWNhbC1iZXRhLWJpbm9taWFsLnN0YW4iLgoKYGBge3IgZXZhbCA9IEZBTFNFfQpkYXRhIHsKICBpbnQ8bG93ZXI9MT4gSzsgICAgICAgICAgICAgICAvLyBudW1iZXIgb2Ygb2JzZXJ2YXRpb25zCiAgaW50PGxvd2VyPTA+IHlbS107ICAgICAgICAgICAgLy8gc3VjY2Vzc2VzCiAgaW50PGxvd2VyPTA+IG5bS107ICAgICAgICAgICAgLy8gdHJpYWxzCiAgcmVhbDxsb3dlcj0wPiBuMTsgICAgICAgICAgICAgLy8gZml4ZWQgY29uc3RhbnQgZm9yIGV0YSBwcmlvcgp9CgpwYXJhbWV0ZXJzIHsKICByZWFsPGxvd2VyPTAsdXBwZXI9MT4gbXU7ICAgICAvLyBtZWFuIHBhcmFtZXRlciBvZiBCZXRhCiAgcmVhbDxsb3dlcj0wPiBldGE7ICAgICAgICAgICAgLy8gcHJlY2lzaW9uIHBhcmFtZXRlciAoYStiKQogIHZlY3Rvcjxsb3dlcj0wLHVwcGVyPTE+W0tdIHA7IC8vIGluZGl2aWR1YWwgcHJvYmFiaWxpdGllcwp9Cgptb2RlbCB7CiAgLy8gLS0tLSBQcmlvciBmb3IgbXUgLS0tLQogIC8vIG11IH4gVW5pZm9ybSgwLDEpIGlzIGltcGxpY2l0IHNpbmNlIFN0YW4gcGFyYW1ldGVycyBhcmUgdW5pZm9ybQogIC8vIG9uIGJvdW5kZWQgaW50ZXJ2YWxzIHVubGVzcyBvdGhlcndpc2Ugc3BlY2lmaWVkCgogIC8vIC0tLS0gUHJpb3IgZm9yIGV0YSAtLS0tCiAgLy8gcChldGEpIOKInSBuMSAvIChuMSArIGV0YSleMgogIHRhcmdldCArPSBsb2cobjEpIC0gMiAqIGxvZyhuMSArIGV0YSk7CgogIC8vIC0tLS0gSGllcmFyY2hpY2FsIG1vZGVsIC0tLS0KICAvLyBwW2ldIH4gQmV0YShtdSAqIGV0YSwgKDEgLSBtdSkgKiBldGEpCiAgcCB+IGJldGEobXUgKiBldGEsICgxIC0gbXUpICogZXRhKTsKCiAgLy8geVtpXSB+IEJpbm9taWFsKG5baV0sIHBbaV0pCiAgeSB+IGJpbm9taWFsKG4sIHApOwp9CmBgYAoKIyBNQ01DIHZpYSBTVEFOCmBgYHtyIG1lc3NhZ2UgPSBGQUxTRSwgd2FybmluZyA9IEZBTFNFLCByZXN1bHRzPSdoaWRlJ30KI2luc3RhbGwucGFja2FnZXMoInJzdGFuIikKbGlicmFyeSgicnN0YW4iKQpvcHRpb25zKG1jLmNvcmVzPTQpCgpzdGFuX2RhdGEgPSBsaXN0KAogIEsgPSBLLAogIG4gPSBuLAogIHkgPSB5LAogIG4xID0gMTAgICAKKQoKIyBSdW5uaW5nIHN0YW4gY29kZQptb2RlbCA9IHN0YW5fbW9kZWwoImhpZXJhcmNoaWNhbC1iZXRhLWJpbm9taWFsLnN0YW4iKQoKZml0ID0gc2FtcGxpbmcobW9kZWwsZGF0YT1zdGFuX2RhdGEsc2VlZD0zMTQxNSxpdGVyPTE1MDAwLHdhcm11cD0xMDAwMCx0aGluPTEsY2hhaW5zPTQpCgpwYXJhbXMgPSBleHRyYWN0KGZpdCkKCm11ICA9IHBhcmFtcyRtdQpldGEgPSBwYXJhbXMkZXRhCmEgPSBtdSpldGEKYiA9ICgxLW11KSpldGEKc2QgPSBzcXJ0KGEqYi8oKGErYileMiooYStiKzEpKSkKYGBgCgojIFBvc3RlcmlvciBzdW1tYXJ5CgpgYGB7cn0KcHJpbnQoZml0KQpgYGAKCiMgTUNNQyBjaGFpbnMgYW5kIG1hcmdpbmFsIHBvc3RlcmlvcnMKCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTZ9CnBhcihtZnJvdz1jKDIsMykpCnRzLnBsb3QobXUpCnRzLnBsb3QoZXRhKQp0cy5wbG90KHNkKQpoaXN0KG11LHByb2I9VFJVRSxtYWluPWV4cHJlc3Npb24obXUpKQpoaXN0KGV0YSxwcm9iPVRSVUUsbWFpbj1leHByZXNzaW9uKGV0YSkpCmhpc3Qoc2QscHJvYj1UUlVFLG1haW49IlN0YW5kYXJkIGRldmlhdGlvbiIpCmBgYAoKIyBNYXJnaW5hbCBwb3N0ZXJpb3Igc3VtbWFyaWVzCgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTZ9CnRhYiA9IGFwcGx5KGNiaW5kKG11LGV0YSxzZCksMixxdWFudGlsZSxjKDAuMDUsMC41LDAuOTUpKQpjb2xuYW1lcyh0YWIpID0gYygibXUiLCJldGEiLCJzZCIpCnJvd25hbWVzKHRhYikgPSBjKCI1JSIsIjUwJSIsIjk1JSIpCnRhYgpgYGAKCiMgUG9zdGVyaW9yIGZvciBkZWF0aCBwcm9wb3J0aW9ucwoKYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD02fQpwID0gcGFyYW1zJHAKCnBtZWFuID0gYXBwbHkocCwyLG1lYW4pCgpwYXIobWZyb3c9YygxLDEpKQpib3hwbG90KHAsb3V0bGluZT1GQUxTRSx5bGltPWMoMCwwLjE1KSkKcG9pbnRzKDE6MTMscGhhdCxjb2w9MixwY2g9MTYpCmFibGluZShoPW1lYW4ocGhhdCksY29sPTIsbHdkPTIpCmBgYAoKIyBCb3Jyb3dpbmcgc3RyZW5ndGggYW5kIHNocmlua2FnZSBlZmZlY3QKCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTgsIGZpZy5oZWlnaHQ9Nn0KcGxvdChyZXAoMC4xLEspLHBoYXQseGxpbT1jKDAsMC4zKSxheGVzPUZBTFNFLHhsYWI9IiIseWxhYj0iIixwY2g9MTYseWxpbT1jKDAsMC4xNCkpCnBvaW50cyhyZXAoMC4yLEspLHBtZWFuLGNvbD0yLHBjaD0xNikKZm9yIChpIGluIDE6SykKICBzZWdtZW50cygwLjEscGhhdFtpXSwwLjIscG1lYW5baV0sY29sPWdyYXkoMC44KSxsd2Q9MikKcG9pbnRzKHJlcCgwLjEsSykscGhhdCxwY2g9MTYpCnBvaW50cyhyZXAoMC4yLEspLHBtZWFuLGNvbD0yLHBjaD0xNikKdGV4dCgwLjEsMC4wMSwieS9uIikKdGV4dCgwLjIsMC4wMSwiRShwKSIpCmJveCgpCmBgYA==