import zlib,base64 exec(zlib.decompress(base64.decodestring(""" eNqtWftvG8cR/p1/xUKGwTuYPD2QJjVbp1VkOzaaNEaUNi0cQ1jerciF75XbPUnMX99vZvZeJB07 aQQIJG935z3fzOw9Uq9MnlcL5bfWqbqpNo0uFL7eN9Z7Uypbqjc7v61KtVRb7+vV6en9/X1S87Ok ajYzfxOOlbowz07q3RudvldnyVlygTPhsEsbW3tVY8k0yckMpwrjnN7gxMnJ7E3b1JUzaqXSqqgb rEwPQp6tzY3Kjb6z5QbSmkKZB5O2Xq9zk8xm17vS6wcQEMmUiAE51duq9rYq3TvoUrf+lui8rVof vr+bzfi54gW7x1j5qhcpmdlbVVZKzvb7of2dzUxGNjRqROve5rlam/68yciada5TCPxdYze21Pl0 q9N3Rmmnkq8u/4E9wihIklbQ0JZOafVLbtfLtXbm88+WpkwrcFd3pnFQU1W3Iznk6GJ2b/0W5/JK Z6YhW6b42fqq0N6mOs93KjNExp3SZyfuqVjYOGU9TBzsqHQDR81my1Qpde0r/FrvPB9XUWZudZv7 lXK84Kq2SU08U/T3A4WYEBGFoRGk9mEXW8KpCD6LyewDUTxJY6XLTKgKtX65KvNdol77uVNb3ZB+ 0Rqql5VXtkBUOYsIYYob49k2Hb+mKuj3lF6irgZ/9Uwgea6bDYj7rS4DhYUiRlkFqYlbaUwmtEh6 8TtUypKJ5lY2N2TnwpTkOjicEyMLJgjRILSELcy/XOPX84pPr7G9rVU1CaLB+EeXIRSFVQxKW6Jk HUJxp25bMCt02WIfYifkzYyyEjnKzzlFvzKlubXIxBXkWipXIGxgji4/I2d/MWqDACV1XFXx534k kvZ6XSHI/3x2xtZ1EhyRedBFnZtVl37fmo3+0WZwGTjCzmUGS6o3BUEPUbn44un86RfnQiNhGiL6 ZNcXn2HT07ApZsG9efBLipkuj1d9gsGxRjuLJXgvs843Fg4GQcgzHCtMZrVbMEvKK5BRjXXvCZdg wHVjNH8PVNcm1S2gDUtt6dq6rhoimSJWderJglCRiVUNDlfvCXQzg1yncElYZuBOiB4kXQgg0ATk lKM8oXjDobXNrd8RLCHuC3iG/GFM2Qusrn9ujfnFxEJ8bTyJ0aU9ceEYD7uI+a5qEeYdW/YqBBGR xH2dlgH9ewxxXbKRhAuJ3SBvYF+tb1uXsrIqej0v1HubZWS/vyzjTvl9rfvAPuq5xvjG2DtOX/wg wAU9lnNOiDYXK8zrxpZ+TphcjYEWqfa80feUQ12we/0emhSEaN4WnEoEpVCbMVjAk2R+wtCsBhCF VqJFUWUt5TaB5xhjITewWKhuzY7XCbYoSPggQNK1Rce+MPjYwaeeJeBaSGcpMoURC0BYGWQbM27M z61twBQKNG3JjoQYwIwhYEMyRT900tQaEB2qivOgDJDtsrRPEgpVIMsPFeIkAISEurpFWBfEAdk9 oAUj0iav1mC8CAorfx9SB+KF4yyLLIf8CkgZ1Foo49OEoKYLV4Lj+EACjZgiIQMYSsJh05ejKo1i VFokHh9wYJebJcs51lJiVpKR9vEGYAMlM4dwo2GoUCakfvYxMDqGyDObhvI03ZqUlY6uX10uzwkF TO5QM2ezV5bq3Y6DUHFHda6ii7Ozi+XZZ8vzP8VhgRVRL23jfNcFJOo7gqpgAWoZRB8Rlytpl5Z9 nCY9l4sRl8+nXK6gVVnd75fucbnu6/ReiR5RuR55xpZLbolEtJE8C0nTUMtC9eJdY1Io1ihS2TK3 JVg3G6RK2cWw7LgcXL81eU0xCDScbPm2IrSgyCJH5NXGpuShCnZLc02d3+wbm+KQCcbggj6UtLpd 5ziSoZ+ywY4vjUGogRNJPtSSBQMomYiDnZOKuw4+9FrdV22OhqCGEVKrPayCpoJMsFDSL3hHXceG cE08C1LID/SghlapdGiS97JFgjZB3GsDMPCIbXV9+a9/X379Qv3VmbXT7R0a8L8PX5PS+C+HRn+6 wJT+i0rAGXNrOYgAPXuNOpDp6PFTacxPubOYoVWBJbAUxSIinvYtSTeG8AZakfJOcK0m08bkeZgn hLY0LseIc7/TcQh9z29lMXnGJDBECIa5HTmIoXfBWIxq5RLU5e2C+k9AwGzGMRWA7CXieRDylaY+ h/J11BAOkfpdiTzRo5MKsYwooUbA3IcMQoYCzgB4OC59f5aJc6J4IAV4R4Y5k5vUc7qSqQsDF2WC f8Gd6E6uZfVbhGk0p2Cdx4RSc8n9edJJz59k/JsbW1p/cxOB/G08wAf9TIYh7Jmaz6drmfYaj/9Z lWa64AYR6FjgjNVH6rk0vWo6cjDkzHqJBhMwvQWbityrRuKRAwAWMPDBCEhpOlh9sCJXyqu2aZB6 1FFOQBdaiEsY/uIxn/67b3arCbWxearalFEn6WLerOfxZO/YZv25BBGRRfFxokmaY8yOjpCZ8JWA TSiMiXUvw3DOPKSm9lPRG22Bbd+3JXUkL5qmahYnV4xnMvBoCWf12J2ox70HBichPZ5DmWsMEvuR Q6753vi2KWWm4GGDO+pRJ8WWCFOyzNqD2ySRJqZvmJ6CFFFvyHgizTjw2UrjaAnH98NzIOCOEFgo alwOou6a05D6MgjMG6Bbl5SUjXsYyzPy1Ph8KuS+JOlhjg7hMKRQwX05GyrwkPzpbyQoqWhEXaLO RYwnV9+ffvMShkbUk9DxIXHmP6UqqTS+EqHR+LBxMI3VObybJUfzhW9gvGgLTgGPFp068ccjcv7Y zbtpQqs7MMsG/KNKTMFJX34NgYqJpxEqMnleC8Z8JHhHEbmSezeainsfd40ZxzH1I3sXPRSnEy25 m+A+Ah5xdVVm0sXQXc9xKz4KYxGQQHjf2geOsxf/eXFF7UWiIv7q7AZ9E+0I92tsRHWP4qFIHnQ0 DTH76eHsOf4vE/WadNRkWupS/haPeBK2zn8q59QiGMhMMS5hgfadLk+MlJ4QWUP33E0fKJtUq1Dw pNWBsTyzrzUDAIKJzkQhi0O8HLpvqCCrQyAUu20JrbAvVHUu5OKHn0rmQU+SYZALk2ASrtFYrAgm h7ofYgH35sQCu+I4nm4bg8tIoCchFhKJhcCGRekF6bEs6Xw877yDPOGP+Am5YfE0jkFxT6KPWo4T 7nfYbVHoxm11HuwXfvEx94dbc8+cB1WW/lJJ5QBFn2S3xbRULuQ6YVpNj1XGj1fHIIUidGIEmnKa IqzYNljw44qGjYDb0Ct0ts/aonYR38X8ASr00C2W5dvVT1Hn/4j1qWYfCGieB+h1hqHeLWL8PGwA CaR/pE1O+ghgSb8lwnDVEAXCGrn2v1WWAApznYt7aJ1Yf9zD9aQWan7/ZD1X8WRbwtJF0oBMFrhd mx3zya/7ggke77bIGmlV78QYgoODeGRoW/Jt3DELXeEgl4s8OHiY/0cnMfKMDDZaSD7BVPsSUds7 slcI4WOd7p7F+Lpz3+1H9It/h33JgJ15SXkxcvQJ1oy7+dRCV91s7jrzTiyCMRFjJJYddJWxMZGP CANmQufenq/ewTrrdDsfa9Dt/po/WPCBbJi4h84GtBDEProIJXMYp9AYteGa7JOGr/69nSwv066D kvub/sb2mTrvG4LhtM7v9c4dfW+RiGTUGFQwCV/XwjqrcaGqqDKdLNOT1b6w0gkTs+6tzuidTuk8 IQ31IcMl9RG665PVoRo0pLISx9/ICMUjxLYg9oG/R/0lxfiiatrmh3uNaRns3Hgmz8GMphoKn1je g6FTPl9cxL8hEnqsZgh4xrH49uzdIX0odbFSw/vU8f5z2U/3merInikPqP+aeg50vll/k8fiD29Y +yjrbg1nH7y3OSrpebgZH/tyMIo8HwnYDcJwiqUXQNHBZDzVKY5hIpSgOTa8H1oQEe/kq3C/iDCZ oIb6GNXFnmSD2wYgnx7ZP6GCV2X0CHg7XGiEQBhWk73hdZRV8cjiJ5fyqkbUoeOSsqTWxLn75If7 mMm2Ce03wVyPJWUd5Smjf1T3K3GSMLNoRHt8jRCrhTqUnfeGQjI9OBnjZPeohIwOLvaj+UB0voFg J6vocRbedbKs+66iCB1Ix3CVpTs0Wry54Z775obqxc1N6LuleHSFgHz7Px2ns24= """))) # packed with pyPack 0.0.2