1 The Michaelis-Menten nonlinear model

In biochemistry, Michaelis–Menten kinetics, named after Leonor Michaelis and Maud Menten, is the simplest case of enzyme kinetics, applied to enzyme-catalysed reactions involving the transformation of one substrate into one product. It takes the form of a differential equation describing the reaction rate \(y\) (μmol/min:Micromoles per minute), as a function of \(x\), the concentration of the substrate (mM:millimolar) - Source: https://en.wikipedia.org/wiki/Michaelis-Menten_kinetics.

The dataset below is from a enzyme kinetics experiments, which will be modeled as \[ y_i = \frac{\alpha x_i}{\beta+x_i} + \epsilon_i \qquad\qquad \epsilon_i \sim N(0,\sigma^2), \] where \(\alpha\) is the maximum reaction rate and \(\beta\) is the Michaelis constant.

#install.packages("mvtnorm")
library("mvtnorm")

substrate = c(0.5, 1.0, 2.0, 3.0, 5.0, 7.0, 10.0, 15.0)
rate      = c(0.26, 0.50, 0.85, 1.10, 1.40, 1.55, 1.65, 1.75)
x         = substrate
y         = rate
n         = length(x)

1.1 Exploratory data analysis

par(mfrow=c(1,1))
plot(x,y,ylab="Rate of a reaction (μmol)",xlab="Concentration of a substrate (mM)")

Here we try to figure out \(\alpha\) and \(\beta\) by running regressions through the origin of the for \[ y_i = \alpha z_i + \epsilon_i \] where \(z_i=x_i/(\beta+x_i)\), for each value of \(\beta\) on a grid in the interval \((0,5)\), and then choosing the \(\beta\) that minimizes the residual sum of squares, \(RSS(\beta)\).

nn = 100
bs = seq(0,5,length=nn)
rss = rep(0,nn)
for (i in 1:nn){
  x1 = x/(bs[i]+x)
  rss[i] = mean(lm(y~x1-1)$res^2)
}

beta.eda  = bs[rss==min(rss)]
x1        = x/(beta.eda+x)
alpha.eda = lm(y~x1-1)$coef
alpha.eda
##       x1 
## 2.153489
beta.eda
## [1] 2.979798
par(mfrow=c(1,2))
plot(bs,rss,xlab=expression(beta),ylab="Residual sum of squares",pch=16,cex=0.5)
abline(v=beta.eda)
title(paste("alpha=",round(alpha.eda,3)," - beta=",round(beta.eda,3),sep=""))
plot(x,y,ylab="Rate of a reaction (μmol)",xlab="Concentration of a substrate (mM)",pch=16)
xx = seq(min(x),max(x),length=100)
lines(xx,alpha.eda*xx/(beta.eda+xx),col=2)
points(x,alpha.eda*x/(beta.eda+x),col=2,pch=16)

2 Nonlinear least squares estimation

Let us plot the likelihood function on a grid for \((\alpha,\beta)\).

sigma   = 0.04305 
alpha.g = seq(1,3,length=200)
beta.g  = seq(0,6,length=200)
like    = matrix(0,200,200)
for (i in 1:200)
for (j in 1:200)
  like[i,j] = sum(dnorm(y,alpha.g[i]*x/(beta.g[j]+x),sigma,log=TRUE))
  
contour(alpha.g,beta.g,exp(like),xlab=expression(alpha),ylab=expression(beta),drawlabels=FALSE)
title("Likelihood function")

2.1 Nonlinear fit via function nls

fit.nls = nls(y~alpha*x/(beta+x),start=list(alpha=alpha.eda,beta=beta.eda))

summary(fit.nls)
## 
## Formula: y ~ alpha * x/(beta + x)
## 
## Parameters:
##       Estimate Std. Error t value Pr(>|t|)    
## alpha  2.15547    0.06062   35.56 3.30e-08 ***
## beta   2.98860    0.24264   12.32 1.75e-05 ***
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## Residual standard error: 0.04305 on 6 degrees of freedom
## 
## Number of iterations to convergence: 3 
## Achieved convergence tolerance: 6.585e-06
beta.nls  = summary(fit.nls)$coef[2]
alpha.nls = summary(fit.nls)$coef[1]
sigma.nls = summary(fit.nls)$sigma
se = sigma.nls*sqrt(diag(summary(fit.nls)$cov.unscaled))
sa.nls = se[1]
sb.nls = se[2]
c(alpha.nls,beta.nls)
## [1] 2.15547 2.98860
c(sa.nls,sb.nls)
##      alpha       beta 
## 0.06062228 0.24264405

3 Bayesian estimation

Let us rewrite the likelihood function for clarity \[ L(\alpha,\beta|\mbox{data}) \propto \exp\left\{-\frac{1}{2\sigma^2}\sum_{i=1}^n \left(y_i-\frac{\alpha x_i}{\beta + x_i}\right)^2\right\}. \] We will assume that the prior for \((\alpha,\beta)\) is \[ p(\alpha,\beta)=p_N(\alpha|\mu_\alpha,\sigma_\alpha^2)p(\beta|\mu_\beta,\sigma_\beta^2), \] where \(p_N(\cdot|\theta,\tau^2)\) is the density of Gaussian distribution with mean \(\theta\) and variance \(\tau^2\), Here we assume that \(\mu_\alpha=2\), \(\sigma_\alpha^2=1\), \(\mu_\beta=3\) and \(\sigma_\beta^2=1\).

mua   = 2
mub   = 3
siga  = 1
sigb  = 1
prior = matrix(0,200,200)
post  = matrix(0,200,200)
for (i in 1:200)
for (j in 1:200){
  prior[i,j] = dnorm(alpha.g[i],mua,siga,log=TRUE)+dnorm(beta.g[j],mub,sigb,log=TRUE)
  post[i,j]  = like[i,j] + prior[i,j]
}
contour(alpha.g,beta.g,exp(prior),xlab=expression(alpha),ylab=expression(beta),drawlabels=FALSE)
contour(alpha.g,beta.g,exp(post),drawlabels=FALSE,col=2,add=TRUE)
legend("topleft",legend=c("Prior","Posterior"),col=1:2,lwd=2,bty="n",lty=1)

3.1 Sampling importance resampling (SIR)

Here, we will use the output of the previous nonlinear least squares estimation to feed the hyperparameters for the proposal densities: \[ q(\alpha,\beta) = q(\alpha)q(\beta) \equiv p_N(\alpha|\alpha_{nls},9\sigma_{\alpha,nls}^2) p_N(\beta|\beta_{nls},9\sigma_{\beta,nls}^2). \]

M     = 10000
ma    = alpha.nls
sa    = 3*sa.nls
mb    = beta.nls
sb    = 3*sb.nls


set.seed(12345)
alphas = rnorm(M,ma,sa)
betas  = rnorm(M,mb,sb)
w      = rep(0,M)
for (i in 1:M)
w[i] = sum(dnorm(y,alphas[i]*x/(betas[i]+x),sigma,log=TRUE))+
       dnorm(alphas[i],mua,siga,log=TRUE)+
       dnorm(betas[i],mub,sigb)-
       dnorm(alphas[i],ma,sa,log=TRUE)-
       dnorm(betas[i],mb,sb,log=TRUE)
w = exp(w-max(w))
ind = sample(1:M,size=M,replace=TRUE,prob=w)
alphas1 = alphas[ind]
betas1 = betas[ind]
draws.sir = cbind(alphas1,betas1)

par(mfrow=c(1,1))
contour(alpha.g,beta.g,exp(prior),xlab=expression(alpha),ylab=expression(beta),
        drawlabels=FALSE,col=2)
points(alphas,betas,pch=16)
points(draws.sir[,1],draws.sir[,2],pch=16,col=3)
contour(alpha.g,beta.g,exp(post),add=TRUE,col=4)
legend("topleft",legend=c("Prior density (grid)","Proposal draws","Posterior (grid)",
       "Posterior draws (SIR)"),col=c(2,1,4,3),pch=16,bty="n")

3.2 MCMC1

In this first MCMC scheme, we use a random-walk Metropolis step for \(\beta\) and a Gibbs sampler step for \(\alpha\). The Gibbs sampler for \(\alpha\) takes advantage of the fact that conditional on \(\beta\) the nonlinear model becomes a linear model as far as \(\alpha\) is concerned so the full conditional \(p(\alpha|\beta,\mbox{data})\) is an easily derived Gaussian distribution.

  • Random walk Metropolis step: \(\beta \sim N(\beta^{(i)},v_\beta^2)\)

  • Gibbs sampler step: \(\alpha|\beta,\mbox{data} \sim N(\gamma,\omega^2)\), where \[ \omega^2 = \left( \frac{1}{\sigma_\alpha^2} + \frac{\sum_{i=1}^n z_i^2}{\sigma^2} \right)^{-1} \ \ \ \mbox{and} \ \ \ \gamma = \omega^2\left( \frac{\mu_\alpha}{\sigma_\alpha^2} + \frac{\sum_{i=1}^n y_iz_i}{\sigma^2}\right), \] where \(z_i = x_i/(\beta+x_i)\), for \(i=1,\ldots,n\).

# MCMC setup
M0    = 10000
M     = 20000
L     = 1
niter = M0+M*L
v.b   = 0.5
beta  = beta.nls
draws = matrix(0,niter,2)
for (iter in 1:niter){
  # sampling alpha (Gibbs step)
  z     = x/(beta+x)
  var   = 1/(1/siga^2+sum(z^2)/sigma^2)
  mean  = var*(mua/siga^2+sum(z*y)/sigma^2)
  alpha = rnorm(1,mean,sqrt(var))
  # sampling beta (random-walk Metropolis step)
  beta1     = rnorm(1,beta,v.b)
  logaccept = min(0,dnorm(beta1,mub,sigb,log=TRUE)+sum(dnorm(y,alpha*x/(beta1+x),sigma,log=TRUE))-
                    dnorm(beta,mub,sigb,log=TRUE)-sum(dnorm(y,alpha*x/(beta+x),sigma,log=TRUE)))
  if (log(runif(1))<logaccept){
    beta = beta1
  }
  draws[iter,] = c(alpha,beta)
}
draws.mcmc1 = draws[seq(M0+1,niter,by=L),]


names = c("alpha","beta")
par(mfrow=c(2,3))
for (i in 1:2){
  ts.plot(draws.mcmc1[,i],ylab="",main=names[i])
  acf(draws.mcmc1[,i],main="")
  hist(draws.mcmc1[,i],xlab="",main="",prob=TRUE)
}

3.3 MCMC2

Here, we decided to sample \((\alpha,\beta)\) jointly in the MCM scheme. In order to do that, we implement an independent Metropolis algorithm for \((\alpha,\beta)\) where the proposal \(q(\alpha,\beta)\) is the same one used in our implementation of the above SIR scheme.

