The data
The state wildlife biologists want to model how many fish are being
caught by fishermen at a state park. Visitors are asked how long they
stayed, how many people were in the group, were there children in the
group and how many fish were caught. Some visitors do not fish, but
there is no data on whether a person fished or not. Some visitors who
did fish did not catch any fish so there are excess zeros in the data
because of the people that did not fish.
We have data on 250 groups that went to a park. Each group was
questioned about how many fish they caught (count), how many children
were in the group (child), how many people were in the group (persons),
and whether or not they brought a camper to the park (camper).
# Data
data <- read.csv("https://stats.idre.ucla.edu/stat/data/fish.csv")
head(data)
## nofish livebait camper persons child xb zg count
## 1 1 0 0 1 0 -0.8963146 3.0504048 0
## 2 0 1 1 1 0 -0.5583450 1.7461489 0
## 3 0 1 0 1 0 -0.4017310 0.2799389 0
## 4 0 1 1 2 1 -0.9562981 -0.6015257 0
## 5 0 1 0 1 0 0.4368910 0.5277091 1
## 6 0 1 1 4 2 1.3944855 -0.7075348 0
y = data$count[data$camper==1 & data$child==1]
par(mfrow=c(1,1))
plot(table(y),xlab="Number of fishes",ylab="Frequency",axes=FALSE,ylim=c(0,25))
axis(2);axis(1,at=min(y):max(y))
for (i in min(y):max(y))
text(i,25,sum(y==i))

