1 The model

In this illustration we will consider a simple and Gaussian linear regression model where the errors follow a first order autogressive structure, where, for \(t=1,\ldots,n\), \[\begin{eqnarray*} y_t &=& \beta x_t + u_t\\ u_t &=& \rho u_{t-1} + \epsilon_t \end{eqnarray*}\] where \(\epsilon_t\)s follows a Gaussian white noise process with variance \(\sigma^2\). This is studied, amongst various extensions, where studied in Zellner and Tiao (1964) Bayesian Analysis of the Regression Model With Autocorrelated Errors, Journal of the American Statistical Association (JASA), 59, 763-778. The paper can be downloaded freely from either https://www.jstor.org/stable/2283097 or https://doi.org/10.2307/2283097.

2 The data

In one of their exercises, \(\beta=3\), \(\sigma^2=1\) and \(\rho=0.5\) (case I) or \(\rho=1.25\) (case II), and \(n=16\). The \(x\)’s are rescaled investment expenditures taken from Haavelmo (1947) Methods of measuring the marginal propensity to consume, JASA, 42, 105-22, which can be downloaded freely from either https://www.jstor.org/stable/2280191 or https://doi.org/10.2307/2280191.

x=c(3.0,3.9,6.0,4.2,5.2,4.7,5.1,4.5,6.0,3.9,4.1,2.2,1.7,2.7,3.3,4.8)
y1=c(9.500,12.649,18.794,12.198,14.372,13.909,14.556,14.700,18.281,
     13.890,10.318,5.473,4.044,6.361,7.036,13.368)
y2=c(9.500,13.024,19.975,14.270,16.760,15.923,16.931,17.111,22.195,
     18.992,18.338,14.012,13.873,17.855,20.099,27.549)
n = length(x)

par(mfrow=c(2,3))
plot(x,y1,type="n",col=0)
text(x,y1,label=1:n,col='blue')
ts.plot(y1-3*x)
acf(y1-3*x)

plot(x,y2,type="n",col=0)
text(x,y2,label=1:n,col='blue')
ts.plot(y2-3*x)
acf(y2-3*x)

3 Simple OLS fits

fit1 = lm(y1~x)
summary(fit1)
## 
## Call:
## lm(formula = y1 ~ x)
## 
## Residuals:
##      Min       1Q   Median       3Q      Max 
## -2.20858 -0.86812 -0.01237  0.74634  2.65171 
## 
## Coefficients:
##             Estimate Std. Error t value Pr(>|t|)    
## (Intercept)  -1.7209     1.1427  -1.506    0.154    
## x             3.3229     0.2683  12.385 6.23e-09 ***
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 1.306 on 14 degrees of freedom
## Multiple R-squared:  0.9164, Adjusted R-squared:  0.9104 
## F-statistic: 153.4 on 1 and 14 DF,  p-value: 6.231e-09
fit2 = lm(y2~x)
summary(fit2)
## 
## Call:
## lm(formula = y2 ~ x)
## 
## Residuals:
##     Min      1Q  Median      3Q     Max 
## -5.9539 -2.3962 -0.3135  1.7708  9.0627 
## 
## Coefficients:
##             Estimate Std. Error t value Pr(>|t|)   
## (Intercept)  10.3998     3.2577   3.192  0.00652 **
## x             1.6847     0.7649   2.202  0.04489 * 
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 3.724 on 14 degrees of freedom
## Multiple R-squared:  0.2573, Adjusted R-squared:  0.2043 
## F-statistic: 4.851 on 1 and 14 DF,  p-value: 0.04489

3.1 Residual plots of the OLS fits

u1 = fit1$res
u2 = fit2$res
par(mfrow=c(1,2))
plot(u1,type="b")
plot(u2,type="b")

3.2 Fitting AR(1) to the residuals

summary(lm(u1[2:n]~u1[1:(n-1)]))
## 
## Call:
## lm(formula = u1[2:n] ~ u1[1:(n - 1)])
## 
## Residuals:
##      Min       1Q   Median       3Q      Max 
## -2.05668 -0.71217  0.04631  0.38774  2.73466 
## 
## Coefficients:
##               Estimate Std. Error t value Pr(>|t|)
## (Intercept)   -0.08763    0.33698  -0.260    0.799
## u1[1:(n - 1)]  0.07222    0.27126   0.266    0.794
## 
## Residual standard error: 1.304 on 13 degrees of freedom
## Multiple R-squared:  0.005423,   Adjusted R-squared:  -0.07108 
## F-statistic: 0.07088 on 1 and 13 DF,  p-value: 0.7942
summary(lm(u2[2:n]~u2[1:(n-1)]))
## 
## Call:
## lm(formula = u2[2:n] ~ u2[1:(n - 1)])
## 
## Residuals:
##     Min      1Q  Median      3Q     Max 
## -3.6734 -0.8364 -0.2031  1.1456  3.9352 
## 
## Coefficients:
##               Estimate Std. Error t value Pr(>|t|)    
## (Intercept)     0.9994     0.5213   1.917 0.077438 .  
## u2[1:(n - 1)]   0.9972     0.1907   5.228 0.000163 ***
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 1.969 on 13 degrees of freedom
## Multiple R-squared:  0.6777, Adjusted R-squared:  0.6529 
## F-statistic: 27.34 on 1 and 13 DF,  p-value: 0.0001628