alpha = alpha.nls
beta  = beta.nls
niter = M0+M*L
draws = matrix(0,niter,2)
for (iter in 1:niter){
  alpha1 = rnorm(1,ma,sa)
  beta1  = rnorm(1,mb,sb)
  post.n = dnorm(alpha1,mua,siga,log=TRUE)+dnorm(beta1,mub,sigb,log=TRUE)+
           sum(dnorm(y,alpha1*x/(beta1+x),sigma,log=TRUE))
  post.d = dnorm(alpha,mua,siga,log=TRUE)+dnorm(beta,mub,sigb,log=TRUE)+
           sum(dnorm(y,alpha*x/(beta+x),sigma,log=TRUE))
  prop.n = dnorm(alpha,ma,sa)+dnorm(beta,mb,sb)
  prop.d = dnorm(alpha1,ma,sa)+dnorm(beta1,mb,sb)
  logaccept = min(0,post.n-post.d+prop.n-prop.d)
  if (log(runif(1))<logaccept){
    alpha = alpha1
    beta = beta1
  }
  draws[iter,] = c(alpha,beta)
}
draws.mcmc2 = draws[seq(M0+1,niter,by=L),]

par(mfrow=c(2,3))
for (i in 1:2){
  ts.plot(draws.mcmc2[,i],ylab="",main=names[i])
  acf(draws.mcmc2[,i],main="")
  hist(draws.mcmc2[,i],xlab="",main="",prob=TRUE)
}

3.4 MC

Here, we integrate out \(\alpha\) analytically in order to obtain \(p(\beta|\mbox{data})\). Then we sample \(\beta\) from this marginal posterior distribution via SIR. Then, the \(\beta\) draws are used to directly sample \(\alpha\) from \(p(\alpha|\beta,\mbox{data})\). Therefore, an MCMC is not needed!

  1. Sample \(\{\beta^{(1)},\ldots,\beta^{(M)}\}\) from \(p(\beta|\mbox{data})\) via SIR with proposal \(q(\beta)=p_N(\beta|\beta_{nls},\sigma_{nls}^2)\). To implement SIR we need the integrated likelihood for \(\beta\) given \(y=(y_1,\ldots,y_n)'\): \[ p(y|\beta) = \int_{-\infty}^{\infty} p(y|\alpha,\beta)p(\alpha)d\alpha = p_N(y|\mu_\alpha z,\sigma^2 I_n + \sigma_\alpha^2 zz'), \] where \(z=(z_1,\ldots,z_n)'\) and \(z_i=x_i/(\beta+x_i)\), for \(i=1,\ldots,n\). Notice that, by integration \(\alpha\) out, the marginal \(p(y|\beta)\) is a multivariate normal with non-diagonal variance function of the \((n \times n\)) matrix \(zz'\).

  2. Sample \(\alpha^{(i)}\) from \(p(\alpha|\beta^{(i)},\mbox{data})\), similar to the Gibbs sampler step of the above MCMC1 algorithm.

# sampling beta from p(beta|data)
M    = 10000
beta = rnorm(M,mb,sb)
for (i in 1:M){
 xx = x/(beta[i]+x)
 mean = mua*xx
 var = siga^2*xx%*%t(xx)+diag(sigma^2,n)
 w[i] = dmvnorm(y,mean=mean,sigma=var,log=TRUE)+
        dnorm(beta[i],mub,sigb,log=TRUE)-
        dnorm(beta[i],mb,sb,log=TRUE)
}
w     = exp(w-max(w))
beta1 = sample(beta,size=M,replace=TRUE,prob=w)
beta  = beta1

# sampling alpha from p(alpha|beta,data)
alpha = rep(0,M)
for (i in 1:M){
  z        = x/(beta[i]+x)
  var      = 1/(1/siga^2+sum(z^2)/sigma^2)
  mean     = var*(mua/siga^2+sum(z*y)/sigma^2)
  alpha[i] = rnorm(1,mean,sqrt(var))
}
draws.mc = cbind(alpha,beta)

par(mfrow=c(2,2))
for (i in 1:2){
  ts.plot(draws.mc[,i],ylab="",main=names[i])
  hist(draws.mc[,i],xlab="",main="",prob=TRUE)
}

3.5 Comparing MC and MCMC algorithms

par(mfrow=c(2,2))
xrange = range(draws.sir[,1],draws.mcmc1[,1],draws.mcmc2[,1],draws.mc[,1])
yrange = range(draws.sir[,2],draws.mcmc1[,2],draws.mcmc2[,2],draws.mc[,2])
plot(draws.sir[,1],draws.sir[,2],xlab=expression(alpha),ylab=expression(beta),pch=16,ylim=yrange,xlim=xrange)
title("SIR")
contour(alpha.g,beta.g,exp(post),add=TRUE,col=5,drawlabels=FALSE)
plot(draws.mcmc1[,1],draws.mcmc1[,2],xlab=expression(alpha),ylab=expression(beta),pch=16,ylim=yrange,xlim=xrange)
title("MCMC 1")
contour(alpha.g,beta.g,exp(post),add=TRUE,col=5,drawlabels=FALSE)
plot(draws.mcmc2[,1],draws.mcmc2[,2],xlab=expression(alpha),ylab=expression(beta),pch=16,ylim=yrange,xlim=xrange)
title("MCMC 2")
contour(alpha.g,beta.g,exp(post),add=TRUE,col=5,drawlabels=FALSE)
plot(draws.mc[,1],draws.mc[,2],xlab=expression(alpha),ylab=expression(beta),pch=16,ylim=yrange,xlim=xrange)
title("MC")
contour(alpha.g,beta.g,exp(post),add=TRUE,col=5,drawlabels=FALSE)

par(mfrow=c(1,2))
plot(density(draws.sir[,1]),xlab="",main=expression(alpha))
lines(density(draws.mcmc1[,1]),col=2)
lines(density(draws.mcmc2[,1]),col=3)
lines(density(draws.mc[,1]),col=4)
plot(density(draws.sir[,2]),xlab="",main=expression(beta))
lines(density(draws.mcmc1[,2]),col=2)
lines(density(draws.mcmc2[,2]),col=3)
lines(density(draws.mc[,2]),col=4)

tab.a = rbind(quantile(draws.sir[,1],c(0.05,0.25,0.5,0.75,0.95)),
quantile(draws.mcmc1[,1],c(0.05,0.25,0.5,0.75,0.95)),
quantile(draws.mcmc2[,1],c(0.05,0.25,0.5,0.75,0.95)),
quantile(draws.mc[,1],c(0.05,0.25,0.5,0.75,0.95)))

tab.b = rbind(quantile(draws.sir[,2],c(0.05,0.25,0.5,0.75,0.95)),
quantile(draws.mcmc1[,2],c(0.05,0.25,0.5,0.75,0.95)),
quantile(draws.mcmc2[,2],c(0.05,0.25,0.5,0.75,0.95)),
quantile(draws.mc[,2],c(0.05,0.25,0.5,0.75,0.95)))

rownames(tab.a) = c("SIR","MCMC1","MCMC2","MC")
rownames(tab.b) = c("SIR","MCMC1","MCMC2","MC")

round(tab.a,2)
##         5%  25%  50% 75%  95%
## SIR   2.06 2.12 2.15 2.2 2.26
## MCMC1 2.07 2.12 2.16 2.2 2.26
## MCMC2 2.07 2.12 2.16 2.2 2.26
## MC    2.07 2.12 2.16 2.2 2.26
round(tab.b,2)
##         5%  25%  50%  75%  95%
## SIR   2.64 2.85 2.99 3.16 3.40
## MCMC1 2.65 2.87 3.01 3.17 3.41
## MCMC2 2.67 2.87 3.02 3.18 3.40
## MC    2.66 2.87 3.01 3.17 3.41

3.6 Posterior predictive distribution

A final exercise is to obtain a Monte Carlo approximation to the posterior predictive of \(y\) for a new value of \(x\), say \({\widetilde x}\): \[ p({\widetilde y}|{\widetilde x}) = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty} p_N\left({\widetilde y}|\frac{\alpha{\widetilde x}}{\beta+{\widetilde x}},\sigma^2\right) p(\alpha,\beta|\mbox{data})d\alpha d\beta, \] which can be approximated by \[ p_{MC}({\widetilde y}|{\widetilde x}) = \frac1M\sum_{i=1}^N p_N\left({\widetilde y}|\frac{\alpha^{(i)}{\widetilde x}}{\beta^{(i)}+{\widetilde x}},\sigma^2\right) \] where \(\{(\alpha,\beta)^{(1)},\ldots,(\alpha,\beta)^{(M)}\}\) is a Monte Carlo sample from \(p(\alpha,\beta|\mbox{data})\), which could be from any of the previous 4 schemes we arleady implemente, ie. SIR, MCMC1, MCMC2 or MC.

# Posterior predictive for xnew=5 and xnew=10
alpha.d  = draws.mc[,1]
beta.d   = draws.mc[,2]
N        = 200
yy       = seq(1,2.5,length=N)
postpred = matrix(0,N,2)
for (i in 1:N){
  postpred[i,1] = mean(dnorm(yy[i],alpha.d*5/(beta.d+5),sigma))
  postpred[i,2] = mean(dnorm(yy[i],alpha.d*10/(beta.d+10),sigma))
}
par(mfrow=c(1,2))
plot(yy,postpred[,1],ylab="Posterior predictive density",xlab="Rate of a reaction (μmol)",type="l")
title("x = 5")
points(1.4,0,pch=16,cex=2)
plot(yy,postpred[,2],ylab="Posterior predictive density",xlab="Rate of a reaction (μmol)",type="l")
title("x = 10")
points(1.65,0,pch=16,cex=2)

postpred1 = postpred

Similarly, given \({\widetilde x}\), a sample from \(p(y|{\widetilde x})\) can be obtained as follows \[ {\widetilde y}^{(i)} \sim N\left(\frac{\alpha^{(i)}{\widetilde x}}{\beta^{(i)}+{\widetilde x}},\sigma^2\right), \qquad\qquad i=1,\ldots,M. \] Therefore, \(\{{\widetilde y}^{(1)},\ldots,{\widetilde y}^{(M)}\}\) is a sample from \(p(y|{\widetilde x})\).

alpha.d = draws.mc[,1]
beta.d  = draws.mc[,2]
N       = 20
xx      = seq(min(x),max(x),length=N)
yy      = matrix(0,N,M)
for (i in 1:N)
  yy[i,] = rnorm(M,alpha.d*xx[i]/(beta.d+xx[i]),sigma)
quant = t(apply(yy,1,quantile,c(0.05,0.5,0.95)))

par(mfrow=c(1,1))
plot(x,y,ylab="Rate of a reaction (μmol)",xlab="Concentration of a substrate (mM)",
     ylim=range(quant,y),pch=16,cex=0.75)
lines(xx,quant[,1],lty=2,col=2,lwd=2)
lines(xx,quant[,2],col=2,lwd=2)
lines(xx,quant[,3],lty=2,col=2,lwd=2)

quant1 = quant

4 Learning \((\alpha,\beta,\sigma^2)\)

