From a7853a26c2894e77ecd1b473d3de9174885bdc5e Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 21 May 2007 19:51:09 +0200 Subject: [PATCH] Dalsi verze zapisu o QuickSortu. --- 5-qs/5-qs.tex | 138 ++++++++++++++++--------------------------- 5-qs/strom-dukaz.eps | Bin 0 -> 109314 bytes 2 files changed, 50 insertions(+), 88 deletions(-) create mode 100644 5-qs/strom-dukaz.eps diff --git a/5-qs/5-qs.tex b/5-qs/5-qs.tex index b28bd5a..be1fffb 100644 --- a/5-qs/5-qs.tex +++ b/5-qs/5-qs.tex @@ -30,13 +30,21 @@ nejefektivn \:chová se v prùmìru dobøe, a¾ na multiplikativní konstantu \endlist - \s{Vìta:} QS s náhodnou volbou pivota má slo¾itost prùmìrnì $\O(n\log n)$ +\s{Vìta:} QS s náhodnou volbou pivota má slo¾itost prùmìrnì $\O(n\log n)$ \foot{Vìta': QS s pevnou volbou pivota má v prùmìru pøes v¹echny permutace na vstupu èasovou slo¾itost $\O(n\log n)$.} +\proof + +\figure{strom-dukaz.eps}{Dùkaz rozdìlením na fáze}{0.3\hsize} + +Provedeme rozdìlováním na fáze, pøi¾em¾ fází rozumíme cestu ve stromu, která sleduje +vìt¹í díl a konèí, kdy¾ se povede vybrat za pivota l¾imedián. +\qed + \s{Pozorování:} \itemize\ibull -\:Ka¾dá fáze rozdìlí vstup na disjunktní èásti + pivoty $X_1, \ldots, X_k$ ($k \geq 2$) +\:Ka¾dá fáze rozdìlí vstup na disjunktní èásti a pivoty $X_1, \ldots, X_k$ ($k \geq 2$) \:$\forall i: \vert X_i \vert \leq {3\over 4} \vert X \vert$ @@ -52,6 +60,8 @@ nejefektivn \s{Komprimovaný strom} + + Hloubka je logaritmická $\Rightarrow$ $\O(log n)$ (proto¾e velikost fáze klesá exponencálnì, a tak po $\O(\log n)$ krocích dostaneme posloupnosti velikosti~1). @@ -60,108 +70,60 @@ Pr $\Downarrow$ -Celkem je v~prùmìru $\O(n \log n)$. +Celková èasová slo¾itost je tedy v~prùmìru $\O(n \log n)$. + +Pamì»ové nároky jsou: +$\O(n)$ na pomocné pole +$\O(n)$ na zásobníku + + +Dal¹í modifikace QSortu mù¾ete najít na: +http://mj.ucw.cz/vyuka/0607/ads1/quicksort.pdf + \s{Vìta:} Ka¾dý tøídící algoritmus zalo¾ený na porovnávání (a prohazování) potøebuje na~vstup délky~$n$ v~nejhor¹ím pøípadì $\Omega (n \log n)$ porovnání. -\bye - \proof - 1) {\tmsamp{BÚNO}} nejdøíve algoritmus porovnává a potom - prohazuje - - {\small{ (algoritmus mù¾eme upravit tak aby - prohazoval a¾ nakonci)}} - - 2) {\tmsamp{BÚNO}} hledáme vstupy, které jsou permutace na \{1 - n\} - - 3) Sestrojíme rozhodovací strom ne¹eho algoritmu - - \begin{tabular}{l} - \ - \begin{tabular}{|l|} - \hline - $x_1 < x_2$\\ - \hline - \end{tabular} - \end{tabular} - - $\swarrow - \searrow$ - - \begin{tabular}{|l|} - \hline - $x_1 < x_3$\\ - \hline - \end{tabular} - - $\swarrow \searrow$ \ - Ka¾dý algoritmus mù¾eme popsat podobným Stromem - - \begin{tabular}{|l|} - \hline - $x_2 < x_3$\\ - \hline - \end{tabular} - - $\swarrow \searrow$ - - {\tmstrong{$x_1 < x_2 < x_3$}} $\Leftarrow$ \ - {\tmstrong{Listy}} {\small{- algoritmus u¾ zde dotøídil a u¾ bude jen - pøehazovat a pak zkonèí}} - - - - Jde vidìt ¾e $\tmmathbf{}$Existence dvou rùzných $\Pi_1 a \Pi_2 $, - - pøi kterých bychom zkonèili ve stejném listu vede ke Sporu - - - - pøitom {\tmstrong{\# listù $\geqslant$ n!}} - - - - {\tmstrong{Pozorování:}} Binární strom hloubku {\tmstrong{k}} - má {\tmstrong{poèet listù $\leq 2^k$ }} - - \begin{tmparmod}{0pt}{2cm}{0pt} - \begin{proof} - {\small{}}Uva¾me binární strom hloubky k s maximálním - poètem listù - - pak v¹echny listy le¾í na poslední hladinì - - víme ¾e na i-té hladinì je $2^i$ vrcholù - - $\tmmathbf{\Rightarrow}$ poèet listù je $2^k$ +\itemize\ibull + \:BÚNO nejdøíve algoritmus porovnává a potom + prohazuje (algoritmus mù¾eme upravit tak aby + prohazoval a¾ na~konci). - \tmmathbf{$\Rightarrow$} v ka¾édém binárním stromu je - maximálnì $2^k$ listù - \end{proof} - \end{tmparmod} + \:BÚNO hledáme vstupy, které jsou permutace na $\{1 - n\}$. - {\tiny{pokraèování pùvodního dùkazu...}} + \:Sestrojíme rozhodovací strom na¹eho algoritmu - Z toho co u¾ víme plyne ¾e $\Rightarrow$\begin{tabular}{l} + - \end{tabular}Hloubka stromu je $\geqslant$ log(n!) + \:Je vidìt, ¾e existence dvou rùzných $\Pi_1$ a $\Pi_2 $, + pøi kterých bychom skonèili ve stejném listu vede ke sporu, + pøitom poèet listù $\geq n!$ +\endlist - {\small{z Diskrétní matematiky víme ¾e: \ - $\tmmathbf{n^{n / 2} \leq n!} \leq (n / 2)^n$}} +{\narrower + \s{Pozorování:} Binární strom hloubku $k$ má poèet listù $\leq 2^k$. + Uva¾me binární strom hloubky $k$ s maximálním poètem listù, pak v¹echny listy + le¾í na poslední hladinì. Víme, ¾e na $i$-té hladinì je $2^i$ vrcholù a + poèet listù je $2^k$. Odtud plyne, ¾e v ka¾édém binárním stromu je maximálnì $2^k$ listù - {\small{ Udìlá se to pomocí {\tmstrong{AG - Nerovnosti}}}} +} - tedy $\Rightarrow$ Hloubka stromu je $\geqslant \log (n^{n / 2}) = (n / 2) - \log (n) \Longrightarrow \tmmathbf{\Omega (n \log n)}$ + pokraèování pùvodního dùkazu... + Z toho co u¾ víme plyne, ¾e hloubka stromu je nejvý¹e $\log(n!)$. -\end{proof} + Z diskrétní matematiky víme ¾e: \ + ${n^{n / 2} \leq n!} \leq (n / 2)^n$ + + My potøebujeme jen levou èást, tedy ¾e ${n^{n / 2} \leq n!}$ + Toto jde dokázat pou¾ítím "AG Nerovnosti" + + ...tedy dostáváme, ¾e hloubka stromu je $\geq \log (n^{n / 2}) = (n / 2) + \log (n) \Longrightarrow \Omega (n \log n)$ -\end{document} +\qed \bye diff --git a/5-qs/strom-dukaz.eps b/5-qs/strom-dukaz.eps new file mode 100644 index 0000000000000000000000000000000000000000..5120426c633726f5877169df13676037d65e4706 GIT binary patch literal 109314 zcmeHw31D2sdH;~Kv{CHciqt29mazK)wBa-@G?7Z}+{o zhjuL)Yi;eD_sz^V-~7IBzB%99zxw94pEybgarGF!oX;Hy4=z7U6pP0my?*ed<-?hw z@sU0lTD^pZdiVn)kpM=WBF8anKhWtX2w@eZjE2io}9?33}cz} z%6OjQ<9Tase8!6OS&`VXuI^P3V`&tV%8a(Q*vlvLnboOyK8-@Hk$5VXw1$%-PQ+jy^{_e|%D~!lPF)+%Zp~Tw z?4+CQjGRQsipW&Qu9zH44SNu>&P--=0Kw{OkM>bzxpLM-HZw9tuvzPdl8N;HIs_}1 zoQP-Ri62{;;avQJWctTc2Nv3`-ZDy>$R+dEc2-2+%CSTq+&e6&);4L;4hTxQjc~5x(YzN3^xsZG$UUx3(zj!+jzfccdIl z=5c33+p+|%bS_uuv;cE*8mW@o3gACtMPY+5>y*`HorLDfK>~AZ#A3K5*ZAtg2yljGYTiQC0jj1i;CPF)N zg9C10ts6MU4V)?iWFs40UZ=af*14(HuQn8yi@2iYBCc$?h$~z!qNK}3@(zPsM9DX_ zb=2TB=#*~{x}pubq75pkGZTiLSmW`0c5K?UKzV1kCGz8JV-vVKDI`E8_qqIdYm1p+ zWMm?pSI*6rPCgsoz5#}vfNh+aOyoC3x)*n##ZmJ^FlG;B(LuDfAlz*aXY%nx0*!&9 zdhIOw7YZ%6w@ju-C6o-9|p!*n0OX~1YifQOQ#wK!OIeR!hI-1Nn7sN^) zy>?`^#&mL!!N$=mBzajw3IEQ4t*EPF^*u%@FN z88rlFm(1Jfo#MGIc5<99l2@;tN8gbok2RbeM^9ttN{W^oGK@vvYWtkwF*H?FiSsXy z*l6de`1o*Ud)g*7*tvW%n*w^abW({Kdj>vgD4W@uOanZ4m4x)}06*SqyX@?Q+b!6c z?C?l(d@MbdPBH?iT5*|8f zPoySuGG%^yCN~L)$1+(vzXfsXE}odoC++b`oBBXl*~Au7#aL#Tsza;XqI$)nd^C3&opJXRSzR;kQuWSTWH%^D-k8aEBI8}6`I z<+s?U%fi>mTt!ORv2S9U_eH49VdP$>9ux!x<{;IWltN zmP|HnquGq3Nerc=#U(pzQqok?j>}YWg9XM7WXy5JDb5hZlQvugE03i~_S!HH;*pd* zk_Hc?lLl^&$uwg!&6ts9%uU1WMmp>yAWF-^Gcs33=E@kkGEM?FGi-lqY*;$7kzP9^ z0h*NgCuROgBmbnzI3pwBE&$MsOFkDa7d^>oogcDO&PX~%BWc~cT3&jmHJaQ};4y&H z?{OzaUFU}i#A$LIU389zda8$(-N%lCy*xEMnG24Op!1=B7&^7KU?`CopV^wAA-3Ch zXhQ#J)}k?j``2NmlgKGKAV0>ZI(uu2Gy18RUvenTUsil;OF;P~eT3xqlwXz~DLmrS zum$qNX5BvrT=zl)%=M=g?9DYfq;Y>FTo3y)N0fC26hCLoUk+H0(UHY;7S)J9@!#cr1<{;zWjBGm)Z1 ztP#uOC};8q3dE!`aM)MIP8np(|;}^o^@Of}UfGg>ksGZE`FR)zN>_98Ze| zXE0r)`6wnjh1?9fpmCb>$ni_GgImnjG`sbn=us#nIh{;^uT{$7wB)pAQHU7vY!4{d zO<{0h=`iuEMK+8GP`=I6RfDT;>?JW01k0Sk7VQ49kyK%L61M8J%n?j|Ua@d3t7j90~?)9r|Kg062GZ zdMPX2V$Gn@rYBGaR8ufZ?PMoHjRG=2TADd9Fc^=gZ2F?f3|-A^kgm{A#2uK_O-v-w z^iZcAm@=~JB@>!rrZO-VmpfTQk|xwCTV9B@41u2^RiWUdtC@WQ!$+u`F2tO!C5(ww z6I(gKO=c(~q;*-#PziHM3}FvuzOdx5EVDISqke`{rV2Ml# zet~Xi8NzPMbMiDL=Q}P}P03x=JGGeM#B#ElKp6bmJi?ypDXy$ALpBt)QC8A!bLQ;E zIs;YHZj%*~m7|JMg{JMTq=K{UQ|Xc$2`iAQi)lPq(Hx#@=rgT%>qwJ-PRg~U9lB0W_2qxMF0wSs61}5m`IW&GHHxJWE^S2NgUzzCAyJob|op@bmRvj z)^-xAA0~@T7MNmr4GUeQStux%kSk*-m$1M+MIj?+f?=vmSPnxBvJ4Ka=cI!J%bhDl zux2^a%1X;%5*_i0N>}-a{{%RU@i2(Par%)AmBRfT*)qPB}|+ zTnkw-)vvBS+f6kZm?? z8Ip`OS)>Ikr(#>}Gm}6$D3=6AKxTA>&WT5pj zAfQt_4B*G=V#jrxOiM}WX8X!qeqc*tD~fM%6a1nIZVMiv!g?WDD#XdU3i%}8c5~IH&`7IhRbnQ$SpDe zRs=Y85=*etlBgwNH@VXSq`FVHN{e>-1=-)Yi|~Mon2)Na*4~L70>Z#uf^LuX_82(G z4x&90!3;?1v$dtm#h7a0{1HxP#Z$u=d}1bAvJi}>xM6gNI(QT=r>byiCo@&sof(H5 zCue6U2PW<80Fjy~j*Yrh$r;l&HB$gTvm6@6(}Jli%uMLAQpLJS!Sj^d5IR=HlQ?e4 zIg-1{z!Axel3j+SDIpQc=mfdoiYxOHW}r&LQ6@u%ixp2y=ShQVAHbCgSvPKjKv2DmS#eAQh6-T|DbS~UldJO?UqRK)b$6jesKoaUPM}HoBaBkmX#oT7gWuQ!{FWP>@Dm^z#6kXB_Dn;xlbYL&a+0r4) zl%B!luD7XNufSJY$zrb{cOz(rOYRj#Y5IyexE#Qeg3-dM9QxPQ+TtYRy)P|?Q@!$x zPK2sHsz)n3ta?mcGUL+oC@X;~ed2+AJWD<&&fAb$HI8)$aDq`Jbd&@gYbF?nkb^7% z6(mfvNz*jt^(tUTVW4z74v2M0xB-r%UJM?cjxL6w2kq#Wz^Gtw?Xo|YAk!j)q9MLL zl*y!$@w7YKhak!(cknc28wsark|B3t=g}~d>QyE^)fNk%<*>Wc9uG`zT}t4giRTV# zn=l8|5~I)3M$_6ti-1_oGmM?JJ2p=Hx=O`ZHbQT-hKL0nze9RABM!Pvb9{~mZ0PCo zV+dJoGQ=}sRM|}vrTSybY1;})j_b+JbpvH$?GiewZD7byK&lOF3!I#yIX~g$Y>+cY zp4}jZ=Qp_036qSqhFC2J?rx+MC zt+1+g>8f%?;g%XzQw+HF}dLC>sT} z0F#$Fo8m-%d`5}Onsg2uRVxPujk5!5)-FGJl`TCPhRGa2GgCvv?G%8B~(6822ud&1+dF9*}ayzVv4I&u=2sK z1d_2=EZx#Pvnuzn8Wvzj@`bj1Dm9G;PwNfjDoD{xqk&c11Xfac3X6S+w)`|X^0xdW zx>R1Lpy7f{Pb5r9+a|Uoaa03*(AtrKmb%D9`*ZoB0v*8`8p=%DZIqf8H72vf(QZqn z#LP01&JE1g(qO7}%+kDe!{46vDC)Gpvbl0(F84;y`2w zC;J99z3O6L`&8d}9 zRS=d|H07y*%a_&9>H=@H3Rwrq4mF!`YNiE~)iceXD(&5z;>w`{#7|+R>*>^hY8fJN z+lYIfY&&gg(de2;@N9I80(q~?Q598jJ6RCARVNkQQ7XPVeuA3Q#7F`A4`4>8#Lxjb zt7^0+DHnjz_vVKz=7!*uwPJ{x2Yr(l7`MjMiX0leY}wRLBgpPz#SrP9zI~Fr4WE1v zT0XiCc~Db2Ao>R43>)GlcQhJiU3$mO-tk;cMhmNwmg{xMdZmD^E#z|?`4A`(!fvD1 z>J~zRk!EQ9r;YrFELY}oBIt}l&T5;&zBoz)c9 zv;mQ=7LF(CRIM%Ec?=L9$&OkWA5n>f0ZEI-EQMr;MyCy|_jh!B5M3%Z(&@mr}ZN;Dvw$zC*#&m~W4~(c2N$mI2;XrCVq!Ts=2{?1{O+>v05Q4+u)%O1U z6fKXyJLzh1ec(oAwRL|$roSGh4}&g6e0`2~({M;6gTsVsnE^u#XraUUFyhYNbS@UQ zp^QL9vcD;5Qa#v{iFEJ*>?!Uxou($YUC8q|4UU4cl`(L#sc}%ZHR!>C3{x3fCIJ|w zM575hyvTmac*(Uw$w@W`XZg@2Np-BpBEIf_+Scc=GfRCEFZaRj2YI^P+Tz+e?L$zz zb2l+pyZcX`KFFdyA)K+s?hn4=^o5>}H%Q>T#^^LAxjA?$v>n>45(O%PgUDQ*aKQ_ZUk9v z8!ha$wylN1onv7a7JHW1t9D$6V<#n`(GHwrFmiWYdvDru($z#kv^`b1MmegHHAod& zL7jrNnp@AHoYxF->g;NfQU|SK!ZOH{+H~qH;FcT_cm>tuuV16{B_8uCE3Y zBw!ay9+3}@@8GJ3v~4E?S{wH39a930_j7rSK-~*DCAop^yP?Ozt#^dOQV8`f)SM_Q z`5!PhR}eu&(<6SIacm4LQM5S=hbu>Z?sZ&I+$9uhE^?m`)%PaG;0XgTerUkW?~FU0 z(UKZ9K?8Xxv_FxcbuXMLg5w-V_0h7&#;}Yinb6b^mIuVqWw||!;sO7FR!ke@bV#1| zzv*B+?TXXxxw3Yd8;X>Cykl#2DAF5HkLzt-Y^~6TqY`pDrBe+Wn7G}&9CDyv$jb#g z*;mQlpVUArAhMgH6g1TA<#imx#bUvfk2{e5Ebdpi>eO3@GLW1jBC(C^+b19_(r$fg@Xi7}8iA<8}F1k2}A>@fWX7+1l55jLk=@u1=+P zsoh~)K9S-pNlf=tHeKEE2e$1c?raYRz-QSB4PRa?M{5grr8N9tCy5pS$#@f6nK_Gy z4%ml^%w8(=0kI-%JQV6wp(uxTsD-a;iZdGxfqq9WEYj1Ra8cgDAx405kB8SG*>MLu z5OOf4C-0@X4xYW_XDy9oQy!eyXYrXuZl{FzDRMc|b(%axC|xFXJTfI;nWP7@jEZi; zg2TCH6^Q@^@*g71TOyxZR##%nDqhP^mDS|yoTnX(l~%*1?d5|5Yu5C}9GPL}*h{h4 zz#JV7Z1luoKNHqRyE+&_*c&F(r}5^4H;wN2A-KDPzhAfvo+%AbNyowIV$G{;SnWw+IuGPS4SSHQ7%*5+6a7b4^R*~jH zO6NTV8ZSAI8nYd#h_VL21MhlT0FQIHZFm|0c8a&Lh1b>syimZ5;Ob`60*svok5jL+ z0mz9jWU8tK!0Jsu%^K-Z8fk4Yd^pFIDn-sp*3dpD_V}lgyu%}jl$G+dwm9g>Td4+>C_ps?OQOX#hmh_9=w18mBAQz+`W;c6dt;Aquj7e zjpG5l)a)*R;bAa5$wG?*v~mGm7B6;OuL z%7uc<$w|9nE!IeAYJ>F<^EZRx>r9*%g}_(R6JX|> zK-k@5>av1f{9!(ohGABFcO(jv@IGG?X-B&NjUG&Z-r7cT^spmbDs_`ws8b5vtw*EB zJ7V}PF{jDr!W|ODa+!4RV!y#D%BN{ek9eX++{9lGwqnwXz7RcBeZSU&t ziuG90zV7zkSVy$aigtChM`Ar)y;fH&+8*nQq7wb9=!s8Ww6`{$OKu8(8}QeEG9su- z`ipCLDy8p4L`Nj5u9Sw_e*bo^xw8|8`La)msD+;<$J>Ui8!C$|xyxiBuUS zh!!riGELP?M|)?an@!NY2AG*4wQKCN(u{5&y7j~&5GUH**%_`GZY11hbcowbv>h)B z>VvsD*T6QT+N&;+Dq|?jZM>nHQEYT&bV#$VY-U`KlFIaOCAuv4T4QCjAUYIQ8J)^c zA3C=iDoGE%LPUUZcT6G`jBWBOX@&DD%w ziKvX9aFr`VeY|!Zeo7Cm3@e58QDSCp!*{Pi4#2NORT-~vVU^MP&|?R!4_(2~%IGTS zP)%*duS7C4Wh`2_u*zsQI=z9DYIk!|87+twF03-qNTj_t66xr){02hNSXX;A+R-Bi zniy8nYr*>Q9zosOb!cl-hoX9rP|Z@)lyz`+g}oM3v(y#Rr7Ie;_v3Fx;F!C+ zx1DAUU8Y`@p=+?nNas|qdhDm_#%;2ry{k7G>oE1I#n*5dGgel=@gR3j^{O^_IaXX+fl6G{qcXjrm zuh%R!B3l2NMtbeVn>)L@Fgw#^t%R6jY0%8lO|mPfW~nQrOV_lDdR6w<6~%i~dpbHy zm)6zY)7}&5j&;qwUX`J1nW(+07OBbF$#iu`+M|FR&PW-$?nOy4n%os@?}>Kzq4t`k zMnspcXp~*GNCP|#sAj2YY6XR|YqAzpvsBpY-a=QhqF%KxP%T&6hqmYW*SqU_pf>I4R$ZflNenkta8E3)9w=F z4+}k!C`?-A?(FMn?~eBL;>ld)k>^^kdK9Q-f?gqdduLBapDC&#zS66vX;lImgRESt zW@#XzmoXJel)VQlXR+Q+4|oQku3in0O}%Qe)~jZz>*-hbN_zF}7*wySdC#?8^*CS4 z1ii-mdQdIC(yQ*6JbE?AO0Sxw)~haE(}1jB4{8GH>eZl`devmDSItt_Qs0LKC z)HKymQ+9)_1l25c->*wov`Tu7VZps87VEl@bh=8WFuLsAxbIxV1+*JJDeo;AucLOHDKNYGAJg)hty# z{pwyxuiCE|-d^>py8oGLy=wQVWuo?~Jgp{cXQjJJgQmJlYB9Q|s;e|u>aJ3`PmL0? z>%o>L8-Oa72F)zpAgf`5!BUNK{OVpwui6(FA?3)lpPFmEYCo)H^7vs*HbbsUHE7DI zkzRF8mH*SO-9SWT(lpAhGbxv<6Zpm|MwDG=Qu7=mla@_o((+cXS8Y8yx3=ebq*v9( zyn0n+LwwbmHBB48N3Xh_XuTSUC}cIwqgPGV$}(6g1$s+YWbGpiz3K|7(zQM+>J=VF zt}ytXr?DL$jWINER`QNN>?->s|T+dJUz%Y zrYss{vveb=^1}v8<%f;Z70uMEJg>4b8^?irJoAYIOU@U5$w(1#s>XXv24`>RFiXg9 z4u$+G56-x(!;!}|YmOH;_8%t1BJpm~hQH%QM8rgoSSCIw){2wG8Dg8bK&%kwiC+`% z6u&Hv632;O5-nntSR+ou-#VmOkAEK#gGhUpI1_*8h>wbM#b)ta$o1PIftX=@kBFog z6OGyak1DbeotH{{#e{5?iC*skBWa3 z&wzG`_#JVn_-Fq2Rsq4qa&TA;Nlt~l8&KBAAj8>^VYB$SxD083S6nVWA+8Wticf;$ zRpM%Kjrg?qjJRIhD1Kl3p|}};pF`R|5uX=-D*jyjnb(h z*Tpx)H^p<}Td2)HiSLLf#na+h+&?G2C!QBCpoae=UKKCm?^Ur+yoSHW!9{ZT2ju>H zCGj)F{fz&;E?(x?AB+D0{T2NCsrYZ^`Lg(l z_%G)Dy4Ww?5dVws{h}z26t=KLw>Vau1Ph2Fv`oB5ychqDf^B>N)Rn;aEOELRfF3hI zeU&%`7H}%=Ps6{pumrM!4Pqng;7s6uw%7z6oC_N`A675~3mAeOBw+_5jtyi)8g?)N z3(JW~u^s=WU;)#xfD2#;iy+U@_;(EcEfI@hoyWp5$To6Z!r9RDmC)rSxZde#>0W5# zcc7#DSVt7IlP%!muz<^91H0G;K80M@u?^fPZW4b0EBGvQ{yF^n6Ij6K#TQ@&yI}#l zVF9_<*MY@-uZ?dKTfv#VHHIV-4o~-I;j{aX~{lCHb|8?m3y^QwpqFr>r z0(#&Lj^Mu|#QVfjpubd{fEXKpF?fdov^w$v%klSNZhd3{(i3cirJTWjfIPuR;R$|A z#2qUbh82(>IG?q@72g@h0;b>z$O^~?E`UWIDSpHGcMNQitnortmj{$1EX^_D~jX$`E)7xE)nS#V_>smJt^SCIY7jkvH$1@FF4Z z_8~8jTm)_s!g9mr^)49V>n33#>_OnwHX-i!P~4lO5G&m9!nF*6dxTh4Mr6Xv3;lyX zFp|0rztSEM9~I)^fT#s>5#x>^6mAt_dr;gVPk&8_V}d|ip9?ead=SdvqHQrDDIG_!>W!C0^zxkW*n5~kfFaS#IZq@eQ04I7X%IH3%zOx zIAKw%h4^AXJl5sD6cDvQE`A|w<`6isy%(ZbaS z0W4Ww=R@um;+Ox@hrU2^5x_#G{|a#H+6@cHxhVNu&wCe;yGC!-P?G($)Af-J8#es4 zPlg2&BXHj4&4k>drwlx9!n(OQ6}WBK@K*+TA!r}~+$3_M>jqvafBngwys6KyEg)w= zg!1>{^L%C5gn{lez4GP*-pKrR583b=V& z>%w?Wp;!^O1>_V~W}ph(7LYRmbHWn0Ej}?GlIiCbS}UNb61N4L^O#W$xOtKLn-VsM z+-=qNM#z}0^$twy zA~(e2w>tfs>lF_{Ki3f44ndo15N?MYat*_+SUk&ED|yq8N*aip7rDQ8o!^_|`q=$9 zt-Rp(AA8lUO+#_>L+-J=uI(-C_CB2M7JkrN-?$~_o&xE;g{5vVZeHa6ws_0TQm4S9 zPLTy3G+3E}dd|*>qpm6zC2qrJqS=N`KX<09Ccd8Zz-)QXP5zfH65m>}{ettSR^V(e z!cD-T`oe)uq0KXPSk${L5~J`!A>aO`A4vZm7Kxduem) zKf(n*;}p2>^5bzIdD$)hpt(K`u}^v06!)uiFnUwtadVJ6l?vQv7D(kqOv1qs-V33( zl?qDjCs9gl#64{8H1NKugx4#*LiCl;=K1YwN8|k=<_Tz)_c0*X9Jg~8`L{dDKzRV? zuFoi=&S%2KLQMI|cd`)I`q5`i`;~xa?*&-xXIr%o67(PvA$Bj`!j z9S7GlU{?w81%E6);n$-4lh#6AE<`~8`92}ktfdx?bCdQ&Av_(bmI5#9dY`^)R4C+i zF4IC>)~I5d&gXd{jteRTBVo^&At+r<^lODk2W0s2!SwcsFA0$gs7G-?h$n*L>ZVT# zaa&MkXeuab-qEiR;$uNVw3-c&TRKatLPquT;TeUL-k5h#P_gnG|9&D6Ve$ z+l2UGQ08|Fu{$VkzR`OyNez+-?<*(-#nnxJdkAodyS{G52RP$pLR=bDB;3(wgW~F@ zW6TlgI5F1`7^&12XD& z>Pdi}%y-6BEMm^pgtsB%HDHSa@}S>34lAI9nq6PTyBAK~aA(TiypUKVI4>cD`6z;!}8Sd2<#ri+7{I zuauToeD*hmXx;F4W%PMW_%13^=9JO-iM>q{`gg(mfl}U>r~W^jlK4(3eIDOqC?~{> zXOj5B3`oA7uOan-Hxn}+PBXww@ad9+2RX(KV&9_Ht)ICCx8jMwDW#{%_1rv&5u31X zQLC1>U^*dM*2`l#2McmvfXvrXMbOzzU2(~-%cd~0qmQaqJQ(Z|YN*Ty@Em zMK>+#G}FO>9N~sNnOCtAVt$Sbd0TBIP^yZ5)%%+*N1sM7WO6-sOz4~k9Cn- zdihU^KyJD!1nN$7`5^f<{&Zu3#zl>;^B*~l8`b~T8!kEG{g>X#Clg*ojeJL2bpz#- z@z!(Sb=a@H>knnWbTA=DxLxB@AtGUb-&{9Gg(T=?_Kzrp&%uLS7;eSlxDd9iQS-h% z!0k7Yo6jTRFNW9~Vby#$=e4+^2f2T4p1NkqnQ*&0j0YBgn*HlD9*e{KtxTJnugF!z zO}e?pZ>*ZSDgo|bKyEk83FlSAKUn7O3{Nr3*izu;KXO&!#%|6#r<^5FrP<4XoA1a~ ziCeMRZmt}-`HdXm_Nh|s``+JxludMVKETaq|GR@eOlS@^4KmyjI49+wWDM>3Jl-r~2fzrSu1Gej-;RZpGq_O>}bs zz|BYGYR0WtOf~NjgdpI&$o*?=X55t2gxe=;P zN*@ed@qf)8VyE`9Md0Qdxd!0IZti{sV`Bo9 zfh+#Z9M3i1=AQH%KDuM}_6DFn11_&Cz+P2nbQG!fKw>kV{CD?N1G0ON`+=KiZzGC# znaS%5ySk6V;ey58JD+qS2)DqeK)jhl@8ITQoZ!pT-N)c*)+OCHc=QvRxjb_3HQn!g zs}OJPxbX4vNP|*_+}-JJJk@QT(0!|sYPP{g)Cmxvbu2%@-6-6OMWA(Iv3QlIh&^>m z{FH~w?}u^mB8TUJ^=C>qfiMo0<1Udrk2?H4G7!6@cqc+vRL)sVif6$pjeTnR9PxH} zEkDdz4X2_bs5tyc$>zkeGoc0>1Gx|Xl1%@0r-F4BZ!o9eo<-ogc=E-cApGi!7h+XI z2s$^~Al!<@>xd(Yxa>t5)4g~*7S`)qS|{`uPuxvMkN3TJ2@AR#;h>K~ZVeTLHzgvLE1*XmO|NPR}SdV*HKuXdJJwI1Fw&pnW`tb5*%F1$9;j}H>`yCI?h zxl>X61EooxI!TD_rNo--4Z^bqK1u1OF|K&dVX1NJ2Js8Q zXSiX%>(4fz_^*`5(5Crp`qrnA-%tE~81jVq-Ev6+Dez~<`$f_MfFIqT_6kz_p7pf6 z4!SJ&2ZdN&Mg#%JmrwGeS4oR_-L1}r;m9I=H;WK0EtNfi!~9l;JoH*tAl^IT?{yyo z|5wYBD*~2x7O5Lg06kXdc{NYs(wkTP{Dw?~H;X({n!KL-tA*I=pYKT_e$zk3hYFV% z@aPGicDUUqgF}MP`GkM$%|a~qkEw$CSs?}kl6|~EtG75{e@{RWaQ9CIM3s^sK-XVN zbMA3a<@|sskTGoucx2^unCkxEjNvh>eH|y~`DuV_3TIdr`x?Y6BRYhuLZ0j|$%BW) z0^d6l_T1eQA!daK_U{ED6lG>s=-EYHll7+|$+Y2v1YN;;P+utzdD!BRmqUg2hdQ3m+W2;Nya^ z35{93(5r^x6BrpXj=MC(tp@V*iFk94;}&KPKB}&YbYSMH{yPk{&Q&LUYgG4K6|122 z&sB>Ht0TVJsDk+EgM2*>+c%Zh;~psoVz%pX#iHf6K!UZ1H~$LoZ` zQ(p;=pyF*uNG>Oav61%1$ClJi{@dK*|A~Q{t<4o5VKZ}>F6Of%Az0KBMSH)z<#3g! z2r`;_K2LeL%;xM!gODq}uq(!=m163&Qa$x5%R{)m;84Fj9fL*x{F2x#Pb;Irf` zLqBD>aq7L#8JQZ1oWZsc!L5e9F~3FuS5Y_*Zb2t99pt`Nk=ubzP=;H>EUr>bJWnPC z;Z`ipQ{>8VJ5a!Ra0`2)>mOy`I=^ggytJLdOb$#_ts1vtaULQ^xIJImqz(vhHQ+W6 zk@LmvfLL5jxXnA{{Bb)Fz}1M`JVP!3w*vrN&A1hd-zzf%%>p-Nb90AWC~i#!&V$=O*K8Z#mVN77A(uwK@NBTqP3#-xHZw@W{q31_)TeZbAenX+?oem18|!|WbA((KxHSp5hT*1=`*vu%X>26n7I^gEEvhL^wSl zplohiHTKq=)e-XzBj0gNdlpv*xo^#aMfF*$#H|??*J#{|#ji`7YXWk&eR}7T!Aoy@ zK>=GOZhLRTBU#pUfe&RVe&K=JuGw*P@`~GD;Z%*stqi$+w_Q2)-U~l<+bnnMcWuK# z0{J;{mwd)Ji`%EdD~s4&oo+sBy#5z9?J|C|23(qfn-{rVeXiJIMg3wI_t9pl@wpU_ zdsTzmzE9F2PyJb0-(zC?aQNT&H0@WCzUH*neYZKMteir->Jz(Iyq_6#PVL%t@ugGz z(wSrS;ZfSk_J+qs@!E%}OFy~u$|*d~gU=T$nrL}~PjOECF4xB|ZSwDOImrD66?oLt z&TDpFy#sCrpNq?-s!VzM3Cg-#ol4zJXW!^kshvJS=C(pT8u|DWCbimSU0e z)pL|}+9T*RDTLizBgP>f)3KZ#M1sRpHZ)DqrjQ9>lo5OpH(hZ0l0L1n~7Y`O#e( zUUYN38#b?aG^NkHuMj>y;JqWLNK<~%cP|)w+>#?7{Jd2`RB!Zm!N|8w-dEu*Nhb*5 ze^wVQ_&#qLA$NappnpR;S?b?h;ocWuKyG~L6>qL9^Dr{aj9(j4*`Eu0??_H1s}xus z_TCZI(N^M8LpkA;s6wAOqf*QarhOqlc%S3@GC9TAfY+A1@g$ z^)4?(-Qj7Mz!xN_L@IDa$e=kIGL(BcVowp`{-8Jve0qc8Fv3U$#g)+EkpssrFpjcOQc3ojZ{f%S`_7kw`YGR1 zFzC3^Hv&WeHxm?x_l_JL6o-ZMBZJ~f=yP^jTxwcWlCAFBheBSLf{D=K)iXXR zWS|dF1G`7OSaeZPDHswR5foQKe|N|M0eI1COOns}7K6`U3}W(nNL+ayj5z`a%y_u| z!SWoE@{|xgL2-A6y!faj50;YxpFo1e$wkeQJhQqD(f1E)YO3f}FAkCfokL(dLYEu( zk~nk@zH(&Y^~0^((=@7WI=5?G%fcO!}YBEEYc`#GO7M`H`*_ zV#1FO8a$=nTRsC)S4&^LzMxVTz2NC!`%7UI0wZVK%j(H#dY#JmwSiSx4OJB(_A z`k3GXeE3vN`fTtk3Gpt+r>o{uEG|sB9I!A_>8b%Y{+TV`IoEFg_slBZv7onwRv2NuVC(?Fq~=k0wH)j`Bm(SOc`8P_#6@xvaVuPeu3a`%_%)x*7(*TBLk=PB0jEpKWPAt}@?CDzoUo9&^gewnLwn%vgC_%} zsd0~KhL3_CTvXwOEk2y8B%ves8D%{PYT&pmfHSbBA7=1=fJ%_pRteFypQvt}z$d`0 z49(I+=KYU;9XU!@Oke30;vIivCTn1LBMK}%mP_jMZFiyN-j7^^9-F&o5TwvN9En8Y z7Bkt)l<#JfQYrkS&70qaJcFKfDB|+Y&6}Hr9I+qt2u75vJd~<#o~7kvu}cl%cR}C6 z+Uu!{FQdK3Az{SX_b(Qo-bH-&*3zc~x6L2jMA>#d;}o%P7c5!4V-sSUgxuZ_qJYJ_ z+-b=REcR5upv<@8iue?XE{<6_lboK!L<=8F#f1hePP{U|Eq}pELQ#mXhNdrxB;4@% z9nQIAWg%I}%HrR{^kyMfw79^P6Z!Fr#$|zFFV-m$+IxEuvvR+V_TNqLX5qWrC0uUC zDW4?4q<@$2{CTmMaT)OS#QTf?(_G{p#hAhPoE$7;#h6@8O-VVbJQu!rOC(@Z`o=&1umYfP3&?&9=-Sa6Q^!|)Nhnip4g!5fAr=H z-uIciA2mqT1Wnv1{iAnXd&0%L6_;ishXQXYM6bG26#Z-45# zud1(ycx!dqY3;Zj;x;!6+zx5vW`&zV?oX<2-fxzKKbFI>dfKUk!0~g38gdS9pPz*t z9FoX20JlT3wf>iEr?as)GF6Aoq0?F$R^f&*nuW(WfLR+@-3GEcfB@84R6{GsI7+uX z@NN8dfkckpgCR0sk_A41^W-7VNrj6(r?D49?nO@;BHV-%(BfU2H#Z(Pwz*CJAM8Dk z3FDDQ(Q8Uz2s3|!mqF^Qz5aRs2SD4@4BQC0cYwLKyyAY#=REiPg^VS`!>!_|G8yr( zNc-Jo)P@k=Bg6+EDCP7NdRU8_ZfVTCy+^b3d%6^lOXQj&^CM8y^W~iPfqZ*8dHzy% z2AsFP3l({x8DirQ?`l83lOfN8`lX*^+N;2){JlFQ)P=P@p;T=>ZVPeHamf>;OEYvshZD!&rX!Z18gT~~cWe+Jys=_MP+Z+~Jm%{E)G0XP zS(mHpW_*A%q8@fok zVB*zNH{%1G@dY7H3Mvv0*fsub4xb5meG?uA+!-Xye52znB*z5F^gvCo^9bTnLccr2 z;?RuieipE#nC9Ou^s04Yj1|S8o(#)!-dEn%S%fzmCi4OBi$M=xzS!W+Jdf_~2^_A6 zypm-$@^25DISkH*^MTF#DweLX!{GBl|JV3oT(O9`YUyH}Q#jrt9%TGJ;>|hfhLF{f zrmTxK+h#UpzT#xtT_R-tvlglWWNvMQULhEZ?fpuzsmEbU!=*8vj#>5EsN_};@$T(-IqFA$krjKcvT ze^+Ce@b1I$ns>Zj<}GXC!Y73I&ufKtB7{YHk?5&*U7m@C*PMGo>?u6fp@H>$HZMaVMA0~d)Nb^o3{4R&*dy($fo%A0; e`XdkfdC4CV|ArI(6@-@<{QD6W_)jv>=l=j&=B*|G literal 0 HcmV?d00001 -- 2.39.2