4 Likelihood and prior

It is easy to see that \[\begin{eqnarray*} y_t &=& \beta x_t + u_t\\ \rho y_{t-1} &=& \rho \beta x_{t-1} + \rho u_{t-1}, \end{eqnarray*}\] such that \[ y_t - \rho y_{t-1} = \beta (x_t-\rho x_{t-1}) + \epsilon_t. \] So, for the sake of the exercise, assume that the likelihood is conditional on \(y_1\) and \(x_1\). Therefore \[ p(y_{2:n}|x_{2:n},\theta) \propto (\sigma^2)^{-(n-1)/2}\exp\left\{-\frac{1}{\sigma^2} \sum_{t=2}^n (y_t - \rho y_{t-1} - \beta (x_t-\rho x_{t-1}))^2 \right\}, \] and assume that the prior for \(\theta=(\beta,\rho,\sigma^2)\) is \[ p(\beta,\rho,\sigma^2) \propto \frac{1}{\sigma^2}. \]

5 Contours of \(p(\beta,\rho|\mbox{data})\)

loglikelihoodprior = function(y,x,beta,rho,sig){
  sum(dnorm(y[2:n],rho*y[1:(n-1)]+beta*(x[2:n]-rho*x[1:(n-1)]),sig,log=TRUE))-2*log(sig)
}
M = 200
betas = seq(1,4.5,length=M)
rhos  = seq(-2,2,length=M)
sigs  = seq(0.1,4,length=M)
post  = array(0,c(M,M,M))
post2 = matrix(0,M,M)
for (i in 1:M)
  for (j in 1:M)
    for (k in 1:M)
      post[i,j,k] = loglikelihoodprior(y1,x,betas[i],rhos[j],sigs[k])
max = max(post)
for (i in 1:M)
  for (j in 1:M)
    post2[i,j] = sum(exp(post[i,j,]-max))

contour(betas,rhos,post2,xlab=expression(beta),ylab=expression(rho),nlevels=20,
        xlim=c(1,4),ylim=c(-1,2),drawlabels=FALSE)

6 SIR-based posterior inference for the case I dataset (\(\rho=0.5\))

M = 100000
beta0 = runif(M,-5,5)
rho0 = runif(M,-3,3)
sig0 = runif(M,0.01,4)
w = rep(0,M)
for (i in 1:M)
  w[i] = loglikelihoodprior(y1,x,beta0[i],rho0[i],sig0[i])
w = exp(w-max(w))
k = sample(1:M,size=M,replace=TRUE,prob=w)
beta = beta0[k]
rho  = rho0[k]
sig  = sig0[k]

draws.sir = cbind(beta,rho,sig)

par(mfrow=c(2,2))
hist(beta,main=expression(beta),ylab="Posterior",xlab="",prob=TRUE)
legend("topright",legend=c(
paste("5th perc.=",round(quantile(beta,0.05),2),sep=""),
paste("50th perc.=",round(quantile(beta,0.5),2),sep=""),
paste("95th perc.=",round(quantile(beta,0.95),2),sep="")),bty="n")                          
abline(v=3,lwd=2,col=2)
hist(rho,main=expression(rho),ylab="Posterior",xlab="",prob=TRUE)
legend("topright",legend=c(
paste("5th perc.=",round(quantile(rho,0.05),2),sep=""),
paste("50th perc.=",round(quantile(rho,0.5),2),sep=""),
paste("95th perc.=",round(quantile(rho,0.95),2),sep="")),bty="n")                          
hist(sig,main=expression(sig),ylab="Posterior",xlab="",prob=TRUE)
legend("topright",legend=c(
paste("5th perc.=",round(quantile(sig,0.05),2),sep=""),
paste("50th perc.=",round(quantile(sig,0.5),2),sep=""),
paste("95th perc.=",round(quantile(sig,0.95),2),sep="")),bty="n")
abline(v=1,lwd=2,col=2)

plot(beta,rho,xlab=expression(beta),ylab=expression(rho))
contour(betas,rhos,post2,add=TRUE,col=3,nlevels=20,drawlabels=FALSE)

7 Gibbs sampler

We need to derive the full conditional distributions in order to implement the Gibbs sampler.

7.1 \(p(\sigma^2|\beta,\rho,x_{2:n},y_{2:n})\)

Conditional on \((\beta,\rho)\), the full conditional distribution of \(\sigma^2\) is inverse-gamma with parameters \((n-1)/2\) and \(\sum_{t=2}^n (y_t-\rho y_{t-1}-\beta x_t-\rho\beta x_{t-1})^2/2\): \[ p(\sigma^2|\beta,\rho,x_{2:n},y_{2:n}) \propto \sigma^{-\left(\frac{n-1}{2}+1\right)} \exp\left\{-\frac{1}{2\sigma^2} \sum_{t=2}^n (y_t-\rho y_{t-1}-\beta x_t+\rho\beta x_{t-1})^2\right\} \]

