1 The mcyle dataset from MASS

A data frame giving a series of measurements of head acceleration in a simulated motorcycle accident, used to test crash helmets:

Source: Silverman (1985) Some aspects of the spline smoothing approach to non-parametric curve tting. JRSS-B, 47, 1-52.

library(MASS) 
n = nrow(mcycle) 
x = mcycle$times 
y = mcycle$accel 
x = x/max(x) 
y = y/max(y) 
x =-1+2*x 
xt = x 
yt = y 
xt = x[1:132] 
yt = y[1:132] 
n = length(xt) 
x = (xt-mean(xt))/sqrt(var(xt)) 
y = (yt-mean(yt))/sqrt(var(yt))

par(mfrow=c(1,1))
plot(x,y,xlab="Time after impact (standardized)",ylab="Head accelaration (standardized)")

2 Gaussian polynomial regression

graus <- c(1,2,3,4,5,11,12,13,14,15)
par(mfrow=c(2,5))
for (d in 1:length(graus)){
   fit = lm(y ~ poly(x, graus[d]))
   r2adj = summary(fit)$adj.r.squared
   plot(x,y,xlab="Time after impact (standardized)",ylab="Head accelaration (standardized)")
   lines(x, fit$fit, col = 2)
   title(paste("d = ", graus[d] , sep=""))
   legend("bottomright", legend = c(paste("R2adj = ",round(100*r2adj,1),"%", sep = "")),bty="n")
}

2.1 Adjusted \(R^2\) and BIC

dmax = 15
ds    = 1:dmax
N     = length(ds)
r2adj = rep(0,N)
bic   = rep(0,N)
l     = 0


for (d in ds){
  fit      <- lm(y ~ poly(x, d))
  sig2hat  <- summary(fit)$sigma^2
  RSS      <- sum(fit$residuals^2)
  r2adj[d] <- summary(fit)$adj.r.squared
  bic[d]   <- 1/n*(RSS + log(n)*(d + 1)*sig2hat)
}

par(mfrow=c(1,2))
plot(ds, r2adj,xlab = "Order of polynomial", ylab = "Adjusted R2", type = "b", 
     lwd = 2, main = "In-sample Adjusted R2")
points(ds[r2adj == max(r2adj)], max(r2adj), lty = 2, pch = 20, col = 2)

plot(ds, bic, xlab = "Order of polynomial", ylab = "BIC", type="b", 
     main = "In-sample BIC", lwd = 2)
points(ds[bic == min(bic)], min(bic), lty = 2, pch = 20, col =2)

3 Cross-validation: training and testing

set.seed(2718282)
perc = c(0.1,0.15,0.2)
par(mfrow=c(1,3))
for (j in 1:3){
train = sample(1:length(x),length(x)*(1-perc[j]))
test  = (-train)
ytr   = y[train]
xtr   = x[train]
yte   = y[test]
xte   = x[test]
N     = length(ds)
RMSE  = rep(0,N)
xxtr  = NULL
xxte  = NULL

for (d in ds){
  xxtr  = cbind(xxtr,xtr^d)
  xxte  = cbind(xxte,xte^d)
  fit = lm(ytr~xxtr)
  ehat = yte - cbind(1,xxte)%*%fit$coef
  RMSE[d] = sqrt(mean(ehat^2))
}

plot(ds, RMSE, xlab = "Order of polynomial", ylab = "Root MSE",type="b")
abline(v = ds[RMSE==min(RMSE)], lty = 2)
title(paste("Cross validation (",1-perc[j],",",perc[j],")",sep=""))
}

4 Cross-validation: training and testing - 200 replications

set.seed(56789)
perc = c(0.1,0.15,0.2,0.25)
S     = 200
N     = length(ds)
RMSE  = matrix(0,S,N)

