- Modeling
- Prelude to modeling
Initially we look at different models that would be appropriate for the respective price series.
library(astsa)
library(forecast)
orig1 <- orig
orig1[,1]=as.POSIXct(orig[,1])
orig2 <- as.ts(orig1, order.by = more_coins$time)
# functions used
# z=1
# for(q in 0:7){
# for(p in 0:7){
#
# if(p+z+q<=7){
# model <- arima(x=log(orig$Neo), order = c((p),z,(q)))
# pval <- Box.test(model$residuals, lag=log(length(model$residuals)))
# sse <- sum(model$residuals^2)
# cat(p,d,q,'AIC=', model$aic, ' SSE=',sse,' p-VALUE=', pval$p.value,'\n')
# }
# }
# }
Residuals for all coins for model ARIMA (0, 1, 6)
residuals = matrix(nrow = 18752, ncol = 21)
for (i in 2:21){
order = c(0,1,6)
model = arima(log(orig2[,i]), order = order)
residuals[,i] = model$residuals
}
residuals = residuals[,2:21]
# Change column names
colnames(residuals) <- c('Bitcoin', 'Bitcoin Cash', 'Bitcoin Gold', 'Cardano', 'Dash',
'Nem', 'Eos', 'Ethereum', 'Ethereum Classic', 'Iota', 'Lisk',
'Litecoin', 'Monero', 'Neo', 'Ripple', 'Stellar', 'Tether',
'Tron', 'Zcash', 'Dogecoin')
Plot ACF and PACF of the residuals:
for (i in 1:20){
acf2((residuals[,i]),main=paste("ACF/PACF of residuals:", colnames(residuals)[i]))
}




















Plot ACF and PACF of squared residuals:
for (i in 1:20){
acf2(((residuals[,i])^2),main=paste("ACF/PACF of squared residuals:", colnames(residuals)[i]))
}




















