Name : Violetta Ammara Irianti Agung

Student ID : 5003251126

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