1. Multikolinearita – definícia
Uvažujme lineárny regresný model
\[
y_i = \beta_0 + \beta_1 x_{1i} + \cdots + \beta_k x_{ki} + u_i,
\]
alebo maticovo
\[
y = X\beta + u.
\]
Multikolinearita znamená, že niektoré vysvetľujúce premenné v matici
\(X\) sú silno lineárne závislé.
Dokonalá multikolinearita nastáva vtedy, keď existuje nenulový vektor
\(a\), pre ktorý
\[
Xa = 0.
\]
Vtedy matica \(X'X\) nie je
regulárna a OLS odhad
\[
\hat\beta = (X'X)^{-1}X'y
\]
neexistuje.
V praxi častejšie pozorujeme nedokonalú, ale silnú multikolinearitu.
Potom \(X'X\) je síce invertibilná,
ale zle podmienená. Odhady existujú, no môžu byť veľmi nepresné.
Simulované dáta
Vytvoríme hlavný dátový súbor data_main, ktorý budeme
používať v ďalších častiach.
Premenné:
y je závislá premenná,
x1, x2, x3 sú vysvetľujúce
premenné,
x2 je konštruovaná tak, aby bola silno korelovaná s
x1,
x3 je približne nezávislá od x1 a
x2.
n <- 200
x1 <- rnorm(n)
x2 <- 0.95 * x1 + rnorm(n, sd = 0.15)
x3 <- rnorm(n)
u <- rnorm(n)
y <- 1 + 2*x1 - 1.5*x2 + 0.8*x3 + u
data_main <- data.frame(y = y, x1 = x1, x2 = x2, x3 = x3)
head(data_main)
2.Dôsledky multikolinearity pre OLS odhad
Pri multikolinearite OLS odhad zostáva nestranný za štandardných
exogenitných predpokladov,
\[
E(u)=0,
\]
ale jeho rozptyl môže byť veľký:
\[
Var(\hat\beta)=\sigma^2(X'X)^{-1}.
\]
Ak sú stĺpce matice \(X\) takmer
lineárne závislé, niektoré prvky matice \((X'X)^{-1}\) sú veľké.
X <- cbind(1, x1, x2, x3)
colnames(X) <- c("intercept", "x1", "x2", "x3")
XtX <- t(X) %*% X
XtX_inv <- solve(XtX)
XtX_inv
intercept x1 x2 x3
intercept 0.0050154322 0.001439290 -0.001476833 -0.0001822219
x1 0.0014392904 0.207599270 -0.213616763 -0.0015627618
x2 -0.0014768332 -0.213616763 0.225963071 0.0018298489
x3 -0.0001822219 -0.001562762 0.001829849 0.0054181885
To vedie k veľkým štandardným chybám, nízkym t-štatistikám a
nestabilným odhadom \(\beta\)
koeficientov. Pripomíname
\[var(\hat\beta_i) = \sigma^2
(X^TX)^{-1}_{ii}\]
model_ols <- lm(y ~ x1 + x2 + x3, data = data_main)
summary(model_ols)
Call:
lm(formula = y ~ x1 + x2 + x3, data = data_main)
Residuals:
Min 1Q Median 3Q Max
-2.53250 -0.67022 0.07388 0.70545 2.68627
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 0.97304 0.07277 13.372 < 2e-16 ***
x1 1.42700 0.46815 3.048 0.00262 **
x2 -0.94615 0.48842 -1.937 0.05416 .
x3 0.83698 0.07563 11.067 < 2e-16 ***
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Residual standard error: 1.027 on 196 degrees of freedom
Multiple R-squared: 0.4671, Adjusted R-squared: 0.459
F-statistic: 57.27 on 3 and 196 DF, p-value: < 2.2e-16
3. Multicollinearity detection and testing
3.1 Korelačná analýza vysvetľujúcich premenných
Najjednoduchší diagnostický krok je korelačná matica medzi
vysvetľujúcimi premennými.
X <- data_main[, c("x1", "x2", "x3")]
cor_matrix <- cor(X)
round(cor_matrix, 4)
x1 x2 x3
x1 1.0000 0.9863 -0.0302
x2 0.9863 1.0000 -0.0384
x3 -0.0302 -0.0384 1.0000
Vysoká absolútna hodnota korelácie, napríklad \(|r_{ij}| > 0.8\), môže indikovať problém
multikolinearity. Sama o sebe však nestačí, pretože multikolinearita
môže byť aj viacrozmerná: premenná môže byť lineárnou kombináciou
viacerých ostatných premenných.
cor.test(data_main$x1, data_main$x2)
Pearson's product-moment correlation
data: data_main$x1 and data_main$x2
t = 84.039, df = 198, p-value < 2.2e-16
alternative hypothesis: true correlation is not equal to 0
95 percent confidence interval:
0.9818871 0.9895986
sample estimates:
cor
0.9862705
cor.test(data_main$x1, data_main$x3)
Pearson's product-moment correlation
data: data_main$x1 and data_main$x3
t = -0.4256, df = 198, p-value = 0.6709
alternative hypothesis: true correlation is not equal to 0
95 percent confidence interval:
-0.1682678 0.1089655
sample estimates:
cor
-0.03023254
cor.test(data_main$x2, data_main$x3)
Pearson's product-moment correlation
data: data_main$x2 and data_main$x3
t = -0.54143, df = 198, p-value = 0.5888
alternative hypothesis: true correlation is not equal to 0
95 percent confidence interval:
-0.1762504 0.1008293
sample estimates:
cor
-0.0384496
if (!requireNamespace("corrplot", quietly = TRUE)) {
install.packages("corrplot")
}
library(corrplot)
corrplot(cor_matrix, method = "number", type = "upper")

3.2 Variance Inflation Factor
Pre premennú \(x_j\) definujeme
\[
VIF_j = \frac{1}{1-R_j^2},
\]
kde \(R_j^2\) je koeficient
determinácie z pomocnej regresie, v ktorej je \(x_j\) vysvetľovaná ostatnými
regresormi.
Ak je \(R_j^2\) blízko jednej, potom
je \(VIF_j\) veľký a premenná \(x_j\) je silno lineárne vysvetliteľná
ostatnými premennými.
install.packages(“car”) # run once if not installed
library(car)
# Variance Inflation Factors
vif_values <- vif(model)
vif_values
x1 x2 x3
36.74934 36.77011 1.00366
Interpretation:
- \(VIF_j = 1\): žiadna
multikolinearita,
- \(1 < VIF_j < 5\): mierna
multikolinearita
- \(VIF_j \geq 5\): silná
multikolinearita (niektorí autori používajú prísnejší prah \(VIF_j \geq 10\)).
3.3 Číslo podmienenosti
Číslo podmienenosti je založené na vlastných číslach matice \(X'X\). Ak sú vlastné čísla veľmi
rozdielne, matica je zle podmienená.
\[
\kappa = \sqrt{\frac{\lambda_{\max}}{\lambda_{\min}}}.
\]
X_scaled <- scale(X)
eigen_values <- eigen(cor(X_scaled))$values
condition_number <- sqrt(max(eigen_values) / min(eigen_values))
eigen_values
[1] 1.98865618 0.99764855 0.01369527
condition_number
[1] 12.05021
Interpretácia čísla podmienenosti: - \(\kappa \approx 1\): žiadna
multikolinearita, - \(\kappa > 10\):
mierna multikolinearita, - \(\kappa >
30\): silná multikolinearita.
3.4 Farrar–Glauberov test
Farrar–Glauberov test skúma multikolinearitu pomocou korelačnej
matice regresorov. Nech \(R\) je
korelačná matica vysvetľujúcich premenných, \(n\) je počet pozorovaní a \(k\) počet regresorov.
Celkový \(\chi^2\) test
Testujeme nulovú hypotézu, že regresory nie sú navzájom
korelované:
\[
H_0: R = I_k.
\]
Testovacia štatistika je
\[
\chi^2 =
-\left(n-1-\frac{2k+5}{6}\right)\ln |R|.
\]
Stupne voľnosti sú
\[
df = \frac{k(k-1)}{2}.
\]
fg_chi_square <- function(X) {
X <- as.data.frame(X)
R <- cor(X)
n <- nrow(X)
k <- ncol(X)
chi_stat <- -(n - 1 - (2*k + 5)/6) * log(det(R))
df <- k * (k - 1) / 2
p_value <- 1 - pchisq(chi_stat, df = df)
data.frame(
chi_square = chi_stat,
df = df,
p_value = p_value,
det_R = det(R)
)
}
fg_chi <- fg_chi_square(X)
round(fg_chi, 4)
Malá p-hodnota znamená, že zamietame hypotézu \(R=I_k\), teda medzi vysvetľujúcimi
premennými existuje štatisticky významná korelačná štruktúra.
4. Eliminácia problému multikolinearity
Multikolinearita nie je porušením exogenity. Nie je teda automaticky
dôvodom na zamietnutie OLS modelu. Problém je hlavne inferenčný: veľké
štandardné chyby a nestabilné individuálne koeficienty.
Možné riešenia:
- získať viac dát,
- odstrániť alebo spojiť silno korelované premenné,
- transformovať premenné,
- použiť teoretické obmedzenia,
- použiť regularizačné metódy, napríklad ridge regresiu.
4.1 Odstránenie jednej z korelovaných premenných
Ak sú dve premenné takmer rovnaké a ekonomická teória nevyžaduje obe,
môžeme jednu z nich vynechať.
model_reduced <- lm(y ~ x1 + x3, data = data_main)
summary(model_ols)
Call:
lm(formula = y ~ x1 + x2 + x3, data = data_main)
Residuals:
Min 1Q Median 3Q Max
-2.53250 -0.67022 0.07388 0.70545 2.68627
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 0.97304 0.07277 13.372 < 2e-16 ***
x1 1.42700 0.46815 3.048 0.00262 **
x2 -0.94615 0.48842 -1.937 0.05416 .
x3 0.83698 0.07563 11.067 < 2e-16 ***
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Residual standard error: 1.027 on 196 degrees of freedom
Multiple R-squared: 0.4671, Adjusted R-squared: 0.459
F-statistic: 57.27 on 3 and 196 DF, p-value: < 2.2e-16
summary(model_reduced)
Call:
lm(formula = y ~ x1 + x3, data = data_main)
Residuals:
Min 1Q Median 3Q Max
-2.75173 -0.64762 0.09045 0.69569 2.69396
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 0.96686 0.07320 13.208 < 2e-16 ***
x1 0.53254 0.07780 6.845 9.46e-11 ***
x3 0.84464 0.07605 11.106 < 2e-16 ***
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
Residual standard error: 1.035 on 197 degrees of freedom
Multiple R-squared: 0.4569, Adjusted R-squared: 0.4514
F-statistic: 82.87 on 2 and 197 DF, p-value: < 2.2e-16
Pozor: vynechanie relevantnej premennej môže viesť k vychýleniu
odhadov. Preto sa premenné nemajú vyhadzovať mechanicky iba podľa
korelácie.
4.2 Ridge regression
Ridge regresia rieši problém nestability tým, že minimalizuje
penalizovanú sumu štvorcov:
\[
\hat\beta^{ridge}
=
\arg\min_{\beta}
\left[
\sum_{i=1}^n (y_i - x_i'\beta)^2
+
\lambda \sum_{j=1}^k \beta_j^2
\right].
\]
Parameter \(\lambda \geq 0\) určuje
silu penalizácie. Ak \(\lambda=0\),
dostaneme OLS. Ak \(\lambda\) rastie,
koeficienty sa zmenšujú smerom k nule.
Maticovo, pri centrovaných a škálovaných regresoroch,
\[
\hat\beta^{ridge}
=
(X'X+\lambda I)^{-1}X'y.
\]
Ridge znižuje rozptyl odhadov za cenu určitého vychýlenia. Preto je
užitočná najmä pri predikcii alebo pri veľmi nestabilných OLS
koeficientoch.
if (!requireNamespace("glmnet", quietly = TRUE)) {
install.packages("glmnet")
}
library(glmnet)
X_mat <- model.matrix(y ~ x1 + x2 + x3, data = data_main)[, -1]
y_vec <- data_main$y
ridge_cv <- cv.glmnet(
x = X_mat,
y = y_vec,
alpha = 0,
standardize = TRUE
)
ridge_cv$lambda.min
[1] 0.07977274
ridge_cv$lambda.1se
[1] 0.8164987
coef(ridge_cv, s = "lambda.min")
4 x 1 sparse Matrix of class "dgCMatrix"
lambda.min
(Intercept) 0.96790458
x1 0.47731517
x2 0.02760042
x3 0.79830075
plot(ridge_cv)

Porovnajme OLS a ridge koeficienty.
ols_coef <- coef(model_ols)
ridge_coef <- as.matrix(coef(ridge_cv, s = "lambda.min"))
comparison <- data.frame(
coefficient = rownames(ridge_coef),
OLS = as.numeric(ols_coef[rownames(ridge_coef)]),
Ridge = as.numeric(ridge_coef[, 1])
)
round_numeric(comparison, 4)
Ridge regresia typicky nemení cieľ z inferencie na jednotlivé
nepenalizované parametre, ale pomáha stabilizovať odhady a zlepšiť
predikčnú výkonnosť v prítomnosti silnej multikolinearity.
4.3 Predikčné porovnanie OLS a ridge
set.seed(321)
train_id <- sample(1:nrow(data_main), size = 0.7*nrow(data_main))
train <- data_main[train_id, ]
test <- data_main[-train_id, ]
ols_train <- lm(y ~ x1 + x2 + x3, data = train)
X_train <- model.matrix(y ~ x1 + x2 + x3, data = train)[, -1]
y_train <- train$y
X_test <- model.matrix(y ~ x1 + x2 + x3, data = test)[, -1]
y_test <- test$y
ridge_train_cv <- cv.glmnet(
x = X_train,
y = y_train,
alpha = 0,
standardize = TRUE
)
pred_ols <- predict(ols_train, newdata = test)
pred_ridge <- predict(ridge_train_cv, newx = X_test, s = "lambda.min")
mse_ols <- mean((y_test - pred_ols)^2)
mse_ridge <- mean((y_test - pred_ridge)^2)
data.frame(
model = c("OLS", "Ridge"),
test_MSE = c(mse_ols, as.numeric(mse_ridge))
)
Zhrnutie
Multikolinearita znamená silnú lineárnu závislosť medzi
vysvetľujúcimi premennými. Pri dokonalej multikolinearite OLS odhad
neexistuje. Pri silnej, ale nedokonalej multikolinearite OLS existuje,
no štandardné chyby môžu byť veľké a odhady nestabilné.
V praxi je vhodné použiť viacero diagnostík: korelačnú maticu, VIF,
číslo podmienenosti a Farrar–Glauberov test. Pri riešení problému treba
zohľadniť ekonomickú teóriu. Ridge regresia je vhodná najmä vtedy, keď
je cieľom stabilná predikcia.
LS0tCnRpdGxlOiAiTXVsdGlrb2xpbmVhcml0YSB2IGxpbmXDoXJuZWogcmVncmVzaWkiCmF1dGhvcjogIkVjb25vbWV0cmljcyBHUFQiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDMKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSkKc2V0LnNlZWQoMTIzKQpgYGAKCiMgMS4gTXVsdGlrb2xpbmVhcml0YSDigJMgZGVmaW7DrWNpYQoKVXZhxb51am1lIGxpbmXDoXJueSByZWdyZXNuw70gbW9kZWwKClxbCnlfaSA9IFxiZXRhXzAgKyBcYmV0YV8xIHhfezFpfSArIFxjZG90cyArIFxiZXRhX2sgeF97a2l9ICsgdV9pLApcXQoKYWxlYm8gbWF0aWNvdm8KClxbCnkgPSBYXGJldGEgKyB1LgpcXQoKTXVsdGlrb2xpbmVhcml0YSB6bmFtZW7DoSwgxb5lIG5pZWt0b3LDqSB2eXN2ZXTEvnVqw7pjZSBwcmVtZW5uw6kgdiBtYXRpY2kgXChYXCkgc8O6IHNpbG5vIGxpbmXDoXJuZSB6w6F2aXNsw6kuIERva29uYWzDoSBtdWx0aWtvbGluZWFyaXRhIG5hc3TDoXZhIHZ0ZWR5LCBrZcSPIGV4aXN0dWplIG5lbnVsb3bDvSB2ZWt0b3IgXChhXCksIHByZSBrdG9yw70KClxbClhhID0gMC4KXF0KClZ0ZWR5IG1hdGljYSBcKFgnWFwpIG5pZSBqZSByZWd1bMOhcm5hIGEgT0xTIG9kaGFkCgpcWwpcaGF0XGJldGEgPSAoWCdYKV57LTF9WCd5ClxdCgpuZWV4aXN0dWplLgoKViBwcmF4aSDEjWFzdGVqxaFpZSBwb3pvcnVqZW1lIG5lZG9rb25hbMO6LCBhbGUgc2lsbsO6IG11bHRpa29saW5lYXJpdHUuIFBvdG9tIFwoWCdYXCkgamUgc8OtY2UgaW52ZXJ0aWJpbG7DoSwgYWxlIHpsZSBwb2RtaWVuZW7DoS4gT2RoYWR5IGV4aXN0dWrDuiwgbm8gbcO0xb51IGJ5xaUgdmXEvm1pIG5lcHJlc27DqS4KCiMjIFNpbXVsb3ZhbsOpIGTDoXRhCgpWeXR2b3LDrW1lIGhsYXZuw70gZMOhdG92w70gc8O6Ym9yIGBkYXRhX21haW5gLCBrdG9yw70gYnVkZW1lIHBvdcW+w612YcWlIHYgxI9hbMWhw61jaCDEjWFzdGlhY2guCgpQcmVtZW5uw6k6CgotIGB5YCBqZSB6w6F2aXNsw6EgcHJlbWVubsOhLAotIGB4MWAsIGB4MmAsIGB4M2Agc8O6IHZ5c3ZldMS+dWrDumNlIHByZW1lbm7DqSwKLSBgeDJgIGplIGtvbsWhdHJ1b3ZhbsOhIHRhaywgYWJ5IGJvbGEgc2lsbm8ga29yZWxvdmFuw6EgcyBgeDFgLAotIGB4M2AgamUgcHJpYmxpxb5uZSBuZXrDoXZpc2zDoSBvZCBgeDFgIGEgYHgyYC4KCmBgYHtyIGRhdGEtbWFpbn0KbiA8LSAyMDAKCngxIDwtIHJub3JtKG4pCngyIDwtIDAuOTUgKiB4MSArIHJub3JtKG4sIHNkID0gMC4xNSkKeDMgPC0gcm5vcm0obikKCnUgPC0gcm5vcm0obikKCnkgPC0gMSArIDIqeDEgLSAxLjUqeDIgKyAwLjgqeDMgKyB1CgpkYXRhX21haW4gPC0gZGF0YS5mcmFtZSh5ID0geSwgeDEgPSB4MSwgeDIgPSB4MiwgeDMgPSB4MykKCmhlYWQoZGF0YV9tYWluKQpgYGAKCiMgMi5Ew7RzbGVka3kgbXVsdGlrb2xpbmVhcml0eSBwcmUgT0xTIG9kaGFkCgpQcmkgbXVsdGlrb2xpbmVhcml0ZSBPTFMgb2RoYWQgem9zdMOhdmEgbmVzdHJhbm7DvSB6YSDFoXRhbmRhcmRuw71jaCBleG9nZW5pdG7DvWNoIHByZWRwb2tsYWRvdiwKClxbCkUodSk9MCwKXF0KCmFsZSBqZWhvIHJvenB0eWwgbcO0xb5lIGJ5xaUgdmXEvmvDvToKClxbClZhcihcaGF0XGJldGEpPVxzaWdtYV4yKFgnWCleey0xfS4KXF0KCkFrIHPDuiBzdMS6cGNlIG1hdGljZSBcKFhcKSB0YWttZXIgbGluZcOhcm5lIHrDoXZpc2zDqSwgbmlla3RvcsOpIHBydmt5IG1hdGljZSBcKChYJ1gpXnstMX1cKSBzw7ogdmXEvmvDqS4KCmBgYHtyfQpYIDwtIGNiaW5kKDEsIHgxLCB4MiwgeDMpCmNvbG5hbWVzKFgpIDwtIGMoImludGVyY2VwdCIsICJ4MSIsICJ4MiIsICJ4MyIpCgpYdFggPC0gdChYKSAlKiUgWAoKWHRYX2ludiA8LSBzb2x2ZShYdFgpCgpYdFhfaW52CmBgYAoKCgoKVG8gdmVkaWUgayB2ZcS+a8O9bSDFoXRhbmRhcmRuw71tIGNoeWLDoW0sIG7DrXpreW0gdC3FoXRhdGlzdGlrw6FtIGEgbmVzdGFiaWxuw71tIG9kaGFkb20gJFxiZXRhJCBrb2VmaWNpZW50b3YuIFByaXBvbcOtbmFtZQoKJCR2YXIoXGhhdFxiZXRhX2kpID0gXHNpZ21hXjIgKFheVFgpXnstMX1fe2lpfSQkCgpgYGB7ciBvbHMtbWFpbn0KbW9kZWxfb2xzIDwtIGxtKHkgfiB4MSArIHgyICsgeDMsIGRhdGEgPSBkYXRhX21haW4pCnN1bW1hcnkobW9kZWxfb2xzKQpgYGAKCgoKIyAzLiBNdWx0aWNvbGxpbmVhcml0eSBkZXRlY3Rpb24gYW5kIHRlc3RpbmcKCiMjIDMuMSBLb3JlbGHEjW7DoSBhbmFsw716YSB2eXN2ZXTEvnVqw7pjaWNoIHByZW1lbm7DvWNoCgpOYWpqZWRub2R1Y2jFocOtIGRpYWdub3N0aWNrw70ga3JvayBqZSBrb3JlbGHEjW7DoSBtYXRpY2EgbWVkemkgdnlzdmV0xL51asO6Y2ltaSBwcmVtZW5uw71taS4KCmBgYHtyIGNvcnJlbGF0aW9uLW1hdHJpeH0KWCA8LSBkYXRhX21haW5bLCBjKCJ4MSIsICJ4MiIsICJ4MyIpXQoKY29yX21hdHJpeCA8LSBjb3IoWCkKcm91bmQoY29yX21hdHJpeCwgNCkKYGBgCgpWeXNva8OhIGFic29sw7p0bmEgaG9kbm90YSBrb3JlbMOhY2llLCBuYXByw61rbGFkIFwofHJfe2lqfXwgPiAwLjhcKSwgbcO0xb5lIGluZGlrb3ZhxaUgcHJvYmzDqW0gbXVsdGlrb2xpbmVhcml0eS4gU2FtYSBvIHNlYmUgdsWhYWsgbmVzdGHEjcOtLCBwcmV0b8W+ZSBtdWx0aWtvbGluZWFyaXRhIG3DtMW+ZSBiecWlIGFqIHZpYWNyb3ptZXJuw6E6IHByZW1lbm7DoSBtw7TFvmUgYnnFpSBsaW5lw6Fybm91IGtvbWJpbsOhY2lvdSB2aWFjZXLDvWNoIG9zdGF0bsO9Y2ggcHJlbWVubsO9Y2guCgpgYGB7ciBjb3JyZWxhdGlvbi10ZXN0c30KY29yLnRlc3QoZGF0YV9tYWluJHgxLCBkYXRhX21haW4keDIpCmNvci50ZXN0KGRhdGFfbWFpbiR4MSwgZGF0YV9tYWluJHgzKQpjb3IudGVzdChkYXRhX21haW4keDIsIGRhdGFfbWFpbiR4MykKYGBgCgpgYGB7ciBjb3JyZWxhdGlvbi1wbG90fQppZiAoIXJlcXVpcmVOYW1lc3BhY2UoImNvcnJwbG90IiwgcXVpZXRseSA9IFRSVUUpKSB7CiAgaW5zdGFsbC5wYWNrYWdlcygiY29ycnBsb3QiKQp9CgpsaWJyYXJ5KGNvcnJwbG90KQoKY29ycnBsb3QoY29yX21hdHJpeCwgbWV0aG9kID0gIm51bWJlciIsIHR5cGUgPSAidXBwZXIiKQpgYGAKCiMjIDMuMiBWYXJpYW5jZSBJbmZsYXRpb24gRmFjdG9yCgpQcmUgcHJlbWVubsO6IFwoeF9qXCkgZGVmaW51amVtZQoKXFsKVklGX2ogPSBcZnJhY3sxfXsxLVJfal4yfSwKXF0KCmtkZSBcKFJfal4yXCkgamUga29lZmljaWVudCBkZXRlcm1pbsOhY2llIHogcG9tb2NuZWogcmVncmVzaWUsIHYga3RvcmVqIGplIFwoeF9qXCkgdnlzdmV0xL5vdmFuw6Egb3N0YXRuw71taSByZWdyZXNvcm1pLgoKQWsgamUgXChSX2peMlwpIGJsw616a28gamVkbmVqLCBwb3RvbSBqZSBcKFZJRl9qXCkgdmXEvmvDvSBhIHByZW1lbm7DoSBcKHhfalwpIGplIHNpbG5vIGxpbmXDoXJuZSB2eXN2ZXRsaXRlxL5uw6Egb3N0YXRuw71taSBwcmVtZW5uw71taS4KCiMgaW5zdGFsbC5wYWNrYWdlcygiY2FyIikgICMgcnVuIG9uY2UgaWYgbm90IGluc3RhbGxlZAoKCmBgYHtyfQpsaWJyYXJ5KGNhcikKIyBWYXJpYW5jZSBJbmZsYXRpb24gRmFjdG9ycwp2aWZfdmFsdWVzIDwtIHZpZihtb2RlbCkKCnZpZl92YWx1ZXMKYGBgCgoqKkludGVycHJldGF0aW9uOioqCgotIFwoVklGX2ogPSAxXCk6IMW+aWFkbmEgbXVsdGlrb2xpbmVhcml0YSwKLSBcKDEgPCBWSUZfaiA8IDVcKTogbWllcm5hIG11bHRpa29saW5lYXJpdGEKLSBcKFZJRl9qIFxnZXEgNVwpOiBzaWxuw6EgbXVsdGlrb2xpbmVhcml0YSAobmlla3RvcsOtIGF1dG9yaSBwb3XFvsOtdmFqw7ogcHLDrXNuZWrFocOtIHByYWggXChWSUZfaiBcZ2VxIDEwXCkpLgoKIyMgMy4zIMSMw61zbG8gcG9kbWllbmVub3N0aQoKxIzDrXNsbyBwb2RtaWVuZW5vc3RpIGplIHphbG/FvmVuw6kgbmEgdmxhc3Ruw71jaCDEjcOtc2xhY2ggbWF0aWNlIFwoWCdYXCkuIEFrIHPDuiB2bGFzdG7DqSDEjcOtc2xhIHZlxL5taSByb3pkaWVsbmUsIG1hdGljYSBqZSB6bGUgcG9kbWllbmVuw6EuCgpcWwpca2FwcGEgPSBcc3FydHtcZnJhY3tcbGFtYmRhX3tcbWF4fX17XGxhbWJkYV97XG1pbn19fS4KXF0KCmBgYHtyIGNvbmRpdGlvbi1udW1iZXJ9Clhfc2NhbGVkIDwtIHNjYWxlKFgpCmVpZ2VuX3ZhbHVlcyA8LSBlaWdlbihjb3IoWF9zY2FsZWQpKSR2YWx1ZXMKCmNvbmRpdGlvbl9udW1iZXIgPC0gc3FydChtYXgoZWlnZW5fdmFsdWVzKSAvIG1pbihlaWdlbl92YWx1ZXMpKQplaWdlbl92YWx1ZXMKY29uZGl0aW9uX251bWJlcgpgYGAKICAKKipJbnRlcnByZXTDoWNpYSDEjcOtc2xhIHBvZG1pZW5lbm9zdGk6KiogCi0gXChca2FwcGEgXGFwcHJveCAxXCk6IMW+aWFkbmEgbXVsdGlrb2xpbmVhcml0YSwKLSBcKFxrYXBwYSA+IDEwXCk6IG1pZXJuYSBtdWx0aWtvbGluZWFyaXRhLAotIFwoXGthcHBhID4gMzBcKTogc2lsbsOhIG11bHRpa29saW5lYXJpdGEuCgogIAojIyAzLjQgRmFycmFy4oCTR2xhdWJlcm92IHRlc3QKCkZhcnJhcuKAk0dsYXViZXJvdiB0ZXN0IHNrw7ptYSBtdWx0aWtvbGluZWFyaXR1IHBvbW9jb3Uga29yZWxhxI1uZWogbWF0aWNlIHJlZ3Jlc29yb3YuIE5lY2ggXChSXCkgamUga29yZWxhxI1uw6EgbWF0aWNhIHZ5c3ZldMS+dWrDumNpY2ggcHJlbWVubsO9Y2gsIFwoblwpIGplIHBvxI1ldCBwb3pvcm92YW7DrSBhIFwoa1wpIHBvxI1ldCByZWdyZXNvcm92LgoKIyMjIENlbGtvdsO9IFwoXGNoaV4yXCkgdGVzdAoKVGVzdHVqZW1lIG51bG92w7ogaHlwb3TDqXp1LCDFvmUgcmVncmVzb3J5IG5pZSBzw7ogbmF2esOham9tIGtvcmVsb3ZhbsOpOgoKXFsKSF8wOiBSID0gSV9rLgpcXQoKVGVzdG92YWNpYSDFoXRhdGlzdGlrYSBqZQoKXFsKXGNoaV4yID0KLVxsZWZ0KG4tMS1cZnJhY3syays1fXs2fVxyaWdodClcbG4gfFJ8LgpcXQoKU3R1cG5lIHZvxL5ub3N0aSBzw7oKClxbCmRmID0gXGZyYWN7ayhrLTEpfXsyfS4KXF0KCmBgYHtyIGZhcnJhci1nbGF1YmVyLWNoaS1zcXVhcmV9CmZnX2NoaV9zcXVhcmUgPC0gZnVuY3Rpb24oWCkgewogIFggPC0gYXMuZGF0YS5mcmFtZShYKQogIFIgPC0gY29yKFgpCiAgbiA8LSBucm93KFgpCiAgayA8LSBuY29sKFgpCgogIGNoaV9zdGF0IDwtIC0obiAtIDEgLSAoMiprICsgNSkvNikgKiBsb2coZGV0KFIpKQogIGRmIDwtIGsgKiAoayAtIDEpIC8gMgogIHBfdmFsdWUgPC0gMSAtIHBjaGlzcShjaGlfc3RhdCwgZGYgPSBkZikKCiAgZGF0YS5mcmFtZSgKICAgIGNoaV9zcXVhcmUgPSBjaGlfc3RhdCwKICAgIGRmID0gZGYsCiAgICBwX3ZhbHVlID0gcF92YWx1ZSwKICAgIGRldF9SID0gZGV0KFIpCiAgKQp9CgpmZ19jaGkgPC0gZmdfY2hpX3NxdWFyZShYKQpyb3VuZChmZ19jaGksIDQpCmBgYAoKTWFsw6EgcC1ob2Rub3RhIHpuYW1lbsOhLCDFvmUgemFtaWV0YW1lIGh5cG90w6l6dSBcKFI9SV9rXCksIHRlZGEgbWVkemkgdnlzdmV0xL51asO6Y2ltaSBwcmVtZW5uw71taSBleGlzdHVqZSDFoXRhdGlzdGlja3kgdsO9em5hbW7DoSBrb3JlbGHEjW7DoSDFoXRydWt0w7pyYS4KCgoKIyA0LiBFbGltaW7DoWNpYSBwcm9ibMOpbXUgbXVsdGlrb2xpbmVhcml0eQoKTXVsdGlrb2xpbmVhcml0YSBuaWUgamUgcG9ydcWhZW7DrW0gZXhvZ2VuaXR5LiBOaWUgamUgdGVkYSBhdXRvbWF0aWNreSBkw7R2b2RvbSBuYSB6YW1pZXRudXRpZSBPTFMgbW9kZWx1LiBQcm9ibMOpbSBqZSBobGF2bmUgaW5mZXJlbsSNbsO9OiB2ZcS+a8OpIMWhdGFuZGFyZG7DqSBjaHlieSBhIG5lc3RhYmlsbsOpIGluZGl2aWR1w6FsbmUga29lZmljaWVudHkuCgpNb8W+bsOpIHJpZcWhZW5pYToKCjEuIHrDrXNrYcWlIHZpYWMgZMOhdCwKMi4gb2RzdHLDoW5pxaUgYWxlYm8gc3BvamnFpSBzaWxubyBrb3JlbG92YW7DqSBwcmVtZW5uw6ksCjMuIHRyYW5zZm9ybW92YcWlIHByZW1lbm7DqSwKNC4gcG91xb5pxaUgdGVvcmV0aWNrw6kgb2JtZWR6ZW5pYSwKNS4gcG91xb5pxaUgcmVndWxhcml6YcSNbsOpIG1ldMOzZHksIG5hcHLDrWtsYWQgcmlkZ2UgcmVncmVzaXUuCgojIyA0LjEgT2RzdHLDoW5lbmllIGplZG5laiB6IGtvcmVsb3ZhbsO9Y2ggcHJlbWVubsO9Y2gKCkFrIHPDuiBkdmUgcHJlbWVubsOpIHRha21lciByb3ZuYWvDqSBhIGVrb25vbWlja8OhIHRlw7NyaWEgbmV2ecW+YWR1amUgb2JlLCBtw7TFvmVtZSBqZWRudSB6IG5pY2ggdnluZWNoYcWlLgoKYGBge3IgcmVkdWNlZC1tb2RlbH0KbW9kZWxfcmVkdWNlZCA8LSBsbSh5IH4geDEgKyB4MywgZGF0YSA9IGRhdGFfbWFpbikKCnN1bW1hcnkobW9kZWxfb2xzKQpzdW1tYXJ5KG1vZGVsX3JlZHVjZWQpCmBgYAoKUG96b3I6IHZ5bmVjaGFuaWUgcmVsZXZhbnRuZWogcHJlbWVubmVqIG3DtMW+ZSB2aWVzxaUgayB2eWNow71sZW5pdSBvZGhhZG92LiBQcmV0byBzYSBwcmVtZW5uw6kgbmVtYWrDuiB2eWhhZHpvdmHFpSBtZWNoYW5pY2t5IGliYSBwb2TEvmEga29yZWzDoWNpZS4KCiMjIDQuMiBSaWRnZSByZWdyZXNzaW9uCgpSaWRnZSByZWdyZXNpYSByaWXFoWkgcHJvYmzDqW0gbmVzdGFiaWxpdHkgdMO9bSwgxb5lIG1pbmltYWxpenVqZSBwZW5hbGl6b3ZhbsO6IHN1bXUgxaF0dm9yY292OgoKXFsKXGhhdFxiZXRhXntyaWRnZX0KPQpcYXJnXG1pbl97XGJldGF9ClxsZWZ0Wwpcc3VtX3tpPTF9Xm4gKHlfaSAtIHhfaSdcYmV0YSleMgorClxsYW1iZGEgXHN1bV97aj0xfV5rIFxiZXRhX2peMgpccmlnaHRdLgpcXQoKUGFyYW1ldGVyIFwoXGxhbWJkYSBcZ2VxIDBcKSB1csSNdWplIHNpbHUgcGVuYWxpesOhY2llLiBBayBcKFxsYW1iZGE9MFwpLCBkb3N0YW5lbWUgT0xTLiBBayBcKFxsYW1iZGFcKSByYXN0aWUsIGtvZWZpY2llbnR5IHNhIHptZW7FoXVqw7ogc21lcm9tIGsgbnVsZS4KCk1hdGljb3ZvLCBwcmkgY2VudHJvdmFuw71jaCBhIMWha8OhbG92YW7DvWNoIHJlZ3Jlc29yb2NoLAoKXFsKXGhhdFxiZXRhXntyaWRnZX0KPQooWCdYK1xsYW1iZGEgSSleey0xfVgneS4KXF0KClJpZGdlIHpuacW+dWplIHJvenB0eWwgb2RoYWRvdiB6YSBjZW51IHVyxI1pdMOpaG8gdnljaMO9bGVuaWEuIFByZXRvIGplIHXFvml0b8SNbsOhIG5ham3DpCBwcmkgcHJlZGlrY2lpIGFsZWJvIHByaSB2ZcS+bWkgbmVzdGFiaWxuw71jaCBPTFMga29lZmljaWVudG9jaC4KCmBgYHtyIHJpZGdlLXJlZ3Jlc3Npb259CmlmICghcmVxdWlyZU5hbWVzcGFjZSgiZ2xtbmV0IiwgcXVpZXRseSA9IFRSVUUpKSB7CiAgaW5zdGFsbC5wYWNrYWdlcygiZ2xtbmV0IikKfQoKbGlicmFyeShnbG1uZXQpCgpYX21hdCA8LSBtb2RlbC5tYXRyaXgoeSB+IHgxICsgeDIgKyB4MywgZGF0YSA9IGRhdGFfbWFpbilbLCAtMV0KeV92ZWMgPC0gZGF0YV9tYWluJHkKCnJpZGdlX2N2IDwtIGN2LmdsbW5ldCgKICB4ID0gWF9tYXQsCiAgeSA9IHlfdmVjLAogIGFscGhhID0gMCwKICBzdGFuZGFyZGl6ZSA9IFRSVUUKKQoKcmlkZ2VfY3YkbGFtYmRhLm1pbgpyaWRnZV9jdiRsYW1iZGEuMXNlCmBgYAoKYGBge3IgcmlkZ2UtY29lZmZpY2llbnRzfQpjb2VmKHJpZGdlX2N2LCBzID0gImxhbWJkYS5taW4iKQpgYGAKCmBgYHtyIHJpZGdlLXBsb3R9CnBsb3QocmlkZ2VfY3YpCmBgYAoKUG9yb3ZuYWptZSBPTFMgYSByaWRnZSBrb2VmaWNpZW50eS4KCmBgYHtyIGNvbXBhcmUtb2xzLXJpZGdlfQpvbHNfY29lZiA8LSBjb2VmKG1vZGVsX29scykKCnJpZGdlX2NvZWYgPC0gYXMubWF0cml4KGNvZWYocmlkZ2VfY3YsIHMgPSAibGFtYmRhLm1pbiIpKQoKY29tcGFyaXNvbiA8LSBkYXRhLmZyYW1lKAogIGNvZWZmaWNpZW50ID0gcm93bmFtZXMocmlkZ2VfY29lZiksCiAgT0xTID0gYXMubnVtZXJpYyhvbHNfY29lZltyb3duYW1lcyhyaWRnZV9jb2VmKV0pLAogIFJpZGdlID0gYXMubnVtZXJpYyhyaWRnZV9jb2VmWywgMV0pCikKCnJvdW5kX251bWVyaWMoY29tcGFyaXNvbiwgNCkKYGBgCgpSaWRnZSByZWdyZXNpYSB0eXBpY2t5IG5lbWVuw60gY2llxL4geiBpbmZlcmVuY2llIG5hIGplZG5vdGxpdsOpIG5lcGVuYWxpem92YW7DqSBwYXJhbWV0cmUsIGFsZSBwb23DoWhhIHN0YWJpbGl6b3ZhxaUgb2RoYWR5IGEgemxlcMWhacWlIHByZWRpa8SNbsO6IHbDvWtvbm5vc8WlIHYgcHLDrXRvbW5vc3RpIHNpbG5laiBtdWx0aWtvbGluZWFyaXR5LgoKIyMgNC4zIFByZWRpa8SNbsOpIHBvcm92bmFuaWUgT0xTIGEgcmlkZ2UKCmBgYHtyIHByZWRpY3Rpb24tY29tcGFyaXNvbn0Kc2V0LnNlZWQoMzIxKQoKdHJhaW5faWQgPC0gc2FtcGxlKDE6bnJvdyhkYXRhX21haW4pLCBzaXplID0gMC43Km5yb3coZGF0YV9tYWluKSkKCnRyYWluIDwtIGRhdGFfbWFpblt0cmFpbl9pZCwgXQp0ZXN0IDwtIGRhdGFfbWFpblstdHJhaW5faWQsIF0KCm9sc190cmFpbiA8LSBsbSh5IH4geDEgKyB4MiArIHgzLCBkYXRhID0gdHJhaW4pCgpYX3RyYWluIDwtIG1vZGVsLm1hdHJpeCh5IH4geDEgKyB4MiArIHgzLCBkYXRhID0gdHJhaW4pWywgLTFdCnlfdHJhaW4gPC0gdHJhaW4keQoKWF90ZXN0IDwtIG1vZGVsLm1hdHJpeCh5IH4geDEgKyB4MiArIHgzLCBkYXRhID0gdGVzdClbLCAtMV0KeV90ZXN0IDwtIHRlc3QkeQoKcmlkZ2VfdHJhaW5fY3YgPC0gY3YuZ2xtbmV0KAogIHggPSBYX3RyYWluLAogIHkgPSB5X3RyYWluLAogIGFscGhhID0gMCwKICBzdGFuZGFyZGl6ZSA9IFRSVUUKKQoKcHJlZF9vbHMgPC0gcHJlZGljdChvbHNfdHJhaW4sIG5ld2RhdGEgPSB0ZXN0KQpwcmVkX3JpZGdlIDwtIHByZWRpY3QocmlkZ2VfdHJhaW5fY3YsIG5ld3ggPSBYX3Rlc3QsIHMgPSAibGFtYmRhLm1pbiIpCgptc2Vfb2xzIDwtIG1lYW4oKHlfdGVzdCAtIHByZWRfb2xzKV4yKQptc2VfcmlkZ2UgPC0gbWVhbigoeV90ZXN0IC0gcHJlZF9yaWRnZSleMikKCmRhdGEuZnJhbWUoCiAgbW9kZWwgPSBjKCJPTFMiLCAiUmlkZ2UiKSwKICB0ZXN0X01TRSA9IGMobXNlX29scywgYXMubnVtZXJpYyhtc2VfcmlkZ2UpKQopCmBgYAoKIyBaaHJudXRpZQoKTXVsdGlrb2xpbmVhcml0YSB6bmFtZW7DoSBzaWxuw7ogbGluZcOhcm51IHrDoXZpc2xvc8WlIG1lZHppIHZ5c3ZldMS+dWrDumNpbWkgcHJlbWVubsO9bWkuIFByaSBkb2tvbmFsZWogbXVsdGlrb2xpbmVhcml0ZSBPTFMgb2RoYWQgbmVleGlzdHVqZS4gUHJpIHNpbG5laiwgYWxlIG5lZG9rb25hbGVqIG11bHRpa29saW5lYXJpdGUgT0xTIGV4aXN0dWplLCBubyDFoXRhbmRhcmRuw6kgY2h5YnkgbcO0xb51IGJ5xaUgdmXEvmvDqSBhIG9kaGFkeSBuZXN0YWJpbG7DqS4KClYgcHJheGkgamUgdmhvZG7DqSBwb3XFvmnFpSB2aWFjZXJvIGRpYWdub3N0w61rOiBrb3JlbGHEjW7DuiBtYXRpY3UsIFZJRiwgxI3DrXNsbyBwb2RtaWVuZW5vc3RpIGEgRmFycmFy4oCTR2xhdWJlcm92IHRlc3QuIFByaSByaWXFoWVuw60gcHJvYmzDqW11IHRyZWJhIHpvaMS+YWRuacWlIGVrb25vbWlja8O6IHRlw7NyaXUuIFJpZGdlIHJlZ3Jlc2lhIGplIHZob2Ruw6EgbmFqbcOkIHZ0ZWR5LCBrZcSPIGplIGNpZcS+b20gc3RhYmlsbsOhIHByZWRpa2NpYS4K