Question 1 – Dataset: AirPassengers
df <- matrix(AirPassengers,nrow=12,ncol=12)
colnames(df) <- 1949:1960
rownames(df) <- month.abb
# (a) arith_mean manual
arith_mean <- function(x){
n <- 0
total <- 0
for(val in x){
total <- total+val
n <- n+1
}
return(total/n)
}
# apply arith_mean() to each column of df
Y_bar <- numeric(12)
for (j in 1:12){
Y_bar[j] <- arith_mean(df[,j])
}
# display results
names(Y_bar) <- 1949:1960
print(Y_bar)
1949 1950 1951 1952 1953 1954
126.6667 139.6667 170.1667 197.0000 225.0000 238.9167
1955 1956 1957 1958 1959 1960
284.0000 328.2500 368.4167 381.0000 428.3333 476.1667
# validation
print(colMeans(df)==Y_bar)
1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960
TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE
# (b) geo_mean_growth()
geo_mean_growth <- function(y){
n <- 0
for(val in y) n <- n+1
# (i) growth factors r_t = Y_t / Y_{t-1}, t = 2..n
r <- numeric(n-1)
for(t in 2:n){
r[t-1] <- y[t]/y[t-1]
}
# (ii) geometric mean GM = (r2 * r3 * ... * rn)^(1/(n-1))
product <- 1
for(val in r){
product <- product*val
}
GM <- product^(1/(n-1))
# (iii) convert to percentage
g_bar <- (GM-1)*100
return(list(r=r,
GM=GM,
g_bar=g_bar))
}
# apply to Y_bar
results_GM <- geo_mean_growth(Y_bar)
cat(sprintf("Geometric mean growth rate: %.4f%%\n", results_GM$g_bar))
Geometric mean growth rate: 12.7928%
# (c) arithmetic mean of growth factors r_t
# arithmetic mean of r_t
AM <- arith_mean(results_GM$r)
# convert into percentage growth
g_bar_AM <- (AM-1)*100
cat(sprintf("Arithmetic mean growth rate: %.4f%%\n", g_bar_AM))
Arithmetic mean growth rate: 12.9056%
# (d) predict Y_bar_1960 and compare with the actual value
# extract from Y_bar
Y_1949 <- Y_bar["1949"]
Y_1960 <- Y_bar["1960"]
# prediction using geometric mean growth rate
Y_hat_GM <- Y_1949*(1+(results_GM$g_bar/100))^11
# prediction using arithmetic mean growth rate
Y_hat_AM <- Y_1949*(1+(g_bar_AM/100))^11
# absolute prediction error for each |Y_hat_1960 - Y_bar_1960|
err_GM <- abs(Y_hat_GM-Y_1960)
err_AM <- abs(Y_hat_AM-Y_1960)
{
cat(sprintf("Y_hat_GM (geometric) : %10.3f\n", Y_hat_GM))
cat(sprintf("Y_hat_AM (arithmetic): %10.3f\n", Y_hat_AM))
cat("\n")
cat(sprintf("Absolute error GM : %10.3f\n", err_GM))
cat(sprintf("Absolute error AM : %10.3f\n", err_AM))
}
Y_hat_GM (geometric) : 476.167
Y_hat_AM (arithmetic): 481.431
Absolute error GM : 0.000
Absolute error AM : 5.264
Question 2 – Dataset: airquality
data <- na.omit(airquality[, c("Ozone", "Solar.R", "Wind", "Temp")])
# (a) mat_mult() manual
mat_mult <- function(A,B){
m <- nrow(A)
n <- ncol(A)
p <- ncol(B)
C <- matrix(0,nrow=m,ncol=p)
for(i in 1:m){
for(j in 1:p){
val <- 0
for(k in 1:n){
val <- val+A[i,k]*B[k,j]
}
C[i,j] <- val
}
}
return(C)
}
# validation
a <- matrix(c(1, 2, 3, 4), nrow = 2)
b <- matrix(c(5, 6, 7, 8), nrow = 2)
c_std <- a %*% b
c_manual <- mat_mult(a, b)
{
cat("Standard result (a %*% b):\n")
print(c_std)
cat("\nManual result mat_mult(a, b):\n")
print(c_manual)
cat("\nElement-wise match:\n")
print(c_std == c_manual)
}
Standard result (a %*% b):
[,1] [,2]
[1,] 23 31
[2,] 34 46
Manual result mat_mult(a, b):
[,1] [,2]
[1,] 23 31
[2,] 34 46
Element-wise match:
[,1] [,2]
[1,] TRUE TRUE
[2,] TRUE TRUE
# (b) corr_matrix()
corr_matrix <- function(X){
X <- as.matrix(X)
n <- nrow(X)
p <- ncol(X)
# (i) column mean vector X_bar
ones <- matrix(1,nrow=n,ncol=1)
X_bar <- (1/n)*mat_mult(t(X),ones)
# (ii) centered matrix X_c and covariance matrix S
X_c <- X-mat_mult(ones,t(X_bar))
S <- (1/(n-1))*mat_mult(t(X_c),X_c)
# (iii) D^{-1/2} and correlation matrix R
D_inv_half <- diag(1/sqrt(diag(S)))
# Return R
R <- mat_mult(mat_mult(D_inv_half,S),D_inv_half)
rownames(R) <- colnames(X)
colnames(R) <- colnames(X)
return(R)
}
# apply to air quality data and display
R_hat <- corr_matrix(data)
print(round(R_hat, 6))
Ozone Solar.R Wind Temp
Ozone 1.000000 0.348342 -0.612497 0.698541
Solar.R 0.348342 1.000000 -0.127183 0.294088
Wind -0.612497 -0.127183 1.000000 -0.497190
Temp 0.698541 0.294088 -0.497190 1.000000
# validation
cat("\nElement-wise match with cor():\n\n")
Element-wise match with cor():
print(round(R_hat, 10) == round(cor(data), 10))
Ozone Solar.R Wind Temp
Ozone TRUE TRUE TRUE TRUE
Solar.R TRUE TRUE TRUE TRUE
Wind TRUE TRUE TRUE TRUE
Temp TRUE TRUE TRUE TRUE
# (c) corr_test_matrix() via trapezoidal integration
corr_test_matrix <- function(X,alpha=0.05){
X <- as.matrix(X)
n <- nrow(X)
p <- ncol(X)
df <- n-2
N <- 10000
# correlation matrix R
R <- corr_matrix(X)
# initialise p-value matrix
P <- matrix(0,nrow=p,ncol=p)
rownames(P) <- colnames(X)
colnames(P) <- colnames(X)
# p-values for each off-diagonal pair
for(i in 1:p){
for(j in 1:p){
if(i==j){
# set diagonal p-value to 0
P[i, j] <- 0
} else {
r_ij <- R[i,j]
# (i) test statistic t_ij
t_ij <- r_ij*sqrt(n-2)/sqrt(1-r_ij^2)
# (ii) trapezoidal integration of dt(t, df) from 0 to |t_ij|
abs_t <- abs(t_ij)
h <- abs_t/N
total <- dt(0,df)+dt(abs_t,df)
for(k in 1:(N-1)){
total <- total+2*dt(k*h, df)
}
integral <- (h/2)*total
# (ii) p_ij = 1 - 2 * integral
p_ij <- 1-2*integral
# store result in P[i, j]
P[i,j] <- p_ij
}
}
}
return(list(R = R, P = P))
}
# apply to air quality data
results <- corr_test_matrix(data, alpha = 0.05)
{
cat("========== Correlation Matrix (R) ==========\n")
print(round(results$R, 6))
cat("\n========== P-value Matrix (P) ==========\n")
print(round(results$P, 6))
}
========== Correlation Matrix (R) ==========
Ozone Solar.R Wind Temp
Ozone 1.000000 0.348342 -0.612497 0.698541
Solar.R 0.348342 1.000000 -0.127183 0.294088
Wind -0.612497 -0.127183 1.000000 -0.497190
Temp 0.698541 0.294088 -0.497190 1.000000
========== P-value Matrix (P) ==========
Ozone Solar.R Wind Temp
Ozone 0.000000 0.000179 0.000000 0.000000
Solar.R 0.000179 0.000000 0.183452 0.001731
Wind 0.000000 0.183452 0.000000 0.000000
Temp 0.000000 0.001731 0.000000 0.000000
# validation: compare P against cor.test() p-values
cor_mat <- matrix(0, ncol=4, nrow=4)
for (i in 1:4){
for (j in 1:4){
if(i==j){
cor_mat[i,j] <- 0
} else cor_mat[i,j] <- cor.test(data[,i], data[,j])$p.value
}
}
rownames(cor_mat) <- colnames(cor_mat) <- names(data)
{
cat("\nCorrelation Matrix\n")
print(cor(data))
cat("\n")
cat("P-value matrix\n")
print(cor_mat)
}
Correlation Matrix
Ozone Solar.R Wind Temp
Ozone 1.0000000 0.3483417 -0.6124966 0.6985414
Solar.R 0.3483417 1.0000000 -0.1271835 0.2940876
Wind -0.6124966 -0.1271835 1.0000000 -0.4971897
Temp 0.6985414 0.2940876 -0.4971897 1.0000000
P-value matrix
Ozone Solar.R Wind Temp
Ozone 0.000000e+00 0.0001793109 9.089415e-13 1.552677e-17
Solar.R 1.793109e-04 0.0000000000 1.834520e-01 1.730786e-03
Wind 9.089415e-13 0.1834519762 0.000000e+00 2.841966e-08
Temp 1.552677e-17 0.0017307856 2.841966e-08 0.000000e+00
# verify answer
round(results$P,10) == round(cor_mat,10)
Ozone Solar.R Wind Temp
Ozone TRUE TRUE TRUE TRUE
Solar.R TRUE TRUE FALSE FALSE
Wind TRUE FALSE TRUE TRUE
Temp TRUE FALSE TRUE TRUE
LS0tDQp0aXRsZTogIlJlZG8gTWlkdGVybSBFeGFtIg0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCg0KIyMjIE5hbWUgOiBWaW9sZXR0YSBBbW1hcmEgSXJpYW50aSBBZ3VuZw0KIyMjIFN0dWRlbnQgSUQgOiA1MDAzMjUxMTI2DQoNCiMjIyBRdWVzdGlvbiAxIOKAkyBEYXRhc2V0OiBBaXJQYXNzZW5nZXJzDQoNCmBgYHtyfQ0KZGYgPC0gbWF0cml4KEFpclBhc3NlbmdlcnMsbnJvdz0xMixuY29sPTEyKQ0KY29sbmFtZXMoZGYpIDwtIDE5NDk6MTk2MA0Kcm93bmFtZXMoZGYpIDwtIG1vbnRoLmFiYg0KDQojIChhKSBhcml0aF9tZWFuIG1hbnVhbA0KYXJpdGhfbWVhbiA8LSBmdW5jdGlvbih4KXsNCiAgbiA8LSAwDQogIHRvdGFsIDwtIDANCiAgZm9yKHZhbCBpbiB4KXsNCiAgICB0b3RhbCA8LSB0b3RhbCt2YWwNCiAgICBuIDwtIG4rMQ0KICB9DQogIHJldHVybih0b3RhbC9uKQ0KfQ0KDQojIGFwcGx5IGFyaXRoX21lYW4oKSB0byBlYWNoIGNvbHVtbiBvZiBkZg0KWV9iYXIgPC0gbnVtZXJpYygxMikNCmZvciAoaiBpbiAxOjEyKXsNCiAgWV9iYXJbal0gPC0gYXJpdGhfbWVhbihkZlssal0pDQp9DQoNCiMgZGlzcGxheSByZXN1bHRzDQpuYW1lcyhZX2JhcikgPC0gMTk0OToxOTYwDQpwcmludChZX2JhcikNCg0KIyB2YWxpZGF0aW9uDQpwcmludChjb2xNZWFucyhkZik9PVlfYmFyKQ0KYGBgDQoNCmBgYHtyfQ0KIyAoYikgZ2VvX21lYW5fZ3Jvd3RoKCkNCmdlb19tZWFuX2dyb3d0aCA8LSBmdW5jdGlvbih5KXsNCiAgbiA8LSAwDQogIGZvcih2YWwgaW4geSkgbiA8LSBuKzENCg0KICAjIChpKSBncm93dGggZmFjdG9ycyByX3QgPSBZX3QgLyBZX3t0LTF9LCB0ID0gMi4ubg0KICByIDwtIG51bWVyaWMobi0xKQ0KICBmb3IodCBpbiAyOm4pew0KICAgIHJbdC0xXSA8LSB5W3RdL3lbdC0xXQ0KICB9DQoNCiAgIyAoaWkpIGdlb21ldHJpYyBtZWFuIEdNID0gKHIyICogcjMgKiAuLi4gKiBybileKDEvKG4tMSkpDQogIHByb2R1Y3QgPC0gMQ0KICBmb3IodmFsIGluIHIpew0KICAgIHByb2R1Y3QgPC0gcHJvZHVjdCp2YWwNCiAgfQ0KICBHTSA8LSBwcm9kdWN0XigxLyhuLTEpKQ0KDQogICMgKGlpaSkgY29udmVydCB0byBwZXJjZW50YWdlDQogIGdfYmFyIDwtIChHTS0xKSoxMDANCg0KICByZXR1cm4obGlzdChyPXIsDQogICAgICAgICAgICAgIEdNPUdNLA0KICAgICAgICAgICAgICBnX2Jhcj1nX2JhcikpDQp9DQoNCiMgYXBwbHkgdG8gWV9iYXINCnJlc3VsdHNfR00gPC0gZ2VvX21lYW5fZ3Jvd3RoKFlfYmFyKQ0KY2F0KHNwcmludGYoIkdlb21ldHJpYyBtZWFuIGdyb3d0aCByYXRlOiAlLjRmJSVcbiIsIHJlc3VsdHNfR00kZ19iYXIpKQ0KYGBgDQoNCmBgYHtyfQ0KIyAoYykgYXJpdGhtZXRpYyBtZWFuIG9mIGdyb3d0aCBmYWN0b3JzIHJfdA0KDQojIGFyaXRobWV0aWMgbWVhbiBvZiByX3QNCkFNIDwtIGFyaXRoX21lYW4ocmVzdWx0c19HTSRyKQ0KDQojIGNvbnZlcnQgaW50byBwZXJjZW50YWdlIGdyb3d0aA0KZ19iYXJfQU0gPC0gKEFNLTEpKjEwMA0KY2F0KHNwcmludGYoIkFyaXRobWV0aWMgbWVhbiBncm93dGggcmF0ZTogJS40ZiUlXG4iLCBnX2Jhcl9BTSkpDQpgYGANCg0KYGBge3J9DQojIChkKSBwcmVkaWN0IFlfYmFyXzE5NjAgYW5kIGNvbXBhcmUgd2l0aCB0aGUgYWN0dWFsIHZhbHVlDQoNCiMgZXh0cmFjdCBmcm9tIFlfYmFyDQpZXzE5NDkgPC0gWV9iYXJbIjE5NDkiXQ0KWV8xOTYwIDwtIFlfYmFyWyIxOTYwIl0NCg0KIyBwcmVkaWN0aW9uIHVzaW5nIGdlb21ldHJpYyBtZWFuIGdyb3d0aCByYXRlDQpZX2hhdF9HTSA8LSBZXzE5NDkqKDErKHJlc3VsdHNfR00kZ19iYXIvMTAwKSleMTENCg0KIyBwcmVkaWN0aW9uIHVzaW5nIGFyaXRobWV0aWMgbWVhbiBncm93dGggcmF0ZQ0KWV9oYXRfQU0gPC0gWV8xOTQ5KigxKyhnX2Jhcl9BTS8xMDApKV4xMQ0KDQojIGFic29sdXRlIHByZWRpY3Rpb24gZXJyb3IgZm9yIGVhY2ggfFlfaGF0XzE5NjAgLSBZX2Jhcl8xOTYwfA0KZXJyX0dNIDwtIGFicyhZX2hhdF9HTS1ZXzE5NjApDQplcnJfQU0gPC0gYWJzKFlfaGF0X0FNLVlfMTk2MCkNCg0Kew0KICBjYXQoc3ByaW50ZigiWV9oYXRfR00gKGdlb21ldHJpYykgOiAlMTAuM2ZcbiIsIFlfaGF0X0dNKSkNCiAgY2F0KHNwcmludGYoIllfaGF0X0FNIChhcml0aG1ldGljKTogJTEwLjNmXG4iLCBZX2hhdF9BTSkpDQogIGNhdCgiXG4iKQ0KICBjYXQoc3ByaW50ZigiQWJzb2x1dGUgZXJyb3IgR00gICAgOiAlMTAuM2ZcbiIsIGVycl9HTSkpDQogIGNhdChzcHJpbnRmKCJBYnNvbHV0ZSBlcnJvciBBTSAgICA6ICUxMC4zZlxuIiwgZXJyX0FNKSkNCn0NCmBgYA0KDQojIyMgUXVlc3Rpb24gMiDigJMgRGF0YXNldDogYWlycXVhbGl0eQ0KDQpgYGB7cn0NCmRhdGEgPC0gbmEub21pdChhaXJxdWFsaXR5WywgYygiT3pvbmUiLCAiU29sYXIuUiIsICJXaW5kIiwgIlRlbXAiKV0pDQoNCiMgKGEpIG1hdF9tdWx0KCkgbWFudWFsDQptYXRfbXVsdCA8LSBmdW5jdGlvbihBLEIpew0KICBtIDwtIG5yb3coQSkNCiAgbiA8LSBuY29sKEEpDQogIHAgPC0gbmNvbChCKQ0KICBDIDwtIG1hdHJpeCgwLG5yb3c9bSxuY29sPXApDQogIA0KICBmb3IoaSBpbiAxOm0pew0KICAgIGZvcihqIGluIDE6cCl7DQogICAgICB2YWwgPC0gMA0KICAgICAgZm9yKGsgaW4gMTpuKXsNCiAgICAgICAgdmFsIDwtIHZhbCtBW2ksa10qQltrLGpdDQogICAgICB9DQogICAgICBDW2ksal0gPC0gdmFsDQogICAgfQ0KICB9DQogIHJldHVybihDKQ0KfQ0KDQojIHZhbGlkYXRpb24NCmEgPC0gbWF0cml4KGMoMSwgMiwgMywgNCksIG5yb3cgPSAyKQ0KYiA8LSBtYXRyaXgoYyg1LCA2LCA3LCA4KSwgbnJvdyA9IDIpDQoNCmNfc3RkICAgIDwtIGEgJSolIGINCmNfbWFudWFsIDwtIG1hdF9tdWx0KGEsIGIpDQoNCnsNCiAgY2F0KCJTdGFuZGFyZCByZXN1bHQgKGEgJSolIGIpOlxuIikNCiAgcHJpbnQoY19zdGQpDQogIGNhdCgiXG5NYW51YWwgcmVzdWx0IG1hdF9tdWx0KGEsIGIpOlxuIikNCiAgcHJpbnQoY19tYW51YWwpDQogIGNhdCgiXG5FbGVtZW50LXdpc2UgbWF0Y2g6XG4iKQ0KICBwcmludChjX3N0ZCA9PSBjX21hbnVhbCkNCn0NCmBgYA0KDQpgYGB7cn0NCiMgKGIpIGNvcnJfbWF0cml4KCkNCmNvcnJfbWF0cml4IDwtIGZ1bmN0aW9uKFgpew0KICBYIDwtIGFzLm1hdHJpeChYKQ0KICBuIDwtIG5yb3coWCkNCiAgcCA8LSBuY29sKFgpDQogIA0KICAjIChpKSBjb2x1bW4gbWVhbiB2ZWN0b3IgWF9iYXINCiAgb25lcyA8LSBtYXRyaXgoMSxucm93PW4sbmNvbD0xKQ0KICBYX2JhciA8LSAoMS9uKSptYXRfbXVsdCh0KFgpLG9uZXMpDQogIA0KICAjIChpaSkgY2VudGVyZWQgbWF0cml4IFhfYyBhbmQgY292YXJpYW5jZSBtYXRyaXggUw0KICBYX2MgPC0gWC1tYXRfbXVsdChvbmVzLHQoWF9iYXIpKQ0KICBTIDwtICgxLyhuLTEpKSptYXRfbXVsdCh0KFhfYyksWF9jKQ0KICANCiAgIyAoaWlpKSBEXnstMS8yfSBhbmQgY29ycmVsYXRpb24gbWF0cml4IFINCiAgRF9pbnZfaGFsZiA8LSBkaWFnKDEvc3FydChkaWFnKFMpKSkNCiAgDQogICMgUmV0dXJuIFINCiAgUiA8LSBtYXRfbXVsdChtYXRfbXVsdChEX2ludl9oYWxmLFMpLERfaW52X2hhbGYpDQogIHJvd25hbWVzKFIpIDwtIGNvbG5hbWVzKFgpDQogIGNvbG5hbWVzKFIpIDwtIGNvbG5hbWVzKFgpDQogIHJldHVybihSKQ0KfQ0KDQojIGFwcGx5IHRvIGFpciBxdWFsaXR5IGRhdGEgYW5kIGRpc3BsYXkNClJfaGF0IDwtIGNvcnJfbWF0cml4KGRhdGEpDQpwcmludChyb3VuZChSX2hhdCwgNikpDQoNCiMgdmFsaWRhdGlvbg0KY2F0KCJcbkVsZW1lbnQtd2lzZSBtYXRjaCB3aXRoIGNvcigpOlxuXG4iKQ0KcHJpbnQocm91bmQoUl9oYXQsIDEwKSA9PSByb3VuZChjb3IoZGF0YSksIDEwKSkNCmBgYA0KDQpgYGB7cn0NCiMgKGMpIGNvcnJfdGVzdF9tYXRyaXgoKSB2aWEgdHJhcGV6b2lkYWwgaW50ZWdyYXRpb24NCmNvcnJfdGVzdF9tYXRyaXggPC0gZnVuY3Rpb24oWCxhbHBoYT0wLjA1KXsNCiAgWCA8LSBhcy5tYXRyaXgoWCkNCiAgbiA8LSBucm93KFgpDQogIHAgPC0gbmNvbChYKQ0KICBkZiA8LSBuLTINCiAgTiAgPC0gMTAwMDANCiAgDQogICMgY29ycmVsYXRpb24gbWF0cml4IFINCiAgUiA8LSBjb3JyX21hdHJpeChYKQ0KICANCiAgIyBpbml0aWFsaXNlIHAtdmFsdWUgbWF0cml4DQogIFAgPC0gbWF0cml4KDAsbnJvdz1wLG5jb2w9cCkNCiAgcm93bmFtZXMoUCkgPC0gY29sbmFtZXMoWCkNCiAgY29sbmFtZXMoUCkgPC0gY29sbmFtZXMoWCkNCiAgDQogICMgcC12YWx1ZXMgZm9yIGVhY2ggb2ZmLWRpYWdvbmFsIHBhaXINCiAgZm9yKGkgaW4gMTpwKXsNCiAgICBmb3IoaiBpbiAxOnApew0KICAgICAgaWYoaT09ail7DQogICAgICAgIA0KICAgICAgICAjIHNldCBkaWFnb25hbCBwLXZhbHVlIHRvIDANCiAgICAgICAgUFtpLCBqXSA8LSAwDQogICAgICAgIA0KICAgICAgfSBlbHNlIHsNCiAgICAgICAgDQogICAgICAgIHJfaWogPC0gUltpLGpdDQogICAgICAgIA0KICAgICAgICAjIChpKSB0ZXN0IHN0YXRpc3RpYyB0X2lqDQogICAgICAgIHRfaWogPC0gcl9paipzcXJ0KG4tMikvc3FydCgxLXJfaWpeMikNCiAgICAgICAgDQogICAgICAgICMgKGlpKSB0cmFwZXpvaWRhbCBpbnRlZ3JhdGlvbiBvZiBkdCh0LCBkZikgZnJvbSAwIHRvIHx0X2lqfA0KICAgICAgICBhYnNfdCA8LSBhYnModF9paikNCiAgICAgICAgaCA8LSBhYnNfdC9ODQogICAgICAgIHRvdGFsIDwtIGR0KDAsZGYpK2R0KGFic190LGRmKQ0KICAgICAgICBmb3IoayBpbiAxOihOLTEpKXsNCiAgICAgICAgICB0b3RhbCA8LSB0b3RhbCsyKmR0KGsqaCwgZGYpDQogICAgICAgIH0NCiAgICAgICAgaW50ZWdyYWwgPC0gKGgvMikqdG90YWwNCiAgICAgICAgDQogICAgICAgICMgKGlpKSBwX2lqID0gMSAtIDIgKiBpbnRlZ3JhbA0KICAgICAgICBwX2lqIDwtIDEtMippbnRlZ3JhbA0KICAgICAgICANCiAgICAgICAgIyBzdG9yZSByZXN1bHQgaW4gUFtpLCBqXQ0KICAgICAgICBQW2ksal0gPC0gcF9pag0KICAgICAgfQ0KICAgIH0NCiAgfQ0KICByZXR1cm4obGlzdChSID0gUiwgUCA9IFApKQ0KfQ0KDQojIGFwcGx5IHRvIGFpciBxdWFsaXR5IGRhdGENCnJlc3VsdHMgPC0gY29ycl90ZXN0X21hdHJpeChkYXRhLCBhbHBoYSA9IDAuMDUpDQp7DQpjYXQoIj09PT09PT09PT0gQ29ycmVsYXRpb24gTWF0cml4IChSKSA9PT09PT09PT09XG4iKQ0KcHJpbnQocm91bmQocmVzdWx0cyRSLCA2KSkNCg0KY2F0KCJcbj09PT09PT09PT0gUC12YWx1ZSBNYXRyaXggKFApID09PT09PT09PT1cbiIpDQpwcmludChyb3VuZChyZXN1bHRzJFAsIDYpKQ0KfQ0KDQojIHZhbGlkYXRpb246IGNvbXBhcmUgUCBhZ2FpbnN0IGNvci50ZXN0KCkgcC12YWx1ZXMNCmNvcl9tYXQgPC0gbWF0cml4KDAsIG5jb2w9NCwgbnJvdz00KQ0KZm9yIChpIGluIDE6NCl7DQogIGZvciAoaiBpbiAxOjQpew0KICAgIGlmKGk9PWopew0KICAgICAgY29yX21hdFtpLGpdIDwtIDANCiAgICB9IGVsc2UgY29yX21hdFtpLGpdIDwtIGNvci50ZXN0KGRhdGFbLGldLCBkYXRhWyxqXSkkcC52YWx1ZQ0KICB9DQp9DQpyb3duYW1lcyhjb3JfbWF0KSA8LSBjb2xuYW1lcyhjb3JfbWF0KSA8LSBuYW1lcyhkYXRhKQ0KDQp7DQogIGNhdCgiXG5Db3JyZWxhdGlvbiBNYXRyaXhcbiIpDQogIHByaW50KGNvcihkYXRhKSkNCiAgY2F0KCJcbiIpDQogIGNhdCgiUC12YWx1ZSBtYXRyaXhcbiIpDQogIHByaW50KGNvcl9tYXQpDQp9DQoNCiMgdmVyaWZ5IGFuc3dlcg0Kcm91bmQocmVzdWx0cyRQLDEwKSA9PSByb3VuZChjb3JfbWF0LDEwKSANCmBgYA0K