Úvod

Klastrová (zhluková) analýza patrí medzi najpoužívanejšie metódy exploratívnej štatistiky. V praxi sa využíva všade tam, kde je potrebné rozdeliť pozorovania do homogénnych celkov - napríklad pri segmentácii zákazníkov v marketingu, identifikácii podobných krajín v makroekonomických ukazovateľoch, hodnotenízdravotných rizík, klasifikácii biologických vzoriek či v geoinformatike pri zoskupovaní priestorových sobjektov. Jej výhodou je, že pracuje s viacerými premennými naraz a dokáže odhaliť vzory, ktoré by pri samotnom hodnotení jednotlivých ukazovateľov zostali skryté. Správne zvolená metrika vzdialenosti a metóda zhlukovania umožňujú odhaliť skryté vzťahy v dátach, čím poskytujú cenný podklad pre rozhodovanie v rôznych oblastiach aplikovaného výskumu.

My predstavíme zhlukovú analýzu pri analýze údajov niektorých východo- a severoeurópskych krajín z hľadiska niektorých priemerných ukazovateľov charakterizujúcich zdravotný stav obyvateľstva. Budeme využívať údaje za rok 2015. V Tab. 1. uvádzame celú nami používanú databázu.

Table 1.

Hierarchická zhluková analýza pracuje s mierami vzdialenosti medzi pozorovaniami. Aby boli tieto vzdialenosti porovnateľné, je potrebné, aby všetky premenné boli definované na rovnakejškále. Používame pritom tzv. z-škálovanie, pričom transformované \(z\) hodnoty (skóre) vypočítame nasledovne

\[z = \frac{x-\mu}{\sigma}\]

kde \(\mu\) je stredná hodnota a \(\sigma\) je štandardná odchýlka pozorovaní \(x\). Predpokladáme pritom, že súbor údajov už neobsahuje NA hodnoty, ktoré boli ošetrené v predchádzajúcich krokoch.

Touto operáciou získame škálované pozorovania, pričom ich rozloženie je znázornené nasledovne:

Obr. 1.

Tentokrát odľahlé hodnoty nevylúčime, nakoľko definujú konkrétnu krajinu.

Pri zhlukovej analýze je dôležitá korelačná matica premenných. Vysoká korelácia zvýhodňuje pri zhlukovej analýze korelované premenné. Preto pri korelácii nad 0,8 alebo 0.9 vylúčime jednu z korelovaných premenných. V Tab. 2. sa však takáto vysoká korelácia nenachádza, preto sa nemusíme ďalej s problémom zaoberať.

V prípade, ak máme väčší počet významne korelovaných premenných, sa odporúča transformácia pomocou Analýzy hlavných komponentov (Principal Component Analysis)

Tab. 2

                Life.expectancy   BMI   GDP Schooling
Life.expectancy            1.00 -0.48  0.79      0.70
BMI                       -0.48  1.00 -0.57     -0.46
GDP                        0.79 -0.57  1.00      0.67
Schooling                  0.70 -0.46  0.67      1.00

Každej krajine zodpovedá jeden riadok pozorovaní. Vzdialenosť medzi krajinami \(i\) a \(j\) je:

\[ d^{ij} = \sqrt{\sum_k (x^i_k - x^j_k)^2} \] kde \(x^i_k\) je \(k\)ta premenná vstupujúca do výpočtu (Life.expectancy, BMI, GDP, Schooling) krajiny \(i\). Tento typ vzdialenosti nazývame aj Euklidovská vzdialenosť. Vzdialenosti medzi jednotlivými krajinami sa súhrnne vyjadrujú aj v matici vzdialenosti, čo v našom prípade je uvedené v Tab.3.. Analýzou tejto tabuľky zistíme, že najväčšia vzdialenosť je medzi Rumunskom a Dánskom, zatiaľ čo malá vzdialenosť je medzi Rumunskom a Bulharskom. Oba prípady vieme vysvetliť polohou týchto krajín, podnebím, ako aj históriou, ktorá je podobná, alebo rozdielna.

Tab. 3

      Aus  Bul  Cro Den.  Est  Fin  Hun  Lat  Lit  Mon  Pol Roma  Ser  Slo  Swe
Bul  4.18                                                                      
Cro  3.15 1.16                                                                 
Den. 3.05 5.76 4.82                                                            
Est  1.98 2.78 1.85 3.57                                                       
Fin  2.02 3.31 2.44 2.59 1.86                                                  
Hun  3.58 0.75 0.70 5.02 2.15 2.60                                             
Lat  2.67 2.01 1.38 4.40 0.96 2.34 1.49                                        
Lit  3.09 1.88 1.50 4.40 1.33 2.32 1.32 0.67                                   
Mon  3.00 1.59 0.92 5.00 1.58 2.81 1.31 0.95 1.40                              
Pol  2.57 2.11 1.23 3.95 0.78 1.93 1.45 0.75 0.90 1.20                         
Roma 4.55 0.60 1.56 6.09 3.29 3.59 1.19 2.57 2.42 2.11 2.62                    
Ser  2.97 2.33 1.77 5.40 1.97 3.37 2.20 1.53 2.13 0.94 1.92 2.80               
Slo  2.46 4.15 3.09 2.38 2.46 1.80 3.48 3.21 3.33 3.41 2.56 4.43 3.88          
Swe  1.04 4.14 3.18 2.93 2.44 1.61 3.54 2.99 3.27 3.29 2.82 4.41 3.45 2.41     
Ukr  3.57 1.92 1.82 5.51 2.00 3.44 1.81 1.14 1.39 1.10 1.75 2.48 1.32 4.25 3.96