7.2 \(p(\beta|\rho,\sigma^2,x_{2:n},y_{2:n})\)

Conditional on \((\rho,\sigma^2)\), the full conditional distribution of \(\beta\) takes advantage of the following regression set up: \[ \underbrace{y_t - \rho y_{t-1}}_{{\tilde y}_t} = \beta (\underbrace{x_t - \rho x_{t-1}}_{{\tilde x}_t}) + \epsilon_t, \] such that \[ (\beta|\rho,\sigma^2,x_{2:n},y_{2:n}) \sim N\left( \frac{\sum_{t=2}^n (y_t-\rho y_{t-1})(x_t-\rho x_{t-1})} {\sum_{t=2}^n (x_{t-1}-\rho x_{t-1})^2};\frac{\sigma^2}{\sum_{t=2}^n (x_{t-1}-\rho x_{t-1})^2} \right). \]

7.3 \(p(\rho|\beta,\sigma^2,x_{2:n},y_{2:n})\)

Conditional on \((\beta,\sigma^2)\), the full conditional distribution of \(\rho\) takes advantage of the following regression set up: \[ \underbrace{y_t - \beta x_t}_{{\tilde y}_t} = \rho (\underbrace{y_{t-1} - \beta x_{t-1}}_{{\tilde x}_t}) + \epsilon_t, \] such that \[ (\rho|\beta,\sigma^2,x_{2:n},y_{2:n}) \sim N\left( \frac{\sum_{t=2}^n (y_t-\beta x_t)(y_{t-1}-\beta x_{t-1})} {\sum_{t=2}^n (y_{t-1}-\beta x_{t-1})^2};\frac{\sigma^2}{\sum_{t=2}^n (y_{t-1}-\beta x_{t-1})^2}\right). \]

y = y1

sig2 = 1
beta = 3
rho  = 0.5

niter = 10000
draws = matrix(0,niter,3)

for (iter in 1:niter){
# Full conditional of sigma2
z    = y[2:n]-rho*y[1:(n-1)]-beta*x[2:n]+rho*beta*x[1:(n-1)]
sig2 = 1/rgamma(1,(n-1)/2,sum(z^2)/2)

# Full conditional of beta
yt   = y[2:n]-rho*y[1:(n-1)]
xt   = x[2:n]-rho*x[1:(n-1)]
beta = rnorm(1,sum(yt*xt)/sum(xt^2),sqrt(sig2/sum(xt^2)))

# Full conditional of rho
yt  = y[2:n]-beta*x[2:n]
xt  = y[1:(n-1)]-beta*x[1:(n-1)]
rho = rnorm(1,sum(yt*xt)/sum(xt^2),sqrt(sig2/sum(xt^2)))

draws[iter,] = c(beta,rho,sqrt(sig2))
}

draws.gibbs = draws

par(mfrow=c(2,3))
ts.plot(draws[,1],xlab="Iterations",ylab="",main=expression(beta))
ts.plot(draws[,2],xlab="Iterations",ylab="",main=expression(rho))
ts.plot(draws[,3],xlab="Iterations",ylab="",main=expression(sigma))
hist(draws[,1],prob=TRUE,xlab="",main="")
hist(draws[,2],prob=TRUE,xlab="",main="")
hist(draws[,3],prob=TRUE,xlab="",main="")

8 Comparing SIR and Gibbs sampler

par(mfrow=c(2,2))
hist(draws.sir[,1],prob=TRUE,xlab="",main=expression(beta))
lines(density(draws.gibbs[,1]),col=2)
abline(v=3,col=3,lwd=3)
legend("topright",legend=c("SIR","GIBBS"),col=c(1,2),lwd=3)
hist(draws.sir[,2],prob=TRUE,xlab="",main=expression(rho))
lines(density(draws.gibbs[,2]),col=2)
abline(v=0.5,col=3,lwd=3)
hist(draws.sir[,3],prob=TRUE,xlab="",main=expression(sigma))
lines(density(draws.gibbs[,3]),col=2)
abline(v=1,col=3,lwd=3)
plot(draws.sir[,1],draws.sir[,2],xlab=expression(beta),ylab=expression(rho))
points(draws.gibbs[,1],draws.gibbs[,2],col=2)

