# Original solution
import base64

exec(base64.b64decode(b'aW1wb3J0IHN1YnByb2Nlc3MKaW1wb3J0IHN5cwoKY29kZSA9IHIiIiIjaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y29tcGxleD4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHJhbmRvbT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dHVwbGU+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnVzaW5nIGludDY0ID0gbG9uZyBsb25nOwoKI2RlZmluZSBhbGwoXykgYmVnaW4oXyksIGVuZChfKQojZGVmaW5lIHJhbGwoXykgcmJlZ2luKF8pLCByZW5kKF8pCgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIHZvaWQgZXJhcXVlKHN0ZDo6dmVjdG9yPFQ+JiB2ZWMpIHsKICB2ZWMuZXJhc2Uoc3RkOjp1bmlxdWUodmVjLmJlZ2luKCksIHZlYy5lbmQoKSksIHZlYy5lbmQoKSk7CiAgcmV0dXJuOwp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIGludCBsb3dlcl9wb3NpdGlvbihjb25zdCBzdGQ6OnZlY3RvcjxUPiYgdmVjLCBUIHZhbCkgewogIHJldHVybiBzdGF0aWNfY2FzdDxpbnQ+KHN0ZDo6ZGlzdGFuY2UoCiAgICAgIHZlYy5iZWdpbigpLCBzdGQ6Omxvd2VyX2JvdW5kKHZlYy5iZWdpbigpLCB2ZWMuZW5kKCksIHZhbCkpKTsKfQoKdGVtcGxhdGUgPGNsYXNzIFQ+CmlubGluZSBpbnQgdXBwZXJfcG9zaXRpb24oY29uc3Qgc3RkOjp2ZWN0b3I8VD4mIHZlYywgVCB2YWwpIHsKICByZXR1cm4gc3RhdGljX2Nhc3Q8aW50PihzdGQ6OmRpc3RhbmNlKAogICAgICB2ZWMuYmVnaW4oKSwgc3RkOjp1cHBlcl9ib3VuZCh2ZWMuYmVnaW4oKSwgdmVjLmVuZCgpLCB2YWwpKSk7Cn0KCnRlbXBsYXRlIDxjbGFzcyBUPgppbmxpbmUgc3RkOjpzdHJpbmcgdG9fYmluYXJ5KFQgbikgewogIGFzc2VydChuID4gMCk7CiAgc3RkOjpzdHJpbmcgcmV0ID0gIiI7CiAgd2hpbGUgKG4pIHJldCArPSAobiAmIDEpID8gJzEnIDogJzAnLCBuID4+PSAxOwogIHN0ZDo6cmV2ZXJzZShyZXQuYmVnaW4oKSwgcmV0LmVuZCgpKTsKICByZXR1cm4gcmV0Owp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIHZvaWQgcHJpbnRsbihUIHZhbCkgewogIHN0ZDo6Y291dCA8PCB2YWwgPDwgJ1xuJzsKfQoKdGVtcGxhdGUgPGNsYXNzIFQ+CnVzaW5nIGJpbmFyeV9oZWFwID0gc3RkOjpwcmlvcml0eV9xdWV1ZTxULCBzdGQ6OnZlY3RvcjxUPiwgc3RkOjpncmVhdGVyPFQ+PjsKCnRlbXBsYXRlIDxjbGFzcyBUPgpzdGQ6OmlzdHJlYW0mIG9wZXJhdG9yPj4oc3RkOjppc3RyZWFtJiBpcywgc3RkOjp2ZWN0b3I8VD4mIHZlYykgewogIGZvciAoVCYgZSA6IHZlYykgaXMgPj4gZTsKICByZXR1cm4gaXM7Cn0KCnRlbXBsYXRlIDxjbGFzcyBULCBjbGFzcyBVPgpzdGQ6OmlzdHJlYW0mIG9wZXJhdG9yPj4oc3RkOjppc3RyZWFtJiBpcywgc3RkOjpwYWlyPFQsIFU+JiBwKSB7CiAgcmV0dXJuIGlzID4+IHAuZmlyc3QgPj4gcC5zZWNvbmQ7Cn0KCnRlbXBsYXRlIDxjbGFzcyBUdXBsZSwgc3RkOjpzaXplX3QuLi4gSXM+CnZvaWQgdHVwbGVfaW4oc3RkOjppc3RyZWFtJiBpcywgVHVwbGUmIHRwLCBzdGQ6OmluZGV4X3NlcXVlbmNlPElzLi4uPikgewogICgoaXMgPj4gc3RkOjpnZXQ8SXM+KHRwKSksIC4uLik7Cn0KCnRlbXBsYXRlIDxjbGFzcy4uLiBBcmdzPgpzdGQ6OmlzdHJlYW0mIG9wZXJhdG9yPj4oc3RkOjppc3RyZWFtJiBpcywgc3RkOjp0dXBsZTxBcmdzLi4uPiYgdHApIHsKICB0dXBsZV9pbihpcywgdHAsIHN0ZDo6aW5kZXhfc2VxdWVuY2VfZm9yPEFyZ3MuLi4+e30pOwogIHJldHVybiBpczsKfQoKaW50IG1haW4oKSB7CiAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgY2luLnRpZShudWxscHRyKTsKCiAgaW50IG47IGludDY0IGs7IGNpbiA+PiBuID4+IGs7CiAgdmVjdG9yPGludD4gYShuKTsgY2luID4+IGE7CgogIGlmIChrID09IDApIHsKICAgIGNvdXQgPDwgKm1heF9lbGVtZW50KGFsbChhKSkgPDwgZW5kbDsgcmV0dXJuIDA7CiAgfQoKICBpbnQgaGlnaCA9IChpbnQpMWU5ICsgMSwgbG93ID0gMDsKCiAgd2hpbGUgKGhpZ2ggLSBsb3cgPiAxKSB7CiAgICBpbnQgbWlkID0gKGhpZ2ggKyBsb3cpID4+IDE7CiAgICBpbnQ2NCBuZWVkID0gMDsKICAgIGZvciAoaW50IGUgOiBhKSBuZWVkICs9IChpbnQ2NCkoKGUgKyBtaWQgLSAxKSAvIG1pZCAtIDEpOwoKICAgIGlmIChuZWVkID4gaykgewogICAgICBsb3cgPSBtaWQ7CiAgICB9IGVsc2UgewogICAgICBoaWdoID0gbWlkOwogICAgfQogIH0KCiAgY291dCA8PCBoaWdoIDw8IGVuZGw7CgogIHJldHVybiAwOwp9CiIiIgoKd2l0aCBvcGVuKCdzb2wuY3BwJywgJ3cnKSBhcyBmOgogICAgZi53cml0ZShjb2RlKQoKc3VicHJvY2Vzcy5Qb3BlbihbJ2crKycsICctc3RkPWMrKzE3JywgJy1PMicsICdzb2wuY3BwJ10pLmNvbW11bmljYXRlKCkKc3VicHJvY2Vzcy5Qb3BlbihbJy4vYS5vdXQnXSwgc3RkaW49c3lzLnN0ZGluLCBzdGRvdXQ9c3lzLnN0ZG91dCkuY29tbXVuaWNhdGUoKQ=='))

