// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



/*

i.r7LvLr7iii,.ri:,,.::i::,:,,::::::.       .:::,::::::::i:iiririrrrrr;rr7r7r7rrr7rrrvvYLJYUjLL555u1FPFPFFP0551k5S5UJ1LYYLr.     .   ..    ,ri,,.,.:,:.

i ,:::.... .  .,..   ..,..                  .......,.,.,,::::::i:i:i:::::::i:i:iii:;;7r77Lvv7vYUJuu115Uuu522uUjUuU5FjYJLr;                 :.         

;,rii::,::ii:,ii::i,.,iii::,:. .      .,::;irirrrrr;7r7r7rv777v7v7Lvv77r7r7r7vLvLvLYuuuu1uUUFSX5FFkFPkkP0XXN8NEZ8O8NqPEP0kr         :.    ii:...,.:,: 

i:iiiiii:ii;::::,:rr::::::,:,.       .:i:r7v7v777v77r7777vvLvLvvvL7v7v7777r77LLLYJYJJUU1u2U55S551XkqPNq0XNXGGGOMGOE8ZOGMMBGXi       :.   .rr,,....,,: 

;,iiiiri:,:ii:::,:ii:::,:.  .   ....::::iiii;i777r7r77vvLvLvLvLvLvv7v777vrr7vvLLjjuYJJU215F5S5kXNE8ZOqXk0qN8O8MOOMBBBBMMBM@B@8U:    ,.   .ri:,,...,,: 

r:iriiii:,,ii::i,:::::...      ..::::::::iiiirr7r77LLJLJYJLYLYLjLYvv7v7777r77vvYJUuUu11S5SFPPNPZ0GkqFSPZEOOMGMMMOMOMMOM@MBM@B@B@5r..     ,i:,,...,.,,.

7:rir;ri::::i:::::ii:.       .::iirr7rrr7vvvYvLvLYuJuuuYuJuJjjjYjJuLL7vr77rrv7vLuJuu15k5SSkXqq0NqPL5OZO8OGOEG8MOMMMOMG@BBMMMMMMM@BM2.    :i:....,.,,, 

7ir7;r;rii:ii: .:i:...   ..,,::i:iir7LLJuuuuJuuUu2uUu2juJjjuYjJuLJYYLL77r7rrr7vLLYYuu52F155XkNP00GEP8M8OOM8MMMGMMBOME8GOOOMBMMOMOMMBGv   ri:.....,.:,.

;:7rri;ii:iiri:,:,.   ,,::iirrvvLLJYuuUU2U1u2uUuUUUU1u2u2uuJuYjLLLLLJvL77rrrrrv7LvLJuJUu2U55PSkXEqZEZ0Z888O8M8O8MMBMMMMOM8OMMB@B@B@BBMqi,i;:,.....,.: 

..iriririiii::,:.   .,:i;rr7vLLuu2U115U52122U2u1U2u2u1U111U2U1uuJJLYvYLL77777v7vvLvLvYYuuUU5U15SFkSqkPq0NGOOOMMBZG8OOMMBMBM80MB@B@@@MBBZJ7::,,...,.,, 

. iiri;i;;;ii::..   ,:;r77LvLLujuJuu2U22F11U5252522uuu2JujUu2uUjuJYvLLYLYvv77rvvLvYvLLYLJYujUu1215FSkSNqE0ZZGEOOMMOGMZMMMMMOMOMGBB@B@B@MZji,,...,.,., 

. :ii;iiirii;7:.   .:7vYu2u2jUuUjUU1u521U2u2U121U2jjLYvL7LvLLJJjLLvLvYLLvLvv7vvLvLLYvYJjYujujU2Fu125kqX0q0EGGGN8GMOMMMMMOMBBMMOOGMMB@@B@Bqr:.,.,.,.,, 

. ,:ii;iiirii:    ,:7LU251F15155SFFu2uuu2uujuLJLL7v7v7777777vvLvLvLvYLLvYvv7vvLvLLJYuYjjuuujuY1SS1515FP08EE0G88GGGMOOOMMMMMMBBMOMOMB@BBB@M2:,.,.,.,,: 

. .::iii:ii:.  .,:irvuU1UF1S252122uujuYuLLvL77r7;rir;rrrrrrrr7777LvL7L7v7v777LvvvLLYJUuUujLJjujS1kSkkS5XPGZZZGEGGO8MOMOMOMMMMBMMOO8MM@BBM@OJ:......,, 

, .,::ii:,::, .:irYj11S1FFk5F21uujuJjLL7777rrrririrrrrriri;iri;ir;rrrr7r7rrrv7LvLLLvYLuYJYJJjj2USFkFkPP5SqG08ZGG8EOOMMMOMOBM@B@@BMOEOO@B@BBS7:..,...: 

. .,::ii:::i:,:vYuUS5kFSSk51U1uujuYJLv77rrrr;rrr;rir;ri;i;iiii:iiiiii;irrrr7rv7v7v7v7vvYLYLjYJJ22F1kFXXPPPqEZ80GZMGOOM8BOMMMM@@@M@BBOM8MM@MX7i:,...,. 

, ..::ii;iriii7LJj5SXFkSS5FuUuuJjLLvvr7rr;r;rir;7rr;ri;iiiiii:iiiir;rir;r;7r7r7777v7v7vvLLLJjvLYu2F2kXXXNq0qE8OEOGOOMOMOBMMB@M@MBBBB@OMM@BM17::::..., 

. ..,::ir77LJUYLL1FqkXSk15uuuUjuYLvvr7rrir;r;r;r;riiiiiiii:iiiiiirir;rrrr7rrr7r7777v7v7vvYvLYJvJju2F2kkSXqqE0ZOO88MBGOOMMBO@B@M@M@BM8BMBOM@Erri:,,.,, 

: ,.:,::irvuYr7vjFkXPSkFFu2u2ujvv77r7rrrrrrrririi:iiiii:i:::i:iiiii;r;rrrrrr7r77v7vvL7LvYLL7LJuYJYuu25PkXSE0ZEOMO8BBBGMMMBBM@B@BBM@MMOBMMMB@Pr7:...., 

;:;i:::iirvr:iv25qPNXPFS222UYJLv77r7r7r7rririiiiii:iiiii:::::::iiririr;rr7rrr7777v7LvLvvvLvLvLLuuuJuu1FPPPk0EGG@BMO@BMMBB@BBB@@BB@B@@BMBMMM@Mu7Li:.., 

Lru7:,::iiri7LJuXqEPNPX5FUULLvL7v777rrr;ri;iiiiiiii:i:i:i:::::ii;i;ir;rrrr7r77vr77vvLvv7v7LLLvYLjjuuUU15kXPk0EZEMBMM@B@M@B@BBB@B@B@B@BBMBMBO@5L7r:,.: 

L7u7,.:::i;JJv;JSqN000kS5ULYvL7v77r7rr;ri;iiiiiiiiii:i:::::::i:i:iii;rr7r7r7r7777v7v7v7vvvvLLYLYvJjuU22F1PPqX0NZNOMBO@B@B@B@B@B@B@B@@@B@MBMBMG2vii,,. 

7iLi:,:,:,rYvi75NPEqEPPF2YL7vvL77r7r7rri;iiiiii:iii:i:::::::i:iiiiiirr7rrr7r777777v7v7v7v7vvYYJvJvuj2U5FS1SkPX0PEXZMMO@B@B@B@B@B@B@B@B@BBBBM@Mk7ii:., 

r:ri.,::::ivii75SNqGZEF1jL7vvLvvr7r7rr;ri;iiii:i:i:i:i:i:::::::iiiirirrrr7r7r777r77v7vvv7vvLLYLJYuLUuUu5Fk1F5XXPqEPNN8OMB@@@B@B@B@B@B@B@BBBBB@GJvri,. 

7:7:..,:i7Lr;ir7Xq0GOX5jL777vvv7777r7;r;riiiiii:i:i:i:i:::::::i:ii;ir;rr7r7rrr7r77v777v7vvvvJLJYJuuu2uUuFFF5F5XPPPEXPPZEMM@B@B@B@B@B@B@B@B@MMM@MUvJi. 

Y7Li,,,::rj7;r:i20GOZSJL777v7v7v77r7rririii;iriiii:::i:::::i:iiiiii;;rr7r7rrrrrr777v777vvLvLLYYjYJJuu1212F5F151kPqqE00qEZOOMB@@@@@B@B@B@@@BBMBMM8X2Yi 

2LFi,:ii;ii:::;vX8OGquY77r77v7v77rr;riri;i;i;i;ii:i:i:::i:i:i:i:iiiirrrr7r7r7rrr777777v7vvLLYLYLJYujuu222U55F5kSqXPqEqNPEGOMBB@B@@@B@@@B@B@@@BEFGXJir,

YrYi.::ii:.  .7k0OO8SY77777v7v77r7rrrrrriiiiiiii:i:i:i:::i:iiiiiirir;rr7r7r7rrrrr7r7rv7vvv7vvLLLLJJuuUU2UF255kSPPPkNXqNZEGEOOBB@B@B@B@B@B@B@B@8j18qv. 

:.rr::ii:.    i2OGOE1vv7v7Lvv77rrrrrririiiiiiiiii:i:::i:i:i:i:ii;irirr7r7r7rrrr;7r7r77v7v7LvLvLvYLjYuu1U1112FFXkPkPk0qNNZG8ZOM@B@@@B@B@B@B@B@BEriU05i 

:i50FY7r:,    i0OOONuL777L7vr7rrir;r;;ii:iiiiiiiii:i:::i:i:iiiiriiir;rr7r7rrr7rrr7r777r77vvLvLLLLJLuYUuU25252SkXSPSPNEqEqGGOOMM@B@B@B@B@@@B@@@u.vLL2r 

0kGNGEk1ui    :EMGOkjvv7v7777rriiiriii;ii:iiiiiii:i:::::i:ii;ir;ririrrrrrrrrrrrr7r7r7r77vvvvLvYLYLJYuuU2UU2211S5SSXkNXNNZZ8GMMMB@B@B@@@B@B@B@Bj rj7rr 

qSqE0OEG8F,   r8OMMqLL7v77rrrririiiiiiiiiiii:i:i:i:i::iii;ir;r;rrr;r;r;rr7rrr7rrr7777v7vvv7LvYvLLYLujujU22U2212SFkSkPqPE0ZEOOMOBB@B@B@@@B@@@B@r  iiii,

kuZOMOMZ8ki  .:ZBMMFL7L77r7r7;r;ri;iiiiiiiiiiiiii:i:iiiiri;irrrrrrrir;rr7r7r7rrrrr77v7vvLvLvYLYLJLjjujuu11525255kkPkNXqE0N8888OM@B@B@B@B@B@B@Bv:.:7i;:

GSvi,,:SEq;.  :GMM817v7v77r7rr;r;riririiiii;iiii:iii:iirirrrrrrri;irirrrr7rrrrrrr7777v7LvYLYYJYjJuYuj2u1UF1S1FFXFXkPkNNZNGGOZOOOM@B@B@B@B@B@B@Xv7Y7;:.

@P     Y8S7.  LOMOMUv7v7vr7rr;ririrrrrr;;i;iriiiiii:iirir;r;r;r;ririr;r;rirrrrrrrr7r77vvYLJYjYjYuuuu1U522UFSk555kSqXNN0qGZOZOOMOMB@B@B@B@B@BOOq7rr7;i.

BF,     uEL.  u@OOOS7v777777r7rrrrrrrr;rrriri;iii;iiir;rir;r;r;ririr;ririrrrrrr7r7r77vvYLjYuJuu2UUuUU2u1U12FFS255kFPXEqGZGZ8GOOMMBB@B@@@B@B@8X1uLjjjj7

@7      :X5:  UMBOMF777r7r7r7r7r7r7rrrr;ri;iriri;iririr;r;rrrrrir;rrr;r;rr7rrr777r77LvJYuJujuJUJ2UuuUu1U5U2U5F5U5FkSq0EN8Z8O8GOOBB@B@B@B@B@BM01qBB@qMX

.             vMMMOSr7r7rrr777777777r7rr;ri;rrrrrr;;irrrrrr7r7rrir;rrrr7r7r7r77v7vvLLJJujuJuJuJuu2u1U2U22F11u5kkSPSqqE00N8ZOE8ZMOB@@B@B@@@BBMG7i:i:::.

               7@MBF7rrr77LvLLv777v77r7777v77rrr7rrr7r7r77777r7rrrr;7r777r77vvLvLLjYuu2UF1FFPqNPEEZ0GNEXqNEXNNGGZ8ON0qZ0GEOEGZ8GMO@B@B@B@B@BqLr.      

.               8BMXrrr77Yu1UUJuu22F151S5XFkFF2UYLvv7vr7r7r7r7rrr7r7777v7vvLvLvJYuu51XSkX0ZGGMOMOMM@B@B@B@MBMMMBM@BMEZEZEOZ8E8G88MM@B@B@B@B@5L:       

                qMMF7;r7vJkkNqENEEZ0OG800qEPqXqXk2uYYvv77r7r7r7r7r7r77v7LvLLYLjjUU15kkqkZEGGOOOOMMBB@B@B@B@B@B@B@B@BBZ8GOEGG8EGGOOMB@B@B@@MBv,L       

.        .     .SBMXrrr7vFPEN0X0PEPEEG0XSkFkFF1F21uUJjLL77r7r77777r77v7vvLvLYuJ22F1kSXPN0EqEqEGOZOM@B@B@@@@@B@B@B@B@@O08Z8EGZZ0ZGG8@B@@@B@MOu.i:      

, .             JMBSrir72XEXqkkSkSk1F2515uuJuJuJjYuJuJUYLvv77777v7vvvvLvvvLLjJ22F5k5F1SSXXPkPqGZZE8ZGG88MB@B@B@B@B@@@M8ZGZ8ZEEGN8Z8M@B@B@B@vr:,.      

           ..   :MB0ii7ju51S1UYYLL77777LLJYJLJvLvYLJjuuuLLvL7v7v7vvLvLvvvYLJLu2XkS25UF5SSXSkSPkk5k5S151kS0E8M@B@M@B@B@OOEGEZE0NG0GZMB@B@B@@u,i.,..... 

            .    rOErivLuu5uJLLvvrrrr;r;77vvLLYLLvLYuuUuJvL7vvLvLvLLYYLLYLjY2UFFk5S2S5SFSFXFkFF21u1u2uU2FFqqZ0OMMMBMMB@G8NGEZqEN0qGZBB@@@B@qi,:...,.. 

            ,     :NrirvvJvvr777rrir;r;r;rrv7LLLLYLLLJYuYYvvvLvLLLLLYJLYLuYuu52F5S1F5S5S5XFF1FuUJujuu2uUj11FFPP8GOOMMMMBZG0ZNEq0qEqZ8@B@B@0Y,.,. ...  

            :      27i;;777rrrrir;r;rrrrrr77v7LLjYuLJLLvYLL7vLYLLvJLjLJLJJuu2U555211SFkFk55U1uUjujjJuYuuuu2U5SPk00Z8BBM8OGZ0ENNPqX0NGM@@@Bk:  ... .., 

            ,.     ;riirrrrrir;rir;rrrrrr77vvLLJLujuJuYJLL7LLJLJLJYuJJYJJuu11F5S5S5kFSkXFS15uuuuJuJuJjjuu2UF5SSkXPq0EOOMGZ0ZPNXqkXkqEBB@BMFi  ..  .,, 

            :,      ::iir;rrrir;r;r;rr7777vvLvLYJYujujUuuYYLJYJLjJuuuJujju51FFPSPkPXXSXFX5F2uuUuUuuJuuuu221255XkqXqqZ0EZ800q0XqkPFXSGM@B@O2:  .   ... 

            .i      .iiiiririr;rrrr7r7r7777L7LvYLuJuuUU2uUuuYjJjuuuuuuU52F5kSPPqP0PqXPFk11u1uUuuuuuuu2u2U12F5FFPkXPE00NEN0qqPqXPSF5k0@B@M@L,   ... ...

                     :iiiir;rr7r7rrrr;rr7777LvYYjYUjUu11F21uuuujuuuuuu2U55XXPXqqZEEXPSS11uUuUuujUuU22U1U1251F1k5kkqXqPNq0PqkqXXFS15FO@@MOM7..  ....., 

       .             :iiiiir;rrr7vvLvL7LLujuu2uuJuuujuu1SX11uUJuJuuUjUu21FSqXN0GEZPP15uUu1U1U2uuuUjuu2U5251F1F5SFXkq0EXEq0PqXq5S11uSM@MZ8k:.   ... .,.

    .:;,            .:ii;ir;rr7vYvLvLY1USSqqEENPk11u1uuUS5S15uUjjYuu2u22FSPXE08EZ0X2UU12F5kFFuuJUUS1S5k5SFS1S5F5kkqq0qqPNXPkPkk5Fu2SMMMZq,:,. . ....:.

i.,...               :iiirr77vvvL1Z@B@B@B@B@B@B@BM0k1FU2251F11uuJJLYYuu55XX008ZGNP11UFFPPXXNEBB@B@OZ00P0EGEGNPSPPNq0q0NEXqkPSkFFujjNMMMM: .,.......,::

              ..     .iiii7vuFEM@B@B@B@B@B@B@B@B@B@MN22u22511uuYJLLvLL21XXPP0qZNPFF5XP8ZMB@B@B@B@B@B@B@BMZNkNq0qZqEEGGGPPkXSXFSUuYuG@M@2.   .   ....,,

             .rL.    ,:iiii7vFq@@@B@u0B@B@B@B@B@B@XOBO1u2512juYJLLLLvLJ5SqPqkqPqFS1kqEM@B@B@@@O@@@B@B@@@@@@@@MZ8GMMBOEkkFX5kFS12LLU@M@j             .:

              rr  .ii:iiiiiiiivuPNN5uu@B@B@B@@@B@OEZZkGu22ujuYLvv7v77vJukqqkPkqPX5FFSO@@@B@B@B@B@B@B@B8M@B@B@B@B@B@GP555kFkFk55uJvN@@L              .r

                 :vjvi:iii:i:iirr77L2S5BBBB@B@B@GNEN1vYuuuLLvL77r7rrrvL1SNXkFSSP1FUu8@B@MFB@B@B@B@B@BM20B@B@B@GN5FUUu22F2SSk5F2j7JM@S               ,7

                ruJ7i:iii:i:iiiiiiiiriir;:irLvvr777rrrjujv77vrrrrrr;77JuXSX5F2S2ujUuXMBBEL8B@B@B@B@B@OOG80MqEEFuJLJYUu515FS5S5Uv72@O             ,7vuL

              .:.ir7:::iiiiiiiiiirrrrrrrrrr7rvvJJuUFFFuJ77r7rrrri;ir;7vjUF51uuu2JjYuJ7rrr7;rrrvFFX2Uu1uUu21X5XS5uujuu11FFSFk11J77OB:              .7Uj

             .:    .::iiiii:iiiirr7LJjUUSFkkPk0NZ00SULv77r7rr;;iiiiirrvLuu5uUuuuuJjJUU2uuYL77rrr77v77vLLu2XP0kk11u2u1U52S5F55uYrUO2                  :

            ,i  .:rFJiiiiiiiiiiiirr7vuuSSXkNqNXk1ULv77rrrr;ri;ii:i:iirrLYUU1u2uUuujJJu2kkqN0q0PPkPFkFPkNNZPPSFU12Uu2U2UF1k5122v70Ou                   

           :i. iEM@Oi:iiiiiiiii:iiiir;77vvLvLvL77rr;rrri;iiiiiiii::::i77YjuU12Uu2uuLLLuJUUSXEEOGO8OOOGG0NS5uUjuYjJuu1U12F5k5FuvuMEkuFY;               

          ,ri7JkuZM, ::iiii;iiiiiiiiiiiiiiiri;i;i;i;iiii:iiiiiiiii:::r7vLjj22FUUuuJJvLvLvLLJJujUU1uUuUJjLLvLvYvjYuj22F2F1SFk1u78MES08M7Lv,            

        .   ,.:v8M. Yiiiriiiiiiii:i:iii:iiiiiiiiiiiii:i::iii;iiii:::ii7vJYju22S22uuYLvv7v7v7vvv7vvv777777777LvYYjJ2U5151XFXF5LuMMO@E0PEEX:7.          

   :7r,i:i:::::1@r.M8jiiiriiiii;ii:iii:i:iiiii:i:i:i:i:i:iiii;ii::,:irrvLuuuu225UuJjLv77rrr7r77v7v777777r77vvLLJYuu1U51FFXSS1YS@B@BM0S227,717.        

  i2q:7u7i,.:YB0r.Gv:..irrri;iiiiii:i:i:i:ii::i:i:::::::ii;iriiii:::i;77Ju2U2u521uUJY77rrrrrrr7rrr7r7r77v7vvLLYJuuU2F5SFkSPS5J@B@B@M8EUEqPkP02:       

r:rJ0;:.     iEu r2: .,iir;ri;iiii:i:i:i:i:i:i:i:::::iiii;i;irii::,:irrLL2U11F1515uuLv77r7rr;rirrrrrr7rv7v7LLJYuuuuF5SSkSPXkUP@@B@BMMB2@OMBBuLNu      

PvJvL:..  .:7:7vi7iB@BEiiirrriiiiii:iiiiiiiii:i:i:iiiiriri;iriii::::;r7Luu15kkFFS12YY77rr;r;r;rir;rr7r777vLvLYjuuu11F5XkPkqSuM@B@B@MB@5B@@M, vB82     

MXuur,ir:::uZXu kL OB@O7:;rrrririiiii;iiiii;iiiiiii77v77rri;iiii::,:irvYju2FFXSNXk1UYL7vrrrririrrrrrr7777vvYLjjuu2155SkqXqPqU@@@B@@@B@FNB@uiiMMBM     

B8OSL.r7   rrLU,8 ,XBB@kiirrr;riri;i;i;iri;irirr7L21uL777iriiii::,::ir7vjj21kFXPEPqk5jL77r7rr;rrr;rr7777v7LLJJuu22F5SSPX0qEXSB@@@B@B@BOu2E@k8BB@@r i1k

U1O@Oiii  .v.iSYPrXOO@B@viirrririririrrr;7r77vvuSO02v7rrrr;riiii::.:ir7vLJj15XkN0000XFuJvv7rrrrrr7r7r77vvLLjJJJuu15SFPPNqE0XE@B@B@B@B@B0MP:UB@B@B@XXFG

5JkM@PLF:  ..SqLX7XZ8M@@@iiirrr;r;rrrr7r77vvYuXZM8Fv;iiiii;iiii::.::;r7vLLuuX0ZPqXPP0XP55Jv77rrr7r77v7L7v7LLuJUUF2kXPPEEZZ8F@B@B@B@@@B@BBLXB@B@@@BEqM5

BMGMOi:00MB@B7 58YvEM@B@BOir;rrrrrrrr77vvLJ2FEO@0Fj7i::i:ririi::,::r;77vLJjFPOX1u2u21XNZkkUJvv77777v7vvLvLvJYuu15SkPNZZ88OZ0B@B@@@B@B@B@B@B@B@kNM@@@Bk

0jUuuriSqFY iiOBBO8ZBB@@@BPr77v77r77vvLLjjSXGOMZ2Jj7i:i:iirii:i:iirr7rvvYYUFqX5JYYJJ2FEOMPP5UJYLv7v7LvYLjLujUu55kk0qGGOOMOEB@B@B@B@@@B@B@B@B@B@B@B@BML

Y7YjuS:iL7..u@BBB@B@q@@@B@@u7LvLvLvLvJYuUFX0ZMPuLLvL77;iiii;iii;irr7r77LLu2kXkuJLYLu1P0@BZPPS5uuLYLLLJJujju1uF5Xk0E8OMMMOOG@B@B@@@B@B@@@@@@@@@@@@@B@@5

1Y22SO0 jSuOru@7.;OBP@@B@B@@vLjJuLjJuJU2FFN0Oq2LL7v7LLYLLrrr7i;rrr7777vLuUSkkUuLJYU5qE@BBO0FS15uuYJJuJuuUu11XFkXEG8OMOBMBZ@@@B@B@B@B@B@BOM@@@B@M@B@@@M

k2SPXMBr @B@O:Or vFqO@B@B@B@Ovj22115u2UF5XqGEkuJ77r7r7vJ1qXXuJvv777L7LLU1PXk2uj21PEOM@MMOM8P1522jujUuUu22FSXkPPZGMMMMBBBM@B@B@B@B@B@B@B@B@OZB@M@B@B@B@

05PFXOBB5JEB@jBMri@B@B@B@B@B@qLu22SFk1kSqqEE01uLvrrrr;rr7jFXPkk22u2255qZMMMOOM@B@B@B@MMOMMM0S2522u2u2U55XkPP0q88MMBMBB@MM@@B@B@B@B@B@B@@@@EjkB@M@B@ZOB

JvJ2SMB@BMFG2SBNYvB@B@B@B@B@B@FYjUu5155XqENNXFuJv7r7rr;rrrr7vu2k0MMMOMB@B@B@B@B@B@B@MMOOOMOGkS5k552F5FSXkPqZGMMBM@B@BBMB@@B@B@B@B@B@B@B@B@B@MBB@B@.i2@

GP8k5u2SOB@qL7 ,2B@B@B@B@B@B@B@5LLuJuu2U55PXqF5jY77rrr7rr;rrr;77JU0M@@@@@B@B@B@@@B@BBMBMMMMZEPXSPkkkPXqNGE8MMB@B@B@B@B@B@B@@@B@B@B@B@B@B@B@BqM@B@M2O@@

M8M@@@OMB@BG:.u@B@B@@@@@@@B@B@B@5LYjJjJUu55PkS11JLrrir;rrr;ri;irr7vJ18MB@@B@B@B@BBMBOOO80ZNZEZNqkNPqPENZGOOBM@BBB@@@B@@@B@B@B@@@B@B@@@B@@@@@B@B@B@B@B@

q1PXqO@B@BNPOB@@@@@B@B@B@@@B@@@B@XYLuJJJUuu2F211XqXLvr7r7r7r;iiirr7rrr7vU1PP0XNPqkqSF2FFqNEGO8OEZ0qFSkNNZZOOMM@B@@BB@B@B@B@B@@@@@B@B@@@B@B@B@B@B@B@@@@

5UP0Z@B@BPZMB@B@@@@@B@B@B@B@B@B@B@OYLJLLLYLuj2uSX@@@@@M80qF5U5UuLL77;iirrv7vvLvJYuuuu2UFkqGMM@BMG05uJU5kkqN0ZMM@B@B@@@B@B@B@B@B@B@B@@@B@@@B@O@B@@@B@B@

MEZSkPE0kLEPMB@B@@@@@B@B@B@@@@@B@B@BuvJLuYJLYYuU1u1F@@@BX508MEGGOOMOO0GGOGOGGEG08G8GMMBM@B@B@B@MEF2YYJUUFS0NOMBB@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@@@@

BMB@B@OXuZB@J8B@B@B@B@@@B@B@B@B@B@B@BqLjLYLLLLLuLL77YGBqiiLXq::r7J2qM@OMMBOMOBMMMBB@B@B@B@B@B@B85UYJYu155PqEOMM@@@B@B@B@B@@@B@@@B@B@B@@@B@@@B@B@M@@@B@

GXZOBE7:uB@BOM@B@B@@@B@B@B@B@@@B@B@B@B@YLvLLYLYLL7LvvJXGFvr:7:,,::::r:ir77vrLB@B@B@B@B@B@B@B@O01ULLLju1FPPGOM@@B@B@@@B@B@B@B@@@B@B@B@@@B@B@qNM@B@B@@@B

MMMBPi7OB@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@FLvLvL7v777LLJJ0MBu;iiii;7rLBZ77i;irG@@@@@quX@B@B@NFF5uUuJLLJ21kN8M@B@B@B@B@B@@@B@@@B@B@B@B@B@B@B@BBB@B@B@B@B@

@B@P77Z@@B@@@B@@@B@B@B@B@B@B@B@B@B@B@B@B@OL7v77r7r77vLUFkP0k5Lv7LJkq@@G0XSXZ@GP2U7LUGBMGZX555U225jJY15kNOM@@@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@@@B@B@B@@@B

EEPr;GO@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@Bjr7r7rrrrrvJ1uUuqEMqFuULiirr;r7vJYLvLj8GGOGqOZqPX5Fu12uYu2kP8M@B@@@B@B@B@B@B@B@@@@@B@B@B@B@@@B@B@B@@@B@B@B@

0S2:1BZZ@B@@@B@B@@@B@B@B@B@@@B@B@B@@@B@@@B@BFirr7rrrrrvJ512u20OX5ZNFS1511USSEEGGMGNFqMOZ88ZSF11U1YJUSqM@@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@@BOEB@B@B@B@B

XSF20OGSB@B@@@B@B@B@B@B@B@@@@@B@@@B@@@B@B@B@BGrrr7r7r77LjSSFUuj;rXk1FPqqUXSPP8NPS52qMB8MMOXS22u1u2UFNOB@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@

PUNM8N@B@@@@@B@B@M@B@@@B@B@B@B@B@B@@@B@B@B@B@B@vrr7rrr77YuFFXSFuF2Fu21k11Uuu2uFFkqGM@M@@OPFU12SFkFPNB@@B@B@B@@@@@B@B@B@B@@@B@B@@@B@B@@@@@B@B@@@@@B@B@B

BMB@1BB@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@@@Urr7rrr77Lu11kSPkXkS1kPX11222XNO8MMB@@B8S5u15E0EN8M@B@B@@@B@B@B@@@B@B@B@B@B@B@@@B@B@@@B@B@@@B@B@B@B@B@

BO@X70@B@B@B@@@B@B@@@B@B@B@B@B@B@B@@@@@B@B@B@B@B@E7r7rrr77LLu2kk0ZZZOZGEGZ8OMMBB@B@BMZkU2u5S8ZG8BB@B@B@B@B@B@B@B@B@@@B@B@@@B@B@B@B@B@B@@@B@B@B@@@B@M@B

@BB8B@B@B@B@B@B@B@@@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@@v7v77r7r77LJu2Sk0EGZOOMOMMM8OZEqX52u2UFXG8OO@B@@@B@B@B@B@B@@@B@@@B@B@B@B@B@B@B@B@B@@@B@B@B@BM@@@@FU

GPPJ@@@B@B@B@B@B@@@B@B@B@B@B@@@B@B@B@B@@@B@@@B@B@B@BF77rr;rrrr7777LvLLYJuLuJjJujuj2uuuUuFqOM@B@B@@@B@@@B@B@B@B@B@B@B@@@B@@@B@@@B@@@B@B@B@B@B@B@BO@@BB;

2JuPZOOOZ@B@B@B@B@B@B@B@B@B@B@@@@@B@B@B@B@B@B@B@B@B@B@jvr7i;i;irir;rir;7rrr77vvLLJLjJU2kNMB@B@B@B@B@B@B@B@B@B@B@B@B@@@B@@@B@B@B@B@B@B@B@B@@@B@B@B@B@BE

BZMO8M@B@B@B@@@@@B@@@B@B@B@B@B@B@B@B@B@@@@@B@B@B@B@B@B@Mu77r;irrrr7r7rrr7777v7LvLLjj5FNO@B@B@@@B@B@B@B@B@B@BLB@B@B@B@B@B@@@@@B@B@B@B@B@B@B@B@B@B@O@B@B

M8M@B@B@B@B@B@@@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@MU7rrrrr7r77v7v7vvv7LvYYUuF0MB@B@B@B@B@B@B@@@B@@@B@B@B@B@B@B@B@B@B@B@B@@@B@B@@@@@B@B@B@@@8@B@

@B@B@B@B@B@B17vuXSE@@B@B@B@B@@@B@B@B@@@B@B@B@B@B@@@@@B@B@B@@NJ7r7777LvLvLvLvLLJu2FO@@B@B@@@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@@@B@@@B@B@B@B@B@B@@@B@B@B@B

B@@@B@B@B@B;,JE@BO2SB@B@B@@@B@B@B@B@B@@@B@B@@@B@B@B@B@B@B@B@B@BMXFuuLuYjYJLJj210M@B@B@@@@@@@B@B@B@B@@@B@B@B@B@@@B@B@B@B@B@B@B@@@B@B@B@B@@@B@@@B@B@BBBB

@B@@@B@B@BX J5@B@M:G@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@@@@@B@B@B@@@B@B@B@B@B@@@B@B@B@B@B@B@B@B@@@@@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@BMB

B@@@B@BBE@BiLSB@BF1@B@@@B@B@B@@@B@B@B@@@@@@@B@B@B@B@B@@@B@B@B@B@B@B@B@@@B@B@B@B@B@@@@@B@@@B@B@B@B@B@B@B@B@@@B@B@B@B@@@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@

@B@B@B@B@B@BJvuuFE@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@@@B@@@B@@@B@@@B@B@B@B@B@B@B@B@B@B@@@B@@@B@B@@@B@B@B@B@@@B@B@@

B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@@@B@B@B@B@B@B@B@@@B@B@B@B@B@@@B@B@B@B@B@B@@@B@B@B@B@@@B@B@B@@@B@B@B@B@B@@@B@@@@@B@B@B@B@@@B@B@@@

@B@B@B@@@@@B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@BOB@B@B@@@B@@@B@B@B@M@B@@@  7@B 0@B@B@@@@@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B

B@B@B@B@B@XBB@@@B@B@B@B@B@@@B@B@B@@@@@B@B@B@@@B@B@B@B@B@@@B@B@B@B@Bi @B@B@B@B@     @B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@8@B@

@@@B@@@B@B@B@B@B@@@B@@@@@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@@@B@@@B@B@@GB@B@B@B@B@O2X@@@B@B@B@B@B@B@B@B@B@B@B@B@B@@@@@B@B@B@B@B@B@B@B@B@B@@@@@B@B@@@@O8@B

B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@@@@@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@@@B@B@B@B@B@

@B@B@M5FU5@B@M@@@B@B@B@B@BBq@B@B@@@B@B@B@B@@@B@B@B@@@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@@@B@B@@@B@@@B@B@B@B@@@B@B@@@B@B@B@B@@

B@B@BGYY0@B@UJB@B@B@B@B@@@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@@@B@@@B@B@@@B@B@B@@@B@B@B@@@B@B@B@B@B@@@B@@@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@

@B@BGLPB@B@MFJ@@@M@@@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@@@B@B@B@B@@@B@@@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@@@B@@@B@B@@@B@B@B@@@B@B@@@B@B@B@B@@@B

B@B@GMB@@@B@ZYB@B@B@BZYZB@B@B@B@B@@@@@B@B@@@B@B@B@B@B@@@B@B@B@B@@@B@B@@@B@@@B@@@B@B@B@B@@@B@B@B@B@@@B@B@B@B@B@B@@@B@B@@@@@B@B@B@B@B@B@@@8@B@B@B@B@P@B@

@B@B@B@B@@@@@B@ZZB@B0LMB@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@@@@@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@8O0@B@XqB@@@BB@@@@B

@@B@@@B@B@B@B@X@8JM@B@B@@@B@B@B@B@@@@@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@BOE20@B@BEM@@@B@B@B@

@B@B@@@B@B@BMvPO@B@B@@@MEXOB@B@B@B@B@B@B@B@B@@@B@B@@@B@B@BEB@B@M@B@B@B@B@B@ukB@B@B@B@B@B@@@@@B@B@B@@@B@B@@@B@B@@@B@B@B@B@B@@Mu@B@@@@ZB@B@B@B@O@@@B@B@B

*/