The model
Let \(\{y_1,\ldots,y_n\}\) be the
number of fishes caught by \(n=42\)
individuals/groups, who brought campers, children and live baits to the
park. Some of them do not fish, but there is no data on whether a person
fished or not. Some visitors who did fish did not catch any fish
(Poisson zeros), so there are excess zeros in the data because of the
people that did not fish (inflated zeros).
The data \(\{y_1,\ldots,y_n\}\) will
be modeled as \(Poisson(\lambda,\pi)\),
where \(\lambda\) is the usual rate of
fish catching and \(\pi\) the
proportion of visitor who do not fish. Therefore,
\[
Pr(y_i|\lambda,\pi) = \left\{
\begin{array}{ll}
\pi + (1-\pi)\exp\{-\lambda\} & \mbox{if} \ \ y_i=0\\
(1-\pi) \frac{\lambda^{y_i}\exp\{-\lambda\}}{k!} & \mbox{if} \ \
y_i=1,2,\ldots \\
\end{array}
\right.
\] It follows that \[
E(y_i|\lambda,\pi) = (1-\pi)\lambda \ \ \ \mbox{and} \ \ \
V(y_i|\lambda,\pi) = (1-\pi)\lambda(1+\pi\lambda).
\]
Maximum likelihood
estimators
The likelihood function is \[\begin{eqnarray*}
L(\lambda,\pi;\mbox{data}) &=& \prod_{i=1}^n
Pr(y_i|\lambda,\pi)\\
&\propto& \left[\pi +
(1-\pi)\exp\{-\lambda\}\right]^{n_0}[(1-\pi)\exp\{-\lambda\}]^{n-n_0}
\lambda^{n{\bar y}},
\end{eqnarray*}\] where \(n_0\)
is the observed number of zeros (inflated or otherwise) and \(n{\bar y}=\sum_{i=1}^n y_i\).
The maximum likelihood estimator (MLE) of \((\lambda,\pi)\) are \[
{\widehat \lambda}_{mle} = W_0(-{\bar z} e^{-{\bar z}})+{\bar z} \ \ \
\mbox{and} \ \ \
{\widehat \pi}_{mle} = 1-\frac{{\bar y}}{{\widehat \lambda}_{mle}},
\] where \(W_0\) being the main
branch of Lambert’s W-function and \[
{\bar z} = \frac{\sum_{i=1}^n y_i}{n-n_0}.
\]
#install.packages("LambertW")
library("LambertW")
## Loading required package: MASS
## Loading required package: ggplot2
## This is 'LambertW' v0.6.9.2. See NEWS and citation("LambertW").
##
## R: https://github.com/gmgeorg/LambertW
## Python: https://github.com/gmgeorg/pylambertw
## ---------------------------------------------
likelihood = function(y,lambda,pi){
ifelse(y==0,pi+(1-pi)*exp(-lambda),(1-pi)*dpois(y,lambda))
}
n = length(y)
n0 = sum(y==0)
ybar = mean(y)
s2 = var(y)
zbar = sum(y)/(n-n0)
lambda.mle = W(-zbar*exp(-zbar))+zbar
pi.mle = 1-ybar/lambda.mle
N = 30
lambdas = seq(3,6,length=N)
pis = seq(0.3,0.7,length=N)
like = matrix(0,N,N)
for (i in 1:N)
for (j in 1:N)
like[i,j] = prod(likelihood(y,lambdas[i],pis[j]))
par(mfrow=c(1,2))
persp(x=lambdas,y=pis,z=like,
theta = 40, # rotation angle
phi = 25, # elevation angle
col = "lightblue", # color of surface
shade = 0.5, # shading intensity
expand = 0.7, # scaling factor for z-axis
ticktype = "detailed",
xlab = expression(lambda),
ylab = expression(pi),
zlab = "Likelihood",
main = "Likelihood Surface over λ and π"
)
contour(lambdas,pis,like,drawlabels=FALSE,xlab=expression(lambda),
ylab=expression(pi),main="Likelihood Contours over λ and π")
points(lambda.mle,pi.mle,col=2,pch=16,cex=2)

Method of moments
estimators
By matching the sample mean, \({\bar
y}\) and the sample variance, \(s^2\), to the population moments \(E(y|\lambda,\pi)\) and \(V(y|\lambda,\pi)\), respectively, it can be
shown that the MM estimator of \((\lambda,\pi)\) are \[
\lambda_{mm} = \frac{s^2+{\bar y}^2}{{\bar y}}-1\ \ \ \mbox{and} \ \ \
\pi_{mm} = \frac{s^2-{\bar y}}{s^2+{\bar y}^2-{\bar y}}
\]
lambda.mm = (s2+ybar^2)/ybar-1
pi.mm = (s2-ybar)/(s2+ybar^2-ybar)
tab = rbind(c(lambda.mm,pi.mm),c(lambda.mle,pi.mle))
colnames(tab) = c("lambda","pi")
rownames(tab) = c("Method of moments","Maximum likelihood")
round(tab,3)
## lambda pi
## Method of moments 7.159 0.721
## Maximum likelihood 4.223 0.526
Comparing fitted
models
yy = sort(unique(y))
nn = length(yy)
freq = rep(0,nn)
for (i in 1:nn)
freq[i] = sum(y==yy[i])/n
fit.mle = likelihood(yy,lambda.mle,pi.mle)
fit.mm = likelihood(yy,lambda.mm,pi.mm)
rmse.mle = sqrt(mean((freq-fit.mle)^2))
rmse.mm = sqrt(mean((freq-fit.mm)^2))
par(mfrow=c(1,1))
plot(yy+0.1,freq,ylim=c(0,1),xlab="Counts",ylab="Probability",pch=16,axes=FALSE)
axis(2)
axis(1,at=0:max(yy))
points(yy-0.1,fit.mle,col=2,pch=16)
points(yy,fit.mm,col=4,pch=16)
legend("topright",legend=c("Observed count","Method of Moments","Maximum likelihood"),col=c(1,4,2),bty="n",pch=16)
legend("topleft",legend=c(paste("RMSE(MLE) = ",round(rmse.mle,3),sep=""),
paste("RMSE(MM) = ",round(rmse.mm,3),sep="")))

tab = round(cbind(yy,n*freq,n*fit.mle,n*fit.mm))
colnames(tab) = c("counts","Frequency","MLE","MM")
tab
## counts Frequency MLE MM
## [1,] 0 24 24 32
## [2,] 1 6 1 0
## [3,] 2 2 3 0
## [4,] 3 4 4 1
## [5,] 4 2 4 1
## [6,] 5 3 3 2
## [7,] 7 1 1 2
## [8,] 8 1 1 2
## [9,] 14 1 0 0
## [10,] 16 1 0 0
Posterior inference via
SIR
M = 10000
lambda.d = runif(M,1,8)
pi.d = runif(M,0.1,0.9)
w = rep(0,M)
for (i in 1:M)
w[i] = prod(likelihood(y,lambda.d[i],pi.d[i]))
ind = sample(1:M,size=M,prob=w,replace=TRUE)
lambda.p = lambda.d[ind]
pi.p = pi.d[ind]
par(mfrow=c(2,2))
plot(lambda.d,pi.d,xlab=expression(lambda),ylab=expression(pi))
contour(lambdas,pis,like,col=2,add=TRUE,drawlabels=FALSE,lwd=2)
title("Prior & likelihood ")
plot(lambda.p,pi.p,xlim=range(lambda.d),ylim=range(pi.d),xlab=expression(lambda),ylab=expression(pi))
contour(lambdas,pis,like,col=2,add=TRUE,drawlabels=FALSE,lwd=2)
title("Posterior vs likelihood")
hist(lambda.p,prob=TRUE,main="",xlab=expression(lambda))
hist(pi.p,prob=TRUE,main="",xlab=expression(pi))

Posterior predictive
inference via SIR
pred = matrix(0,M,nn)
for (i in 1:M)
for (j in 1:nn)
pred[i,j] = likelihood(yy[j],lambda.p[i],pi.p[i])
qpred = t(apply(pred,2,quantile,c(0.025,0.5,0.925)))
plot(yy,qpred[,2],ylim=range(qpred),pch=16,xlab="Counts",ylab="Predictive probability",col=6)
segments(yy,qpred[,1],yy,qpred[,3],col=6)
points(yy,freq,pch=16)
legend("topright",legend=c("Observed count","95% predictive interval"),col=c(1,6),bty="n",pch=16)

LS0tCnRpdGxlOiAgICAiWmVyby1JbmZsYXRlZCBQb2lzc29uIG1vZGVsaW5nIgpzdWJ0aXRsZTogIk1ldGhvZCBvZiBtb21lbnRzLCBNTCBhbmQgQmF5ZXNpYW4gZXN0aW1hdGlvbiIKYXV0aG9yOiAgICJIZWRpYmVydCBGcmVpdGFzIExvcGVzIgpkYXRlOiAiMDQvMTEvMjAyNSIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICB0b2M6IHRydWUKICAgIHRvY19kZXB0aDogMwogICAgdG9jX2NvbGxhcHNlZDogdHJ1ZQogICAgY29kZV9kb3dubG9hZDogdHJ1ZQogICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCiAgcGRmX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6ICczJwoKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFKQpgYGAKCiMgVGhlIGRhdGEKClRoZSBzdGF0ZSB3aWxkbGlmZSBiaW9sb2dpc3RzIHdhbnQgdG8gbW9kZWwgaG93IG1hbnkgZmlzaCBhcmUgYmVpbmcgY2F1Z2h0IGJ5IGZpc2hlcm1lbiBhdCBhIHN0YXRlIHBhcmsuIFZpc2l0b3JzIGFyZSBhc2tlZCBob3cgbG9uZyB0aGV5IHN0YXllZCwgaG93IG1hbnkgcGVvcGxlIHdlcmUgaW4gdGhlIGdyb3VwLCB3ZXJlIHRoZXJlIGNoaWxkcmVuIGluIHRoZSBncm91cCBhbmQgaG93IG1hbnkgZmlzaCB3ZXJlIGNhdWdodC4gU29tZSB2aXNpdG9ycyBkbyBub3QgZmlzaCwgYnV0IHRoZXJlIGlzIG5vIGRhdGEgb24gd2hldGhlciBhIHBlcnNvbiBmaXNoZWQgb3Igbm90LiBTb21lIHZpc2l0b3JzIHdobyBkaWQgZmlzaCBkaWQgbm90IGNhdGNoIGFueSBmaXNoIHNvIHRoZXJlIGFyZSBleGNlc3MgemVyb3MgaW4gdGhlIGRhdGEgYmVjYXVzZSBvZiB0aGUgcGVvcGxlIHRoYXQgZGlkIG5vdCBmaXNoLgoKV2UgaGF2ZSBkYXRhIG9uIDI1MCBncm91cHMgdGhhdCB3ZW50IHRvIGEgcGFyay4gRWFjaCBncm91cCB3YXMgcXVlc3Rpb25lZCBhYm91dCBob3cgbWFueSBmaXNoIHRoZXkgY2F1Z2h0IChjb3VudCksIGhvdyBtYW55IGNoaWxkcmVuIHdlcmUgaW4gdGhlIGdyb3VwIChjaGlsZCksIGhvdyBtYW55IHBlb3BsZSB3ZXJlIGluIHRoZSBncm91cCAocGVyc29ucyksIGFuZCB3aGV0aGVyIG9yIG5vdCB0aGV5IGJyb3VnaHQgYSBjYW1wZXIgdG8gdGhlIHBhcmsgKGNhbXBlcikuCgoqIFNvdXJjZTogaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvWmVyby1pbmZsYXRlZF9tb2RlbAoKKiBTb3VyY2U6IGh0dHBzOi8vc3RhdHMub2FyYy51Y2xhLmVkdS9yL2RhZS96aXAvCgoKYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD02fQojIERhdGEKZGF0YSA8LSByZWFkLmNzdigiaHR0cHM6Ly9zdGF0cy5pZHJlLnVjbGEuZWR1L3N0YXQvZGF0YS9maXNoLmNzdiIpCgpoZWFkKGRhdGEpCgp5ID0gZGF0YSRjb3VudFtkYXRhJGNhbXBlcj09MSAmIGRhdGEkY2hpbGQ9PTFdCgpwYXIobWZyb3c9YygxLDEpKQpwbG90KHRhYmxlKHkpLHhsYWI9Ik51bWJlciBvZiBmaXNoZXMiLHlsYWI9IkZyZXF1ZW5jeSIsYXhlcz1GQUxTRSx5bGltPWMoMCwyNSkpCmF4aXMoMik7YXhpcygxLGF0PW1pbih5KTptYXgoeSkpCmZvciAoaSBpbiBtaW4oeSk6bWF4KHkpKQogIHRleHQoaSwyNSxzdW0oeT09aSkpCmBgYAoKIyBUaGUgbW9kZWwKTGV0ICRce3lfMSxcbGRvdHMseV9uXH0kIGJlIHRoZSBudW1iZXIgb2YgZmlzaGVzIGNhdWdodCBieSAkbj00MiQgaW5kaXZpZHVhbHMvZ3JvdXBzLCB3aG8gYnJvdWdodCAKY2FtcGVycywgY2hpbGRyZW4gYW5kIGxpdmUgYmFpdHMgdG8gdGhlIHBhcmsuICBTb21lIG9mIHRoZW0gZG8gbm90IGZpc2gsIGJ1dCB0aGVyZSBpcyBubyBkYXRhIG9uIHdoZXRoZXIgYSBwZXJzb24gZmlzaGVkIG9yIG5vdC4gU29tZSB2aXNpdG9ycyB3aG8gZGlkIGZpc2ggZGlkIG5vdCBjYXRjaCBhbnkgZmlzaCAoUG9pc3NvbiB6ZXJvcyksIHNvIHRoZXJlIGFyZSBleGNlc3MgemVyb3MgaW4gdGhlIGRhdGEgYmVjYXVzZSBvZiB0aGUgcGVvcGxlIHRoYXQgZGlkIG5vdCBmaXNoIChpbmZsYXRlZCB6ZXJvcykuCgpUaGUgZGF0YSAkXHt5XzEsXGxkb3RzLHlfblx9JCB3aWxsIGJlIG1vZGVsZWQgYXMgJFBvaXNzb24oXGxhbWJkYSxccGkpJCwgd2hlcmUgJFxsYW1iZGEkIGlzIHRoZSB1c3VhbCByYXRlIG9mIGZpc2ggY2F0Y2hpbmcgYW5kICRccGkkIHRoZSBwcm9wb3J0aW9uIG9mIHZpc2l0b3Igd2hvIGRvIG5vdCBmaXNoLiAgVGhlcmVmb3JlLAoKJCQKUHIoeV9pfFxsYW1iZGEsXHBpKSA9IFxsZWZ0XHsKXGJlZ2lue2FycmF5fXtsbH0KXHBpICsgKDEtXHBpKVxleHBcey1cbGFtYmRhXH0gJiBcbWJveHtpZn0gXCBcIHlfaT0wXFwKKDEtXHBpKSBcZnJhY3tcbGFtYmRhXnt5X2l9XGV4cFx7LVxsYW1iZGFcfX17ayF9ICYgXG1ib3h7aWZ9IFwgXCB5X2k9MSwyLFxsZG90cyBcXApcZW5ke2FycmF5fQpccmlnaHQuCiQkCkl0IGZvbGxvd3MgdGhhdCAKJCQKRSh5X2l8XGxhbWJkYSxccGkpID0gKDEtXHBpKVxsYW1iZGEgXCBcIFwgXG1ib3h7YW5kfSBcIFwgXCAKVih5X2l8XGxhbWJkYSxccGkpID0gKDEtXHBpKVxsYW1iZGEoMStccGlcbGFtYmRhKS4KJCQKCiMgTWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRvcnMKClRoZSBsaWtlbGlob29kIGZ1bmN0aW9uIGlzClxiZWdpbntlcW5hcnJheSp9CkwoXGxhbWJkYSxccGk7XG1ib3h7ZGF0YX0pICY9JiBccHJvZF97aT0xfV5uIFByKHlfaXxcbGFtYmRhLFxwaSlcXAomXHByb3B0byYgIFxsZWZ0W1xwaSArICgxLVxwaSlcZXhwXHstXGxhbWJkYVx9XHJpZ2h0XV57bl8wfVsoMS1ccGkpXGV4cFx7LVxsYW1iZGFcfV1ee24tbl8wfSBcbGFtYmRhXntue1xiYXIgeX19LApcZW5ke2VxbmFycmF5Kn0Kd2hlcmUgJG5fMCQgaXMgdGhlIG9ic2VydmVkIG51bWJlciBvZiB6ZXJvcyAoaW5mbGF0ZWQgb3Igb3RoZXJ3aXNlKSBhbmQgJG57XGJhciB5fT1cc3VtX3tpPTF9Xm4geV9pJC4gCgpUaGUgbWF4aW11bSBsaWtlbGlob29kIGVzdGltYXRvciAoTUxFKSBvZiAkKFxsYW1iZGEsXHBpKSQgYXJlCiQkCntcd2lkZWhhdCBcbGFtYmRhfV97bWxlfSA9IFdfMCgte1xiYXIgen0gZV57LXtcYmFyIHp9fSkre1xiYXIgen0gXCBcIFwgXG1ib3h7YW5kfSBcIFwgXCAKe1x3aWRlaGF0IFxwaX1fe21sZX0gPSAxLVxmcmFje3tcYmFyIHl9fXt7XHdpZGVoYXQgXGxhbWJkYX1fe21sZX19LAokJAp3aGVyZSAkV18wJCBiZWluZyB0aGUgbWFpbiBicmFuY2ggb2YgTGFtYmVydCdzIFctZnVuY3Rpb24gYW5kIAokJAp7XGJhciB6fSA9IFxmcmFje1xzdW1fe2k9MX1ebiB5X2l9e24tbl8wfS4KJCQKCgoKYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9MTUsIGZpZy5oZWlnaHQ9OH0KI2luc3RhbGwucGFja2FnZXMoIkxhbWJlcnRXIikKbGlicmFyeSgiTGFtYmVydFciKQpsaWtlbGlob29kID0gZnVuY3Rpb24oeSxsYW1iZGEscGkpewogIGlmZWxzZSh5PT0wLHBpKygxLXBpKSpleHAoLWxhbWJkYSksKDEtcGkpKmRwb2lzKHksbGFtYmRhKSkKfQoKbiAgICAgICAgICA9IGxlbmd0aCh5KQpuMCAgICAgICAgID0gc3VtKHk9PTApCnliYXIgICAgICAgPSBtZWFuKHkpCnMyICAgICAgICAgPSB2YXIoeSkKemJhciAgICAgICA9IHN1bSh5KS8obi1uMCkKbGFtYmRhLm1sZSA9IFcoLXpiYXIqZXhwKC16YmFyKSkremJhcgpwaS5tbGUgICAgID0gMS15YmFyL2xhbWJkYS5tbGUKCgpOID0gMzAKbGFtYmRhcyA9IHNlcSgzLDYsbGVuZ3RoPU4pCnBpcyA9IHNlcSgwLjMsMC43LGxlbmd0aD1OKQpsaWtlID0gbWF0cml4KDAsTixOKQpmb3IgKGkgaW4gMTpOKQogIGZvciAoaiBpbiAxOk4pCiAgICAgbGlrZVtpLGpdID0gcHJvZChsaWtlbGlob29kKHksbGFtYmRhc1tpXSxwaXNbal0pKQoKcGFyKG1mcm93PWMoMSwyKSkKcGVyc3AoeD1sYW1iZGFzLHk9cGlzLHo9bGlrZSwKICB0aGV0YSA9IDQwLCAgICAgICAgICAjIHJvdGF0aW9uIGFuZ2xlCiAgcGhpID0gMjUsICAgICAgICAgICAgIyBlbGV2YXRpb24gYW5nbGUKICBjb2wgPSAibGlnaHRibHVlIiwgICAjIGNvbG9yIG9mIHN1cmZhY2UKICBzaGFkZSA9IDAuNSwgICAgICAgICAjIHNoYWRpbmcgaW50ZW5zaXR5CiAgZXhwYW5kID0gMC43LCAgICAgICAgIyBzY2FsaW5nIGZhY3RvciBmb3Igei1heGlzCiAgdGlja3R5cGUgPSAiZGV0YWlsZWQiLCAKICB4bGFiID0gZXhwcmVzc2lvbihsYW1iZGEpLCAKICB5bGFiID0gZXhwcmVzc2lvbihwaSksIAogIHpsYWIgPSAiTGlrZWxpaG9vZCIsIAogIG1haW4gPSAiTGlrZWxpaG9vZCBTdXJmYWNlIG92ZXIgzrsgYW5kIM+AIgopCmNvbnRvdXIobGFtYmRhcyxwaXMsbGlrZSxkcmF3bGFiZWxzPUZBTFNFLHhsYWI9ZXhwcmVzc2lvbihsYW1iZGEpLAogICAgICAgIHlsYWI9ZXhwcmVzc2lvbihwaSksbWFpbj0iTGlrZWxpaG9vZCBDb250b3VycyBvdmVyIM67IGFuZCDPgCIpCnBvaW50cyhsYW1iZGEubWxlLHBpLm1sZSxjb2w9MixwY2g9MTYsY2V4PTIpCmBgYAoKCiMgTWV0aG9kIG9mIG1vbWVudHMgZXN0aW1hdG9ycwpCeSBtYXRjaGluZyB0aGUgc2FtcGxlIG1lYW4sICR7XGJhciB5fSQgYW5kIHRoZSBzYW1wbGUgdmFyaWFuY2UsICRzXjIkLCB0byB0aGUgcG9wdWxhdGlvbiBtb21lbnRzICRFKHl8XGxhbWJkYSxccGkpJCBhbmQgJFYoeXxcbGFtYmRhLFxwaSkkLCByZXNwZWN0aXZlbHksIGl0IGNhbiBiZSBzaG93biB0aGF0IHRoZSBNTSBlc3RpbWF0b3Igb2YgJChcbGFtYmRhLFxwaSkkIGFyZQokJApcbGFtYmRhX3ttbX0gPSBcZnJhY3tzXjIre1xiYXIgeX1eMn17e1xiYXIgeX19LTFcIFwgXCBcbWJveHthbmR9IFwgXCBcIApccGlfe21tfSA9IFxmcmFje3NeMi17XGJhciB5fX17c14yK3tcYmFyIHl9XjIte1xiYXIgeX19CiQkCgpgYGB7cn0KbGFtYmRhLm1tICA9IChzMit5YmFyXjIpL3liYXItMQpwaS5tbSAgICAgID0gKHMyLXliYXIpLyhzMit5YmFyXjIteWJhcikKCnRhYiA9IHJiaW5kKGMobGFtYmRhLm1tLHBpLm1tKSxjKGxhbWJkYS5tbGUscGkubWxlKSkKY29sbmFtZXModGFiKSA9IGMoImxhbWJkYSIsInBpIikKcm93bmFtZXModGFiKSA9IGMoIk1ldGhvZCBvZiBtb21lbnRzIiwiTWF4aW11bSBsaWtlbGlob29kIikKcm91bmQodGFiLDMpCmBgYAoKIyBDb21wYXJpbmcgZml0dGVkIG1vZGVscwoKYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD02fQp5eSA9IHNvcnQodW5pcXVlKHkpKQpubiA9IGxlbmd0aCh5eSkKZnJlcSA9IHJlcCgwLG5uKQpmb3IgKGkgaW4gMTpubikKICBmcmVxW2ldID0gc3VtKHk9PXl5W2ldKS9uCmZpdC5tbGUgPSBsaWtlbGlob29kKHl5LGxhbWJkYS5tbGUscGkubWxlKQpmaXQubW0gID0gbGlrZWxpaG9vZCh5eSxsYW1iZGEubW0scGkubW0pCnJtc2UubWxlID0gc3FydChtZWFuKChmcmVxLWZpdC5tbGUpXjIpKQpybXNlLm1tID0gc3FydChtZWFuKChmcmVxLWZpdC5tbSleMikpCgpwYXIobWZyb3c9YygxLDEpKQpwbG90KHl5KzAuMSxmcmVxLHlsaW09YygwLDEpLHhsYWI9IkNvdW50cyIseWxhYj0iUHJvYmFiaWxpdHkiLHBjaD0xNixheGVzPUZBTFNFKQpheGlzKDIpCmF4aXMoMSxhdD0wOm1heCh5eSkpCnBvaW50cyh5eS0wLjEsZml0Lm1sZSxjb2w9MixwY2g9MTYpCnBvaW50cyh5eSxmaXQubW0sY29sPTQscGNoPTE2KQpsZWdlbmQoInRvcHJpZ2h0IixsZWdlbmQ9YygiT2JzZXJ2ZWQgY291bnQiLCJNZXRob2Qgb2YgTW9tZW50cyIsIk1heGltdW0gbGlrZWxpaG9vZCIpLGNvbD1jKDEsNCwyKSxidHk9Im4iLHBjaD0xNikKbGVnZW5kKCJ0b3BsZWZ0IixsZWdlbmQ9YyhwYXN0ZSgiUk1TRShNTEUpID0gIixyb3VuZChybXNlLm1sZSwzKSxzZXA9IiIpLAogICAgICAgICAgICAgICAgICAgICAgICAgIHBhc3RlKCJSTVNFKE1NKSAgPSAiLHJvdW5kKHJtc2UubW0sMyksc2VwPSIiKSkpCgp0YWIgPSByb3VuZChjYmluZCh5eSxuKmZyZXEsbipmaXQubWxlLG4qZml0Lm1tKSkKY29sbmFtZXModGFiKSA9IGMoImNvdW50cyIsIkZyZXF1ZW5jeSIsIk1MRSIsIk1NIikKdGFiCgpgYGAKCgojIFBvc3RlcmlvciBpbmZlcmVuY2UgdmlhIFNJUgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTZ9Ck0gPSAxMDAwMApsYW1iZGEuZCA9IHJ1bmlmKE0sMSw4KQpwaS5kID0gcnVuaWYoTSwwLjEsMC45KQp3ID0gcmVwKDAsTSkKZm9yIChpIGluIDE6TSkKIHdbaV0gPSBwcm9kKGxpa2VsaWhvb2QoeSxsYW1iZGEuZFtpXSxwaS5kW2ldKSkKCmluZCA9IHNhbXBsZSgxOk0sc2l6ZT1NLHByb2I9dyxyZXBsYWNlPVRSVUUpCmxhbWJkYS5wID0gbGFtYmRhLmRbaW5kXQpwaS5wID0gcGkuZFtpbmRdCgpwYXIobWZyb3c9YygyLDIpKQpwbG90KGxhbWJkYS5kLHBpLmQseGxhYj1leHByZXNzaW9uKGxhbWJkYSkseWxhYj1leHByZXNzaW9uKHBpKSkKY29udG91cihsYW1iZGFzLHBpcyxsaWtlLGNvbD0yLGFkZD1UUlVFLGRyYXdsYWJlbHM9RkFMU0UsbHdkPTIpCnRpdGxlKCJQcmlvciAmIGxpa2VsaWhvb2QgIikKcGxvdChsYW1iZGEucCxwaS5wLHhsaW09cmFuZ2UobGFtYmRhLmQpLHlsaW09cmFuZ2UocGkuZCkseGxhYj1leHByZXNzaW9uKGxhbWJkYSkseWxhYj1leHByZXNzaW9uKHBpKSkKY29udG91cihsYW1iZGFzLHBpcyxsaWtlLGNvbD0yLGFkZD1UUlVFLGRyYXdsYWJlbHM9RkFMU0UsbHdkPTIpCnRpdGxlKCJQb3N0ZXJpb3IgdnMgbGlrZWxpaG9vZCIpCgpoaXN0KGxhbWJkYS5wLHByb2I9VFJVRSxtYWluPSIiLHhsYWI9ZXhwcmVzc2lvbihsYW1iZGEpKQpoaXN0KHBpLnAscHJvYj1UUlVFLG1haW49IiIseGxhYj1leHByZXNzaW9uKHBpKSkKYGBgCgojIFBvc3RlcmlvciBwcmVkaWN0aXZlIGluZmVyZW5jZSB2aWEgU0lSCgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTZ9CnByZWQgPSBtYXRyaXgoMCxNLG5uKQpmb3IgKGkgaW4gMTpNKQogIGZvciAoaiBpbiAxOm5uKQogICAgcHJlZFtpLGpdID0gbGlrZWxpaG9vZCh5eVtqXSxsYW1iZGEucFtpXSxwaS5wW2ldKQoKcXByZWQgPSB0KGFwcGx5KHByZWQsMixxdWFudGlsZSxjKDAuMDI1LDAuNSwwLjkyNSkpKQpwbG90KHl5LHFwcmVkWywyXSx5bGltPXJhbmdlKHFwcmVkKSxwY2g9MTYseGxhYj0iQ291bnRzIix5bGFiPSJQcmVkaWN0aXZlIHByb2JhYmlsaXR5Iixjb2w9NikKc2VnbWVudHMoeXkscXByZWRbLDFdLHl5LHFwcmVkWywzXSxjb2w9NikKcG9pbnRzKHl5LGZyZXEscGNoPTE2KQpsZWdlbmQoInRvcHJpZ2h0IixsZWdlbmQ9YygiT2JzZXJ2ZWQgY291bnQiLCI5NSUgcHJlZGljdGl2ZSBpbnRlcnZhbCIpLGNvbD1jKDEsNiksYnR5PSJuIixwY2g9MTYpCgpgYGAKCgoK