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)")

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")
}

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)

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=""))
}

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=""))
}

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)

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)

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)

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==