par(mfrow=c(2,2))
for (j in 1:4){
freq  = rep(0,N)
for (s in 1:S){
  train = sample(1:length(x),length(x)*(1-perc[j]))
  test  = (-train)
  ytr   = y[train]
  xtr   = x[train]
  yte   = y[test]
  xte   = x[test]
  l     = 0
  xxtr  = NULL
  xxte  = NULL
  for (d in ds){
    l     = l + 1
    xxtr  = cbind(xxtr,xtr^d)
    xxte  = cbind(xxte,xte^d)
    fit = lm(ytr~xxtr)
    ehat = yte - cbind(1,xxte)%*%fit$coef
    RMSE[s,l] = sqrt(mean(ehat^2))
  }
  freq[ds[RMSE[s,]==min(RMSE[s,],na.rm=TRUE)][1]] = freq[ds[RMSE[s,]==min(RMSE[s,],na.rm=TRUE)][1]] + 1
}
boxplot(RMSE,outline=FALSE,xlab="Order of polynomial", ylab = "Root MSE",ylim=c(0,2))  
for (i in 1:N)
  text(i,0,paste(round(100*freq[i]/S,1),"%",sep=""),cex=0.75)
title(paste("Cross validation\n Training = ",100*(1-perc[j]),"% - ",S," replications",sep=""))
}

5 Cross-validation: leave-one-out (LOO)

set.seed(2718282)
RMSE  = rep(0,N)
for (i in 1:n){
  test = i
  ytr = y[-i]
  xtr = x[-i]
  N     = length(ds)
  xxtr  = NULL
  xxte = NULL
  for (d in ds){
    xxtr   = cbind(xxtr,xtr^d)
    xxte  = cbind(xxte,x[i]^d)
    fit      = lm(ytr~xxtr)
    RMSE[d] = RMSE[d] + (y[i] - cbind(1,xxte)%*%fit$coef)^2
  }
}
par(mfrow=c(1,1))
plot(ds, RMSE, xlab = "Order of polynomial", ylab = "Root MSE",type="b",main="Leave-one-out (LOO)")
abline(v = ds[RMSE==min(RMSE)], lty = 2)

6 10-fold cross-validation

ind = sample(1:n,size=n,replace=FALSE)
x1 = x[ind]
y1 = y[ind]
fold = 10
L = trunc(n/fold)
left = seq(1,n,by=L)[1:fold]
right = seq(L,n,by=L)
right[fold]=n
MSE = rep(0,dmax)
for (f in 1:fold){
  test = left[f]:right[f]
  ytr = y1[-test]
  xtr = x1[-test]
  yte = y1[test]
  xte = x1[test]
  xxtr  = NULL
  xxte  = NULL
  for (d in ds){
    xxtr  = cbind(xxtr,xtr^d)
    xxte  = cbind(xxte,xte^d)
    fit = lm(ytr~xxtr)
    ehat = yte - cbind(1,xxte)%*%fit$coef
    MSE[d] = MSE[d] + sum(ehat^2)
  }
}
RMSE = MSE/n

par(mfrow=c(1,1))
plot(ds, RMSE, xlab = "Order of polynomial", ylab = "Root MSE",type="b",main="")
title(paste(fold,"-fold cross validation",sep=""))
abline(v = ds[RMSE==min(RMSE)], lty = 2)

7 10-fold cross-validation - 200 replications

fold = 10
S = 200
RMSE = matrix(0,S,dmax)
order = rep(0,S)
for (s in 1:S){
ind = sample(1:n,size=n,replace=FALSE)
x1 = x[ind]
y1 = y[ind]
L = trunc(n/fold)
left = seq(1,n,by=L)[1:fold]
right = seq(L,n,by=L)
right[fold]=n
MSE = rep(0,dmax)
for (f in 1:fold){
  test = left[f]:right[f]
  ytr = y1[-test]
  xtr = x1[-test]
  yte = y1[test]
  xte = x1[test]
  xxtr  = NULL
  xxte  = NULL
  for (d in ds){
    xxtr  = cbind(xxtr,xtr^d)
    xxte  = cbind(xxte,xte^d)
    fit = lm(ytr~xxtr)
    ehat = yte - cbind(1,xxte)%*%fit$coef
    MSE[d] = MSE[d] + sum(ehat^2)
  }
}
RMSE[s,] = MSE/n
order[s] = ds[MSE==min(MSE)]
}