Princíp hierarchického zhlukovania (Wardova metóda)

Zhlukovanie v prípade Wardovej metódy prebieha zdola smerom nahor, t.j. začíname s jednočlennými klastrami, ktoré postupne zlučujeme. Táto metóda patrí teda medzi aglomeratívne hierarchické metódy. Minimalizuje nárast vnútornej variability pri spojení dvoch klastrov, pričom využíva nasledovné výpočty:

Wardová metóda minimalizuje sumu štvorcov chýb (Error sum of Squares - ESS)

\[ESS(C) = \sum_{i \in C} \lVert x_i - \bar{x}_C \rVert^2\] kde \(C\) je zvažovaný klaster (zhluk). V každom kroku zlučovania dvoch klasterov, Wardova metóda hľadá minimálny prírastok sumy štvorcov chýb (\(\Delta ESS\)), pričom

\[\Delta ESS = ESS(A \cup B) - ESS(A) - ESS(B)\] Dvojica zhlukov, ktoré tejto podmienke o minimalizácii vyhovuje, je následne zlúčená a prechádza sa k ďalšiemu kkroku. To spravidla vedie k vytváraniu homogénnych zhlukov, pričom nedochádza k odtrhávaniu odľahlých hodnôt tak, ako pri iných zhlukovacích metódach.

Obr. 2. Hierarchické zhlukovanie - dendogram. Červená čiara určuje rez definujúci tri klastre.

Tab.4. Príslušnosť krajín do klastrov.

Vykonaná klastrová analýza klasifikuje krajiny do troch klastrov. Klaster 1 vytvárajú všetky vyspelé krajiny západu + Slovinsko, ktoré je najvyspelejšou postkomunistickou krajinou. Klaster 2 tvoria krajiny z kompaktného regiónu balkánu + Maďarsko. Tretí klaster tvoria tvoria všetky postkomunistické krajiny Pobaltia a Poľsko a tiež ďalší opäť krajiny tradičného Západu. Výnimku tvorí dvojčlenný klaster Švédska a najvyspelejšej postkomunistickej krajiny - Slovinska. Tretí klaster tvoria Poľsko a pobaltské štáty a tiež susediace Srbsko a Čierna Hora ako aj Ukrajina.

Deskriptívne štatistiky výsledkov

Na základe Tab. 5 môžeme konštatovať, že vnútroklastrová variabilita je dostatočne nízka u všetkých premenných. Výnimku tvorí Schooling, ktorý sa nejaví byť tak dobrým separátorom, ako ostatné zvažované premenné. Jeho prípadné vylúčenie by teda zrejme nezmenilo podstatne klasterovú klasifikáciu.

Tab. 5. Vysvetlenie vnútroklastrovej variability z hľadiska jednotlivých premenných

Tab. 6. Centroidy - priemerné hodnoty sledovaných premenných

Prvý klaster je charakterizovaný vysokým stupňom ekonomického rozvoja, ako aj vysokou očakávanou dĺžkou dožitia. druhý a tretí klaster sa na seba podobajú, pričom jediným signifikantným rozdielom je BMI, ktorý je v prípade druhého klastra vyšší, ako v treťom klastri.

Záver

Predložená analýza sa zaoberá zdravotným stavom obyvateľstva vybraných členských štátov EU v závislosti na priemerných hodnotách vybraných zdravotných charakteristík. Klasifikuje krajiny do troch klastrov - pričom klastre sa do značnej miery prekrývajú s ich stupňom ekonomického rozvoja, histórie a geografickej blízkosti. Uvedená analýza môže umožniť Európskej komisii vypisovať problémovo zamerané projektové výzvy cielené na štáty podľa ich príslušnosti ku klasterom.

