1 Global mean temperature anomaly

Global mean temperature anomaly (difference between current year and the 1951-1980 average) - Section 3.1.4 of Reich and Ghosh (2026) Bayesian Statistical Methods: With Applications to Machine Learning (2nd edition).

y  = scan("anomaly.txt")
n  = length(y)
par(mfrow=c(1,1))
plot(y,type="b",ylab="Temperature anomaly (C)",xlab="Year")

2 MODEL 1: AR(1)

Here we model data\(=\{y_1,\ldots,y_n\}\) as a Gaussian AR(1) structure. \[ y_t|y_{t-1},\rho,\sigma^2 \sim N(\rho y_{t-1},\sigma^2(1-\rho^2)), \qquad t=2,\ldots,n, \] for \(y_1 \sim N(0,\sigma^2)\). The prior for \((\rho,\sigma^2)\) is \[ (\rho,\sigma^2) \sim Beta(a,b)IG(c,d), \] for \((a,b,c,d)=(104,5,6,10)\).

prior = function(rho,sig){
  dbeta(rho,a,b)*dgamma(sig,c,d)
}

like = function(rho,sig){
  sd = sig*sqrt((1-rho^2))
  like = dnorm(y[1],0,sig)*prod(dnorm(y[2:n],rho*y[1:(n-1)],sd))
  return(like)
}

post = function(rho,sig){
  like(rho,sig)*prior(rho,sig)
}

a = 104
b = 5
c = 6
d = 10

N      = 200
sigs   = seq(0.1,1.75,length=N)
rhos   = seq(0.9,1.0,length=N)
likes  = matrix(0,N,N)
priors = matrix(0,N,N)
for (i in 1:N){
  for (j in 1:N){
    priors[i,j] = prior(rhos[i],sigs[j])
    likes[i,j] = like(rhos[i],sigs[j])
  }
}
posts = priors*likes

par(mfrow=c(1,2),mar = c(4, 4, 1, 1))
contour(rhos,sigs,priors,xlab=expression(rho),ylab=expression(sigma),drawlabels=FALSE)
contour(rhos,sigs,likes,xlab=expression(rho),ylab=expression(sigma),drawlabels=FALSE,add=TRUE,col=2)
legend("topleft",legend=c("Likelihood","Prior"),col=2:1,bty="n",lty=1)

contour(rhos,sigs,priors,xlab=expression(rho),ylab=expression(sigma),drawlabels=FALSE)
contour(rhos,sigs,posts,xlab=expression(rho),ylab=expression(sigma),drawlabels=FALSE,add=TRUE,col=2)
legend("topleft",legend=c("Posterior","Prior"),col=2:1,bty="n",lty=1)

2.1 Random-walk Metropolis-Hastings algorithm

rho.d  = 0.9
sig.d  = 1.4
sd.rho = 0.02
sd.sig = 0.05
M0     = 10000
M      = 5000
L      = 50
niter = M0+M*L
draws = matrix(0,niter,2)
for (iter in 1:niter){
  rho.mh = rnorm(1,rho.d,sd.rho)
  sig.mh = rnorm(1,sig.d,sd.sig)
  if ((abs(rho.mh)<1) & (sig.mh>0)){
    alpha  = min(1,post(rho.mh,sig.mh)/post(rho.d,sig.d))
    if (runif(1)<alpha){
      rho.d = rho.mh
      sig.d = sig.mh
    }
  }
  draws[iter,] = c(rho.d,sig.d)
}
draws1 = draws[seq(M0+1,niter,by=L),]

par(mfrow=c(2,3),mar = c(4, 4, 1, 1))
ts.plot(draws1[,1],xlab="iterations",ylab="",main=expression(rho))
acf(draws1[,1],main="")
hist(draws1[,1],prob=TRUE,main="",xlab="")
ts.plot(draws1[,2],xlab="iterations",ylab="",main=expression(sigma))
acf(draws1[,1],main="")
hist(draws1[,2],prob=TRUE,main="",xlab="")

2.2 One-step ahead forecast

ys = matrix(0,M,n)
ys[,1] = rnorm(M,0,draws[,2])
sds = draws[,2]*sqrt((1-draws[,1]^2))
for (t in 2:n)
  ys[,t] = rnorm(M,draws[,1]*y[t-1],sds)

qys = t(apply(ys,2,quantile,c(0.05,0.5,0.95)))


par(mfrow=c(1,1))
plot(y,pch=16,ylab="Temperature anomaly (C)",ylim=range(qys[2:n,]),xlab="Time")
for (t in 2:n)
  segments(t,qys[t,1],t,qys[t,3],col=2)
points(qys[,2],pch=16,col=2,cex=0.75)

3 MODEL 2: LOCAL LEVEL MODEL

Here we model data\(=\{y_1,\ldots,y_n\}\) as a Gaussian dynamic linear model: \[\begin{eqnarray*} y_t &=& x_t + \nu_t \qquad\qquad \nu_t \sim N(0,V)\\ x_t &=& x_{t-1} + \omega_t \qquad\qquad \omega_t \sim N(0,W), \end{eqnarray*}\] where \(x_0 \sim N(m_0,C_0)\).

The prior for \((V,W)\) is \[ (V,W) \sim IG(a_v,b_v)IG(c_w,d_w), \] for \((a_v,b_v,c_w,d_w)=(2.011.01,2.01,1.01)\).

3.1 MCMC algorithm via FFBS

