#define g/*_._"_`.~__.,~-_~_";;"~~,!?*/getchar ( )//;_-._""~.~-_"_. __~!"`-,_,~.~~-__ _;_~!";-`---_~,--_-^__
/*~~,-_,?*iio&^,_*/ int s/*_?iXC*;_-*/,w,o; z( a/*~_!&Co&+;,_*/ ){"_!,*+*%oo+;,-!`__!~_--?=&%$i*?!-.,,,~,__"
;a++/*`-;hMMW$&!*/< '6'/*,!;OMMHX&;_.*/ &&~z(a)+"^\"cHMM@x*^"?o=g,"__\"+XMM@Xc",a >'#'?".-*fMMMbo?,._!;_.~ \
^-_,,~-_+MMMHf%?,_!,,-,_.~!xMMMMh%*^__,!^--`-~~-!.!!@MMMMXi=,,!~-~_~.,;=HMMMhC=!_!,~^ :-.^fMMMMWx&^_-_--.-^"
-"~`.~^-%WhfC&;_-^!-~~._.`.c@@hOi?,~,,^^,~__! ~-`^,!OW@h$&?,_-^--__~._~?hHh$o=,-!,~---!,_,X@@hX%=^-",s=w=o:a
==' '?",,o&&=!.`_"-"!_._;c++&*=!~~,;&c+_.-_,,`~~!cc++**?,~",s*=o,"_!*%&=**=,~` -^,^"-",=i&oo*+^-` ":',':'.';
}y(a)/*-;b@Hhx*!-_-`!,;bMMh%&^ `-cbHMh%?!_-^?+!oMMHXi+_  ` _.~~-!-cHMHbC*^. `..,^-!!~*fMMW%c;` */ {char *l =
"!-_--.!XMMMMb%?!^!~,^@MMMHOc;_?*hMMMHXc;!""-?%MMMMW$&^_!_`--_~_,;MMMMHO&;,_^!,^~-`~^HMMMMXi=,~,",* m=( char
*)/*~^"^XMHh$o=,-!!_--@HWb$&?,_"c@W@b$c;,_"^. +M@@f%*"-_"_~^.~.,,;HH@bxc;,_!""^!,-.-+MH@hOc=!~~*/ calloc ( (
"_^__!!_^occ=^~ .!~,!_^coc=,.`;=^;coc=!` -_.-~_coo*;_` ~!-~~!!!!,-=oc&=!` .,_,-~-^!-_=ioc+!~  -~!",1 ),w + 2
);do ",.~Ch@bC=_,-~""^?X@@fo;!,^!=xW@fi^__..-_-*WWW$c",m[w-1-("_,^+fWWfi",a---1)%w/*_`^$W@bi=,~*/]="%e+{(Z)"
 "$["/*-oMMMMb%?!!!.-"WMMMHOo?,?cWMMMHXc;!^^,_iMMMMW$&^!_"!~~.,-`;MMMMHXc;!-,,!~--`.;HMMMMXi=,~*/"'>:8./"/*,
~!_ _;.,$MHWX%+!~!"~.,HMHWXo=,~"c@HHWXi?,_^^!~cMHHhxc;-*/"#f"/*.,iHHHWXi;,*/"jl"/*~_oMHH@fi+!~~ */" F}!J]cg"
"mRE"/*_=iic=^~  -;!..+ic+^-~-!?&%%i+^_` .-!___*ic=!~~_^?;"~_.!!"^=io=^-.-!?&"~-_.,"!iCo+"_~-,"=!_*/ "MH" /*
._-__;"!!obWXi?___"__^.~,-..cX@W$o=_   ` */ [ ".~~. _ibHb%+^",(g+g/*~.`~oXWhx*^,,_!^--___``+$@@Oc"_*/+ g)/24
/*,.`-._+MMMMbi?^,*/]^5,",!cMMMMhi+^~.";while ( ".-;bMMMHXi=^-_!-_,,-.~xMMMMh%=^__~`,,-,,_xMMMMWC*",a % w );
for ("`_iMMHbx&^",o=w %4,"^@MMHW$c;__";o;o--)-g,",-oMMMHhC&^-";a && "^!@MMHh$c;"-y(a);"-!=HMMHWXo="- puts /*
^!-~`."-^C%c?!~  ~*/( m ),"ox%o+^~  ";} main /* .!^_&C%c?,~  ~_.~`~_^^^cxCo=^-` `--!.`_-_^cCCo*;-. `_- __-__
} ..!"!.`,,~`   .~_`.^-.^.^,,^_.  `.,*/ ( ) {y (( "_~;!-.`   ,!.-_~-_,!_~_,.  .", z(-o )," _~_,.  .",s) ),-o
,"~~,,`-_!-~_!~^?,,`,^~!__-^!- .--;-!~_,_^?^_,-_,_!__,^-!_-,__^-_,_~~-,~.!^...!~-!__-.`..^~!-!_-!-``,_,!" ;}