install.packages("vars")
library(ggfortify)
Warning: package ‘ggfortify’ was built under R version 4.1.2
Loading required package: ggplot2
Warning: package ‘ggplot2’ was built under R version 4.1.2
library(tseries)
Warning: package ‘tseries’ was built under R version 4.1.2
Registered S3 method overwritten by 'quantmod':
method from
as.zoo.data.frame zoo
‘tseries’ version: 0.10-49
‘tseries’ is a package for time series analysis and computational
finance.
See ‘library(help="tseries")’ for details.
library(forecast)
Warning: package ‘forecast’ was built under R version 4.1.2
Registered S3 methods overwritten by 'forecast':
method from
autoplot.Arima ggfortify
autoplot.acf ggfortify
autoplot.ar ggfortify
autoplot.bats ggfortify
autoplot.decomposed.ts ggfortify
autoplot.ets ggfortify
autoplot.forecast ggfortify
autoplot.stl ggfortify
autoplot.ts ggfortify
fitted.ar ggfortify
fortify.ts ggfortify
residuals.ar ggfortify
library(vars)
Warning: package ‘vars’ was built under R version 4.1.2
Loading required package: MASS
Loading required package: strucchange
Warning: package ‘strucchange’ was built under R version 4.1.2
Loading required package: zoo
Attaching package: ‘zoo’
The following objects are masked from ‘package:base’:
as.Date, as.Date.numeric
Loading required package: sandwich
Warning: package ‘sandwich’ was built under R version 4.1.2
Loading required package: urca
Loading required package: lmtest
homes = read.csv(file ="C:/CS-637-Time-Series-and-Forecasting--main/EHSv2.csv")
homes.ts <- ts(homes, start=c(1999, 1), frequency=12)
# Plot the raw data using the base plot function
plot(homes.ts,xlab="Date", ylab = "Existing Homes (1000's)",main="Existing Home Sales from 1999 to 2020")

decomposehomes <- decompose(homes.ts,"multiplicative")
autoplot(decomposehomes)

#Holtwinters
H.hw <- HoltWinters(homes.ts, alpha = 1, gamma = 0)
plot(H.hw)

acf(resid(H.hw))

plot (H.hw$fitted)

H.hw$coef
a b s1 s2 s3 s4
169.59722222 -0.11413878 -72.34722222 -62.72222222 -7.18055556 0.06944444
s5 s6 s7 s8 s9 s10
32.27777778 63.19444444 52.02777778 52.86111111 -1.59722222 -11.18055556
s11 s12
-23.80555556 -21.59722222
H.hw$SSE
[1] 101053.3
#AR Model
acf(diff(homes.ts))