mcmc.joint = function(y,a1,R1,av,bv,aw,bw,M0,M,V,W){
  n      = length(y)
  V.draw = V
  W.draw = W
  niter  = M0+M
  draws  = matrix(0,niter,n+2)
  for (iter in 1:niter){
    beta.draw = ffbs(y,rep(1,n),0.0,V.draw,1.0,0.0,W.draw,a1,R1,nd=1)
    par2v     = bv+sum((y-beta.draw)^2)/2
    par2w     = bw+sum((beta.draw[2:n]-beta.draw[1:(n-1)])^2)/2
    V.draw    = 1/rgamma(1,av+n/2,par2v)
    W.draw    = 1/rgamma(1,aw+(n-1)/2,par2w)
    draws[iter,] = c(beta.draw,V.draw,W.draw)
  }
  return(draws[(M0+1):niter,])
}

ffbs = function(y,Ft,alpha,V,G,gamma,W,a1,R1,nd=1){
  n = length(y)
  if (length(Ft)==1){Ft=rep(Ft,n)}
  if (length(alpha)==1){alpha=rep(alpha,n)}
  if (length(V)==1){V=rep(V,n)}
  a = rep(0,n)
  R = rep(0,n)
  m = rep(0,n)
  C = rep(0,n)
  B = rep(0,n-1)
  H = rep(0,n-1)
  # time t=1
  a[1] = a1
  R[1] = R1
  f    = alpha[1]+Ft[1]*a[1]
  Q    = R[1]*Ft[1]**2+V[1]
  A    = R[1]*Ft[1]/Q
  m[1] = a[1]+A*(y[1]-f)
  C[1] = R[1]-Q*A**2
  # forward filtering
  for (t in 2:n){
    a[t] = gamma + G*m[t-1]
    R[t] = C[t-1]*G**2 + W
    f    = alpha[t]+Ft[t]*a[t]
    Q    = R[t]*Ft[t]**2+V[t]
    A    = R[t]*Ft[t]/Q
    m[t] = a[t]+A*(y[t]-f)
    C[t] = R[t]-Q*A**2
    B[t-1] = C[t-1]*G/R[t]
    H[t-1] = sqrt(C[t-1]-R[t]*B[t-1]**2)
  }
  # backward sampling
  theta = matrix(0,nd,n)
  theta[,n] = rnorm(nd,m[n],sqrt(C[n]))
  for (t in (n-1):1)
    theta[,t] = rnorm(nd,m[t]+B[t]*(theta[,t+1]-a[t+1]),H[t])
  if (nd==1){
    theta[1,]
  }
  else{
    theta
  }
}

# Prior for beta(0) ~ N(m0,C0)
# Prior for beta(1) ~ N(a1,R1), a1=m0,R1=C0+W
a1     = 0
R1     = 10
av     = 2.01
bv     = 1.01
aw     = 2.01
bw     = 1.01    
m0     = 0
C0     = 10

# MCMC initual values
V0     = 1
W0     = 0.5
M0     = 10000
M      = 10000

set.seed(65432)
draws = mcmc.joint(y,a1,R1,av,bv,aw,bw,M0,M,V0,W0)
qbeta = t(apply(draws[,1:n],2,quantile,c(0.05,0.5,0.95)))
draws2 = draws

3.2 MCMC-based posterior inference

par(mfrow=c(1,2))
hist(draws[,n+1],main="V",prob=TRUE,xlab="")
hist(draws[,n+2],main="W",prob=TRUE,xlab="")

par(mfrow=c(1,1))
ts.plot(qbeta,col=c(3,2,3),lwd=2)
points(y,pch=16,cex=0.5)

3.3 Comparing AR(1) and LLM

n1 = 100
par(mfrow=c(1,1))
ts.plot(qbeta[2:n1,],lwd=c(1,2,1))
lines(qys[2:n1,1],col=2,lwd=1)
lines(qys[2:n1,2],col=2,lwd=2)
lines(qys[2:n1,3],col=2,lwd=1)

4 MODEL 3: AR(1) PLUS NOISE MODEL

4.1 MCMC algorithm via FFSB

# Set up of prior hyperparameters
m0        = 0
C0        = 100
nu0       = 10
sig20     = 1
eta0      = 10
tau20     = 1
nu0sig20  = nu0*sig20
eta0tau20 = eta0*tau20
nu0n      = (nu0+n)/2
eta0n     = (eta0+n)/2

# initial values
x     = y
x0    = 0
alpha = 0
beta  = 1
# MCMC set up
thin   = 1
burnin = 1000
M      = 1000
niter  = burnin+thin*M
draws  = matrix(0,niter,n+5)
mts    = rep(0,n)
Cts    = rep(0,n)
for (iter in 1:niter){
  # Learning sig2
  sig2 = 1/rgamma(1,nu0n,(nu0sig20+sum((y-x)^2))/2)
  # Learning tau2
  xx = c(x0,x[1:(n-1)])
  tau2 = 1/rgamma(1,eta0n,(eta0tau20+sum((x-alpha-beta*xx)^2))/2)
  # Learning (alpha,beta)
  X = cbind(1,xx)
  v = solve(t(X)%*%X)
  m = v%*%t(X)%*%x
  ab = m+t(chol(v))%*%rnorm(2,0,sqrt(tau2))
  alpha = ab[1]
  beta  = ab[2]
  # Learning x0
  var  = 1/(1/C0+beta^2/tau2)
  mean = var*(m0/C0+(x[1]-alpha)*beta/tau2)
  x0   = rnorm(1,mean,sqrt(var))
  # Learning x1,...,xn
  mt = m0
  Ct = C0
  for (t in 1:n){
    at = alpha+beta*mt
    Rt = beta^2*Ct+tau2
    Qt = Rt+sig2
    At = Rt/Qt
    mt = (1-At)*at + At*y[t]
    Ct = Rt - At^2*Qt
    mts[t] = mt
    Cts[t] = Ct
  }  
  x[n] = rnorm(1,mts[n],sqrt(Cts[n]))
  for (t in (n-1):1){
    v = 1/(beta^2/tau2+1/Cts[t])
    m = v*(beta*(x[t+1]-alpha)/tau2+mts[t]/Cts[t])
    x[t] = rnorm(1,m,sqrt(v))
  }
  # Storing the draws
  draws[iter,] = c(x,sig2,tau2,alpha,beta,x0)
}
ind = seq(burnin+1,niter,by=thin)
draws3 = draws[ind,]

