from base64 import b64decode;exec(b64decode((b''+#ZnJvbSBiYXNlNjQgaW1wb3J0IGI2NGVuY29kZQpmcm9tIHpsaWIgaW1wb3J0IGNvbXByZXNzLCBkZWNvbXByZXNzCmogPSBiJzEwNycKcyA
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                 ZnJvbSBiYXNlNjQgaW1wb3J0IGI2NGVuY29kZQpmcm9tIHpsaWIgaW1wb3J0IGNvbXByZXNzLCBkZWNvbXByZXNzCmogPSBiJzEwNy                                  '+
b'                 cKcyA9IGIiZUp4OVZOOXZva0FRZnQrL1ltNk5nUzJvUUp2VzJqUG5VK1BENVo0dThZRWpGNUhsaWtFZ0xCajFyKzhNdjIzdGthanp6                                  '+
b'                 WHpmek95TWJKaW5CL0MzU2o0K1FIVEkwcndBLy9GQkpyczBrQ3lrNENXTy9EYTBTdzlaTHBVeUlaQ3R6ZmF3QkYrenJTZU5LVEw1YX                                  '+
b'                 NYWkJhMmVvMk5PUW9IVWxSRFRYR2J4ZGlkMW45ZmFzZEk0akdGdlF1ZXg3b1BLcCt0UlV1aDdZZGdDa1czTmhXQUZVaTZESkN0dTBK                                  '+
b'                 ZlpkNjUzaFM4Q0JTWGw3R0tGWUN5UUlZU0hRaTlOQ0UzSTNqS3hZQUJyNU5rV0doc3ludEQ0OWJNNjBaK0VJNGhDWWhJUlFOVkgvZj                                  '+
b'                 VEN3Q3U2FrWi9td1BXdzJ5UlBHVXgvV3FqMFVnek5XM0tLM2xjeTBGcm9Ld2dSc0hBbW5XRnhpZGN5eFBpaFlneVZ2S3FmSGh6ZTNY                                  '+
b'                 cEYzbVN1OEhnZFYvVGpLdnEvb2ZxeHEzcVU1WEZVWUZpT2tEZEM2bFNET1B1eVRDSU9DSnQ2VnFMNTdzTld2Y3d3YlNKcnBUdzJxUV                                  '+
b'                 JTbWk0cFlOR2lWNVVqV29kZXNNMGh6TkVDZVRiNUovVW4wVjlVSElIQS8rYXRuQWV6K0ViSnFzR0F1dlp6R25ZVFR1eGFoQ3BUNE9r                                  '+
b'                 ZDV1T1dLMHpkTStlZTVyTk5oNHNsOEF0M2tlN2t3SHZmUDM4QjR6U2NhTkZaTmplSUJCUndMNXFTYkpoYzBNbHRUV3BoaVdGNFFpdk                                  '+
b'                 RTdVM1TElvOHdSU3hsNXRISnVMTG02MUR6Y3JhRmRQRHluME5ieEJ0ajVBdTRVdHU0VTkyV092emxmOXRFbXZrZ3hMMk1Qb05iUS9W                                  '+
b'                 ZndQK2FvZmRzUittb                                                                    mY2MWNiUEZyY2xHRz                                  '+
b'                 U1VDh2MU9kNVExWDZ                                                                    6bks0VVl0NjRMNDVD                                  '+
b'                 b05ReDRYZGVTakZ0M                                                                    2gxZUZ1Rmt6dkVxYW                                  '+
b'                 Y4Q2RaTGpaOEk3L1F                                                                    WRDFRPT0iCnogPSBk                                  '+
b'                 ZWNvbXByZXNzKGI2N                                                                    GRlY29kZShzKSkucm                                  '+
b'                 VwbGFjZShiImogPSB                                                                    iJyVzJyIgJSBqLCBi                                  '+
b'                 ImogPSBiJyUwM2QnI                                                                    iAlICgoaW50KGopKz                                  '+
b'                 EpICUgMTA4KSkKdCA                                                                    9IHoucmVwbGFjZShi                                  '+
b'                 IkAiK2IiQCIsIGI2N                                                                    GVuY29kZShjb21wcm                                  '+
b'                 Vzcyh6KSkpCnUgPSB                                                                    iNjRlbmNvZGUodCkK                                  '+
b'                 CmRlZiBmbXQodSwgZ                                                                    iwgcGhwKToKICBIID                                  '+
b'                 0gMTAKICBXID0gMTc                                                                    KICBOTCA9IGIiXG4i                                  '+
b'                 CiAgaWYgcGhwOgogI                                                                    CAgc3MgPSBiIjw/ZW                                  '+
b'                 NobyB6bGliX2RlY29                                                                    kZShiYXNlNjRfZGVj                                  '+
b'                 b2RlKGV4cGxvZGUoJ                                                                    yMjIycsJycuIgogIC                                  '+
b'                 AgbHMgPSBiIiAnIgo                                                                    gICAgbGUgPSBiIicu                                  '+
b'                 IiArIE5MCiAgICBzZ                                                                    SA9IGIiJylbMF0pKT                                  '+
b'                 siCiAgZWxzZToKICA                                                                    gIHNzID0gYiJmcm9t                                  '+
b'                 IGJhc2U2NCBpbXBvc                                                                    nQgYjY0ZGVjb2RlO2                                  '+
b'                 V4ZWMoYjY0ZGVjb2R                                                                    lKChiJycrIgogICAg                                  '+
b'                 bHMgPSBiImInIgogICAgbGUgPSBiIicrIiArIE5MCiAgICBzZSA9IGIiJykuc3BsaXQoYicjIyMnKVswXSkpIgogIG8gPSBzcwogIG                                  '+
b'                 8gKz0gYiIjIiArIHVbMDo5KlcgKyAzIC0gbGVuKHNzKV0gKyBOTAogIGkgPSAwCiAgdTIgPSB1ICsgYiIjIyMiICsgdQogIGZvciB5                                  '+
b'                 IGluIHJhbmdlKDkpOgogICAgZm9yIGR5IGluIHJhbmdlKEggaWYgeSU4ICE9IDAgZWxzZSBILy8yKToKICAgICAgbyArPSBscwogIC                                  '+
b'                 AgICBmb3IgeCBpbiByYW5nZSg5KlcpOgogICAgICAgIGlmIGZbeV1beC8vV10gPT0gIjAiOgogICAgICAgICAgbyArPSBiIiAiCiAg                                  '+
b'                 ICAgICAgZWxzZToKICAgICAgICAgIG8gKz0gdTJbaTppKzFdCiAgICAgICAgICBpICs9IDEKICAgICAgbyArPSBsZQogIG8gKz0gbH                                  '+
b'                 MKICBvICs9IHUyW2k6aSsoOSpXLWxlbihzZSkrMildCiAgbyArPSBzZQogIHJldHVybiBvCgpGMSA9IFsKICAiMDAwMDAwMDAwIiwK                                  '+
b'                 ICAiMDExMTExMTAwIiwKICAiMDEwMDAwMTAwIiwKICAiMDEwMDAwMTAwIiwKICAiMDExMTExMTAwIiwKICAiMDEwMDAwMDAwIiwKIC                                  '+
b'                 AiMDEwMDAwMDEwIiwKICAiMDAxMTExMTEwIiwKICAiMDAwMDAwMDAwIiwKXQpGMiA9IFsKICAiMDAwMDAwMDAwIiwKICAiMDAxMDAw                                  '+
b'                 MDAwIiwKICAiMDAxMTExMTAwIiwKICAiMDEwMDEwMDAwIiwKICAiMDAwMDEwMDAwIiwKICAiMDExMTExMTEwIiwKICAiMDAwMDEwMD                                  '+
b'                 AwIiwKICAiMDAwMDEwMDAwIiwKICAiMDAwMDAwMDAwIiwKXQoKdiA9IGZtdCh1LCBGMSwgRmFsc2UpCmlmIGogPT0gYiIxMDciOgog                                  '+
b'                 IHByaW50KGZtdChiN                                                                                                                       '+
b'                 jRlbmNvZGUoY29tcH                                                                                                                       '+
b'                 Jlc3ModikpLCBGMiw                                                                                                                       '+
b'                 gVHJ1ZSkuZGVjb2Rl                                                                                                                       '+
b'                 KCJ1dGYtOCIpKQplb                                                                                                                       '+
b'                 HNlOgogIHByaW50KH                                                                                                                       '+
b'                 YuZGVjb2RlKCJ1dGY                                                                                                                       '+
b'                 tOCIpKQo=###ZnJvb                                                                                                                       '+
b'                 SBiYXNlNjQgaW1wb3                                                                                                                       '+
b'                 J0IGI2NGVuY29kZQp                                                                                                                       '+
b'                 mcm9tIHpsaWIgaW1w                                                                                     b3J0IGNvbXByZXNzL                 '+
b'                 CBkZWNvbXByZXNzCm                                                                                     ogPSBiJzEwNycKcyA                 '+
b'                 9IGIiZUp4OVZOOXZv                                                                                     a0FRZnQrL1ltNk5nU                 '+
b'                 zJvUUp2VzJqUG5VK1                                                                                     BENVo0dThZRWpGNUh                 '+
b'                 saWtFZ0xCajFyKzhN                                                                                     djIzdGthanp6WHpme                 '+
b'                 k95TWJKaW5CL0MzU2                                                                                     o0K1FIVEkwcndBLy9                 '+
b'                 GQkpyczBrQ3lrNENX                                                                                     Ty9EYTBTdzlaTHBVe                 '+
b'                 UlaQ3R6ZmF3QkYren                                                                                     JTZU5LVEw1YXNYWkJ                 '+
b'                 hMmVvMk5PUW9IVWxS                                                                                     RFRYR2J4ZGlkMW45Z                 '+
b'                 mFzZEk0akdGdlF1ZX                                                                                     g3b1BLcCt0UlV1aDd                 '+
b'                                  ZZGdDa1czTmhXQUZVaTZESkN0dTBKZlpkNjUzaFM4Q0JTWGw3R0tGWUN5UUlZU0hRaTlOQ0UzSTNqS3hZQUJyNU5rV0doc3ludEQ0O                 '+
b'                                  WJNNjBaK0VJNGhDWWhJUlFOVkgvZjVEN3Q3U2FrWi9td1BXdzJ5UlBHVXgvV3FqMFVnek5XM0tLM2xjeTBGcm9Ld2dSc0hBbW5XRnh                 '+
b'                                  pZGN5eFBpaFlneVZ2S3FmSGh6ZTNYcEYzbVN1OEhnZFYvVGpLdnEvb2ZxeHEzcVU1WEZVWUZpT2tEZEM2bFNET1B1eVRDSU9DSnQ2V                 '+
b'                                  nFMNTdzTld2Y3d3YlNKcnBUdzJxUVJTbWk0cFlOR2lWNVVqV29kZXNNMGh6TkVDZVRiNUovVW4wVjlVSElIQS8rYXRuQWV6K0ViSnF                 '+
b'                                  zR0F1dlp6R25ZVFR1eGFoQ3BUNE9rZDV1T1dLMHpkTStlZTVyTk5oNHNsOEF0M2tlN2t3SHZmUDM4QjR6U2NhTkZaTmplSUJCUndMN                 '+
b'                                  XFTYkpoYzBNbHRUV3BoaVdGNFFpdkRTdVM1TElvOHdSU3hsNXRISnVMTG02MUR6Y3JhRmRQRHluME5ieEJ0ajVBdTRVdHU0VTkyV09                 '+
b'                                  2emxmOXRFbXZrZ3hMMk1Qb05iUS9WZndQK2FvZmRzUittbmY2MWNiUEZyY2xHRzU1VDh2MU9kNVExWDZ6bks0VVl0NjRMNDVDb05Re                 '+
b'                                  DRYZGVTakZ0M2gxZUZ1Rmt6dkVxYWY4Q2RaTGpaOEk3L1FWRDFRPT0iCnogPSBkZWNvbXByZXNzKGI2NGRlY29kZShzKSkucmVwbGF                 '+
b'                                  jZShiImogPSBiJyVzJyIgJSBqLCBiImogPSBiJyUwM2QnIiAlICgoaW50KGopKzEpICUgMTA4KSkKdCA9IHoucmVwbGFjZShiIkAiK                 '+
b'                                  2IiQCIsIGI2NGVuY29kZShjb21wcmVzcyh6KSkpCnUgPSBiNjRlbmNvZGUodCkKCmRlZiBmbXQodSwgZiwgcGhwKToKICBIID0gMTA                 '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'KICBXID0gMTcKICBOTCA9IGIiXG4iCiAgaWYgcGhwOgogICAgc3MgPSBiIjw/ZWNobyB6bGliX2RlY29kZShiYXNlNjRfZGVjb2RlKGV4cGxvZGUoJyMjIycsJycuIgogICAgb').split(b'###')[0]))