1 Simulating some linear regression data

First we simulated \(n\) pairs of observations, \((y_i,x_i)\) as follows \[ x_i \sim N(0,1) \ \ \ \mbox{and} \ \ \ y_i|x_i \sim N(\alpha+\beta x_i,\sigma^2), \] and randomly select \(d\) regressores \(x_i\) as missing. For convenience, we rearrange the pairs \((y_i,x_i)\) so the last \(d\) are the missing cases.

set.seed(3141593)
set.seed(12345)
n     = 10
d     = 5
x1    = rnorm(n)
alpha = 0
beta  = 1
sig   = 1
true  = c(alpha,beta,sig)
y1    = alpha+beta*x1+rnorm(n,0,sig)
missing = sort(sample(1:n,size=d,replace=FALSE))
y = c(y1[-missing],y1[missing])
x = c(x1[-missing],x1[missing])
 
par(mfrow=c(1,1))
plot(x,y,pch=16)
points(x[(n-d+1):n],y[(n-d+1):n],col=4,pch=16,cex=2)
abline(lm(y~x)$coef,col=4,lwd=2)
abline(lm(y[1:(n-d)]~x[1:(n-d)])$coef,col=1,lwd=2)
legend("topleft",legend=c("OLS fit n-ds obs",
"OLS fit n obs"),col=c(1,4),lwd=2)

2 OLS estimation

2.1 OLS based on \(n\) observations

ols = lm(y~x)
summary(ols)
## 
## Call:
## lm(formula = y ~ x)
## 
## Residuals:
##      Min       1Q   Median       3Q      Max 
## -0.95785 -0.54544 -0.07149  0.13093  1.76813 
## 
## Coefficients:
##             Estimate Std. Error t value Pr(>|t|)  
## (Intercept)   0.2486     0.2757   0.902   0.3936  
## x             0.7189     0.3520   2.042   0.0754 .
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 0.8593 on 8 degrees of freedom
## Multiple R-squared:  0.3427, Adjusted R-squared:  0.2605 
## F-statistic: 4.171 on 1 and 8 DF,  p-value: 0.07541

2.2 OLS based on \(n-d\) observations

ols = lm(y[1:(n-d)]~x[1:(n-d)])
summary(ols)
## 
## Call:
## lm(formula = y[1:(n - d)] ~ x[1:(n - d)])
## 
## Residuals:
##        1        2        3        4        5 
##  0.07834 -0.01394 -0.04091 -0.10670  0.08322 
## 
## Coefficients:
##              Estimate Std. Error t value Pr(>|t|)   
## (Intercept)  -0.41399    0.04482  -9.237  0.00268 **
## x[1:(n - d)]  0.31526    0.04486   7.027  0.00592 **
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 0.09366 on 3 degrees of freedom
## Multiple R-squared:  0.9427, Adjusted R-squared:  0.9236 
## F-statistic: 49.39 on 1 and 3 DF,  p-value: 0.005919

3 Bayesian inference

We will assume the missing values are completely at random and perform Bayesian inference where the unknowns are \[ \theta = (\alpha,\beta,\sigma^2,x_{d+1},\ldots,x_n), \] with independent prior \[ p(\theta) = p(\alpha)p(\beta)p(\sigma^2)\prod_{i=(n-d)+1}^n p(x_{n-d+i}), \] where \(\mu \sim N(a_0,A_0)\), \(\beta \sim N(b_0,B_0)\) and \(\sigma^2 \sim IG(c_0,d_0)\). Here, we will try two noninformative priors for \(x_{n-d+i}\): \[\begin{eqnarray*} \mbox{Prior I} &:& x_{n-d+i} \sim N(0,1), \ \ \mbox{for} \ \ i=1,\ldots,d\\ \mbox{Prior II} &:& x_{n-d+i} \sim U(x_{min},x_{max}), \ \ \mbox{for} \ \ i=1,\ldots,d. \end{eqnarray*}\]

a0   = 0
A0   = 1
b0   = 0
B0   = 1
c0   = 3
d0   = 4
xmin = min(x[1:(n-d)])
xmax = max(x[1:(n-d)])

3.1 Gibbs sampler