As a final task, let us now consider unknown the error variance, \(\sigma^2\), and assume its prior is a inverse-gamma distribution with parameters \(a_0\) and \(b_0\), denoted by \(\sigma^2 \sim IG(a_0,b_0)\) with density \[ p(\sigma^2|a_0,b_0) \propto (\sigma^2)^{-(a_0+1)}\exp\{-b_0/\sigma^2\}. \] Therefore, the full conditional posterior distribution of \(\sigma^2\) can be easily derived by noticing that \[ z_i \equiv y_i-\frac{\alpha x_i}{\beta+x_i} \sim N(0,\sigma^2), \] has likelihood \[ L(\sigma^2|\mbox{data}) \propto (\sigma^2)^{-n/2}\exp\left\{-\frac12\sum_{i=1}^n z_i^2\sigma^2\right\}. \] Combining \(p(\sigma^2|a_0,b_0)\) and \(L(\sigma^2|\mbox{data})\), leads to \[ p(\sigma^2|\alpha,\beta,\mbox{data}) \propto (\sigma^2)^{-(a_0+n/2+1)}\exp\left\{-\frac{b_0+\sum_{i=1}^n z_i^2/2}{\sigma^2}\right\}, \] which is an inverse-gamma with parameters \(a_0+n/2\) and \(b_0+\sum_{i=1}^n z_i^2/2\). Here we will consider a fairly uninformative prior for \(\sigma^2\) with \(a_0=10\) and \(b_0=0.018\). The prior mean for \(\sigma^2\) is \(0.04^2\). The 95% prior credibility interval (C.I.) for \(\sigma^2\) is \((0.001054,0.003754)\). It is worth noting that the 95% prior C.I. for \(\sigma\) is \((0.0324,0.0613)\). Recall that we fixed \(\sigma=0.04305\) in the previous analyses.

Therefore, we only need to add another layer in the MCMC scheme that was designed to sample from \(p(\alpha,\beta|\mbox{data},\sigma^2)\). The compositional aspect of the Gibbs sampler or, more generally, of all MCMC schemes is one of its main strengths and one can argue that it is the main reason for the massive success of MCMC for modern Bayesian inference that spreaded quickly to virtually all areas of applied sciences.

# Hyperparameters of p(sigma^2)
a0 = 10
b0 = 0.018

# MCMC setup
set.seed(12566)
M0    = 2000
M     = 5000
L     = 40
niter = M0+M*L
v.b   = 0.5
beta  = beta.nls
sigma = 0.04305 
draws = matrix(0,niter,3)
for (iter in 1:niter){
  # sampling alpha (Gibbs step)
  z     = x/(beta+x)
  var   = 1/(1/siga^2+sum(z^2)/sigma^2)
  mean  = var*(mua/siga^2+sum(z*y)/sigma^2)
  alpha = rnorm(1,mean,sqrt(var))
  # sampling beta (random-walk Metropolis step)
  beta1     = rnorm(1,beta,v.b)
  logaccept = min(0,dnorm(beta1,mub,sigb,log=TRUE)+sum(dnorm(y,alpha*x/(beta1+x),sigma,log=TRUE))-
                    dnorm(beta,mub,sigb,log=TRUE)-sum(dnorm(y,alpha*x/(beta+x),sigma,log=TRUE)))
  if (log(runif(1))<logaccept){
    beta = beta1
  }
  e    = y-alpha*x/(beta+x)
  par1 = a0 + n/2
  par2 = b0 + sum(e^2)/2
  sigma = sqrt(1/rgamma(1,par1,par2))
  draws[iter,] = c(alpha,beta,sigma)
}
draws.full = draws[seq(M0+1,niter,by=L),]


names = c("alpha","beta","sigma")
par(mfrow=c(3,3))
for (i in 1:3){
  ts.plot(draws.full[,i],ylab="",main=names[i])
  acf(draws.full[,i],main="")
  hist(draws.full[,i],xlab="",main="",prob=TRUE)
}

4.1 Bivariate marginal posterior distributions

par(mfrow=c(1,3))
plot(draws.full[,1],draws.full[,2],xlab=expression(alpha),ylab=expression(beta))
plot(draws.full[,1],draws.full[,3],xlab=expression(alpha),ylab=expression(sigma))
plot(draws.full[,2],draws.full[,3],xlab=expression(beta),ylab=expression(sigma))

tab = t(apply(draws.full,2,quantile,c(0.05,0.5,0.95)))
rownames(tab) = c("alpha","beta","sigma")
tab
##               5%        50%        95%
## alpha 2.06764694 2.16068167 2.26425048
## beta  2.64535474 3.01337054 3.41879442
## sigma 0.03492138 0.04320209 0.05496438

4.2 Posterior predictive distribution

alpha.d = draws.full[,1]
beta.d  = draws.full[,2]
sigma.d = draws.full[,3]
N       = 20
xx      = seq(min(x),max(x),length=N)
yy      = matrix(0,N,M)
for (i in 1:N)
  yy[i,] = rnorm(M,alpha.d*xx[i]/(beta.d+xx[i]),sigma.d)
quant = t(apply(yy,1,quantile,c(0.05,0.5,0.95)))

par(mfrow=c(1,2))
plot(x,y,ylab="Rate of a reaction (μmol)",xlab="Concentration of a substrate (mM)",
     ylim=range(quant,y),pch=16,cex=0.75)
lines(xx,quant[,1],lty=2,col=2,lwd=2)
lines(xx,quant[,2],col=2,lwd=2)
lines(xx,quant[,3],lty=2,col=2,lwd=2)
lines(xx,quant1[,1],lty=2,col=4,lwd=2)
lines(xx,quant1[,2],col=4,lwd=2)
lines(xx,quant1[,3],lty=2,col=4,lwd=2)
legend("topleft",legend=c("known sigma","unknown sigma"),col=c(4,2),lty=1,lwd=2,bty="n")

N        = 200
yy       = seq(1,2.5,length=N)
postpred = rep(0,N)
for (i in 1:N)
  postpred[i] = mean(dnorm(yy[i],alpha.d*10/(beta.d+10),sigma.d))

plot(yy,postpred,ylab="Posterior predictive density",xlab="Rate of a reaction (μmol)",
    type="l",col=2,ylim=c(0,8.5),lwd=2)
title("x = 10")
points(1.65,0,pch=16,cex=2)
lines(yy,postpred1[,2],col=4,lwd=2)

