from base64 import b64decode;exec(b64decode((b''+#ZnJvbSBiYXNlNjQgaW1wb3J0IGI2NGVuY29kZQpmcm9tIHpsaWIgaW1wb3J0IGNvbXByZXNzLCBkZWNvbXByZXNzCmogPSBiJzAwMCcKcyA
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                 ZnJvbSBiYXNlNjQgaW1wb3J0IGI2NGVuY29kZQpmcm9tIHpsaWIgaW1wb3J0IGNvbXByZXNzLCBkZWNvbXByZXNzCmogPSBiJzAwMC                                  '+
b'                 cKcyA9IGIiZUp4OVZOOXZva0FRZnQrL1ltNk5nUzJvUUp2VzJqUG5VK1BENVo0dThZRWpGNUhsaWtFZ0xCajFyKzhNdjIzdGthanp6                                  '+
b'                 WHpmek95TWJKaW5CL0MzU2o0K1FIVEkwcndBLy9GQkpyczBrQ3lrNENXTy9EYTBTdzlaTHBVeUlaQ3R6ZmF3QkYrekxFdGppa3krV2                                  '+
b'                 5GMlFhdm42SmlUVUNCMUpjUTBsMW04M1VuZDU3VjJyRFFPWTlpYjBIbXMrNkR5NlhxVUZQcGVHTFpBWkZ0eklWaUJsTXNneVlvYjlH                                  '+
b'                 WDJuZXRkNFl0QVFVazV1MWdoR0F0a0NPR2gwRXNUUWhPeXQwd3NHTUFhZWJhRnhvYU1KelIrL2F4TzlDZmhDS0tRbUVRRVVQVlJ2Ly                                  '+
b'                 tRdTdlMG10SGY1b0QxTUZza1QxbE12OXBvTk5KTVRadnlTaDdYY3RBYUtDdUlVVEN3WmwyaDhRblg4b1I0SWFLTWxid3FIOTdjWGwz                                  '+
b'                 NlJaN2tiakI0M2RjMDQ2cTYvNkc2Y2F2NlZHVnhWS0NZRGxEM1Fxb1V3N2g3TWd3aWpraGJ1dGJpK1c2RDFqMU1NRzJpS3lXOE5tbU                                  '+
b'                 VFaHB1NmFCUm9oZFZvMXFIM2pETjRReFJBdmsyK1NmMVoxRWZsTnpCd0wrbUxaekhjL2lHeWFxQndIbzJjeHAyMDA2c0drVHEweURw                                  '+
b'                 M2FZalZ1c00zYlBubm1hempRZkxKWENMOTlIdVpNQTdYei8vQWFOMDNHZ1JHYlkzQ0VRVXNLOWFrbXpZM0ZCSmJVMnFZVWxoT01Kcn                                  '+
b'                 c0b2t1U3pLUElHVXNWY2J4K2FpaTF2dHc4MEsydFhUUXdwOURXK1FyUS9RYm1ITGJtRlA5dGlyODFVL2JkS3JKTU1TOWpCNkRlMVBG                                  '+
b'                 ZjlEdnVxSEhiR2Y1c                                                                    DErdGZHenhXMEpobH                                  '+
b'                 ZlMDNKOWJsdFAxWDZ                                                                    6bks0VVl0NjRMNDVD                                  '+
b'                 b05ReDRYZGVTakZ0M                                                                    2gxZUZ1Rmt6dkVxYW                                  '+
b'                 Y4Q2RaTGpaOEk3MU5                                                                    ORHpRPT0iCnogPSBk                                  '+
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                                                                                     ogPSBiJzAwMCcKcyA                 '+
b'                 9IGIiZUp4OVZOOXZv                                                                                     a0FRZnQrL1ltNk5nU                 '+
b'                 zJvUUp2VzJqUG5VK1                                                                                     BENVo0dThZRWpGNUh                 '+
b'                 saWtFZ0xCajFyKzhN                                                                                     djIzdGthanp6WHpme                 '+
b'                 k95TWJKaW5CL0MzU2                                                                                     o0K1FIVEkwcndBLy9                 '+
b'                 GQkpyczBrQ3lrNENX                                                                                     Ty9EYTBTdzlaTHBVe                 '+
b'                 UlaQ3R6ZmF3QkYrek                                                                                     xFdGppa3krV25GMlF                 '+
b'                 hdm42SmlUVUNCMUpj                                                                                     UTBsMW04M1VuZDU3V                 '+
b'                 jJyRFFPWTlpYjBIbX                                                                                     MrNkR5NlhxVUZQcGV                 '+
b'                                  HTFpBWkZ0eklWaUJsTXNneVlvYjlHWDJuZXRkNFl0QVFVazV1MWdoR0F0a0NPR2gwRXNUUWhPeXQwd3NHTUFhZWJhRnhvYU1KelIrL                 '+
b'                                  2F4TzlDZmhDS0tRbUVRRVVQVlJ2LytRdTdlMG10SGY1b0QxTUZza1QxbE12OXBvTk5KTVRadnlTaDdYY3RBYUtDdUlVVEN3WmwyaDh                 '+
b'                                  Rblg4b1I0SWFLTWxid3FIOTdjWGwzNlJaN2tiakI0M2RjMDQ2cTYvNkc2Y2F2NlZHVnhWS0NZRGxEM1Fxb1V3N2g3TWd3aWpraGJ1d                 '+
b'                                  GJpK1c2RDFqMU1NRzJpS3lXOE5tbUVFaHB1NmFCUm9oZFZvMXFIM2pETjRReFJBdmsyK1NmMVoxRWZsTnpCd0wrbUxaekhjL2lHeWF                 '+
b'                                  xQndIbzJjeHAyMDA2c0drVHEweURwM2FZalZ1c00zYlBubm1hempRZkxKWENMOTlIdVpNQTdYei8vQWFOMDNHZ1JHYlkzQ0VRVXNLO                 '+
b'                                  WFrbXpZM0ZCSmJVMnFZVWxoT01Kcnc0b2t1U3pLUElHVXNWY2J4K2FpaTF2dHc4MEsydFhUUXdwOURXK1FyUS9RYm1ITGJtRlA5dGl                 '+
b'                                  yODFVL2JkS3JKTU1TOWpCNkRlMVBGZjlEdnVxSEhiR2Y1cDErdGZHenhXMEpobHZlMDNKOWJsdFAxWDZ6bks0VVl0NjRMNDVDb05Re                 '+
b'                                  DRYZGVTakZ0M2gxZUZ1Rmt6dkVxYWY4Q2RaTGpaOEk3MU5ORHpRPT0iCnogPSBkZWNvbXByZXNzKGI2NGRlY29kZShzKSkucmVwbGF                 '+
b'                                  jZShiImogPSBiJyVzJyIgJSBqLCBiImogPSBiJyUwM2QnIiAlICgoaW50KGopKzEpICUgMTA4KSkKdCA9IHoucmVwbGFjZShiIkAiK                 '+
b'                                  2IiQCIsIGI2NGVuY29kZShjb21wcmVzcyh6KSkpCnUgPSBiNjRlbmNvZGUodCkKCmRlZiBmbXQodSwgZiwgcGhwKToKICBIID0gMTA                 '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'                                                                                                                                                         '+
b'KICBXID0gMTcKICBOTCA9IGIiXG4iCiAgaWYgcGhwOgogICAgc3MgPSBiIjw/ZWNobyB6bGliX2RlY29kZShiYXNlNjRfZGVjb2RlKGV4cGxvZGUoJyMjIycsJycuIgogICAgb').split(b'###')[0]))