LS0tCnRpdGxlOiAiUmVncmVzc2lvbiBNb2RlbCBXaXRoIEF1dG9jb3JyZWxhdGVkIEVycm9ycyIKc3VidGl0bGU6ICJCYXNlZCBvbiBaZWxsbmVyIGFuZCBUaWFvICgxOTY0KSBKQVNBIHBhcGVyIgphdXRob3I6ICJIZWRpYmVydCBGcmVpdGFzIExvcGVzIgpkYXRlOiAiMi8zLzIwMjIiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDIKICAgIGNvZGVfZG93bmxvYWQ6IHllcwogICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCi0tLQoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSkKYGBgCgojIFRoZSBtb2RlbApJbiB0aGlzIGlsbHVzdHJhdGlvbiB3ZSB3aWxsIGNvbnNpZGVyIGEgc2ltcGxlIGFuZCBHYXVzc2lhbiBsaW5lYXIgcmVncmVzc2lvbiBtb2RlbCB3aGVyZSB0aGUgZXJyb3JzIGZvbGxvdyBhIGZpcnN0IG9yZGVyIGF1dG9ncmVzc2l2ZSBzdHJ1Y3R1cmUsIHdoZXJlLCBmb3IgJHQ9MSxcbGRvdHMsbiQsClxiZWdpbntlcW5hcnJheSp9CnlfdCAmPSYgXGJldGEgeF90ICsgdV90XFwKdV90ICY9JiBccmhvIHVfe3QtMX0gKyBcZXBzaWxvbl90ClxlbmR7ZXFuYXJyYXkqfQp3aGVyZSAkXGVwc2lsb25fdCRzIGZvbGxvd3MgYSBHYXVzc2lhbiB3aGl0ZSBub2lzZSBwcm9jZXNzIHdpdGggdmFyaWFuY2UgJFxzaWdtYV4yJC4gIFRoaXMgaXMgc3R1ZGllZCwgYW1vbmdzdCB2YXJpb3VzIGV4dGVuc2lvbnMsIHdoZXJlIHN0dWRpZWQgaW4gWmVsbG5lciBhbmQgVGlhbyAoMTk2NCkgQmF5ZXNpYW4gQW5hbHlzaXMgb2YgdGhlIFJlZ3Jlc3Npb24gTW9kZWwgV2l0aCBBdXRvY29ycmVsYXRlZCBFcnJvcnMsICpKb3VybmFsIG9mIHRoZSBBbWVyaWNhbiBTdGF0aXN0aWNhbCBBc3NvY2lhdGlvbiAoSkFTQSkqLCA1OSwgNzYzLTc3OC4gIFRoZSBwYXBlciBjYW4gYmUgZG93bmxvYWRlZCBmcmVlbHkgZnJvbSBlaXRoZXIKaHR0cHM6Ly93d3cuanN0b3Iub3JnL3N0YWJsZS8yMjgzMDk3IG9yIGh0dHBzOi8vZG9pLm9yZy8xMC4yMzA3LzIyODMwOTcuCgoKIyBUaGUgZGF0YQpJbiBvbmUgb2YgdGhlaXIgZXhlcmNpc2VzLCAkXGJldGE9MyQsICRcc2lnbWFeMj0xJCBhbmQgJFxyaG89MC41JCAoY2FzZSBJKSBvciAkXHJobz0xLjI1JCAoY2FzZSBJSSksIGFuZCAkbj0xNiQuICBUaGUgJHgkJ3MgYXJlIHJlc2NhbGVkIGludmVzdG1lbnQgZXhwZW5kaXR1cmVzIHRha2VuIGZyb20gSGFhdmVsbW8gKDE5NDcpIE1ldGhvZHMgb2YgbWVhc3VyaW5nIHRoZSBtYXJnaW5hbCBwcm9wZW5zaXR5IHRvIGNvbnN1bWUsICpKQVNBKiwgNDIsIDEwNS0yMiwgd2hpY2ggY2FuIGJlIGRvd25sb2FkZWQgZnJlZWx5IGZyb20gZWl0aGVyIGh0dHBzOi8vd3d3LmpzdG9yLm9yZy9zdGFibGUvMjI4MDE5MSBvciBodHRwczovL2RvaS5vcmcvMTAuMjMwNy8yMjgwMTkxLgoKYGBge3IgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTd9Cng9YygzLjAsMy45LDYuMCw0LjIsNS4yLDQuNyw1LjEsNC41LDYuMCwzLjksNC4xLDIuMiwxLjcsMi43LDMuMyw0LjgpCnkxPWMoOS41MDAsMTIuNjQ5LDE4Ljc5NCwxMi4xOTgsMTQuMzcyLDEzLjkwOSwxNC41NTYsMTQuNzAwLDE4LjI4MSwKICAgICAxMy44OTAsMTAuMzE4LDUuNDczLDQuMDQ0LDYuMzYxLDcuMDM2LDEzLjM2OCkKeTI9Yyg5LjUwMCwxMy4wMjQsMTkuOTc1LDE0LjI3MCwxNi43NjAsMTUuOTIzLDE2LjkzMSwxNy4xMTEsMjIuMTk1LAogICAgIDE4Ljk5MiwxOC4zMzgsMTQuMDEyLDEzLjg3MywxNy44NTUsMjAuMDk5LDI3LjU0OSkKbiA9IGxlbmd0aCh4KQoKcGFyKG1mcm93PWMoMiwzKSkKcGxvdCh4LHkxLHR5cGU9Im4iLGNvbD0wKQp0ZXh0KHgseTEsbGFiZWw9MTpuLGNvbD0nYmx1ZScpCnRzLnBsb3QoeTEtMyp4KQphY2YoeTEtMyp4KQoKcGxvdCh4LHkyLHR5cGU9Im4iLGNvbD0wKQp0ZXh0KHgseTIsbGFiZWw9MTpuLGNvbD0nYmx1ZScpCnRzLnBsb3QoeTItMyp4KQphY2YoeTItMyp4KQpgYGAKCgojIFNpbXBsZSBPTFMgZml0cwoKYGBge3J9CmZpdDEgPSBsbSh5MX54KQpzdW1tYXJ5KGZpdDEpCgpmaXQyID0gbG0oeTJ+eCkKc3VtbWFyeShmaXQyKQpgYGAKCiMjIFJlc2lkdWFsIHBsb3RzIG9mIHRoZSBPTFMgZml0cwoKCmBgYHtyIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTV9CnUxID0gZml0MSRyZXMKdTIgPSBmaXQyJHJlcwpwYXIobWZyb3c9YygxLDIpKQpwbG90KHUxLHR5cGU9ImIiKQpwbG90KHUyLHR5cGU9ImIiKQpgYGAKCgojIyBGaXR0aW5nIEFSKDEpIHRvIHRoZSByZXNpZHVhbHMKYGBge3J9CnN1bW1hcnkobG0odTFbMjpuXX51MVsxOihuLTEpXSkpCnN1bW1hcnkobG0odTJbMjpuXX51MlsxOihuLTEpXSkpCmBgYAoKIyBMaWtlbGlob29kIGFuZCBwcmlvcgpJdCBpcyBlYXN5IHRvIHNlZSB0aGF0ClxiZWdpbntlcW5hcnJheSp9CnlfdCAmPSYgXGJldGEgeF90ICsgdV90XFwKXHJobyB5X3t0LTF9ICY9JiBccmhvIFxiZXRhIHhfe3QtMX0gKyBccmhvIHVfe3QtMX0sClxlbmR7ZXFuYXJyYXkqfQpzdWNoIHRoYXQKJCQKeV90IC0gXHJobyB5X3t0LTF9ID0gXGJldGEgKHhfdC1ccmhvIHhfe3QtMX0pICsgXGVwc2lsb25fdC4KJCQKU28sIGZvciB0aGUgc2FrZSBvZiB0aGUgZXhlcmNpc2UsIGFzc3VtZSB0aGF0IHRoZSBsaWtlbGlob29kIGlzIGNvbmRpdGlvbmFsIG9uICR5XzEkIGFuZCAkeF8xJC4KVGhlcmVmb3JlCiQkCnAoeV97MjpufXx4X3syOm59LFx0aGV0YSkgXHByb3B0byAoXHNpZ21hXjIpXnstKG4tMSkvMn1cZXhwXGxlZnRcey1cZnJhY3sxfXtcc2lnbWFeMn0KXHN1bV97dD0yfV5uICh5X3QgLSBccmhvIHlfe3QtMX0gLSBcYmV0YSAoeF90LVxyaG8geF97dC0xfSkpXjIKXHJpZ2h0XH0sCiQkCmFuZCBhc3N1bWUgdGhhdCB0aGUgcHJpb3IgZm9yICRcdGhldGE9KFxiZXRhLFxyaG8sXHNpZ21hXjIpJCBpcyAKJCQKcChcYmV0YSxccmhvLFxzaWdtYV4yKSBccHJvcHRvIFxmcmFjezF9e1xzaWdtYV4yfS4KJCQKCiMgQ29udG91cnMgb2YgJHAoXGJldGEsXHJob3xcbWJveHtkYXRhfSkkCgpgYGB7cn0KbG9nbGlrZWxpaG9vZHByaW9yID0gZnVuY3Rpb24oeSx4LGJldGEscmhvLHNpZyl7CiAgc3VtKGRub3JtKHlbMjpuXSxyaG8qeVsxOihuLTEpXStiZXRhKih4WzI6bl0tcmhvKnhbMToobi0xKV0pLHNpZyxsb2c9VFJVRSkpLTIqbG9nKHNpZykKfQpNID0gMjAwCmJldGFzID0gc2VxKDEsNC41LGxlbmd0aD1NKQpyaG9zICA9IHNlcSgtMiwyLGxlbmd0aD1NKQpzaWdzICA9IHNlcSgwLjEsNCxsZW5ndGg9TSkKcG9zdCAgPSBhcnJheSgwLGMoTSxNLE0pKQpwb3N0MiA9IG1hdHJpeCgwLE0sTSkKZm9yIChpIGluIDE6TSkKICBmb3IgKGogaW4gMTpNKQogICAgZm9yIChrIGluIDE6TSkKICAgICAgcG9zdFtpLGosa10gPSBsb2dsaWtlbGlob29kcHJpb3IoeTEseCxiZXRhc1tpXSxyaG9zW2pdLHNpZ3Nba10pCm1heCA9IG1heChwb3N0KQpmb3IgKGkgaW4gMTpNKQogIGZvciAoaiBpbiAxOk0pCiAgICBwb3N0MltpLGpdID0gc3VtKGV4cChwb3N0W2ksaixdLW1heCkpCgpjb250b3VyKGJldGFzLHJob3MscG9zdDIseGxhYj1leHByZXNzaW9uKGJldGEpLHlsYWI9ZXhwcmVzc2lvbihyaG8pLG5sZXZlbHM9MjAsCiAgICAgICAgeGxpbT1jKDEsNCkseWxpbT1jKC0xLDIpLGRyYXdsYWJlbHM9RkFMU0UpCmBgYAoKIyBTSVItYmFzZWQgcG9zdGVyaW9yIGluZmVyZW5jZSBmb3IgdGhlIGNhc2UgSSBkYXRhc2V0ICgkXHJobz0wLjUkKQoKYGBge3IgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTh9Ck0gPSAxMDAwMDAKYmV0YTAgPSBydW5pZihNLC01LDUpCnJobzAgPSBydW5pZihNLC0zLDMpCnNpZzAgPSBydW5pZihNLDAuMDEsNCkKdyA9IHJlcCgwLE0pCmZvciAoaSBpbiAxOk0pCiAgd1tpXSA9IGxvZ2xpa2VsaWhvb2Rwcmlvcih5MSx4LGJldGEwW2ldLHJobzBbaV0sc2lnMFtpXSkKdyA9IGV4cCh3LW1heCh3KSkKayA9IHNhbXBsZSgxOk0sc2l6ZT1NLHJlcGxhY2U9VFJVRSxwcm9iPXcpCmJldGEgPSBiZXRhMFtrXQpyaG8gID0gcmhvMFtrXQpzaWcgID0gc2lnMFtrXQoKZHJhd3Muc2lyID0gY2JpbmQoYmV0YSxyaG8sc2lnKQoKcGFyKG1mcm93PWMoMiwyKSkKaGlzdChiZXRhLG1haW49ZXhwcmVzc2lvbihiZXRhKSx5bGFiPSJQb3N0ZXJpb3IiLHhsYWI9IiIscHJvYj1UUlVFKQpsZWdlbmQoInRvcHJpZ2h0IixsZWdlbmQ9YygKcGFzdGUoIjV0aCBwZXJjLj0iLHJvdW5kKHF1YW50aWxlKGJldGEsMC4wNSksMiksc2VwPSIiKSwKcGFzdGUoIjUwdGggcGVyYy49Iixyb3VuZChxdWFudGlsZShiZXRhLDAuNSksMiksc2VwPSIiKSwKcGFzdGUoIjk1dGggcGVyYy49Iixyb3VuZChxdWFudGlsZShiZXRhLDAuOTUpLDIpLHNlcD0iIikpLGJ0eT0ibiIpICAgICAgICAgICAgICAgICAgICAgICAgICAKYWJsaW5lKHY9Myxsd2Q9Mixjb2w9MikKaGlzdChyaG8sbWFpbj1leHByZXNzaW9uKHJobykseWxhYj0iUG9zdGVyaW9yIix4bGFiPSIiLHByb2I9VFJVRSkKbGVnZW5kKCJ0b3ByaWdodCIsbGVnZW5kPWMoCnBhc3RlKCI1dGggcGVyYy49Iixyb3VuZChxdWFudGlsZShyaG8sMC4wNSksMiksc2VwPSIiKSwKcGFzdGUoIjUwdGggcGVyYy49Iixyb3VuZChxdWFudGlsZShyaG8sMC41KSwyKSxzZXA9IiIpLApwYXN0ZSgiOTV0aCBwZXJjLj0iLHJvdW5kKHF1YW50aWxlKHJobywwLjk1KSwyKSxzZXA9IiIpKSxidHk9Im4iKSAgICAgICAgICAgICAgICAgICAgICAgICAgCmhpc3Qoc2lnLG1haW49ZXhwcmVzc2lvbihzaWcpLHlsYWI9IlBvc3RlcmlvciIseGxhYj0iIixwcm9iPVRSVUUpCmxlZ2VuZCgidG9wcmlnaHQiLGxlZ2VuZD1jKApwYXN0ZSgiNXRoIHBlcmMuPSIscm91bmQocXVhbnRpbGUoc2lnLDAuMDUpLDIpLHNlcD0iIiksCnBhc3RlKCI1MHRoIHBlcmMuPSIscm91bmQocXVhbnRpbGUoc2lnLDAuNSksMiksc2VwPSIiKSwKcGFzdGUoIjk1dGggcGVyYy49Iixyb3VuZChxdWFudGlsZShzaWcsMC45NSksMiksc2VwPSIiKSksYnR5PSJuIikKYWJsaW5lKHY9MSxsd2Q9Mixjb2w9MikKCnBsb3QoYmV0YSxyaG8seGxhYj1leHByZXNzaW9uKGJldGEpLHlsYWI9ZXhwcmVzc2lvbihyaG8pKQpjb250b3VyKGJldGFzLHJob3MscG9zdDIsYWRkPVRSVUUsY29sPTMsbmxldmVscz0yMCxkcmF3bGFiZWxzPUZBTFNFKQpgYGAKCiMgR2liYnMgc2FtcGxlcgoKV2UgbmVlZCB0byBkZXJpdmUgdGhlIGZ1bGwgY29uZGl0aW9uYWwgZGlzdHJpYnV0aW9ucyBpbiBvcmRlciB0byBpbXBsZW1lbnQgdGhlIEdpYmJzIHNhbXBsZXIuCgojIyAkcChcc2lnbWFeMnxcYmV0YSxccmhvLHhfezI6bn0seV97MjpufSkkCgpDb25kaXRpb25hbCBvbiAkKFxiZXRhLFxyaG8pJCwgdGhlIGZ1bGwgY29uZGl0aW9uYWwgZGlzdHJpYnV0aW9uIG9mICRcc2lnbWFeMiQgaXMgaW52ZXJzZS1nYW1tYSB3aXRoIHBhcmFtZXRlcnMgJChuLTEpLzIkIGFuZCAkXHN1bV97dD0yfV5uICh5X3QtXHJobyB5X3t0LTF9LVxiZXRhIHhfdC1ccmhvXGJldGEgeF97dC0xfSleMi8yJDoKJCQKcChcc2lnbWFeMnxcYmV0YSxccmhvLHhfezI6bn0seV97MjpufSkgXHByb3B0byBcc2lnbWFeey1cbGVmdChcZnJhY3tuLTF9ezJ9KzFccmlnaHQpfQpcZXhwXGxlZnRcey1cZnJhY3sxfXsyXHNpZ21hXjJ9IFxzdW1fe3Q9Mn1ebiAoeV90LVxyaG8geV97dC0xfS1cYmV0YSB4X3QrXHJob1xiZXRhIHhfe3QtMX0pXjJccmlnaHRcfQokJAoKIyMgJHAoXGJldGF8XHJobyxcc2lnbWFeMix4X3syOm59LHlfezI6bn0pJApDb25kaXRpb25hbCBvbiAkKFxyaG8sXHNpZ21hXjIpJCwgdGhlIGZ1bGwgY29uZGl0aW9uYWwgZGlzdHJpYnV0aW9uIG9mICRcYmV0YSQgdGFrZXMgYWR2YW50YWdlIG9mIHRoZSBmb2xsb3dpbmcgcmVncmVzc2lvbiBzZXQgdXA6CiQkClx1bmRlcmJyYWNle3lfdCAtIFxyaG8geV97dC0xfX1fe3tcdGlsZGUgeX1fdH0gPSBcYmV0YSAoXHVuZGVyYnJhY2V7eF90IC0gXHJobyB4X3t0LTF9fV97e1x0aWxkZSB4fV90fSkgKyBcZXBzaWxvbl90LAokJApzdWNoIHRoYXQKJCQKKFxiZXRhfFxyaG8sXHNpZ21hXjIseF97MjpufSx5X3syOm59KSBcc2ltIE5cbGVmdCgKXGZyYWN7XHN1bV97dD0yfV5uICh5X3QtXHJobyB5X3t0LTF9KSh4X3QtXHJobyB4X3t0LTF9KX0Ke1xzdW1fe3Q9Mn1ebiAoeF97dC0xfS1ccmhvIHhfe3QtMX0pXjJ9O1xmcmFje1xzaWdtYV4yfXtcc3VtX3t0PTJ9Xm4gKHhfe3QtMX0tXHJobyB4X3t0LTF9KV4yfQpccmlnaHQpLgokJAoKIyMgJHAoXHJob3xcYmV0YSxcc2lnbWFeMix4X3syOm59LHlfezI6bn0pJApDb25kaXRpb25hbCBvbiAkKFxiZXRhLFxzaWdtYV4yKSQsIHRoZSBmdWxsIGNvbmRpdGlvbmFsIGRpc3RyaWJ1dGlvbiBvZiAkXHJobyQgdGFrZXMgYWR2YW50YWdlIG9mIHRoZSBmb2xsb3dpbmcgcmVncmVzc2lvbiBzZXQgdXA6CiQkClx1bmRlcmJyYWNle3lfdCAtIFxiZXRhIHhfdH1fe3tcdGlsZGUgeX1fdH0gPSBccmhvIChcdW5kZXJicmFjZXt5X3t0LTF9IC0gXGJldGEgeF97dC0xfX1fe3tcdGlsZGUgeH1fdH0pICsgXGVwc2lsb25fdCwKJCQKc3VjaCB0aGF0CiQkCihccmhvfFxiZXRhLFxzaWdtYV4yLHhfezI6bn0seV97MjpufSkgXHNpbSBOXGxlZnQoClxmcmFje1xzdW1fe3Q9Mn1ebiAoeV90LVxiZXRhIHhfdCkoeV97dC0xfS1cYmV0YSB4X3t0LTF9KX0Ke1xzdW1fe3Q9Mn1ebiAoeV97dC0xfS1cYmV0YSB4X3t0LTF9KV4yfTtcZnJhY3tcc2lnbWFeMn17XHN1bV97dD0yfV5uICh5X3t0LTF9LVxiZXRhIHhfe3QtMX0pXjJ9XHJpZ2h0KS4KJCQKYGBge3IgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTh9CnkgPSB5MQoKc2lnMiA9IDEKYmV0YSA9IDMKcmhvICA9IDAuNQoKbml0ZXIgPSAxMDAwMApkcmF3cyA9IG1hdHJpeCgwLG5pdGVyLDMpCgpmb3IgKGl0ZXIgaW4gMTpuaXRlcil7CiMgRnVsbCBjb25kaXRpb25hbCBvZiBzaWdtYTIKeiAgICA9IHlbMjpuXS1yaG8qeVsxOihuLTEpXS1iZXRhKnhbMjpuXStyaG8qYmV0YSp4WzE6KG4tMSldCnNpZzIgPSAxL3JnYW1tYSgxLChuLTEpLzIsc3VtKHpeMikvMikKCiMgRnVsbCBjb25kaXRpb25hbCBvZiBiZXRhCnl0ICAgPSB5WzI6bl0tcmhvKnlbMToobi0xKV0KeHQgICA9IHhbMjpuXS1yaG8qeFsxOihuLTEpXQpiZXRhID0gcm5vcm0oMSxzdW0oeXQqeHQpL3N1bSh4dF4yKSxzcXJ0KHNpZzIvc3VtKHh0XjIpKSkKCiMgRnVsbCBjb25kaXRpb25hbCBvZiByaG8KeXQgID0geVsyOm5dLWJldGEqeFsyOm5dCnh0ICA9IHlbMToobi0xKV0tYmV0YSp4WzE6KG4tMSldCnJobyA9IHJub3JtKDEsc3VtKHl0Knh0KS9zdW0oeHReMiksc3FydChzaWcyL3N1bSh4dF4yKSkpCgpkcmF3c1tpdGVyLF0gPSBjKGJldGEscmhvLHNxcnQoc2lnMikpCn0KCmRyYXdzLmdpYmJzID0gZHJhd3MKCnBhcihtZnJvdz1jKDIsMykpCnRzLnBsb3QoZHJhd3NbLDFdLHhsYWI9Ikl0ZXJhdGlvbnMiLHlsYWI9IiIsbWFpbj1leHByZXNzaW9uKGJldGEpKQp0cy5wbG90KGRyYXdzWywyXSx4bGFiPSJJdGVyYXRpb25zIix5bGFiPSIiLG1haW49ZXhwcmVzc2lvbihyaG8pKQp0cy5wbG90KGRyYXdzWywzXSx4bGFiPSJJdGVyYXRpb25zIix5bGFiPSIiLG1haW49ZXhwcmVzc2lvbihzaWdtYSkpCmhpc3QoZHJhd3NbLDFdLHByb2I9VFJVRSx4bGFiPSIiLG1haW49IiIpCmhpc3QoZHJhd3NbLDJdLHByb2I9VFJVRSx4bGFiPSIiLG1haW49IiIpCmhpc3QoZHJhd3NbLDNdLHByb2I9VFJVRSx4bGFiPSIiLG1haW49IiIpCmBgYAoKCiMgQ29tcGFyaW5nIFNJUiBhbmQgR2liYnMgc2FtcGxlcgoKYGBge3IgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTh9CnBhcihtZnJvdz1jKDIsMikpCmhpc3QoZHJhd3Muc2lyWywxXSxwcm9iPVRSVUUseGxhYj0iIixtYWluPWV4cHJlc3Npb24oYmV0YSkpCmxpbmVzKGRlbnNpdHkoZHJhd3MuZ2liYnNbLDFdKSxjb2w9MikKYWJsaW5lKHY9Myxjb2w9Myxsd2Q9MykKbGVnZW5kKCJ0b3ByaWdodCIsbGVnZW5kPWMoIlNJUiIsIkdJQkJTIiksY29sPWMoMSwyKSxsd2Q9MykKaGlzdChkcmF3cy5zaXJbLDJdLHByb2I9VFJVRSx4bGFiPSIiLG1haW49ZXhwcmVzc2lvbihyaG8pKQpsaW5lcyhkZW5zaXR5KGRyYXdzLmdpYmJzWywyXSksY29sPTIpCmFibGluZSh2PTAuNSxjb2w9Myxsd2Q9MykKaGlzdChkcmF3cy5zaXJbLDNdLHByb2I9VFJVRSx4bGFiPSIiLG1haW49ZXhwcmVzc2lvbihzaWdtYSkpCmxpbmVzKGRlbnNpdHkoZHJhd3MuZ2liYnNbLDNdKSxjb2w9MikKYWJsaW5lKHY9MSxjb2w9Myxsd2Q9MykKcGxvdChkcmF3cy5zaXJbLDFdLGRyYXdzLnNpclssMl0seGxhYj1leHByZXNzaW9uKGJldGEpLHlsYWI9ZXhwcmVzc2lvbihyaG8pKQpwb2ludHMoZHJhd3MuZ2liYnNbLDFdLGRyYXdzLmdpYmJzWywyXSxjb2w9MikKYGBgCg==