homes.ar <- ar(homes.ts)
paste0("Mean: ", mean(homes.ts))
[1] "Mean: 93.0416666666667"
paste0("Order: ", homes.ar$order)
[1] "Order: 18"
paste0("Alpha: ", homes.ar$ar)
[1] "Alpha: 0.74092284126783" "Alpha: -0.00064557182983364"
[3] "Alpha: 0.0695373768056502" "Alpha: -0.135294734973541"
[5] "Alpha: -0.0143891027438956" "Alpha: 0.0917129578437509"
[7] "Alpha: 0.0022692678372882" "Alpha: 0.0324558909377331"
[9] "Alpha: -0.00593466469575808" "Alpha: -0.0322397889430825"
[11] "Alpha: 0.0885102471552561" "Alpha: 0.696120587845432"
[13] "Alpha: -0.58257269720213" "Alpha: 0.120507164069272"
[15] "Alpha: -0.172167110327466" "Alpha: 0.151507269552817"
[17] "Alpha: 0.000165208083174551" "Alpha: -0.131012461122949"
paste0("95% CI: ", homes.ar$ar + c(-2, 2) * sqrt(homes.ar$asy.var))
Warning in sqrt(homes.ar$asy.var) : NaNs produced
[1] "95% CI: 0.61424885927159" "95% CI: NaN"
[3] "95% CI: 0.051245006547405" "95% CI: NaN"
[5] "95% CI: -0.0640545426427443" "95% CI: NaN"
[7] "95% CI: NaN" "95% CI: 0.0447957566315232"
[9] "95% CI: NaN" "95% CI: -0.0230638224039667"
[11] "95% CI: 0.0641015116521294" "95% CI: NaN"
[13] "95% CI: NaN" "95% CI: 0.217875603446453"
[15] "95% CI: NaN" "95% CI: 0.205909756471183"
[17] "95% CI: NaN" "95% CI: -0.091236575319032"
[19] "95% CI: NaN" "95% CI: 0.157496826644101"
[21] "95% CI: NaN" "95% CI: -0.100998263735436"
[23] "95% CI: NaN" "95% CI: 0.139610417356546"
[25] "95% CI: -0.00754703718192579" "95% CI: 0.0367969495381682"
[27] "95% CI: -0.0292792230112198" "95% CI: NaN"
[29] "95% CI: NaN" "95% CI: 0.73694291146916"
[31] "95% CI: -0.666120903724099" "95% CI: NaN"
[33] "95% CI: -0.276755431181472" "95% CI: NaN"
[35] "95% CI: -0.0690617391870011" "95% CI: NaN"
[37] "95% CI: 0.722630471009584" "95% CI: NaN"
[39] "95% CI: -0.0874156684793713" "95% CI: NaN"
[41] "95% CI: -0.0440469660347151" "95% CI: NaN"
[43] "95% CI: -0.0216322884626641" "95% CI: NaN"
[45] "95% CI: -0.0158468119813041" "95% CI: -0.00858157958947119"
[47] "95% CI: NaN" "95% CI: NaN"
[49] "95% CI: -0.620417973687976" "95% CI: 0.204304752412022"
[51] "95% CI: NaN" "95% CI: 0.25527877173673"
[53] "95% CI: NaN" "95% CI: -0.0766099742045827"
[55] "95% CI: NaN" "95% CI: 0.0336508994082711"
[57] "95% CI: NaN" "95% CI: 0.0203627782093273"
[59] "95% CI: NaN" "95% CI: NaN"
[61] "95% CI: -0.0167446066105613" "95% CI: 0.0611378262395565"
[63] "95% CI: NaN" "95% CI: -0.0235892793940565"
[65] "95% CI: 0.0637243863469893" "95% CI: NaN"
[67] "95% CI: -0.609695997200473" "95% CI: 0.147533476546945"
[69] "95% CI: -0.254499055872116" "95% CI: NaN"
[71] "95% CI: -0.104423112770832" "95% CI: NaN"
[73] "95% CI: 0.691257401368981" "95% CI: NaN"
[75] "95% CI: 0.0398795135148309" "95% CI: NaN"
[77] "95% CI: -0.170244868095874" "95% CI: NaN"
[79] "95% CI: NaN" "95% CI: 0.0459604877071382"
[81] "95% CI: -0.0344722263089891" "95% CI: NaN"
[83] "95% CI: 0.0794443888895956" "95% CI: 0.716476532238231"
[85] "95% CI: NaN" "95% CI: 0.165793194632829"
[87] "95% CI: -0.199193422805139" "95% CI: 0.235304857895568"
[89] "95% CI: NaN" "95% CI: -0.0336440217457678"
[91] "95% CI: NaN" "95% CI: 0.0472518876829614"
[93] "95% CI: NaN" "95% CI: NaN"
[95] "95% CI: NaN" "95% CI: 0.228655731463068"
[97] "95% CI: NaN" "95% CI: NaN"
[99] "95% CI: NaN" "95% CI: -0.00468366979464279"
[101] "95% CI: 0.075677373625157" "95% CI: 0.705229950459068"
[103] "95% CI: -0.616086078867268" "95% CI: NaN"
[105] "95% CI: -0.19929041032581" "95% CI: 0.189352546038664"
[107] "95% CI: -0.0833829984387949" "95% CI: NaN"
[109] "95% CI: NaN" "95% CI: 0.00917073318938027"
[111] "95% CI: 0.0456358205056979" "95% CI: -0.116280860525691"
[113] "95% CI: NaN" "95% CI: NaN"
[115] "95% CI: -0.102511821176648" "95% CI: NaN"
[117] "95% CI: NaN" "95% CI: NaN"
[119] "95% CI: 0.0700116927730463" "95% CI: 0.712595510974366"
[121] "95% CI: -0.591682059815766" "95% CI: 0.140863108462071"
[123] "95% CI: NaN" "95% CI: NaN"
[125] "95% CI: -0.0406571155405534" "95% CI: NaN"
[127] "95% CI: 0.72858297557404" "95% CI: 0.00369548677060156"
[129] "95% CI: NaN" "95% CI: -0.106612799671717"
[131] "95% CI: -0.0278936995133003" "95% CI: NaN"
[133] "95% CI: NaN" "95% CI: 0.136625260746595"
[135] "95% CI: NaN" "95% CI: NaN"
[137] "95% CI: NaN" "95% CI: 0.714619142227641"
[139] "95% CI: -0.595405570732229" "95% CI: 0.129573022334932"
[141] "95% CI: -0.196952971135733" "95% CI: NaN"
[143] "95% CI: NaN" "95% CI: -0.106603725619822"
[145] "95% CI: NaN" "95% CI: 0.0226989864856281"
[147] "95% CI: 0.0596252295201042" "95% CI: NaN"
[149] "95% CI: -0.0429266643571268" "95% CI: NaN"
[151] "95% CI: NaN" "95% CI: NaN"
[153] "95% CI: -0.110105130113762" "95% CI: NaN"
[155] "95% CI: NaN" "95% CI: NaN"
[157] "95% CI: -0.610128816350569" "95% CI: NaN"
[159] "95% CI: -0.180817619876491" "95% CI: 0.175165478906429"
[161] "95% CI: NaN" "95% CI: -0.121836494583833"
[163] "95% CI: 0.731746874728714" "95% CI: NaN"
[165] "95% CI: 0.0458791674520389" "95% CI: -0.126644225424515"
[167] "95% CI: NaN" "95% CI: 0.119269076992191"
[169] "95% CI: NaN" "95% CI: NaN"
[171] "95% CI: NaN" "95% CI: 0.0719306764749211"
[173] "95% CI: NaN" "95% CI: NaN"
[175] "95% CI: NaN" "95% CI: 0.149044725682503"
[177] "95% CI: NaN" "95% CI: 0.161419416838363"
[179] "95% CI: -0.0231793502322874" "95% CI: NaN"
[181] "95% CI: 0.716514105764703" "95% CI: NaN"
[183] "95% CI: NaN" "95% CI: -0.110508874165274"
[185] "95% CI: -0.0234549610095559" "95% CI: 0.10454583137385"
[187] "95% CI: -0.0162292865449214" "95% CI: NaN"
[189] "95% CI: NaN" "95% CI: NaN"
[191] "95% CI: -0.0156591226536057" "95% CI: NaN"
[193] "95% CI: NaN" "95% CI: 0.134011760838677"
[195] "95% CI: -0.20084904562929" "95% CI: NaN"
[197] "95% CI: -0.00417585051726052" "95% CI: -0.118672595429159"
[199] "95% CI: NaN" "95% CI: 0.0401767517938944"
[201] "95% CI: NaN" "95% CI: NaN"
[203] "95% CI: -0.0347450471366948" "95% CI: 0.100822320457388"
[205] "95% CI: -0.0142056552916467" "95% CI: 0.0509544453199427"
[207] "95% CI: NaN" "95% CI: NaN"
[209] "95% CI: NaN" "95% CI: 0.800901676859367"
[211] "95% CI: NaN" "95% CI: NaN"
[213] "95% CI: -0.191180984775316" "95% CI: 0.17540882585277"
[215] "95% CI: -0.00965109693603949" "95% CI: NaN"
[217] "95% CI: NaN" "95% CI: 0.0829026346921353"
[219] "95% CI: 0.0316921003198032" "95% CI: -0.108171434975197"
[221] "95% CI: NaN" "95% CI: 0.12522633950889"
[223] "95% CI: -0.00684009477634864" "95% CI: 0.0452887644678323"
[225] "95% CI: -0.0334907838441977" "95% CI: NaN"
[227] "95% CI: NaN" "95% CI: NaN"
[229] "95% CI: -0.719515470821447" "95% CI: NaN"
[231] "95% CI: NaN" "95% CI: NaN"
[233] "95% CI: -0.0477322514296204" "95% CI: NaN"
[235] "95% CI: 0.643554401890649" "95% CI: NaN"
[237] "95% CI: -0.0142602115371001" "95% CI: -0.108268422495868"
[239] "95% CI: -0.0596751333074524" "95% CI: NaN"
[241] "95% CI: -0.0180866765555111" "95% CI: 0.0415217492033932"
[243] "95% CI: NaN" "95% CI: -0.00370222732985142"
[245] "95% CI: 0.0750056503858512" "95% CI: NaN"
[247] "95% CI: NaN" "95% CI: 0.27636292942125"
[249] "95% CI: NaN" "95% CI: 0.181165132843637"
[251] "95% CI: NaN" "95% CI: -0.0813470212241"
[253] "95% CI: NaN" "95% CI: 0.103942749024173"
[255] "95% CI: NaN" "95% CI: -0.0529627894288909"
[257] "95% CI: -0.0414154152215685" "95% CI: 0.118836257842094"
[259] "95% CI: NaN" "95% CI: 0.057241751746"
[261] "95% CI: -0.0145851742447835" "95% CI: NaN"
[263] "95% CI: 0.0598283118534327" "95% CI: 0.715134462293281"
[265] "95% CI: NaN" "95% CI: NaN"
[267] "95% CI: -0.327824623510334" "95% CI: NaN"
[269] "95% CI: -0.0341312631549306" "95% CI: NaN"
[271] "95% CI: 0.686520354349464" "95% CI: NaN"
[273] "95% CI: -0.0342341253782617" "95% CI: NaN"
[275] "95% CI: -0.098186691086646" "95% CI: 0.129558234329598"
[277] "95% CI: NaN" "95% CI: NaN"
[279] "95% CI: -0.0295928740493695" "95% CI: -0.0223276416575369"
[281] "95% CI: NaN" "95% CI: 0.720022144145384"
[283] "95% CI: NaN" "95% CI: 0.150165027360091"
[285] "95% CI: NaN" "95% CI: 0.308460314837839"
[287] "95% CI: NaN" "95% CI: -0.112720090864703"
[289] "95% CI: NaN" "95% CI: 0.068581375440342"
[291] "95% CI: NaN" "95% CI: -0.0307064141195342"
[293] "95% CI: NaN" "95% CI: 0.17526116436572"
[295] "95% CI: -0.0385530557864399" "95% CI: NaN"
[297] "95% CI: NaN" "95% CI: -0.0088952306276206"
[299] "95% CI: 0.0841691885548217" "95% CI: 0.705936892864646"
[301] "95% CI: -0.630470156714925" "95% CI: NaN"
[303] "95% CI: -0.206463581565571" "95% CI: NaN"
[305] "95% CI: -0.15797719039076" "95% CI: NaN"
[307] "95% CI: 0.701146955463913" "95% CI: NaN"
[309] "95% CI: 0.0151348898872841" "95% CI: NaN"
[311] "95% CI: -0.111757542121077" "95% CI: NaN"
[313] "95% CI: NaN" "95% CI: 0.05686462644086"
[315] "95% CI: -0.0151106312348738" "95% CI: NaN"
[317] "95% CI: 0.0761703814614659" "95% CI: NaN"
[319] "95% CI: NaN" "95% CI: 0.170172603968121"
[321] "95% CI: NaN" "95% CI: 0.169799639811064"
[323] "95% CI: NaN" "95% CI: -0.00433847912670843"
acf(homes.ar$res[-1])
Error in na.fail.default(as.ts(x)) : missing values in object
ts.plot(homes.ts)

