이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNKNMMMKodKWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWKx0WMMMMMMMMMMMMMMMMMMMMMMMMMNl';loo,..,cdOXWWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWX0d' ,0MMMMMMMMMMMMMMMMMMMMMMMMMWo.,;,,'';c:;;:lllldOXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWKkl:,',;..;ccccloxOXWMMMMMMMNkdkO0KKKk'.';;,...,,;::cc:,',cxXMMMMMMMMWXkood0WMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWOl,,;:::,'...',,,,,,,;:ok0KKXWXl..','',,...',,,,;,,,,,'',:c:,.'dXMMMMMNx'.','.cKMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWNKKNWMMMMMMMMMMMNd,,col;,,;:cllccclloool:,''..;0MNkc;;:cllllooooooolcc::;,...'::'.;ONMMM0,.cooo'.dWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWOc,,,,cOWMMMMMMMWKl':ool::::,,,;;;;::;,;:lool,.,kNWXOd;...';looooool:,,''''... ,cc,,:lxOk,.',''.'OMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO'.:ll:.'OMMWX0kdl,'colc:;'. ..,;;cloooc,..,'..:0WMNx;'',;;,..',:looollooooolc,. 'lolc:;,'. ...cNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWWMMMMMMk..lool..cdl:;;,,;cloolc:;,'''. .;loc:;;;;;;,,,;:d0NNKkolc:cc;'..'',;;;;;;,'.. .',:lc::clll:,.;oo;'dNMMMMMMMNkclOWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNxcxNMMMMMNd'.''....';cllooolcc:,.....,;;;;:c;'';coooooollc;..:OWMWWNkl;:lllc:;,,,,'. .';::,;clc'..;loooool:,:kXMMMMM0' .'ckXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMKl. .xWMMMMW0; .;:ccloooc;;,.. ... ...... .;cc:;;;:cccc:,. .xWMMMMXd;'',;;::clc'..':ll:;:d0Ol;. ':cccclol:;:okKNMXl':c;:ldk0WMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNx'.',.:XMMWKo'.,lol:;,,;;:;,....,..cOx:...',;;,,,,,,,. 'xXNWWWNKxoOWMMMMMMN0dlc' .;l:';ll:;:oONMO'.:c:. ,lll:,',col:;;:lO0c,lc;;::;:xXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMW0xxxxo, .;,..oxd:. .';;'. .,:clc;. .,;,..lxd:...,;;;;;;;;;,. ,dxxxxxxxxxxxxxxxxxxxxd' .;;;;;'..,lxxxx:..;;;,..lxxxdc. .,;;;,...:;.,;...,,..,dxxxxxxxkXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMX: . . . . .. .......... . .. .. . .. .dWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMX: ................................................................................................................................................... .dWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNOdONMW0, ...''''.............................''.........................................................................''...............''............''.'. :0WMXkokNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMX: ,do' ....'''..........................................................................................................'....''.....'''''...............'. .'lo' :XMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNc ... .. ...........................................................................................'............''.......................''.............''. '' ... cNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO''ll:... ......'.....'''.................................................................................................................................''. ...col''kWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWO,'cooo:. ......'....'''.................''...............................'...'........................................'................................''''. .:oooc''kWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWx..cool;. ...........''.......'''.......................''.............''.....''.......'......................''''....................'...'...............''. ..;looc..dNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO'.cooc...,. ...................''''...........................'''''''''.......'.........'''............''.''''............................'...'''............'. ':...cooc..kMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWX0kxxk0Kc.:oo:..,ll. ...............''........................''........'.''.....'.....'...........''..............'''...............................'''''....'''.....'. ,ol;..:oo:.c0OxddxOXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMXc..,,,,,.'loc..;ool. .........''.......... ................................. .........'....'''................ ................................. .........''.....'''. ,ooo:..col'.',,,,..cXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWKo;;lol:.,oo,.,lol:. ........''''... .::,'.......''...............',;cl' .. ... ......'''.'....'.. ... .:doc;,,',,,;;;'. ..''''''''',;:cl. .. ......'.....''''. .:loo,.,oo,.:ool;:dXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWO,,loc';oc..:o:. ........''..'. .,..:c.:XMWXK00000KXX0o. 'd0KXXXXXKXXNWMNc'xd.'c' ...'...'''''..... ,c''c..OMMMWNNNNNWWWWXl .oKXXNNXXXXXNWWMX:.do.'c,...'.......''. .:oc..co,'col',OWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWo.:l;.'l:..:, .........'.... .:.;KO.:XMMMMMMMMMMMMMNc.dWMMMMMMMMMMMMMX:'0X:'l, ......'...''.......:;.dX:.OMMMMMMMMMMMMMMO.,0MMMMMMMMMMMMMMX;,KX:.c:............'. .. ':..:c..;l;.oWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO''lc. .. .;. ..'........... ':.:XO':XMMMMMMMMMMMMMNl.xMMMMMMMMMMMMMMX;'0Nc'l, ......'....'..... .c;'kX:.OMMMMMMMMMMMMMM0',KMMMMMMMMMMMMMMX;,0Nl.c:............'. ,c. .. .ll.,0MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWk;,:' .,. .;c. ...............:c.:Xk.:XMMMMMMMMMMMMMWl.xMMMMMMMMMMMMMMX:,0Nc.c:..........'........;l;'kX:.OMMMMMMMMMMMMMM0',KMMMMMMMMMMMMMMX:'0Wl.cl;.......'..''. 'c;. .';. ':,:OWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMWWWMMMMMMMXkc..:ol:. .. ........ .:lllooc.:Xk.cNWWWWWWWWWWWWWWo'kMMMMMMWWMMMMMMN:,0Nc.colccc, ..''. .;cllooo,'kN:.OMMMMMWNKKKKNWMO.;XNXWMMMMMMMMWXXX:'OWl.coolllc' ..''.'. ... .:loc..lONMMMMMMWNNWMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMNOl:::cdKWMMMMWx,:ooc'..''.. ........ .',,,;c:.:Xk.cNKo:;;;:llc;,oXo,OMMMMMXolKMMMMMNc,0Nc.cl,...............'',:l,'kNc'OMMNOl;,cool;;xx.;0l':llccclll:.:0c,0Wl.cl:''''.....'... .'','..coo:,xWMMMMXxc;,,;ckNMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMXl.';::;.'xWMMWk;:oo:..';,,,. ............. ':.:Xk.cNWK; ;OK0d.;Ko,OMMMMWd. cNMMMMNc,0Nl.c:. ......''''...... .c,'kN:'0WO;. ,kNMMWO;;o.;d,,dk; ;kk:.:Kc,KWl.cc. ............ .;,;;,..:ooc;xNMWO' .;::,. cXMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMx.'loool' .oXXo;:oo:,oO0Oko:. .............. .;.:Xk.lNMNc lWMMW00No,OMMMM0' .kMMMMNc,0Nc.c;........'..'........:,'kX:,0x. ,0MMMMMMXKx.:kxXMWl cNMXxOXc,KNl.c:.......'...... .cdO0K0d;:ooc;oK0; 'cooo; .xMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMWKold0k..cooo,..'.','col;;kWMWWWMX; .............. ':.cNk.lWMNc cNWKoxWWl,0MMMNd,. :XMMMX:,0Nc.c;............'.......c,'kX:,d, .dWMMMMMMMMk.:NMMMWl cNMMMMN:;KNc.c:.....'''...... .oWWNNWMWO:;loc,'..,..,ool' 'kOocl0MMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMWx....:c,'','..,l:',lol,;ON0o:::cl' ..''.....'.'.. ':.cNk'lWMNc .ll'.lWNc'0MMMOlkl .xWMMX;'0Nc.c; .....'....'........:,'kX:,l. .kMMMMMMMMMk.:NMMMWl cNMMMMX;;KNc.c:.............. :o:,,;lOXk;,lol;,:c. .''..;c;....xWMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMNd';:,,oOxddkl.'loool;.,l;..;::,. ...'.....'.... ':.cNO'cNMNl :0Kd'lWNc'OMMXlcKx. ,KMMX;'0Nc.c, .....'....'...'....:;'kX:'l. .kMMMMMMMMMx.:NMMMWl cNMMMMX;;KX:.c:............'. .,::;..;c;.;loool'.cddxkOo',c;'dWMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMK,.co:,xWMMMK;.coool:;:,..:oooo; .....'........ ':.cNO'cNMNl lNMWKKWN:'OMWk,:dl' oWMX;'0N:.c, .......''''..''....:;'kX:'d, .dWMMMMMMMWx.:NMMMWl cNMMMMX;;KX:.c:......'''...'. ;oooo;..,;:cloooc.;KMMMWd,coc.,KMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMX;.coo;:0MMMX;.loooc,'''...:cc;. .............. ':.:Nk.:XMNl lWMMMMMX:'OMKcoNWWK; '0MX;'0N:.c, ............'''....:,'kX;.kk. ,0MMMMMM0oc.:XMMMWl cNMMMMX;;KX:.c;........''..'. .;::;..coc;,:oool.;KMMM0::ooc.;XMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMM0,,oooc'dWMWx';ool,.,cool,..;;:c' .............. ':.:Xk.;XW0; ;KWMMMMX;.ONo'dWMMWd. cXX;'0X:.c, ...........'''.....:,'kX;.kWO:. 'xXWWNk,':.;XMMMX: ;KMMMMX;;KNc.c; ...........'. :l;,,..lXWWKo,,coo;'xWMWd'cooo,,0MMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMX:'cooo;.'dKx,,lo:..:ol:'..;0NNWX: .............. ':.:Xk.;XKd:::::o0WMMMX;.dx,.:kNMXl'..'oO;,0X:'c, .......'...........c,'kX;.kMMWOo;;cool:ckd.;KMMXx;,,,;dXMMMK,;KNc.c;........''..'. .dWWNN0;.'cxKW0:.:ol,'d0o..,looc':KMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMWNo.'ool,......;lo;.'c:,.',,.dWMMMN: ....''....... ,:.:Xx.;XMWWWMMWWMMMMMX;.xNXXXNWMWXXXXXXK:,0X:.l:. .......'.........,l,.kX;.kMMMMMWNXXXNWMMx.;KMMMWNWWWWWWMMMK,;KN:.cc..........'.'. .dMMMMWd.,;',ck0l.,ll;...''.,loo'.lXNWMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMKc'. ,ol,.:oo:..cc' .''.,cclc'oWMMMNc ..'..... .',,;:l:.cNk.;XMMMMMMMMMMMMMX:.xMMMMMMMMMMMMMMN:,KX:.col:::;. ...... .;;:clo,'kK;.OMMMMMMMMMMMMMWd.:XMMMMMMMMMMMMMM0,;KX:.colc:::'......'. .xMMMMWo'clcc;':l. .:c..coo:.,lo' ..:KMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMX;.. .''.;oooo;...'. .,ll;,cl'cNMMMWl ...''.. .,::ccoc.cNk.;XMMMMMMMMMMMMMX:.xMMMMMMMMMMMMMMX:,0X:.cl;,,,'. ...... .;;;:lo,.kK;'OMMMMMMMMMMMMMWd.lNMMMMMMMMMMMMMM0';KNc.ll:,,,,. ....... .kMMMMNc'lc,,cl;...'...;oooo:..'....:XMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMWo.::' .coooc'.'cl,.co:.'col':XMMWWd. ..''........ .;c.cNk..lkOOOOOO000KKXXc.xXK0000O00000Oxc..l0:.c, .........'........c,.xO' ;odxkkxxxxxxxkOc.lK0kkkkkOOOOOOkxc..dK:'l:. ........... 'OWWWMX:'loc'.:oc.,lc,..coooc. .'c:.lWMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMWo.;ol:. .co:..:ooo,.:,..cooc.,doc:dd. ...''''...... 'c',occol::;;;;;;:::::,. .':c:;;;:::cccloxxc,..c' .....''............;;.';:dxdlllcccccccc:' .';::cc:::c:ccclodo:,.'l, ............. ,Oo;:lo'.cooc..,;.,ooo:..:o:. .:oo;.oWMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMWd.:oool,..'..coooo;. .cooc. .';'.cx' ..'.'''....'. 'c, 'oxkxxxxdddddddxo. .oOkxxxxxxxxxxxxxl. ,c' .......''..'''.....;c. .:oooollllllllodd:....:ddddddddddddddddc. ,l' .......'''... :Kc.,;,. .:loc. .;ooooc'....;loooc'dWMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMWo,looooo;. .coooool' ,c;'.';cl:.;0X; ............. .:c;,'',,,,,,,,,,,,,'. .::'..',,,,,,',,,,,'',;c:. .................. 'cc:;;;;,,,;;,,,,,,'. 'll,. .,,,,''''''''',,,;c:. ............ oWK:.;ol:,..,c, ,loooooc. .;oooool,oWMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMXc;ooollol..:oooooool, ...;cooo:..oOk, ............. ......'.'''''''''''. 'lo:. ................... ............''..... ................... .:c;. .................... ..'.''....... .ckko..;oool;'. ,ooooooooc..clclooo;cXMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMXc;oool,;;.,ooolclooc'.':loooo:..';;,. ......'''..'....................... .... ..........................'....................................................................''...... .,;;'..:oolooc'..cool:looo;.;;,looo;cXMMMMMMMMMMMMMMMM
MMMMMMMMMMMWNKOkx:,lool'...cool;:ol;.'coolccol'.;oool' .......'...''''......'''.....''''.........''''................'...''..........''''....'......'''..'..........'.''..............''''''....'...... .,looo:.'locclooc,.,lo:;looc...'lool,;dxkOXWMMMMMMMMMMM
MMMMMMMMMWO:,'.....cooo;. 'loo:':c'.:ool:,coo:.,ooo:;c, .........'...''''.....''.........''..'....''''.........................'''...........'........''..'''....''..''.....'.''.......''''......''..'. .lo;:loo,.:ooc,;loo:''c:':ool' .;oooc......';kWMMMMMMMMM
MMMMMMMMMNo..:lll:',lool,.,ool'.;''cooc''cool''lol,,xNk. ..............'..........................''''.........................'''...................'''..................................'............ ;KWk,'col''looc'':ool,';.'loo,.,lool,'clll:..dNMMMMMMMMM
MMMMMMMMMMW0o,,loo:.,loo:.;oo:...'lol;..cooo;.;l:.'kWMX: ..'......................................''.......'''...................................................................................'.... .dWMWk'.;l:.,oooc..,lol,...:oo,.:ool''cooc,;dKWMMMMMMMMMM
MMMMMMMMMMMMW0:'coo:.'co:.,ol' .:oc. .cooo;.';'.:0WMMWx. .....................................................................................................'...................................... ,0MMMW0c..;'.;looc. .:o:. 'lo,.:oc'.:ooc'cKWMMMMMMMMMMMM
MMMMMMMMMMMMMMK:.coo:..;:.'lc. .:;. .:ool, .':kNMMMMMX; ..............................................'...........'''''............................................................................ .oWMMMMMWOc'. 'coo:. .,:. .cl'.:,..coo:.:XMMMMMMMMMMMMMM
MMMMMMMMMMMMMMM0;.:ooc'....c; .. . ;ol;. .'cONMMMMMMMWx. ...............................'.....''.......'..............'..'..................'''......'...'......................................'.. ,KMMMMMMMMNkc'. .,cl; . .. ;c. ..,loo:.:KMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMKc',loo:' .. .. .,'. .',,ckNMMMMMMNc ...'...........................'............ ............................................ .........''................................... .dWMMMMMW0l,''.. ..'. .' .. 'cooc,'lXMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMNOc,;:ll' .;;... .''. .;lllc'.oNMMMMMMO' ............................'.'......... .:c;'.......'''''''.........',,''.........',:ll. ......................................'.. :XMMMMMWk' 'cll:' .','....;:. 'll:;;lOWMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMWKkdoo' ..,llc' ;oc;..;oooooc.,0MMMMMMWo. ...........................'''.... .;:..,.,KMWXK000KKKXXNNNNXK0o. :kOKXNNXXKKKK00KKKXNWMK,.o:.'l;..................................... 'OMMMMMMNl .cooooc. .;co; 'cll,'. 'oddOXWMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMWWMMMMMNl .loool. .';c,..coool,.cNMMMMMMMX: .........'''..................''.. .c,'kO''OMMMMMMMMMMMMMMMMMMMX:.dWWMMMMMMMMMMMMMMMMMMM0',KK,.c:........'''''............''......... .dWMMMMMMWx. ,cool, ;l:,. .loool. oWMMMMWWWWMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMW0oc::lxKWMWx..:ooo:..:l:,.''''''',dXMMMMMMMMMO' ..........'...................... 'c.,0O..OMMMMMMMMMMMMMMMMMMMNc.xMMMMMMMMMMMMMMMMMMMMMO.;KX;.cc.........''..............''..'...... cXMMMMMMMMWk:...''',''':l:..:ooo:..xMMXkl:;;:lONMMMMMMMMMMMMM
MMMMMMMMMMMMXl.';::,.'dKNO' ,oooc;c:''ckXNKOkk0NWMMMMMMMMMMWx. ......''........''...............;c.,KO'.OMMMMMMMMMMMMMMMMMMMWl'kMMMMMMMMMMMMMMMMMMMMMO.,KN:.cl;........'......................'.. ,0MMMMMMMMMMMWKOkO0XWXOl'.:c:cooo, 'OXx,..;:;'..cXMMMMMMMMMMMM
MMMMMMMMMMMWx.'looooc..';;. 'loooo;.;0WMMMMMMMMMMMMMMMMMMMMMNo. ..''......'...'......... .';:::col.,K0''0MMMMMMMMMWMMMMMMMMMWl,OMMMMMMMMMMMMMMMMMMMMM0',0Nc.coollcc' ...'''.''...........'...... .kWMMMMMMMMMMMMMMMMMMMMMWK:.;ooool' .;,. .coooo; .dWMMMMMMMMMMM
MMMMMMMMMMMWx.'looooc..,:;'.'loooc.'0MWK0XWMMMMMMN0OXMMMMMMMMXc .'''.....'............. .;;;;cll.,K0',KMMMWXkoooolloONMMMMWl,0MMMMMMMWKxddoloOWMMMMK,'0Nc.:o:,''.. ..''''.............'''.... .xWMMMMMMMWKkONMMMMMMWXO0NM0,.coool'.,:;. .:oool, .xWMMMMMMMMMMM
MMMMMMMMMMMMNd'.,;;'.,;,',cccoooo:.:XMK;.,oXMMMWk;..oWMMMMMMMMK: ..'.....''....'''............ .;c.,K0',KMMKo'.:kKX0l..'dXMMWl,0MMMMMMNo.'d00o.'0MMMMK,'0Nl.:c. .....................''..''... .dNMMMMMMMMWo..,xNMMMKl,.;KMX:.:ooooll:,','..',,..'xNMMMMMMMMMMMM
MMMMMMMMMMMMMWKxollokXWXk:.,cooooc.'xXK:,;.,OWXl.',,xWMMMMMMMMMK; ..''...''.....''......''..... 'c',K0',KWO, cXMMMMWk. :KMNc,0MMMMMWd. ;XMMWxc0MMMMX;,KNl.::....'...'''.................... .oNMMMMMMMMMMx,;'.lXWk'.:,:KXd..cooooc'.cONNOdlcldkXMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMWWWMMNk'.coooc. l0c:o:..l:':ol;dWMMMMMMMMMM0; ......''............''....'. 'c',K0''0K, .OMMMMMMWo :XN:'0MMMMMNc ,d0NWNWMMMMX;,KWl.::...'.....''......''..'....''.. .lNMMMMMMMMMMWd;loc';c..co:cOl .cooo:.,OWMWNNNWMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMKc,:lokKk'.col,.'.cd:coo;. 'cool,;KMMNOdkNMMMM0; .................''...'..'. 'c',K0''0x. ,KMMMMMMMk. .kN:'0MMMMMWk. .'oKWMMMMX;;KNl.::...'............'''.''....... .lNMMMMNxokXWM0;,lool' .;ooc;o:.'.'loc.'k0xoc;':KMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMK;.,:;,;;. ,l,.,o;..,ooo:..coooo;.,odc;.,0MMMMMK; ...'.....'......'''.....'. 'c',K0''Od ,KMMMMMMMO. .xX:'0MMMMMMW0l' .dNMMMX:;XNc.::...''''....'.........''..... .oNMMMMM0,.::ol'.:ooool..:ooo,..;o;.,l, .;,,:c,.;KMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMWXKWMWO,'lool:'..'..loc..:ool'.:ol:col' .;lo,'kMMMMMMK: ....'..............''... 'c',K0''0k. .OMMMMMMMO. '0X;'OMMMMMMMMWXOl' .OMMMX;;XNc.::...'''.....'''.......'.''.. .dNMMMMMMk',ol;. 'loc:lo:.'loo:..col.....,coooc.,0MMN0KWMMMMMMMMMMMMMM
MMMMMMMMMMMMMM0;.:kXWO;,loooo:. .;ooo;.;ooc.'lo:,co:..cooo;'xMMMMMMMXl. ......'...........'''.. 'l',K0''0Nl lNMMMMMWd. .dWX;.OMMMMMNk0MMMMXl. .OMMMX;;XNc.c:...'......'''..........'.. .xWMMMMMMMx.;oooc'.;oc';ol'.:oo;.;ooo;. 'cooool,;0WKx;.;0MMMMMMMMMMMMMM
MMMMMMMMMMMMMMO;,,',cl,.:oooll:..coool,.,l;.;ol'.c;.'ll:;l;'xMMMMMMMMNo. .....''''........'''.. 'c',K0''0MXo. .oNMMMWk. .xNMX;.OMMMMMK;:KMMMMk. lXMMMK,;KNc.c;...'.......'......''..... 'kWMMMMMMMMx';l;;ll'.,c.'lo;.;l,.,loooc..:llooo;.,c:,';,;OMMMMMMMMMMMMMM
MMMMMMMMMMMMMMKc;olc;,,.'looc;. 'lol,;l;....:o:..'..ll,.:o:'xMMMMMMMMMWx. ...''''.....''....... 'c.,00''0MMW0l'.:oxdc,,oKWMMX;.kMMMMMNl.;dkko;;dNMMMMK,,KNc.c:...'...''......''''''.. ;0WMMMMMMMMMx':oc.'ll'....:o:....;l;,lol' .,cool'.,;:coo;cXMMMMMMMMMMMMMM
MMMMMMMMMMMMMMWx;cooooo;.:oooc. 'oo:.'lo:. .:o; .cl,.;oo:'xMMMMMMMMMMW0; ...'......''........ 'c.,00''0MMMMMN0kkkkOKNMMMMMX;.xMMMMMMWKkxdxx0NMMMMMMK,,KNc.cc. .............''''.. .lXMMMMMMMMMMMx':oo;.'lc. ;o:..'col'.:ol' .cooo:.;oooooc;xWMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMNo,cooll;.,oooo;.'lo:..cool:..,' ;o; .:oo:'xMMMMMMMMMMMMXc. ......'''... .....,cc.,00''0MMMMMMMMMMMMMMMMMMMN:.xWMMMMMMMMMMMMMMMMMMMMK,,KN:.:oc;,,'. ............. .xNMMMMMMMMMMMMx':ooc. ;o;. .,.'coooc..:ol'.:oooo,.;clooc,oNMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMXc'col,. .coooc..coc. 'loool' 'lc. .coo:'kMMMMMN0doodONNx. .....''... 'clllool.,00''0MMMMMMMMMMMMMMMMMMMN:.dWMMMMMMMMMMMMMMMMMMMMK,,KX:.:oolccc;. .....''.... ;0WKkoookKWMMMMMk':ooc. .cl' ,loool' .coc..coooc. .,lo:'lXMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMXc.;ll' ,oooo,.;ol' 'loool' .:o,. .coo;,kMMMW0:.',,'.;OW0:. ..''.'.........':l',0O..ck0KXXXXXXXNNNNXXXNNK;.xWWNXXXXXXXXXXXXXXXK0x:..kX:.co;..........''..... .oXXo'.,,,.'oXMMMMk';ooc. .,l:. 'loooc' 'lo;.,oooo, ,ll,.cXMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMWO;..;:'..,looc.'lo; .:oooc. .ll'''.,;,..cOXWK;.:oooo:.,KMNd. ....'......... 'c''lccdoc::c::::::cccc:::c:' ,cc:::::::::::::::::::ldl:c'.cc. ....'...'''... ,kWWd.'loool'.dWMN0l..,;;',''ll. .cooo:. ;oc.'lolc, .':;. ;ONMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMNk;'..',,,'..''''..,ll..,..:ooo' 'll;'.';clooc;;xk..:ooooc.,0MMW0:. ..'.''''.''. .c, ,dxxkkxxxxxxxxxxxxxxxxc. . .cdxxxxxxxxxxxxxxxkkkOk: .l:...'..'''..''.. .lXMMWd.,loool,.lKd;;clol:,.',:ol' 'ooo:..,..ll'..''''.',,;,''..,xNMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMNd;'.':loooollc;,....;,.;c..coo:':l;.'o0KkxKWMK;.....',,'.;kWMMMMNd. ...''''.''. .cc'....'',,,,,,,,,,,,,,,'. .:l;....''',,,,,,,''''''',,,,,;co; ...'''''.... .;OWMMMMXo'.,,,.. ''.oXWNOxOKOl'.;l:,:ooc..c;.,,...',:cloooool;'',:xNMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMWN0dc;;looooolool:'....::.;oooc,.,oKWXc.cKWMNc .,..cloOXMMMMMMMWKc. .....''... ';;;;;;;,,,,,;;;,,,,,,''.. .co:'. .,,,,,,,,,,,,,,,,,,,,,,,,'. ..''.''.... .dXMMMMMMMWKxlc..,' 'kWMWO,.oWWKo,.;looo,.:;....,:lolllooooc;;lkKNMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMWKo;;looc;',:lol:'..;;;lc,.,dXMMMNl.,kKKd. ...:XMMMMMMMMMMMMMWk;. ...'''..... . ............. ... .............................''..... .cKWMMMMMMMMMMMMX;.,.....cOX0:,kWMMMXd,.,cl;:;..':lol:'';cooc;:dXWMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMWKc':ool:'..;looc;cl:'.;xXMMMMMMNkc;:::clllc;;:cxKWMMMMMMMMMMMNd' .................................'.............................'.'''.....'... .;OWMMMMMMMMMMWXko:''::ccc:;;coxXMMMMMMMXx;.,clc:cooc,..'cooo;'lXMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMNo';ooooc'..;looc'.:kNMMMMMMMMMMWNNNNXkolcc:cc:;:xNMMMMMMMMN000o. .....'......''.....''...............''.....................'..''......... .,dOOXMMMMMMMMW0l;;clloodxOXWWNNWMMMMMMMMMMMNx;.,cool;..,coooo;'oNMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMNo,,coool:''::'.:ONMMMMMMMMMMMMMMMXo,;oxkxo:;:ol,;OWMMMMMWd..;xOl. ...........''....''................................''.....'.''.'...... 'dxc. :XMMMMMMNd,;ol:;clolc:;ckNMMMMMMMMMMMMMMMNk:.'cc''cooooc,,dNMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMW0l,,:lool;.'cOWMMMMMMMMMMMMMMMNx,,xNMMMWXk:.'O0;,OMMMMMX:.'..:OOc. ...'.'....''...........................................''''....... 'dOo..'.'OMMMMMMk.cO:.;xXWMMMW0l':0WMMMMMMMMMMMMMMMNO:.':looc;,;oKWMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMWKd:'''.'l0WMMMMMMMMMMMMMMMW0:'oXMMMNOc;:cokNWo.lXNWMMK;.:l,.'xX0c. ....................................................''''...... 'oK0;.'cc..kMMWXXNk.:0klc:;:dKWMMW0:'oXMMMMMMMMMMMMMMMMWOc..'',:xXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNd..lKWMMMMMMMMMMMMMMMMXo':0WMMWO:,lOXOocc:,cxc':o00; ,ooc..lko;'. .........'......................................''''..... .';dd'.;lo:..k0d:';0Nk:;:cd0Kx:,lKWMMNx,;kWMMMMMMMMMMMMMMMMWO:.;0WMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMX:'kWMMMMMMMMMMMMMMMMNx;,xNMMWKl'c0WWk';xOOKWNc.;;,;..:olll,. .,ol. ......'''...................................''....... .,o:.. ..clclc..',;:':KMMNK0d';KMNk;,oXMMWKc'lKMMMMMMMMMMMMMMMMMXc.xWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM0,;XMMMMMMMMMMMMMMMW0:'lKMMMXd,;kNMMWk',odddxk;.:ol;.'lo;'ll,.'l:c0Ko'. ....'.'.................................''.''... .;kKx:c:..co;'co;.'loc.,OXOkxxo',0MMMNx;,dXMMNk;,xNMMMMMMMMMMMMMMMMx.lNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMX;,0MMMMMMMMMMMMMMXo':OWMMNk;,dXMMMMMWKxooolc:. 'cl,.,ooc',l;'coolcdKXx;. ............................................ .cOXklcloo,'l:';oo:..lo:. ,::clllxKWMMMMMXd,;kNMMXl'c0WMMMMMMMMMMMMMNl.xWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWx':XMMMMMMMMMMMNk, ,OWMW0:'lKWMMMMMMMMMMMMMMW0d:'. ,ooo;.'''coc;::;oKNOc. .....................'........'........ .,oKNkc;:::lo;.,.'loo:. ',.'ckXWMMMMMMMMMMMMMWKl'c0WWO; .dXMMMMMMMMMMMXl'lNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWk,;xNMMMMMMMW0c'co:,oOl':0WMMMMMMMMMMMMMMMMMMMWKd:..,:lc. .:ol'.;c,,oKWKd,. ...''..'..................''...... .:kXNOc,::'.:ol'. ,ool, 'ckXWMMMMMMMMMMMMMMMMMMWO:,c:,:ol,:OWMMMMMMMNx;,xNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWKo;;ok0KXKOl':OWMNl..;kNMMMMMMMMMMMMMMMMMMMMMMMMWKxc,'...'.,oo:. 'cc,;dXWNk:. ........................'.... .'cONW0l,;l:. .loc.''.,,'';lkXWMMMMMMMMMMMMMMMMMMMMMMMNx,.:XMW0c':x0XXKOo;,oKWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWXkl,.... .,cONk;'dXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMN0d:,. .;l:. 'lo:',do:;,;,. ....................... .;;;;:ol',lo:. 'll'....,cd0NMMMMMWNKOKWMMMMMMMMMMMMMMMMMMXo,:OXk;. .....;xXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNk:...'',,';ld:'lKWMMMMMMMMMMMMMMMMMMMMWNKOOOOKXWMMMMWXOdc;'. .,oo:. .;c,'oOo,. ..........''...... .:xOl.;c,. .lol'.. .''.,cx0NMMMMMMMW0xkxlckNMMMMMMMMMMMMMMMMMMW0c'cdl,',,'....:kWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO' .,:lol:ckO;'kWMMMMMMMMMMMMMMMMMMMMXkc,;ldkOOOkkKWMMMMMMNKko:,..',,. ,loc..kWNOl,. ............ .;dKWWx..lol' .:;...',cokKWMMMMMMMMMMWxcOWMMXKWMMMMMMMMMMMMMMMMMMMMNd'c0x:clll:'. '0MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNOdlc;'.':xNd.oWMMMMMMMMMMMMMMMMMMMWk,.'dXWMMMMMNk:lXWNWMMMMMMWNKOdl:,..'''. ;OKXNXkl,. ..... .;d0NNNXO; .,,'..';coxOXNMMMMMMMWWMMMMMMNc'xNMMMMMMMMMMMMMMMMMMMMMMMMMMNl.xXd;'.,;cod0WMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNKx;.:0o.dWMMMMMMMMMMMMMMMMMMWd. cXMMMMMMMMMNl:KWOccx0XWMMMMMMMWNX0kxol::::::ccc;. .,:cccc:::;:cldxOKNWMMMMMMMMWX0xdONMMMMMMWO,.,:loodk0NMMMMMMMMMMMMMMMMMMMx.ok,.:xKWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWK0Nk':XMMMMMMMMMMMMMMMMMMO' :XMMMMMMMMMMNOKMMO..cxxddxKWMMMMMMMMMMMMWWNXK00OkkkkxxxxxkkkOO0KXXNWWMMMMMMMMMMWX0XWN0d'.lNMMMMMMMMMXklc;,'...,oXMMMMMMMMMMMMMMMMNc.xX0KWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWx';kNMMMMMMMMMMMMMMMMk..kMMMMMMMMMMMMMMMK;.dWMWNx;dWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWX0OxkOOkdo0WMWx.,0MMMMMMMMMMMMMWWNX0d,.cXMMMMMMMMMMMMMW0c'oNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMW0l;;lx0XWMMMMMMMMMMMK,.kMMMMMMMMMMMMMMX:.lNMMMMNKXMMMMMMMMMW0dodkO000KNWMMMMMWNNNXXNMMMMMNkookNXkl..xNWMMXXWMMNo.:XMMMMMMMMMMMMMMMMMM0,;KMMMMMMMWNXK0xc,:OWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWXkoc:::ld0NMMMMMMMWO,:KMMMMMMMMMMMMXc.'oOKK0NMMMMMMMMMMMMMWo.'k000kdccxXMMWWKo,,dXMMMMMNO,'OMMMX:.dWMMMMMMMMMX:.lNMMMMMMMMNN0x0NWWKxlOWMMMMNOoc::c:cd0WMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWNXOdc;:o0WMMMMMMKddk0XNNKk0WMMNl.;O0kd;cXMMMMMMMMMMMMMWl.oWMMMMWKl.,OWMMMO..OMMMMMMMMx;kMMMMk.,KMWKdOWMMMM0,.dWMMMMMMWkd0d:cdxkONMMMW0o:;ckKXNWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWXkc,:xXWMMMMMNKOkdlcoKWMNo.'0MMMW0KMMMMMMMMMMMMMMK;.kMMMMMMMNo..OMMMK,.OMMMMMMMMK:oWMMMX:.:kOxloXMMMMWk..kMMMMMWO;,0WXKXWMMMN0o:;cxXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMW0o:;cxKWMMMMMMWNNWN0kc..xWMMMMMMMMMMMMMMMMMMMMk.,KMMMMMMMMK, cNMMK,.kMMMMMMMMWocXMMMMk..OWMWNNMMMMMNo.,kX0kxxddONMMMMMNOo:;cxKWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMN0d:;:oOXWMMMMMMWKOd::dXMMMMMMMMMMMMMMMMMMMNl.lNMMMMMMMMX; cNMMX;.xMMMMMMMMMkcOMMMMX:.oWMMMMMNO0WNd..:dkOKNMMMMMWKxc;;lkXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWXkl:;cdOXWMMMMMMMNKXWMMMMMMMMMMMMMMMMMMK,.xMMMMMMMMMO..xWMMX: oWMMMMMMMMk:kMMMMMx.'0MMWX0o,dNKkkKNMMMMMMWXkl:;:dONMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMN0xl::cokKWMMMMMMMMMMMMMMMMMMMMMMMMWx.'0MMMMMMMW0;.oNMMMWo.,0WMMMMMMNolXMMMMWx. ;xkkxxkONMMMMMMMMNKkl:;:okXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNKkl:::ldOKNMMMMMMMMMMMMMMMMMN0d;..l0XNNNKko:cOWMMMMMXl.'oOKXK0kodKMMMMN0xdk0XNWMMMMMMMMWXOdc:;:okKWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWXOxl:::cox0XWMMMMMMMMMMMWXK0OkxxkkkkxxkKWMMMMMMMMW0dccloodxKWMMMMMMMMMMMMMMMMWNKkdc:::ldOXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWX0xoc:::cldk0XNWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWWMMMMMMMMMMMMMMWNX0xol:::cldOXWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWX0kdlc:::ccldxk0KXNWWMMMMMMMMMMMMMMMMMMMMMMMMMMMWWNXK0Oxolcc:::cldOKNWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWXKOxdllcc::::ccllloodddxxxxxxxxxdddoolllcc::::cccodxOKNWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWNXK0OOkxdooolllllllllllllloodxxkO0KXNWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
*/
#include <bits/stdc++.h>
#include "homecoming.h"
typedef long long ll;
using namespace std;
#define MXL 1000000000000000000
#define pb push_back
#define sc second
#define fr first
const int N = 2e6+5;
ll dp[N][2];
ll solve(int n, int k, int a[], int b[])
{
vector<ll> pref;
pref.pb(b[0]);
for(int i = 1; i < n; i++)
{
pref.pb(pref.back()+b[i]);
}
for(int i = 0; i < n; i++)
{
dp[i][0] = -MXL;
dp[i][0] = -MXL;
}
dp[0][1] = a[0]-pref[k-1];
for(int i = 1; i < n; i++)
{
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = max(dp[i-1][1]+a[i]-(i+k-1 < n ? b[i+k-1] : 0), dp[i-1][0]+pref[i-1]-pref[min(i+k-1, n-1)]);
}
ll ans = max(dp[n-1][0], dp[n-1][1]);
for(int i = 0; i < n; i++)
{
dp[i][0] = -MXL;
dp[i][0] = -MXL;
}
dp[0][0] = 0;
for(int i = 1; i < n; i++)
{
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = max(dp[i-1][1]+a[i]-b[(i+k-1)%n], dp[i-1][0]+pref[i-1]-pref[min(i+k-1, n-1)] - (i+k-1 > n ? pref[(i+k-1)%n] : 0));
}
ans = max({ans, dp[n-1][0], dp[n-1][1]});
return ans;
}
//int32_t main(){
// startt
// int t;
// cin >> t;
// while(t--)
// {
// int n, k;
// cin >> n >> k;
// vint a = read(n);
// vint b = read(n);
// cout << solve(n, k, a, b) << endl;
// }
//}
//
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