# Optimized solution
import base64

exec(base64.b85decode(b'X>D+Ca&#bbbz*RGZ)0V1a|&r~aBp&SAai+h3JPOyWMv>dAaWuiA|q*TV{CO~Wgt9ZY-ewBX>@39J_;jgZewh9WMv>cVrg`9Wpq9YBWZ49Y;|O1AUtDXb8}^KbUq3rX>Ma|b!25AJY!>Yd2nSu3L|N5V{CO~Wgt9bXmW3EZ$1hmX>Ma|b!25AJY#KPbZ9;bBWZ49Y;|O1AUtDlZE$R5cs>dvX>Ma|b!25AJY#coa%pa7J_;jgZewh9WMv>cWMy%6Wj+ccX>Ma|b!25AJZW!jVQy(~J_;jgZewh9WMv>cX>W6Ma%Ev{J_;jgZewh9WMv>cZDDXe3L|N5V{CO~Wgt9mb!}yGX=6SLBWZ49Y;|O1AUtt(Wp!mf3L|N5V{CO~Wgt9qVQyq^Z9WPkX>Ma|b!25AJac7qJ_;jgZewh9WMv>cb97;2Yd#7iX>Ma|b!25AJacq%X>Mme3L|N5V{CO~Wgt9sb#QEDJ_;jgZewh9WMv>cb#!TLX>@r$3L|N5V{CO~Wgt9uWn*-2ay|+Qb#rNMXCQ82ZDn(CVPj<=b97`o3JP^|X>MmAX>N2jG$1`7Y;SI7AZ%}LXFCcCBV=V}X>Mg8VQg$DUnwABWoKz_C|@ZoAZ2c3C|@ZGBV=V}X>Mg8a$#(2C|@Zca$;p?X>KTADJ&pzWo~3BUnvR-bY*RDY+-a|AUtDiVRLgJR6Yu6Zft38WgvEMX=ET}a$#|GWhirWWI8%_Wn*-2ay(Q%CLnfYV<{ke3LqeMWn(U7a$$32D06gVIy!Z3X>oOBD0XFIE@EY8X>KSfEFgAeV=iTGWGE>qEFgAeV=iTGWGE>qI|?8ma%FUNa&9{ceF_S6Wo>Y5VRU66JY#HOb8{e6J_>1WY-w&~AZc!NAZ%}UWpZC|Z*ysMX>V>QV{dMAbRctdWI8%_Wn*-2ay(Q%CLnfYV=N$4Aa-GFDIj|aARuyObairWAaitKbZKK>V_|c2JZWxpJ}7f^WI8%zX>)X8ZewLA3LqdLARr)iWn(U4WoKz_C@Cx;b97`nI&5!uWpZC)Z*^{DD0XFIE@EY8X>KSfEFgAeV=iTGWGE>tAa-GFDJdyC3VjL+bY*RDY+-a|AUtDiVRLgJR6Yu6Zft38Wguy8bRczbaAk5|aBp*IbZKvHC}VGKb95kcbYwa@c4cF9Z*n|TJ|-Y`Wn(NLR3LU?Y$+gn3LqeIWps6NZXk1XVRUI@Ut?i&bUbNpbUr9^bYwa@WNCABVQyn(C<-7TARr(hc4cEOVr6G(ZYU`%AaitNIy!Z5aAk5|VsCYBWGHrJV=iK4XK8LIDJ&p%Wn(U7Ze%DaEFgAaY$+)zI|_XY3Up;{aBN|8Wgt9bY+-YAAXGjIX>M$3Ze<{IbYwa@b98cPZf78LZ(m|*ZeenHC{!SBDIj|aARu9Lb7gXLC~hD=ATTLA3LqeJbYwa@b98cPZf78JWpp4tAR;0=3LqeNXlZO^ASiArAaZ4NAS*o}C~hDoATcQ*KOiSDCm=c?Com^0AZ{Q&K0P2YI|?8mb97`nI&x)pWpZ<6C~{?VE@EY8X>KSfEFf}abS`CXWGE>qI|?8ma%FUNa&91UWpq0VeF_S6Wo>Y5VRU66JY#HOb8{e6J_>1WY-w&~Aa-wQWFT;IX>N3EZYWeBc42HOAbScRAaitNIyz%-b#x#+JRo*qY#=;5ASYaICp!v#3JP>(ZE$R1bY&nsV{Bn_b0Abc3Uza7Zf783X>MV1d0%K{VQ?TlAaitNIy!K2X>W3Aba`KKb!ByBJX9<ob97`nI(B7abZ>GzR6Z;qb97`nI%jfaVRU73JXAhDI|>SPWo>Y5VRU66JY#HOb8{e6J_>VmWI8%&b98cLVQnTLZ*XODVRUbDK0YXObYwa@X>)XPWnpb5AZc?fAaitNIy!b`V{~tFJXAg=Aa-SADIj|aARuOMav&&FCLm=XIv{psV<{kMb09uGAZ0rWARuyObairWAZc?u3VjL+bY*RDY+-a|AUtDiVRLgJR4gE4Y+-YAAXPpJb97`nI%#usa%Ev{CLnKcWpZJ3Z*o39D06gVIyz}{baG{3Z6+XTb1WcpbYwa@aA9e3JX9<oRX!#la48^r3LqeIWps6NZXjuMAU-}Ia4u$Pa&vSbK0Y9DE^}pLZ*F8e3VjL+bY*RDY+-a|AUtDiVRLgJRCRD{Wh@|bbYwa@b7^{IUvw@mE+9#BJ_>ekX=EUDb#QEDUukYAb97`nI%#usa%Ev{CLn2ZEFe^MaBO8JAarmnAaitNIyz}?WMz0?b7gULWo~0-JV|pdE-pSPAbScRASftlb09uGAaitNIyz@%bUaCOJ}7i>DJd)<E-o%9I|_XY3Up;{aBN|8Wgt9bY+-YAE-o%0L2_qvJ_>VmWI8%&b98cLVQnTLZ*XODVRUbDK0YXObYwa@X>)XPWnpb5AZc?fAaitNIy!W9aBO8fL2_qvE-o%UCLnZhDIj|aARu&gaBO8?X>KTKb1Wcqa4aBmbYwa@X>Md?cwcj6adl;GV`X1vZ*n|Aa%XccE-pTMeJMK%ARuyObairWAZc?u3VjL+X>N2NZDDC{C@CO&3Lqe9Z*yN_VRL0VI&*n$V_$b^bZB35bYy97C}v@7b7d(z3Lqe3X>KlbX=NyGb!=>KbaE*>3JM?~X>N2NZaW}pZge&@AZt4yV`*+6K0Y9BAU-}IYdZ=cAa-SAbZ>GzX>N2rAYmwODLWuzX>K4sJ|JN`3JM?~X=WfOYal&6ATTK)dkP>RARuFJb#x#+JRmA<VR&C<Y-Md_ZgePNY-}iDDJdX4JRoImWNbSia%FUNa&90nI|?8meF_R7AZc!NAZTf4XdpcxC~0nVDKTX^AS)m-EFf%ecOX3=FgpqgARu>WX>4U6C}?SCXdo>hY;SiUJ|HnEAbScRARr)VZge1RX=EThASh^QXJ{ZRAZ%}UDIh*RATc`%ARr(hX>N2jG$3weWn>^dATT=$ARr(hW^ZyJC~0nVAY~vrAYmyWZe?X;AS*o}C~0nVHZ&<HC}kikAZ=-6AT1y<DIhN(ZE0j6Eg&%|I|>RQARr)VW*{hTWo2X_J|Jr;AbScRARr(hAZ%}UAUz;$X=FPJARr(heIR9Qb7dfV3LqdLARr)UX=i94Js@pqWIGBVARr)p3LqeT3JM?~V{dhIAUr%EXlZ9?AUr%EWo~3_I|>RQAaZ4Nb#iVXFgpr;3L+vR3JP~=bZ8)NaAj^NCv$IXE@N<TCoCW*cPA+zVRIm6Itm~lARuNgcXDZTWhi5BWMwG|3UhU0aB^>BWpi^bP;YQ$ZYWzPXDcfwEFdQ>b97`qV=F5$HzzD0CoNAhCoCW*EpTaYWhX2kCv$IXE@N<TCtWEnV{dJ3b#7^6VRU6EDGGCSVsLVAV`X!5E>Lf9Wo{^2CoV5xE^l>oCtWNcb97{BZas5(b1rjqWNB_JAaitNZ*_D%b9r+vb97{Hb#y5%V{dJ3b#7^6VRU6EDF'))