import bz2, base64 exec bz2.decompress(base64.b64decode('QlpoOTFBWSZTWQ/4zvQACC7fgHwQev//+j////q//9/qYAk8fKrzjuS2ygUvsN7DroU0AMgNNEVHpGmgAPSHqA9QNADQMT1PFB6m9UBoDjJk0aA0aYjI0MQwJo0xBiNBhAAYNTT0JKGgaaDI0NAaaeoDTQ00DQABo00BKekkjQmptDUGifqTQ00HqPUGQ9RpoAAGgNqDaUpP1TGo09QeoemhAAAAaBkAAAABIkIATQBT00aCZTymSND9JlPU9IaAxqaD1D1HJy05lAyBR392piPpjE+xZ9t1BT6Eu4NBiDI1+UlHcqj0NBV1+2nI68EUdLEM7uWQZlLbjSZXQRVL7nl/q/DoI86cG/76787jo9Mm1Z4MjgIEuaEGbSEtkhQmDG0MYmDQ2mNAMdtWmr41RuaA+p8GgKqCGxFYyO3XXtkVNiXIvakDmBN/t56vkxlSmszIcuEH5fjS4J41z9Uxf8qBj9WQXibsqxrrnVT5D4AZfVrXVlZa6sSsbWbM2Bvav3TRdUWhu7/nyXedjYacNIFzJmaM0QyUggnSmNedZVQdZFJQFUyiqjAgFoLTCrMsAZKUREoxaZmfDQAhCiLhOYBgZRDxkcV4XpRIGM4mQMGVAJVMSjQSewJ54GJBIRSoJJJIISsEASSyss08stu7TDspoh3zQ8Jp54eVHpVVbv3Kr8LkIUS7m2nMQhICC1a515VQZYBQB3G5gzL1zCS8HVn46gYEJBieyMOq8I32CHmv2hXuW64WGd3dNm1r/czfXZSvGlRN48RnOp6uErJ8mhOLy6pleTrKRJ+vx+zxtP37Yu086PEJ89dhYabGEpUitazqjMEE6xorMNWNChT8HaTnBUSJDIG4icXyKsO5Hw9MKO1IsQjGDSRQUjCRkiIxjUC0LbhBphCBJJUkEIqxkYwMIITaxrQi1CtxM8KJbo+nMsurKw/187ESAZGKMpggrzjCwfQlp1szdybIjaTfCs55jc0XqpMWuow8TRYmc3b98vnxpwfu6Lko7U59E0vBL6HOQqOtrVKqg6SRgbEA38rA5Xd2Gcq1hj4aVnMiJwO7RNwSoULrYZIcZ+wOB5gik+kT1mYHQYCLAIRdyGGVaiiUHLQkpsDyHUHTl21HpHmePsRFZKmUin6z1gB8BgtXWvvkgKHJRF4Hkv0mXJQB+TGzPoQZpg1as/MC1ViDUqqagBGpapz+4NgrcWDc/6AC9CQz17Zv3iSWIuRYk7AYQIgIUAOAZVI1hjA1vXEoSAxWSynsNXTQW0v7R2h6CC2gK+nYbZU2hgGDmlpSVKAhWomI0wE+YTBSF0TO9GOVgMZA3ChpjhiMdN0SkuJG7aNdBzbc/Ad63waKM2jUGrjJXXMNCNmovyVYphXndTsTgcoiScD1IpkSFkpkTomrF2rgqigmmNhbXqsc1zVCvsDvWdZjTTqMqxybMZ0dM1q+I+krd7CKiKi3UBGCY22AxpkUjZmlJFXRHHS1S4DGhoTpYq/+oK48LT3rYb5lFaDBpZINx6btIDamInpBd4FKFgJpLDzQ+pcEvv9xpFpRNRyTcmSKwTsGklMoU+VjcixjfyYvCt8EK8vFLdUdbZXG17ymGE8nX8c1a0gmcJbBpO9UV9UtCDKQNpeho6uKf5WmqNnJWoTLXw9BwzqFkt7rhF8VZWQ2iwDU4OIwQBEIiKyRDjLMkALsFLHWDOVFyKpqY4cOd1cqyboIsUJoZQVm6YUAd9AhVCJgoEpqEiqxSVasQMQ/mwLWj+AJYJFAhJHiA0VlD0SQdGo1MYPezEEGuDlzi5CDHR0dNPatgIOhFRPd8xtMaG0wY0qDBvFFUUQnJ74lRIpsBbA0xpiagTxKBVUwaQNI+IlqPoaBNrkMbBiGNA2MUb6Nw3VKSiiUVUKttiEED36ObenAaDd3FSKZTbGMQd6BjBJTOZ2lDWcFihUvPs16V7AtXoO0AKLekGK8td4dzfc4BPx/8auIxFK2xpeq7sOPfSIjjvLg3F+32xsIAk2NeXKzCL6qB4FpM5sRqscwRylM0ZdtADr/FeOda7C65DwgnZ8eLkmBRRVVVcQnrnOAaSvDUru40kmK8q35Hk1CCP44dYxvBF5X8FYCYMaSYIOKqPX1GIvcA9AFSr0EwhHSJQJKmkm6pCZMgPNqAShVqJCUCMbVekZDvaaVMWTqJkAeMUcTa7Zykm0SmkTKgUY0SNhJZe9ImgkOtOEIrHemiQVEMaGqQxJVJgyUyUz3711ZesNoDNyQz1L67QC8KyqWkZtQzNpHwEeyAqMFwB20NyUTAlbPtD6WdyLD6F1mK9tyVfBHoWrWTINBKXcbEfmQtvPTWTIrFd1d/ZBYGtFojRw0EQ2wkA0CyXUlMFYqSWpLisw42IK1Wy1XBpnmHu6CeVa7wXdYCl2q9XtJZXcKvUOpwfXUSipzOKyOO8KlqPwE0MG0NiPLsVmgWnY3CmiGw8Et4vFh5OByZzlKRKUpGPYRabFyRJykGPSQKnY9WWtM0plkibCwsIiqFE5aUidVFYlXLmhxVEFypgOw1G7jhXFiDiEcQmg4azMuniJTJJKgNRFGqtO9t0krjqqNBnWqqhTZq6LJliLkjgH57+KoBYWHsC+7K0YbsCZBuSG0gwL7gYm33pLeB56FtzDhmGtw9aPGrzHMbGIu1oA0LpnJL5fdGqBkLYwZoeySUZUISiBEJSWHpQqzxDcuZQ/+LuSKcKEgH/Gd6A=='))