LS0tCnRpdGxlOiAiTm9ubGluZWFyIEdhdXNzaWFuIHJlZ3Jlc3Npb24iCnN1YnRpdGxlOiAiU0lSLCBNQ01DIGFuZCBNQyBhbGdvcml0aG1zIgphdXRob3I6ICJIZWRpYmVydCBGLiBMb3BlcyIKZGF0ZTogIjEyLzA2LzIwMjUiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDMKICAgIHRvY19jb2xsYXBzZWQ6IHRydWUKICAgIGNvZGVfZG93bmxvYWQ6IHllcwogICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCi0tLQoKIyBUaGUgTWljaGFlbGlzLU1lbnRlbiBub25saW5lYXIgbW9kZWwKCkluIGJpb2NoZW1pc3RyeSwgTWljaGFlbGlz4oCTTWVudGVuIGtpbmV0aWNzLCBuYW1lZCBhZnRlciBMZW9ub3IgTWljaGFlbGlzIGFuZCBNYXVkIE1lbnRlbiwgaXMgdGhlIHNpbXBsZXN0IGNhc2Ugb2YgZW56eW1lIGtpbmV0aWNzLCBhcHBsaWVkIHRvIGVuenltZS1jYXRhbHlzZWQgcmVhY3Rpb25zIGludm9sdmluZyB0aGUgdHJhbnNmb3JtYXRpb24gb2Ygb25lIHN1YnN0cmF0ZSBpbnRvIG9uZSBwcm9kdWN0LiBJdCB0YWtlcyB0aGUgZm9ybSBvZiBhIGRpZmZlcmVudGlhbCBlcXVhdGlvbiBkZXNjcmliaW5nIHRoZSByZWFjdGlvbiByYXRlICR5JCAozrxtb2wvbWluOk1pY3JvbW9sZXMgcGVyIG1pbnV0ZSksIGFzIGEgZnVuY3Rpb24gb2YgJHgkLCB0aGUgY29uY2VudHJhdGlvbiBvZiB0aGUgc3Vic3RyYXRlIChtTTptaWxsaW1vbGFyKSAtIFNvdXJjZTogaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvTWljaGFlbGlzLU1lbnRlbl9raW5ldGljcy4KClRoZSBkYXRhc2V0IGJlbG93IGlzIGZyb20gYSBlbnp5bWUga2luZXRpY3MgZXhwZXJpbWVudHMsIHdoaWNoIHdpbGwgYmUgbW9kZWxlZCBhcwokJAp5X2kgPSBcZnJhY3tcYWxwaGEgeF9pfXtcYmV0YSt4X2l9ICsgXGVwc2lsb25faSBccXF1YWRccXF1YWQgXGVwc2lsb25faSBcc2ltIE4oMCxcc2lnbWFeMiksCiQkCndoZXJlICRcYWxwaGEkIGlzIHRoZSBtYXhpbXVtIHJlYWN0aW9uIHJhdGUgYW5kICRcYmV0YSQgaXMgdGhlIE1pY2hhZWxpcyBjb25zdGFudC4KCgpgYGB7cn0KI2luc3RhbGwucGFja2FnZXMoIm12dG5vcm0iKQpsaWJyYXJ5KCJtdnRub3JtIikKCnN1YnN0cmF0ZSA9IGMoMC41LCAxLjAsIDIuMCwgMy4wLCA1LjAsIDcuMCwgMTAuMCwgMTUuMCkKcmF0ZSAgICAgID0gYygwLjI2LCAwLjUwLCAwLjg1LCAxLjEwLCAxLjQwLCAxLjU1LCAxLjY1LCAxLjc1KQp4ICAgICAgICAgPSBzdWJzdHJhdGUKeSAgICAgICAgID0gcmF0ZQpuICAgICAgICAgPSBsZW5ndGgoeCkKYGBgCgojIyBFeHBsb3JhdG9yeSBkYXRhIGFuYWx5c2lzCgpgYGB7ciBmaWcud2lkdGg9NixmaWcuaGVpZ2h0PTUsZmlnLmFsaWduPSdjZW50ZXInfQpwYXIobWZyb3c9YygxLDEpKQpwbG90KHgseSx5bGFiPSJSYXRlIG9mIGEgcmVhY3Rpb24gKM68bW9sKSIseGxhYj0iQ29uY2VudHJhdGlvbiBvZiBhIHN1YnN0cmF0ZSAobU0pIikKYGBgCgpIZXJlIHdlIHRyeSB0byBmaWd1cmUgb3V0ICRcYWxwaGEkIGFuZCAkXGJldGEkIGJ5IHJ1bm5pbmcgcmVncmVzc2lvbnMgdGhyb3VnaCB0aGUgb3JpZ2luIG9mIHRoZSBmb3IKJCQKeV9pID0gXGFscGhhIHpfaSArIFxlcHNpbG9uX2kKJCQgCndoZXJlICR6X2k9eF9pLyhcYmV0YSt4X2kpJCwgZm9yIGVhY2ggdmFsdWUgb2YgJFxiZXRhJCBvbiBhIGdyaWQgaW4gdGhlIGludGVydmFsICQoMCw1KSQsIGFuZCB0aGVuIGNob29zaW5nIHRoZSAkXGJldGEkIHRoYXQgbWluaW1pemVzIHRoZSByZXNpZHVhbCBzdW0gb2Ygc3F1YXJlcywgJFJTUyhcYmV0YSkkLgoKYGBge3IgZmlnLndpZHRoPTgsZmlnLmhlaWdodD00LGZpZy5hbGlnbj0nY2VudGVyJ30Kbm4gPSAxMDAKYnMgPSBzZXEoMCw1LGxlbmd0aD1ubikKcnNzID0gcmVwKDAsbm4pCmZvciAoaSBpbiAxOm5uKXsKICB4MSA9IHgvKGJzW2ldK3gpCiAgcnNzW2ldID0gbWVhbihsbSh5fngxLTEpJHJlc14yKQp9CgpiZXRhLmVkYSAgPSBic1tyc3M9PW1pbihyc3MpXQp4MSAgICAgICAgPSB4LyhiZXRhLmVkYSt4KQphbHBoYS5lZGEgPSBsbSh5fngxLTEpJGNvZWYKYWxwaGEuZWRhCmJldGEuZWRhCgpwYXIobWZyb3c9YygxLDIpKQpwbG90KGJzLHJzcyx4bGFiPWV4cHJlc3Npb24oYmV0YSkseWxhYj0iUmVzaWR1YWwgc3VtIG9mIHNxdWFyZXMiLHBjaD0xNixjZXg9MC41KQphYmxpbmUodj1iZXRhLmVkYSkKdGl0bGUocGFzdGUoImFscGhhPSIscm91bmQoYWxwaGEuZWRhLDMpLCIgLSBiZXRhPSIscm91bmQoYmV0YS5lZGEsMyksc2VwPSIiKSkKcGxvdCh4LHkseWxhYj0iUmF0ZSBvZiBhIHJlYWN0aW9uICjOvG1vbCkiLHhsYWI9IkNvbmNlbnRyYXRpb24gb2YgYSBzdWJzdHJhdGUgKG1NKSIscGNoPTE2KQp4eCA9IHNlcShtaW4oeCksbWF4KHgpLGxlbmd0aD0xMDApCmxpbmVzKHh4LGFscGhhLmVkYSp4eC8oYmV0YS5lZGEreHgpLGNvbD0yKQpwb2ludHMoeCxhbHBoYS5lZGEqeC8oYmV0YS5lZGEreCksY29sPTIscGNoPTE2KQpgYGAKCgojIE5vbmxpbmVhciBsZWFzdCBzcXVhcmVzIGVzdGltYXRpb24KCkxldCB1cyBwbG90IHRoZSBsaWtlbGlob29kIGZ1bmN0aW9uIG9uIGEgZ3JpZCBmb3IgJChcYWxwaGEsXGJldGEpJC4KCmBgYHtyIGZpZy53aWR0aD01LGZpZy5oZWlnaHQ9NSxmaWcuYWxpZ249J2NlbnRlcid9CnNpZ21hICAgPSAwLjA0MzA1IAphbHBoYS5nID0gc2VxKDEsMyxsZW5ndGg9MjAwKQpiZXRhLmcgID0gc2VxKDAsNixsZW5ndGg9MjAwKQpsaWtlICAgID0gbWF0cml4KDAsMjAwLDIwMCkKZm9yIChpIGluIDE6MjAwKQpmb3IgKGogaW4gMToyMDApCiAgbGlrZVtpLGpdID0gc3VtKGRub3JtKHksYWxwaGEuZ1tpXSp4LyhiZXRhLmdbal0reCksc2lnbWEsbG9nPVRSVUUpKQogIApjb250b3VyKGFscGhhLmcsYmV0YS5nLGV4cChsaWtlKSx4bGFiPWV4cHJlc3Npb24oYWxwaGEpLHlsYWI9ZXhwcmVzc2lvbihiZXRhKSxkcmF3bGFiZWxzPUZBTFNFKQp0aXRsZSgiTGlrZWxpaG9vZCBmdW5jdGlvbiIpCmBgYAoKCiMjIE5vbmxpbmVhciBmaXQgdmlhIGZ1bmN0aW9uICpubHMqCgpgYGB7cn0KZml0Lm5scyA9IG5scyh5fmFscGhhKngvKGJldGEreCksc3RhcnQ9bGlzdChhbHBoYT1hbHBoYS5lZGEsYmV0YT1iZXRhLmVkYSkpCgpzdW1tYXJ5KGZpdC5ubHMpCgpiZXRhLm5scyAgPSBzdW1tYXJ5KGZpdC5ubHMpJGNvZWZbMl0KYWxwaGEubmxzID0gc3VtbWFyeShmaXQubmxzKSRjb2VmWzFdCnNpZ21hLm5scyA9IHN1bW1hcnkoZml0Lm5scykkc2lnbWEKc2UgPSBzaWdtYS5ubHMqc3FydChkaWFnKHN1bW1hcnkoZml0Lm5scykkY292LnVuc2NhbGVkKSkKc2EubmxzID0gc2VbMV0Kc2IubmxzID0gc2VbMl0KYyhhbHBoYS5ubHMsYmV0YS5ubHMpCmMoc2EubmxzLHNiLm5scykKYGBgCgojIEJheWVzaWFuIGVzdGltYXRpb24KTGV0IHVzIHJld3JpdGUgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gZm9yIGNsYXJpdHkKJCQKTChcYWxwaGEsXGJldGF8XG1ib3h7ZGF0YX0pIFxwcm9wdG8gXGV4cFxsZWZ0XHstXGZyYWN7MX17MlxzaWdtYV4yfVxzdW1fe2k9MX1ebiBcbGVmdCh5X2ktXGZyYWN7XGFscGhhIHhfaX17XGJldGEgKyB4X2l9XHJpZ2h0KV4yXHJpZ2h0XH0uCiQkCldlIHdpbGwgYXNzdW1lIHRoYXQgdGhlIHByaW9yIGZvciAkKFxhbHBoYSxcYmV0YSkkIGlzIAokJApwKFxhbHBoYSxcYmV0YSk9cF9OKFxhbHBoYXxcbXVfXGFscGhhLFxzaWdtYV9cYWxwaGFeMilwKFxiZXRhfFxtdV9cYmV0YSxcc2lnbWFfXGJldGFeMiksCiQkCndoZXJlICRwX04oXGNkb3R8XHRoZXRhLFx0YXVeMikkIGlzIHRoZSBkZW5zaXR5IG9mIEdhdXNzaWFuIGRpc3RyaWJ1dGlvbiB3aXRoIG1lYW4gJFx0aGV0YSQgYW5kIHZhcmlhbmNlICRcdGF1XjIkLCAgSGVyZSB3ZSBhc3N1bWUgdGhhdCAkXG11X1xhbHBoYT0yJCwgJFxzaWdtYV9cYWxwaGFeMj0xJCwgJFxtdV9cYmV0YT0zJCBhbmQgJFxzaWdtYV9cYmV0YV4yPTEkLgoKYGBge3IgZmlnLndpZHRoPTYsZmlnLmhlaWdodD02LGZpZy5hbGlnbj0nY2VudGVyJ30KbXVhICAgPSAyCm11YiAgID0gMwpzaWdhICA9IDEKc2lnYiAgPSAxCnByaW9yID0gbWF0cml4KDAsMjAwLDIwMCkKcG9zdCAgPSBtYXRyaXgoMCwyMDAsMjAwKQpmb3IgKGkgaW4gMToyMDApCmZvciAoaiBpbiAxOjIwMCl7CiAgcHJpb3JbaSxqXSA9IGRub3JtKGFscGhhLmdbaV0sbXVhLHNpZ2EsbG9nPVRSVUUpK2Rub3JtKGJldGEuZ1tqXSxtdWIsc2lnYixsb2c9VFJVRSkKICBwb3N0W2ksal0gID0gbGlrZVtpLGpdICsgcHJpb3JbaSxqXQp9CmNvbnRvdXIoYWxwaGEuZyxiZXRhLmcsZXhwKHByaW9yKSx4bGFiPWV4cHJlc3Npb24oYWxwaGEpLHlsYWI9ZXhwcmVzc2lvbihiZXRhKSxkcmF3bGFiZWxzPUZBTFNFKQpjb250b3VyKGFscGhhLmcsYmV0YS5nLGV4cChwb3N0KSxkcmF3bGFiZWxzPUZBTFNFLGNvbD0yLGFkZD1UUlVFKQpsZWdlbmQoInRvcGxlZnQiLGxlZ2VuZD1jKCJQcmlvciIsIlBvc3RlcmlvciIpLGNvbD0xOjIsbHdkPTIsYnR5PSJuIixsdHk9MSkKYGBgCgojIyBTYW1wbGluZyBpbXBvcnRhbmNlIHJlc2FtcGxpbmcgKFNJUikKCkhlcmUsIHdlIHdpbGwgdXNlIHRoZSBvdXRwdXQgb2YgdGhlIHByZXZpb3VzIG5vbmxpbmVhciBsZWFzdCBzcXVhcmVzIGVzdGltYXRpb24gdG8gZmVlZCB0aGUgIGh5cGVycGFyYW1ldGVycyBmb3IgdGhlIHByb3Bvc2FsIGRlbnNpdGllczoKJCQKcShcYWxwaGEsXGJldGEpID0gcShcYWxwaGEpcShcYmV0YSkgXGVxdWl2IHBfTihcYWxwaGF8XGFscGhhX3tubHN9LDlcc2lnbWFfe1xhbHBoYSxubHN9XjIpCnBfTihcYmV0YXxcYmV0YV97bmxzfSw5XHNpZ21hX3tcYmV0YSxubHN9XjIpLgokJAoKYGBge3IgZmlnLndpZHRoPTcsZmlnLmhlaWdodD03LGZpZy5hbGlnbj0nY2VudGVyJ30KTSAgICAgPSAxMDAwMAptYSAgICA9IGFscGhhLm5scwpzYSAgICA9IDMqc2EubmxzCm1iICAgID0gYmV0YS5ubHMKc2IgICAgPSAzKnNiLm5scwoKCnNldC5zZWVkKDEyMzQ1KQphbHBoYXMgPSBybm9ybShNLG1hLHNhKQpiZXRhcyAgPSBybm9ybShNLG1iLHNiKQp3ICAgICAgPSByZXAoMCxNKQpmb3IgKGkgaW4gMTpNKQp3W2ldID0gc3VtKGRub3JtKHksYWxwaGFzW2ldKngvKGJldGFzW2ldK3gpLHNpZ21hLGxvZz1UUlVFKSkrCiAgICAgICBkbm9ybShhbHBoYXNbaV0sbXVhLHNpZ2EsbG9nPVRSVUUpKwogICAgICAgZG5vcm0oYmV0YXNbaV0sbXViLHNpZ2IpLQogICAgICAgZG5vcm0oYWxwaGFzW2ldLG1hLHNhLGxvZz1UUlVFKS0KICAgICAgIGRub3JtKGJldGFzW2ldLG1iLHNiLGxvZz1UUlVFKQp3ID0gZXhwKHctbWF4KHcpKQppbmQgPSBzYW1wbGUoMTpNLHNpemU9TSxyZXBsYWNlPVRSVUUscHJvYj13KQphbHBoYXMxID0gYWxwaGFzW2luZF0KYmV0YXMxID0gYmV0YXNbaW5kXQpkcmF3cy5zaXIgPSBjYmluZChhbHBoYXMxLGJldGFzMSkKCnBhcihtZnJvdz1jKDEsMSkpCmNvbnRvdXIoYWxwaGEuZyxiZXRhLmcsZXhwKHByaW9yKSx4bGFiPWV4cHJlc3Npb24oYWxwaGEpLHlsYWI9ZXhwcmVzc2lvbihiZXRhKSwKICAgICAgICBkcmF3bGFiZWxzPUZBTFNFLGNvbD0yKQpwb2ludHMoYWxwaGFzLGJldGFzLHBjaD0xNikKcG9pbnRzKGRyYXdzLnNpclssMV0sZHJhd3Muc2lyWywyXSxwY2g9MTYsY29sPTMpCmNvbnRvdXIoYWxwaGEuZyxiZXRhLmcsZXhwKHBvc3QpLGFkZD1UUlVFLGNvbD00KQpsZWdlbmQoInRvcGxlZnQiLGxlZ2VuZD1jKCJQcmlvciBkZW5zaXR5IChncmlkKSIsIlByb3Bvc2FsIGRyYXdzIiwiUG9zdGVyaW9yIChncmlkKSIsCiAgICAgICAiUG9zdGVyaW9yIGRyYXdzIChTSVIpIiksY29sPWMoMiwxLDQsMykscGNoPTE2LGJ0eT0ibiIpCmBgYAoKCgojIyBNQ01DMSAKCkluIHRoaXMgZmlyc3QgTUNNQyBzY2hlbWUsIHdlIHVzZSBhIHJhbmRvbS13YWxrIE1ldHJvcG9saXMgc3RlcCBmb3IgJFxiZXRhJCBhbmQgYSBHaWJicyBzYW1wbGVyIHN0ZXAgZm9yICRcYWxwaGEkLiAgVGhlIEdpYmJzIHNhbXBsZXIgZm9yICRcYWxwaGEkIHRha2VzIGFkdmFudGFnZSBvZiB0aGUgZmFjdCB0aGF0IGNvbmRpdGlvbmFsIG9uICRcYmV0YSQgdGhlIG5vbmxpbmVhciBtb2RlbCBiZWNvbWVzIGEgbGluZWFyIG1vZGVsIGFzIGZhciBhcyAkXGFscGhhJCBpcyBjb25jZXJuZWQgc28gdGhlIGZ1bGwgY29uZGl0aW9uYWwgJHAoXGFscGhhfFxiZXRhLFxtYm94e2RhdGF9KSQgaXMgYW4gZWFzaWx5IGRlcml2ZWQgR2F1c3NpYW4gZGlzdHJpYnV0aW9uLgoKKiBSYW5kb20gd2FsayBNZXRyb3BvbGlzIHN0ZXA6ICRcYmV0YSBcc2ltIE4oXGJldGFeeyhpKX0sdl9cYmV0YV4yKSQgCgoqIEdpYmJzIHNhbXBsZXIgc3RlcDogJFxhbHBoYXxcYmV0YSxcbWJveHtkYXRhfSBcc2ltIE4oXGdhbW1hLFxvbWVnYV4yKSQsIHdoZXJlCiQkClxvbWVnYV4yID0gXGxlZnQoIFxmcmFjezF9e1xzaWdtYV9cYWxwaGFeMn0gKyBcZnJhY3tcc3VtX3tpPTF9Xm4gel9pXjJ9e1xzaWdtYV4yfSBccmlnaHQpXnstMX0gXCBcIFwgXG1ib3h7YW5kfSBcIFwgXCBcZ2FtbWEgPSBcb21lZ2FeMlxsZWZ0KCBcZnJhY3tcbXVfXGFscGhhfXtcc2lnbWFfXGFscGhhXjJ9ICsgClxmcmFje1xzdW1fe2k9MX1ebiB5X2l6X2l9e1xzaWdtYV4yfVxyaWdodCksCiQkCndoZXJlICR6X2kgPSB4X2kvKFxiZXRhK3hfaSkkLCBmb3IgJGk9MSxcbGRvdHMsbiQuCgpgYGB7ciBmaWcud2lkdGg9MTAsZmlnLmhlaWdodD03LGZpZy5hbGlnbj0nY2VudGVyJ30KIyBNQ01DIHNldHVwCk0wICAgID0gMTAwMDAKTSAgICAgPSAyMDAwMApMICAgICA9IDEKbml0ZXIgPSBNMCtNKkwKdi5iICAgPSAwLjUKYmV0YSAgPSBiZXRhLm5scwpkcmF3cyA9IG1hdHJpeCgwLG5pdGVyLDIpCmZvciAoaXRlciBpbiAxOm5pdGVyKXsKICAjIHNhbXBsaW5nIGFscGhhIChHaWJicyBzdGVwKQogIHogICAgID0geC8oYmV0YSt4KQogIHZhciAgID0gMS8oMS9zaWdhXjIrc3VtKHpeMikvc2lnbWFeMikKICBtZWFuICA9IHZhcioobXVhL3NpZ2FeMitzdW0oeip5KS9zaWdtYV4yKQogIGFscGhhID0gcm5vcm0oMSxtZWFuLHNxcnQodmFyKSkKICAjIHNhbXBsaW5nIGJldGEgKHJhbmRvbS13YWxrIE1ldHJvcG9saXMgc3RlcCkKICBiZXRhMSAgICAgPSBybm9ybSgxLGJldGEsdi5iKQogIGxvZ2FjY2VwdCA9IG1pbigwLGRub3JtKGJldGExLG11YixzaWdiLGxvZz1UUlVFKStzdW0oZG5vcm0oeSxhbHBoYSp4LyhiZXRhMSt4KSxzaWdtYSxsb2c9VFJVRSkpLQogICAgICAgICAgICAgICAgICAgIGRub3JtKGJldGEsbXViLHNpZ2IsbG9nPVRSVUUpLXN1bShkbm9ybSh5LGFscGhhKngvKGJldGEreCksc2lnbWEsbG9nPVRSVUUpKSkKICBpZiAobG9nKHJ1bmlmKDEpKTxsb2dhY2NlcHQpewogICAgYmV0YSA9IGJldGExCiAgfQogIGRyYXdzW2l0ZXIsXSA9IGMoYWxwaGEsYmV0YSkKfQpkcmF3cy5tY21jMSA9IGRyYXdzW3NlcShNMCsxLG5pdGVyLGJ5PUwpLF0KCgpuYW1lcyA9IGMoImFscGhhIiwiYmV0YSIpCnBhcihtZnJvdz1jKDIsMykpCmZvciAoaSBpbiAxOjIpewogIHRzLnBsb3QoZHJhd3MubWNtYzFbLGldLHlsYWI9IiIsbWFpbj1uYW1lc1tpXSkKICBhY2YoZHJhd3MubWNtYzFbLGldLG1haW49IiIpCiAgaGlzdChkcmF3cy5tY21jMVssaV0seGxhYj0iIixtYWluPSIiLHByb2I9VFJVRSkKfQpgYGAKCgojIyBNQ01DMgoKSGVyZSwgd2UgZGVjaWRlZCB0byBzYW1wbGUgJChcYWxwaGEsXGJldGEpJCBqb2ludGx5IGluIHRoZSBNQ00gc2NoZW1lLiAgSW4gb3JkZXIgdG8gZG8gdGhhdCwgd2UgaW1wbGVtZW50IGFuIGluZGVwZW5kZW50IE1ldHJvcG9saXMgYWxnb3JpdGhtIGZvciAkKFxhbHBoYSxcYmV0YSkkIHdoZXJlIHRoZSBwcm9wb3NhbCAkcShcYWxwaGEsXGJldGEpJCBpcyB0aGUgc2FtZSBvbmUgdXNlZCBpbiBvdXIgaW1wbGVtZW50YXRpb24gb2YgdGhlIGFib3ZlIFNJUiBzY2hlbWUuCgpgYGB7ciBmaWcud2lkdGg9MTAsZmlnLmhlaWdodD03LGZpZy5hbGlnbj0nY2VudGVyJ30KYWxwaGEgPSBhbHBoYS5ubHMKYmV0YSAgPSBiZXRhLm5scwpuaXRlciA9IE0wK00qTApkcmF3cyA9IG1hdHJpeCgwLG5pdGVyLDIpCmZvciAoaXRlciBpbiAxOm5pdGVyKXsKICBhbHBoYTEgPSBybm9ybSgxLG1hLHNhKQogIGJldGExICA9IHJub3JtKDEsbWIsc2IpCiAgcG9zdC5uID0gZG5vcm0oYWxwaGExLG11YSxzaWdhLGxvZz1UUlVFKStkbm9ybShiZXRhMSxtdWIsc2lnYixsb2c9VFJVRSkrCiAgICAgICAgICAgc3VtKGRub3JtKHksYWxwaGExKngvKGJldGExK3gpLHNpZ21hLGxvZz1UUlVFKSkKICBwb3N0LmQgPSBkbm9ybShhbHBoYSxtdWEsc2lnYSxsb2c9VFJVRSkrZG5vcm0oYmV0YSxtdWIsc2lnYixsb2c9VFJVRSkrCiAgICAgICAgICAgc3VtKGRub3JtKHksYWxwaGEqeC8oYmV0YSt4KSxzaWdtYSxsb2c9VFJVRSkpCiAgcHJvcC5uID0gZG5vcm0oYWxwaGEsbWEsc2EpK2Rub3JtKGJldGEsbWIsc2IpCiAgcHJvcC5kID0gZG5vcm0oYWxwaGExLG1hLHNhKStkbm9ybShiZXRhMSxtYixzYikKICBsb2dhY2NlcHQgPSBtaW4oMCxwb3N0Lm4tcG9zdC5kK3Byb3Aubi1wcm9wLmQpCiAgaWYgKGxvZyhydW5pZigxKSk8bG9nYWNjZXB0KXsKICAJYWxwaGEgPSBhbHBoYTEKICAgIGJldGEgPSBiZXRhMQogIH0KICBkcmF3c1tpdGVyLF0gPSBjKGFscGhhLGJldGEpCn0KZHJhd3MubWNtYzIgPSBkcmF3c1tzZXEoTTArMSxuaXRlcixieT1MKSxdCgpwYXIobWZyb3c9YygyLDMpKQpmb3IgKGkgaW4gMToyKXsKICB0cy5wbG90KGRyYXdzLm1jbWMyWyxpXSx5bGFiPSIiLG1haW49bmFtZXNbaV0pCiAgYWNmKGRyYXdzLm1jbWMyWyxpXSxtYWluPSIiKQogIGhpc3QoZHJhd3MubWNtYzJbLGldLHhsYWI9IiIsbWFpbj0iIixwcm9iPVRSVUUpCn0KYGBgCgojIyBNQwoKSGVyZSwgd2UgaW50ZWdyYXRlIG91dCAkXGFscGhhJCBhbmFseXRpY2FsbHkgaW4gb3JkZXIgdG8gb2J0YWluICRwKFxiZXRhfFxtYm94e2RhdGF9KSQuIFRoZW4gd2Ugc2FtcGxlICRcYmV0YSQgZnJvbSB0aGlzIG1hcmdpbmFsIHBvc3RlcmlvciBkaXN0cmlidXRpb24gdmlhIFNJUi4gIFRoZW4sIHRoZSAkXGJldGEkIGRyYXdzIGFyZSB1c2VkIHRvIGRpcmVjdGx5IHNhbXBsZSAkXGFscGhhJCBmcm9tICRwKFxhbHBoYXxcYmV0YSxcbWJveHtkYXRhfSkkLiAgVGhlcmVmb3JlLCBhbiBNQ01DIGlzIG5vdCBuZWVkZWQhIAoKMSkgU2FtcGxlICRce1xiZXRhXnsoMSl9LFxsZG90cyxcYmV0YV57KE0pfVx9JCBmcm9tICRwKFxiZXRhfFxtYm94e2RhdGF9KSQgdmlhIFNJUiB3aXRoIHByb3Bvc2FsICRxKFxiZXRhKT1wX04oXGJldGF8XGJldGFfe25sc30sXHNpZ21hX3tubHN9XjIpJC4gIFRvIGltcGxlbWVudCBTSVIgd2UgbmVlZCB0aGUgaW50ZWdyYXRlZCBsaWtlbGlob29kIGZvciAkXGJldGEkIGdpdmVuICR5PSh5XzEsXGxkb3RzLHlfbiknJDoKJCQKcCh5fFxiZXRhKSA9IFxpbnRfey1caW5mdHl9XntcaW5mdHl9IHAoeXxcYWxwaGEsXGJldGEpcChcYWxwaGEpZFxhbHBoYSA9IApwX04oeXxcbXVfXGFscGhhIHosXHNpZ21hXjIgSV9uICsgXHNpZ21hX1xhbHBoYV4yIHp6JyksCiQkCndoZXJlICR6PSh6XzEsXGxkb3RzLHpfbiknJCBhbmQgJHpfaT14X2kvKFxiZXRhK3hfaSkkLCBmb3IgJGk9MSxcbGRvdHMsbiQuICBOb3RpY2UgdGhhdCwgYnkgaW50ZWdyYXRpb24gJFxhbHBoYSQgb3V0LCB0aGUgbWFyZ2luYWwgJHAoeXxcYmV0YSkkIGlzIGEgbXVsdGl2YXJpYXRlIG5vcm1hbCB3aXRoIG5vbi1kaWFnb25hbCB2YXJpYW5jZSBmdW5jdGlvbiBvZiB0aGUgJChuIFx0aW1lcyBuJCkgbWF0cml4ICR6eickLgoKMikgU2FtcGxlICRcYWxwaGFeeyhpKX0kIGZyb20gJHAoXGFscGhhfFxiZXRhXnsoaSl9LFxtYm94e2RhdGF9KSQsIHNpbWlsYXIgdG8gdGhlIEdpYmJzIHNhbXBsZXIgc3RlcCBvZiB0aGUgYWJvdmUgTUNNQzEgYWxnb3JpdGhtLgoKYGBge3IgZmlnLndpZHRoPTEwLGZpZy5oZWlnaHQ9NyxmaWcuYWxpZ249J2NlbnRlcid9CiMgc2FtcGxpbmcgYmV0YSBmcm9tIHAoYmV0YXxkYXRhKQpNICAgID0gMTAwMDAKYmV0YSA9IHJub3JtKE0sbWIsc2IpCmZvciAoaSBpbiAxOk0pewogeHggPSB4LyhiZXRhW2ldK3gpCiBtZWFuID0gbXVhKnh4CiB2YXIgPSBzaWdhXjIqeHglKiV0KHh4KStkaWFnKHNpZ21hXjIsbikKIHdbaV0gPSBkbXZub3JtKHksbWVhbj1tZWFuLHNpZ21hPXZhcixsb2c9VFJVRSkrCiAgICAgICAgZG5vcm0oYmV0YVtpXSxtdWIsc2lnYixsb2c9VFJVRSktCiAgICAgICAgZG5vcm0oYmV0YVtpXSxtYixzYixsb2c9VFJVRSkKfQp3ICAgICA9IGV4cCh3LW1heCh3KSkKYmV0YTEgPSBzYW1wbGUoYmV0YSxzaXplPU0scmVwbGFjZT1UUlVFLHByb2I9dykKYmV0YSAgPSBiZXRhMQoKIyBzYW1wbGluZyBhbHBoYSBmcm9tIHAoYWxwaGF8YmV0YSxkYXRhKQphbHBoYSA9IHJlcCgwLE0pCmZvciAoaSBpbiAxOk0pewogIHogICAgICAgID0geC8oYmV0YVtpXSt4KQogIHZhciAgICAgID0gMS8oMS9zaWdhXjIrc3VtKHpeMikvc2lnbWFeMikKICBtZWFuICAgICA9IHZhcioobXVhL3NpZ2FeMitzdW0oeip5KS9zaWdtYV4yKQogIGFscGhhW2ldID0gcm5vcm0oMSxtZWFuLHNxcnQodmFyKSkKfQpkcmF3cy5tYyA9IGNiaW5kKGFscGhhLGJldGEpCgpwYXIobWZyb3c9YygyLDIpKQpmb3IgKGkgaW4gMToyKXsKICB0cy5wbG90KGRyYXdzLm1jWyxpXSx5bGFiPSIiLG1haW49bmFtZXNbaV0pCiAgaGlzdChkcmF3cy5tY1ssaV0seGxhYj0iIixtYWluPSIiLHByb2I9VFJVRSkKfQpgYGAKCiMjIENvbXBhcmluZyBNQyBhbmQgTUNNQyBhbGdvcml0aG1zCgpgYGB7ciBmaWcud2lkdGg9MTAsZmlnLmhlaWdodD04LGZpZy5hbGlnbj0nY2VudGVyJ30KcGFyKG1mcm93PWMoMiwyKSkKeHJhbmdlID0gcmFuZ2UoZHJhd3Muc2lyWywxXSxkcmF3cy5tY21jMVssMV0sZHJhd3MubWNtYzJbLDFdLGRyYXdzLm1jWywxXSkKeXJhbmdlID0gcmFuZ2UoZHJhd3Muc2lyWywyXSxkcmF3cy5tY21jMVssMl0sZHJhd3MubWNtYzJbLDJdLGRyYXdzLm1jWywyXSkKcGxvdChkcmF3cy5zaXJbLDFdLGRyYXdzLnNpclssMl0seGxhYj1leHByZXNzaW9uKGFscGhhKSx5bGFiPWV4cHJlc3Npb24oYmV0YSkscGNoPTE2LHlsaW09eXJhbmdlLHhsaW09eHJhbmdlKQp0aXRsZSgiU0lSIikKY29udG91cihhbHBoYS5nLGJldGEuZyxleHAocG9zdCksYWRkPVRSVUUsY29sPTUsZHJhd2xhYmVscz1GQUxTRSkKcGxvdChkcmF3cy5tY21jMVssMV0sZHJhd3MubWNtYzFbLDJdLHhsYWI9ZXhwcmVzc2lvbihhbHBoYSkseWxhYj1leHByZXNzaW9uKGJldGEpLHBjaD0xNix5bGltPXlyYW5nZSx4bGltPXhyYW5nZSkKdGl0bGUoIk1DTUMgMSIpCmNvbnRvdXIoYWxwaGEuZyxiZXRhLmcsZXhwKHBvc3QpLGFkZD1UUlVFLGNvbD01LGRyYXdsYWJlbHM9RkFMU0UpCnBsb3QoZHJhd3MubWNtYzJbLDFdLGRyYXdzLm1jbWMyWywyXSx4bGFiPWV4cHJlc3Npb24oYWxwaGEpLHlsYWI9ZXhwcmVzc2lvbihiZXRhKSxwY2g9MTYseWxpbT15cmFuZ2UseGxpbT14cmFuZ2UpCnRpdGxlKCJNQ01DIDIiKQpjb250b3VyKGFscGhhLmcsYmV0YS5nLGV4cChwb3N0KSxhZGQ9VFJVRSxjb2w9NSxkcmF3bGFiZWxzPUZBTFNFKQpwbG90KGRyYXdzLm1jWywxXSxkcmF3cy5tY1ssMl0seGxhYj1leHByZXNzaW9uKGFscGhhKSx5bGFiPWV4cHJlc3Npb24oYmV0YSkscGNoPTE2LHlsaW09eXJhbmdlLHhsaW09eHJhbmdlKQp0aXRsZSgiTUMiKQpjb250b3VyKGFscGhhLmcsYmV0YS5nLGV4cChwb3N0KSxhZGQ9VFJVRSxjb2w9NSxkcmF3bGFiZWxzPUZBTFNFKQpgYGAKCmBgYHtyIGZpZy53aWR0aD0xMCxmaWcuaGVpZ2h0PTYsZmlnLmFsaWduPSdjZW50ZXInfQpwYXIobWZyb3c9YygxLDIpKQpwbG90KGRlbnNpdHkoZHJhd3Muc2lyWywxXSkseGxhYj0iIixtYWluPWV4cHJlc3Npb24oYWxwaGEpKQpsaW5lcyhkZW5zaXR5KGRyYXdzLm1jbWMxWywxXSksY29sPTIpCmxpbmVzKGRlbnNpdHkoZHJhd3MubWNtYzJbLDFdKSxjb2w9MykKbGluZXMoZGVuc2l0eShkcmF3cy5tY1ssMV0pLGNvbD00KQpwbG90KGRlbnNpdHkoZHJhd3Muc2lyWywyXSkseGxhYj0iIixtYWluPWV4cHJlc3Npb24oYmV0YSkpCmxpbmVzKGRlbnNpdHkoZHJhd3MubWNtYzFbLDJdKSxjb2w9MikKbGluZXMoZGVuc2l0eShkcmF3cy5tY21jMlssMl0pLGNvbD0zKQpsaW5lcyhkZW5zaXR5KGRyYXdzLm1jWywyXSksY29sPTQpCmBgYAoKYGBge3J9CnRhYi5hID0gcmJpbmQocXVhbnRpbGUoZHJhd3Muc2lyWywxXSxjKDAuMDUsMC4yNSwwLjUsMC43NSwwLjk1KSksCnF1YW50aWxlKGRyYXdzLm1jbWMxWywxXSxjKDAuMDUsMC4yNSwwLjUsMC43NSwwLjk1KSksCnF1YW50aWxlKGRyYXdzLm1jbWMyWywxXSxjKDAuMDUsMC4yNSwwLjUsMC43NSwwLjk1KSksCnF1YW50aWxlKGRyYXdzLm1jWywxXSxjKDAuMDUsMC4yNSwwLjUsMC43NSwwLjk1KSkpCgp0YWIuYiA9IHJiaW5kKHF1YW50aWxlKGRyYXdzLnNpclssMl0sYygwLjA1LDAuMjUsMC41LDAuNzUsMC45NSkpLApxdWFudGlsZShkcmF3cy5tY21jMVssMl0sYygwLjA1LDAuMjUsMC41LDAuNzUsMC45NSkpLApxdWFudGlsZShkcmF3cy5tY21jMlssMl0sYygwLjA1LDAuMjUsMC41LDAuNzUsMC45NSkpLApxdWFudGlsZShkcmF3cy5tY1ssMl0sYygwLjA1LDAuMjUsMC41LDAuNzUsMC45NSkpKQoKcm93bmFtZXModGFiLmEpID0gYygiU0lSIiwiTUNNQzEiLCJNQ01DMiIsIk1DIikKcm93bmFtZXModGFiLmIpID0gYygiU0lSIiwiTUNNQzEiLCJNQ01DMiIsIk1DIikKCnJvdW5kKHRhYi5hLDIpCnJvdW5kKHRhYi5iLDIpCmBgYAoKIyMgUG9zdGVyaW9yIHByZWRpY3RpdmUgZGlzdHJpYnV0aW9uCgpBIGZpbmFsIGV4ZXJjaXNlIGlzIHRvIG9idGFpbiBhIE1vbnRlIENhcmxvIGFwcHJveGltYXRpb24gdG8gdGhlIHBvc3RlcmlvciBwcmVkaWN0aXZlIG9mICR5JCBmb3IgYSBuZXcgdmFsdWUgb2YgJHgkLCBzYXkgJHtcd2lkZXRpbGRlIHh9JDoKJCQKcCh7XHdpZGV0aWxkZSB5fXx7XHdpZGV0aWxkZSB4fSkgPSBcaW50X3stXGluZnR5fV57XGluZnR5fVxpbnRfey1caW5mdHl9XntcaW5mdHl9IApwX05cbGVmdCh7XHdpZGV0aWxkZSB5fXxcZnJhY3tcYWxwaGF7XHdpZGV0aWxkZSB4fX17XGJldGEre1x3aWRldGlsZGUgeH19LFxzaWdtYV4yXHJpZ2h0KQpwKFxhbHBoYSxcYmV0YXxcbWJveHtkYXRhfSlkXGFscGhhIGRcYmV0YSwKJCQKd2hpY2ggY2FuIGJlIGFwcHJveGltYXRlZCBieQokJApwX3tNQ30oe1x3aWRldGlsZGUgeX18e1x3aWRldGlsZGUgeH0pID0gXGZyYWMxTVxzdW1fe2k9MX1eTiBwX05cbGVmdCh7XHdpZGV0aWxkZSB5fXxcZnJhY3tcYWxwaGFeeyhpKX17XHdpZGV0aWxkZSB4fX17XGJldGFeeyhpKX0re1x3aWRldGlsZGUgeH19LFxzaWdtYV4yXHJpZ2h0KQokJAp3aGVyZSAkXHsoXGFscGhhLFxiZXRhKV57KDEpfSxcbGRvdHMsKFxhbHBoYSxcYmV0YSleeyhNKX1cfSQgaXMgYSBNb250ZSBDYXJsbyBzYW1wbGUgZnJvbSAkcChcYWxwaGEsXGJldGF8XG1ib3h7ZGF0YX0pJCwgd2hpY2ggY291bGQgYmUgZnJvbSBhbnkgb2YgdGhlIHByZXZpb3VzIDQgc2NoZW1lcyB3ZSBhcmxlYWR5IGltcGxlbWVudGUsIGllLiBTSVIsIE1DTUMxLCBNQ01DMiBvciBNQy4gIAoKYGBge3IgZmlnLndpZHRoPTgsZmlnLmhlaWdodD00LGZpZy5hbGlnbj0nY2VudGVyJ30KIyBQb3N0ZXJpb3IgcHJlZGljdGl2ZSBmb3IgeG5ldz01IGFuZCB4bmV3PTEwCmFscGhhLmQgID0gZHJhd3MubWNbLDFdCmJldGEuZCAgID0gZHJhd3MubWNbLDJdCk4gICAgICAgID0gMjAwCnl5ICAgICAgID0gc2VxKDEsMi41LGxlbmd0aD1OKQpwb3N0cHJlZCA9IG1hdHJpeCgwLE4sMikKZm9yIChpIGluIDE6Til7CiAgcG9zdHByZWRbaSwxXSA9IG1lYW4oZG5vcm0oeXlbaV0sYWxwaGEuZCo1LyhiZXRhLmQrNSksc2lnbWEpKQogIHBvc3RwcmVkW2ksMl0gPSBtZWFuKGRub3JtKHl5W2ldLGFscGhhLmQqMTAvKGJldGEuZCsxMCksc2lnbWEpKQp9CnBhcihtZnJvdz1jKDEsMikpCnBsb3QoeXkscG9zdHByZWRbLDFdLHlsYWI9IlBvc3RlcmlvciBwcmVkaWN0aXZlIGRlbnNpdHkiLHhsYWI9IlJhdGUgb2YgYSByZWFjdGlvbiAozrxtb2wpIix0eXBlPSJsIikKdGl0bGUoInggPSA1IikKcG9pbnRzKDEuNCwwLHBjaD0xNixjZXg9MikKcGxvdCh5eSxwb3N0cHJlZFssMl0seWxhYj0iUG9zdGVyaW9yIHByZWRpY3RpdmUgZGVuc2l0eSIseGxhYj0iUmF0ZSBvZiBhIHJlYWN0aW9uICjOvG1vbCkiLHR5cGU9ImwiKQp0aXRsZSgieCA9IDEwIikKcG9pbnRzKDEuNjUsMCxwY2g9MTYsY2V4PTIpCnBvc3RwcmVkMSA9IHBvc3RwcmVkCmBgYAoKClNpbWlsYXJseSwgZ2l2ZW4gJHtcd2lkZXRpbGRlIHh9JCwgYSBzYW1wbGUgZnJvbSAkcCh5fHtcd2lkZXRpbGRlIHh9KSQgY2FuIGJlIG9idGFpbmVkIGFzIGZvbGxvd3MKJCQKe1x3aWRldGlsZGUgeX1eeyhpKX0gXHNpbSBOXGxlZnQoXGZyYWN7XGFscGhhXnsoaSl9e1x3aWRldGlsZGUgeH19e1xiZXRhXnsoaSl9K3tcd2lkZXRpbGRlIHh9fSxcc2lnbWFeMlxyaWdodCksIFxxcXVhZFxxcXVhZCBpPTEsXGxkb3RzLE0uCiQkClRoZXJlZm9yZSwgJFx7e1x3aWRldGlsZGUgeX1eeygxKX0sXGxkb3RzLHtcd2lkZXRpbGRlIHl9XnsoTSl9XH0kIGlzIGEgc2FtcGxlIGZyb20gJHAoeXx7XHdpZGV0aWxkZSB4fSkkLgoKYGBge3IgZmlnLndpZHRoPTcsZmlnLmhlaWdodD03LGZpZy5hbGlnbj0nY2VudGVyJ30KYWxwaGEuZCA9IGRyYXdzLm1jWywxXQpiZXRhLmQgID0gZHJhd3MubWNbLDJdCk4gICAgICAgPSAyMAp4eCAgICAgID0gc2VxKG1pbih4KSxtYXgoeCksbGVuZ3RoPU4pCnl5ICAgICAgPSBtYXRyaXgoMCxOLE0pCmZvciAoaSBpbiAxOk4pCiAgeXlbaSxdID0gcm5vcm0oTSxhbHBoYS5kKnh4W2ldLyhiZXRhLmQreHhbaV0pLHNpZ21hKQpxdWFudCA9IHQoYXBwbHkoeXksMSxxdWFudGlsZSxjKDAuMDUsMC41LDAuOTUpKSkKCnBhcihtZnJvdz1jKDEsMSkpCnBsb3QoeCx5LHlsYWI9IlJhdGUgb2YgYSByZWFjdGlvbiAozrxtb2wpIix4bGFiPSJDb25jZW50cmF0aW9uIG9mIGEgc3Vic3RyYXRlIChtTSkiLAogICAgIHlsaW09cmFuZ2UocXVhbnQseSkscGNoPTE2LGNleD0wLjc1KQpsaW5lcyh4eCxxdWFudFssMV0sbHR5PTIsY29sPTIsbHdkPTIpCmxpbmVzKHh4LHF1YW50WywyXSxjb2w9Mixsd2Q9MikKbGluZXMoeHgscXVhbnRbLDNdLGx0eT0yLGNvbD0yLGx3ZD0yKQpxdWFudDEgPSBxdWFudApgYGAKCgojIExlYXJuaW5nICQoXGFscGhhLFxiZXRhLFxzaWdtYV4yKSQKQXMgYSBmaW5hbCB0YXNrLCBsZXQgdXMgbm93IGNvbnNpZGVyIHVua25vd24gdGhlIGVycm9yIHZhcmlhbmNlLCAkXHNpZ21hXjIkLCBhbmQgYXNzdW1lIGl0cyBwcmlvciBpcyBhIGludmVyc2UtZ2FtbWEgZGlzdHJpYnV0aW9uIHdpdGggcGFyYW1ldGVycyAkYV8wJCBhbmQgJGJfMCQsIGRlbm90ZWQgYnkgJFxzaWdtYV4yIFxzaW0gSUcoYV8wLGJfMCkkIHdpdGggZGVuc2l0eQokJApwKFxzaWdtYV4yfGFfMCxiXzApIFxwcm9wdG8gKFxzaWdtYV4yKV57LShhXzArMSl9XGV4cFx7LWJfMC9cc2lnbWFeMlx9LgokJApUaGVyZWZvcmUsIHRoZSBmdWxsIGNvbmRpdGlvbmFsIHBvc3RlcmlvciBkaXN0cmlidXRpb24gb2YgJFxzaWdtYV4yJCBjYW4gYmUgZWFzaWx5IGRlcml2ZWQgYnkgbm90aWNpbmcgdGhhdCAKJCQKel9pIFxlcXVpdiB5X2ktXGZyYWN7XGFscGhhIHhfaX17XGJldGEreF9pfSBcc2ltIE4oMCxcc2lnbWFeMiksCiQkCmhhcyBsaWtlbGlob29kIAokJApMKFxzaWdtYV4yfFxtYm94e2RhdGF9KSBccHJvcHRvIChcc2lnbWFeMileey1uLzJ9XGV4cFxsZWZ0XHstXGZyYWMxMlxzdW1fe2k9MX1ebiB6X2leMlxzaWdtYV4yXHJpZ2h0XH0uCiQkCkNvbWJpbmluZyAkcChcc2lnbWFeMnxhXzAsYl8wKSQgYW5kICRMKFxzaWdtYV4yfFxtYm94e2RhdGF9KSQsIGxlYWRzIHRvIAokJApwKFxzaWdtYV4yfFxhbHBoYSxcYmV0YSxcbWJveHtkYXRhfSkgXHByb3B0byAoXHNpZ21hXjIpXnstKGFfMCtuLzIrMSl9XGV4cFxsZWZ0XHstXGZyYWN7Yl8wK1xzdW1fe2k9MX1ebiB6X2leMi8yfXtcc2lnbWFeMn1ccmlnaHRcfSwKJCQKd2hpY2ggaXMgYW4gaW52ZXJzZS1nYW1tYSB3aXRoIHBhcmFtZXRlcnMgJGFfMCtuLzIkIGFuZCAkYl8wK1xzdW1fe2k9MX1ebiB6X2leMi8yJC4gIEhlcmUgd2Ugd2lsbCBjb25zaWRlciBhIGZhaXJseSB1bmluZm9ybWF0aXZlIHByaW9yIGZvciAkXHNpZ21hXjIkIHdpdGggJGFfMD0xMCQgYW5kICRiXzA9MC4wMTgkLiBUaGUgcHJpb3IgbWVhbiBmb3IgJFxzaWdtYV4yJCBpcyAkMC4wNF4yJC4gIFRoZSA5NSUgcHJpb3IgY3JlZGliaWxpdHkgaW50ZXJ2YWwgKEMuSS4pIGZvciAkXHNpZ21hXjIkIGlzICQoMC4wMDEwNTQsMC4wMDM3NTQpJC4gSXQgaXMgd29ydGggbm90aW5nIHRoYXQgdGhlIDk1JSBwcmlvciBDLkkuIGZvciAkXHNpZ21hJCBpcyAKJCgwLjAzMjQsMC4wNjEzKSQuICBSZWNhbGwgdGhhdCB3ZSBmaXhlZCAkXHNpZ21hPTAuMDQzMDUkIGluIHRoZSBwcmV2aW91cyBhbmFseXNlcy4KClRoZXJlZm9yZSwgd2Ugb25seSBuZWVkIHRvIGFkZCBhbm90aGVyIGxheWVyIGluIHRoZSBNQ01DIHNjaGVtZSB0aGF0IHdhcyBkZXNpZ25lZCB0byBzYW1wbGUgZnJvbSAkcChcYWxwaGEsXGJldGF8XG1ib3h7ZGF0YX0sXHNpZ21hXjIpJC4gIFRoZSBjb21wb3NpdGlvbmFsIGFzcGVjdCBvZiB0aGUgR2liYnMgc2FtcGxlciBvciwgbW9yZSBnZW5lcmFsbHksIG9mIGFsbCBNQ01DIHNjaGVtZXMgaXMgb25lIG9mIGl0cyBtYWluIHN0cmVuZ3RocyBhbmQgb25lIGNhbiBhcmd1ZSB0aGF0IGl0IGlzIHRoZSBtYWluIHJlYXNvbiBmb3IgdGhlIG1hc3NpdmUgc3VjY2VzcyBvZiBNQ01DIGZvciBtb2Rlcm4gQmF5ZXNpYW4gaW5mZXJlbmNlIHRoYXQgc3ByZWFkZWQgcXVpY2tseSB0byB2aXJ0dWFsbHkgYWxsIGFyZWFzIG9mIGFwcGxpZWQgc2NpZW5jZXMuCgpgYGB7ciBmaWcud2lkdGg9MTAsZmlnLmhlaWdodD0xMCxmaWcuYWxpZ249J2NlbnRlcid9CiMgSHlwZXJwYXJhbWV0ZXJzIG9mIHAoc2lnbWFeMikKYTAgPSAxMApiMCA9IDAuMDE4CgojIE1DTUMgc2V0dXAKc2V0LnNlZWQoMTI1NjYpCk0wICAgID0gMjAwMApNICAgICA9IDUwMDAKTCAgICAgPSA0MApuaXRlciA9IE0wK00qTAp2LmIgICA9IDAuNQpiZXRhICA9IGJldGEubmxzCnNpZ21hID0gMC4wNDMwNSAKZHJhd3MgPSBtYXRyaXgoMCxuaXRlciwzKQpmb3IgKGl0ZXIgaW4gMTpuaXRlcil7CiAgIyBzYW1wbGluZyBhbHBoYSAoR2liYnMgc3RlcCkKICB6ICAgICA9IHgvKGJldGEreCkKICB2YXIgICA9IDEvKDEvc2lnYV4yK3N1bSh6XjIpL3NpZ21hXjIpCiAgbWVhbiAgPSB2YXIqKG11YS9zaWdhXjIrc3VtKHoqeSkvc2lnbWFeMikKICBhbHBoYSA9IHJub3JtKDEsbWVhbixzcXJ0KHZhcikpCiAgIyBzYW1wbGluZyBiZXRhIChyYW5kb20td2FsayBNZXRyb3BvbGlzIHN0ZXApCiAgYmV0YTEgICAgID0gcm5vcm0oMSxiZXRhLHYuYikKICBsb2dhY2NlcHQgPSBtaW4oMCxkbm9ybShiZXRhMSxtdWIsc2lnYixsb2c9VFJVRSkrc3VtKGRub3JtKHksYWxwaGEqeC8oYmV0YTEreCksc2lnbWEsbG9nPVRSVUUpKS0KICAgICAgICAgICAgICAgICAgICBkbm9ybShiZXRhLG11YixzaWdiLGxvZz1UUlVFKS1zdW0oZG5vcm0oeSxhbHBoYSp4LyhiZXRhK3gpLHNpZ21hLGxvZz1UUlVFKSkpCiAgaWYgKGxvZyhydW5pZigxKSk8bG9nYWNjZXB0KXsKICAgIGJldGEgPSBiZXRhMQogIH0KICBlICAgID0geS1hbHBoYSp4LyhiZXRhK3gpCiAgcGFyMSA9IGEwICsgbi8yCiAgcGFyMiA9IGIwICsgc3VtKGVeMikvMgogIHNpZ21hID0gc3FydCgxL3JnYW1tYSgxLHBhcjEscGFyMikpCiAgZHJhd3NbaXRlcixdID0gYyhhbHBoYSxiZXRhLHNpZ21hKQp9CmRyYXdzLmZ1bGwgPSBkcmF3c1tzZXEoTTArMSxuaXRlcixieT1MKSxdCgoKbmFtZXMgPSBjKCJhbHBoYSIsImJldGEiLCJzaWdtYSIpCnBhcihtZnJvdz1jKDMsMykpCmZvciAoaSBpbiAxOjMpewogIHRzLnBsb3QoZHJhd3MuZnVsbFssaV0seWxhYj0iIixtYWluPW5hbWVzW2ldKQogIGFjZihkcmF3cy5mdWxsWyxpXSxtYWluPSIiKQogIGhpc3QoZHJhd3MuZnVsbFssaV0seGxhYj0iIixtYWluPSIiLHByb2I9VFJVRSkKfQpgYGAKCiMjIEJpdmFyaWF0ZSBtYXJnaW5hbCBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9ucwoKYGBge3IgZmlnLndpZHRoPTEwLGZpZy5oZWlnaHQ9NCxmaWcuYWxpZ249J2NlbnRlcid9CnBhcihtZnJvdz1jKDEsMykpCnBsb3QoZHJhd3MuZnVsbFssMV0sZHJhd3MuZnVsbFssMl0seGxhYj1leHByZXNzaW9uKGFscGhhKSx5bGFiPWV4cHJlc3Npb24oYmV0YSkpCnBsb3QoZHJhd3MuZnVsbFssMV0sZHJhd3MuZnVsbFssM10seGxhYj1leHByZXNzaW9uKGFscGhhKSx5bGFiPWV4cHJlc3Npb24oc2lnbWEpKQpwbG90KGRyYXdzLmZ1bGxbLDJdLGRyYXdzLmZ1bGxbLDNdLHhsYWI9ZXhwcmVzc2lvbihiZXRhKSx5bGFiPWV4cHJlc3Npb24oc2lnbWEpKQoKdGFiID0gdChhcHBseShkcmF3cy5mdWxsLDIscXVhbnRpbGUsYygwLjA1LDAuNSwwLjk1KSkpCnJvd25hbWVzKHRhYikgPSBjKCJhbHBoYSIsImJldGEiLCJzaWdtYSIpCnRhYgpgYGAKCiMjIFBvc3RlcmlvciBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbgpgYGB7ciBmaWcud2lkdGg9MTAsZmlnLmhlaWdodD02LGZpZy5hbGlnbj0nY2VudGVyJ30KYWxwaGEuZCA9IGRyYXdzLmZ1bGxbLDFdCmJldGEuZCAgPSBkcmF3cy5mdWxsWywyXQpzaWdtYS5kID0gZHJhd3MuZnVsbFssM10KTiAgICAgICA9IDIwCnh4ICAgICAgPSBzZXEobWluKHgpLG1heCh4KSxsZW5ndGg9TikKeXkgICAgICA9IG1hdHJpeCgwLE4sTSkKZm9yIChpIGluIDE6TikKICB5eVtpLF0gPSBybm9ybShNLGFscGhhLmQqeHhbaV0vKGJldGEuZCt4eFtpXSksc2lnbWEuZCkKcXVhbnQgPSB0KGFwcGx5KHl5LDEscXVhbnRpbGUsYygwLjA1LDAuNSwwLjk1KSkpCgpwYXIobWZyb3c9YygxLDIpKQpwbG90KHgseSx5bGFiPSJSYXRlIG9mIGEgcmVhY3Rpb24gKM68bW9sKSIseGxhYj0iQ29uY2VudHJhdGlvbiBvZiBhIHN1YnN0cmF0ZSAobU0pIiwKICAgICB5bGltPXJhbmdlKHF1YW50LHkpLHBjaD0xNixjZXg9MC43NSkKbGluZXMoeHgscXVhbnRbLDFdLGx0eT0yLGNvbD0yLGx3ZD0yKQpsaW5lcyh4eCxxdWFudFssMl0sY29sPTIsbHdkPTIpCmxpbmVzKHh4LHF1YW50WywzXSxsdHk9Mixjb2w9Mixsd2Q9MikKbGluZXMoeHgscXVhbnQxWywxXSxsdHk9Mixjb2w9NCxsd2Q9MikKbGluZXMoeHgscXVhbnQxWywyXSxjb2w9NCxsd2Q9MikKbGluZXMoeHgscXVhbnQxWywzXSxsdHk9Mixjb2w9NCxsd2Q9MikKbGVnZW5kKCJ0b3BsZWZ0IixsZWdlbmQ9Yygia25vd24gc2lnbWEiLCJ1bmtub3duIHNpZ21hIiksY29sPWMoNCwyKSxsdHk9MSxsd2Q9MixidHk9Im4iKQoKTiAgICAgICAgPSAyMDAKeXkgICAgICAgPSBzZXEoMSwyLjUsbGVuZ3RoPU4pCnBvc3RwcmVkID0gcmVwKDAsTikKZm9yIChpIGluIDE6TikKICBwb3N0cHJlZFtpXSA9IG1lYW4oZG5vcm0oeXlbaV0sYWxwaGEuZCoxMC8oYmV0YS5kKzEwKSxzaWdtYS5kKSkKCnBsb3QoeXkscG9zdHByZWQseWxhYj0iUG9zdGVyaW9yIHByZWRpY3RpdmUgZGVuc2l0eSIseGxhYj0iUmF0ZSBvZiBhIHJlYWN0aW9uICjOvG1vbCkiLAogICAgdHlwZT0ibCIsY29sPTIseWxpbT1jKDAsOC41KSxsd2Q9MikKdGl0bGUoInggPSAxMCIpCnBvaW50cygxLjY1LDAscGNoPTE2LGNleD0yKQpsaW5lcyh5eSxwb3N0cHJlZDFbLDJdLGNvbD00LGx3ZD0yKQpgYGA=