4.2 MCMC-based posterior inference

par(mfrow=c(4,3),mar = c(2, 2, 1, 1))
ts.plot(draws[,n+1],xlab="iterations",ylab="",main=expression(sigma^2))
acf(draws[,n+1],main="")
hist(draws[,n+1],prob=TRUE,main="",xlab="")
ts.plot(draws[,n+2],xlab="iterations",ylab="",main=expression(tau^2))
acf(draws[,n+2],main="")
hist(draws[,n+2],prob=TRUE,main="",xlab="")
ts.plot(draws[,n+3],xlab="iterations",ylab="",main=expression(alpha))
acf(draws[,n+3],main="")
hist(draws[,n+3],prob=TRUE,main="",xlab="")
ts.plot(draws[,n+4],xlab="iterations",ylab="",main=expression(beta))
acf(draws[,n+4],main="")
hist(draws[,n+4],prob=TRUE,main="",xlab="")

acf1 = acf(draws[,1],plot=FALSE)
par(mfrow=c(1,1))
plot(acf1$acf,type="l",xlab="Lag",ylab="ACF",col=grey(0.75),ylim=c(-0.2,1))
for (i in 2:n){
  acf1 = acf(draws[,i],plot=FALSE)
  lines(acf1$acf,col=grey(0.75))
}
title("ACF for each x(t)")
abline(h=0,lty=3)

4.3 Comparison

qx = t(apply(draws[,1:n],2,quantile,c(0.025,0.5,0.975)))
ts.plot(qx,xlab="Time",col=2,lty=c(2,1,2))
points(y)
lines(qbeta[,1],col=4,lty=2)
lines(qbeta[,2],col=4)
lines(qbeta[,3],col=4,lty=2)

par(mfrow=c(2,4))
hist(draws1[,1],main=expression(rho),prob=TRUE,xlab="")
hist(draws1[,2],main=expression(sigma),prob=TRUE,xlab="")
hist(draws2[,n+1],main="V",prob=TRUE,xlab="")
hist(draws2[,n+2],main="W",prob=TRUE,xlab="")
hist(draws3[,n+3],main=expression(alpha),prob=TRUE,xlab="")
hist(draws3[,n+4],main=expression(beta),prob=TRUE,xlab="")
hist(draws3[,n+1],main="V",prob=TRUE,xlab="")
hist(draws3[,n+2],main="W",prob=TRUE,xlab="")