LS0tCnRpdGxlOiAiWmhsdWtvdsOhIGFuYWzDvXphIChrbGFzdGVyIEFuYWx5c2lzKSIKYXV0aG9yOiAiVmxhZGltw61yIEdhemRhICh6YSBwb21vY2kgQ2hhdEdQVCkiCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCi0tLS0tLS0tLQoKYGBge3Igc2V0dXAxLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQoCiAgZWNobyAgICA9IFRSVUUsICAgIyBkbyBub3Qgc2hvdyBjb2RlCiAgbWVzc2FnZSA9IFRSVUUsICAgIyBzdXBwcmVzcyBwYWNrYWdlL3N5c3RlbSBtZXNzYWdlcwogIHdhcm5pbmcgPSBGQUxTRSwgICAjIHN1cHByZXNzIHdhcm5pbmdzCiAgZXJyb3IgICA9IEZBTFNFICAgICMgc3VwcHJlc3MgZXJyb3Igb3V0cHV0CikKYGBgCgojIyDDmnZvZAoKS2xhc3Ryb3bDoSAoemhsdWtvdsOhKSBhbmFsw716YSBwYXRyw60gbWVkemkgbmFqcG91xb7DrXZhbmVqxaFpZSBtZXTDs2R5IGV4cGxvcmF0w612bmVqIMWhdGF0aXN0aWt5LiBWIHByYXhpIHNhIHZ5dcW+w612YSB2xaFhZGUgdGFtLCBrZGUgamUgcG90cmVibsOpIHJvemRlbGnFpSBwb3pvcm92YW5pYSBkbyBob21vZ8Opbm55Y2ggY2Vsa292IC0gbmFwcsOta2xhZCBwcmkgc2VnbWVudMOhY2lpIHrDoWthem7DrWtvdiB2IG1hcmtldGluZ3UsIGlkZW50aWZpa8OhY2lpIHBvZG9ibsO9Y2gga3JhasOtbiB2IG1ha3JvZWtvbm9taWNrw71jaCB1a2F6b3ZhdGXEvm9jaCwgaG9kbm90ZW7DrXpkcmF2b3Ruw71jaCByaXrDrWssIGtsYXNpZmlrw6FjaWkgYmlvbG9naWNrw71jaCB2em9yaWVrIMSNaSB2IGdlb2luZm9ybWF0aWtlIHByaSB6b3NrdXBvdmFuw60gcHJpZXN0b3JvdsO9Y2ggc29iamVrdG92LiBKZWogdsO9aG9kb3UgamUsIMW+ZSBwcmFjdWplIHMgdmlhY2Vyw71taSBwcmVtZW5uw71taSBuYXJheiBhIGRva8Ohxb5lIG9kaGFsacWlIHZ6b3J5LCBrdG9yw6kgYnkgcHJpIHNhbW90bm9tIGhvZG5vdGVuw60gamVkbm90bGl2w71jaCB1a2F6b3ZhdGXEvm92IHpvc3RhbGkgc2tyeXTDqS4gU3Byw6F2bmUgenZvbGVuw6EgbWV0cmlrYSB2emRpYWxlbm9zdGkgYSBtZXTDs2RhIHpobHVrb3ZhbmlhIHVtb8W+xYh1asO6IG9kaGFsacWlIHNrcnl0w6kgdnrFpWFoeSB2IGTDoXRhY2gsIMSNw61tIHBvc2t5dHVqw7ogY2VubsO9IHBvZGtsYWQgcHJlIHJvemhvZG92YW5pZSB2IHLDtHpueWNoIG9ibGFzdGlhY2ggYXBsaWtvdmFuw6lobyB2w71za3VtdS4KCk15IHByZWRzdGF2w61tZSB6aGx1a292w7ogYW5hbMO9enUgcHJpIGFuYWzDvXplIMO6ZGFqb3Ygbmlla3RvcsO9Y2ggdsO9Y2hvZG8tIGEgc2V2ZXJvZXVyw7Nwc2t5Y2gga3JhasOtbiB6IGjEvmFkaXNrYSBuaWVrdG9yw71jaCBwcmllbWVybsO9Y2ggdWthem92YXRlxL5vdiBjaGFyYWt0ZXJpenVqw7pjaWNoIHpkcmF2b3Ruw70gc3RhdiBvYnl2YXRlxL5zdHZhLiBCdWRlbWUgdnl1xb7DrXZhxaUgw7pkYWplIHphIHJvayAyMDE1LiBWICoqVGFiLiAxLioqIHV2w6FkemFtZSBjZWzDuiBuYW1pIHBvdcW+w612YW7DuiBkYXRhYsOhenUuCgpgYGB7ciBzZXR1cDIsIG1lc3NhZ2U9RkFMU0V9CmxpYnJhcnkoa25pdHIpCmxpYnJhcnkoa2FibGVFeHRyYSkKYGBgCgoKYGBge3J9CnJtKGxpc3Q9bHMoKSkKdWRhamUgPC0gcmVhZC5jc3YoInVkYWplL0xpZmVfRXhwZWN0YW5jeV9EYXRhLmNzdiIsIHN0cmluZ3NBc0ZhY3RvcnMgPSBGQUxTRSkKCnVkYWplMjAxNSA8LSBzdWJzZXQodWRhamUsIFllYXIgPT0gMjAxNSkKCnVkYWplMjAxNSA8LSBzdWJzZXQodWRhamUyMDE1LAogIENvdW50cnkgPT0gIlBvbGFuZCIgfCBDb3VudHJ5ID09ICJIdW5nYXJ5IiB8IENvdW50cnkgPT0gIkxhdHZpYSIgfAogIENvdW50cnkgPT0gIkxpdGh1YW5pYSIgfCBDb3VudHJ5ID09ICJDcm9hdGlhIiB8IENvdW50cnkgPT0gIlNsb3ZlbmlhIiB8CiAgQ291bnRyeSA9PSAiQXVzdHJpYSIgfCBDb3VudHJ5ID09ICJTZXJiaWEiIHwgQ291bnRyeSA9PSAiTW9udGVuZWdybyIgfAogIENvdW50cnkgPT0gIlVrcmFpbmUiIHwgQ291bnRyeSA9PSAiQnVsZ2FyaWEiIHwgQ291bnRyeSA9PSAiUm9tYW5pYSIgfAogIENvdW50cnkgPT0gIk1vbGRvdmEiIHwgQ291bnRyeSA9PSAiRmlubGFuZCIgfCBDb3VudHJ5ID09ICJTd2VkZW4iIHwKICBDb3VudHJ5ID09ICJEZW5tYXJrIiB8IENvdW50cnkgPT0gIkVzdG9uaWEiCikKCnVkYWplMjAxNSA8LSB1ZGFqZTIwMTVbLCBjKCJDb3VudHJ5IiwgIlllYXIiLCAiTGlmZS5leHBlY3RhbmN5IiwgIkJNSSIsICJHRFAiLCAiU2Nob29saW5nIildCnJvd25hbWVzKHVkYWplMjAxNSkgPC0gdWRhamUyMDE1JENvdW50cnkKdWRhamUyMDE1JENvdW50cnkgPC0gTlVMTAp1ZGFqZTIwMTUgPC0gc3Vic2V0KHVkYWplMjAxNSwgc2VsZWN0ID0gLVllYXIpCnVkYWplMjAxNSRHRFAgPC0gYyg0MzY2NS45NDcsNjk5My40NzcsMTE1NzkuNjY3LDUzMTQ2LjQ0LDE3NzQ5LjI5LDQyNDUzLjk3LDEyMzY1LjYyNiwxMzY2Ni41ODMsMTQyNTIuNDI5LDY0NjEuMTkzLDEyNTY1Ljk4OCw4OTU4Ljc4OSw1MjM3LjI1NSwyNzI5OC42NCw1NTg1Mi41OCwyMTI0LjY2MykKdWRhamUyMDE1JEJNSSA8LSBjKDU3LjYsIDY1LjcsIDYzLjcsIDU4LjgsIDU5LjksIDYyLjEsIDY0LjgsIDYxLjIsIDYyLjQsIDYxLjgsIDYxLjcsICA2NywgIDYwLCAgNjEsIDU5LjUsIDYxLjMpCmBgYAoKCioqVGFibGUgMS4qKgpgYGB7cn0KdWRhamUyMDE1CmBgYAoKSGllcmFyY2hpY2vDoSB6aGx1a292w6EgYW5hbMO9emEgcHJhY3VqZSBzIG1pZXJhbWkgdnpkaWFsZW5vc3RpIG1lZHppIHBvem9yb3ZhbmlhbWkuIEFieSBib2xpIHRpZXRvIHZ6ZGlhbGVub3N0aSBwb3Jvdm5hdGXEvm7DqSwgamUgcG90cmVibsOpLCBhYnkgdsWhZXRreSBwcmVtZW5uw6kgYm9saSBkZWZpbm92YW7DqSBuYSByb3ZuYWtlasWha8OhbGUuIFBvdcW+w612YW1lIHByaXRvbSB0enYuIHotxaFrw6Fsb3ZhbmllLCBwcmnEjW9tIHRyYW5zZm9ybW92YW7DqSAkeiQgaG9kbm90eSAoc2vDs3JlKSB2eXBvxI3DrXRhbWUgbmFzbGVkb3ZuZQoKJCR6ID0gXGZyYWN7eC1cbXV9e1xzaWdtYX0kJAoKa2RlICRcbXUkIGplIHN0cmVkbsOhIGhvZG5vdGEgYSAkXHNpZ21hJCBqZSDFoXRhbmRhcmRuw6Egb2RjaMO9bGthIHBvem9yb3ZhbsOtICR4JC4gUHJlZHBva2xhZMOhbWUgcHJpdG9tLCDFvmUgc8O6Ym9yIMO6ZGFqb3YgdcW+IG5lb2JzYWh1amUgTkEgaG9kbm90eSwga3RvcsOpIGJvbGkgb8WhZXRyZW7DqSB2IHByZWRjaMOhZHphasO6Y2ljaCBrcm9rb2NoLgoKVG91dG8gb3BlcsOhY2lvdSB6w61za2FtZSDFoWvDoWxvdmFuw6kgcG96b3JvdmFuaWEsIHByacSNb20gaWNoIHJvemxvxb5lbmllIGplIHpuw6F6b3JuZW7DqSBuYXNsZWRvdm5lOgoKCmBgYHtyfQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KIyMgMSkgUHLDrXByYXZhIMO6ZGFqb3YgYSBkYXRhLmZyYW1lIHNvIMWhbMOhbG92YW7DvW1pIMO6ZGFqbWkKIyMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Cgp1ZGFqZV9jb21wbGV0ZSA8LSBuYS5vbWl0KHVkYWplMjAxNSkKdWRhamVfc2NhbGVkIDwtIHNjYWxlKHVkYWplX2NvbXBsZXRlKQpgYGAKCgoqKk9ici4gMS4qKgpgYGB7ciBib3hwbG90cywgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRSwgZmlnLnNob3c9J2hvbGQnfQpudW1fdmFycyA8LSBhcy5kYXRhLmZyYW1lKHVkYWplX3NjYWxlZCkKbnVtX3Bsb3RzIDwtIG5jb2wobnVtX3ZhcnMpCgpwYXIobWZyb3cgPSBjKGNlaWxpbmcoc3FydChudW1fcGxvdHMpKSwgY2VpbGluZyhudW1fcGxvdHMgLyBjZWlsaW5nKHNxcnQobnVtX3Bsb3RzKSkpKSkKcGFyKG1hciA9IGMoNCwgNCwgMiwgMSkpCgpmb3IgKGNvbCBpbiBuYW1lcyhudW1fdmFycykpIHsKICBib3hwbG90KG51bV92YXJzW1tjb2xdXSwKICAgICAgICAgIG1haW4gPSBjb2wsCiAgICAgICAgICBjb2wgPSAibGlnaHRibHVlIiwKICAgICAgICAgIGhvcml6b250YWwgPSBUUlVFKQp9CgptdGV4dCgiQm94cGxvdHkgbnVtZXJpY2vDvWNoIHByZW1lbm7DvWNoIChyb2sgMjAxNSkiLCBvdXRlciA9IFRSVUUsIGNleCA9IDEuMywgZm9udCA9IDIpCmBgYAoKClRlbnRva3LDoXQgb2TEvmFobMOpIGhvZG5vdHkgbmV2eWzDusSNaW1lLCBuYWtvxL5rbyBkZWZpbnVqw7oga29ua3LDqXRudSBrcmFqaW51LiAKCgoKUHJpIHpobHVrb3ZlaiBhbmFsw716ZSBqZSBkw7RsZcW+aXTDoSBrb3JlbGHEjW7DoSBtYXRpY2EgcHJlbWVubsO9Y2guIFZ5c29rw6Ega29yZWzDoWNpYSB6dsO9aG9kxYh1amUgcHJpIHpobHVrb3ZlaiBhbmFsw716ZSBrb3JlbG92YW7DqSBwcmVtZW5uw6kuIFByZXRvIHByaSBrb3JlbMOhY2lpIG5hZCAwLDggYWxlYm8gMC45IHZ5bMO6xI1pbWUgamVkbnUgeiBrb3JlbG92YW7DvWNoIHByZW1lbm7DvWNoLiBWICoqVGFiLiAyLioqIHNhIHbFoWFrIHRha8OhdG8gdnlzb2vDoSBrb3JlbMOhY2lhIG5lbmFjaMOhZHphLCBwcmV0byBzYSBuZW11c8OtbWUgxI9hbGVqIHMgcHJvYmzDqW1vbSB6YW9iZXJhxaUuIAoKPiBWIHByw61wYWRlLCBhayBtw6FtZSB2w6TEjcWhw60gcG/EjWV0IHbDvXpuYW1uZSBrb3JlbG92YW7DvWNoIHByZW1lbm7DvWNoLCBzYSBvZHBvcsO6xI1hIHRyYW5zZm9ybcOhY2lhIHBvbW9jb3UgQW5hbMO9enkgaGxhdm7DvWNoIGtvbXBvbmVudG92IChQcmluY2lwYWwgQ29tcG9uZW50IEFuYWx5c2lzKSAKCioqVGFiLiAyKioKYGBge3J9CmNvcl9tYXQgPC0gY29yKHVkYWplX3NjYWxlZCwgdXNlPSJwYWlyd2lzZS5jb21wbGV0ZS5vYnMiKQpjb3JfbWF0IDwtIHJvdW5kKGNvcl9tYXQsMikKcHJpbnQoY29yX21hdCkKYGBgCkthxb5kZWoga3JhamluZSB6b2Rwb3ZlZMOhIGplZGVuIHJpYWRvayBwb3pvcm92YW7DrS4gVnpkaWFsZW5vc8WlIG1lZHppIGtyYWppbmFtaSAkaSQgYSAkaiQgamU6CgokJApkXntpan0gPSBcc3FydHtcc3VtX2sgKHheaV9rIC0geF5qX2spXjJ9CiQkCmtkZSAkeF5pX2skIGplICRrJHRhIHByZW1lbm7DoSB2c3R1cHVqw7pjYSBkbyB2w71wb8SNdHUgKExpZmUuZXhwZWN0YW5jeSwgQk1JLCBHRFAsIFNjaG9vbGluZykga3JhamlueSAkaSQuICBUZW50byB0eXAgdnpkaWFsZW5vc3RpIG5hesO9dmFtZSBhaiBFdWtsaWRvdnNrw6EgdnpkaWFsZW5vc8WlLiBWemRpYWxlbm9zdGkgbWVkemkgamVkbm90bGl2w71taSBrcmFqaW5hbWkgc2Egc8O6aHJubmUgdnlqYWRydWrDuiBhaiB2IG1hdGljaSB2emRpYWxlbm9zdGksIMSNbyB2IG5hxaFvbSBwcsOtcGFkZSBqZSB1dmVkZW7DqSB2ICoqVGFiLjMuKiouIEFuYWzDvXpvdSB0ZWp0byB0YWJ1xL5reSB6aXN0w61tZSwgxb5lIG5hanbDpMSNxaFpYSB2emRpYWxlbm9zxaUgamUgbWVkemkgUnVtdW5za29tIGEgRMOhbnNrb20sIHphdGlhxL4gxI1vIG1hbMOhIHZ6ZGlhbGVub3PFpSBqZSBtZWR6aSBSdW11bnNrb20gYSBCdWxoYXJza29tLiBPYmEgcHLDrXBhZHkgdmllbWUgdnlzdmV0bGnFpSBwb2xvaG91IHTDvWNodG8ga3JhasOtbiwgcG9kbmViw61tLCBha28gYWogaGlzdMOzcmlvdSwga3RvcsOhIGplIHBvZG9ibsOhLCBhbGVibyByb3pkaWVsbmEuCgoqKlRhYi4gMyoqCgpgYGB7cn0KIyMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQojIyAzKSBEaXN0YW5jZSBtYXRyaXgKIyMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQpyb3duYW1lcyh1ZGFqZV9zY2FsZWQpIDwtIGMoIkF1cyIsICAgICJCdWwiLCAgICJDcm8iLCAgICAiRGVuLiIsICAgICJFc3QiLCAgICAiRmluIiwgICAgIkh1biIsICAgICJMYXQiLCAgICAgIkxpdCIsICAiTW9uIiwgIlBvbCIsICAgIAoiUm9tYSIsICAgICJTZXIiLCAgICAgIlNsbyIsICAgIlN3ZSIsICAgICAiVWtyIikKZGlzdF9tYXQgPC0gcm91bmQoZGlzdCh1ZGFqZV9zY2FsZWQsIG1ldGhvZCA9ICJldWNsaWRlYW4iKSwgMikKZGlzdF9tYXQKYGBgCgojIyBQcmluY8OtcCBoaWVyYXJjaGlja8OpaG8gemhsdWtvdmFuaWEgKFdhcmRvdmEgbWV0w7NkYSkKClpobHVrb3ZhbmllIHYgcHLDrXBhZGUgV2FyZG92ZWogbWV0w7NkeSBwcmViaWVoYSB6ZG9sYSBzbWVyb20gbmFob3IsIHQuai4gemHEjcOtbmFtZSBzIGplZG5vxI1sZW5uw71taSBrbGFzdHJhbWksIGt0b3LDqSBwb3N0dXBuZSB6bHXEjXVqZW1lLiBUw6F0byBtZXTDs2RhIHBhdHLDrSB0ZWRhIG1lZHppIGFnbG9tZXJhdMOtdm5lIGhpZXJhcmNoaWNrw6kgbWV0w7NkeS4gTWluaW1hbGl6dWplIG7DoXJhc3Qgdm7DunRvcm5laiB2YXJpYWJpbGl0eSBwcmkgc3BvamVuw60gZHZvY2gga2xhc3Ryb3YsIHByacSNb20gdnl1xb7DrXZhIG5hc2xlZG92bsOpIHbDvXBvxI10eToKCldhcmRvdsOhIG1ldMOzZGEgbWluaW1hbGl6dWplIHN1bXUgxaF0dm9yY292IGNow71iIChFcnJvciBzdW0gb2YgU3F1YXJlcyAtIEVTUykKCiQkRVNTKEMpID0gXHN1bV97aSBcaW4gQ30gXGxWZXJ0IHhfaSAtIFxiYXJ7eH1fQyBcclZlcnReMiQkCmtkZSAkQyQgamUgenZhxb5vdmFuw70ga2xhc3RlciAoemhsdWspLiBWIGthxb5kb20ga3Jva3Ugemx1xI1vdmFuaWEgZHZvY2gga2xhc3Rlcm92LCBXYXJkb3ZhIG1ldMOzZGEgaMS+YWTDoSBtaW5pbcOhbG55IHByw61yYXN0b2sgc3VteSDFoXR2b3Jjb3YgY2jDvWIgKCRcRGVsdGEgRVNTJCksIHByacSNb20KCiQkXERlbHRhIEVTUyA9IEVTUyhBIFxjdXAgQikgLSBFU1MoQSkgLSBFU1MoQikkJApEdm9qaWNhIHpobHVrb3YsIGt0b3LDqSB0ZWp0byBwb2RtaWVua2UgbyBtaW5pbWFsaXrDoWNpaSB2eWhvdnVqZSwgamUgbsOhc2xlZG5lIHpsw7rEjWVuw6EgYSBwcmVjaMOhZHphIHNhIGsgxI9hbMWhaWVtdSBra3Jva3UuIFRvIHNwcmF2aWRsYSB2ZWRpZSBrIHZ5dHbDoXJhbml1IGhvbW9nw6lubnljaCB6aGx1a292LCBwcmnEjW9tIG5lZG9jaMOhZHphIGsgb2R0cmjDoXZhbml1IG9kxL5haGzDvWNoIGhvZG7DtHQgdGFrLCBha28gcHJpIGluw71jaCB6aGx1a292YWPDrWNoIG1ldMOzZGFjaC4KCgoqKk9ici4gMi4qKiBIaWVyYXJjaGlja8OpIHpobHVrb3ZhbmllIC0gZGVuZG9ncmFtLiDEjGVydmVuw6EgxI1pYXJhIHVyxI11amUgcmV6IGRlZmludWrDumNpIHRyaSBrbGFzdHJlLgpgYGB7cn0KIyMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQojIyA0KSBIaWVyYXJjaGljYWwga2xhc3RlcmluZwojIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09CgpoYyA8LSBoY2x1c3QoZGlzdF9tYXQsIG1ldGhvZCA9ICJ3YXJkLkQyIikKCnBsb3QoaGMsIGxhYmVscyA9IHJvd25hbWVzKHVkYWplX3NjYWxlZCksCiAgICAgbWFpbiA9ICJIaWVyYXJjaGljYWwga2xhc3RlcmluZyBvZiBjb3VudHJpZXMgKFdhcmQuRDIpIiwKICAgICB4bGFiID0gIiIsIHN1YiA9ICIiKQoKayA8LSAzCmhfY3V0IDwtIGhjJGhlaWdodFtsZW5ndGgoaGMkaGVpZ2h0KSAtIChrIC0gMSldCmFibGluZShoID0gaF9jdXQsIGNvbCA9ICJyZWQiLCBsd2QgPSAyLCBsdHkgPSAyKQoKa2xhc3Rlcl9tZW1iZXJzaGlwIDwtIGN1dHJlZShoYywgayA9IGspCgp1ZGFqZV9rbGFzdGVycyA8LSBkYXRhLmZyYW1lKAogIENvdW50cnkgPSByb3duYW1lcyh1ZGFqZV9jb21wbGV0ZSksCiAgdWRhamVfY29tcGxldGUsCiAga2xhc3RlciA9IGZhY3RvcihrbGFzdGVyX21lbWJlcnNoaXApCikKYGBgCgoqKlRhYi40LioqICBQcsOtc2x1xaFub3PFpSBrcmFqw61uIGRvIGtsYXN0cm92LgpgYGB7cn0KZGF0YV9wcmFjIDwtIGRhdGEuZnJhbWUoY2JpbmQodWRhamVfa2xhc3RlcnMkQ291bnRyeSwgdWRhamVfa2xhc3RlcnMka2xhc3RlcikpCmNvbG5hbWVzKGRhdGFfcHJhYykgPC0gYygiQ291bnRyeSIsImtsYXN0ZXIiKQpkYXRhX3ByYWMKYGBgCgpWeWtvbmFuw6Ega2xhc3Ryb3bDoSBhbmFsw716YSBrbGFzaWZpa3VqZSBrcmFqaW55IGRvIHRyb2NoIGtsYXN0cm92LiBLbGFzdGVyIDEgdnl0dsOhcmFqw7ogdsWhZXRreSB2eXNwZWzDqSBrcmFqaW55IHrDoXBhZHUgKyBTbG92aW5za28sIGt0b3LDqSBqZSBuYWp2eXNwZWxlasWhb3UgcG9zdGtvbXVuaXN0aWNrb3Uga3Jhamlub3UuIEtsYXN0ZXIgMiB0dm9yaWEga3JhamlueSB6IGtvbXBha3Ruw6lobyByZWdpw7NudSBiYWxrw6FudSArIE1hxI9hcnNrby4gVHJldMOtIGtsYXN0ZXIgdHZvcmlhICB0dm9yaWEgdsWhZXRreSBwb3N0a29tdW5pc3RpY2vDqSBrcmFqaW55IFBvYmFsdGlhIGEgUG/EvnNrbyBhIHRpZcW+ICDEj2FsxaHDrSBvcMOkxaUga3JhamlueSB0cmFkacSNbsOpaG8gWsOhcGFkdS4gVsO9bmlta3UgdHZvcsOtIGR2b2rEjWxlbm7DvSBrbGFzdGVyIMWgdsOpZHNrYSBhIG5hanZ5c3BlbGVqxaFlaiBwb3N0a29tdW5pc3RpY2tlaiBrcmFqaW55IC0gU2xvdmluc2thLiBUcmV0w60ga2xhc3RlciB0dm9yaWEgUG/EvnNrbyBhIHBvYmFsdHNrw6kgxaF0w6F0eSBhIHRpZcW+IHN1c2VkaWFjZSBTcmJza28gYSDEjGllcm5hIEhvcmEgYWtvIGFqIFVrcmFqaW5hLgoKIyMgRGVza3JpcHTDrXZuZSDFoXRhdGlzdGlreSB2w71zbGVka292CgpOYSB6w6FrbGFkZSAqKlRhYi4gNSoqIG3DtMW+ZW1lIGtvbsWhdGF0b3ZhxaUsIMW+ZSB2bsO6dHJva2xhc3Ryb3bDoSB2YXJpYWJpbGl0YSBqZSBkb3N0YXRvxI1uZSBuw616a2EgdSB2xaFldGvDvWNoIHByZW1lbm7DvWNoLiBWw71uaW1rdSB0dm9yw60gU2Nob29saW5nLCBrdG9yw70gc2EgbmVqYXbDrSBiecWlIHRhayBkb2Jyw71tIHNlcGFyw6F0b3JvbSwgYWtvIG9zdGF0bsOpIHp2YcW+b3ZhbsOpIHByZW1lbm7DqS4gSmVobyBwcsOtcGFkbsOpIHZ5bMO6xI1lbmllIGJ5IHRlZGEgenJlam1lIG5lem1lbmlsbyBwb2RzdGF0bmUga2xhc3Rlcm92w7oga2xhc2lmaWvDoWNpdS4KCgoqKlRhYi4gNS4qKiBWeXN2ZXRsZW5pZSB2bsO6dHJva2xhc3Ryb3ZlaiB2YXJpYWJpbGl0eSB6IGjEvmFkaXNrYSBqZWRub3RsaXbDvWNoIHByZW1lbm7DvWNoCgpgYGB7cn0KIyMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQojIyA1KSBWYXJpYWJpbGl0eSBtZWFzdXJlcwojIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09Cgpzc3EgPC0gZnVuY3Rpb24oeCwgbSkgc3VtKCh4IC0gbSleMikKCnZhcl9uYW1lcyA8LSBjb2xuYW1lcyh1ZGFqZV9zY2FsZWQpCgpUU1MgPC0gc2FwcGx5KHZhcl9uYW1lcywgZnVuY3Rpb24odikgc3NxKHVkYWplX3NjYWxlZFssIHZdLCBtZWFuKHVkYWplX3NjYWxlZFssIHZdKSkpCgpXU1MgPC0gc2FwcGx5KHZhcl9uYW1lcywgZnVuY3Rpb24odikgewogIHggPC0gdWRhamVfc2NhbGVkWywgdl0KICB0YXBwbHkoeCwga2xhc3Rlcl9tZW1iZXJzaGlwLCBmdW5jdGlvbih6KSBzc3EoeiwgbWVhbih6KSkpIHw+IHN1bSgpCn0pCgpCU1MgPC0gVFNTIC0gV1NTCgpzc190YWJsZSA8LSBkYXRhLmZyYW1lKAogIFZhcmlhYmxlID0gdmFyX25hbWVzLAogIFRTUyA9IFRTUywKICBXU1MgPSBXU1MsCiAgQlNTID0gQlNTLAogIFByb3BfQmV0d2VlbiA9IEJTUyAvIFRTUwopCgpzc190YWJsZQpgYGAKCgoKCmBgYHtyfQphdHRhY2godWRhamUyMDE1KQp1ZGFqZTIwMTUgPC0gZGF0YS5mcmFtZShjYmluZCh1ZGFqZTIwMTUsdWRhamVfa2xhc3RlcnMka2xhc3RlcikpCmNvbG5hbWVzKHVkYWplMjAxNSkgPC0gYygiTGlmZS5leHBlY3RhbmN5IiwiQk1JIiwiR0RQIiwiU2Nob29saW5nIiwia2xhc3RlciIpCmBgYAoKCioqVGFiLiA2LioqIENlbnRyb2lkeSAtIHByaWVtZXJuw6kgaG9kbm90eSBzbGVkb3ZhbsO9Y2ggcHJlbWVubsO9Y2gKYGBge3J9CmxpYnJhcnkoZHBseXIpCgpkZXNjcmlwdGl2ZXMgPC0gdWRhamUyMDE1ICU+JQogIGdyb3VwX2J5KGtsYXN0ZXIpICU+JQogIHN1bW1hcmlzZSgKICAgIGFjcm9zcygKICAgICAgLmNvbHMgPSB3aGVyZShpcy5udW1lcmljKSwKICAgICAgLmZucyA9IGxpc3QoCiAgICAgICAgbWVhbiA9IH5tZWFuKC54LCBuYS5ybSA9IFRSVUUpCiAgICAgICksCiAgICAgIC5uYW1lcyA9ICJ7LmNvbH1fey5mbn0iCiAgICApCiAgKQpkZXNjcmlwdGl2ZXMKCmBgYAoKUHJ2w70ga2xhc3RlciBqZSBjaGFyYWt0ZXJpem92YW7DvSB2eXNva8O9bSBzdHVwxYhvbSBla29ub21pY2vDqWhvIHJvenZvamEsIGFrbyBhaiB2eXNva291IG/EjWFrw6F2YW5vdSBkxLrFvmtvdSBkb8W+aXRpYS4gZHJ1aMO9IGEgdHJldMOtIGtsYXN0ZXIgc2EgbmEgc2ViYSBwb2RvYmFqw7osIHByacSNb20gamVkaW7DvW0gc2lnbmlmaWthbnRuw71tIHJvemRpZWxvbSBqZSBCTUksIGt0b3LDvSBqZSB2IHByw61wYWRlIGRydWjDqWhvIGtsYXN0cmEgdnnFocWhw60sIGFrbyB2IHRyZcWlb20ga2xhc3RyaS4gCgojIyBaw6F2ZXIKClByZWRsb8W+ZW7DoSBhbmFsw716YSBzYSB6YW9iZXLDoSB6ZHJhdm90bsO9bSBzdGF2b20gb2J5dmF0ZcS+c3R2YSB2eWJyYW7DvWNoIMSNbGVuc2vDvWNoIMWhdMOhdG92IEVVIHYgesOhdmlzbG9zdGkgbmEgcHJpZW1lcm7DvWNoIGhvZG5vdMOhY2ggdnlicmFuw71jaCB6ZHJhdm90bsO9Y2ggY2hhcmFrdGVyaXN0w61rLiAgS2xhc2lmaWt1amUga3JhamlueSBkbyB0cm9jaCBrbGFzdHJvdiAtIHByacSNb20ga2xhc3RyZSBzYSBkbyB6bmHEjW5laiBtaWVyeSBwcmVrcsO9dmFqw7ogcyBpY2ggc3R1cMWIb20gZWtvbm9taWNrw6lobyByb3p2b2phLCBoaXN0w7NyaWUgYSBnZW9ncmFmaWNrZWogYmzDrXprb3N0aS4gVXZlZGVuw6EgYW5hbMO9emEgbcO0xb5lIHVtb8W+bmnFpSBFdXLDs3Bza2VqIGtvbWlzaWkgdnlwaXNvdmHFpSBwcm9ibMOpbW92byB6YW1lcmFuw6kgcHJvamVrdG92w6kgdsO9enZ5IGNpZWxlbsOpIG5hIMWhdMOhdHkgcG9kxL5hIGljaCBwcsOtc2x1xaFub3N0aSBrdSBrbGFzdGVyb20u