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.
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)
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
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")
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
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}.
\]
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)
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)
Gibbs sampler
We need to derive the full conditional distributions in order to
implement the Gibbs sampler.
\(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\}
\]
\(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).
\]
\(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="")
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==