1 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))

2 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). \]

3 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)

4 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

5 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

6 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))

7 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