int n;

int cnt1=0,cnt2=0;

queue<int> q;

vector<int> v[100010];



vector<int> bfs(int x){

	vector <int> d(n,100010);

	d[x]=0;

	q.push(x);

	while(!q.empty()){

		int u=q.front();

		q.pop();

		for (int i=0;i<v[u].size();i++){

			int tmp=v[u][i];

			if (d[tmp]>d[u]+1){

				d[tmp]=d[u]+1;

				q.push(tmp);

			}

		}

	}

	return d;

}



int main(){

	cin>>n;

	for (int i=1;i<n;i++){

		int x,y;

		cin>>x>>y;

		x--;y--;

		v[x].push_back(y);

		v[y].push_back(x);

	}

	vector<int> d1=bfs(0);

	vector<int> d2=bfs(n-1);

	for (int i=0;i<n;i++){

		if (d1[i]<=d2[i]) cnt1++;

		else cnt2++;

//		cout<<i+1<<" "<<d[i][0]<<" "<<d[i][1]<<endl;

	}

//	cout<<cnt1<<" "<<cnt2;

	if (cnt1>cnt2) cout<<"Fennec"<<endl;

	else cout<<"Snuke"<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int dis0[100005], dis1[100005];



struct edge {

    int to, next;

} eg[200010];

int head[100005], tot = 0;



void init() {

    memset(head, 0xff, sizeof(head));

    tot = 0;

}



void addedge(int from, int to) {

    eg[tot] = {to, head[from]};

    head[from] = tot++;

}



void dfs(int u, int pa, int* d) {

    if(pa != -1) d[u] = d[pa] + 1;

    else d[u] = 0;

    for(int i = head[u]; i != -1; i = eg[i].next) {

        int to = eg[i].to;

        if(to != pa) {

            dfs(to, u, d);

        }

    }

}



int main() {

    int n;

    scanf("%d", &n);

    init();

    for(int i = 0; i < n - 1; ++i) {

        int u, v;

        scanf("%d %d", &u, &v);

        addedge(u, v);

        addedge(v, u);

    }

    dfs(1, -1, dis0);

    dfs(n, -1, dis1);

    int lcnt = 0, rcnt = 0;

//    for(int i = 1; i <= n; ++i) {

//        printf("%d %d\n", dis0[i], dis1[i]);

//    }

    for(int i = 1; i <= n; ++i) {

        if(dis0[i] <= dis1[i]) ++lcnt;

        else ++rcnt;

    }

//    printf("%d %d\n", lcnt, rcnt);

    if(lcnt > rcnt) {

        puts("Fennec");

    } else {

        puts("Snuke");

    }

    return 0;

}


// Fastest known solution for this problem: