Wprowadzenie
Regresja kwantylowa (ang. quantile regression) została zaproponowana
przez Koenkera i Bassetta (1978). Szczególny przypadek regresji
kwantylowej dla kwantyla rzędu 0,5 (czyli mediany) jest równoważny
estymatorowi LAD (ang. Least Absolute Deviation) – minimalizuje sumę
bezwzględnych błędów.
Wprowadzenie różnych kwantyli regresji daje pełniejszy opis rozkładów
warunkowych zwłaszcza w przypadku rozkładów asymetrycznych lub
uciętych.
Regresja kwantylowa jest kolejną wariacją na temat najmniejszych
kwadratów . Stratą jest współczynnik \(l_1\) funkcji:
\[
\phi(u) = \tau\max(u,0) - (1-\tau)\max(-u,0) = \frac{1}{2}|u| +
\left(\tau - \frac{1}{2}\right)u,
\]
gdzie \(\tau \in (0,1)\) oznacza
konkretny kwantyl. Problemem jak poprzednio jest minimalizacja
całkowitej straty resztowej. Model ten jest powszechnie stosowany w
ekologii, ochronie zdrowia i innych dziedzinach, gdzie sama średnia nie
wystarcza do uchwycenia złożonych zależności między zmiennymi.
Przykład 1.
Wykorzystamy przykład z pakietu quantreg.
Jaki jest związek między całkowitym dochodem gospodarstwa domowego a
odsetkiem dochodów wydatkowanych na żywność? Prawo Engela w ekonomii
głosi, że w miarę wzrostu dochodów, część dochodów wydatkowanych na
żywność spada, nawet jeśli wydatki na żywność bezwzględnie rosną.
Stosując regresję kwantylową do tych danych, można określić, jakie
wydatki na żywność ponosi 90% rodzin (dla 100 rodzin z danym dochodem),
gdy nie interesują nas średnie wydatki na żywność.
Dane, które wykorzystamy - to zbiór “engel” - dane dotyczące wydatków
na żywność. Jest to zbiór danych regresyjnych składający się z 235
obserwacji dotyczących dochodów i wydatków na żywność dla belgijskich
gospodarstw domowych klasy robotniczej.

Powyższy wykres przedstawia dopasowanie regresji kwantylowej dla
\(\tau = (0.1, 0.25, 0.5, 0.75, 0.90,
0.95)\). Dopasowanie KMNK to gruba czarna linia.
Poniżej znajduje się tabela z oszacowanymi współczynnikami.
knitr::kable(fits, format = "html", caption = "Oszacowania z KMNK oraz `quantreg`") %>%
kable_styling("striped") %>%
column_spec(1:8, background = "#ececec")
Oszacowania z KMNK oraz quantreg
|
|
OLS
|
\(\tau_{0.10}\)
|
\(\tau_{0.25}\)
|
\(\tau_{0.50}\)
|
\(\tau_{0.75}\)
|
\(\tau_{0.90}\)
|
\(\tau_{0.95}\)
|
|
(Intercept)
|
147.4753885
|
110.1415742
|
95.4835396
|
81.4822474
|
62.3965855
|
67.3508721
|
64.1039632
|
|
income
|
0.4851784
|
0.4017658
|
0.4741032
|
0.5601806
|
0.6440141
|
0.6862995
|
0.7090685
|
Ok, możemy to zrobić bardziej przejrzyście i sformatować w ładnej
tabeli wyników:
##
## Wyniki regresji kwantylowych
## ==========================================
## Dependent variable:
## -----------------------------
## foodexp
## (1) (2) (3)
## ------------------------------------------
## income 0.474*** 0.560*** 0.644***
## (0.029) (0.028) (0.023)
##
## Constant 95.484*** 81.482*** 62.397***
## (21.392) (19.251) (16.305)
##
## ------------------------------------------
## Observations 235 235 235
## ==========================================
## Note: *p<0.1; **p<0.05; ***p<0.01
Finalnie, zaprezentujmy wyłącznie te 3 modele na wykresie:

