From c136885c6a89ce25f4012b33a756b40172659bf8 Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Tue, 13 Feb 2024 15:35:37 -0600 Subject: [PATCH] day 25 optimize and improve heuristics My earlier algorithm assumes that the node with the most external edges will always be on the other edge of the min-cut. While it worked for my input, it is fairly easy to construct a graph that violates this property; several of the graphs at [1] went into an inf-loop as a result. Furthermore, it does O(n+e) work per iteration determining the candidate node, and takes O(n) iterations (in reality, closer to n/2 iterations); since the input is sparse enough that e is approx 2n, this is roughly O(n^2) work, and trace shows 1135260 calls to _round() and 843030 to visit(). The new algorithm takes a different approach: use two BFS to find two distant nodes (a heuristic which happened to work for the sample, my input, and all graphs at [1]); I suspect it is still possible to construct a graph that violates my assumption, but I think it is statistically less likely compared to my earlier heuristic. Then, with those nodes in hand, do 3 more BFS passes, removing the shortest path between the two chosen nodes on each pass, in order to partition the graph (assuming the two chosen nodes were indeed on opposite sides) (not done here: I could short-circuit these BFS searches once dst is found). One more BFS search is then sufficient to count the size on one side of the cut. Since each BFS pass is O(n+e) work, and I use only a constant number of passes, I have reduced the problem to roughly O(n); trace shows a mere 59050 calls to v(). This speeds things up to ~140ms. [1] https://github.com/mattcl/unofficial-aoc2023-inputs/blob/master/day_025/solutions.md --- 2023/day25.m4 | 46 +++++++++++++++++++++++++++++++++------------- times.ods | Bin 43197 -> 43182 bytes 2 files changed, 33 insertions(+), 13 deletions(-) diff --git a/2023/day25.m4 b/2023/day25.m4 index 5c795e6..ad7b1a6 100644 --- a/2023/day25.m4 +++ b/2023/day25.m4 @@ -1,6 +1,5 @@ divert(-1)dnl -*- m4 -*- # Usage: m4 [-Dfile=day25.input] day25.m4 -# Optionally use -Dverbose=1 to see some progress include(`common.m4')ifelse(common(25), `ok', `', `errprint(`Missing common initialization @@ -16,7 +15,7 @@ changecom(`#', nl) define(`n', 0)define(`e', 0) define(`to_n', `ifdef(`n$1', `', `define(`n$1', n)define(`n', incr(n))define(`s'n$1)')n$1()') -define(`_join', `define(`c$1', defn(`c$1')`ifdef(`s$2',,-)')') +define(`_join', `define(`c$1', defn(`c$1')`v($1, $2)')') define(`join', `_$0($1, $2)_$0($2, $1)define(`e', incr(e))') define(`_do', `_foreach(`join(to_n(`$1'), to_n(', `))', $@)') define(`do', `_$0(translit(`$1', `.', `,'))') @@ -27,24 +26,45 @@ ifdef(`__gnu__', ` define(`_chew', `do(substr(`$1', 0, index(`$1', `;')))define( `tail', substr(`$1', incr(index(`$1', `;'))))ifelse(index(defn(`tail'), `;'), -1, `', `$0(defn(`tail'))')') - define(`chew', `ifelse(eval($1 < 75), 1, `_$0(`$2')', `$0(eval($1/2), + define(`chew', `ifelse(eval($1 < 140), 1, `_$0(`$2')', `$0(eval($1/2), substr(`$2', 0, eval($1/2)))$0(eval(len(defn(`tail')) + $1 - $1/2), defn(`tail')substr(`$2', eval($1/2)))')') chew(len(defn(`input')), defn(`input')) ') -# Borrowing heavily from this, which iteratively removes a node with the -# highest outgoing count until the set has a cumulative outgoing count of 3: -# https://www.reddit.com/r/adventofcode/comments/18qbsxs/comment/ketzp94 +# Find two nodes relatively far apart, maximizing the chance they are on +# opposite sides of the cut. Do this by two BFS searches: one from the +# first node, then one from the last node seen. It is possible to design +# a graph where this does not work, but not likely in a random setup. +define(`v', `ifdef(`d$2', `', `pushdef(`q', $2)')') +define(`_bfs', `ifdef(`q', `define(`d'q, $1)`c'q``''popdef(`q')$0($1)')') +define(`bfs', `ifdef(`q', `define(`best', q)first(_$0($1))$0(incr($1))')') +pushdef(`q', 0) +bfs(0) +forloop(0, decr(n), `popdef(`d'', `)') +define(`src', best) +pushdef(`q', best) +bfs(0) +define(`dst', best) -define(`visit', `ifelse(eval($1>bestc), 1, `define(`bestc', $1)define(`bestn', - $2)')define(`total', eval(total+$1))') -define(`_round', `ifdef(`s$1', `visit(len(c$1), $1)')') -define(`round', `define(`total', 0)define(`bestn', 0)define(`bestc', - -1)forloop_arg(0, 'decr(n)`, `_$0')ifelse(eval($1%100), 0, `output(1, - `...$1')')ifelse(total, 3, `', `popdef(`s'bestn)$0(incr($1))')') +# Now perform three BFS tracking the shorted path from src to dst, and +# removing those edges. +define(`v', `ifdef(`e$1_$2', `', `ifdef(`p$2', `', `define(`p$2', $1)pushdef( + `q', $2)')')') +define(`_bfs', `ifdef(`q', ``c'q``''popdef(`q')$0($1)')') +define(`wipe', `ifelse(`$1', 'src`, `', `define(`e$1_$2')define(`e$2_$1')$0($2, + defn(`p'$2))')') +define(`round', `define(`p'src)pushdef(`q', src)bfs(0)wipe(dst, + defn(`p'dst))forloop(0, decr(n), `popdef(`p'', `)')') +round()round()round() -round(0) +# If src and dst do indeed straddle the min-cut, this final BFS from src +# can only reach its side of the graph. +define(`v', `ifdef(`e$1_$2', `', `ifdef(`s$2', `popdef(`s$2')pushdef(`q', + $2)')')') +pushdef(`q', src) +bfs(0) +ifdef(`s'dst, `', `fatal(`heuristic for selecting src and dst failed')') define(`size', len(forloop(0, decr(n), `ifdef(`s'', `, `-')'))) define(`part1', eval(size * (n - size))) diff --git a/times.ods b/times.ods index 575ae958d19f6a7d1db202295f492a2cb37b3995..57cabf4f25f11eb86ce2be566deac6e17774e869 100644 GIT binary patch delta 11913 zcwUWqWl&w+lJ+6E1lQn}-~@uh!QI^@0fM{xCP1)|AO}CVySs+qPJ+9;yTeD`xp(T$ z{F!f6?b=KFXe4i*j<1VRFVxGEH)U#q~rydVcKAO7{GgjnaH zp#CSxCrU^<4DLV6;xOE>|C(a{*VJExT<-ruaQ;J;#P=@{CFD8}{T~V>B&5F-)%vdl zVE$Qz!cqg`HCiV82q^fOsH$B^V6BPuU8V*^U80_+BOx@Eu0pn`MJ{{)Py***DNzr*{u|w=btgA(^E*Vf zJj-b5n71dSlTxr^rU`)+`BOtj)fK0ghC@Tx+inWLP$Koi!c?hMW1;()6Klg_U=s5U zaYBgpI#YMQ)iN(>M9$BQPnfldJ-DL_*_vCMy6n2R@aXpDMYUJrB&rd<+i#G`wsH97 zk4xVlvcx8)jpC1FSuGun)iQ{ge2&$smHZ`gSXwN|ON)=ux!q ze+;E4fJHw=vmJZJ5sCAwDriH3FV(q_E_bDxL&P+UPH#K{X8=NDMw9Ixo14@1!FI*y zn+HN^Z(0 ze6DZDYfOs9UiSs^?h6k?)e7-UBS_HJ>UI$i-IVD05Jk(d9n&+nC6A|FgqpU|nY%XU zpT4b={y~Qk$L&@e0k3M(Dwzh~PS_z96TQPKll3`8T(Pb%y+c)&LqwXP)m!O;0fCBP zL7@Noy#BS%kXU#YVCJZdz+I-i^$HtTrtHyUMK*Rw5*t3o@OZ1deN~QCuBxT{V()bo zmU-}p&ZJvMXAVf07V_a2URUSaWVs}{8 zp5abb^>C0U@}2m1cDt{D>K6ozb8yubrxz4@aR$x`|HRbOL#ZoCPb_y^5wq_0AC=;b zq@0VmaPETz0a?pjMHCD4W^i0kG6p38@bXdHIBWU*ib;pn0kmhm}MJvmrrBME~Yf+ zfMPQ@fhNk*{0}kThh5m_XHq|8R#?BK`(+oA9bsQqLpoWJot`_lKdS_nqRP1DBMNWB z7KIwm`EIuJ@&KbC=Yf?}5X|GOt0w2i-3@;OBi(f!bdE12BMt}cB{de;h;{GcXrle) z8FH-rMKy}3uC$Yf#Y;9^&wIGczf9g~a_!hpYO4)|l>d!9o-51hQFxaDIWz&)3ysf4(CV6hwhT zg@oQov^qIq@W!gSp-)JPawb8_h0z~W3o6m@cF}X+2cdFe!VDoHynTMKoJyU7-w~Fu ze*z{VRKI+lu;Tb_RaH~2C&$LXym}ZS){VXT!Dm@dn{*P-y8JA>iPqo}Z?_kN;RdXd zifx6bhOObqHCk#R!s6VqLtv>S36r?YG{Q3Sdv+*#o+aaRyhiMxL!5Y6_%Kght#l5igZ*o?V?j#7x1EI3VqZy#o)0U=QMnzzbxtnV_jrbu+s$e?HZJn<4cy> zy@jJUX1eC~#8+d;iQ5~B&xlxOkkmvjUtiij_qaUdam)N1GguM}1)`b1?y^e5Cw&em@ELG5y zV31)u7kL%gi7(W(VdYHB%^g=EkCJv)BiRE7ZLN235TvVtM) zw5P{Lps}UoV`Vq?r`c*Wg z-)IOx(nJl~snJ;yjk%(I*71hM!8mNf#&Z$LQ!}U(&q(hW9)sPY$O@;>jdy_2vA7nW z&ZT(}IIn#-uo-f{vEA8XD3n(#_o(fD7PiqyspO?@lF-5A8^DREQ;+!NK_{f2O^KI& z;u8maV`7fD!&oNn#SpKE3T9cbddIH+2A%UDnir*Vbt30?!u+(4YhgEwJl+w)H_I?! z7W^xpg^@t{U7>Izd5wFFp9n=f% zW-2>(DHT$o*gvm8CtS|(kZ#o#*kq8C1f*IOe=uz*-AMG1w+PF5iOKi&!-59~$UIYU zocaVdH_Ia}?hV(#%(8?4m9nP$P{;|Vba~aVgM4{4VufP+hNp--?Z3Rixxm}*4n zabEY)XExGmn@mI=zGUF-{j&^38GuY)#%gG%Q^r z3#N~8gO|3u3r4?9U-4?D@BZ-V@_E2~ypTPxy*8|1E;5pm=T%?~3FaR$K{TUXvXxfq zh4fsOv;iDpW8UNQ{WalInF9t*@yoXNX#@NUz3!sRIyYVdZE39-ADNtCc^h6omJeUI z4aDBLmh113AOqNq@eUVNbSYjMxIYZ>zA7~{#2k0)Ym+zOFrP0ac)s8N#Mjbk+ipIX z$Y^Jc8!fk}VcCPtqtH?A_F9_!;B})AhSoN!v+e6u#V=+oHS>X249(!V20|m|VS^fO zn>e;@J#8!2>t?e$g)?+xHp<}DXB{-?_R~i{L-PBVGz!>y9TIcK3d=Y-j(m5PubYX0 zsIDE3aklw$epyoVF|us-^xz7iV-nM;tC+rs`@~Fngu@MfsU(D~Z+y$XY=WCz?i^~* zHnjkKX^iFk7Lo%aR4!Spu(Ni72gL1m{j@=+CM8}(jAGBUi(D9g#J=A`efhL zPKJ-d0oJd#8)}zCTzY2e z;l}*Elu{#$l+l=`qKQGfjjbQ$!QGUXFoNtjqpzrMeJB>O+X9oO+RxDEk$qPtJQ9|Prcww^4 z(2$7(3V=t13A_BbxbJxw)YFbm6tc^P5I~u$Z3de$PeFt^# z*(c6fzm`u5+3mQ5lW02@;&?@!oP(TL^5D#kd65~=Y1L@(gCf-Fkd&1ve+G(t<;U9- zt1{B`X>i6a0okPaIX!eMOL=kdQ~TrIupR4sx^q`1!Qhq+HwjKNGg3UG99*_k zAs%|^z32C^SEeQf?~%~<2(DOf=LlG_R=*axsQCcMXL3Iccs6e-BBKYlLox<8i${%q z1lx;oK*>!XRh!y;xbL^gPDZgDS5cZqEjxBj=xMEkdMYlxd4g4XeS6G)CMkar<vWbQ*$~ z#fjyQKM*T6g~}$yv-Bo_=d!_&(&OWarH_nvDqO(z-7gyPoURO8roOikT%Rqdf8c&x z{Df;lTrp8#6f;0TF1V_lj)@~3Yyb0O3V0)9m5m6MJ^6$@WeKMH<~nv8zEpMVDh z_=#Ug^8;5&FpXETR84+XB#z0*D75SL4z36ixZ*Ba4&(Noc{#~SlNC0gO9q)W9(F%9 zgZymf%f9t!9?#e(s~MhPX=4RjN@9{hDUYSMVX02>p{HDxJWoXGuwRgrc`;{ReFNJT zS1!<5ywBi~FBOp893=wpI^P6t_Ew&F0T#^`VFBt_N^pLOwmT&8(>1t|R=9)~Lrh5LkUqT2t^s#Pebevvl2C9U1}=fT|0C~J$HUX#{= zb%=uX>9ZvLDAlE$wx?9xIlb)LnN`a=@jSros&-Zj$u}VReJfJZ(&Qfv)`^ z`4$W`ty>%~ynCd3g`dr$(?DRw9gWH&&Jk^^B?GnyaU%;&B!jyTYAtFX6CCTkNAoNE zn36QUh~4~*9~Tj%RzHK_TcrK#3%cv4r&rLTc_cqeT3}yKUiNz3)$eR;_k_v{Q-qNH zwwMV1`Mq|3gA3x^xQeWR-+hnE4n#k4Af)2dedZT2aZkua-5)HhyFnn5X?dWaLC1hN zq@rdntHwW;xo}@6%O^eJ|%UEn^$l zj`Fp4Z+9OgsG1-om#_r+^r=gNGu2klt)p>{b|?gpRxUrk#-gB7y8QO%384~?l zO8Cx0V|dm-wb2pHY-CBo=il_l=OZY3UJR2JTNg)k zhE!f9@HZwL5av@#ECypQ*v4k$-v}L?S?zkfahrQXN=PbmQd6mCHv2}Z%7a{o+4_?L z({rXkjCUun)lByEiAYtww>EPMwFB*%RcrE|Ybk-U!GLeJLG)h+$)3Q&4aF{w)K zEvA0qbPd{ka!^-=mz+y-fe$W&POa;67IDf~n_UoCdbxYw|Hi+wKn253cVNFcAFD4@TiHeR!-aJRK8pZ{&k3>-SJ*DV#5vu`uh-qK-CF&i1vSvY^pPZ9RKU=1}|6`2o0i%_tbkO zz<0NWC}TLHRQ2IJpGH;++neT!QquLIqwXidSbL+(HJX`M+wFSq?a-Za>He-Y}%*h-Oaez=deye`VZJFM;#xIB-~ZGK5uu{G~EpklajMSZ?oMS0y{E_ z{aW!#^OXeV4xcVVj+Y}@i#=zPSoZStBZ`}w-`*cL;Rza*ZC~O5XNCkq%ScM`=kL;) zX!s@(RWj=TTzY^FI4Ab}FYF}xwA7B{tD3Jz2Di?_*pJ)+Orav+@#OKlKr+Fl?R-ze zdE2Iw=RKb%ERCJ)yPdUTe)c`6;8gXiKdtwAFR&~7+if=w-7eU1IXhr*P?dBtP!r}~AxEicJ3YuXlXcjx@kB`6fp-Y{(( zn%FSf>}yV6^mNO`wZo9P_$H@KZUDu(xp>F)P-&bONKlIY@*vOBwDF5oN1HGez4tkta>+kd#6Vm_k|hi5~i)J1i!+< zdK{_w(nrdcQy-)nb*GGkqFxl*U&_w)+0N2MdjDyEuh`OH8KSKKt#nW#AGlP%oIN6& zj87QvkuAd5%xb~B7AT#E6$y8mc2yfT%3h2d1k4J=%hl zEy9|g(~D3#8JVpnZ`D`H z13UUlhg>zvN)Mmyv!Sz2j+E(*tqj!BfIa`Ri~DoStu2f0#^#`XdhE2)!onlmYLcXZ zrxM4W6<71^XN|JW6{W}1j5l@IRxP#n_mNAfVIBviPby1qTJ}mu1^G5$u!j$4rzHi- zU0cD&hm~#h_c@MBPY!h{`pXg&jGuDfUVhdHTl#Xu8bS_D3Mb%mo$NCNOo)!s08c>! zdA{nilH{=H8&BTiubKW49CrJAq5_{5v7-Mp6@6YgPn?)^;UY@dm+>{fJ;}bi*2Hu; z&J8#k9&VobgR<0YzYiwE(onRpUQsTxE9CY%es(Tt0U7X#OqtCI*