Models with the highest p-values
# bitcoin arima(0,1,6) AIC= -163146.9 SSE= 0.1827101 p-VALUE= 0.8898061
# bitcoin cash arima (0,1,6) AIC= -148875.8 SSE= 0.3909791 p-VALUE= 0.9844488
# bitcoin cash arima (6,1,0) AIC= -148874 SSE= 0.3910169 p-VALUE= 0.9196427
# bitcoin gold arima 5 1 0 AIC= -139988.1 SSE= 0.6280686 p-VALUE= 0.9285041
# bitcoin gold arima 0 1 5 AIC= -139988 SSE= 0.6280735 p-VALUE= 0.9194634
# bitcoin gold arima 0 1 6 AIC= -139987 SSE= 0.6280371 p-VALUE= 0.9671026
# bitcoin gold arima 0 1 6 AIC= -139987 SSE= 0.6280371 p-VALUE= 0.9671026
# cardano arima 0 1 6 AIC= -134310.3 SSE= 0.8500523 p-VALUE= 0.8903308
# cardano arima 0 1 5 AIC= -134311.8 SSE= 0.8500761 p-VALUE= 0.8507009
# cardano arima 5 1 0 AIC= -134311.7 SSE= 0.8500809 p-VALUE= 0.842242
# cardano arima 6 1 0 AIC= -134310.2 SSE= 0.8500576 p-VALUE= 0.8826964
# dash arima 6 1 0 AIC= -151438.9 SSE= 0.3410233 p-VALUE= 0.0146797
# dash arima 5 1 0 AIC= -151431.9 SSE= 0.3411868 p-VALUE= 0.0004798259
# dash arima 1 1 5 AIC= -151440.4 SSE= 0.3409961 p-VALUE= 0.01534037
# dash arima 0 1 6 AIC= -151440.8 SSE= 0.3409897 p-VALUE= 0.01704869
# nem arima 0 1 5 AIC= -128251.3 SSE= 1.174429 p-VALUE= 0.603514
# nem arima 0 1 6 AIC= -128252.5 SSE= 1.174226 p-VALUE= 0.8934795
# nem arima 6 1 0 AIC= -128253.3 SSE= 1.174176 p-VALUE= 0.9439804
# eos arima 5 1 0 AIC= -141334.1 SSE= 0.5845431 p-VALUE= 0.910631
# eos arima 6 1 0 AIC= -141332.6 SSE= 0.5845274 p-VALUE= 0.9378108
# eos arima 0 1 5 AIC= -141334.3 SSE= 0.5845383 p-VALUE= 0.9192631
# eos arima 1 1 5 AIC= -141332.3 SSE= 0.5845389 p-VALUE= 0.9182253
# eos arima 0 1 6 AIC= -141332.4 SSE= 0.5845351 p-VALUE= 0.9250239
# etherium arima 6 1 0 AIC= -154959.9 SSE= 0.2826508 p-VALUE= 0.1889165
# etherium arima 0 1 6 AIC= -154961 SSE= 0.2826346 p-VALUE= 0.2142195
# etherium classic 0 1 6 AIC= -143172.9 SSE= 0.5298932 p-VALUE= 0.8009095
# etherium classic 6 1 0 AIC= -143171.6 SSE= 0.5299287 p-VALUE= 0.7044136
# iota arima 0 1 6 AIC= -135322.1 SSE= 0.8054028 p-VALUE= 0.8211937
# iota arima 6 1 0 AIC= -135322.1 SSE= 0.8053994 p-VALUE= 0.8354789
# lisk arima 0 1 5 AIC= -133271.1 SSE= 0.8985987 p-VALUE= 0.300508
# lisk arima 1 1 5 AIC= -133269.2 SSE= 0.8985939 p-VALUE= 0.3066513
# lisk arima 0 1 6 AIC= -133269.4 SSE= 0.8985846 p-VALUE= 0.3175778
# litecoin arima 0 1 6 AIC= -147684.7 SSE= 0.4165891 p-VALUE= 0.002356966
# monero arima 0 1 6 AIC= -145422.5 SSE= 0.4700091 p-VALUE= 0.4633666
# neo arima 0 1 6 AIC= -137683.7 SSE= 0.7101156 p-VALUE= 0.2783678
#Dogecoin 6 1 0 AIC= -134235.4 SSE= 0.8534827 p-VALUE= 0.2259134
#Dogecoin 0 1 6 AIC= -134236 SSE= 0.8534515 p-VALUE= 0.2605084
#Zcash 0 1 6 AIC= -147257.9 SSE= 0.4261904 p-VALUE= 0.563043
#Tron 0 1 6 AIC= -132231.9 SSE= 0.9497042 p-VALUE= 0.07077541
#Tron 5 1 1 AIC= -132232.1 SSE= 0.9496931 p-VALUE= 0.08028114
#Tether 0 1 6 AIC= -144870.1 SSE= 0.4840216 p-VALUE= 0.01319184
#Tether 1 1 5 AIC= -144870.3 SSE= 0.4840165 p-VALUE= 0.0144533
#Tether 3 1 1 AIC= -144874.8 SSE= 0.4840031 p-VALUE= 0.01522452
#Stellar 0 1 6 AIC= -131486.6 SSE= 0.9882045 p-VALUE= 0.9684533
#Ripple 6 1 0 AIC= -137749.8 SSE= 0.7075952 p-VALUE= 0.9969477
#Ripple 1 1 5 AIC= -137748.8 SSE= 0.7076322 p-VALUE= 0.9825528
#Ripple 0 1 6 AIC= -137749.9 SSE= 0.7075889 p-VALUE= 0.9976909
Code for rolling window for Dash
# x=orig[,6]
# x=log((x))
# mm=list()
#
# for (i in 1:(length(x)-2016+1)){
# mm[[i]]=arima(x[i:(i+2015)], order=c(0,1,6))
# }
# f=list()
# ff=rep(0,length(x))
# for (i in 1:(length(x)-2016+1)){
# f[[i]]=predict(mm[[i]],n.ahead = 1)
# ff[2016+i]=f[[i]]$pred[1]
# }