Przykład 2.
Tutaj przeprowadzimy testy użycia pakietu quantreg, wykorzystując
wbudowany zbiór danych “mtcars”. Zmienna
“mpg” oznacza spalanie samochodów
(mile/galon).
Zamodulejmy zależność regresyjną dla tej zmiennej od kilku
predyktorów.
Najpierw oszacujmy regresję KMNK:
kmnk <- lm(mpg ~ disp + hp + factor(am) + factor(vs), data = mtcars)
summary(kmnk)
##
## Call:
## lm(formula = mpg ~ disp + hp + factor(am) + factor(vs), data = mtcars)
##
## Residuals:
## Min 1Q Median 3Q Max
## -4.7981 -1.9532 0.0111 1.5665 5.6321
##
## Coefficients:
## Estimate Std. Error t value Pr(>|t|)
## (Intercept) 24.832119 2.890418 8.591 3.32e-09 ***
## disp -0.008304 0.010087 -0.823 0.41757
## hp -0.037623 0.013846 -2.717 0.01135 *
## factor(am)1 4.419257 1.493243 2.960 0.00634 **
## factor(vs)1 2.052472 1.627096 1.261 0.21794
## ---
## Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
##
## Residual standard error: 2.812 on 27 degrees of freedom
## Multiple R-squared: 0.8104, Adjusted R-squared: 0.7823
## F-statistic: 28.85 on 4 and 27 DF, p-value: 2.13e-09
Teraz oszacujmy warunkowe regresje kwantylowe na różnych kwantylach,
błąd standardowy uzyskany przez bootstrap.
Zauważ, że istnieje gradient we współczynnikach kwantylowych
hp, jak również disp. Znak
disp odwraca się, również współczynnik na czynniku
am jest różny w zależności od kwantyli:
kwantyle <- c(0.25, 0.50, 0.75)
reg_kwantylowa <- rq(mpg ~ disp + hp + factor(am),tau = kwantyle,data = mtcars)
summary(reg_kwantylowa, se = "boot")
##
## Call: rq(formula = mpg ~ disp + hp + factor(am), tau = kwantyle, data = mtcars)
##
## tau: [1] 0.25
##
## Coefficients:
## Value Std. Error t value Pr(>|t|)
## (Intercept) 25.34665 1.62350 15.61236 0.00000
## disp -0.02441 0.00801 -3.04861 0.00498
## hp -0.01672 0.01590 -1.05125 0.30213
## factor(am)1 1.39719 1.28460 1.08765 0.28602
##
## Call: rq(formula = mpg ~ disp + hp + factor(am), tau = kwantyle, data = mtcars)
##
## tau: [1] 0.5
##
## Coefficients:
## Value Std. Error t value Pr(>|t|)
## (Intercept) 27.49722 1.84519 14.90209 0.00000
## disp -0.02253 0.01572 -1.43290 0.16296
## hp -0.02713 0.02303 -1.17809 0.24868
## factor(am)1 3.37328 2.07860 1.62287 0.11583
##
## Call: rq(formula = mpg ~ disp + hp + factor(am), tau = kwantyle, data = mtcars)
##
## tau: [1] 0.75
##
## Coefficients:
## Value Std. Error t value Pr(>|t|)
## (Intercept) 28.06384 1.80140 15.57892 0.00000
## disp 0.00445 0.01485 0.29987 0.76649
## hp -0.06662 0.01775 -3.75420 0.00081
## factor(am)1 7.91402 2.45299 3.22627 0.00319
Testy współczynników
Użyjemy funkcji rq.anova z pakietu regresji kwantylowej, aby
przeprowadzić test WALDA. Pamiętaj, że test WALDA mówi, że biorąc pod
uwagę nieograniczone oszacowania modelu, przetestujemy hipotezę zerową
mówiącą, że współczynniki spełniają pewne liniowe ograniczenia.
Aby ją przetestować, użyjemy obiektu zwróconego z uruchomienia
rq z różnymi liczbami kwantyli i ustawimy
opcję joint na true lub false. Gdy
joint jest true: “równość współczynników
kierunkowych powinna być wykonana jako wspólne testy na wszystkich
parametrach nachylenia”, gdy joint jest false:
“należy zgłaszać oddzielne testy na każdym z parametrów nachylenia”.
Zauważ, że testy kwantylowe są testami “linii równoległej”. Oznacza
to, że powinniśmy wyjąć różne x-wyrazy_wolne dla każdego kwantyla,
ponieważ reprezentują one poziomy rozkładów warunkowych. Jeśli jednak
współczynniki kwantyli dla współczynnikow są takie same, to nie ma
efektów specyficznych dla kwantyli, wystarczą efekty średnie.
Badanie statystycznej różnicy między 25. i 50. kwantylem
warunkowym:
Biorąc pod uwagę powyższe oszacowania kwantyli, różnica między
kwantylami 0,25 i 0,50 istnieje, ale czy są one wystarczająco duże, aby
być statystycznie różne? Jaka jest wartość p? Przeglądając poniższe
wyniki, nie są one statystycznie różne!
Po pierwsze, joint = TRUE. To nie jest testowanie, czy współczynnik
na disp jest taki sam jak współczynnik na hp. To jest wspólne
testowanie, czy współczynniki dla różnych kwantyli disp i różnych
kwantyli hp są takie same dla każdej zmiennej.
kwantyle <- c(0.25, 0.50)
reg_kwantylowa <- rq(mpg ~ disp + hp + factor(am),tau = kwantyle, data = mtcars)
anova(reg_kwantylowa, test = "Wald", joint=TRUE)
## Quantile Regression Analysis of Deviance Table
##
## Model: mpg ~ disp + hp + factor(am)
## Joint Test of Equality of Slopes: tau in { 0.25 0.5 }
##
## Df Resid Df F value Pr(>F)
## 1 3 61 0.8421 0.4761
Po drugie, joint = False:
anova(reg_kwantylowa, test = "Wald", joint=FALSE)
## Quantile Regression Analysis of Deviance Table
##
## Model: mpg ~ disp + hp + factor(am)
## Tests of Equality of Distinct Slopes: tau in { 0.25 0.5 }
##
## Df Resid Df F value Pr(>F)
## disp 1 63 0.0305 0.8619
## hp 1 63 0.5461 0.4627
## factor(am)1 1 63 1.3500 0.2497
Badanie statystycznej różnicy między 25, 50 i 75 kwantylem
warunkowym:
Pierwszy kwartyl i mediana nie wydają się być statystycznie różne,
teraz dołączymy trzeci kwartyl. Jak widać wcześniej, kwartyle wspólnie
wykazują gradient. Teraz możemy zobaczyć, że disp,
hp i am są oddzielnie statystycznie
różne.
Po pierwsze, joint = TRUE:
kwantyle <- c(0.25, 0.50, 0.75)
reg_kwantylowa <- rq(mpg ~ disp + hp + factor(am),tau = kwantyle, data = mtcars)
anova(reg_kwantylowa, test = "Wald", joint=TRUE)
## Quantile Regression Analysis of Deviance Table
##
## Model: mpg ~ disp + hp + factor(am)
## Joint Test of Equality of Slopes: tau in { 0.25 0.5 0.75 }
##
## Df Resid Df F value Pr(>F)
## 1 6 90 3.3173 0.005367 **
## ---
## Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
Po drugie, joint = False:
anova(reg_kwantylowa, test = "Wald", joint=FALSE)
## Quantile Regression Analysis of Deviance Table
##
## Model: mpg ~ disp + hp + factor(am)
## Tests of Equality of Distinct Slopes: tau in { 0.25 0.5 0.75 }
##
## Df Resid Df F value Pr(>F)
## disp 2 94 5.4903 0.005558 **
## hp 2 94 6.7221 0.001868 **
## factor(am)1 2 94 7.2758 0.001154 **
## ---
## Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
Dobroć dopasowania
Możemy obliczyć współczynniki dobroci dopasowania regresji
kwantylowej z wykorzystaniem reszt i reszt bezwarunkowych:
goodfit(resid, resid_nl, tau)
Miara dobroci dopasowania dla regresji kwantylowej jest szacowana
jako 1 minus stosunek sumy odchyleń bezwzględnych w modelach w pełni
sparametryzowanych do sumy odchyleń bezwzględnych w zerowym
(bezwarunkowym) modelu kwantylowym.
Wartości te są przydatne do porównań między modelami kwantylowymi,
ale nie są porównywalne ze standardowymi współczynnikami determinacji.
Te ostatnie oparte są na wariancji odchyleń kwadratowych, natomiast
wartości dobroci dopasowania dla regresji kwantylowej oparte są na
odchyleniach bezwzględnych. Wartości dobroci dopasowania zawsze będą
mniejsze niż wartości R2.
## model kwantylowy
model1 <- rq(mpg ~ disp + hp + factor(am),tau = 0.5, data = mtcars)
reszty1 <- resid(model1)
## bezwarunkowy (pusty) model kwantylowy
model2 <- rq(mpg ~ 1, tau = 0.5,data=mtcars)
reszty2 <- resid(model2)
goodfit(reszty1, reszty2, 0.5)
## [1] 0.5403311
## r2 modelu KMNK dla porównania
model_lm <- lm(mpg ~ disp + hp + factor(am), data = mtcars)
summary(model_lm)$r.squared
## [1] 0.7992061
LS0tDQp0aXRsZTogJ05pZWtsYXN5Y3puZSBtZXRvZHkgc3RhdHlzdHlraScNCnN1YnRpdGxlOiAnUmVncmVzamEga3dhbnR5bG93YScNCmRhdGU6ICJgciBTeXMuRGF0ZSgpYCINCmF1dGhvcjogIlR3b2plIGltacSZIGkgbmF6d2lza28iDQpvdXRwdXQ6DQogIGh0bWxfZG9jdW1lbnQ6IA0KICAgIHRoZW1lOiBjZXJ1bGVhbg0KICAgIGhpZ2hsaWdodDogdGV4dG1hdGUNCiAgICBmb250c2l6ZTogMTBwdA0KICAgIHRvYzogeWVzDQogICAgY29kZV9kb3dubG9hZDogeWVzDQogICAgdG9jX2Zsb2F0Og0KICAgICAgY29sbGFwc2VkOiBubw0KICAgIGRmX3ByaW50OiBkZWZhdWx0DQogICAgdG9jX2RlcHRoOiA1DQplZGl0b3Jfb3B0aW9uczogDQogIG1hcmtkb3duOiANCiAgICB3cmFwOiA3Mg0KLS0tDQoNCmBgYHtyIHByZXJlcXMsIG1lc3NhZ2UgPSBGQUxTRSwgZWNobyA9IEZBTFNFfQ0KbGlicmFyeShDVlhSKQ0KbGlicmFyeShBRVIpDQpsaWJyYXJ5KHN0YXJnYXplcikNCmxpYnJhcnkoV1JURFN0aWRhbCkNCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeShrYWJsZUV4dHJhKQ0KbGlicmFyeShxdWFudHJlZykNCmxpYnJhcnkoUG9ncm9tY3lEYW55Y2gpDQpgYGANCg0KIyMgRGxhY3plZ28ga3dhbnR5bG93YT8NCg0KRGxhY3plZ28gcG90cnplYnVqZW15IHJlZ3Jlc2ppIGt3YW50eWxvd2VqIChRUik/DQoNClcgc3pjemVnw7Nsbm/Fm2NpLCBRUjoNCg0KLSAgIGplc3Qgb2Rwb3JuYSBuYSBwdW5rdHkgb2RzdGFqxIVjZSBpIHdwxYJ5d293ZQ0KDQotICAgbmllIHpha8WCYWRhIHN0YcWCZWogd2FyaWFuY2ppICh6bmFuZWogamFrbyBob21vc2tlZGFzdHljem5vxZvEhykgZGxhDQogICAgem1pZW5uZWogb2Rwb3dpZWR6aSBsdWIgcmVzenQNCg0KLSAgIG5pZSB6YWvFgmFkYSBub3JtYWxub8WbY2kgYWxlIGfFgsOzd27EhSB6YWxldMSFIFFSIHcgcG9yw7N3bmFuaXUgeiByZWdyZXNqxIUNCiAgICBsaW5pb3fEhSAoTFIpIGplc3QgdG8sIMW8ZSBRUiBiYWRhIHLDs8W8bmUgd2FydG/Fm2NpIHptaWVubmVqIG9kcG93aWVkemksDQogICAgYSBuaWUgdHlsa28gxZtyZWRuacSFLCBpIGRvc3RhcmN6YSB3IHp3acSFemt1IHogdHltIHBlxYJuaWVqc3plZ28gb2JyYXp1DQogICAgendpxIV6a8OzdyBtacSZZHp5IHptaWVubnltaSENCg0KIyMgV3Byb3dhZHplbmllDQoNClJlZ3Jlc2phIGt3YW50eWxvd2EgKGFuZy4gcXVhbnRpbGUgcmVncmVzc2lvbikgem9zdGHFgmEgemFwcm9wb25vd2FuYQ0KcHJ6ZXogS29lbmtlcmEgaSBCYXNzZXR0YSAoMTk3OCkuIFN6Y3plZ8OzbG55IHByenlwYWRlayByZWdyZXNqaQ0Ka3dhbnR5bG93ZWogZGxhIGt3YW50eWxhIHJ6xJlkdSAwLDUgKGN6eWxpIG1lZGlhbnkpIGplc3QgcsOzd25vd2HFvG55DQplc3R5bWF0b3Jvd2kgTEFEIChhbmcuIExlYXN0IEFic29sdXRlIERldmlhdGlvbikgLS0gbWluaW1hbGl6dWplIHN1bcSZDQpiZXp3emdsxJlkbnljaCBixYLEmWTDs3cuXA0KV3Byb3dhZHplbmllIHLDs8W8bnljaCBrd2FudHlsaSByZWdyZXNqaSBkYWplIHBlxYJuaWVqc3p5IG9waXMgcm96a8WCYWTDs3cNCndhcnVua293eWNoIHp3xYJhc3pjemEgdyBwcnp5cGFka3Ugcm96a8WCYWTDs3cgYXN5bWV0cnljem55Y2ggbHViIHVjacSZdHljaC4NCg0KUmVncmVzamEga3dhbnR5bG93YSBqZXN0IGtvbGVqbsSFIHdhcmlhY2rEhSBuYSB0ZW1hdCBuYWptbmllanN6eWNoDQprd2FkcmF0w7N3IFxjaXRlcHtxdWFudGlsZX0uIFN0cmF0xIUgamVzdCB3c3DDs8WCY3p5bm5payAkbF8xJCBmdW5rY2ppOg0KDQokJA0KICAgIFxwaGkodSkgPSBcdGF1XG1heCh1LDApIC0gKDEtXHRhdSlcbWF4KC11LDApID0gXGZyYWN7MX17Mn18dXwgKyBcbGVmdChcdGF1IC0gXGZyYWN7MX17Mn1ccmlnaHQpdSwNCiQkDQoNCmdkemllICRcdGF1IFxpbiAoMCwxKSQgb3puYWN6YSBrb25rcmV0bnkga3dhbnR5bC4gUHJvYmxlbWVtIGphaw0KcG9wcnplZG5pbyBqZXN0IG1pbmltYWxpemFjamEgY2HFgmtvd2l0ZWogc3RyYXR5IHJlc3p0b3dlai4gTW9kZWwgdGVuDQpqZXN0IHBvd3N6ZWNobmllIHN0b3Nvd2FueSB3IGVrb2xvZ2lpLCBvY2hyb25pZSB6ZHJvd2lhIGkgaW5ueWNoDQpkemllZHppbmFjaCwgZ2R6aWUgc2FtYSDFm3JlZG5pYSBuaWUgd3lzdGFyY3phIGRvIHVjaHd5Y2VuaWEgesWCb8W8b255Y2gNCnphbGXFvG5vxZtjaSBtacSZZHp5IHptaWVubnltaS4NCg0KIyMgV3ltYWdhbmlhDQoNCld5bWFnYW5hIGplc3QgamVkbmEgbGljemJvd2Egem1pZW5uYSB6YWxlxbxuYS4gWm1pZW5uYSBwcnpld2lkeXdhbmEgbXVzaQ0KYnnEhyB6bWllbm7EhSBpbG/Fm2Npb3fEhS4gUHJlZHlrdG9yeSBtb2fEhSBiecSHIHptaWVubnltaSBpbG/Fm2Npb3d5bWkgbHViDQpzenR1Y3pueW1pIHptaWVubnltaSB3IHByenlwYWRrdSBwcmVkeWt0b3LDs3cgamFrb8WbY2lvd3ljaC4gQWJ5IG1vxbxuYQ0KYnnFgm8gdXJ1Y2hvbWnEhyBhbmFsaXrEmSwgd3ltYWdhbnkgamVzdCB3eXJheiB3b2xueSBsdWIgY28gbmFqbW5pZWogamVkZW4NCnByZWR5a3Rvci4NCg0KUmVncmVzamEga3dhbnR5bG93YSBuaWUgY3p5bmkgemHFgm/FvGXFhCBkb3R5Y3rEhWN5Y2ggcm96a8WCYWR1IHptaWVubmVqDQpwcnpld2lkeXdhbmVqIGkgamVzdCBvZHBvcm5hIG5hIHdwxYJ5dyBvYnNlcndhY2ppIG9kc3RhasSFY3ljaC4NCg0KQW5hbGl6YSBrd2FudHlsb3dhIGplc3QgcG9rcmV3bmEgcmVncmVzamkgbWV0b2TEhSBuYWptbmllanN6eWNoDQprd2FkcmF0w7N3Lg0KDQojIyBQcnp5a8WCYWQgMS4NCg0KV3lrb3J6eXN0YW15IHByenlrxYJhZCB6IHBha2lldHUgcXVhbnRyZWcuDQoNCkpha2kgamVzdCB6d2nEhXplayBtacSZZHp5IGNhxYJrb3dpdHltIGRvY2hvZGVtIGdvc3BvZGFyc3R3YSBkb21vd2VnbyBhDQpvZHNldGtpZW0gZG9jaG9kw7N3IHd5ZGF0a293YW55Y2ggbmEgxbx5d25vxZvEhz8gUHJhd28gRW5nZWxhIHcgZWtvbm9taWkNCmfFgm9zaSwgxbxlIHcgbWlhcsSZIHd6cm9zdHUgZG9jaG9kw7N3LCBjesSZxZvEhyBkb2Nob2TDs3cgd3lkYXRrb3dhbnljaCBuYQ0Kxbx5d25vxZvEhyBzcGFkYSwgbmF3ZXQgamXFm2xpIHd5ZGF0a2kgbmEgxbx5d25vxZvEhyBiZXp3emdsxJlkbmllIHJvc27EhS4NClN0b3N1asSFYyByZWdyZXNqxJkga3dhbnR5bG93xIUgZG8gdHljaCBkYW55Y2gsIG1vxbxuYSBva3JlxZtsacSHLCBqYWtpZQ0Kd3lkYXRraSBuYSDFvHl3bm/Fm8SHIHBvbm9zaSA5MCUgcm9kemluIChkbGEgMTAwIHJvZHppbiB6IGRhbnltIGRvY2hvZGVtKSwNCmdkeSBuaWUgaW50ZXJlc3VqxIUgbmFzIMWbcmVkbmllIHd5ZGF0a2kgbmEgxbx5d25vxZvEhy4NCg0KRGFuZSwga3TDs3JlIHd5a29yenlzdGFteSAtIHRvIHpiacOzciAiZW5nZWwiIC0gZGFuZSBkb3R5Y3rEhWNlIHd5ZGF0a8OzdyBuYQ0Kxbx5d25vxZvEhy4gSmVzdCB0byB6YmnDs3IgZGFueWNoIHJlZ3Jlc3lqbnljaCBza8WCYWRhasSFY3kgc2nEmSB6IDIzNQ0Kb2JzZXJ3YWNqaSBkb3R5Y3rEhWN5Y2ggZG9jaG9kw7N3IGkgd3lkYXRrw7N3IG5hIMW8eXdub8WbxIcgZGxhIGJlbGdpanNraWNoDQpnb3Nwb2RhcnN0dyBkb21vd3ljaCBrbGFzeSByb2JvdG5pY3plai4NCg0KYGBge3IgZWNobz1GQUxTRX0NCmRhdGEoZW5nZWwpICNkYW5lIA0KcCA8LSBnZ3Bsb3QoZGF0YSA9IGVuZ2VsKSArDQogICAgZ2VvbV9wb2ludChtYXBwaW5nID0gYWVzKHggPSBpbmNvbWUsIHkgPSBmb29kZXhwKSwgY29sb3IgPSAiYmx1ZSIpDQp0YXVzIDwtIGMoMC4xLCAwLjI1LCAwLjUsIDAuNzUsIDAuOTAsIDAuOTUpDQpmaXRzIDwtIGRhdGEuZnJhbWUoDQogICAgY29lZihsbShmb29kZXhwIH4gaW5jb21lLCBkYXRhID0gZW5nZWwpKSwNCiAgICBzYXBwbHkodGF1cywgZnVuY3Rpb24oeCkgY29lZihycShmb3JtdWxhID0gZm9vZGV4cCB+IGluY29tZSwgZGF0YSA9IGVuZ2VsLCB0YXUgPSB4KSkpKQ0KbmFtZXMoZml0cykgPC0gYygiT0xTIiwgc3ByaW50ZigiJFxcdGF1X3slMC4yZn0kIiwgdGF1cykpDQpuZiA8LSBuY29sKGZpdHMpDQpjb2xvcnMgPC0gY29sb3JSYW1wUGFsZXR0ZShjb2xvcnMgPSBjKCJibGFjayIsICJyZWQiKSkobmYpDQpwIDwtIHAgKyBnZW9tX2FibGluZShpbnRlcmNlcHQgPSBmaXRzWzEsIDFdLCBzbG9wZSA9IGZpdHNbMiwgMV0sIGNvbG9yID0gY29sb3JzWzFdLCBsaW5ld2lkdGggPSAxLjUpDQpmb3IgKGkgaW4gc2VxX2xlbihuZilbLTFdKSB7DQogICAgcCA8LSBwICsgZ2VvbV9hYmxpbmUoaW50ZXJjZXB0ID0gZml0c1sxLCBpXSwgc2xvcGUgPSBmaXRzWzIsIGldLCBjb2xvciA9IGNvbG9yc1tpXSkNCn0NCnANCmBgYA0KDQpQb3d5xbxzenkgd3lrcmVzIHByemVkc3Rhd2lhIGRvcGFzb3dhbmllIHJlZ3Jlc2ppIGt3YW50eWxvd2VqIGRsYQ0KJFx0YXUgPSAoMC4xLCAwLjI1LCAwLjUsIDAuNzUsIDAuOTAsIDAuOTUpJC4gRG9wYXNvd2FuaWUgS01OSyB0byBncnViYQ0KY3phcm5hIGxpbmlhLg0KDQpQb25pxbxlaiB6bmFqZHVqZSBzacSZIHRhYmVsYSB6IG9zemFjb3dhbnltaSB3c3DDs8WCY3p5bm5pa2FtaS4NCg0KYGBge3J9DQprbml0cjo6a2FibGUoZml0cywgZm9ybWF0ID0gImh0bWwiLCBjYXB0aW9uID0gIk9zemFjb3dhbmlhIHogS01OSyBvcmF6IGBxdWFudHJlZ2AiKSAlPiUNCiAgICBrYWJsZV9zdHlsaW5nKCJzdHJpcGVkIikgJT4lDQogICAgY29sdW1uX3NwZWMoMTo4LCBiYWNrZ3JvdW5kID0gIiNlY2VjZWMiKQ0KYGBgDQoNCk9rLCBtb8W8ZW15IHRvIHpyb2JpxIcgYmFyZHppZWogcHJ6ZWpyennFm2NpZSBpIHNmb3JtYXRvd2HEhyB3IMWCYWRuZWogdGFiZWxpDQp3eW5pa8OzdzoNCg0KYGBge3IgZWNobz1GQUxTRSwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRSwgcGFnZWQucHJpbnQ9VFJVRX0NCnEyNSA8LSBycShmb29kZXhwIH4gaW5jb21lLCBkYXRhID0gZW5nZWwsIHRhdSA9IDAuMjUpDQpxNTAgPC0gcnEoZm9vZGV4cCB+IGluY29tZSwgZGF0YSA9IGVuZ2VsLCB0YXUgPSAwLjUwKQ0KcTc1IDwtIHJxKGZvb2RleHAgfiBpbmNvbWUsIGRhdGEgPSBlbmdlbCwgdGF1ID0gMC43NSkNCg0KIyBUYWJlbGEgeiBwb3LDs3duYW5pZW0gd3luaWvDs3cgdHJ6ZWNoIG1vZGVsaTogDQoNCnN0YXJnYXplcihxMjUsIHE1MCwgcTc1LCB0aXRsZSA9ICJXeW5pa2kgcmVncmVzamkga3dhbnR5bG93eWNoIiwgdHlwZSA9ICJ0ZXh0IikNCmBgYA0KDQpGaW5hbG5pZSwgemFwcmV6ZW50dWpteSB3ecWCxIVjem5pZSB0ZSAzIG1vZGVsZSBuYSB3eWtyZXNpZToNCg0KYGBge3IgZWNobz1GQUxTRX0NCm15X3FyIDwtIHJxKGZvb2RleHAgfiBpbmNvbWUsIGRhdGEgPSBlbmdlbCwgdGF1ID0gc2VxKDAuMjUsIDAuNzUsIDAuMjUpKQ0KDQppbnRlcmNlcHRfc2xvcGUgPC0gbXlfcXIgJT4lIA0KICBjb2VmKCkgJT4lIA0KICB0KCkgJT4lIA0KICBkYXRhLmZyYW1lKCkgJT4lIA0KICByZW5hbWUoaW50ZXJjZXB0ID0gWC5JbnRlcmNlcHQuLCBzbG9wZSA9IGluY29tZSkgJT4lIA0KICBtdXRhdGUocXVhbnRpbGUgPSByb3cubmFtZXMoLikpDQoNCmdncGxvdCgpICsgDQogIGdlb21fcG9pbnQoZGF0YSA9IGVuZ2VsLCBhZXMoaW5jb21lLCBmb29kZXhwKSwgYWxwaGEgPSAwLjUpICsgDQogIGdlb21fYWJsaW5lKGRhdGEgPSBpbnRlcmNlcHRfc2xvcGUsIGFlcyhpbnRlcmNlcHQgPSBpbnRlcmNlcHQsIHNsb3BlID0gc2xvcGUsIGNvbG9yID0gcXVhbnRpbGUpKSArIA0KICB0aGVtZV9taW5pbWFsKCkgKyANCiAgbGFicyh4ID0gIkRvY2jDs2QiLCB5ID0gIld5ZGF0a2kgbmEgxbx5d25vxZvEhyIsIHRpdGxlID0gIlJlZ3Jlc2plIGt3YW50eWxvd2UgeiB0YXUgPSAwLjI1LCAwLjUwIG9yYXogMC43NSIsIA0KICAgICAgIGNhcHRpb24gPSAixblyw7NkxYJvIGRhbnljaDogS29lbmtlciBhbmQgQmFzc2V0dCAoMTk4MikiKQ0KYGBgDQoNCiMjIFByenlrxYJhZCAyLg0KDQpUdXRhaiBwcnplcHJvd2FkemlteSB0ZXN0eSB1xbx5Y2lhIHBha2lldHUgcXVhbnRyZWcsIHd5a29yenlzdHVqxIVjDQp3YnVkb3dhbnkgemJpw7NyIGRhbnljaCAiKiptdGNhcnMqKiIuIFptaWVubmEgIioqbXBnKioiIG96bmFjemEgc3BhbGFuaWUNCnNhbW9jaG9kw7N3ICgqbWlsZS9nYWxvbiopLg0KDQpaYW1vZHVsZWpteSB6YWxlxbxub8WbxIcgcmVncmVzeWpuxIUgZGxhIHRlaiB6bWllbm5laiBvZCBraWxrdSBwcmVkeWt0b3LDs3cuDQoNCk5hanBpZXJ3IG9zemFjdWpteSByZWdyZXNqxJkgS01OSzoNCg0KYGBge3J9DQprbW5rIDwtIGxtKG1wZyB+IGRpc3AgKyBocCArIGZhY3RvcihhbSkgKyBmYWN0b3IodnMpLCBkYXRhID0gbXRjYXJzKQ0Kc3VtbWFyeShrbW5rKQ0KYGBgDQoNClRlcmF6IG9zemFjdWpteSB3YXJ1bmtvd2UgcmVncmVzamUga3dhbnR5bG93ZSBuYSByw7PFvG55Y2gga3dhbnR5bGFjaCwNCmLFgsSFZCBzdGFuZGFyZG93eSB1enlza2FueSBwcnpleiAqKipib290c3RyYXAqKiouDQoNClphdXdhxbwsIMW8ZSBpc3RuaWVqZSBncmFkaWVudCB3ZSB3c3DDs8WCY3p5bm5pa2FjaCBrd2FudHlsb3d5Y2ggKipocCoqLCBqYWsNCnLDs3duaWXFvCAqKmRpc3AqKi4gWm5hayAqKmRpc3AqKiBvZHdyYWNhIHNpxJksIHLDs3duaWXFvCB3c3DDs8WCY3p5bm5payBuYQ0KY3p5bm5pa3UgKiphbSoqIGplc3QgcsOzxbxueSB3IHphbGXFvG5vxZtjaSBvZCBrd2FudHlsaToNCg0KYGBge3J9DQprd2FudHlsZSA8LSBjKDAuMjUsIDAuNTAsIDAuNzUpDQpyZWdfa3dhbnR5bG93YSA8LSBycShtcGcgfiBkaXNwICsgaHAgKyBmYWN0b3IoYW0pLHRhdSA9IGt3YW50eWxlLGRhdGEgPSBtdGNhcnMpDQpzdW1tYXJ5KHJlZ19rd2FudHlsb3dhLCBzZSA9ICJib290IikNCmBgYA0KDQojIyMgVGVzdHkgd3Nww7PFgmN6eW5uaWvDs3cNCg0KVcW8eWplbXkgZnVua2NqaSBycS5hbm92YSB6IHBha2lldHUgcmVncmVzamkga3dhbnR5bG93ZWosIGFieQ0KcHJ6ZXByb3dhZHppxIcgdGVzdCBXQUxEQS4gUGFtacSZdGFqLCDFvGUgdGVzdCBXQUxEQSBtw7N3aSwgxbxlIGJpb3LEhWMgcG9kDQp1d2FnxJkgbmllb2dyYW5pY3pvbmUgb3N6YWNvd2FuaWEgbW9kZWx1LCBwcnpldGVzdHVqZW15IGhpcG90ZXrEmSB6ZXJvd8SFDQptw7N3acSFY8SFLCDFvGUgd3Nww7PFgmN6eW5uaWtpIHNwZcWCbmlhasSFIHBld25lIGxpbmlvd2Ugb2dyYW5pY3plbmlhLg0KDQpBYnkgasSFIHByemV0ZXN0b3dhxIcsIHXFvHlqZW15IG9iaWVrdHUgendyw7Njb25lZ28geiB1cnVjaG9taWVuaWEgKioqcnEqKioNCnogcsOzxbxueW1pIGxpY3piYW1pIGt3YW50eWxpIGkgdXN0YXdpbXkgb3BjasSZICoqKmpvaW50KioqIG5hIHRydWUgbHViDQpmYWxzZS4gR2R5ICoqKmpvaW50KioqIGplc3QgdHJ1ZTogInLDs3dub8WbxIcgd3Nww7PFgmN6eW5uaWvDs3cga2llcnVua293eWNoDQpwb3dpbm5hIGJ5xIcgd3lrb25hbmEgamFrbyB3c3DDs2xuZSB0ZXN0eSBuYSB3c3p5c3RraWNoIHBhcmFtZXRyYWNoDQpuYWNoeWxlbmlhIiwgZ2R5ICoqKmpvaW50KioqIGplc3QgZmFsc2U6ICJuYWxlxbx5IHpnxYJhc3phxIcgb2RkemllbG5lDQp0ZXN0eSBuYSBrYcW8ZHltIHogcGFyYW1ldHLDs3cgbmFjaHlsZW5pYSIuDQoNClphdXdhxbwsIMW8ZSB0ZXN0eSBrd2FudHlsb3dlIHPEhSB0ZXN0YW1pICJsaW5paSByw7N3bm9sZWfFgmVqIi4gT3puYWN6YSB0bywNCsW8ZSBwb3dpbm5pxZtteSB3eWrEhcSHIHLDs8W8bmUgeC13eXJhenlfd29sbmUgZGxhIGthxbxkZWdvIGt3YW50eWxhLCBwb25pZXdhxbwNCnJlcHJlemVudHVqxIUgb25lIHBvemlvbXkgcm96a8WCYWTDs3cgd2FydW5rb3d5Y2guIEplxZtsaSBqZWRuYWsNCndzcMOzxYJjenlubmlraSBrd2FudHlsaSBkbGEgd3Nww7PFgmN6eW5uaWtvdyBzxIUgdGFraWUgc2FtZSwgdG8gbmllIG1hDQplZmVrdMOzdyBzcGVjeWZpY3pueWNoIGRsYSBrd2FudHlsaSwgd3lzdGFyY3rEhSBlZmVrdHkgxZtyZWRuaWUuDQoNCioqQmFkYW5pZSBzdGF0eXN0eWN6bmVqIHLDs8W8bmljeSBtacSZZHp5IDI1LiBpIDUwLiBrd2FudHlsZW0gd2FydW5rb3d5bToqKg0KDQpCaW9yxIVjIHBvZCB1d2FnxJkgcG93ecW8c3plIG9zemFjb3dhbmlhIGt3YW50eWxpLCByw7PFvG5pY2EgbWnEmWR6eQ0Ka3dhbnR5bGFtaSAwLDI1IGkgMCw1MCBpc3RuaWVqZSwgYWxlIGN6eSBzxIUgb25lIHd5c3RhcmN6YWrEhWNvIGR1xbxlLCBhYnkNCmJ5xIcgc3RhdHlzdHljem5pZSByw7PFvG5lPyBKYWthIGplc3Qgd2FydG/Fm8SHIHA/IFByemVnbMSFZGFqxIVjIHBvbmnFvHN6ZQ0Kd3luaWtpLCBuaWUgc8SFIG9uZSBzdGF0eXN0eWN6bmllIHLDs8W8bmUhDQoNClBvIHBpZXJ3c3plLCBqb2ludCA9IFRSVUUuIFRvIG5pZSBqZXN0IHRlc3Rvd2FuaWUsIGN6eSB3c3DDs8WCY3p5bm5payBuYQ0KZGlzcCBqZXN0IHRha2kgc2FtIGphayB3c3DDs8WCY3p5bm5payBuYSBocC4gVG8gamVzdCB3c3DDs2xuZSB0ZXN0b3dhbmllLA0KY3p5IHdzcMOzxYJjenlubmlraSBkbGEgcsOzxbxueWNoIGt3YW50eWxpIGRpc3AgaSByw7PFvG55Y2gga3dhbnR5bGkgaHAgc8SFDQp0YWtpZSBzYW1lIGRsYSBrYcW8ZGVqIHptaWVubmVqLg0KDQpgYGB7cn0NCmt3YW50eWxlIDwtIGMoMC4yNSwgMC41MCkNCnJlZ19rd2FudHlsb3dhIDwtIHJxKG1wZyB+IGRpc3AgKyBocCArIGZhY3RvcihhbSksdGF1ID0ga3dhbnR5bGUsIGRhdGEgPSBtdGNhcnMpDQphbm92YShyZWdfa3dhbnR5bG93YSwgdGVzdCA9ICJXYWxkIiwgam9pbnQ9VFJVRSkNCmBgYA0KDQpQbyBkcnVnaWUsIGpvaW50ID0gRmFsc2U6DQoNCmBgYHtyfQ0KYW5vdmEocmVnX2t3YW50eWxvd2EsIHRlc3QgPSAiV2FsZCIsIGpvaW50PUZBTFNFKQ0KYGBgDQoNCioqQmFkYW5pZSBzdGF0eXN0eWN6bmVqIHLDs8W8bmljeSBtacSZZHp5IDI1LCA1MCBpIDc1IGt3YW50eWxlbQ0Kd2FydW5rb3d5bToqKg0KDQpQaWVyd3N6eSBrd2FydHlsIGkgbWVkaWFuYSBuaWUgd3lkYWrEhSBzacSZIGJ5xIcgc3RhdHlzdHljem5pZSByw7PFvG5lLCB0ZXJheg0KZG/FgsSFY3p5bXkgdHJ6ZWNpIGt3YXJ0eWwuIEphayB3aWRhxIcgd2N6ZcWbbmllaiwga3dhcnR5bGUgd3Nww7NsbmllDQp3eWthenVqxIUgZ3JhZGllbnQuIFRlcmF6IG1vxbxlbXkgem9iYWN6ecSHLCDFvGUgKipkaXNwKiosICoqaHAqKiBpICoqYW0qKg0Kc8SFIG9kZHppZWxuaWUgc3RhdHlzdHljem5pZSByw7PFvG5lLg0KDQpQbyBwaWVyd3N6ZSwgam9pbnQgPSBUUlVFOg0KDQpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQ0Ka3dhbnR5bGUgPC0gYygwLjI1LCAwLjUwLCAwLjc1KQ0KDQpyZWdfa3dhbnR5bG93YSA8LSBycShtcGcgfiBkaXNwICsgaHAgKyBmYWN0b3IoYW0pLHRhdSA9IGt3YW50eWxlLCBkYXRhID0gbXRjYXJzKQ0KDQphbm92YShyZWdfa3dhbnR5bG93YSwgdGVzdCA9ICJXYWxkIiwgam9pbnQ9VFJVRSkNCmBgYA0KDQpQbyBkcnVnaWUsIGpvaW50ID0gRmFsc2U6DQoNCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQphbm92YShyZWdfa3dhbnR5bG93YSwgdGVzdCA9ICJXYWxkIiwgam9pbnQ9RkFMU0UpDQpgYGANCg0KIyMjIERvYnJvxIcgZG9wYXNvd2FuaWENCg0KTW/FvGVteSBvYmxpY3p5xIcgd3Nww7PFgmN6eW5uaWtpIGRvYnJvY2kgZG9wYXNvd2FuaWEgcmVncmVzamkga3dhbnR5bG93ZWogeg0Kd3lrb3J6eXN0YW5pZW0gcmVzenQgaSByZXN6dCBiZXp3YXJ1bmtvd3ljaDoNCg0KYGBgIHINCmdvb2RmaXQocmVzaWQsIHJlc2lkX25sLCB0YXUpDQpgYGANCg0KTWlhcmEgZG9icm9jaSBkb3Bhc293YW5pYSBkbGEgcmVncmVzamkga3dhbnR5bG93ZWogamVzdCBzemFjb3dhbmEgamFrbyAxDQptaW51cyBzdG9zdW5layBzdW15IG9kY2h5bGXFhCBiZXp3emdsxJlkbnljaCB3IG1vZGVsYWNoIHcgcGXFgm5pDQpzcGFyYW1ldHJ5em93YW55Y2ggZG8gc3VteSBvZGNoeWxlxYQgYmV6d3pnbMSZZG55Y2ggdyB6ZXJvd3ltDQooYmV6d2FydW5rb3d5bSkgbW9kZWx1IGt3YW50eWxvd3ltLg0KDQpXYXJ0b8WbY2kgdGUgc8SFIHByenlkYXRuZSBkbyBwb3LDs3duYcWEIG1pxJlkenkgbW9kZWxhbWkga3dhbnR5bG93eW1pLCBhbGUNCm5pZSBzxIUgcG9yw7N3bnl3YWxuZSB6ZSBzdGFuZGFyZG93eW1pIHdzcMOzxYJjenlubmlrYW1pIGRldGVybWluYWNqaS4gVGUNCm9zdGF0bmllIG9wYXJ0ZSBzxIUgbmEgd2FyaWFuY2ppIG9kY2h5bGXFhCBrd2FkcmF0b3d5Y2gsIG5hdG9taWFzdA0Kd2FydG/Fm2NpIGRvYnJvY2kgZG9wYXNvd2FuaWEgZGxhIHJlZ3Jlc2ppIGt3YW50eWxvd2VqIG9wYXJ0ZSBzxIUgbmENCm9kY2h5bGVuaWFjaCBiZXp3emdsxJlkbnljaC4gV2FydG/Fm2NpIGRvYnJvY2kgZG9wYXNvd2FuaWEgemF3c3plIGLEmWTEhQ0KbW5pZWpzemUgbmnFvCB3YXJ0b8WbY2kgUl4yXi4NCg0KYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0NCiMjIG1vZGVsIGt3YW50eWxvd3kNCm1vZGVsMSA8LSBycShtcGcgfiBkaXNwICsgaHAgKyBmYWN0b3IoYW0pLHRhdSA9IDAuNSwgZGF0YSA9IG10Y2FycykNCnJlc3p0eTEgPC0gcmVzaWQobW9kZWwxKQ0KDQojIyBiZXp3YXJ1bmtvd3kgKHB1c3R5KSBtb2RlbCBrd2FudHlsb3d5DQptb2RlbDIgPC0gcnEobXBnIH4gMSwgdGF1ID0gMC41LGRhdGE9bXRjYXJzKQ0KcmVzenR5MiA8LSByZXNpZChtb2RlbDIpDQoNCmdvb2RmaXQocmVzenR5MSwgcmVzenR5MiwgMC41KQ0KDQojIyByMiBtb2RlbHUgS01OSyBkbGEgcG9yw7N3bmFuaWENCm1vZGVsX2xtIDwtIGxtKG1wZyB+IGRpc3AgKyBocCArIGZhY3RvcihhbSksIGRhdGEgPSBtdGNhcnMpDQoNCnN1bW1hcnkobW9kZWxfbG0pJHIuc3F1YXJlZA0KYGBgDQoNCiMjIFphZGFuaWUNCg0KVGVyYXogV2FzemEga29sZWogOy0pDQoNCldhc3p5bSB6YWRhbmllbSBkemlzaWFqIGplc3QgemFtb2RlbG93YW5pZSAtIHBvcsOzd25hbmllIEtNTksgb3Jheg0KcmVncmVzamkga3dhbnR5bG93ZWogKHLDs8W8bm8tcG96aW9tb3dlaikgZGxhIHptaWVubmVqICJlYXJuaW5ncyIgLQ0Kd3luYWdyb2R6ZW5pYS4NCg0KRG9iaWVyeiBpIHByemV0ZXN0dWogcHJlZHlrdG9yeSwga3dhbnR5bGUgZGxhIG1vZGVsaS4gV3lrb25haiB0ZXN0eQ0KcsOzxbxuaWMgd3Nww7PFgmN6eW5uaWtvdyBkbGEgZmluYWxueWNoIG1vZGVsaS4NCg0KVyBwcnp5cGFka3UgcHJvYmxlbcOzdyAtIG9iZWpyenlqIHZpZGVvIHR1dG9yaWFsICh3xYLEhWN6IHBvbHNraWUgbmFwaXN5KQ0Kb3JheiB3ZWpkxbogbmEgamVnbyBzdHJvbsSZIHplIMW6csOzZMWCYW1pLiBNb8W8ZXN6IHLDs3duaWXFvCB3eWtvcnp5c3RhxIcgdy93DQpwcnp5a8WCYWR5Lg0KDQpgYGB7cn0NCmRhdGEoIkNQU1NXOTI5OCIpDQojID9DUFNTVzkyOTggDQpgYGANCg==