DP <- diff(homes.ts)
plot(as.ts(DP))

acf(DP)

mean(DP) + c(-2, 2) * sd(DP)/sqrt(length(DP))
[1] -3.565491 4.569294
boxplot(homes.ts~cycle(homes.ts),xlab="Date", ylab = "Home Sales (1000's)" ,main ="Existing Home Sales Boxplot from 1999 to 2020")

#Test stationarity of the time series (ADF)
adf.test(homes.ts)
Warning in adf.test(homes.ts) : p-value smaller than printed p-value
Augmented Dickey-Fuller Test
data: homes.ts
Dickey-Fuller = -4.2119, Lag order = 6, p-value = 0.01
alternative hypothesis: stationary
#Test stationarity of the time series (Autocorrelation)
autoplot(acf(homes.ts,plot=FALSE))+ labs(title="Correlogram of Existing Home Sales from 1999 to 2020")

# Review random time series for any missing values
decomposehomes$random
Jan Feb Mar Apr May Jun Jul
1999 NA NA NA NA NA NA 1.1032138
2000 0.7471242 0.9647163 1.0861664 0.8958302 0.9721120 1.0445071 0.9562007
2001 0.8959457 0.7994850 1.1391593 0.9683893 0.9705731 1.0303365 1.0521361
2002 1.6262728 1.3400270 1.0502201 1.0852613 1.0217421 0.8509614 0.9684505
2003 1.7534877 1.2839186 0.9490118 0.9656290 0.9166626 0.8123944 0.9521887
2004 1.4442928 1.4816236 1.2023740 1.1029251 0.8671025 0.7759704 0.8619054
2005 1.7919323 1.5852357 1.2420813 1.0279263 0.8434099 0.7520451 0.8447768
2006 1.6669975 1.6224832 1.2762148 1.0070171 0.8981061 0.8111830 0.8741685
2007 1.3275135 1.3018466 1.0083741 0.9750104 1.0345445 1.0610047 1.0888602
2008 0.2606451 0.6648082 0.7157827 0.9353234 1.0903689 1.1357747 1.2788053
2009 0.1121819 0.3435429 0.5572081 0.8234928 0.8231217 1.0757494 1.2348246
2010 0.1474391 0.4288815 1.0574149 1.6052556 1.4723900 1.4924202 0.5071150
2011 0.5977799 0.5220470 1.0816703 1.0884550 0.9479613 1.1842651 0.8776538
2012 0.6673561 0.9362595 0.9248319 0.9667644 1.1269514 1.0438293 0.9189143
2013 0.9663403 0.9074717 0.8878940 1.0947429 1.1400443 0.9189579 1.1392809
2014 0.6540340 0.5667614 0.7057765 0.9507975 1.0670037 1.0174648 1.0989700
2015 0.5822650 0.7278423 0.9177545 0.9791645 0.9634593 1.1020116 1.1708390
2016 0.9101947 0.9731486 0.9753523 1.0284439 0.9979752 1.0216221 0.9131125
2017 1.3281877 0.9338656 1.1801175 0.8482081 1.0859714 0.9986222 0.8904037
2018 1.1307373 1.0553368 1.0310295 0.9710272 1.0513212 1.0386968 1.0022745
2019 0.6579942 0.9448600 0.8371957 0.9970403 1.1517246 0.8951613 1.0726252
2020 1.5379973 1.4225577 0.9810897 0.4900149 0.3641739 0.7437414 NA
Aug Sep Oct Nov Dec
1999 1.0609259 0.9532918 0.8688172 1.0064462 0.9206730
2000 1.0951518 1.0343578 0.9800087 1.1004968 0.8045493
2001 1.1205794 0.7797275 0.9409636 0.9529452 0.8740892
2002 0.9342772 0.9170661 1.0507936 1.0553706 1.1488710
2003 0.9164478 1.2058768 1.1309633 0.9675022 1.1473590
2004 0.8145749 1.0738350 1.0618611 1.3147930 1.2493292
2005 0.8223871 1.1340074 1.0882428 1.3058569 1.1412458
2006 0.8878485 1.0431984 1.0737694 1.2930181 1.1478331
2007 1.1275575 0.6495928 0.7722568 0.8081698 0.6556508
2008 1.1528771 1.1943650 0.9991209 0.3448566 0.6415508
2009 0.9749603 1.1378990 1.3569016 1.4434377 0.7636518
2010 0.6266981 0.6737898 0.4967009 0.6756946 1.2417400
2011 1.1770663 1.0205276 0.7485791 0.9452040 0.9379527
2012 1.1759497 0.7619739 0.9599266 1.1603551 0.8975498
2013 1.0889929 0.9965762 1.0161778 0.8253968 0.9561006
2014 0.9968449 1.0919241 1.1553238 0.7230650 1.0901564
2015 0.9067078 1.1624320 0.9920142 0.6158981 1.1199111
2016 0.9738097 1.1273928 0.9287702 1.0447404 1.0574169
2017 0.9358159 1.0276552 1.0263462 1.1166599 1.0074414
2018 1.0434286 0.8306383 1.0447795 1.0603488 0.7601642
2019 0.9738180 0.9905919 1.1144020 1.0464635 1.2434834
2020 NA NA NA NA NA
# Autoplot the random time series from 7:146 which exclude the NA values
autoplot(acf(decomposehomes$random[7:146],plot=FALSE))+ labs(title="Correlogram of Home Sales Random Component from 1999 to 2020")