par2 <- par(mfrow=c(2, 1))
plot(x,col="blue",type="l",lwd=0.75, main="Dash orginal price series")
plot(ff[2017:length(ff)],col="red",type="l", lwd=0.75, main="Dash prediction price series")
sqrt(mean((x[2017:length(x)]-ff[2017:length(x)])^2))
[1] 0.004110244
# We see a difference in the fifth digit after the decimal point
mean(ff[2017:length(ff)]) # [1] 6.362825
[1] 6.362825
mean(x[2017:length(x)]) # [1] 6.362806
[1] 6.362806
# We see a difference in the fifth third digit after the decimal point
sd(ff[2017:length(ff)]) # [1] 0.2070071
[1] 0.2070071
sd(x[2017:length(x)]) # [1] 0.2069952
[1] 0.2069952
LS0tCnRpdGxlOiAiQWNhZGVtaWEgRGF0YXRob246IERBQiBQQU5EQSBUaGUgQS5JLiBDcnlwdG8gVHJhZGVyIChQYXJ0IDIuMSkiCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCklJSS4gTW9kZWxpbmcKCjEuIFByZWx1ZGUgdG8gbW9kZWxpbmcKCkluaXRpYWxseSB3ZSBsb29rIGF0IGRpZmZlcmVudCBtb2RlbHMgdGhhdCB3b3VsZCBiZSBhcHByb3ByaWF0ZSBmb3IgdGhlIHJlc3BlY3RpdmUgcHJpY2Ugc2VyaWVzLgoKYGBge3J9CmxpYnJhcnkoYXN0c2EpCmxpYnJhcnkoZm9yZWNhc3QpCgpvcmlnMSA8LSBvcmlnCm9yaWcxWywxXT1hcy5QT1NJWGN0KG9yaWdbLDFdKQpvcmlnMiA8LSBhcy50cyhvcmlnMSwgb3JkZXIuYnkgPSBtb3JlX2NvaW5zJHRpbWUpCgojIGZ1bmN0aW9ucyB1c2VkCiMgej0xCiMgZm9yKHEgaW4gMDo3KXsKIyAgIGZvcihwIGluIDA6Nyl7CiMgICAgIAojICAgICBpZihwK3orcTw9Nyl7CiMgICAgICAgbW9kZWwgPC0gYXJpbWEoeD1sb2cob3JpZyROZW8pLCBvcmRlciA9IGMoKHApLHosKHEpKSkKIyAgICAgICBwdmFsIDwtIEJveC50ZXN0KG1vZGVsJHJlc2lkdWFscywgbGFnPWxvZyhsZW5ndGgobW9kZWwkcmVzaWR1YWxzKSkpCiMgICAgICAgc3NlIDwtIHN1bShtb2RlbCRyZXNpZHVhbHNeMikKIyAgICAgICBjYXQocCxkLHEsJ0FJQz0nLCBtb2RlbCRhaWMsICcgU1NFPScsc3NlLCcgcC1WQUxVRT0nLCBwdmFsJHAudmFsdWUsJ1xuJykKIyAgICAgfQojICAgfQojIH0KCgpgYGAKClJlc2lkdWFscyBmb3IgYWxsIGNvaW5zIGZvciBtb2RlbCBBUklNQSAoMCwgMSwgNikKCmBgYHtyfQpyZXNpZHVhbHMgPSBtYXRyaXgobnJvdyA9IDE4NzUyLCBuY29sID0gMjEpCmZvciAoaSBpbiAyOjIxKXsKICBvcmRlciA9IGMoMCwxLDYpCiAgbW9kZWwgPSBhcmltYShsb2cob3JpZzJbLGldKSwgb3JkZXIgPSBvcmRlcikKICByZXNpZHVhbHNbLGldID0gbW9kZWwkcmVzaWR1YWxzCn0KcmVzaWR1YWxzID0gcmVzaWR1YWxzWywyOjIxXQoKIyBDaGFuZ2UgY29sdW1uIG5hbWVzCmNvbG5hbWVzKHJlc2lkdWFscykgPC0gYygnQml0Y29pbicsICdCaXRjb2luIENhc2gnLCAnQml0Y29pbiBHb2xkJywgJ0NhcmRhbm8nLCAnRGFzaCcsCiAgICAgICAgICAgICAgICAgICAgICAgICAnTmVtJywgJ0VvcycsICdFdGhlcmV1bScsICdFdGhlcmV1bSBDbGFzc2ljJywgJ0lvdGEnLCAnTGlzaycsIAogICAgICAgICAgICAgICAgICAgICAgICAgJ0xpdGVjb2luJywgJ01vbmVybycsICdOZW8nLCAnUmlwcGxlJywgJ1N0ZWxsYXInLCAnVGV0aGVyJywKICAgICAgICAgICAgICAgICAgICAgICAgICdUcm9uJywgJ1pjYXNoJywgJ0RvZ2Vjb2luJykKYGBgCgpQbG90IEFDRiBhbmQgUEFDRiBvZiB0aGUgcmVzaWR1YWxzOgoKYGBge3J9CmZvciAoaSBpbiAxOjIwKXsKICBhY2YyKChyZXNpZHVhbHNbLGldKSxtYWluPXBhc3RlKCJBQ0YvUEFDRiBvZiByZXNpZHVhbHM6IiwgY29sbmFtZXMocmVzaWR1YWxzKVtpXSkpCn0KYGBgCgpQbG90IEFDRiBhbmQgUEFDRiBvZiBzcXVhcmVkIHJlc2lkdWFsczoKCmBgYHtyfQpmb3IgKGkgaW4gMToyMCl7CiAgYWNmMigoKHJlc2lkdWFsc1ssaV0pXjIpLG1haW49cGFzdGUoIkFDRi9QQUNGIG9mIHNxdWFyZWQgcmVzaWR1YWxzOiIsIGNvbG5hbWVzKHJlc2lkdWFscylbaV0pKQp9CmBgYAoKTW9kZWxzIHdpdGggdGhlIGhpZ2hlc3QgcC12YWx1ZXMKYGBge3J9CiMgYml0Y29pbiBhcmltYSgwLDEsNikgQUlDPSAtMTYzMTQ2LjkgIFNTRT0gMC4xODI3MTAxICBwLVZBTFVFPSAwLjg4OTgwNjEKIyBiaXRjb2luIGNhc2ggYXJpbWEgKDAsMSw2KSBBSUM9IC0xNDg4NzUuOCAgU1NFPSAwLjM5MDk3OTEgIHAtVkFMVUU9IDAuOTg0NDQ4OAojIGJpdGNvaW4gY2FzaCBhcmltYSAoNiwxLDApIEFJQz0gLTE0ODg3NCAgU1NFPSAwLjM5MTAxNjkgIHAtVkFMVUU9IDAuOTE5NjQyNwojIGJpdGNvaW4gZ29sZCBhcmltYSA1IDEgMCBBSUM9IC0xMzk5ODguMSAgU1NFPSAwLjYyODA2ODYgIHAtVkFMVUU9IDAuOTI4NTA0MQojIGJpdGNvaW4gZ29sZCBhcmltYSAwIDEgNSBBSUM9IC0xMzk5ODggIFNTRT0gMC42MjgwNzM1ICBwLVZBTFVFPSAwLjkxOTQ2MzQKIyBiaXRjb2luIGdvbGQgYXJpbWEgMCAxIDYgQUlDPSAtMTM5OTg3ICBTU0U9IDAuNjI4MDM3MSAgcC1WQUxVRT0gMC45NjcxMDI2CiMgYml0Y29pbiBnb2xkIGFyaW1hIDAgMSA2IEFJQz0gLTEzOTk4NyAgU1NFPSAwLjYyODAzNzEgIHAtVkFMVUU9IDAuOTY3MTAyNgojIGNhcmRhbm8gYXJpbWEgMCAxIDYgQUlDPSAtMTM0MzEwLjMgIFNTRT0gMC44NTAwNTIzICBwLVZBTFVFPSAwLjg5MDMzMDgKIyBjYXJkYW5vIGFyaW1hIDAgMSA1IEFJQz0gLTEzNDMxMS44ICBTU0U9IDAuODUwMDc2MSAgcC1WQUxVRT0gMC44NTA3MDA5CiMgY2FyZGFubyBhcmltYSA1IDEgMCBBSUM9IC0xMzQzMTEuNyAgU1NFPSAwLjg1MDA4MDkgIHAtVkFMVUU9IDAuODQyMjQyIAojIGNhcmRhbm8gYXJpbWEgNiAxIDAgQUlDPSAtMTM0MzEwLjIgIFNTRT0gMC44NTAwNTc2ICBwLVZBTFVFPSAwLjg4MjY5NjQKIyBkYXNoIGFyaW1hIDYgMSAwIEFJQz0gLTE1MTQzOC45ICBTU0U9IDAuMzQxMDIzMyAgcC1WQUxVRT0gMC4wMTQ2Nzk3CiMgZGFzaCBhcmltYSA1IDEgMCBBSUM9IC0xNTE0MzEuOSAgU1NFPSAwLjM0MTE4NjggIHAtVkFMVUU9IDAuMDAwNDc5ODI1OQojIGRhc2ggYXJpbWEgMSAxIDUgQUlDPSAtMTUxNDQwLjQgIFNTRT0gMC4zNDA5OTYxICBwLVZBTFVFPSAwLjAxNTM0MDM3IAojIGRhc2ggYXJpbWEgMCAxIDYgQUlDPSAtMTUxNDQwLjggIFNTRT0gMC4zNDA5ODk3ICBwLVZBTFVFPSAwLjAxNzA0ODY5IAojIG5lbSBhcmltYSAwIDEgNSBBSUM9IC0xMjgyNTEuMyAgU1NFPSAxLjE3NDQyOSAgcC1WQUxVRT0gMC42MDM1MTQKIyBuZW0gYXJpbWEgMCAxIDYgQUlDPSAtMTI4MjUyLjUgIFNTRT0gMS4xNzQyMjYgIHAtVkFMVUU9IDAuODkzNDc5NSAKIyBuZW0gYXJpbWEgNiAxIDAgQUlDPSAtMTI4MjUzLjMgIFNTRT0gMS4xNzQxNzYgIHAtVkFMVUU9IDAuOTQzOTgwNAojIGVvcyBhcmltYSA1IDEgMCBBSUM9IC0xNDEzMzQuMSAgU1NFPSAwLjU4NDU0MzEgIHAtVkFMVUU9IDAuOTEwNjMxIAojIGVvcyBhcmltYSA2IDEgMCBBSUM9IC0xNDEzMzIuNiAgU1NFPSAwLjU4NDUyNzQgIHAtVkFMVUU9IDAuOTM3ODEwOAojIGVvcyBhcmltYSAwIDEgNSBBSUM9IC0xNDEzMzQuMyAgU1NFPSAwLjU4NDUzODMgIHAtVkFMVUU9IDAuOTE5MjYzMSAKIyBlb3MgYXJpbWEgMSAxIDUgQUlDPSAtMTQxMzMyLjMgIFNTRT0gMC41ODQ1Mzg5ICBwLVZBTFVFPSAwLjkxODIyNTMgCiMgZW9zIGFyaW1hIDAgMSA2IEFJQz0gLTE0MTMzMi40ICBTU0U9IDAuNTg0NTM1MSAgcC1WQUxVRT0gMC45MjUwMjM5CiMgZXRoZXJpdW0gYXJpbWEgIDYgMSAwIEFJQz0gLTE1NDk1OS45ICBTU0U9IDAuMjgyNjUwOCAgcC1WQUxVRT0gMC4xODg5MTY1CiMgZXRoZXJpdW0gYXJpbWEgMCAxIDYgQUlDPSAtMTU0OTYxICBTU0U9IDAuMjgyNjM0NiAgcC1WQUxVRT0gMC4yMTQyMTk1CiMgZXRoZXJpdW0gY2xhc3NpYyAwIDEgNiBBSUM9IC0xNDMxNzIuOSAgU1NFPSAwLjUyOTg5MzIgIHAtVkFMVUU9IDAuODAwOTA5NQojIGV0aGVyaXVtIGNsYXNzaWMgNiAxIDAgQUlDPSAtMTQzMTcxLjYgIFNTRT0gMC41Mjk5Mjg3ICBwLVZBTFVFPSAwLjcwNDQxMzYKIyBpb3RhIGFyaW1hIDAgMSA2IEFJQz0gLTEzNTMyMi4xICBTU0U9IDAuODA1NDAyOCAgcC1WQUxVRT0gMC44MjExOTM3CiMgaW90YSBhcmltYSA2IDEgMCBBSUM9IC0xMzUzMjIuMSAgU1NFPSAwLjgwNTM5OTQgIHAtVkFMVUU9IDAuODM1NDc4OQojIGxpc2sgYXJpbWEgMCAxIDUgQUlDPSAtMTMzMjcxLjEgIFNTRT0gMC44OTg1OTg3ICBwLVZBTFVFPSAwLjMwMDUwOCAKIyBsaXNrIGFyaW1hIDEgMSA1IEFJQz0gLTEzMzI2OS4yICBTU0U9IDAuODk4NTkzOSAgcC1WQUxVRT0gMC4zMDY2NTEzIAojIGxpc2sgYXJpbWEgMCAxIDYgQUlDPSAtMTMzMjY5LjQgIFNTRT0gMC44OTg1ODQ2ICBwLVZBTFVFPSAwLjMxNzU3NzgKIyBsaXRlY29pbiBhcmltYSAwIDEgNiBBSUM9IC0xNDc2ODQuNyAgU1NFPSAwLjQxNjU4OTEgIHAtVkFMVUU9IDAuMDAyMzU2OTY2CiMgbW9uZXJvICBhcmltYSAwIDEgNiBBSUM9IC0xNDU0MjIuNSAgU1NFPSAwLjQ3MDAwOTEgIHAtVkFMVUU9IDAuNDYzMzY2NgojIG5lbyBhcmltYSAwIDEgNiBBSUM9IC0xMzc2ODMuNyAgU1NFPSAwLjcxMDExNTYgIHAtVkFMVUU9IDAuMjc4MzY3OAojRG9nZWNvaW4gNiAxIDAgQUlDPSAtMTM0MjM1LjQgIFNTRT0gMC44NTM0ODI3ICBwLVZBTFVFPSAwLjIyNTkxMzQKI0RvZ2Vjb2luIDAgMSA2IEFJQz0gLTEzNDIzNiAgU1NFPSAwLjg1MzQ1MTUgIHAtVkFMVUU9IDAuMjYwNTA4NAojWmNhc2ggMCAxIDYgQUlDPSAtMTQ3MjU3LjkgIFNTRT0gMC40MjYxOTA0ICBwLVZBTFVFPSAwLjU2MzA0MyAKI1Ryb24gMCAxIDYgQUlDPSAtMTMyMjMxLjkgIFNTRT0gMC45NDk3MDQyICBwLVZBTFVFPSAwLjA3MDc3NTQxCiNUcm9uIDUgMSAxIEFJQz0gLTEzMjIzMi4xICBTU0U9IDAuOTQ5NjkzMSAgcC1WQUxVRT0gMC4wODAyODExNAojVGV0aGVyIDAgMSA2IEFJQz0gLTE0NDg3MC4xICBTU0U9IDAuNDg0MDIxNiAgcC1WQUxVRT0gMC4wMTMxOTE4NAojVGV0aGVyIDEgMSA1IEFJQz0gLTE0NDg3MC4zICBTU0U9IDAuNDg0MDE2NSAgcC1WQUxVRT0gMC4wMTQ0NTMzCiNUZXRoZXIgMyAxIDEgQUlDPSAtMTQ0ODc0LjggIFNTRT0gMC40ODQwMDMxICBwLVZBTFVFPSAwLjAxNTIyNDUyCiNTdGVsbGFyIDAgMSA2IEFJQz0gLTEzMTQ4Ni42ICBTU0U9IDAuOTg4MjA0NSAgcC1WQUxVRT0gMC45Njg0NTMzCiNSaXBwbGUgNiAxIDAgQUlDPSAtMTM3NzQ5LjggIFNTRT0gMC43MDc1OTUyICBwLVZBTFVFPSAwLjk5Njk0NzcKI1JpcHBsZSAxIDEgNSBBSUM9IC0xMzc3NDguOCAgU1NFPSAwLjcwNzYzMjIgIHAtVkFMVUU9IDAuOTgyNTUyOCAKI1JpcHBsZSAwIDEgNiBBSUM9IC0xMzc3NDkuOSAgU1NFPSAwLjcwNzU4ODkgIHAtVkFMVUU9IDAuOTk3NjkwOQpgYGAKCmBgYHtyfQpmbSA8LSByb2xsYXBwbHkobG9nKG9yaWdbMToyMDE3LDJdKSwgd2lkdGggPSAyMDE2LAogICAgICAgICAgICAgICAgRlVOID0gZnVuY3Rpb24oeikgYXJpbWEobG9nKG9yaWdbMToyMDE3LDJdKSxvcmRlciA9IGMoMCwxLDYpKQopCmBgYAoKQ29kZSBmb3Igcm9sbGluZyB3aW5kb3cgZm9yIERhc2gKYGBge3J9CiMgeD1vcmlnWyw2XQojIHg9bG9nKCh4KSkKIyBtbT1saXN0KCkKIyAKIyBmb3IgKGkgaW4gMToobGVuZ3RoKHgpLTIwMTYrMSkpewojICAgbW1bW2ldXT1hcmltYSh4W2k6KGkrMjAxNSldLCBvcmRlcj1jKDAsMSw2KSkKIyB9CiMgZj1saXN0KCkKIyBmZj1yZXAoMCxsZW5ndGgoeCkpCiMgZm9yIChpIGluIDE6KGxlbmd0aCh4KS0yMDE2KzEpKXsKIyAgIGZbW2ldXT1wcmVkaWN0KG1tW1tpXV0sbi5haGVhZCA9IDEpCiMgICBmZlsyMDE2K2ldPWZbW2ldXSRwcmVkWzFdCiMgfQpgYGAKCgpgYGB7cn0KCng9b3JpZ1ssNl0KeD1sb2coKHgpKQptbT1saXN0KCkKCmZvciAoaSBpbiAxOihsZW5ndGgoeCktMjAxNisxKSl7CiAgbW1bW2ldXT1hcmltYSh4W2k6KGkrMjAxNSldLCBvcmRlcj1jKDAsMSw2KSkKfQpmPWxpc3QoKQpmZj1yZXAoMCxsZW5ndGgoeCkpCmZvciAoaSBpbiAxOihsZW5ndGgoeCktMjAxNisxKSl7CiAgZltbaV1dPXByZWRpY3QobW1bW2ldXSxuLmFoZWFkID0gMSkKICBmZlsyMDE2K2ldPWZbW2ldXSRwcmVkWzFdCn0KI3dpbmRvd3MoKQojIHBsb3QoeCxjb2w9ImJsdWUiLHR5cGU9ImwiLGx3ZD0wLjc1KQojIGxpbmVzKGZmLGNvbD0icmVkIixsd2Q9MikKIyBzcXJ0KG1lYW4oKHhbMjAxNzpsZW5ndGgoeCldLWZmWzIwMTc6bGVuZ3RoKHgpXSleMikpCgoKcGFyMiA8LSBwYXIobWZyb3c9YygyLCAxKSkKcGxvdCh4LGNvbD0iYmx1ZSIsdHlwZT0ibCIsbHdkPTAuNzUsIG1haW49IkRhc2ggb3JnaW5hbCBwcmljZSBzZXJpZXMiKQpwbG90KGZmWzIwMTc6bGVuZ3RoKGZmKV0sY29sPSJyZWQiLHR5cGU9ImwiLCBsd2Q9MC43NSwgbWFpbj0iRGFzaCBwcmVkaWN0aW9uIHByaWNlIHNlcmllcyIpCnNxcnQobWVhbigoeFsyMDE3Omxlbmd0aCh4KV0tZmZbMjAxNzpsZW5ndGgoeCldKV4yKSkKCgojIFdlIHNlZSBhIGRpZmZlcmVuY2UgaW4gdGhlIGZpZnRoIGRpZ2l0IGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50Cm1lYW4oZmZbMjAxNzpsZW5ndGgoZmYpXSkgICMgWzFdIDYuMzYyODI1Cm1lYW4oeFsyMDE3Omxlbmd0aCh4KV0pICAgICMgWzFdIDYuMzYyODA2CgojIFdlIHNlZSBhIGRpZmZlcmVuY2UgaW4gdGhlIGZpZnRoIHRoaXJkIGRpZ2l0IGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50CnNkKGZmWzIwMTc6bGVuZ3RoKGZmKV0pICAjIFsxXSAwLjIwNzAwNzEKc2QoeFsyMDE3Omxlbmd0aCh4KV0pICAgICMgWzFdIDAuMjA2OTk1MgoKCgpgYGAKCgoKCgoKCgoKCgoKCgo=