freq = rep(0,dmax)
for (s in 1:S){
  freq[order[s]]=  freq[order[s]]+1
}
freq = 100*freq/S

par(mfrow=c(1,1))
boxplot(RMSE,outline=FALSE,xlab = "Order of polynomial", ylab = "Root MSE",ylim=c(0.1,1))
title(paste(fold,"-fold cross validation\n",S," replications",sep=""))
for (d in 1:dmax)
  text(d,0.1,paste(freq[d],"%",sep=""),cex=0.75)

8 Bootstrap for the best model

dbest = ds[freq==max(freq)]
B = 1000
fit = matrix(0,B,n)
plot(x,y,pch=16,xlab="Time after impact (standardized)",ylab="Head accelaration (standardized)",ylim=c(-4,4))
title(paste("Bootstraping the best model\n B=",B," - best model = ",dbest,sep=""))
for (b in 1:B){
  ind = sample(1:n,size=n,replace=TRUE)
  xx = x[ind]
  yy = y[ind]
  X = NULL
  for (d in 1:dbest)
    X  = cbind(X,xx^d)
  fit[b,] = lm(yy~X)$fit
  ord = order(x[ind])
  lines(xx[ord],fit[b,ord],col=grey(0.8))
}
points(x,y,pch=16)

LS0tCnRpdGxlOiAiR2F1c3NpYW4gcG9seW5vbWlhbCByZWdyZXNzaW9uIgpzdWJ0aXRsZTogIlJldmlzaXRpbmcgdGhlIG1vdG9yY3ljbGUgZGF0YSIKYXV0aG9yOiAiSGVkaWJlcnQgRnJlaXRhcyBMb3BlcyIKZGF0ZTogIjI4LzEwLzIwMjUiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDMKICAgIHRvY19jb2xsYXBzZWQ6IHRydWUKICAgIGNvZGVfZG93bmxvYWQ6IHRydWUKICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQogIHBkZl9kb2N1bWVudDoKICAgIHRvYzogdHJ1ZQogICAgdG9jX2RlcHRoOiAnMycKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFKQpgYGAKCiMgVGhlIG1jeWxlIGRhdGFzZXQgZnJvbSBNQVNTIAoKQSBkYXRhIGZyYW1lIGdpdmluZyBhIHNlcmllcyBvZiBtZWFzdXJlbWVudHMgb2YgaGVhZCBhY2NlbGVyYXRpb24gCmluIGEgc2ltdWxhdGVkIG1vdG9yY3ljbGUgYWNjaWRlbnQsIHVzZWQgdG8gdGVzdCBjcmFzaCBoZWxtZXRzOgoKKiAkeCQ6IHRpbWUgaW4gbWlsaXNlY29uZHMgYWZ0ZXIgaW1wYWN0IAoKKiAkeSQ6IGhlYWQgYWNjZWxhcmF0aW9uIChpbiBnKSAKCipTb3VyY2U6KiBTaWx2ZXJtYW4gKDE5ODUpIFNvbWUgYXNwZWN0cyBvZiB0aGUgc3BsaW5lIHNtb290aGluZyBhcHByb2FjaCB0byBub24tcGFyYW1ldHJpYyBjdXJ2ZSB0dGluZy4gSlJTUy1CLCA0NywgMS01Mi4KCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTgsIGZpZy5oZWlnaHQ9Nn0KbGlicmFyeShNQVNTKSAKbiA9IG5yb3cobWN5Y2xlKSAKeCA9IG1jeWNsZSR0aW1lcyAKeSA9IG1jeWNsZSRhY2NlbCAKeCA9IHgvbWF4KHgpIAp5ID0geS9tYXgoeSkgCnggPS0xKzIqeCAKeHQgPSB4IAp5dCA9IHkgCnh0ID0geFsxOjEzMl0gCnl0ID0geVsxOjEzMl0gCm4gPSBsZW5ndGgoeHQpIAp4ID0gKHh0LW1lYW4oeHQpKS9zcXJ0KHZhcih4dCkpIAp5ID0gKHl0LW1lYW4oeXQpKS9zcXJ0KHZhcih5dCkpCgpwYXIobWZyb3c9YygxLDEpKQpwbG90KHgseSx4bGFiPSJUaW1lIGFmdGVyIGltcGFjdCAoc3RhbmRhcmRpemVkKSIseWxhYj0iSGVhZCBhY2NlbGFyYXRpb24gKHN0YW5kYXJkaXplZCkiKQpgYGAKCiMgR2F1c3NpYW4gcG9seW5vbWlhbCByZWdyZXNzaW9uCgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD0xNSwgZmlnLmhlaWdodD04fQpncmF1cyA8LSBjKDEsMiwzLDQsNSwxMSwxMiwxMywxNCwxNSkKcGFyKG1mcm93PWMoMiw1KSkKZm9yIChkIGluIDE6bGVuZ3RoKGdyYXVzKSl7CiAgIGZpdCA9IGxtKHkgfiBwb2x5KHgsIGdyYXVzW2RdKSkKICAgcjJhZGogPSBzdW1tYXJ5KGZpdCkkYWRqLnIuc3F1YXJlZAogICBwbG90KHgseSx4bGFiPSJUaW1lIGFmdGVyIGltcGFjdCAoc3RhbmRhcmRpemVkKSIseWxhYj0iSGVhZCBhY2NlbGFyYXRpb24gKHN0YW5kYXJkaXplZCkiKQogICBsaW5lcyh4LCBmaXQkZml0LCBjb2wgPSAyKQogICB0aXRsZShwYXN0ZSgiZCA9ICIsIGdyYXVzW2RdICwgc2VwPSIiKSkKICAgbGVnZW5kKCJib3R0b21yaWdodCIsIGxlZ2VuZCA9IGMocGFzdGUoIlIyYWRqID0gIixyb3VuZCgxMDAqcjJhZGosMSksIiUiLCBzZXAgPSAiIikpLGJ0eT0ibiIpCn0KYGBgCgojIyBBZGp1c3RlZCAkUl4yJCBhbmQgQklDCgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD01fQpkbWF4ID0gMTUKZHMgICAgPSAxOmRtYXgKTiAgICAgPSBsZW5ndGgoZHMpCnIyYWRqID0gcmVwKDAsTikKYmljICAgPSByZXAoMCxOKQpsICAgICA9IDAKCgpmb3IgKGQgaW4gZHMpewogIGZpdCAgICAgIDwtIGxtKHkgfiBwb2x5KHgsIGQpKQogIHNpZzJoYXQgIDwtIHN1bW1hcnkoZml0KSRzaWdtYV4yCiAgUlNTICAgICAgPC0gc3VtKGZpdCRyZXNpZHVhbHNeMikKICByMmFkaltkXSA8LSBzdW1tYXJ5KGZpdCkkYWRqLnIuc3F1YXJlZAogIGJpY1tkXSAgIDwtIDEvbiooUlNTICsgbG9nKG4pKihkICsgMSkqc2lnMmhhdCkKfQoKcGFyKG1mcm93PWMoMSwyKSkKcGxvdChkcywgcjJhZGoseGxhYiA9ICJPcmRlciBvZiBwb2x5bm9taWFsIiwgeWxhYiA9ICJBZGp1c3RlZCBSMiIsIHR5cGUgPSAiYiIsIAogICAgIGx3ZCA9IDIsIG1haW4gPSAiSW4tc2FtcGxlIEFkanVzdGVkIFIyIikKcG9pbnRzKGRzW3IyYWRqID09IG1heChyMmFkaildLCBtYXgocjJhZGopLCBsdHkgPSAyLCBwY2ggPSAyMCwgY29sID0gMikKCnBsb3QoZHMsIGJpYywgeGxhYiA9ICJPcmRlciBvZiBwb2x5bm9taWFsIiwgeWxhYiA9ICJCSUMiLCB0eXBlPSJiIiwgCiAgICAgbWFpbiA9ICJJbi1zYW1wbGUgQklDIiwgbHdkID0gMikKcG9pbnRzKGRzW2JpYyA9PSBtaW4oYmljKV0sIG1pbihiaWMpLCBsdHkgPSAyLCBwY2ggPSAyMCwgY29sID0yKQpgYGAKCiMgQ3Jvc3MtdmFsaWRhdGlvbjogdHJhaW5pbmcgYW5kIHRlc3RpbmcgCgpgYGB7ciBmaWcuYWxpZ249J2NlbnRlcicsIGZpZy53aWR0aD0xMiwgZmlnLmhlaWdodD00fQpzZXQuc2VlZCgyNzE4MjgyKQpwZXJjID0gYygwLjEsMC4xNSwwLjIpCnBhcihtZnJvdz1jKDEsMykpCmZvciAoaiBpbiAxOjMpewp0cmFpbiA9IHNhbXBsZSgxOmxlbmd0aCh4KSxsZW5ndGgoeCkqKDEtcGVyY1tqXSkpCnRlc3QgID0gKC10cmFpbikKeXRyICAgPSB5W3RyYWluXQp4dHIgICA9IHhbdHJhaW5dCnl0ZSAgID0geVt0ZXN0XQp4dGUgICA9IHhbdGVzdF0KTiAgICAgPSBsZW5ndGgoZHMpClJNU0UgID0gcmVwKDAsTikKeHh0ciAgPSBOVUxMCnh4dGUgID0gTlVMTAoKZm9yIChkIGluIGRzKXsKICB4eHRyICA9IGNiaW5kKHh4dHIseHRyXmQpCiAgeHh0ZSAgPSBjYmluZCh4eHRlLHh0ZV5kKQogIGZpdCA9IGxtKHl0cn54eHRyKQogIGVoYXQgPSB5dGUgLSBjYmluZCgxLHh4dGUpJSolZml0JGNvZWYKICBSTVNFW2RdID0gc3FydChtZWFuKGVoYXReMikpCn0KCnBsb3QoZHMsIFJNU0UsIHhsYWIgPSAiT3JkZXIgb2YgcG9seW5vbWlhbCIsIHlsYWIgPSAiUm9vdCBNU0UiLHR5cGU9ImIiKQphYmxpbmUodiA9IGRzW1JNU0U9PW1pbihSTVNFKV0sIGx0eSA9IDIpCnRpdGxlKHBhc3RlKCJDcm9zcyB2YWxpZGF0aW9uICgiLDEtcGVyY1tqXSwiLCIscGVyY1tqXSwiKSIsc2VwPSIiKSkKfQpgYGAKCiMgQ3Jvc3MtdmFsaWRhdGlvbjogdHJhaW5pbmcgYW5kIHRlc3RpbmcgLSAyMDAgcmVwbGljYXRpb25zCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTE1LCBmaWcuaGVpZ2h0PTEwfQpzZXQuc2VlZCg1Njc4OSkKcGVyYyA9IGMoMC4xLDAuMTUsMC4yLDAuMjUpClMgICAgID0gMjAwCk4gICAgID0gbGVuZ3RoKGRzKQpSTVNFICA9IG1hdHJpeCgwLFMsTikKCnBhcihtZnJvdz1jKDIsMikpCmZvciAoaiBpbiAxOjQpewpmcmVxICA9IHJlcCgwLE4pCmZvciAocyBpbiAxOlMpewogIHRyYWluID0gc2FtcGxlKDE6bGVuZ3RoKHgpLGxlbmd0aCh4KSooMS1wZXJjW2pdKSkKICB0ZXN0ICA9ICgtdHJhaW4pCiAgeXRyICAgPSB5W3RyYWluXQogIHh0ciAgID0geFt0cmFpbl0KICB5dGUgICA9IHlbdGVzdF0KICB4dGUgICA9IHhbdGVzdF0KICBsICAgICA9IDAKICB4eHRyICA9IE5VTEwKICB4eHRlICA9IE5VTEwKICBmb3IgKGQgaW4gZHMpewogICAgbCAgICAgPSBsICsgMQogICAgeHh0ciAgPSBjYmluZCh4eHRyLHh0cl5kKQogICAgeHh0ZSAgPSBjYmluZCh4eHRlLHh0ZV5kKQogICAgZml0ID0gbG0oeXRyfnh4dHIpCiAgICBlaGF0ID0geXRlIC0gY2JpbmQoMSx4eHRlKSUqJWZpdCRjb2VmCiAgICBSTVNFW3MsbF0gPSBzcXJ0KG1lYW4oZWhhdF4yKSkKICB9CiAgZnJlcVtkc1tSTVNFW3MsXT09bWluKFJNU0VbcyxdLG5hLnJtPVRSVUUpXVsxXV0gPSBmcmVxW2RzW1JNU0VbcyxdPT1taW4oUk1TRVtzLF0sbmEucm09VFJVRSldWzFdXSArIDEKfQpib3hwbG90KFJNU0Usb3V0bGluZT1GQUxTRSx4bGFiPSJPcmRlciBvZiBwb2x5bm9taWFsIiwgeWxhYiA9ICJSb290IE1TRSIseWxpbT1jKDAsMikpICAKZm9yIChpIGluIDE6TikKICB0ZXh0KGksMCxwYXN0ZShyb3VuZCgxMDAqZnJlcVtpXS9TLDEpLCIlIixzZXA9IiIpLGNleD0wLjc1KQp0aXRsZShwYXN0ZSgiQ3Jvc3MgdmFsaWRhdGlvblxuIFRyYWluaW5nID0gIiwxMDAqKDEtcGVyY1tqXSksIiUgLSAiLFMsIiByZXBsaWNhdGlvbnMiLHNlcD0iIikpCn0KYGBgCgojIENyb3NzLXZhbGlkYXRpb246IGxlYXZlLW9uZS1vdXQgKExPTykKCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTgsIGZpZy5oZWlnaHQ9Nn0Kc2V0LnNlZWQoMjcxODI4MikKUk1TRSAgPSByZXAoMCxOKQpmb3IgKGkgaW4gMTpuKXsKICB0ZXN0ID0gaQogIHl0ciA9IHlbLWldCiAgeHRyID0geFstaV0KICBOICAgICA9IGxlbmd0aChkcykKICB4eHRyICA9IE5VTEwKICB4eHRlID0gTlVMTAogIGZvciAoZCBpbiBkcyl7CiAgICB4eHRyICAgPSBjYmluZCh4eHRyLHh0cl5kKQogICAgeHh0ZSAgPSBjYmluZCh4eHRlLHhbaV1eZCkKICAgIGZpdCAgICAgID0gbG0oeXRyfnh4dHIpCiAgICBSTVNFW2RdID0gUk1TRVtkXSArICh5W2ldIC0gY2JpbmQoMSx4eHRlKSUqJWZpdCRjb2VmKV4yCiAgfQp9CnBhcihtZnJvdz1jKDEsMSkpCnBsb3QoZHMsIFJNU0UsIHhsYWIgPSAiT3JkZXIgb2YgcG9seW5vbWlhbCIsIHlsYWIgPSAiUm9vdCBNU0UiLHR5cGU9ImIiLG1haW49IkxlYXZlLW9uZS1vdXQgKExPTykiKQphYmxpbmUodiA9IGRzW1JNU0U9PW1pbihSTVNFKV0sIGx0eSA9IDIpCmBgYAoKIyAxMC1mb2xkIGNyb3NzLXZhbGlkYXRpb24KYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD02fQppbmQgPSBzYW1wbGUoMTpuLHNpemU9bixyZXBsYWNlPUZBTFNFKQp4MSA9IHhbaW5kXQp5MSA9IHlbaW5kXQpmb2xkID0gMTAKTCA9IHRydW5jKG4vZm9sZCkKbGVmdCA9IHNlcSgxLG4sYnk9TClbMTpmb2xkXQpyaWdodCA9IHNlcShMLG4sYnk9TCkKcmlnaHRbZm9sZF09bgpNU0UgPSByZXAoMCxkbWF4KQpmb3IgKGYgaW4gMTpmb2xkKXsKICB0ZXN0ID0gbGVmdFtmXTpyaWdodFtmXQogIHl0ciA9IHkxWy10ZXN0XQogIHh0ciA9IHgxWy10ZXN0XQogIHl0ZSA9IHkxW3Rlc3RdCiAgeHRlID0geDFbdGVzdF0KICB4eHRyICA9IE5VTEwKICB4eHRlICA9IE5VTEwKICBmb3IgKGQgaW4gZHMpewogICAgeHh0ciAgPSBjYmluZCh4eHRyLHh0cl5kKQogICAgeHh0ZSAgPSBjYmluZCh4eHRlLHh0ZV5kKQogICAgZml0ID0gbG0oeXRyfnh4dHIpCiAgICBlaGF0ID0geXRlIC0gY2JpbmQoMSx4eHRlKSUqJWZpdCRjb2VmCiAgICBNU0VbZF0gPSBNU0VbZF0gKyBzdW0oZWhhdF4yKQogIH0KfQpSTVNFID0gTVNFL24KCnBhcihtZnJvdz1jKDEsMSkpCnBsb3QoZHMsIFJNU0UsIHhsYWIgPSAiT3JkZXIgb2YgcG9seW5vbWlhbCIsIHlsYWIgPSAiUm9vdCBNU0UiLHR5cGU9ImIiLG1haW49IiIpCnRpdGxlKHBhc3RlKGZvbGQsIi1mb2xkIGNyb3NzIHZhbGlkYXRpb24iLHNlcD0iIikpCmFibGluZSh2ID0gZHNbUk1TRT09bWluKFJNU0UpXSwgbHR5ID0gMikKYGBgCgojIDEwLWZvbGQgY3Jvc3MtdmFsaWRhdGlvbiAtIDIwMCByZXBsaWNhdGlvbnMKCmBgYHtyIGZpZy5hbGlnbj0nY2VudGVyJywgZmlnLndpZHRoPTgsIGZpZy5oZWlnaHQ9Nn0KZm9sZCA9IDEwClMgPSAyMDAKUk1TRSA9IG1hdHJpeCgwLFMsZG1heCkKb3JkZXIgPSByZXAoMCxTKQpmb3IgKHMgaW4gMTpTKXsKaW5kID0gc2FtcGxlKDE6bixzaXplPW4scmVwbGFjZT1GQUxTRSkKeDEgPSB4W2luZF0KeTEgPSB5W2luZF0KTCA9IHRydW5jKG4vZm9sZCkKbGVmdCA9IHNlcSgxLG4sYnk9TClbMTpmb2xkXQpyaWdodCA9IHNlcShMLG4sYnk9TCkKcmlnaHRbZm9sZF09bgpNU0UgPSByZXAoMCxkbWF4KQpmb3IgKGYgaW4gMTpmb2xkKXsKICB0ZXN0ID0gbGVmdFtmXTpyaWdodFtmXQogIHl0ciA9IHkxWy10ZXN0XQogIHh0ciA9IHgxWy10ZXN0XQogIHl0ZSA9IHkxW3Rlc3RdCiAgeHRlID0geDFbdGVzdF0KICB4eHRyICA9IE5VTEwKICB4eHRlICA9IE5VTEwKICBmb3IgKGQgaW4gZHMpewogICAgeHh0ciAgPSBjYmluZCh4eHRyLHh0cl5kKQogICAgeHh0ZSAgPSBjYmluZCh4eHRlLHh0ZV5kKQogICAgZml0ID0gbG0oeXRyfnh4dHIpCiAgICBlaGF0ID0geXRlIC0gY2JpbmQoMSx4eHRlKSUqJWZpdCRjb2VmCiAgICBNU0VbZF0gPSBNU0VbZF0gKyBzdW0oZWhhdF4yKQogIH0KfQpSTVNFW3MsXSA9IE1TRS9uCm9yZGVyW3NdID0gZHNbTVNFPT1taW4oTVNFKV0KfQoKZnJlcSA9IHJlcCgwLGRtYXgpCmZvciAocyBpbiAxOlMpewogIGZyZXFbb3JkZXJbc11dPSAgZnJlcVtvcmRlcltzXV0rMQp9CmZyZXEgPSAxMDAqZnJlcS9TCgpwYXIobWZyb3c9YygxLDEpKQpib3hwbG90KFJNU0Usb3V0bGluZT1GQUxTRSx4bGFiID0gIk9yZGVyIG9mIHBvbHlub21pYWwiLCB5bGFiID0gIlJvb3QgTVNFIix5bGltPWMoMC4xLDEpKQp0aXRsZShwYXN0ZShmb2xkLCItZm9sZCBjcm9zcyB2YWxpZGF0aW9uXG4iLFMsIiByZXBsaWNhdGlvbnMiLHNlcD0iIikpCmZvciAoZCBpbiAxOmRtYXgpCiAgdGV4dChkLDAuMSxwYXN0ZShmcmVxW2RdLCIlIixzZXA9IiIpLGNleD0wLjc1KQpgYGAKCiMgQm9vdHN0cmFwIGZvciB0aGUgYmVzdCBtb2RlbAoKYGBge3IgZmlnLmFsaWduPSdjZW50ZXInLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD02fQpkYmVzdCA9IGRzW2ZyZXE9PW1heChmcmVxKV0KQiA9IDEwMDAKZml0ID0gbWF0cml4KDAsQixuKQpwbG90KHgseSxwY2g9MTYseGxhYj0iVGltZSBhZnRlciBpbXBhY3QgKHN0YW5kYXJkaXplZCkiLHlsYWI9IkhlYWQgYWNjZWxhcmF0aW9uIChzdGFuZGFyZGl6ZWQpIix5bGltPWMoLTQsNCkpCnRpdGxlKHBhc3RlKCJCb290c3RyYXBpbmcgdGhlIGJlc3QgbW9kZWxcbiBCPSIsQiwiIC0gYmVzdCBtb2RlbCA9ICIsZGJlc3Qsc2VwPSIiKSkKZm9yIChiIGluIDE6Qil7CiAgaW5kID0gc2FtcGxlKDE6bixzaXplPW4scmVwbGFjZT1UUlVFKQogIHh4ID0geFtpbmRdCiAgeXkgPSB5W2luZF0KICBYID0gTlVMTAogIGZvciAoZCBpbiAxOmRiZXN0KQogICAgWCAgPSBjYmluZChYLHh4XmQpCiAgZml0W2IsXSA9IGxtKHl5flgpJGZpdAogIG9yZCA9IG9yZGVyKHhbaW5kXSkKICBsaW5lcyh4eFtvcmRdLGZpdFtiLG9yZF0sY29sPWdyZXkoMC44KSkKfQpwb2ludHMoeCx5LHBjaD0xNikKYGBgCg==