#Linear Model
autoplot(homes.ts) + geom_smooth(method="lm")+ labs(x ="Date", y = "Home Sales (1000's)", title="Existing Home Sales from 1999 to 2020")
`geom_smooth()` using formula 'y ~ x'

#ARIMA Model
arimahomes <- auto.arima(homes.ts)
arimahomes
Series: homes.ts
ARIMA(1,0,0)(1,1,0)[12] with drift
Coefficients:
ar1 sar1 drift
0.7427 -0.1052 0.1289
s.e. 0.0440 0.0699 0.3405
sigma^2 estimated as 348.5: log likelihood=-1094.08
AIC=2196.15 AICc=2196.32 BIC=2210.27
ggtsdiag(arimahomes)

forecasthomes <- forecast(arimahomes, level = c(95), h = 36)
autoplot(forecasthomes)

## Seasonal ARIMA
AIC (arima(log(homes.ts), order = c(1,1,0),
seas = list(order = c(1,0,0), 12)))
[1] 164.038
AIC (arima(log(homes.ts), order = c(0,1,1),
seas = list(order = c(0,0,1), 12)))
[1] 359.4662
get.best.arima <- function(x.ts, maxord = c(1,1,1,1,1,1)) {
best.aic <- 1e8
n <- length(x.ts)
for (p in 0:maxord[1]) for(d in 0:maxord[2]) for(q in 0:maxord[3]){
for (P in 0:maxord[4]) for(D in 0:maxord[5]) for(Q in 0:maxord[6]){
fit <- arima(x.ts, order = c(p,d,q),
seas = list(order = c(P,D,Q),
frequency(x.ts)), method = "CSS")
fit.aic <- -2 * fit$loglik + (log(n) + 1) * length(fit$coef)
if (fit.aic < best.aic){
best.aic <- fit.aic
best.fit <- fit
best.model <- c(p,d,q,P,D,Q)
}
}
}
return(list(best.aic, best.fit, best.model))
}
best.arima.homes <- get.best.arima( log(homes.ts),
maxord = c(2,2,2,2,2,2))
Warning in arima(x.ts, order = c(p, d, q), seas = list(order = c(P, D, Q), :
possible convergence problem: optim gave code = 1
Warning in arima(x.ts, order = c(p, d, q), seas = list(order = c(P, D, Q), :
possible convergence problem: optim gave code = 1
Warning in arima(x.ts, order = c(p, d, q), seas = list(order = c(P, D, Q), :
possible convergence problem: optim gave code = 1
Warning in arima(x.ts, order = c(p, d, q), seas = list(order = c(P, D, Q), :
possible convergence problem: optim gave code = 1
Warning in arima(x.ts, order = c(p, d, q), seas = list(order = c(P, D, Q), :
possible convergence problem: optim gave code = 1
Warning in arima(x.ts, order = c(p, d, q), seas = list(order = c(P, D, Q), :
possible convergence problem: optim gave code = 1
best.fit.homes <- best.arima.homes[[2]]
acf(resid(best.fit.homes))

best.arima.homes[[3]]
[1] 2 0 0 0 1 2
ts.plot( cbind( window(homes.ts,start = 1999),
exp(predict(best.fit.homes,12)$pred) ), lty = 1:2)

LS0tDQp0aXRsZTogIkRlbGl2ZXJhYmxlICMzIg0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCmBgYHtyfQ0KaW5zdGFsbC5wYWNrYWdlcygidmFycyIpDQpgYGANCg0KYGBge3J9DQpsaWJyYXJ5KGdnZm9ydGlmeSkNCmxpYnJhcnkodHNlcmllcykNCmxpYnJhcnkoZm9yZWNhc3QpDQpsaWJyYXJ5KHZhcnMpDQpgYGANCg0KDQpgYGB7cn0NCmhvbWVzID0gcmVhZC5jc3YoZmlsZSA9IkM6L0NTLTYzNy1UaW1lLVNlcmllcy1hbmQtRm9yZWNhc3RpbmctLW1haW4vRUhTdjIuY3N2IikNCmhvbWVzLnRzIDwtIHRzKGhvbWVzLCBzdGFydD1jKDE5OTksIDEpLCBmcmVxdWVuY3k9MTIpDQoNCiMgUGxvdCB0aGUgcmF3IGRhdGEgdXNpbmcgdGhlIGJhc2UgcGxvdCBmdW5jdGlvbg0KcGxvdChob21lcy50cyx4bGFiPSJEYXRlIiwgeWxhYiA9ICJFeGlzdGluZyBIb21lcyAoMTAwMCdzKSIsbWFpbj0iRXhpc3RpbmcgSG9tZSBTYWxlcyBmcm9tIDE5OTkgdG8gMjAyMCIpDQoNCmBgYA0KYGBge3J9DQoNCmRlY29tcG9zZWhvbWVzIDwtIGRlY29tcG9zZShob21lcy50cywibXVsdGlwbGljYXRpdmUiKQ0KYXV0b3Bsb3QoZGVjb21wb3NlaG9tZXMpDQpgYGANCmBgYHtyfQ0KI0hvbHR3aW50ZXJzDQoNCkguaHcgPC0gSG9sdFdpbnRlcnMoaG9tZXMudHMsIGFscGhhID0gMSwgZ2FtbWEgPSAwKQ0KcGxvdChILmh3KQ0KYWNmKHJlc2lkKEguaHcpKQ0KcGxvdCAoSC5odyRmaXR0ZWQpDQpILmh3JGNvZWYNCkguaHckU1NFDQpgYGANCmBgYHtyfQ0KI0FSIE1vZGVsDQoNCmFjZihkaWZmKGhvbWVzLnRzKSkNCmhvbWVzLmFyIDwtIGFyKGhvbWVzLnRzKQ0KcGFzdGUwKCJNZWFuOiAiLCBtZWFuKGhvbWVzLnRzKSkNCnBhc3RlMCgiT3JkZXI6ICIsIGhvbWVzLmFyJG9yZGVyKQ0KcGFzdGUwKCJBbHBoYTogIiwgaG9tZXMuYXIkYXIpDQpwYXN0ZTAoIjk1JSBDSTogIiwgaG9tZXMuYXIkYXIgKyBjKC0yLCAyKSAqIHNxcnQoaG9tZXMuYXIkYXN5LnZhcikpDQphY2YoaG9tZXMuYXIkcmVzWy0xXSkNCmBgYA0KYGBge3J9DQp0cy5wbG90KGhvbWVzLnRzKQ0KRFAgPC0gZGlmZihob21lcy50cykNCnBsb3QoYXMudHMoRFApKQ0KYWNmKERQKQ0KbWVhbihEUCkgKyBjKC0yLCAyKSAqIHNkKERQKS9zcXJ0KGxlbmd0aChEUCkpDQpgYGANCmBgYHtyfQ0KYm94cGxvdChob21lcy50c35jeWNsZShob21lcy50cykseGxhYj0iRGF0ZSIsIHlsYWIgPSAiSG9tZSBTYWxlcyAoMTAwMCdzKSIgLG1haW4gPSJFeGlzdGluZyBIb21lIFNhbGVzIEJveHBsb3QgZnJvbSAxOTk5IHRvIDIwMjAiKQ0KYGBgDQpgYGB7cn0NCiNUZXN0IHN0YXRpb25hcml0eSBvZiB0aGUgdGltZSBzZXJpZXMgKEFERikNCmFkZi50ZXN0KGhvbWVzLnRzKSANCg0KYGBgDQpgYGB7cn0NCiNUZXN0IHN0YXRpb25hcml0eSBvZiB0aGUgdGltZSBzZXJpZXMgKEF1dG9jb3JyZWxhdGlvbikNCg0KYXV0b3Bsb3QoYWNmKGhvbWVzLnRzLHBsb3Q9RkFMU0UpKSsgbGFicyh0aXRsZT0iQ29ycmVsb2dyYW0gb2YgRXhpc3RpbmcgSG9tZSBTYWxlcyBmcm9tIDE5OTkgdG8gMjAyMCIpIA0KDQpgYGANCmBgYHtyfQ0KIyBSZXZpZXcgcmFuZG9tIHRpbWUgc2VyaWVzIGZvciBhbnkgbWlzc2luZyB2YWx1ZXMNCmRlY29tcG9zZWhvbWVzJHJhbmRvbSANCmBgYA0KYGBge3J9DQojIEF1dG9wbG90IHRoZSByYW5kb20gdGltZSBzZXJpZXMgZnJvbSA3OjE0NiB3aGljaCBleGNsdWRlIHRoZSBOQSB2YWx1ZXMNCg0KYXV0b3Bsb3QoYWNmKGRlY29tcG9zZWhvbWVzJHJhbmRvbVs3OjE0Nl0scGxvdD1GQUxTRSkpKyBsYWJzKHRpdGxlPSJDb3JyZWxvZ3JhbSBvZiBIb21lIFNhbGVzIFJhbmRvbSBDb21wb25lbnQgZnJvbSAxOTk5IHRvIDIwMjAiKSANCmBgYA0KYGBge3J9DQojTGluZWFyIE1vZGVsDQphdXRvcGxvdChob21lcy50cykgKyBnZW9tX3Ntb290aChtZXRob2Q9ImxtIikrIGxhYnMoeCA9IkRhdGUiLCB5ID0gIkhvbWUgU2FsZXMgKDEwMDAncykiLCB0aXRsZT0iRXhpc3RpbmcgSG9tZSBTYWxlcyBmcm9tIDE5OTkgdG8gMjAyMCIpIA0KYGBgDQpgYGB7cn0NCiNBUklNQSBNb2RlbA0KYXJpbWFob21lcyA8LSBhdXRvLmFyaW1hKGhvbWVzLnRzKQ0KYXJpbWFob21lcw0KYGBgDQpgYGB7cn0NCmdndHNkaWFnKGFyaW1haG9tZXMpDQoNCmBgYA0KYGBge3J9DQpmb3JlY2FzdGhvbWVzIDwtIGZvcmVjYXN0KGFyaW1haG9tZXMsIGxldmVsID0gYyg5NSksIGggPSAzNikNCmF1dG9wbG90KGZvcmVjYXN0aG9tZXMpDQpgYGANCmBgYHtyfQ0KIyMgU2Vhc29uYWwgQVJJTUENCg0KQUlDIChhcmltYShsb2coaG9tZXMudHMpLCBvcmRlciA9IGMoMSwxLDApLA0KICAgICAgICAgICBzZWFzID0gbGlzdChvcmRlciA9IGMoMSwwLDApLCAxMikpKQ0KQUlDIChhcmltYShsb2coaG9tZXMudHMpLCBvcmRlciA9IGMoMCwxLDEpLA0KICAgICAgICAgICBzZWFzID0gbGlzdChvcmRlciA9IGMoMCwwLDEpLCAxMikpKQ0KYGBgDQoNCmBgYHtyfQ0KZ2V0LmJlc3QuYXJpbWEgPC0gZnVuY3Rpb24oeC50cywgbWF4b3JkID0gYygxLDEsMSwxLDEsMSkpIHsNCiAgYmVzdC5haWMgPC0gMWU4DQogIG4gPC0gbGVuZ3RoKHgudHMpDQogIGZvciAocCBpbiAwOm1heG9yZFsxXSkgZm9yKGQgaW4gMDptYXhvcmRbMl0pIGZvcihxIGluIDA6bWF4b3JkWzNdKXsNCiAgICANCiAgICBmb3IgKFAgaW4gMDptYXhvcmRbNF0pIGZvcihEIGluIDA6bWF4b3JkWzVdKSBmb3IoUSBpbiAwOm1heG9yZFs2XSl7DQogICAgICBmaXQgPC0gYXJpbWEoeC50cywgb3JkZXIgPSBjKHAsZCxxKSwNCiAgICAgICAgICAgICAgICAgICBzZWFzID0gbGlzdChvcmRlciA9IGMoUCxELFEpLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZyZXF1ZW5jeSh4LnRzKSksIG1ldGhvZCA9ICJDU1MiKQ0KICAgICAgZml0LmFpYyA8LSAtMiAqIGZpdCRsb2dsaWsgKyAobG9nKG4pICsgMSkgKiBsZW5ndGgoZml0JGNvZWYpDQogICAgICBpZiAoZml0LmFpYyA8IGJlc3QuYWljKXsNCiAgICAgICAgYmVzdC5haWMgPC0gZml0LmFpYw0KICAgICAgICBiZXN0LmZpdCA8LSBmaXQNCiAgICAgICAgYmVzdC5tb2RlbCA8LSBjKHAsZCxxLFAsRCxRKQ0KICAgICAgfQ0KICAgIH0NCiAgfQ0KICByZXR1cm4obGlzdChiZXN0LmFpYywgYmVzdC5maXQsIGJlc3QubW9kZWwpKQ0KfQ0KYmVzdC5hcmltYS5ob21lcyA8LSBnZXQuYmVzdC5hcmltYSggbG9nKGhvbWVzLnRzKSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWF4b3JkID0gYygyLDIsMiwyLDIsMikpDQoNCmJlc3QuZml0LmhvbWVzIDwtIGJlc3QuYXJpbWEuaG9tZXNbWzJdXQ0KYWNmKHJlc2lkKGJlc3QuZml0LmhvbWVzKSkNCmJlc3QuYXJpbWEuaG9tZXNbWzNdXQ0KdHMucGxvdCggY2JpbmQoIHdpbmRvdyhob21lcy50cyxzdGFydCA9IDE5OTkpLA0KICAgICAgICAgICAgICAgIGV4cChwcmVkaWN0KGJlc3QuZml0LmhvbWVzLDEyKSRwcmVkKSApLCBsdHkgPSAxOjIpDQpgYGANCmBgYA0KDQpgYGANCg0K