The MCMC scheme cycles through the following \(d+3\) full conditionals: \[\begin{eqnarray*} p(\alpha|y_{1:n},x_{1:n},\beta,\sigma^2)\\ p(\beta|y_{1:n},x_{1:n},\beta,\sigma^2)\\ p(\sigma^2|y_{1:n},x_{1:n},\beta,\sigma^2)\\ p(x_i|y_{1:n},x_{-i},\alpha,\beta,\sigma^2), \end{eqnarray*}\] for \(i=n-d+1,\ldots,n\). Show that these full conditionals are as follows. \[\begin{eqnarray*} [\alpha] &\sim& N\left\{\left(\frac{1}{A_0}+\frac{n}{\sigma^2}\right)^{-1}\left( \frac{a_0}{A_0}+\frac{\sum_{i=1}^n (y_i-\beta x_i)}{\sigma^2} \right) ;\left(\frac{1}{A_0}+\frac{n}{\sigma^2}\right)^{-1}\right\}\\ [\beta] &\sim& N\left\{\left(\frac{1}{B_0}+\frac{\sum_{i=1}^n x_i^2}{\sigma^2}\right)^{-1}\left( \frac{b_0}{B_0}+\frac{\sum_{i=1}^n (y_i-\alpha)x_i}{\sigma^2} \right) ;\left(\frac{1}{B_0}+\frac{\sum_{i=1}^n x_i^2}{\sigma^2}\right)^{-1}\right\}\\ [\sigma^2] &\sim& IG\left\{c_0+\frac{n}{2};d_0+\frac{\sum_{i=1}^n (y_i-\alpha-\beta x_i)/\sigma^2}{2}\right\}\\ [x_i] &\sim& \left\{ \begin{array}{ll} N\left\{ \left(1+\frac{\beta^2}{\sigma^2}\right)^{-1}\beta(y_i-\alpha); \left(1+\frac{\beta^2}{\sigma^2}\right)^{-1}\right\}, \qquad i=n-d+1,\ldots,n & \mbox{Prior I}\\ N_{[x_{min},x_{max}]}\left(\frac{y_i-\alpha}{\beta};\frac{\sigma^2}{\beta^2}\right)& \mbox{Prior II} \end{array} \right. \end{eqnarray*}\]

3.2 Prior I for missing

# Initial values
xmiss = rep(mean(x[1:(n-d)]),d)
alpha = 0
beta  = 0

# Markov chain parameters
M0    = 10000
M     = 10000
niter = M0+M
draws = matrix(0,niter,3+d)

# Gibbs sampler
for (iter in 1:niter){
  xx    = c(x[1:(n-d)],xmiss)
  
  # Sampling sig2
  sig2 = 1/rgamma(1,c0+n/2,d0+(sum((y-alpha-beta*xx)^2))/2)

  # Sampling alpha
  A1 = 1/(1/A0+n/sig2)
  a1 = A1*(a0/A0+sum(y-beta*xx)/sig2)
  alpha = rnorm(1,a1,sqrt(A1))

  # Sampling beta
  B1 = 1/(1/B0+sum(xx^2)/sig2)
  b1 = B1*(b0/B0+sum((y-alpha)*xx)/sig2)
  beta = rnorm(1,b1,sqrt(B1))

  # Sampling missing x's
  vx    = 1/(1+beta^2/sig2)
  mx    = vx*(beta*(y[(n-d+1):n]-alpha)/sig2)
  xmiss = rnorm(d,mx,sqrt(vx))

  # Storing the Monte Carlo chains
  draws[iter,] = c(alpha,beta,sqrt(sig2),xmiss)
}
drawsI = draws[(M0+1):niter,]

3.3 Prior II for missing

# drawsing truncated normal
rtruncnorm = function(mu,sig,a,b){
  A = pnorm(b,mu,sig)
  B = pnorm(a,mu,sig)
  u = runif(1)
  mu+sig*qnorm(u*A-u*B+B)
}

# Initial values
xmiss = rep(mean(x[1:(n-d)]),d)
alpha = 0
beta  = 0

# Markov chain parameters
M0    = 10000
M     = 10000
niter = M0+M
draws = matrix(0,niter,3+d)

# Gibbs sampler
for (iter in 1:niter){
  xx    = c(x[1:(n-d)],xmiss)
  
  # Sampling sig2
  sig2 = 1/rgamma(1,c0+n/2,d0+(sum((y-alpha-beta*xx)^2))/2)

  # Sampling alpha
  A1 = 1/(1/A0+n/sig2)
  a1 = A1*(a0/A0+sum(y-beta*xx)/sig2)
  alpha = rnorm(1,a1,sqrt(A1))

  # Sampling beta
  B1 = 1/(1/B0+sum(xx^2)/sig2)
  b1 = B1*(b0/B0+sum((y-alpha)*xx)/sig2)
  beta = rnorm(1,b1,sqrt(B1))

  # Sampling missing x's
  mx = (y[(n-d+1):n]-alpha)/beta
  vx = sig2/beta^2
  xmiss = rtruncnorm(mx,sqrt(vx),xmin,xmax)

  # Storing the Monte Carlo chains
  draws[iter,] = c(alpha,beta,sqrt(sig2),xmiss)
}
drawsII = draws[(M0+1):niter,]

3.4 Trace plots, acfs and marginal posteriors

par(mfrow=c(3,2))
ts.plot(drawsI[,1],xlab="Iterations",ylab="",main=expression(alpha))
lines(drawsII[,1],col=2)
hist(drawsI[,1],prob=TRUE,main="",xlab=expression(alpha))
lines(density(drawsII[,1]),col=2)
abline(v=true[1],col=3,lwd=3)

ts.plot(drawsI[,2],xlab="Iterations",ylab="",main=expression(beta))
lines(drawsII[,2],col=2)
hist(drawsI[,2],prob=TRUE,main="",xlab=expression(beta))
lines(density(drawsII[,2]),col=2)
abline(v=true[2],col=3,lwd=3)

ts.plot(drawsI[,3],xlab="Iterations",ylab="",main=expression(sigma))
lines(drawsII[,3],col=2)
hist(drawsI[,3],prob=TRUE,main="",xlab=expression(beta))
lines(density(drawsII[,3]),col=2)
abline(v=true[3],col=3,lwd=3)

3.5 Bivariate marginal posteriors

par(mfrow=c(2,3))
plot(drawsI[,1],drawsI[,2],xlab=expression(alpha),ylab=expression(beta))
plot(drawsI[,1],drawsI[,3],xlab=expression(alpha),ylab=expression(sigma))
plot(drawsI[,2],drawsI[,3],xlab=expression(beta),ylab=expression(sigma))
plot(drawsII[,1],drawsII[,2],xlab=expression(alpha),ylab=expression(beta))
plot(drawsII[,1],drawsII[,3],xlab=expression(alpha),ylab=expression(sigma))
plot(drawsII[,2],drawsII[,3],xlab=expression(beta),ylab=expression(sigma))

3.5.1 Estimating the missing values

qx   = t(apply(rbind(drawsI[,4:(3+d)],drawsI[,4:(3+d)]),2,quantile,c(0.25,0.5,0.75)))
qxI  = t(apply(drawsI[,4:(3+d)],2,quantile,c(0.25,0.5,0.75)))
qxII = t(apply(drawsII[,4:(3+d)],2,quantile,c(0.25,0.5,0.75)))

par(mfrow=c(1,2))
plot(x,y,pch=16,xlim=range(x,qx),main="Prior I")
points(x[(n-d+1):n],y[(n-d+1):n],col=4,pch=16,cex=1.2)
points(qxI[,2],y[(n-d+1):n],col=6,pch=16,cex=1.2)
for (i in 1:d)
  segments(qxI[i,1],y[n-d+i],qxI[i,3],y[n-d+i],col=6)

plot(x,y,pch=16,xlim=range(x,qx),main="Prior II")
points(x[(n-d+1):n],y[(n-d+1):n],col=4,pch=16,cex=1.2)
points(qxII[,2],y[(n-d+1):n],col=6,pch=16,cex=1.2)
for (i in 1:d)
  segments(qxII[i,1],y[n-d+i],qxII[i,3],y[n-d+i],col=6)

3.5.2 Comparing linear predictors

xxx = seq(min(x),max(x),length=100)
fx  = array(0,c(2,M,100))
for (i in 1:100){
  fx[1,,i] = drawsI[,1]+drawsI[,2]*xxx[i]
  fx[2,,i] = drawsII[,1]+drawsII[,2]*xxx[i]
}
qfxI  = t(apply(fx[1,,],2,quantile,c(0.25,0.5,0.75)))
qfxII = t(apply(fx[2,,],2,quantile,c(0.25,0.5,0.75)))

par(mfrow=c(1,1))
plot(x,y,pch=16,xlim=range(x,qx))
points(x[(n-d+1):n],y[(n-d+1):n],col=4,pch=16,cex=1.2)
lines(xxx,qfxI[,1],col=2,lty=2,lwd=2)
lines(xxx,qfxI[,2],col=2,lwd=2)
lines(xxx,qfxI[,3],col=2,lty=2,lwd=2)
lines(xxx,qfxII[,1],col=3,lty=2,lwd=2)
lines(xxx,qfxII[,2],col=3,lwd=2)
lines(xxx,qfxII[,3],col=3,lty=2,lwd=2)
abline(lm(y[1:(n-d)]~x[1:(n-d)])$coef,lwd=2)
abline(lm(y~x)$coef,col=4,lwd=2)
legend("topleft",legend=c("OLS (n-d)","OLS (n)","Bayes (Prior I)","Bayes (Prior II)"),col=c(1,4,2,3),lwd=2)

LS0tCnRpdGxlOiAiTGluZWFyIHJlZ3Jlc3Npb24gd2l0aCBtaXNzaW5nIHJlZ3Jlc3NvcnMiCnN1YnRpdGxlOiAiQmF5ZXNpYW4gaW5mZXJlbmNlIHZpYSBHaWJicyBzYW1wbGVyIgphdXRob3I6ICJIZWRpYmVydCBGcmVpdGFzIExvcGVzIgpkYXRlOiAiMi8yMS8yMDIzIgpvdXRwdXQ6CiAgaHRtbF9kb2N1bWVudDoKICAgIHRvYzogdHJ1ZQogICAgdG9jX2RlcHRoOiAyCiAgICBjb2RlX2Rvd25sb2FkOiB5ZXMKICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUpCmBgYAoKIyBTaW11bGF0aW5nIHNvbWUgbGluZWFyIHJlZ3Jlc3Npb24gZGF0YQpGaXJzdCB3ZSBzaW11bGF0ZWQgJG4kIHBhaXJzIG9mIG9ic2VydmF0aW9ucywgJCh5X2kseF9pKSQgYXMgZm9sbG93cwokJAp4X2kgXHNpbSBOKDAsMSkgXCBcIFwgXG1ib3h7YW5kfSBcIFwgXCB5X2l8eF9pIFxzaW0gTihcYWxwaGErXGJldGEgeF9pLFxzaWdtYV4yKSwKJCQKYW5kIHJhbmRvbWx5IHNlbGVjdCAkZCQgcmVncmVzc29yZXMgJHhfaSQgYXMgbWlzc2luZy4gIEZvciBjb252ZW5pZW5jZSwgd2UgcmVhcnJhbmdlIHRoZSBwYWlycyAkKHlfaSx4X2kpJCBzbyB0aGUgbGFzdCAkZCQgYXJlIHRoZSBtaXNzaW5nIGNhc2VzLgoKYGBge3IgZmlnLndpZHRoPTgsIGZpZy5oZWlnaHQ9Nn0Kc2V0LnNlZWQoMzE0MTU5MykKc2V0LnNlZWQoMTIzNDUpCm4gICAgID0gMTAKZCAgICAgPSA1CngxICAgID0gcm5vcm0obikKYWxwaGEgPSAwCmJldGEgID0gMQpzaWcgICA9IDEKdHJ1ZSAgPSBjKGFscGhhLGJldGEsc2lnKQp5MSAgICA9IGFscGhhK2JldGEqeDErcm5vcm0obiwwLHNpZykKbWlzc2luZyA9IHNvcnQoc2FtcGxlKDE6bixzaXplPWQscmVwbGFjZT1GQUxTRSkpCnkgPSBjKHkxWy1taXNzaW5nXSx5MVttaXNzaW5nXSkKeCA9IGMoeDFbLW1pc3NpbmddLHgxW21pc3NpbmddKQogCnBhcihtZnJvdz1jKDEsMSkpCnBsb3QoeCx5LHBjaD0xNikKcG9pbnRzKHhbKG4tZCsxKTpuXSx5WyhuLWQrMSk6bl0sY29sPTQscGNoPTE2LGNleD0yKQphYmxpbmUobG0oeX54KSRjb2VmLGNvbD00LGx3ZD0yKQphYmxpbmUobG0oeVsxOihuLWQpXX54WzE6KG4tZCldKSRjb2VmLGNvbD0xLGx3ZD0yKQpsZWdlbmQoInRvcGxlZnQiLGxlZ2VuZD1jKCJPTFMgZml0IG4tZHMgb2JzIiwKIk9MUyBmaXQgbiBvYnMiKSxjb2w9YygxLDQpLGx3ZD0yKQpgYGAKCiMgT0xTIGVzdGltYXRpb24KCiMjIE9MUyBiYXNlZCBvbiAkbiQgb2JzZXJ2YXRpb25zCgpgYGB7cn0Kb2xzID0gbG0oeX54KQpzdW1tYXJ5KG9scykKYGBgCgojIyBPTFMgYmFzZWQgb24gJG4tZCQgb2JzZXJ2YXRpb25zCmBgYHtyfQpvbHMgPSBsbSh5WzE6KG4tZCldfnhbMToobi1kKV0pCnN1bW1hcnkob2xzKQpgYGAKCiMgQmF5ZXNpYW4gaW5mZXJlbmNlIApXZSB3aWxsIGFzc3VtZSB0aGUgbWlzc2luZyB2YWx1ZXMgYXJlIGNvbXBsZXRlbHkgYXQgcmFuZG9tIGFuZCBwZXJmb3JtIEJheWVzaWFuIGluZmVyZW5jZSB3aGVyZSB0aGUgdW5rbm93bnMgYXJlCiQkClx0aGV0YSA9IChcYWxwaGEsXGJldGEsXHNpZ21hXjIseF97ZCsxfSxcbGRvdHMseF9uKSwKJCQKd2l0aCBpbmRlcGVuZGVudCBwcmlvcgokJApwKFx0aGV0YSkgPSBwKFxhbHBoYSlwKFxiZXRhKXAoXHNpZ21hXjIpXHByb2Rfe2k9KG4tZCkrMX1ebiBwKHhfe24tZCtpfSksCiQkCndoZXJlICRcbXUgXHNpbSBOKGFfMCxBXzApJCwgJFxiZXRhIFxzaW0gTihiXzAsQl8wKSQgYW5kICRcc2lnbWFeMiBcc2ltIElHKGNfMCxkXzApJC4gIEhlcmUsIHdlIHdpbGwgdHJ5IHR3byBub25pbmZvcm1hdGl2ZSBwcmlvcnMgZm9yICR4X3tuLWQraX0kOgpcYmVnaW57ZXFuYXJyYXkqfQpcbWJveHtQcmlvciBJfSAmOiYgeF97bi1kK2l9IFxzaW0gTigwLDEpLCBcIFwgXG1ib3h7Zm9yfSBcIFwgaT0xLFxsZG90cyxkXFwKXG1ib3h7UHJpb3IgSUl9ICY6JiB4X3tuLWQraX0gXHNpbSBVKHhfe21pbn0seF97bWF4fSksIFwgXCBcbWJveHtmb3J9IFwgXCBpPTEsXGxkb3RzLGQuClxlbmR7ZXFuYXJyYXkqfQoKYGBge3J9CmEwICAgPSAwCkEwICAgPSAxCmIwICAgPSAwCkIwICAgPSAxCmMwICAgPSAzCmQwICAgPSA0CnhtaW4gPSBtaW4oeFsxOihuLWQpXSkKeG1heCA9IG1heCh4WzE6KG4tZCldKQpgYGAKCiMjIEdpYmJzIHNhbXBsZXIKVGhlIE1DTUMgc2NoZW1lIGN5Y2xlcyB0aHJvdWdoIHRoZSBmb2xsb3dpbmcgJGQrMyQgZnVsbCBjb25kaXRpb25hbHM6ClxiZWdpbntlcW5hcnJheSp9CnAoXGFscGhhfHlfezE6bn0seF97MTpufSxcYmV0YSxcc2lnbWFeMilcXApwKFxiZXRhfHlfezE6bn0seF97MTpufSxcYmV0YSxcc2lnbWFeMilcXApwKFxzaWdtYV4yfHlfezE6bn0seF97MTpufSxcYmV0YSxcc2lnbWFeMilcXApwKHhfaXx5X3sxOm59LHhfey1pfSxcYWxwaGEsXGJldGEsXHNpZ21hXjIpLApcZW5ke2VxbmFycmF5Kn0KZm9yICRpPW4tZCsxLFxsZG90cyxuJC4gIFNob3cgdGhhdCB0aGVzZSBmdWxsIGNvbmRpdGlvbmFscyBhcmUgYXMgZm9sbG93cy4KXGJlZ2lue2VxbmFycmF5Kn0KW1xhbHBoYV0gJlxzaW0mIE5cbGVmdFx7XGxlZnQoXGZyYWN7MX17QV8wfStcZnJhY3tufXtcc2lnbWFeMn1ccmlnaHQpXnstMX1cbGVmdCgKXGZyYWN7YV8wfXtBXzB9K1xmcmFje1xzdW1fe2k9MX1ebiAoeV9pLVxiZXRhIHhfaSl9e1xzaWdtYV4yfQpccmlnaHQpCjtcbGVmdChcZnJhY3sxfXtBXzB9K1xmcmFje259e1xzaWdtYV4yfVxyaWdodCleey0xfVxyaWdodFx9XFwKW1xiZXRhXSAmXHNpbSYgTlxsZWZ0XHtcbGVmdChcZnJhY3sxfXtCXzB9K1xmcmFje1xzdW1fe2k9MX1ebiB4X2leMn17XHNpZ21hXjJ9XHJpZ2h0KV57LTF9XGxlZnQoClxmcmFje2JfMH17Ql8wfStcZnJhY3tcc3VtX3tpPTF9Xm4gKHlfaS1cYWxwaGEpeF9pfXtcc2lnbWFeMn0KXHJpZ2h0KQo7XGxlZnQoXGZyYWN7MX17Ql8wfStcZnJhY3tcc3VtX3tpPTF9Xm4geF9pXjJ9e1xzaWdtYV4yfVxyaWdodCleey0xfVxyaWdodFx9XFwKW1xzaWdtYV4yXSAmXHNpbSYgSUdcbGVmdFx7Y18wK1xmcmFje259ezJ9O2RfMCtcZnJhY3tcc3VtX3tpPTF9Xm4gKHlfaS1cYWxwaGEtXGJldGEgeF9pKS9cc2lnbWFeMn17Mn1ccmlnaHRcfVxcClt4X2ldICZcc2ltJiBcbGVmdFx7ClxiZWdpbnthcnJheX17bGx9Ck5cbGVmdFx7ClxsZWZ0KDErXGZyYWN7XGJldGFeMn17XHNpZ21hXjJ9XHJpZ2h0KV57LTF9XGJldGEoeV9pLVxhbHBoYSk7ClxsZWZ0KDErXGZyYWN7XGJldGFeMn17XHNpZ21hXjJ9XHJpZ2h0KV57LTF9XHJpZ2h0XH0sIFxxcXVhZCBpPW4tZCsxLFxsZG90cyxuICYgXG1ib3h7UHJpb3IgSX1cXApOX3tbeF97bWlufSx4X3ttYXh9XX1cbGVmdChcZnJhY3t5X2ktXGFscGhhfXtcYmV0YX07XGZyYWN7XHNpZ21hXjJ9e1xiZXRhXjJ9XHJpZ2h0KSYgXG1ib3h7UHJpb3IgSUl9ClxlbmR7YXJyYXl9ClxyaWdodC4KXGVuZHtlcW5hcnJheSp9CgojIyBQcmlvciBJIGZvciBtaXNzaW5nCgpgYGB7cn0KIyBJbml0aWFsIHZhbHVlcwp4bWlzcyA9IHJlcChtZWFuKHhbMToobi1kKV0pLGQpCmFscGhhID0gMApiZXRhICA9IDAKCiMgTWFya292IGNoYWluIHBhcmFtZXRlcnMKTTAgICAgPSAxMDAwMApNICAgICA9IDEwMDAwCm5pdGVyID0gTTArTQpkcmF3cyA9IG1hdHJpeCgwLG5pdGVyLDMrZCkKCiMgR2liYnMgc2FtcGxlcgpmb3IgKGl0ZXIgaW4gMTpuaXRlcil7CiAgeHggICAgPSBjKHhbMToobi1kKV0seG1pc3MpCiAgCiAgIyBTYW1wbGluZyBzaWcyCiAgc2lnMiA9IDEvcmdhbW1hKDEsYzArbi8yLGQwKyhzdW0oKHktYWxwaGEtYmV0YSp4eCleMikpLzIpCgogICMgU2FtcGxpbmcgYWxwaGEKICBBMSA9IDEvKDEvQTArbi9zaWcyKQogIGExID0gQTEqKGEwL0EwK3N1bSh5LWJldGEqeHgpL3NpZzIpCiAgYWxwaGEgPSBybm9ybSgxLGExLHNxcnQoQTEpKQoKICAjIFNhbXBsaW5nIGJldGEKICBCMSA9IDEvKDEvQjArc3VtKHh4XjIpL3NpZzIpCiAgYjEgPSBCMSooYjAvQjArc3VtKCh5LWFscGhhKSp4eCkvc2lnMikKICBiZXRhID0gcm5vcm0oMSxiMSxzcXJ0KEIxKSkKCiAgIyBTYW1wbGluZyBtaXNzaW5nIHgncwogIHZ4ICAgID0gMS8oMStiZXRhXjIvc2lnMikKICBteCAgICA9IHZ4KihiZXRhKih5WyhuLWQrMSk6bl0tYWxwaGEpL3NpZzIpCiAgeG1pc3MgPSBybm9ybShkLG14LHNxcnQodngpKQoKICAjIFN0b3JpbmcgdGhlIE1vbnRlIENhcmxvIGNoYWlucwogIGRyYXdzW2l0ZXIsXSA9IGMoYWxwaGEsYmV0YSxzcXJ0KHNpZzIpLHhtaXNzKQp9CmRyYXdzSSA9IGRyYXdzWyhNMCsxKTpuaXRlcixdCmBgYAoKIyMgUHJpb3IgSUkgZm9yIG1pc3NpbmcKCmBgYHtyfQojIGRyYXdzaW5nIHRydW5jYXRlZCBub3JtYWwKcnRydW5jbm9ybSA9IGZ1bmN0aW9uKG11LHNpZyxhLGIpewogIEEgPSBwbm9ybShiLG11LHNpZykKICBCID0gcG5vcm0oYSxtdSxzaWcpCiAgdSA9IHJ1bmlmKDEpCiAgbXUrc2lnKnFub3JtKHUqQS11KkIrQikKfQoKIyBJbml0aWFsIHZhbHVlcwp4bWlzcyA9IHJlcChtZWFuKHhbMToobi1kKV0pLGQpCmFscGhhID0gMApiZXRhICA9IDAKCiMgTWFya292IGNoYWluIHBhcmFtZXRlcnMKTTAgICAgPSAxMDAwMApNICAgICA9IDEwMDAwCm5pdGVyID0gTTArTQpkcmF3cyA9IG1hdHJpeCgwLG5pdGVyLDMrZCkKCiMgR2liYnMgc2FtcGxlcgpmb3IgKGl0ZXIgaW4gMTpuaXRlcil7CiAgeHggICAgPSBjKHhbMToobi1kKV0seG1pc3MpCiAgCiAgIyBTYW1wbGluZyBzaWcyCiAgc2lnMiA9IDEvcmdhbW1hKDEsYzArbi8yLGQwKyhzdW0oKHktYWxwaGEtYmV0YSp4eCleMikpLzIpCgogICMgU2FtcGxpbmcgYWxwaGEKICBBMSA9IDEvKDEvQTArbi9zaWcyKQogIGExID0gQTEqKGEwL0EwK3N1bSh5LWJldGEqeHgpL3NpZzIpCiAgYWxwaGEgPSBybm9ybSgxLGExLHNxcnQoQTEpKQoKICAjIFNhbXBsaW5nIGJldGEKICBCMSA9IDEvKDEvQjArc3VtKHh4XjIpL3NpZzIpCiAgYjEgPSBCMSooYjAvQjArc3VtKCh5LWFscGhhKSp4eCkvc2lnMikKICBiZXRhID0gcm5vcm0oMSxiMSxzcXJ0KEIxKSkKCiAgIyBTYW1wbGluZyBtaXNzaW5nIHgncwogIG14ID0gKHlbKG4tZCsxKTpuXS1hbHBoYSkvYmV0YQogIHZ4ID0gc2lnMi9iZXRhXjIKICB4bWlzcyA9IHJ0cnVuY25vcm0obXgsc3FydCh2eCkseG1pbix4bWF4KQoKICAjIFN0b3JpbmcgdGhlIE1vbnRlIENhcmxvIGNoYWlucwogIGRyYXdzW2l0ZXIsXSA9IGMoYWxwaGEsYmV0YSxzcXJ0KHNpZzIpLHhtaXNzKQp9CmRyYXdzSUkgPSBkcmF3c1soTTArMSk6bml0ZXIsXQpgYGAKCiMjIFRyYWNlIHBsb3RzLCBhY2ZzIGFuZCBtYXJnaW5hbCBwb3N0ZXJpb3JzCmBgYHtyIGZpZy53aWR0aD0xMiwgZmlnLmhlaWdodD0xMH0KcGFyKG1mcm93PWMoMywyKSkKdHMucGxvdChkcmF3c0lbLDFdLHhsYWI9Ikl0ZXJhdGlvbnMiLHlsYWI9IiIsbWFpbj1leHByZXNzaW9uKGFscGhhKSkKbGluZXMoZHJhd3NJSVssMV0sY29sPTIpCmhpc3QoZHJhd3NJWywxXSxwcm9iPVRSVUUsbWFpbj0iIix4bGFiPWV4cHJlc3Npb24oYWxwaGEpKQpsaW5lcyhkZW5zaXR5KGRyYXdzSUlbLDFdKSxjb2w9MikKYWJsaW5lKHY9dHJ1ZVsxXSxjb2w9Myxsd2Q9MykKCnRzLnBsb3QoZHJhd3NJWywyXSx4bGFiPSJJdGVyYXRpb25zIix5bGFiPSIiLG1haW49ZXhwcmVzc2lvbihiZXRhKSkKbGluZXMoZHJhd3NJSVssMl0sY29sPTIpCmhpc3QoZHJhd3NJWywyXSxwcm9iPVRSVUUsbWFpbj0iIix4bGFiPWV4cHJlc3Npb24oYmV0YSkpCmxpbmVzKGRlbnNpdHkoZHJhd3NJSVssMl0pLGNvbD0yKQphYmxpbmUodj10cnVlWzJdLGNvbD0zLGx3ZD0zKQoKdHMucGxvdChkcmF3c0lbLDNdLHhsYWI9Ikl0ZXJhdGlvbnMiLHlsYWI9IiIsbWFpbj1leHByZXNzaW9uKHNpZ21hKSkKbGluZXMoZHJhd3NJSVssM10sY29sPTIpCmhpc3QoZHJhd3NJWywzXSxwcm9iPVRSVUUsbWFpbj0iIix4bGFiPWV4cHJlc3Npb24oYmV0YSkpCmxpbmVzKGRlbnNpdHkoZHJhd3NJSVssM10pLGNvbD0yKQphYmxpbmUodj10cnVlWzNdLGNvbD0zLGx3ZD0zKQpgYGAKCiMjIEJpdmFyaWF0ZSBtYXJnaW5hbCBwb3N0ZXJpb3JzCgpgYGB7ciBmaWcud2lkdGg9MTIsIGZpZy5oZWlnaHQ9MTB9CnBhcihtZnJvdz1jKDIsMykpCnBsb3QoZHJhd3NJWywxXSxkcmF3c0lbLDJdLHhsYWI9ZXhwcmVzc2lvbihhbHBoYSkseWxhYj1leHByZXNzaW9uKGJldGEpKQpwbG90KGRyYXdzSVssMV0sZHJhd3NJWywzXSx4bGFiPWV4cHJlc3Npb24oYWxwaGEpLHlsYWI9ZXhwcmVzc2lvbihzaWdtYSkpCnBsb3QoZHJhd3NJWywyXSxkcmF3c0lbLDNdLHhsYWI9ZXhwcmVzc2lvbihiZXRhKSx5bGFiPWV4cHJlc3Npb24oc2lnbWEpKQpwbG90KGRyYXdzSUlbLDFdLGRyYXdzSUlbLDJdLHhsYWI9ZXhwcmVzc2lvbihhbHBoYSkseWxhYj1leHByZXNzaW9uKGJldGEpKQpwbG90KGRyYXdzSUlbLDFdLGRyYXdzSUlbLDNdLHhsYWI9ZXhwcmVzc2lvbihhbHBoYSkseWxhYj1leHByZXNzaW9uKHNpZ21hKSkKcGxvdChkcmF3c0lJWywyXSxkcmF3c0lJWywzXSx4bGFiPWV4cHJlc3Npb24oYmV0YSkseWxhYj1leHByZXNzaW9uKHNpZ21hKSkKYGBgCgojIyMgRXN0aW1hdGluZyB0aGUgbWlzc2luZyB2YWx1ZXMKCmBgYHtyIGZpZy53aWR0aD0xMiwgZmlnLmhlaWdodD0xMH0KcXggICA9IHQoYXBwbHkocmJpbmQoZHJhd3NJWyw0OigzK2QpXSxkcmF3c0lbLDQ6KDMrZCldKSwyLHF1YW50aWxlLGMoMC4yNSwwLjUsMC43NSkpKQpxeEkgID0gdChhcHBseShkcmF3c0lbLDQ6KDMrZCldLDIscXVhbnRpbGUsYygwLjI1LDAuNSwwLjc1KSkpCnF4SUkgPSB0KGFwcGx5KGRyYXdzSUlbLDQ6KDMrZCldLDIscXVhbnRpbGUsYygwLjI1LDAuNSwwLjc1KSkpCgpwYXIobWZyb3c9YygxLDIpKQpwbG90KHgseSxwY2g9MTYseGxpbT1yYW5nZSh4LHF4KSxtYWluPSJQcmlvciBJIikKcG9pbnRzKHhbKG4tZCsxKTpuXSx5WyhuLWQrMSk6bl0sY29sPTQscGNoPTE2LGNleD0xLjIpCnBvaW50cyhxeElbLDJdLHlbKG4tZCsxKTpuXSxjb2w9NixwY2g9MTYsY2V4PTEuMikKZm9yIChpIGluIDE6ZCkKICBzZWdtZW50cyhxeElbaSwxXSx5W24tZCtpXSxxeElbaSwzXSx5W24tZCtpXSxjb2w9NikKCnBsb3QoeCx5LHBjaD0xNix4bGltPXJhbmdlKHgscXgpLG1haW49IlByaW9yIElJIikKcG9pbnRzKHhbKG4tZCsxKTpuXSx5WyhuLWQrMSk6bl0sY29sPTQscGNoPTE2LGNleD0xLjIpCnBvaW50cyhxeElJWywyXSx5WyhuLWQrMSk6bl0sY29sPTYscGNoPTE2LGNleD0xLjIpCmZvciAoaSBpbiAxOmQpCiAgc2VnbWVudHMocXhJSVtpLDFdLHlbbi1kK2ldLHF4SUlbaSwzXSx5W24tZCtpXSxjb2w9NikKYGBgCgoKIyMjIENvbXBhcmluZyBsaW5lYXIgcHJlZGljdG9ycwpgYGB7ciBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD02fQp4eHggPSBzZXEobWluKHgpLG1heCh4KSxsZW5ndGg9MTAwKQpmeCAgPSBhcnJheSgwLGMoMixNLDEwMCkpCmZvciAoaSBpbiAxOjEwMCl7CiAgZnhbMSwsaV0gPSBkcmF3c0lbLDFdK2RyYXdzSVssMl0qeHh4W2ldCiAgZnhbMiwsaV0gPSBkcmF3c0lJWywxXStkcmF3c0lJWywyXSp4eHhbaV0KfQpxZnhJICA9IHQoYXBwbHkoZnhbMSwsXSwyLHF1YW50aWxlLGMoMC4yNSwwLjUsMC43NSkpKQpxZnhJSSA9IHQoYXBwbHkoZnhbMiwsXSwyLHF1YW50aWxlLGMoMC4yNSwwLjUsMC43NSkpKQoKcGFyKG1mcm93PWMoMSwxKSkKcGxvdCh4LHkscGNoPTE2LHhsaW09cmFuZ2UoeCxxeCkpCnBvaW50cyh4WyhuLWQrMSk6bl0seVsobi1kKzEpOm5dLGNvbD00LHBjaD0xNixjZXg9MS4yKQpsaW5lcyh4eHgscWZ4SVssMV0sY29sPTIsbHR5PTIsbHdkPTIpCmxpbmVzKHh4eCxxZnhJWywyXSxjb2w9Mixsd2Q9MikKbGluZXMoeHh4LHFmeElbLDNdLGNvbD0yLGx0eT0yLGx3ZD0yKQpsaW5lcyh4eHgscWZ4SUlbLDFdLGNvbD0zLGx0eT0yLGx3ZD0yKQpsaW5lcyh4eHgscWZ4SUlbLDJdLGNvbD0zLGx3ZD0yKQpsaW5lcyh4eHgscWZ4SUlbLDNdLGNvbD0zLGx0eT0yLGx3ZD0yKQphYmxpbmUobG0oeVsxOihuLWQpXX54WzE6KG4tZCldKSRjb2VmLGx3ZD0yKQphYmxpbmUobG0oeX54KSRjb2VmLGNvbD00LGx3ZD0yKQpsZWdlbmQoInRvcGxlZnQiLGxlZ2VuZD1jKCJPTFMgKG4tZCkiLCJPTFMgKG4pIiwiQmF5ZXMgKFByaW9yIEkpIiwiQmF5ZXMgKFByaW9yIElJKSIpLGNvbD1jKDEsNCwyLDMpLGx3ZD0yKQpgYGAKCg==