[3.4]

Да се покаже дека \((\boldsymbol{x}-\bar{x}\boldsymbol{j})'(\boldsymbol{y}-\bar{y}\boldsymbol{j})=\sum_i (x_i-\bar{x})(y_i-\bar{y})\)

\[ (\boldsymbol{x}-\bar{x}\boldsymbol{j})'(\boldsymbol{y}-\bar{y}\boldsymbol{j})= \begin{pmatrix}x_1-\bar{x} & \dots & x_n-\bar{x}\end{pmatrix} \begin{pmatrix}y_1-\bar{y} \\ \vdots \\ y_n-\bar{y}\end{pmatrix}= \sum_i (x_i-\bar{x})(y_i-\bar{y}) \]

[3.5]

Да се покаже дека (за 3 димензии, мада решението е исто за колку и да е димензии):

\[ \frac{1}{n-1}\sum_{i=1}^{n}(\boldsymbol{y}_i-\bar{\boldsymbol{y}})(\boldsymbol{y}_i-\bar{\boldsymbol{y}})'= \begin{pmatrix} s_{11} & s_{12} & s_{13} \\ s_{21} & s_{22} & s_{23} \\ s_{31} & s_{32} & s_{33} \end{pmatrix} \]

\[ \frac{1}{n-1}\sum_{i=1}^{n}(\boldsymbol{y}_i-\bar{\boldsymbol{y}})(\boldsymbol{y}_i-\bar{\boldsymbol{y}})'=\frac{1}{n-1}\sum_{i=1}^{n}\boldsymbol{a}_i\boldsymbol{a}_i'\\ \boldsymbol{a}_{i}=\begin{pmatrix} \boldsymbol{y}_{i1}-\bar{\boldsymbol{y}}_1\\ \dots \\ \boldsymbol{y}_{in}-\bar{\boldsymbol{y}}_n \end{pmatrix} \\ \boldsymbol{a}_{i}\boldsymbol{a}_{i}'=\begin{pmatrix} (\boldsymbol{y}_{i1}-\bar{\boldsymbol{y}}_1)^2 & \dots & (\boldsymbol{y}_{i1}-\bar{\boldsymbol{y}}_1)(\boldsymbol{y}_{in}-\bar{\boldsymbol{y}}_n)\\ \vdots & \ddots & \vdots\\ (\boldsymbol{y}_{in}-\bar{\boldsymbol{y}}_n)(\boldsymbol{y}_{i1}-\bar{\boldsymbol{y}}_1) & \dots & (\boldsymbol{y}_{in}-\bar{\boldsymbol{y}}_n)^2 \end{pmatrix}\\ \frac{1}{n-1}\sum_{i=1}^{n}(\boldsymbol{y}_i-\bar{\boldsymbol{y}})(\boldsymbol{y}_i-\bar{\boldsymbol{y}})'=\frac{1}{n-1}\sum_{i=1}^{n}\boldsymbol{a}_i\boldsymbol{a}_i'=\\ \begin{pmatrix} \frac{\sum_{i=1}^n(\boldsymbol{y}_{i1}-\bar{\boldsymbol{y}}_1)^2}{n-1} & \dots & \frac{\sum_{i=1}^n(\boldsymbol{y}_{i1}-\bar{\boldsymbol{y}}_1)(\boldsymbol{y}_{in}-\bar{\boldsymbol{y}}_n)}{n-1}\\ \vdots & \ddots & \vdots\\ \frac{\sum_{i=1}^n(\boldsymbol{y}_{in}-\bar{\boldsymbol{y}}_n)(\boldsymbol{y}_{in}-\bar{\boldsymbol{y}}_n)}{n-1} & \dots & \frac{\sum_{i=1}^n(\boldsymbol{y}_{in}-\bar{\boldsymbol{y}}_n)^2}{n-1} \end{pmatrix}=\\ \begin{pmatrix} s_{11} & \dots & s_{1n} \\ \vdots & \ddots & \vdots \\ s_{n1} & \dots & s_{nn} \end{pmatrix} \]

[3.8]

Да се покаже дека \(tr(\boldsymbol{A}\boldsymbol{S}\boldsymbol{A}')=\sum_{i=1}^k\boldsymbol{a}'_i\boldsymbol{S}\boldsymbol{a}_i\)

\[ \boldsymbol{A}\boldsymbol{S}\boldsymbol{A}'=\begin{pmatrix} \boldsymbol{a}_1\boldsymbol{S}\boldsymbol{a}'_1 & \dots & \boldsymbol{a}_1\boldsymbol{S}\boldsymbol{a}'_k\\ \vdots & \ddots & \vdots\\ \boldsymbol{a}_k\boldsymbol{S}\boldsymbol{a}'_1 & \dots & \boldsymbol{a}_k\boldsymbol{S}\boldsymbol{a}'_k \end{pmatrix}\implies tr(\boldsymbol{A}\boldsymbol{S}\boldsymbol{A}')=\sum_{i=1}^k\boldsymbol{a}'_i\boldsymbol{S}\boldsymbol{a}_i \]

[3.18]

Податоци:

data = c(
  191, 155, 179, 145,
  195, 149, 201, 152,
  181, 148, 185, 149,
  183, 153, 188, 149,
  176, 144, 171, 142,
  208, 157, 192, 152,
  189, 150, 190, 149,
  197, 159, 189, 152,
  188, 152, 197, 159,
  192, 150, 187, 151,
  179, 158, 186, 148,
  183, 147, 174, 147,
  174, 150, 185, 152,
  190, 159, 195, 157,
  188, 151, 187, 158,
  163, 137, 161, 130,
  195, 155, 183, 158,
  186, 153, 173, 148,
  181, 145, 182, 146,
  175, 140, 165, 137,
  192, 154, 185, 152,
  174, 143, 178, 147,
  176, 139, 176, 143,
  197, 167, 200, 158,
  190, 163, 187, 150
)
y1 = data[seq(1, length(data), 4)]
y2 = data[seq(2, length(data), 4)]
x1 = data[seq(3, length(data), 4)]
x2 = data[seq(4, length(data), 4)]
data.frame(y1, y2, x1, x2)

(a)

Да се најде \(\bar{\boldsymbol{y}}\)

custom_sum <- function(x) {
  s = 0;
  for (k in 1:length(x)) {
    s = s + x[k];
  }
  return(s);
}

custom_mean <- function(x) {
  return(custom_sum(x) / length(x))
}

y1_mean = custom_mean(y1)
y2_mean = custom_mean(y2)
y_mean = c(y1_mean, y2_mean)
y_mean
[1] 185.72 151.12

Да се најде \(\boldsymbol{S}\)

custom_cov <- function(x, y) {
  n = length(x)
  mean_x = custom_mean(x);
  mean_y = custom_mean(y);
  prod_xy = 0;
  for (k in 1:n) {
    prod_xy = prod_xy + x[k] * y[k];
  }
  return((prod_xy - n * mean_x * mean_y) / (n - 1));
}

vars = list(x1, x2, y1, y2)
S = matrix(rep(0, 16), nrow=4, ncol=4)
for (k in 1:4) {
  for (i in 1:4) {
    S[k, i] = custom_cov(vars[[k]], vars[[i]])
  }
}
S
          [,1]     [,2]     [,3]     [,4]
[1,] 100.80667 56.54000 69.66167 51.31167
[2,]  56.54000 45.02333 46.11167 35.05333
[3,]  69.66167 46.11167 95.29333 52.86833
[4,]  51.31167 35.05333 52.86833 54.36000

Да се најде \(\boldsymbol{R}\)

R = matrix(rep(0, 16), nrow=4, ncol=4)
for (k in 1:4) {
  for (i in 1:4) {
    R[k, i] = S[k, i] / sqrt(S[k, k] * S[i, i])
  }
}
R
          [,1]      [,2]      [,3]      [,4]
[1,] 1.0000000 0.8392519 0.7107518 0.6931573
[2,] 0.8392519 1.0000000 0.7039807 0.7085504
[3,] 0.7107518 0.7039807 1.0000000 0.7345555
[4,] 0.6931573 0.7085504 0.7345555 1.0000000

(b)

Да се најде \(|\boldsymbol{S}|\)

custom_determinant_2_2 <- function(x) {
  return(x[1, 1] * x[2, 2] - x[1, 2] * x[2, 1])
}

custom_determinant <- function(x) {
  n = sqrt(length(x))
  if (n == 2) {
    return(custom_determinant_2_2(x))
  }
  res = 0
  rows = 2:n
  for (k in 1:n) {
    cols_l = c()
    cols_r = c()
    if (k > 1) {
      cols_l = 1:(k - 1)
    }
    if (k < n) {
      cols_r = (k + 1):n
    }
    sub_res = custom_determinant(x[rows, c(cols_l, cols_r)])
    if (k %% 2 == 1) {
      res = res + x[1, k] * sub_res
    } else {
      res = res - x[1, k] * sub_res
    }
  }
  return(res)
}

custom_determinant(S)
[1] 1207109

Да се најде \(tr(\boldsymbol{S})\)

custom_tr <- function(x) {
  s = 0
  n = sqrt(length(x))
  for (k in 1:n) {
    s = s + x[k, k]
  }
  return(s)
}

custom_tr(S)
[1] 295.4833

[3.20]

Податоците од табелата 3.6 се:

data = c(
  1, 47.8, 48.8, 49.0, 49.7,
  2, 46.4, 47.3, 47.7, 48.4,
  3, 46.3, 46.8, 47.8, 48.5,
  4, 45.1, 45.3, 46.1, 47.2,
  5, 47.6, 48.5, 48.9, 49.3,
  6, 52.5, 53.2, 53.3, 53.7,
  7, 51.2, 53.0, 54.3, 54.5,
  8, 49.8, 50.0, 50.3, 52.7,
  9, 48.1, 50.8, 52.3, 54.4,
  10, 45.0, 47.0, 47.3, 48.3,
  11, 51.2, 51.4, 51.6, 51.9,
  12, 48.5, 49.2, 53.0, 55.5,
  13, 52.1, 52.8, 53.7, 55.0,
  14, 48.2, 48.9, 49.3, 49.8,
  15, 49.6, 50.4, 51.2, 51.8,
  16, 50.7, 51.7, 52.7, 53.3,
  17, 47.2, 47.7, 48.4, 49.5,
  18, 53.3, 54.6, 55.1, 55.3,
  19, 46.2, 47.5, 48.1, 48.4,
  20, 46.3, 47.6, 51.3, 51.8
)
y1 = data[seq(2, length(data), 5)]
y2 = data[seq(3, length(data), 5)]
y3 = data[seq(4, length(data), 5)]
y4 = data[seq(5, length(data), 5)]
data.frame(y1, y2, y3, y4)

Новите податоци се:

z1 = 2 * y1 + 3 * y2 - y3 + 4 * y4
z2 = -2 * y1 - y2 + 4 * y3 - 2 * y4
z3 = 3 * y1 - 2 * y2 - y3 + 3 * y4
data.frame(z1, z2, z3)

Матрицата \(\boldsymbol{A}\) со која се помножени \(\boldsymbol{y}\)-ците е:

A = matrix(
  data=c(
    2, 3, -1, 4,
    -2, -1, 4, -2,
    3, -2, -1, 3
  ), 
  nrow=3, 
  ncol=4, 
  byrow=T
)
A
     [,1] [,2] [,3] [,4]
[1,]    2    3   -1    4
[2,]   -2   -1    4   -2
[3,]    3   -2   -1    3

Да се најде \(\bar{\boldsymbol{z}}\)

vars = list(y1, y2, y3, y4)
y_mean = rep(0, 4)
for (k in 1:4) {
  y_mean[k] = custom_mean(vars[[k]])
}
z_mean = A %*% y_mean
z_mean
        [,1]
[1,] 401.415
[2,] -47.555
[3,] 150.495

Да се најде \(\boldsymbol{S}_z\)

S = matrix(rep(0, 16), nrow=4, ncol=4)
for (k in 1:4) {
  for (i in 1:4) {
    S[k, i] = custom_cov(vars[[k]], vars[[i]])
  }
}
S_z = A %*% S %*% t(A)
S_z
          [,1]      [,2]      [,3]
[1,] 399.32029 -44.58439 148.85166
[2,] -44.58439  12.35103 -16.95450
[3,] 148.85166 -16.95450  59.65839

Да се најде \(\boldsymbol{R}_z\)

D_z = matrix(rep(0, 9), nrow=3, ncol=3)
for (k in 1:3) {
  D_z[k, k] = sqrt(S_z[k, k])
}
D_z_inv = solve(D_z)
R_z = D_z_inv %*% S_z %*% D_z_inv
R_z
           [,1]       [,2]       [,3]
[1,]  1.0000000 -0.6348493  0.9644000
[2,] -0.6348493  1.0000000 -0.6245938
[3,]  0.9644000 -0.6245938  1.0000000
LS0tDQp0aXRsZTogItCT0LvQsNCy0LAgMzogQ2hhcmFjdGVyaXppbmcgYW5kIERpc3BsYXlpbmcgTXVsdGl2YXJpYXRlIERhdGEiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQojIFszLjRdDQoNCtCU0LAg0YHQtSDQv9C+0LrQsNC20LUg0LTQtdC60LAgJChcYm9sZHN5bWJvbHt4fS1cYmFye3h9XGJvbGRzeW1ib2x7an0pJyhcYm9sZHN5bWJvbHt5fS1cYmFye3l9XGJvbGRzeW1ib2x7an0pPVxzdW1faSAoeF9pLVxiYXJ7eH0pKHlfaS1cYmFye3l9KSQNCg0KJCQNCihcYm9sZHN5bWJvbHt4fS1cYmFye3h9XGJvbGRzeW1ib2x7an0pJyhcYm9sZHN5bWJvbHt5fS1cYmFye3l9XGJvbGRzeW1ib2x7an0pPQ0KXGJlZ2lue3BtYXRyaXh9eF8xLVxiYXJ7eH0gJiBcZG90cyAmIHhfbi1cYmFye3h9XGVuZHtwbWF0cml4fQ0KXGJlZ2lue3BtYXRyaXh9eV8xLVxiYXJ7eX0gXFwgXHZkb3RzIFxcIHlfbi1cYmFye3l9XGVuZHtwbWF0cml4fT0NClxzdW1faSAoeF9pLVxiYXJ7eH0pKHlfaS1cYmFye3l9KQ0KJCQNCg0KIyBbMy41XQ0KDQrQlNCwINGB0LUg0L/QvtC60LDQttC1INC00LXQutCwICjQt9CwIDMg0LTQuNC80LXQvdC30LjQuCwg0LzQsNC00LAg0YDQtdGI0LXQvdC40LXRgtC+INC1INC40YHRgtC+INC30LAg0LrQvtC70LrRgyDQuCDQtNCwINC1INC00LjQvNC10L3Qt9C40LgpOg0KDQokJA0KXGZyYWN7MX17bi0xfVxzdW1fe2k9MX1ee259KFxib2xkc3ltYm9se3l9X2ktXGJhcntcYm9sZHN5bWJvbHt5fX0pKFxib2xkc3ltYm9se3l9X2ktXGJhcntcYm9sZHN5bWJvbHt5fX0pJz0NClxiZWdpbntwbWF0cml4fQ0Kc197MTF9ICYgc197MTJ9ICYgc197MTN9IFxcDQpzX3syMX0gJiBzX3syMn0gJiBzX3syM30gXFwNCnNfezMxfSAmIHNfezMyfSAmIHNfezMzfQ0KXGVuZHtwbWF0cml4fQ0KJCQNCg0KJCQNClxmcmFjezF9e24tMX1cc3VtX3tpPTF9XntufShcYm9sZHN5bWJvbHt5fV9pLVxiYXJ7XGJvbGRzeW1ib2x7eX19KShcYm9sZHN5bWJvbHt5fV9pLVxiYXJ7XGJvbGRzeW1ib2x7eX19KSc9XGZyYWN7MX17bi0xfVxzdW1fe2k9MX1ee259XGJvbGRzeW1ib2x7YX1faVxib2xkc3ltYm9se2F9X2knXFwNClxib2xkc3ltYm9se2F9X3tpfT1cYmVnaW57cG1hdHJpeH0NClxib2xkc3ltYm9se3l9X3tpMX0tXGJhcntcYm9sZHN5bWJvbHt5fX1fMVxcIFxkb3RzIFxcIFxib2xkc3ltYm9se3l9X3tpbn0tXGJhcntcYm9sZHN5bWJvbHt5fX1fbg0KXGVuZHtwbWF0cml4fSBcXA0KXGJvbGRzeW1ib2x7YX1fe2l9XGJvbGRzeW1ib2x7YX1fe2l9Jz1cYmVnaW57cG1hdHJpeH0NCihcYm9sZHN5bWJvbHt5fV97aTF9LVxiYXJ7XGJvbGRzeW1ib2x7eX19XzEpXjIgJiBcZG90cyAmIChcYm9sZHN5bWJvbHt5fV97aTF9LVxiYXJ7XGJvbGRzeW1ib2x7eX19XzEpKFxib2xkc3ltYm9se3l9X3tpbn0tXGJhcntcYm9sZHN5bWJvbHt5fX1fbilcXA0KXHZkb3RzICYgXGRkb3RzICYgXHZkb3RzXFwNCihcYm9sZHN5bWJvbHt5fV97aW59LVxiYXJ7XGJvbGRzeW1ib2x7eX19X24pKFxib2xkc3ltYm9se3l9X3tpMX0tXGJhcntcYm9sZHN5bWJvbHt5fX1fMSkgJiBcZG90cyAmIChcYm9sZHN5bWJvbHt5fV97aW59LVxiYXJ7XGJvbGRzeW1ib2x7eX19X24pXjINClxlbmR7cG1hdHJpeH1cXA0KXGZyYWN7MX17bi0xfVxzdW1fe2k9MX1ee259KFxib2xkc3ltYm9se3l9X2ktXGJhcntcYm9sZHN5bWJvbHt5fX0pKFxib2xkc3ltYm9se3l9X2ktXGJhcntcYm9sZHN5bWJvbHt5fX0pJz1cZnJhY3sxfXtuLTF9XHN1bV97aT0xfV57bn1cYm9sZHN5bWJvbHthfV9pXGJvbGRzeW1ib2x7YX1faSc9XFwNClxiZWdpbntwbWF0cml4fQ0KXGZyYWN7XHN1bV97aT0xfV5uKFxib2xkc3ltYm9se3l9X3tpMX0tXGJhcntcYm9sZHN5bWJvbHt5fX1fMSleMn17bi0xfSAmIFxkb3RzICYgXGZyYWN7XHN1bV97aT0xfV5uKFxib2xkc3ltYm9se3l9X3tpMX0tXGJhcntcYm9sZHN5bWJvbHt5fX1fMSkoXGJvbGRzeW1ib2x7eX1fe2lufS1cYmFye1xib2xkc3ltYm9se3l9fV9uKX17bi0xfVxcDQpcdmRvdHMgJiBcZGRvdHMgJiBcdmRvdHNcXA0KXGZyYWN7XHN1bV97aT0xfV5uKFxib2xkc3ltYm9se3l9X3tpbn0tXGJhcntcYm9sZHN5bWJvbHt5fX1fbikoXGJvbGRzeW1ib2x7eX1fe2lufS1cYmFye1xib2xkc3ltYm9se3l9fV9uKX17bi0xfSAmIFxkb3RzICYgXGZyYWN7XHN1bV97aT0xfV5uKFxib2xkc3ltYm9se3l9X3tpbn0tXGJhcntcYm9sZHN5bWJvbHt5fX1fbileMn17bi0xfQ0KXGVuZHtwbWF0cml4fT1cXA0KXGJlZ2lue3BtYXRyaXh9DQpzX3sxMX0gJiBcZG90cyAmIHNfezFufSBcXA0KXHZkb3RzICYgXGRkb3RzICYgXHZkb3RzIFxcDQpzX3tuMX0gJiBcZG90cyAmIHNfe25ufQ0KXGVuZHtwbWF0cml4fQ0KJCQNCg0KIyBbMy44XQ0KDQrQlNCwINGB0LUg0L/QvtC60LDQttC1INC00LXQutCwICR0cihcYm9sZHN5bWJvbHtBfVxib2xkc3ltYm9se1N9XGJvbGRzeW1ib2x7QX0nKT1cc3VtX3tpPTF9XmtcYm9sZHN5bWJvbHthfSdfaVxib2xkc3ltYm9se1N9XGJvbGRzeW1ib2x7YX1faSQNCg0KJCQNClxib2xkc3ltYm9se0F9XGJvbGRzeW1ib2x7U31cYm9sZHN5bWJvbHtBfSc9XGJlZ2lue3BtYXRyaXh9DQpcYm9sZHN5bWJvbHthfV8xXGJvbGRzeW1ib2x7U31cYm9sZHN5bWJvbHthfSdfMSAmIFxkb3RzICYgXGJvbGRzeW1ib2x7YX1fMVxib2xkc3ltYm9se1N9XGJvbGRzeW1ib2x7YX0nX2tcXA0KXHZkb3RzICYgXGRkb3RzICYgXHZkb3RzXFwNClxib2xkc3ltYm9se2F9X2tcYm9sZHN5bWJvbHtTfVxib2xkc3ltYm9se2F9J18xICYgXGRvdHMgJiBcYm9sZHN5bWJvbHthfV9rXGJvbGRzeW1ib2x7U31cYm9sZHN5bWJvbHthfSdfaw0KXGVuZHtwbWF0cml4fVxpbXBsaWVzIHRyKFxib2xkc3ltYm9se0F9XGJvbGRzeW1ib2x7U31cYm9sZHN5bWJvbHtBfScpPVxzdW1fe2k9MX1ea1xib2xkc3ltYm9se2F9J19pXGJvbGRzeW1ib2x7U31cYm9sZHN5bWJvbHthfV9pDQokJA0KDQojIFszLjE4XQ0KDQrQn9C+0LTQsNGC0L7RhtC4Og0KDQpgYGB7cn0NCmRhdGEgPSBjKA0KICAxOTEsIDE1NSwgMTc5LCAxNDUsDQogIDE5NSwgMTQ5LCAyMDEsIDE1MiwNCiAgMTgxLCAxNDgsIDE4NSwgMTQ5LA0KICAxODMsIDE1MywgMTg4LCAxNDksDQogIDE3NiwgMTQ0LCAxNzEsIDE0MiwNCiAgMjA4LCAxNTcsIDE5MiwgMTUyLA0KICAxODksIDE1MCwgMTkwLCAxNDksDQogIDE5NywgMTU5LCAxODksIDE1MiwNCiAgMTg4LCAxNTIsIDE5NywgMTU5LA0KICAxOTIsIDE1MCwgMTg3LCAxNTEsDQogIDE3OSwgMTU4LCAxODYsIDE0OCwNCiAgMTgzLCAxNDcsIDE3NCwgMTQ3LA0KICAxNzQsIDE1MCwgMTg1LCAxNTIsDQogIDE5MCwgMTU5LCAxOTUsIDE1NywNCiAgMTg4LCAxNTEsIDE4NywgMTU4LA0KICAxNjMsIDEzNywgMTYxLCAxMzAsDQogIDE5NSwgMTU1LCAxODMsIDE1OCwNCiAgMTg2LCAxNTMsIDE3MywgMTQ4LA0KICAxODEsIDE0NSwgMTgyLCAxNDYsDQogIDE3NSwgMTQwLCAxNjUsIDEzNywNCiAgMTkyLCAxNTQsIDE4NSwgMTUyLA0KICAxNzQsIDE0MywgMTc4LCAxNDcsDQogIDE3NiwgMTM5LCAxNzYsIDE0MywNCiAgMTk3LCAxNjcsIDIwMCwgMTU4LA0KICAxOTAsIDE2MywgMTg3LCAxNTANCikNCnkxID0gZGF0YVtzZXEoMSwgbGVuZ3RoKGRhdGEpLCA0KV0NCnkyID0gZGF0YVtzZXEoMiwgbGVuZ3RoKGRhdGEpLCA0KV0NCngxID0gZGF0YVtzZXEoMywgbGVuZ3RoKGRhdGEpLCA0KV0NCngyID0gZGF0YVtzZXEoNCwgbGVuZ3RoKGRhdGEpLCA0KV0NCmRhdGEuZnJhbWUoeTEsIHkyLCB4MSwgeDIpDQpgYGANCg0KIyMjIChhKQ0KDQrQlNCwINGB0LUg0L3QsNGY0LTQtSAkXGJhcntcYm9sZHN5bWJvbHt5fX0kDQoNCmBgYHtyfQ0KY3VzdG9tX3N1bSA8LSBmdW5jdGlvbih4KSB7DQogIHMgPSAwDQogIGZvciAoayBpbiAxOmxlbmd0aCh4KSkgew0KICAgIHMgPSBzICsgeFtrXQ0KICB9DQogIHJldHVybihzKQ0KfQ0KDQpjdXN0b21fbWVhbiA8LSBmdW5jdGlvbih4KSB7DQogIHJldHVybihjdXN0b21fc3VtKHgpIC8gbGVuZ3RoKHgpKQ0KfQ0KDQp5MV9tZWFuID0gY3VzdG9tX21lYW4oeTEpDQp5Ml9tZWFuID0gY3VzdG9tX21lYW4oeTIpDQp5X21lYW4gPSBjKHkxX21lYW4sIHkyX21lYW4pDQp5X21lYW4NCmBgYA0KDQrQlNCwINGB0LUg0L3QsNGY0LTQtSAkXGJvbGRzeW1ib2x7U30kDQoNCmBgYHtyfQ0KY3VzdG9tX2NvdiA8LSBmdW5jdGlvbih4LCB5KSB7DQogIG4gPSBsZW5ndGgoeCkNCiAgbWVhbl94ID0gY3VzdG9tX21lYW4oeCk7DQogIG1lYW5feSA9IGN1c3RvbV9tZWFuKHkpOw0KICBwcm9kX3h5ID0gMDsNCiAgZm9yIChrIGluIDE6bikgew0KICAgIHByb2RfeHkgPSBwcm9kX3h5ICsgeFtrXSAqIHlba107DQogIH0NCiAgcmV0dXJuKChwcm9kX3h5IC0gbiAqIG1lYW5feCAqIG1lYW5feSkgLyAobiAtIDEpKTsNCn0NCg0KdmFycyA9IGxpc3QoeDEsIHgyLCB5MSwgeTIpDQpTID0gbWF0cml4KHJlcCgwLCAxNiksIG5yb3c9NCwgbmNvbD00KQ0KZm9yIChrIGluIDE6NCkgew0KICBmb3IgKGkgaW4gMTo0KSB7DQogICAgU1trLCBpXSA9IGN1c3RvbV9jb3YodmFyc1tba11dLCB2YXJzW1tpXV0pDQogIH0NCn0NClMNCmBgYA0KDQrQlNCwINGB0LUg0L3QsNGY0LTQtSAkXGJvbGRzeW1ib2x7Un0kDQoNCmBgYHtyfQ0KUiA9IG1hdHJpeChyZXAoMCwgMTYpLCBucm93PTQsIG5jb2w9NCkNCmZvciAoayBpbiAxOjQpIHsNCiAgZm9yIChpIGluIDE6NCkgew0KICAgIFJbaywgaV0gPSBTW2ssIGldIC8gc3FydChTW2ssIGtdICogU1tpLCBpXSkNCiAgfQ0KfQ0KUg0KYGBgDQoNCiMjIyAoYikNCg0K0JTQsCDRgdC1INC90LDRmNC00LUgJHxcYm9sZHN5bWJvbHtTfXwkDQoNCmBgYHtyfQ0KY3VzdG9tX2RldGVybWluYW50XzJfMiA8LSBmdW5jdGlvbih4KSB7DQogIHJldHVybih4WzEsIDFdICogeFsyLCAyXSAtIHhbMSwgMl0gKiB4WzIsIDFdKQ0KfQ0KDQpjdXN0b21fZGV0ZXJtaW5hbnQgPC0gZnVuY3Rpb24oeCkgew0KICBuID0gc3FydChsZW5ndGgoeCkpDQogIGlmIChuID09IDIpIHsNCiAgICByZXR1cm4oY3VzdG9tX2RldGVybWluYW50XzJfMih4KSkNCiAgfQ0KICByZXMgPSAwDQogIHJvd3MgPSAyOm4NCiAgZm9yIChrIGluIDE6bikgew0KICAgIGNvbHNfbCA9IGMoKQ0KICAgIGNvbHNfciA9IGMoKQ0KICAgIGlmIChrID4gMSkgew0KICAgICAgY29sc19sID0gMTooayAtIDEpDQogICAgfQ0KICAgIGlmIChrIDwgbikgew0KICAgICAgY29sc19yID0gKGsgKyAxKTpuDQogICAgfQ0KICAgIHN1Yl9yZXMgPSBjdXN0b21fZGV0ZXJtaW5hbnQoeFtyb3dzLCBjKGNvbHNfbCwgY29sc19yKV0pDQogICAgaWYgKGsgJSUgMiA9PSAxKSB7DQogICAgICByZXMgPSByZXMgKyB4WzEsIGtdICogc3ViX3Jlcw0KICAgIH0gZWxzZSB7DQogICAgICByZXMgPSByZXMgLSB4WzEsIGtdICogc3ViX3Jlcw0KICAgIH0NCiAgfQ0KICByZXR1cm4ocmVzKQ0KfQ0KDQpjdXN0b21fZGV0ZXJtaW5hbnQoUykNCmBgYA0KDQrQlNCwINGB0LUg0L3QsNGY0LTQtSAkdHIoXGJvbGRzeW1ib2x7U30pJA0KDQpgYGB7cn0NCmN1c3RvbV90ciA8LSBmdW5jdGlvbih4KSB7DQogIHMgPSAwDQogIG4gPSBzcXJ0KGxlbmd0aCh4KSkNCiAgZm9yIChrIGluIDE6bikgew0KICAgIHMgPSBzICsgeFtrLCBrXQ0KICB9DQogIHJldHVybihzKQ0KfQ0KDQpjdXN0b21fdHIoUykNCmBgYA0KDQojIFszLjIwXQ0KDQrQn9C+0LTQsNGC0L7RhtC40YLQtSDQvtC0INGC0LDQsdC10LvQsNGC0LAgMy42INGB0LU6DQoNCmBgYHtyfQ0KZGF0YSA9IGMoDQogIDEsIDQ3LjgsIDQ4LjgsIDQ5LjAsIDQ5LjcsDQogIDIsIDQ2LjQsIDQ3LjMsIDQ3LjcsIDQ4LjQsDQogIDMsIDQ2LjMsIDQ2LjgsIDQ3LjgsIDQ4LjUsDQogIDQsIDQ1LjEsIDQ1LjMsIDQ2LjEsIDQ3LjIsDQogIDUsIDQ3LjYsIDQ4LjUsIDQ4LjksIDQ5LjMsDQogIDYsIDUyLjUsIDUzLjIsIDUzLjMsIDUzLjcsDQogIDcsIDUxLjIsIDUzLjAsIDU0LjMsIDU0LjUsDQogIDgsIDQ5LjgsIDUwLjAsIDUwLjMsIDUyLjcsDQogIDksIDQ4LjEsIDUwLjgsIDUyLjMsIDU0LjQsDQogIDEwLCA0NS4wLCA0Ny4wLCA0Ny4zLCA0OC4zLA0KICAxMSwgNTEuMiwgNTEuNCwgNTEuNiwgNTEuOSwNCiAgMTIsIDQ4LjUsIDQ5LjIsIDUzLjAsIDU1LjUsDQogIDEzLCA1Mi4xLCA1Mi44LCA1My43LCA1NS4wLA0KICAxNCwgNDguMiwgNDguOSwgNDkuMywgNDkuOCwNCiAgMTUsIDQ5LjYsIDUwLjQsIDUxLjIsIDUxLjgsDQogIDE2LCA1MC43LCA1MS43LCA1Mi43LCA1My4zLA0KICAxNywgNDcuMiwgNDcuNywgNDguNCwgNDkuNSwNCiAgMTgsIDUzLjMsIDU0LjYsIDU1LjEsIDU1LjMsDQogIDE5LCA0Ni4yLCA0Ny41LCA0OC4xLCA0OC40LA0KICAyMCwgNDYuMywgNDcuNiwgNTEuMywgNTEuOA0KKQ0KeTEgPSBkYXRhW3NlcSgyLCBsZW5ndGgoZGF0YSksIDUpXQ0KeTIgPSBkYXRhW3NlcSgzLCBsZW5ndGgoZGF0YSksIDUpXQ0KeTMgPSBkYXRhW3NlcSg0LCBsZW5ndGgoZGF0YSksIDUpXQ0KeTQgPSBkYXRhW3NlcSg1LCBsZW5ndGgoZGF0YSksIDUpXQ0KZGF0YS5mcmFtZSh5MSwgeTIsIHkzLCB5NCkNCmBgYA0KDQrQndC+0LLQuNGC0LUg0L/QvtC00LDRgtC+0YbQuCDRgdC1Og0KDQpgYGB7cn0NCnoxID0gMiAqIHkxICsgMyAqIHkyIC0geTMgKyA0ICogeTQNCnoyID0gLTIgKiB5MSAtIHkyICsgNCAqIHkzIC0gMiAqIHk0DQp6MyA9IDMgKiB5MSAtIDIgKiB5MiAtIHkzICsgMyAqIHk0DQpkYXRhLmZyYW1lKHoxLCB6MiwgejMpDQpgYGANCg0K0JzQsNGC0YDQuNGG0LDRgtCwICRcYm9sZHN5bWJvbHtBfSQg0YHQviDQutC+0ZjQsCDRgdC1INC/0L7QvNC90L7QttC10L3QuCAkXGJvbGRzeW1ib2x7eX0kLdGG0LjRgtC1INC1Og0KDQpgYGB7cn0NCkEgPSBtYXRyaXgoDQogIGRhdGE9YygNCiAgICAyLCAzLCAtMSwgNCwNCiAgICAtMiwgLTEsIDQsIC0yLA0KICAgIDMsIC0yLCAtMSwgMw0KICApLCANCiAgbnJvdz0zLCANCiAgbmNvbD00LCANCiAgYnlyb3c9VA0KKQ0KQQ0KYGBgDQoNCg0K0JTQsCDRgdC1INC90LDRmNC00LUgJFxiYXJ7XGJvbGRzeW1ib2x7en19JA0KDQpgYGB7cn0NCnZhcnMgPSBsaXN0KHkxLCB5MiwgeTMsIHk0KQ0KeV9tZWFuID0gcmVwKDAsIDQpDQpmb3IgKGsgaW4gMTo0KSB7DQogIHlfbWVhbltrXSA9IGN1c3RvbV9tZWFuKHZhcnNbW2tdXSkNCn0NCnpfbWVhbiA9IEEgJSolIHlfbWVhbg0Kel9tZWFuDQpgYGANCg0K0JTQsCDRgdC1INC90LDRmNC00LUgJFxib2xkc3ltYm9se1N9X3okDQoNCmBgYHtyfQ0KUyA9IG1hdHJpeChyZXAoMCwgMTYpLCBucm93PTQsIG5jb2w9NCkNCmZvciAoayBpbiAxOjQpIHsNCiAgZm9yIChpIGluIDE6NCkgew0KICAgIFNbaywgaV0gPSBjdXN0b21fY292KHZhcnNbW2tdXSwgdmFyc1tbaV1dKQ0KICB9DQp9DQpTX3ogPSBBICUqJSBTICUqJSB0KEEpDQpTX3oNCmBgYA0KDQrQlNCwINGB0LUg0L3QsNGY0LTQtSAkXGJvbGRzeW1ib2x7Un1feiQNCg0KYGBge3J9DQpEX3ogPSBtYXRyaXgocmVwKDAsIDkpLCBucm93PTMsIG5jb2w9MykNCmZvciAoayBpbiAxOjMpIHsNCiAgRF96W2ssIGtdID0gc3FydChTX3pbaywga10pDQp9DQpEX3pfaW52ID0gc29sdmUoRF96KQ0KUl96ID0gRF96X2ludiAlKiUgU196ICUqJSBEX3pfaW52DQpSX3oNCmBgYA0K