it@QT#2Dx;Fp?m4 zY{^(}Am#Sb*K=JjEpz{4OW&%%{8V#B4peP@*_``wh|a{e)K}E+WT5-B0x()@mL+e> z8a}Aml*VgK-hFI3-hEw^>rT#bnNa^2LK;{95!`#|D(-u)sTSs8XY898KULoTpe7zS zC1u@I@uZ^lZ0=gd#QM-XJ!MMYtU=2t(#6yMXfX=w>8SE}H`p$y<%pP`Se1VtYNm7K zS#9qj5t5a)xFaGlc&Bgo1{k~~nXuhnxVv_#50+T;`G-H*ZorqeaU|= z{VPo*Hp^^5Ly2TJwN^;47AebQ4YEvIuncrtHO5BvqW?$Uvk#Ofz&BR{H97hfOJ8j_ zROj}{)YI>dh48_AV=PeC9usrBF({)zUocy&j#rmx|3 z%QlD|o&6AM%{t)TN4t6w7bJBbpFuNk=3_ZL+tPQ2b$@(GvI=@y;dc{?*zx=My#=aA zr$UgE^s2nCl6p-5Tf8wqIdWzzZUZa->l|i^gefgm4^kzbAT@>FK!$64%+zyZu_(geFYe_^;m+`55Kgxr11um%#e}T1gcEo$#lW-(% z3dKVD{(A7@3WOOtYCb#n{?E0**+ctulclCEEtzwLn-A(j@K-99*}F#lsh1d^uNfS* z;oQHm=Wv^%l5X>OXEQa5(HEHJ&n!w+{uXtPK>tq)B6OYN$08{(lF9G+HiEV5s$X!y zya;8wei6p8umXEirL(@1%yy-OX89s<@_QdS0d-y8u3Cs;+h~Jy_ybnE@9$i>d(DxC zu85YFc>5Ed2hdbx-)mlDCPXih_i;hy-r%*T5A^-qR<<2QobRZb7ekN7m5AeiHBr{m z1exwLF|pZrHtVGTUUf<-H248Fxx#j0BWYY0XB}vbau_#FHP+2AuEFZk?4=etSjFe(a0toMHJDEXfZ_ooW5-3`xe zo39G5CIJ=MBJcg%`{;$S%MfL|&TkY)Fxib&3<`$cPV$GG#7= z<4EjjH@2QkjO#OTyY}Q?C==u+jrK8)MsJzIKG|*=UFR%QP+tYd(Ey5TTFtl-=Ej8= zs?vhH@uA#S`f&HUAUZp0LzRlA{06O2(1xyVZ#vxj7WLxA*i8PW<_;rMgJOP_KX@Y>!|Fj} zPqnW5p5~@tJW;jE6+hlX9#0Psd%8%bgWLL(?=4oOhv^UO&14MsFmKZrPkqan>h))h z)D#{e!*gJ^JqN^N6-&|69kW?HP1n!9+aUNBWfH`cR#$f67;`prva}@Ss)x)YJfhGR zthV*Kx_vj7>Kb*Fjgbm#v%d~ydn=waQ6Xl$=0w|%yX?vJ`-)Dc4*6|5$=;o}=%R_X z@S3|@PZHZ%7aebr7fRpM2Z*ZQ#n|*+g4g_wF zZq@zS8UP4V=az3rmH{Pl7w^CVdz?sd)vRPORD&RGiY_lC6(N_+4&N>pr>H5k3i8e! za9}i2ggAx?Mg0zr&?Lie*oiJ@q(WioOU#9_TJNr~z)~hwvA2Zm;NbUE=HCM7SVdTn zoQ8D?8>m_+x2ywR7AXl)zz9OPUyzxDqGN^(fKPOwU@wq}MMzi9E#@XIA#y-;o_SOw zeCUT~*&2->?1dwP!zH}4+(KZUU8l&{Ju|R@zJOuW{IZ?gS*u6gq<*-yk&ZdErzx2$ z;crsnOs1W>kQ_VxH~k1S0&Wu~nM$p=Qk4h-I*YV4IA=?&_I+AY^q@`HUfQ>jLV(U% z;bc}C3&ExJ{B$(Rg~IgJa*>m5+_$ijnZQYmMnDb2=%QxSP$0ss#u17u5bV~aFE%H` zjFC;smNhL%vhjWnt2O+}vj_3_kCv3XOO;-^8fw4zaWXKuB>x&8+2J_(3+X9pL$$f= z0ij-j#qS3Zp+%{8k-SE!VajJYfL0gJvdaaI%w`^}6aLq$+zbl0T{q5FE*e9pP^s@P z5g&tUBW9+0`VdJW@&+qgLm_g2lHWe~qcAi-xZr`h~`5KEWL(buuzxU=6 z(jqMFtzNi((JyH~YMf5Z0oJ{3wGbbfx)426X{KCOX?{~!bi>3tyTf}3eDJD4PUy_j z^>NLS(s#3bEE2=hrp@;@WLHPWf1P*K_Y@1#zM$^F7N5 zh9Om)U~Zc97Lqe&+9SyI?e%P)=Bu+e)gMRAk6y&aS06S?5t#+3j|CCNTLO~D(qy`96{=HE!wL!TaDUUm~rzEqAWwe}I{wWw+~sG9yPZ!4)4FuE^k z+DTA5dV<9rU%Ou{$*4M4yC%%J#-cz!)Aap|{B~hwUF#TnsL_OaEX}e*HoP^FfD_`$ zm5aX#M_V=t)umOZRK!Ib&9p;c@*UNRoG)cE?(KoS{pjj)uZ54myPFCw!RaF`_bhsu zIvv3?MEvx9*lz+AL3?h2V1x}qhx#>C8Dq^z=gHlV(prB&ouYEm*$*$0Vx%%J> z9vw5I=^F$$+_5ZQ+I~|PAO0Pj!*c9RJv}ipmjf9!&xkE4XR;=GK^;;B>ekw@~fQ&Jk%6jq#0 z3Ef@50@lJZ+VD>zC-yIy#q}#-@5u(Ar_lRXF2DN|ccG6}!C8{J;0N_veTH=6A|J{) z){EHddpGfgRzwxUpiFVXJ<6c6L!3uCaZfBs>`yr%EAU*L{?Re%*5CV~BcQ8gz)$F* zxV8v?v!t=kk2@(XU2ETpt*oTFsIjQ1+xCn*>0BWXMGg2SU}^z``SvGWrMMY6 z<-K&=;11h1j=o-Q?*aJOh4{s!M~eWoN0S|L;(XxM zBhF4bVLpKJsJ4^-CLcg}{IHWwlnvtiwE_?ilUtvQ`K3Ha|z58wj*S#yKMO zP!fjBMc6DGa_~w5D}-N6at0kMHrIM@9DXI3sCH^xuM~L?Xk5$h@3CD(W&$=TPskTa z8Gv!h6a9r!CSaBFM07El0hpyc@m`E(0(L1+@E5EZKxQrwa@5QB@WTcvhEh5h0TLn1 z{;FR(J%}rRVm3YW5=k+M?Y=Bn?WmLfI!^5fI#u{$1R(Z2!}He);pZ-%zgCDoPw@P; zLgaaf=dTrF&kH<%tq^_|RRW-V*5x!w22SKGI*w?ryd08GEhdjxJd!JfyH1#+51KKy z&b>90Nr*f@PITM_{Q1e~+y&m3^7oDj1wU0f-n|iq2nc*i za=hCf6AF21bi5-NYxjTpn)XyDw=}zQG&_6Z^_Pn#iI@U<4_xfrkq5}Vghx`Bgw)Fl zI`Xu@CFRf;fyg;V>a;=^!t_K4H-zUQ?KGmqp2gy^VCZH}*=rF7_C<;WuhCu-@jN(5b;Ex6(0{lbV)r4AMKB9}pn~|sf8|s_S zJM<%ayIW$Vzv)tfd#8cz8+@eX|vp=YP}GKGzQL({8*m9wYtCwhn*kpPllQ(x|k+p zV`l&M1qG^E`Z|nr{|f$K%=zF1YA5;0iufK$4xoUu^8(9LUm2SL4JyHZcu(IZDO;N~C8&94lLF6U#vR!p>37A_*dd`Iv+J zaUA1~?V_$tLgK+U-gzy58zY!1-^QL?)NshB6b2we0(OW}I2c5<7Z4Wp5 zUO7YHf3{$HXabD(TR1V9O`Vde{owoV@F?~Zto7$0@|g@T_UqPEcp^o;C^kpYC8iNa zQ#~zt#p)kXBXVaN<#%t^VA<3>g#7ar4G1*~G{nggs0@KgVPt2PHRpxv!=w;9w=#zF z#{x+$5|!GMEKf zvwkcD(NyX~?3&isW-X$e% zz2#&0Gvs~_Vv!-r;HCiP?dT7jPka=piiB}2_(piyNx;*A=+1WUY5ER!MVep?wSd~0 za+VJ=ks(K%$r6eagMotFD7Dh3gb)=?CN1Tcl)>B*Y_SjF%M@hf+lZV^9X;VBP8xVo zpd<{RR)iGB6fP>-?K=;QEv1mS-Zs>7vcmk!!agKBQ-VZnIJttl{W>P;=>A2b%?ABH z5-ER3$C>U!;If2x#gx>iZqbqk{Mq3Klrg%i#ny6KV@$7x`?O!An`KjxYt=p1RGHkE z8PmQuXZjXZ$t2ptzTAMz52;9J0{kMA7xkpiyv+R3U|#%Tsg#xQ@4t;n;dWKPIYFI4 z#?{cyY&e_t{3)M2b`VYJ@c7Oa&HtK_TyE1uEKVusEG%;%U-foEdGkY|k6FQ4qq-os z`mHE~(GLA_e{NS7Wm?om2%&6fCYiX!br^DCER9f?v}gneG=el$jS}K}~-Tzj!TQb-!F-iXp;;J!ythi*Psj(i;mgU{_xEy_~ z%dM5&TpWGT=3bt}Je{ihpab@*RAWxQynIw`oPJamJ>NCvTOK-QDVA#Czx}=*3%e|| zYb7A?u(4Zg1;z)m#&s@tQAfIkeq>(;DAlqG36{0`aF8we*8FTznx3MxVs9$`uwC}{ zxM5NMLUu!ORj5(Vbdd?5^J2xH~HEcWOyOUHjqjiTa89{_q+0Z;fgL8&q*c3Ie?! zg8?ba!Mwr+{dbiLqLTAp7nezLi6L1zxRBScP$12DDF2>&6%K;vi>YjL6Qo{5I*Gm?f*XmO7MXI delta 11828 zcwUuy1yEewvM%ltoCJ3W7ThJcgb>`_-CYKEoq-{^y9NzTg1a*~!QI^-`R}>!opWE+ zt9nyYwYq10{dMo%y=Sjly{aZ*+9zSqzsbYG;X*+nK|w8gOC_Q!!M+V35oij~7&Pub z@-{U8-!ajM0)$?Kg8FahHyGDH5O`>w|29iJ!ToRaalwC}6OB0j1*QP)6=D1{g@lCk zcdAYoMiBa+$#hsM0QqA15A={A$r4q&X^c#DtJHcOiKFU~aueykq@y)Vw1PpfxPx!} z?bGUG*Y>khb&y6)C8syZR7420rG3cEDF4%s`li+)eq5EcLaC_Y z`<|O=AI6c^OPZbCx==c!23wCK?c|OhGgE`w6!y99ed^g2Tfc(K403ujkU=Ag-M=g~ z`Bm8>aU|#|0li^cG0KfY`AO7Tau>#2*)FB@@D|aWlGIYvO9?@}Y&w(l(QMy(GSSdEA_{;(drT2xJ#nW`|83tPu+`%ly8mMaNA z+{7*7TfK{+oTjaKd}keD_~;u9wZNk#3$f~`U&VBj?=~>IAoe=f1mENlkzC>%bGxCT zpvqyPp#H16{*`7>GCT`lVdZ**WxoNUA4ECWK!&Ls30#oL6P-F-dAjED-8Yj3x5r-{ zpx0tqgmHAI-aE0keThxe=TS8{fw~u5_M&MbGb{lT)uGp-~r*3l?l;c zi*4j%2^sD+32TP^4R4T)=0YeTHu}S?H;VG>U70A~4kK2jWh5$qv1Ktui=n|=aKo3v z-kgYHD0%nTz4hLnt(fUr7;r^Big)+f6D(lnlyU78-qCrc%qj)bd<%EFsu>v`JK#eT zwC%jlP-YfuCH%?l4|I6+=`U#eX0IL@hN710=JYtaq-~W#8V40_X=9E*)5*7_5eL<` zB3k|=qos>qj))!r^o7a%3^{y92N_-u%{R7XMTl9=$Zk|=DG7ugS{nQIs)un{fm(Qb zF}Ma{u*{`uIqw%^TX65PwyZRZPT((dQ@iz;n*CMvh*s(<#TAGZYqWRe5^DsD%vxE8)961l2OjoEMsy4b$+Z6 zf5Comma(;zV;RdJ>fRhDr+Ktz%N?ctP_1&zyw?evt}<^aYMP`L zJ`Y)Fdhua^nz**21vOFnzHwutfQ6V5@(nz7*+{&F>OJ=% zDD!VYGTD5s?N47I`zCvD!0+qrxKm#QezK23J%de%I7QlJjsr#@amV}gM3m8=23Wa@ zhg@Q;<--(`bJ*&HJ4HFg>;8FSnDfgCDl2qcec1$Lj}>?Uy$$lHuSC8NxlSU1TOHa5-5PkJhzYthvgfE z&pUws*C_ApEz(-n;v?dc*br-WI)gysyTWfK?>|m4%NZdNSd+ti$3pw^az9-mP>DJb z7`6HYD1BcDGh8xjnKx@{WxxYAR@MH!g!vdn^V{Msx2cA|jB!qX8_!L=<$!T2o=o-3 zCy$?I=3^0c*@kVF&Sa48PS7OlR8|bkr%tU5y^Q?2RH`OD(P5@?`jmC{NNl`xk}um+ z%4Fmy2SXNAzj^431PHJ}ChNijA;>}HP|ij1fS36K8xAuaq{sI3X+mIbNJCkj9g~_F zWnN`Yn*_U}Y)q-Sq*n81_Zw#&3FGn$B`tJ3nJsILa|(F(Q$neU=-)#LNR-7MKRUDt z8(LD|6-4}4Ufa_8QktM%#-S6$9#>ANMbj4NlRdsU+q69&3YKN5Q?`eppU2m+C{bnI z0vx<{R1K_;qSSm$g))!XDIx5wwZ9IRRt1E?A8nlwjG#0)FJ}9>e7UyvSzCY212`1h zHK{uzftcHG%#rMV7w5;aRsIedV{w^Jm2;lRj53+e{m}iO>rIMgW1OklG9X510>G>(TXE9rT$Xv{d7v0--<59_DXXFK=$^` zVK?!5xZQo(o;8DyW(Fe-XU!Umqxag4GCO|#gL5B7X*8km3)>@DwgszEonOKvauP;T zBTrMGx*1AzsH^uP2A6q=1W!!A?h2bDBLW(G+I*(IPao=DnpbI`r#|>frosK4H~HYM4a)e)-QJcFihpPYcoOIP-Hup}o{J3A5td zMFt{Qp>ngm?AD>tzy-#KvnRahshX5k#5`knuDWy_42G+{M&67+1p^Bu@e)%ZdnfjhjC&mwTu5EHIaS7j4R zqwk%6u-87)$Dd{!#`g}$&j(o5zGlN=>%1uA-SWt7f_AvgGnHMG3astrtnOZVLr)bA zDlk16HBEecXyVbLzMNY&3y$TVPL}seKd?`x(<`@6nL4}#&)|*Ld0zRdKjV$<99@@p zeejydmhhvkPetVKE#~rGlf1ZDFKjt=IGLA$Er0*@$Y8WK6G*v3?F^8J%J_3BdTH$| zTconr#^7=4>q1bAB!m;0LudAY` z6@CBQbLwZ->}@ysE6WBd1kAR?3m_4UmiVv z9^cx&cj?uOrF1TB{Wz)#Q_OHTTLrxz+)i=3yMEzoR8>i_%rG$$>h3e4Z`LGDM6fx` z=t6Leu46WGj}KlPey&Qj1GTkleu*%;1K@Y>G>d%ChV;MmZRY~Kx^oMjhP&jhU4uHF zO4Un#LF0ip+I<%;Z<-Rnz2@7v^R~8scH{~nKDUlKKyQ1W#1X3($a9#Bcu{|UXmcGq zGWE1W6vK77@xJ3TgSFPiWZ1nW5T)%H<0wCKo8hrK5SKT~4S-xldQpy?(5C54>Q zruJZ0G*|I;15c#nDA;_;zC8V#b^!u_;lHIn>I}t&b=ZR}pbDOo>8L~AV zb(y~FY!Vwse^2W{)8d~HS+5xtEix2TEc^dlMqOes1Kjz8i`_8%mnO>s zEWJ{3$gTSlYA7NeAP%C(?o9P0Nqnsq#jN0jr<2jqXN)F;IhGF1&pT9dCn$xO%Ih%L z>HHBRrzj@vZuiY+g%ADAnWG8lj2I2D1la!j;$ywIuVPGe{=G$}VLd?si74>G7mRQ} zC#oG=#e`%qhChy505pt^TNAmYOuaNT9Z%GvdOx9wglLe_rxVE6G7)Sxg_kBx6-Q#- z#MOB^YXPgGTX%~W&Zm9eFP*ZR+rGYXOzPs5A@UJ78nmyRn%%lY^14zj=pKbr8GFG0 zayAP!yrXUqn`$A05DrM=hoJYoJGD1T18NuL!<-OC<_|6l;`z>xkA}<d@V?aX6YHr|lziRH_Ocv$OL=dUZ&e`2I9ln)MI zXzmBtorwZJKq2;*u;tS*l%sVKOZ7c}d{B^bwENu6E#B|norfzfilR0K^L>&xf;j}4 zgrw?T6t3}okrC!tV7qKS7wr7Fj4fgXvO%~JCf0mj2p~L(*@axKI7BpEh5IH~Dxf$j zoOr->S3;(mc4J&Q)oI`XdIw2bNBmteDTEOY2O&E=r5@r$>{-niLnR@Hv=|y>`+M(O zSmTBa^qj2}TO*V_`U6d=Z_xeA4YEM?JFJLghXKPR!L6KitoJzVA1+U`*PtcuFq3xS zSMo;CKLO4j1DI80Gw8E?1zke4i@(=OBr~n)Mz-DWpp}7w|J;gILxaC3pDJ*br$GB3 z6@(BB2VPf+AbD)$R2u0?E-CO*iD^-yywILL-lt zmI8pq+u{Z#9=jYfMRGNMDAueIw$Zsh6Cl}$8qW%C>QDI;QDW66Y>HkKI2U_-^9dM% zJ*$mvVl|`~JSYv0@JBh&9G=fX_@dbr4d)rI?d#)*K86)(tZE)Y>!hy-C@Tg;`^TBZ zl)%9`|G`cUBSFfLX&tlY;7cK@nlM#r8wZf%EGU}H3z=v%9`f91Xr;I@wYp)UnDbe(b6e>fWfTA&##&&{d1?j6(b-Qf+*b9TtxvRu~q7?&JO_K z7e21n~(nQ$cIKbPX#KP;J*G#>4$ z&_zvYaOW5AR!y<@Z+KWmvW+GuF51h+r`1-077@M(%k9)N#t%FXS+Ul{Zda`WAD>U3 zSt~zJ+Su<`lxmUmrDg6eO zvNk4Qr!!uqSLY&3Al^D>K@H^F(_`hvE#7IXntrvdMz6bcp?EtZa#o}I5`8-88~&+y zogK?)>An!S-x+W)^XJ&0S0?Wkn5zqI9@32L3~p5ejzFMxAwW?WY` zByFsICw=-p_GBoK!E`bM@}WibLoAwGQDaQvDko{NvQ-Ipzj$FO_~_dMNqJ?h(62ochS zauD6sfF#O?3&Cpp@z`Sy5Iy+*;I%gfc(fW-$?V|uw)26zkBJA`assm04+84Nb*w_*z)x9~T}YxE!bRVq! zeend7gdOQ1KtWa0|M!dMUpqLOzdnh@Y}rFWZQ0kw;h{PF-La|53~~CetsAT`Q2;R( zP;y~tFa4VqO;lc7R}td<9@Taclkln?qI?C z{$!vbld4=htD>lGd!aQy`vrI%CJlJHS?kcs%o_Vzwz+>`+FAluI5lms?Ex@5-PQ{0 zJCtcZsc|1rER9}xs?F6scxthf0Umzx@#$BVZ_l>(-=6ZRpY~pZT5i%kq<0nSgimf+ zSy+xx*Yxei9su{*9Z!`I)$FvF!U>J*5}Tbv*$<9rM1$H`EUzE3f=6e-gLKz9%^$} zyf;L2ZeKttseT>E&-GPLuQ$WD3#cqdW@cs_eh7EB|! zwrlPCdD}5-?e@&?1xsBeN4K|mO2mGUEjgPwlAIM;>67xKsW%9o@sQOrvcJX4w0~lFb_W1j0H@|Fg1Hv+YpRE{ zMGL3f+3wXX`2HndH5jdo)u&aA&Lqn9E6MgBuKPKhSNsKi3T!enQizjmOerVzDmYS2rw&_t=99WLe~6Yd#hM=?sN{$Pxc;Db5tcw z+gVe7M@IHJ(X@OYWnCkAmTuOcHCRjR?xi}M%P;gjt7p&J;Rn&j#f}?a*V2uR2-o zoY#rQP_s+ZQqw6e-^5HWduqPT#qLuP{MPYs5GimTy`U=fEl!9y&Ro9mHH$y~u+i&F z)9ArQobd)=s6+iuR$s8%++sJ@w^@KNDn+F7tg*_w+>Jvg>2mdDWz<|}^4fkV{JNv% z=R5Vv#jCk(t=Vo8SvPI_-BFSfA#%c-{R;i@;o(f-*5bjgFP_V*#$0%cX%60_;g4m% z&*Y-DuTL1COg{0qfSW6ZVjCV`^;|g&n8&v`JT%Mz)E9QA=`SzY8lB7%(Sm@N)#9sLYiDaD?~&}iIN$xqEceXS(1<;{ z)&Q>qc2bM$w(EIVMO0nbutk`68$RJCB=*^?Tkbm zG?-g^*&qKw^OS9?y>{gR>DXWM8-_h?um0oK>6t6HhU#Hu2bnrkj5jDtsq` zhY*7ohCI1L5SNbjYf1TQoi_oP;APXsrUkfC223V5&RFxWB?xT$S>gY@ZIE65GuWr- z=v+8Y3yipWM5I5NTVl!6qB2=4tN~c+a~48$TM}q^5n8D>Qfe~LBHP)%u#o?QY|yU# zY|GqJ(rrC9T)3_Ed(6I9JT$@c>&ggRe@lgpyn?^O@cq+;{L-H5QUY^cqr?|WyGHp# zW7&)bsA8aVgHjJ zVq;ZPSmOCRe4%z(cgSaWdj?o(=Vs0PaWbr{!y;%@oH7%MxP zQ+N1m$Q`rIY?ym|i1clPNo)-1w7ux8{Y03%c$s@QcRi6(15rax=I*-~q>_(tzJ;P3x^h4THMm1UY(Vy6vb1s5&DmcC7sRk*w z06k&YW#lDDXb^c=;9s7WbC{EgZVc=5UjVDQ`IrjrCAQ>z$wqo2c1oK zH7IxIE9YtqrlFL+2VfZ_ohHctUS~v(zhVCTb}4sLX?0$S+psrlM7+PDpMH5984*rC z2M~E_G=0lsk>P;XPc)J4@uH4!hR-GaG0HfIUmV)hH{U;J1($l2h09IxXn?3jB`&pYI$qJ`@slrGZe~&&m=P+RY{1hO#hdfV7ePLaj zkM9SqWKsC_ueB2K zfykuyep z?k=YJfSz{`q)=}Oy@aDc3}_`3B1AYLCnj6FfOj#)nPOv==71?x5Bvu7#RoqKeUot? z`;FaMa~V6i@3XyHk(dI_f1h4E{xdO3kP{;{tS?vS!{nQF$NoTUnu3_@MFX;Px1iy& zzTpnZMNgs&z;L4k9aWwv)45W|)pq0KSB5(Hw5+efEm1Zzs!VuFkFdg^k_Xu7# z#uh6s#wJ}n3WSr z$fLeB6kGeapxK-=tVi*a9MI|=$-I&1vTBaR+SyDLz#?AopzTM(77-HA4`z+CLtg)O z+qv=)#SS2GRIFUokTs2)?|Ze`K&L?9@-lyM9Bi94)o3Ex~PXWFy~2W<6RM| z;crI=2z*&-y(dP!a>wssOfjgA-4pLC2OMuptV44`#}ltb$i>9`@W2g%B+3FX;f(DFH8(17P5SCs z%j>pKq%M@DJASY|gZLo!m=IEBkw!V$#-Fi*JbO-~=qSPmzUPiTGt^=N)Ce_lz)FV% z9t97FaHjijWK|`RKdTf_{+5h{Ksrhfy*|oCDukur<_d9UKuN}#0Sl<%8>Y)BEIzqv zWiBbp?iXK21u*_#Of!f#@VIrl@B&S>78Xd8B|jIsMeD%pf86El4!McMSC@6>TV78% za0;c?aYGwWFz%Y6m7u_B4FhhWk`AU1{KQ8?7CzuCN;=92r6E=6RS)fHuvR`B)z&od z@1Y`1&6jB2>DJpI)uI`MP?lV?Z4Bq*CDcj7>&h<)0|SPbOIJ zg_`c#GM$HLj@rkfI+!!e9@+)_2V&1Su5I$S_SI2s?DD?VXwO6wVhAo+Z}a zqwIm9m=li(%Voqop(+9e*P91Czw7&h93x>!?M+D4ESY^*svg-PrXU!afD)pL`3qgo zM>KBr_1c}PIkv`%AdnQW2WS_?yVMgLdG89XBX-&TlA;TbG z8Ltn}G)yJ^ph)uXmfm53B=1BJKi8|ov6p@wK5paV=M)j*KX8dpIxy$Z z$r92{XkDw4zi9VtoXv=~d0Rp>#=5cDj8z%{?sq9`yqme0SpkoO`f!~u7p&!4TC={5 z-AtMFhb3 zMfCf)#aS7(UJI{5sd2!5)?~iI&o=wAUIJrZ>G zc8$YB){7<*Uj2R=i#AtG(>B{TPC-cBj_g8O77e4>KmWmoohh&@Z=>FTkTc7k8I-j?8B=-lhajhTA;A&K-4)N9IZO7x~3p=_3 zEliq)=DvQH7~0k)8XvvB8FN>fyEc0XZeOKaG%_a>t)>oZSIR;?It*2+lc}Vj%q7AB z*Q^gVOQ^>IcWROfvKQz){59ZTR31>LqKKCH=MBygGtuZ|Y*QLQ-EMU2gXjR(>rhMO zt-8*3*lQxsySL4_ zpb2%jplw$$FYKQC8IUH13*`e&Dk<#fhL46ntPRA$XxCR$r^duNAd2TbtL6FH*bD^6 z!CHM>vh?TN%}w6`HQWzI>RhOjK^PEN?tOVv&I5Q;XA%y)f?*{mr4Bb`0RxKhQS5gYB-h_sne+h2(J~Sp%^-GDGXNJ_=W1p^G z9wB#%inNv%5&K%#@wouBXOqn<#T)?4GtS$X3qW~R*}NLh0U$hcyp6d4jAxh4E7lwU z^fRi^vzhlNi&rw|-_fnNKiK1b@gi($rY9b60-|aA;fQe@zqs=0+qHWV8GOA1ezE>} z0Ihp1+I$dbr6&~j!gduOJ1r9Uf_$YIGc6MO!f>VdrU$>gzZ!qj!(aHW#$%^D176^- zSnID&C!aOr*Aintvm*@78v>DKXvtIeKodJj-r*cS8vi7{pFXwb-KNO6_{O)LYn2J$ z|Nr8@x@sz|yO9Gf&|t0u@%lAW#7(xw1?I8?Okm<7SrE@B9B3A}Jih2;-J|Sc3Gc^A zJN8p;$4M8t?GirpPl#}TeT93Vn-F39`ilEdJR!pMRr3|?!D2#$K^>xHSREq$lfNucCKZFfz6UBVk;MOr!|Rub&X*pyn-<7eE`kpq@l=Lg zp+Jmt9@r3>qG%DRH3noR7Q#86{JbimIi@sY0IS zm|0pxA;&e=cH>9CIDF1Vw8^Jdysxn8AkA1Dn|u);vKGQEZq`%%ruqNz%+-jKNZ=>A z?6M#%Scf@YfhzVzyplRq=uJNA<~R&$)2^8L>y}!*n-%eF82ZWC@Lz7(x@gS_K|v$> zd;uC5f0EtU_&Lt9p-f>CBDn_`{j@Bp>X3H#7e46og=k=`CyP(>yT18jVDW}pSv(d% z7$T%MxjZn22|$LTO@rcoE|?sv>~)VE?D$^i2S0FwN4}I|quY`L63J#{=jZGqhBZY? z_`xExr}8<3y3Rn#oHgJ}y-kSkL*w+X>841;mQQrIC<)7qqRy<4pGTq~_dEv9?}(oe zx(K066au~;$B7xgSzL+Ez_2*f-^Ta-u3oxz8`GH6lx;$2nUN7 zh&+pl$z8O*P!0&8`sez*xY(e(;Gl3;(mwG^alk%)yBfODKiS>>k=%)FehKYty@3=#SB_B)e= z)Ti;ErebgRg-JwTf}|N));vBo#t`cLVGu9Xg=`})TtuluQ0#LRkr*_eGykbs_gG$NI|>mAf!%bgSx3Xb z=J}Ll8t!-XwcNfOKd`@ZfF%bs@hMDF9dx5I-zu9401zELVW##H;t=ion+jLD$zeEh zoPP@S>e>>}kkwazd;BO2f}DWlnEqLIdezLVzFq}87q9<#Ua5)xb#An6QtE44auKO2 z%%*y;`Z4=MnJ;bfIGUPp%Fu4uM+2E{RH1F5=8^BbPdLD*cP7YebHPZ*6l_|_z%4-d zcbSMtbB@}4i$d{e&Z*p$+XRhjUM=S0I`c+t@MRX<$MlC%vT8M(p;4{bEAH)!ii70o z{i3o%59!nK@-nC1yGfzd=hGgK%JTBb(ODVqwRFgcM!G)pO9g4$d^vb@=fb^o`M{q( zx7U_W$CiL6WtM7{Sy#gv*Ky7Wp_ zb<@;&*4>W|yZCC|_$#(){c9`c!>3dKps<3!hmO%e z21O|UG?Z+Mh+tx%K#@hv|EL`WL@uLIj-zk}jeCC!T*#7wUglAc3MvND;&e{>uLgiESI` -- 2.11.4.GIT