LS0tCnRpdGxlOiAiQVIoMSksIExMTSBhbmQgQVIoMSkgcGx1cyBub2lzZSBtb2RlbHMiCmF1dGhvcjogIkhlZGliZXJ0IEZyZWl0YXMgTG9wZXMiCmRhdGU6ICJgciBTeXMuRGF0ZSgpYCIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICB0aGVtZTogcGFwZXIKICAgIGhpZ2hsaWdodDogcHlnbWVudHMKICAgIHRvYzogdHJ1ZQogICAgdG9jX2RlcHRoOiAzCiAgICB0b2NfY29sbGFwc2VkOiB0cnVlCiMgICAgdG9jX2Zsb2F0OiB0cnVlCiAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCiAgICBudW1iZXJfc2VjdGlvbnM6IHRydWUKLS0tCiAgCgoKIyBHbG9iYWwgbWVhbiB0ZW1wZXJhdHVyZSBhbm9tYWx5CgpHbG9iYWwgbWVhbiB0ZW1wZXJhdHVyZSBhbm9tYWx5IChkaWZmZXJlbmNlIGJldHdlZW4gY3VycmVudCB5ZWFyIGFuZCB0aGUgMTk1MS0xOTgwIGF2ZXJhZ2UpIC0gU2VjdGlvbiAzLjEuNCBvZiBSZWljaCBhbmQgR2hvc2ggKDIwMjYpIEJheWVzaWFuIFN0YXRpc3RpY2FsIE1ldGhvZHM6IFdpdGggQXBwbGljYXRpb25zIHRvIE1hY2hpbmUgTGVhcm5pbmcgKDJuZCBlZGl0aW9uKS4KCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTcsIGZpZy5oZWlnaHQ9NX0KeSAgPSBzY2FuKCJhbm9tYWx5LnR4dCIpCm4gID0gbGVuZ3RoKHkpCnBhcihtZnJvdz1jKDEsMSkpCnBsb3QoeSx0eXBlPSJiIix5bGFiPSJUZW1wZXJhdHVyZSBhbm9tYWx5IChDKSIseGxhYj0iWWVhciIpCmBgYAoKIyBNT0RFTCAxOiBBUigxKQpIZXJlIHdlIG1vZGVsIGRhdGEkPVx7eV8xLFxsZG90cyx5X25cfSQgYXMgYSBHYXVzc2lhbiBBUigxKSBzdHJ1Y3R1cmUuCiQkCnlfdHx5X3t0LTF9LFxyaG8sXHNpZ21hXjIgXHNpbSBOKFxyaG8geV97dC0xfSxcc2lnbWFeMigxLVxyaG9eMikpLCBccXF1YWQgdD0yLFxsZG90cyxuLAokJApmb3IgJHlfMSBcc2ltIE4oMCxcc2lnbWFeMikkLiAgVGhlIHByaW9yIGZvciAkKFxyaG8sXHNpZ21hXjIpJCBpcyAKJCQKKFxyaG8sXHNpZ21hXjIpIFxzaW0gQmV0YShhLGIpSUcoYyxkKSwKJCQKZm9yICQoYSxiLGMsZCk9KDEwNCw1LDYsMTApJC4KCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTgsIGZpZy5oZWlnaHQ9NH0KcHJpb3IgPSBmdW5jdGlvbihyaG8sc2lnKXsKICBkYmV0YShyaG8sYSxiKSpkZ2FtbWEoc2lnLGMsZCkKfQoKbGlrZSA9IGZ1bmN0aW9uKHJobyxzaWcpewogIHNkID0gc2lnKnNxcnQoKDEtcmhvXjIpKQogIGxpa2UgPSBkbm9ybSh5WzFdLDAsc2lnKSpwcm9kKGRub3JtKHlbMjpuXSxyaG8qeVsxOihuLTEpXSxzZCkpCiAgcmV0dXJuKGxpa2UpCn0KCnBvc3QgPSBmdW5jdGlvbihyaG8sc2lnKXsKICBsaWtlKHJobyxzaWcpKnByaW9yKHJobyxzaWcpCn0KCmEgPSAxMDQKYiA9IDUKYyA9IDYKZCA9IDEwCgpOICAgICAgPSAyMDAKc2lncyAgID0gc2VxKDAuMSwxLjc1LGxlbmd0aD1OKQpyaG9zICAgPSBzZXEoMC45LDEuMCxsZW5ndGg9TikKbGlrZXMgID0gbWF0cml4KDAsTixOKQpwcmlvcnMgPSBtYXRyaXgoMCxOLE4pCmZvciAoaSBpbiAxOk4pewogIGZvciAoaiBpbiAxOk4pewogICAgcHJpb3JzW2ksal0gPSBwcmlvcihyaG9zW2ldLHNpZ3Nbal0pCiAgICBsaWtlc1tpLGpdID0gbGlrZShyaG9zW2ldLHNpZ3Nbal0pCiAgfQp9CnBvc3RzID0gcHJpb3JzKmxpa2VzCgpwYXIobWZyb3c9YygxLDIpLG1hciA9IGMoNCwgNCwgMSwgMSkpCmNvbnRvdXIocmhvcyxzaWdzLHByaW9ycyx4bGFiPWV4cHJlc3Npb24ocmhvKSx5bGFiPWV4cHJlc3Npb24oc2lnbWEpLGRyYXdsYWJlbHM9RkFMU0UpCmNvbnRvdXIocmhvcyxzaWdzLGxpa2VzLHhsYWI9ZXhwcmVzc2lvbihyaG8pLHlsYWI9ZXhwcmVzc2lvbihzaWdtYSksZHJhd2xhYmVscz1GQUxTRSxhZGQ9VFJVRSxjb2w9MikKbGVnZW5kKCJ0b3BsZWZ0IixsZWdlbmQ9YygiTGlrZWxpaG9vZCIsIlByaW9yIiksY29sPTI6MSxidHk9Im4iLGx0eT0xKQoKY29udG91cihyaG9zLHNpZ3MscHJpb3JzLHhsYWI9ZXhwcmVzc2lvbihyaG8pLHlsYWI9ZXhwcmVzc2lvbihzaWdtYSksZHJhd2xhYmVscz1GQUxTRSkKY29udG91cihyaG9zLHNpZ3MscG9zdHMseGxhYj1leHByZXNzaW9uKHJobykseWxhYj1leHByZXNzaW9uKHNpZ21hKSxkcmF3bGFiZWxzPUZBTFNFLGFkZD1UUlVFLGNvbD0yKQpsZWdlbmQoInRvcGxlZnQiLGxlZ2VuZD1jKCJQb3N0ZXJpb3IiLCJQcmlvciIpLGNvbD0yOjEsYnR5PSJuIixsdHk9MSkKYGBgCgoKIyMgUmFuZG9tLXdhbGsgTWV0cm9wb2xpcy1IYXN0aW5ncyBhbGdvcml0aG0KCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTcsIGZpZy5oZWlnaHQ9NX0KcmhvLmQgID0gMC45CnNpZy5kICA9IDEuNApzZC5yaG8gPSAwLjAyCnNkLnNpZyA9IDAuMDUKTTAgICAgID0gMTAwMDAKTSAgICAgID0gNTAwMApMICAgICAgPSA1MApuaXRlciA9IE0wK00qTApkcmF3cyA9IG1hdHJpeCgwLG5pdGVyLDIpCmZvciAoaXRlciBpbiAxOm5pdGVyKXsKICByaG8ubWggPSBybm9ybSgxLHJoby5kLHNkLnJobykKICBzaWcubWggPSBybm9ybSgxLHNpZy5kLHNkLnNpZykKICBpZiAoKGFicyhyaG8ubWgpPDEpICYgKHNpZy5taD4wKSl7CiAgICBhbHBoYSAgPSBtaW4oMSxwb3N0KHJoby5taCxzaWcubWgpL3Bvc3QocmhvLmQsc2lnLmQpKQogICAgaWYgKHJ1bmlmKDEpPGFscGhhKXsKICAgICAgcmhvLmQgPSByaG8ubWgKICAgICAgc2lnLmQgPSBzaWcubWgKICAgIH0KICB9CiAgZHJhd3NbaXRlcixdID0gYyhyaG8uZCxzaWcuZCkKfQpkcmF3czEgPSBkcmF3c1tzZXEoTTArMSxuaXRlcixieT1MKSxdCgpwYXIobWZyb3c9YygyLDMpLG1hciA9IGMoNCwgNCwgMSwgMSkpCnRzLnBsb3QoZHJhd3MxWywxXSx4bGFiPSJpdGVyYXRpb25zIix5bGFiPSIiLG1haW49ZXhwcmVzc2lvbihyaG8pKQphY2YoZHJhd3MxWywxXSxtYWluPSIiKQpoaXN0KGRyYXdzMVssMV0scHJvYj1UUlVFLG1haW49IiIseGxhYj0iIikKdHMucGxvdChkcmF3czFbLDJdLHhsYWI9Iml0ZXJhdGlvbnMiLHlsYWI9IiIsbWFpbj1leHByZXNzaW9uKHNpZ21hKSkKYWNmKGRyYXdzMVssMV0sbWFpbj0iIikKaGlzdChkcmF3czFbLDJdLHByb2I9VFJVRSxtYWluPSIiLHhsYWI9IiIpCmBgYAoKIyMgT25lLXN0ZXAgYWhlYWQgZm9yZWNhc3QKCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTcsIGZpZy5oZWlnaHQ9NX0KeXMgPSBtYXRyaXgoMCxNLG4pCnlzWywxXSA9IHJub3JtKE0sMCxkcmF3c1ssMl0pCnNkcyA9IGRyYXdzWywyXSpzcXJ0KCgxLWRyYXdzWywxXV4yKSkKZm9yICh0IGluIDI6bikKICB5c1ssdF0gPSBybm9ybShNLGRyYXdzWywxXSp5W3QtMV0sc2RzKQoKcXlzID0gdChhcHBseSh5cywyLHF1YW50aWxlLGMoMC4wNSwwLjUsMC45NSkpKQoKCnBhcihtZnJvdz1jKDEsMSkpCnBsb3QoeSxwY2g9MTYseWxhYj0iVGVtcGVyYXR1cmUgYW5vbWFseSAoQykiLHlsaW09cmFuZ2UocXlzWzI6bixdKSx4bGFiPSJUaW1lIikKZm9yICh0IGluIDI6bikKICBzZWdtZW50cyh0LHF5c1t0LDFdLHQscXlzW3QsM10sY29sPTIpCnBvaW50cyhxeXNbLDJdLHBjaD0xNixjb2w9MixjZXg9MC43NSkKYGBgCgoKCiMgTU9ERUwgMjogTE9DQUwgTEVWRUwgTU9ERUwKSGVyZSB3ZSBtb2RlbCBkYXRhJD1ce3lfMSxcbGRvdHMseV9uXH0kIGFzIGEgR2F1c3NpYW4gZHluYW1pYyBsaW5lYXIgbW9kZWw6ClxiZWdpbntlcW5hcnJheSp9CnlfdCAmPSYgeF90ICsgXG51X3QgICBccXF1YWRccXF1YWQgXG51X3QgXHNpbSBOKDAsVilcXAp4X3QgJj0mIHhfe3QtMX0gKyBcb21lZ2FfdCBccXF1YWRccXF1YWQgXG9tZWdhX3QgXHNpbSBOKDAsVyksClxlbmR7ZXFuYXJyYXkqfQp3aGVyZSAkeF8wIFxzaW0gTihtXzAsQ18wKSQuIAoKVGhlIHByaW9yIGZvciAkKFYsVykkIGlzCiQkCihWLFcpIFxzaW0gSUcoYV92LGJfdilJRyhjX3csZF93KSwKJCQKZm9yICQoYV92LGJfdixjX3csZF93KT0oMi4wMTEuMDEsMi4wMSwxLjAxKSQuCgojIyBNQ01DIGFsZ29yaXRobSB2aWEgRkZCUwpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD03LCBmaWcuaGVpZ2h0PTV9Cm1jbWMuam9pbnQgPSBmdW5jdGlvbih5LGExLFIxLGF2LGJ2LGF3LGJ3LE0wLE0sVixXKXsKICBuICAgICAgPSBsZW5ndGgoeSkKICBWLmRyYXcgPSBWCiAgVy5kcmF3ID0gVwogIG5pdGVyICA9IE0wK00KICBkcmF3cyAgPSBtYXRyaXgoMCxuaXRlcixuKzIpCiAgZm9yIChpdGVyIGluIDE6bml0ZXIpewogICAgYmV0YS5kcmF3ID0gZmZicyh5LHJlcCgxLG4pLDAuMCxWLmRyYXcsMS4wLDAuMCxXLmRyYXcsYTEsUjEsbmQ9MSkKICAgIHBhcjJ2ICAgICA9IGJ2K3N1bSgoeS1iZXRhLmRyYXcpXjIpLzIKICAgIHBhcjJ3ICAgICA9IGJ3K3N1bSgoYmV0YS5kcmF3WzI6bl0tYmV0YS5kcmF3WzE6KG4tMSldKV4yKS8yCiAgICBWLmRyYXcgICAgPSAxL3JnYW1tYSgxLGF2K24vMixwYXIydikKICAgIFcuZHJhdyAgICA9IDEvcmdhbW1hKDEsYXcrKG4tMSkvMixwYXIydykKICAgIGRyYXdzW2l0ZXIsXSA9IGMoYmV0YS5kcmF3LFYuZHJhdyxXLmRyYXcpCiAgfQogIHJldHVybihkcmF3c1soTTArMSk6bml0ZXIsXSkKfQoKZmZicyA9IGZ1bmN0aW9uKHksRnQsYWxwaGEsVixHLGdhbW1hLFcsYTEsUjEsbmQ9MSl7CiAgbiA9IGxlbmd0aCh5KQogIGlmIChsZW5ndGgoRnQpPT0xKXtGdD1yZXAoRnQsbil9CiAgaWYgKGxlbmd0aChhbHBoYSk9PTEpe2FscGhhPXJlcChhbHBoYSxuKX0KICBpZiAobGVuZ3RoKFYpPT0xKXtWPXJlcChWLG4pfQogIGEgPSByZXAoMCxuKQogIFIgPSByZXAoMCxuKQogIG0gPSByZXAoMCxuKQogIEMgPSByZXAoMCxuKQogIEIgPSByZXAoMCxuLTEpCiAgSCA9IHJlcCgwLG4tMSkKICAjIHRpbWUgdD0xCiAgYVsxXSA9IGExCiAgUlsxXSA9IFIxCiAgZiAgICA9IGFscGhhWzFdK0Z0WzFdKmFbMV0KICBRICAgID0gUlsxXSpGdFsxXSoqMitWWzFdCiAgQSAgICA9IFJbMV0qRnRbMV0vUQogIG1bMV0gPSBhWzFdK0EqKHlbMV0tZikKICBDWzFdID0gUlsxXS1RKkEqKjIKICAjIGZvcndhcmQgZmlsdGVyaW5nCiAgZm9yICh0IGluIDI6bil7CiAgICBhW3RdID0gZ2FtbWEgKyBHKm1bdC0xXQogICAgUlt0XSA9IENbdC0xXSpHKioyICsgVwogICAgZiAgICA9IGFscGhhW3RdK0Z0W3RdKmFbdF0KICAgIFEgICAgPSBSW3RdKkZ0W3RdKioyK1ZbdF0KICAgIEEgICAgPSBSW3RdKkZ0W3RdL1EKICAgIG1bdF0gPSBhW3RdK0EqKHlbdF0tZikKICAgIENbdF0gPSBSW3RdLVEqQSoqMgogICAgQlt0LTFdID0gQ1t0LTFdKkcvUlt0XQogICAgSFt0LTFdID0gc3FydChDW3QtMV0tUlt0XSpCW3QtMV0qKjIpCiAgfQogICMgYmFja3dhcmQgc2FtcGxpbmcKICB0aGV0YSA9IG1hdHJpeCgwLG5kLG4pCiAgdGhldGFbLG5dID0gcm5vcm0obmQsbVtuXSxzcXJ0KENbbl0pKQogIGZvciAodCBpbiAobi0xKToxKQogICAgdGhldGFbLHRdID0gcm5vcm0obmQsbVt0XStCW3RdKih0aGV0YVssdCsxXS1hW3QrMV0pLEhbdF0pCiAgaWYgKG5kPT0xKXsKICAgIHRoZXRhWzEsXQogIH0KICBlbHNlewogICAgdGhldGEKICB9Cn0KCiMgUHJpb3IgZm9yIGJldGEoMCkgfiBOKG0wLEMwKQojIFByaW9yIGZvciBiZXRhKDEpIH4gTihhMSxSMSksIGExPW0wLFIxPUMwK1cKYTEgICAgID0gMApSMSAgICAgPSAxMAphdiAgICAgPSAyLjAxCmJ2ICAgICA9IDEuMDEKYXcgICAgID0gMi4wMQpidyAgICAgPSAxLjAxICAgIAptMCAgICAgPSAwCkMwICAgICA9IDEwCgojIE1DTUMgaW5pdHVhbCB2YWx1ZXMKVjAgICAgID0gMQpXMCAgICAgPSAwLjUKTTAgICAgID0gMTAwMDAKTSAgICAgID0gMTAwMDAKCnNldC5zZWVkKDY1NDMyKQpkcmF3cyA9IG1jbWMuam9pbnQoeSxhMSxSMSxhdixidixhdyxidyxNMCxNLFYwLFcwKQpxYmV0YSA9IHQoYXBwbHkoZHJhd3NbLDE6bl0sMixxdWFudGlsZSxjKDAuMDUsMC41LDAuOTUpKSkKZHJhd3MyID0gZHJhd3MKYGBgCgojIyBNQ01DLWJhc2VkIHBvc3RlcmlvciBpbmZlcmVuY2UKCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTcsIGZpZy5oZWlnaHQ9NX0KcGFyKG1mcm93PWMoMSwyKSkKaGlzdChkcmF3c1ssbisxXSxtYWluPSJWIixwcm9iPVRSVUUseGxhYj0iIikKaGlzdChkcmF3c1ssbisyXSxtYWluPSJXIixwcm9iPVRSVUUseGxhYj0iIikKCnBhcihtZnJvdz1jKDEsMSkpCnRzLnBsb3QocWJldGEsY29sPWMoMywyLDMpLGx3ZD0yKQpwb2ludHMoeSxwY2g9MTYsY2V4PTAuNSkKYGBgCgojIyBDb21wYXJpbmcgQVIoMSkgYW5kIExMTQoKYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9NywgZmlnLmhlaWdodD01fQpuMSA9IDEwMApwYXIobWZyb3c9YygxLDEpKQp0cy5wbG90KHFiZXRhWzI6bjEsXSxsd2Q9YygxLDIsMSkpCmxpbmVzKHF5c1syOm4xLDFdLGNvbD0yLGx3ZD0xKQpsaW5lcyhxeXNbMjpuMSwyXSxjb2w9Mixsd2Q9MikKbGluZXMocXlzWzI6bjEsM10sY29sPTIsbHdkPTEpCmBgYAoKCgojIE1PREVMIDM6IEFSKDEpIFBMVVMgTk9JU0UgTU9ERUwKCgojIyBNQ01DIGFsZ29yaXRobSB2aWEgRkZTQgoKYGBge3J9CiMgU2V0IHVwIG9mIHByaW9yIGh5cGVycGFyYW1ldGVycwptMCAgICAgICAgPSAwCkMwICAgICAgICA9IDEwMApudTAgICAgICAgPSAxMApzaWcyMCAgICAgPSAxCmV0YTAgICAgICA9IDEwCnRhdTIwICAgICA9IDEKbnUwc2lnMjAgID0gbnUwKnNpZzIwCmV0YTB0YXUyMCA9IGV0YTAqdGF1MjAKbnUwbiAgICAgID0gKG51MCtuKS8yCmV0YTBuICAgICA9IChldGEwK24pLzIKCiMgaW5pdGlhbCB2YWx1ZXMKeCAgICAgPSB5CngwICAgID0gMAphbHBoYSA9IDAKYmV0YSAgPSAxCiMgTUNNQyBzZXQgdXAKdGhpbiAgID0gMQpidXJuaW4gPSAxMDAwCk0gICAgICA9IDEwMDAKbml0ZXIgID0gYnVybmluK3RoaW4qTQpkcmF3cyAgPSBtYXRyaXgoMCxuaXRlcixuKzUpCm10cyAgICA9IHJlcCgwLG4pCkN0cyAgICA9IHJlcCgwLG4pCmZvciAoaXRlciBpbiAxOm5pdGVyKXsKICAjIExlYXJuaW5nIHNpZzIKICBzaWcyID0gMS9yZ2FtbWEoMSxudTBuLChudTBzaWcyMCtzdW0oKHkteCleMikpLzIpCiAgIyBMZWFybmluZyB0YXUyCiAgeHggPSBjKHgwLHhbMToobi0xKV0pCiAgdGF1MiA9IDEvcmdhbW1hKDEsZXRhMG4sKGV0YTB0YXUyMCtzdW0oKHgtYWxwaGEtYmV0YSp4eCleMikpLzIpCiAgIyBMZWFybmluZyAoYWxwaGEsYmV0YSkKICBYID0gY2JpbmQoMSx4eCkKICB2ID0gc29sdmUodChYKSUqJVgpCiAgbSA9IHYlKiV0KFgpJSoleAogIGFiID0gbSt0KGNob2wodikpJSolcm5vcm0oMiwwLHNxcnQodGF1MikpCiAgYWxwaGEgPSBhYlsxXQogIGJldGEgID0gYWJbMl0KICAjIExlYXJuaW5nIHgwCiAgdmFyICA9IDEvKDEvQzArYmV0YV4yL3RhdTIpCiAgbWVhbiA9IHZhcioobTAvQzArKHhbMV0tYWxwaGEpKmJldGEvdGF1MikKICB4MCAgID0gcm5vcm0oMSxtZWFuLHNxcnQodmFyKSkKICAjIExlYXJuaW5nIHgxLC4uLix4bgogIG10ID0gbTAKICBDdCA9IEMwCiAgZm9yICh0IGluIDE6bil7CiAgICBhdCA9IGFscGhhK2JldGEqbXQKICAgIFJ0ID0gYmV0YV4yKkN0K3RhdTIKICAgIFF0ID0gUnQrc2lnMgogICAgQXQgPSBSdC9RdAogICAgbXQgPSAoMS1BdCkqYXQgKyBBdCp5W3RdCiAgICBDdCA9IFJ0IC0gQXReMipRdAogICAgbXRzW3RdID0gbXQKICAgIEN0c1t0XSA9IEN0CiAgfSAgCiAgeFtuXSA9IHJub3JtKDEsbXRzW25dLHNxcnQoQ3RzW25dKSkKICBmb3IgKHQgaW4gKG4tMSk6MSl7CiAgICB2ID0gMS8oYmV0YV4yL3RhdTIrMS9DdHNbdF0pCiAgICBtID0gdiooYmV0YSooeFt0KzFdLWFscGhhKS90YXUyK210c1t0XS9DdHNbdF0pCiAgICB4W3RdID0gcm5vcm0oMSxtLHNxcnQodikpCiAgfQogICMgU3RvcmluZyB0aGUgZHJhd3MKICBkcmF3c1tpdGVyLF0gPSBjKHgsc2lnMix0YXUyLGFscGhhLGJldGEseDApCn0KaW5kID0gc2VxKGJ1cm5pbisxLG5pdGVyLGJ5PXRoaW4pCmRyYXdzMyA9IGRyYXdzW2luZCxdCmBgYAoKIyMgTUNNQy1iYXNlZCBwb3N0ZXJpb3IgaW5mZXJlbmNlCgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD0xMH0KcGFyKG1mcm93PWMoNCwzKSxtYXIgPSBjKDIsIDIsIDEsIDEpKQp0cy5wbG90KGRyYXdzWyxuKzFdLHhsYWI9Iml0ZXJhdGlvbnMiLHlsYWI9IiIsbWFpbj1leHByZXNzaW9uKHNpZ21hXjIpKQphY2YoZHJhd3NbLG4rMV0sbWFpbj0iIikKaGlzdChkcmF3c1ssbisxXSxwcm9iPVRSVUUsbWFpbj0iIix4bGFiPSIiKQp0cy5wbG90KGRyYXdzWyxuKzJdLHhsYWI9Iml0ZXJhdGlvbnMiLHlsYWI9IiIsbWFpbj1leHByZXNzaW9uKHRhdV4yKSkKYWNmKGRyYXdzWyxuKzJdLG1haW49IiIpCmhpc3QoZHJhd3NbLG4rMl0scHJvYj1UUlVFLG1haW49IiIseGxhYj0iIikKdHMucGxvdChkcmF3c1ssbiszXSx4bGFiPSJpdGVyYXRpb25zIix5bGFiPSIiLG1haW49ZXhwcmVzc2lvbihhbHBoYSkpCmFjZihkcmF3c1ssbiszXSxtYWluPSIiKQpoaXN0KGRyYXdzWyxuKzNdLHByb2I9VFJVRSxtYWluPSIiLHhsYWI9IiIpCnRzLnBsb3QoZHJhd3NbLG4rNF0seGxhYj0iaXRlcmF0aW9ucyIseWxhYj0iIixtYWluPWV4cHJlc3Npb24oYmV0YSkpCmFjZihkcmF3c1ssbis0XSxtYWluPSIiKQpoaXN0KGRyYXdzWyxuKzRdLHByb2I9VFJVRSxtYWluPSIiLHhsYWI9IiIpCmBgYAoKYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9NywgZmlnLmhlaWdodD01fQphY2YxID0gYWNmKGRyYXdzWywxXSxwbG90PUZBTFNFKQpwYXIobWZyb3c9YygxLDEpKQpwbG90KGFjZjEkYWNmLHR5cGU9ImwiLHhsYWI9IkxhZyIseWxhYj0iQUNGIixjb2w9Z3JleSgwLjc1KSx5bGltPWMoLTAuMiwxKSkKZm9yIChpIGluIDI6bil7CiAgYWNmMSA9IGFjZihkcmF3c1ssaV0scGxvdD1GQUxTRSkKICBsaW5lcyhhY2YxJGFjZixjb2w9Z3JleSgwLjc1KSkKfQp0aXRsZSgiQUNGIGZvciBlYWNoIHgodCkiKQphYmxpbmUoaD0wLGx0eT0zKQpgYGAKCiMjIENvbXBhcmlzb24KCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTcsIGZpZy5oZWlnaHQ9NX0KcXggPSB0KGFwcGx5KGRyYXdzWywxOm5dLDIscXVhbnRpbGUsYygwLjAyNSwwLjUsMC45NzUpKSkKdHMucGxvdChxeCx4bGFiPSJUaW1lIixjb2w9MixsdHk9YygyLDEsMikpCnBvaW50cyh5KQpsaW5lcyhxYmV0YVssMV0sY29sPTQsbHR5PTIpCmxpbmVzKHFiZXRhWywyXSxjb2w9NCkKbGluZXMocWJldGFbLDNdLGNvbD00LGx0eT0yKQpgYGAKCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTZ9CnBhcihtZnJvdz1jKDIsNCkpCmhpc3QoZHJhd3MxWywxXSxtYWluPWV4cHJlc3Npb24ocmhvKSxwcm9iPVRSVUUseGxhYj0iIikKaGlzdChkcmF3czFbLDJdLG1haW49ZXhwcmVzc2lvbihzaWdtYSkscHJvYj1UUlVFLHhsYWI9IiIpCmhpc3QoZHJhd3MyWyxuKzFdLG1haW49IlYiLHByb2I9VFJVRSx4bGFiPSIiKQpoaXN0KGRyYXdzMlssbisyXSxtYWluPSJXIixwcm9iPVRSVUUseGxhYj0iIikKaGlzdChkcmF3czNbLG4rM10sbWFpbj1leHByZXNzaW9uKGFscGhhKSxwcm9iPVRSVUUseGxhYj0iIikKaGlzdChkcmF3czNbLG4rNF0sbWFpbj1leHByZXNzaW9uKGJldGEpLHByb2I9VFJVRSx4bGFiPSIiKQpoaXN0KGRyYXdzM1ssbisxXSxtYWluPSJWIixwcm9iPVRSVUUseGxhYj0iIikKaGlzdChkcmF3czNbLG4rMl0sbWFpbj0iVyIscHJvYj1UUlVFLHhsYWI9IiIpCmBgYAo=