import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAEgsaV0C/+19e3wURbZ/z+Q1vDIBUSMIDBgxiIQMBEh0lYQw0COTEElAfGAzmUxINJnJb6YnBFeXYBKXcYiyrtd13V1lvbter+7eZb1eF1mFIErQ9YGiyEMFFXSGgOILsgrM75yq6kl1T3cE3fv74/exldScb5+qOnXq1KlHd1etdLjmmE0mQbnMwlUCUm+MKCZ0McObPAkWwAqFAfB3jHChkA50GsdXLBSrwl6WtBJaGF8K/EuFf4VmSheai1XhhYxPCU1cmCbwV7Eq/GqhoAoFwZaIh7LuXkLR3UuWqsLeFIpnZajjmVm8XhavV+FnoWAWVKFSvlT2r4rhVaxcSjib8c3m+PGqOCTX4O/e+Sy/+cWqsJ3xtWviXQPx0oUzv7JYuIDlZ6SXXCa/Eir1MLmhvnp6weSGmkkN9b5Qy6SWwumTphfkBf15U4hMWYx3bvlClR6zmczDmQ3g/XvnH8xMO5g685/F9xSOem7NwO1VD8zEe9NZPKySDl9WXerYAWaTUCC0QtJ4rwj+XQX/nnx36tsDV62Vfud57sW7G+PbV3d4znurcl3bmuuKP5/0uXRTpq05P9fxtqvr8Piu4Q8MLn3owqYNK5y3PN2ffv4BAgzTwTea9fHzTPp4VsKS1NcYA/zpNP10agzwJwV9XDbg/9QAn5Guj/tS9fEKg3SGGKQzxkBvvzXABYN0phrordwgnT0GeLpB+vMN0v+lgZ6PGOBXGOT7ewM7+cpAn3MN+CcbyP+egd1aDNLpNKjfdQb47w3S/5mBHuoN9DnCQP6lBnr71kA//2ZQrioDOXMN8t1pIL/NIJ0XDfRzgwH+VwM53zYoV6aBHp4xSP9/DOQca1DePxjkOxDSGSuMENZWU/+fzfB/mim+w7NU1X9kplH8AMMXM/wLls4BN8VbGb6G5bs+u1iVbx7TT+sFanwKpDMU0umqWcr1yoLgTqX4AYYr/VKXiea7tFrNf5ylv1ST74w0mk5rtTqdHJZ+F8Oz2I28VJp+cY2mXEz/WSPU6QvQTwblGs/Eidg3ThckaVmj3ycFZXdAliRBurpZWuBdVh+UvYHSBncw6A0KkrOqTKrxBhhcVVba4Pd5q9zVDV56T/+O1CTXBbzuGukW7wrJA79kBD0tbqk24PVK3haPt0mu9/sE6fryymABZNtkz5cwp6Ac8K9wLJhX6XZ6HHh7XqU8zSOvaPICbZ8KPMvra7w+qd5XLzuagaFSts+QJMjOv1yqhhzdDQ1+TzONGbRPra331Ui19YGgLPlrHRXzPI2NJFP/tNqGULBOSWI6n4THHZRJCnBjaiDkk+sbQeZAwB+Ybeci+EFWr7sRRAl6A7LTA6jdU+cOSHLAXS8HQV7HAkyh2h2s9yjcziqpKl9yVE6XKuZVTpUamFpI5iTlIlBmY70PNEZFCJbaUR1BIndVFSRY1JdgvW8ZS1Ynd6JCBy1HYb0/CGULegucoDhWDMCng7LcDd4+QFNglnlCElAgVzcEalQhMpMO8tPVyDRPg9cdcMCdKZITZIJ/MrEOKPqUfKUW/CGsLing9i3zQpZKbU4ntQmmKUs+v7pC8fYMrrI196ucIBlvdghoysqqohos2gc2IHvqOPME2Solb2OTvAJMvgnajD/gXuZVLNQ+jZaaVkl1qNa4PqYCDypbWtbSIjV5A0G/z91QD8k25zMFJsScPYXVShCUVSaB4m6RIMUaBZ3ubmry+mpIIQGpaahohqqQi6DsRIsylnPRWUlH6qHAA/pPjgtmZhAXo/mWN5LIM1junO6KQHXUCTgaG1XGkjBLWlSif9KAgVfjJfxTm0Kyw8Os9OzaAFgp1jYxuPmgskZ/jZeUrxy8DmTa4q6ub7aj+QXrJQ+6Pgk9DrTsWr+D91F2KAlrnw2s0EkaB+YZAS+4hGYorl7rK2WNbR5f1wXL69yytmJZ08OKRd/dSN02/FrmgRpByi5IC33L0ewXeIOhRi/e9FC2Wj+kIYBqZH+DUOv11wq1y7xyEJEGuMGULXtb6mWh0dvoaWwiQdMKodbT4A96kWr0N6PjxkRZN9HorvcJc0tLpal5+cJcl3NWqTQlz16Q+Dklb5pQunhxySynZM+bSuHFi4G7IK9IRdntPElmV2Y2ccUwBf6lwn9mEtK/giqkv9PYXTMM0s1kVpdK8HQWL53dzWChheNO/i+d9bsmoTutb75UMX7FIJz5OdOVeadZOMju58O/+35xfzrOtq9Jp1hoRP0AlOPGBH8q6cuVccrOv9yShpOKOsYfXjnBjCsJQUa7e39lxhnpKkbLE+61YJnXsvR6paXKtCQx58ZLGd+ksfloYhxb3YdfxeGtHM6PFNZy+HQO7+LwEg5XxmGIz+Dl4fBCfpWkpg+fxafP4T/h0+HwKzk8eynFM7ixEhlncbiZH29zeAqH53M4r89CDufXM4o5PIPDRQ638PNTDh/A4Ys5fCBfXxw+iMPrOHwwhzdx+BAOb+HwTL7eOdzK4as5PIu3Bw4fyuEPcPhMfr7G4edw+GMcPpzD13P4uRy+gcPP5+2Ewy/n8O0cns3bJ4dfwOG7OXwEb28cPpLDoxx+IYcf4/BRHN7L4aP5cbi7Dx/Dz4s5nJ+nZnH4WN7+OXwcb/8cfhFv/xx+BW//HH4xb/8cPp63fw6/hLd/Ds/l7Z/DJ/D2z+GX8vbP4RN5++fwy3j75/BS3v45fBJv/xyex9s/h0/m7Z/D83n753A7b/8cPoW3fw6fyts/hxfw9s/h03g9tx2xiJG0F0WbIHZ0yWnRSgK+YNmqnu7Fpz0JLPGLn4K/1jHF8AvpOrwVOxCH6+LHkUbXGdtB6EeQRpcZ6yL0g0ijq4ytJ/S9SKOLjK0j9F1Io1uOrSX0HUijq4y1EvpWpFH8WBOhA0ija4wtJfTNSKNLjFUQuhppdIWxYkJfjzS6wFg+oRcgja4vZiP01Uijy4tlEXoW0ujqYgKhL0caXVzs2GmkpyCdRcpP6EuRHkrKT+hxSA8j5Sf0CKTPIeUn9DCkh5PyE3og0ueS8hPajPR5pPyE/mYu0OeT8hP6C6SzSfkJfRjpC0j5Cf0h0iNI+Qm9F+mRpPyEfhPpC0n5Cf0y0qNI+Qn9PNKjSfkJvRHpMaT8p5B+EmkbKT+hH0d6LCk/oR9BehwpP6EfRPoiUn5C34t0Dik/oe9C+mJSfkLfgfR4Un5C34r0JaT8hA4gnUvKT+ibkZ5Ayk/oaqQvJeUn9PVITyTlJ/QCpC8j5Sf01UhPIuUn9Cyk80j5CX050pNJ+U+S+kc6n5Sf0JcibSflJ/Q4pKeQ8hN6BNJTSfkJPQzpAlJ+oCs2H4SRSfRcyGozruVsQnLjdmi10WsAW7zVftQZfuMmMfyh2HbwWEWVs7ur1VUsiN1bskjQ3TWyWIgeh5S+so6ZDe39HYi6UJy0AwKxrTdTDB9abl6ydQNp89DQv1qyGW/FD1jHkKWeDTs4/i29KcAvhp8XtxyeKZp2iG/0hiDyRhr5TYgshrfR+B+y+K1X3uwEYwgNXQgxoz+DAi7ZlnYtQKYvt6K/ENuuXDwLGOTRCRGGL9x8bAnkFj4U37Ek9lOIYh0jxII0XFhybcmikoUlVZXiqiMiuJHNaOqbcPgWzYdSiuGtDvtxsWOfnCt23peDMmxaj5oI74+i/sXuUlwaBs2UkuGHM/w+l8Kn32IKL4odR+UrMfpqvLObRP8s+gsS3UGiid2zc8jSnxhuyKkD1IIeDUDSJ/WM6LsPP4g3XG8Kw137UVdYzmkq6zgupzrjcyxIFXICNH7LF2GS2LkmZy3eRJE3DiT57Y8+9q1uOTCtFlfkdiJTvuOuS7h0z6UF45AUQJzhF+37yqCwU0qsT7/Q1rswlOKMd2PBHwA+V/gzV/h09EFkhAJibk5WfFe4xxW5LafQGZkpRqZGf/4Npu4QUOaBYnyexdoeG4SyOZiMTGkg12JXRM7JF9tuh2Fh+7UAb5uds9QUAdW0d4UucsbLLaFRzki62NkSfQbH6mLR69aOyGDM8kR0/z/j8bKOuAx88wlfhpovg/DFo38DPrHztpwKsVPOWRxdDd6NkNGrJqIUs3Oga7sR7oK4l6G4ofFiJEWd1OFBVNcNmBTUYQXtFG/LsQjWu2+HmrB3xdZB4exbjm8xWTt2QgeDlZoNJcgODRNByLRoPsRFsXMxDShilhjvEq+A3K1rvBA1Nn0gJtnV+wy1/Jes7VtwxRt7lWPWLZbwmpzZYFURGsT+JGi5n+qH++Ek7v/oh/veJO4H++HuwLlZ9xxSp2XhvLvSLim1CaWrZ+dlxyRks3ReEw9nQSr3RMyo+adyiiGMjgU1xFaoGR5K5xgEZFiTrmJ4lGfY3wsM96kZRlg4hk3IYAGk1jqGPjHG2s7Cyi+mtnDbBSqXceoEaW9gCc+Rp4i5m56nzgIbQRYm+Zve5MYmht9DW87lEnoqkVDJ5uSUsjGla3r1mu1+NMVitL+2lii0iScQjcwQI+VR+5togS+fwIa6jWTobDsdt7Y/hglEJrpMXzNGsft5rCrkXnOcNGtOshF9kj2LWVrbd2AWnQ6Ts2hbybO7gYcaxwYUzDXhmNP0ov04NH4U3IaCbydpbivrrM12tp0yhdx3OYSS1ak5PbW1a4lYibTlFjFeaunx1+Yp+ucE+QUkA/6dcZaL3QLmLXYXM40UM4280DPFFf5EDH/qCh+OvgtK24CtEoS1dtx5ClvURclafBfcghgBUQx9wy9PYtR49DdfQ0+amxDq5NdEqGeoLR9yQXGy5bHWa7usQxMiQZjNRLTR6t8ihl05on0flD8SguyPYC2gysJ7o9cfJ67WGQF/WLQ4ar1jZQpGiYkT9oidz+bgiwWu8KfIuZ7UTIOqA2j4muoafEmBGGkn7M5wuthNf6LGnN1zmDOmTXADgj1Da0n/rsRxYBUeUqugFrMGty2WRZZZyq5YliWPLes4KGeUhQtygN8Jo/uy8DJLzAx8Sv2BhbnCB8QJx7DzB8N6hhiJdXYMrMR6b5dIfARcY8Twy66iw9Z7t1i2uKyOw9Cr0BZ1qbhBYXEWvWj9eSskfnXnT46Sye5Diq5moEgsI9Bu2we9oikmp7vCdixI0cfW9t8yFyVuiaaAH5WtlM+Emg1/IY/EPjtTjMCApgwqiiyliJ2LLGJnmQV1bIPBjlkMfy1CJ5lvveOP2BCIvjpekoeIEbhlErvNNNYsiPGa2LbNImeJkVuBWGERu2dZaA/QZcE7zqIXxPDnMBIKbUKzy++5VuxcYon9XuNH5QsMfGhPRsKFrfxJwn3Fv4zHeybVwpVoP2JkCelWLyH91FhNPxW6F9v89i/IwITN214E4Y6EuqE2e10Ta3LynW0He1FGm7PzxsuyyiKXYJ2Drj+Jrv0CbW2yMyxZru6cfRTsbG4WaUQu+JONJjiGdMgXaDrkUB32agu+oL1aIWgWetvF0At+Bm0s9vj30IH1nppT2GUzPZyApGMLEDnrdKrjXDp/wXRw1rf5RfDF0WIkAyBj9GNQdKwZMliLo58cZ7zMEhpNWqyqwXT2os/4LLrsc3QSwCgSRjGJ8V507cB41ecq5/Lw59TjbSIt4Tu8CrR6HMHlo05FMZIrRoot2HsVitBs2lNNAplfYy4t49ChbHVGFlmcVyzKQtt/U4aR+Qix7XmLM7zIEkMXS/1BWeQqMbzDNaEX22/Jc7T1OqLJrfc1V9GnSuv9FLTC3PR4VfNdvjzRdD8ixvMCpI9yuCZ84wzvcm45DWLsENsO9LpMB1AkYkWDwNhwJLkW1DGv88avLDiGs6AzzjwGCsYBYVl4vDN8k2VeZ+oRZ3hOFlqxWASe0doxCLLuGRAtgOx67gB/C125GL3fhi0D+81+hnATT9Au8T8/o0O4YurPrhKha4jMB92+LJ7YK1pdb4iR5VnYmk/sAeo10fSGWLTd2jkOfBPnmHd+RrpR+9HE3CIfTGzT39ncQj6mP0yA4Xj0sVFowP2Yz804TIKKjX+K49vj1vZOlBRGktaONiYzGVDu/5QMKHsaOLmuIHLBOB5zIHLhK4abNrFJy7uk8NpxeI8YuSI6lIi1T76I6G9Ukv5KTXQIXP8pHU0vjq4cheNecdULOPG6oeTGkiUlN5VIS7ZqopIaDc3HuJMwLlTUYt25AORubT8GbZHMGTqwVYJgtKxTj9Ha6zkKTfWVL9W+wNr+Vj/j081Jo9nufrifTOLe2A/3H5O4/7WScK7s2dOcKzuIangcEI5h6Jccw1ZkiH+hYriCZ3gEGSZoFCnfYORUnVw6rV9w6VyP6fjUGb3Ne+8iZNh6SsUwmmfIRobBiIS7o7dAU+6Z5gx3o6cYTaZP2WDwrvCX1A56eqgdfNRDrVCM/vpC0JVkQo/ZDWOcnpU9Aot+C+muvJruSnapSjzeqMTDY81x9GndsaCJq4iVQxKCS0fohO5alCXRUVKpUi7EGeBR2Us6E0nbmcgOHPSdZXfmDH/N5f5BD+2N9hymvZFE3Ml1WncizzzrEUhfHrf30I4sdJi2W+JglxEH4da08h+Uz7msVocc5nwzdTIjLqCT+EeOkMogXg5ZqyFKrC6uBssQ/Ow0NSXbaPQr3dHs0ZgC+KDN6Gqi1/XQCRQModcJbAiNXUBTFEZyw3FMjnD03hgaGCU21ZYVCxtxUTY6kYNFcGyF0euOqDqGjTFlfmXtuMdMR+DIbN8X+xMZvHfHLqJSK4sO1vZhccXnWfCXxvO2v2TWuo2HzcZu4y6ai5KvOqm707RJ4RtjRkk9YULNneI13BMj1gZ9hrUjE3sEtPvYbafU9fAicMU2D6B6L+y781n0CbyzcAARkYBowvcDmOAII8eXqbQQqJ2vTinaOXxKRzspSdrZ00+RXjCxhI9a23NwJgaNxtoxAn9p++H2k0kpv9mP3p9DbiLm3cQ2NGJOMWkTs/Qj5pdCn4ZQKXIUlNJzUq1lCUHNEsufU/j1j0+A4TcpSi3twlU/xSzCKXwL0I5VyCRSXYC/J3VevzDuvHpW6jXzvE9oMx//MbeKFht+kusbOG6BcfceYu41hsuWepy7PiacsWYDR/30x7hmmd46HwZB0HbXY2MlvmBUFJOeCNYQmoSaWU9qrjgKXKn4O/JUKq6OtL1migZAmp6LsPkuNtHhWcXH1BWQSDiFfz76549pv7aBNLxnc3BpJlr3icpB/PoQHSl3HLR23GKiDgL5HPaDsbuYdUbStk62QaKKRENeQRIFC68hgmHdYSbHcB0eEsCXEdTVtUY776o1qqoqPZW1HaKe/6cH2RjU9w2ITcagNfhLGYPecJD2gZUQxq7+Rr9+pmNiTOIKYljP5hxD1bzHVIi2F11/iCa1HcLi/zGRtr9HUBrV63qNKnmwtrofm2xWVO0Mp+agPI8p/h9ska2hzM4xsv/Pv//gjVPFxIPUqC/6CArZfhTnPSeiHx+k854Woun/MZPRPpT5CfylGb38kG72vz6iGn70Q9r+Wkj7c5j1RW39CBtHWtEklSXOmnR2lviDBD71oYHh/OEgZzjLP1JNsws/pFOgLhwVlZNZtiMx0diM6zbRaQfZE4pOESZ+ZVn4nGmIK2zDtZA0ZxyfCITLLBCHTckdbKEvCrNRC7bc9g/JlMyVA7X0DpmTgUWpzOWZJHO5px/TvJ20+tsF2qjSP+D6wxUfYguELPH5IcvybfyZlOUjSf1VSz/9lceg2sMfoJF8El11gDjN9eA0N1XAn40V84rJY5fVH9J1yny+L9r5AR0hNv0vjRC/PMDmf/up6TbR1bAbc+r+lzK8g2V4K8uwTskQp6k4d59H5u5senrfB5TbxbjJwz72GOtmXMLJF+MizAPoz8i/roXswwwjt+XkR994H+dyt+UUCrJIF+IwxyvpT02Oc1U5jjXK0YoD7wkf6Dt1N8u5MHrt+3QtPX6AjE/sR2PFBh3BpP3Uti6GGLEsYFI9v7VkoGv+Wgz/JKek9XaLAO4fh4GR27M2zYMBuP3NZ3BFNmrBjNt649Z2/HqB61lnQqr2l7AtjzB4moCLxNhswhaHPd4zoHatc1W3gM9xlVWtlc7O1AzxyjiMmTbhi3klVtcJMneLkKdGWdGR75M1PGv7HeqnGVvf0zw5Io96ZHzYdF9ONB319b7BkhDIEymEAUTUeoDO5C4lM7mc5IWhV9jI4+N343G6nkdlK4wehMRBqo4iMuNIzXFF8rHjiNRFIcG/k6ys5e+1tfQKLYOwDbfvRweS7grfBq6u0zUqfteFFq40X7+rPPhm634TrZt2kqfOIj4IWpNzDEs0+b3kxSRn+EhZ+DMuqcff1T5S29r3IKwXkxHf01WMM/ITUMG1UVckJJR1+qLOKxZFQ2CRx6PvvEcKe9/WHjNd58omChvGHgy9GFqMStqyj/hNOYP4TPnc9n1l4VN0Ob1vPV3rRIElNAsttA1it+/DxyMWa/sumHfE3kf2tm29iRcT6ojRHCuxbkmH7jEVjDdCg55rjQdehI0GPVUqtqVGbOUlkfROMV4SzoRC3zM2Tqb92KTwLa3o3n24ehJXL/SwVW/C8AwyTFAz/O0Ux/AAMvyRTK1AGatewGbIrebhXBlnSzsEZba0TdCbLc1M6n3O1fQ+XKFiApmlbsOOb5vS1fXc0kfsj65i9XcDqb9QVXJ/90XSlGq7yTjH/yZj6770x+5jJY5ko0evJx7dcxZdCF9HWt9MFDtzL+0UZuxhOXUL9G2JE9G3IHO6HPHyXto+ulOU6YktVZme/GwfHeUQJA/XIPBFrOjcvbT2clPpLCMbwqh5n2qWMXUP8cVlHXFrxw1sGQL5wO/FluN7MiSDsqTMV6cpmZtY5gQpx8zPJ/LuoZmvTaOZt0IY7diryvzp3X2Zz2WZIx9mrjPsIMoatodOOAZC3FjN6aT+gzAd3U37j0PvANNMYMK1vm2xalq1MFhdM44OVlFjMFj9t3F9g1UC4XPT1L7BalOqdtr016Rh288FQ5vqCdFcz2O5oqog1zFcrgSCXFFdSq670zRD5JUqI7vOKLe5eirZ+w4dImOxlCHyUjSIVXto/bUgUQWK67lKL/6DLD4KqMTfjnVawuIfQGL4bmrKl7GwYDedSQzeQ5cUssl6TQYmhD/ppGoum1PNNZpS/SVJ2R39KDuomBHLCH+eYUavJHmKR/rxFJ0mfRP17yITolybysbstrOzsR/kUo68bVDbv3yHq+3aXaoJ0SVvcxOiMt0JUc47yROiwa5wIT6aS3XG5xrNh8RwKT6+s7bXkEnrfOgdrieTVvXrFu1XJnUO5/TTOZzG16FWGdRC7C1SC4+MVrW5J0afZZv7IbVQ+5ZBmxmyi2szB95S1cLvd35nLTz09g+shcEmpRbMJp1aOJTU3v5u3N5ijwrMqyrTUv+b3LT0w53k5TtIFF8IJHnuw1/aPB9PyrO1nzbu01P3iTfp/OKzN1DtKQdwRrquvFjouUyP+yXGvYVyq+ev5P2Infqdy1oWcTVEjFm/Je+XVorhb3F0MIKstwLDZvwiSQy/j6t9m4HusYEtNl/IjK9zA96OrD8Af3HR8MqdxFYXKfcjD6z3LCVPWWe0/hQmaml3lZb2nIdpT32DLG1vYi91xivyrZuOkcyIvGK4+4bYSsgv+vIOGPsnxq8liyrFtiPZzvBpZ+QmGyY8kYxjLk56fPs4e1v08R04rZ9D3zGI3JTdX5xfsTjNNE42i5PVX5x2FmcWjUMnBZHRGGUciXJhYtKM+kTW8wkrfUen7YXsG0pu2qpqnAv7rMWVkxqBfz1OFcM1PMNgYBjc41AxlPMMw4FheM8sbjh8kDxaLciJdoIksV3qx6rfkptyjiXqx7tHNA9d4/RuVvQavGsGkp9f9M1vK6COyiJXkSZD1iDj87OtHQ8R7YxxRvwWsahHbi55FhXZU6iS/pzk8nNu6RIi+c7XwRYvXOuKTMSnjuPIU8cLlaeOrqJPQn/GBy1/fo20CarprZDle6FXIXusHAvWROdrtAl0vMbXiIWbDdSq508L0QBXHWklA7DTZMqZjQ0Kv/BIvKD8c5BNLPotAeXBMMNAdqjlJVvFzhtzLGS4iXz3gAY3peJIcwJDlrxOpql0iI6WQ97VxYZ2W6olIqfmYiPbjUXPRvZNr9GHwhbWQEfDnW3tOcshu0soDqIhtREdaDT+mjIId7xOnwnSCftPcqJPvU7XoEG1OMxJA0770U34leJG3KIBsVWv07FzJO38bJvyGvGQi7KVfsiVasGVoCzaA83OWXym3c9tJuIPMUjqflpwvfOTV+kiUxbte/Bx832v05Ivjd78Gm1UASpezxIio3rq9INyr3+VrFxb281x9j4z5Bj7+nSfv1RmEz+1RE+Sd/D33xD78lXd++/S+9G3XmV8g17BBpSwLy3/nxj/HxT+ff/ol/82xi8r/E/8g3efayui38Cd6NuvoHSzwZ9eWxKOlyxyho+XLHSG3y6pcnVevH6oTVgodk7aAGGla8Ih+z5xy6kU/CIqeuhlumIzWknQFT7sCh+fDWnEh78LTcwErTp0mLShJUoj2srJ++VW9m0V+5TKpPp6VGffmxpv8+SgXFPvE8r9wnXeoGAbKPCf2l9+eTBUDT81IH4O7/cBFfLINl+oocHm88u2ZndDfY1Q7yOhraFe9gbcDbZaf8DW4Pcty51gW14v19nwK3KbPf/ySwTn5Pk2fxMw4efjNviffLVdY6utb/AKgYnCHAhtY5HFR1LB/Tgge6HUH2qo8V0iszvIpexbZJ8izXXNn1XikqRyyV7YtEKu8/vqPdPwY/igPX+RuyHkdeBWCY4z4Z9aKbt9NbhfAYvSP3+RQ/kW3nFm8kydBbrgIx1T9oMpL1Z9l5z4TpPRB8rYvnDlxbr317P7Sw3ut7L7rZr7/cs7wzmf090ZlG+6w9dcH/D7Gr0+WRNTLc+xcn15lPtdDM+fX6xrx4oecExGvqdkoXZfnMT3nPPV/Ou+g3+dJv0dGn7TyJQr2tm3yIu743Fc3NoAjfkBaH57IMTn4tvBVeBIe3UsHq+AMPc44BDi++/4cnxdbzy+GyeW/4zH8duAxTBkxJftWiCsgBC/y8EvG3dDiK85Z4MvWg/hagh7WTNXvkk23bpAMLVkmUYOzrCsNWVkDWff+9pBFv47VX1+Qchh/K3b4vGl2L9nZs3JzL7aOmi5pVWYOeKKS6fmjOP3E0y5tcJFUshIwS17UpR08EMzTOsxyLdrlCCkDq4sFkoys2ZlZs/KtM3KzJ2VmV+SWTg3szWtLWNNemfa3an3pNxpJvFuxPqOxuO/Gwzxtlfpx+vKVMUbnpBHXR6l/K1fxeP3k4FuZlabmWKYl+XrePw+7MRnZWaVZGbPzsxvS7nbTO9V4Xe1UEdvsHgaGUoyi1Ui0P2OMD9IL/9EPD4EsNR1CxX5SzJtczPXpbSl3g3cKBd+Z5MNdT6KkwvxV/A7aMAv1uAH8btmHfwk2qcOPhzkyN4ej49luLJP4knAlwK/V6DlvsfsyMy+O8WRaetMdWTmrkkTM/PvTBczC9syyjKLG7CkUN5cUnbQAJTFQtLHRzurIR1tTxNPebqtVUj5c8pE9lF8BN94upkR65D4lH223oIfiHpM9Ft78mIUbieBjemvw9iulkg8g0R+Ki2WGwuCaxWY2qf4BezjjEhBtiOpdCeBbCBM57JtsmxI1KZRtmrM56dA2JSdF36TTncZeBUyMz2XTsV5G3N+NYPuhzAcM8UPq3AsOhgJx0C6q8N5RK+DYAwAwTsYZy0QyxRlnBhE2W5Etp8PphJ8juX478H0zjQkxgyhd95F4uoh9M67KMZ8IMzKVp3XDKPbWpyPd+zn0cI14Ve79efRjQx2IvEY/Akr20TYR1CpX0KF146kcX4ximlfNKt2Bo2n7FwlpOwgxF6lDHtZ1fnx8+kBJqqRf8f0ZUacQuI/TXTvAjOyfWmicaxI4FeMFkWeLFYnxTgtGJdGv4e/GonyNG4zhk7GNgvvPMzYupD4BxB/U1K7YwAt3Qj8YxlEiXX43fUw+BMxJWxyh5BSTlSoZIA/8OlvHIkt/L51O9lmFw9h7P1sR4N/NzHeTJPw4/Xj9eP14/Xj9eP14/X/87V2JJvvsf1Im0aq54kmg/C5NDXdraEPMlrZCyv3fJqusgdWu4vSyp5Pyj7iyp5Oyh5Xyt5PUXZfmZcpe3h9fTruJ/v9mIsT+5CR9YEBlE7sDZZCaWUvr9+yG8oeXsqeVOdq9JPSt/EXCZTRZG+qep6p7DWm7IWVP6xYhecOLVbJbWGKGqDJ/3Sclmd1FuWPM1qR4xijT1qL/5/aSWIfe81Vy+q1mYV3svB+Fj7KwqdZuI2Fu1j4MQuPszCdrTucx8LxLJzOwjksXMTCWhY2s/BOFt7PwkdZ+DQLt7FwFws/ZuFxFqazfYXPY+F4Fk5n4RwWLmJhLQubWXgnC+9n4aMsfJqF21i4i4Ufs/A4C9NZOzyPheNZOJ2Fc1i4iIW1LGxm4Z0svJ+Fj47Qt5O5paWX23IXVod8cshWkFeYVzBpSohQ9p/ZC/LyC/IKJlBcYEyeBrdvma3ZGwjimubUvGl5+ZMKaJQpP5MDoaC8YootV3YvC05e4HA5Siod0tRp+ZNrcT/OCbZcXBytwaVQl2tRGY0+QRDygisaZXc1hHKAhnXKr3qf7A00CXk+v+zNK5nlnARJM2qZL5RXHapvqJlUXyMQqs4drBPyalb4ID0aygF6hwmsIiS4F/A2uJGR/WpqkDHLevgre1vgL8hdD/f8NW7ZLeR566TagLvRK9XVBPooSNTjYXuhSjLZXpmkIbkDAfcKmoby+2ZPgAjmbqz3QDy/TP7QfGke1cGgkOfxN+Ka4g9uryOZL1b8Vd+5GYLKj2r9vHJdJKj3aOw7l4LSNg1/qoa2a+LLLL7MrSP1Fx/XcY6Dr1PiK/79AQbUMDxN0x8k1m+Zbzdr/L/iSJcy/5/Oym7R+OFFjNWs6U+WDlD3H0b6u4n5biW+4q9Psk0dV2vk1xwPItzC+gKFVvqD1axjXCf0yZ+iU/5bmU7Nmv4nd6i6/9HqTyl/uya+0p/lD1P3f2msj9fGv1voO0uF7/9zz1f360b1H9bEr2DxK1j8pSlq/ixNeJ8mvjK+Wc8yftOuH1+5HtTEV8Yr7S51v20k/zpN+1vL4q9l8etS+s//MU38vvNd+uqnv/yf1sRvrWDPISoovUazqKm1ny5NfFzepiEbj5n7z/9Nga44pmjGd8r5MdryavN/nz1zSNGM/6JL9Pm19GEmf2LcxOIfO8P4n3Ftix//KOf7KIpJ18RXytWryV/ZF7hX6j9/JTylia+MPwUWdJn6j59uUsfvYvtVdrnPTP+D2cKnEl/Zv3gHi2/R2K+2PxjK8s/X4Er8Ow36HyUcKqj3AVauRdXMf5j697+87fJX/i1MDrbpLm7I6NLxXwMM8ieOFa6pQ/vPv78rBbiV/liNmxP9rBpPSfSfajw10S+q8bS+/k6Fpyf6MTWeoTufSAGtKP2OGh+Q6E/U+MBEP6HGByX8vxofnPDranxIwl+r8cyEH1bj1oR/VeNZCb+pxocm/KEaH5bwc2r8nIT/UuPDE35JjZ+b8Ddq/DzdeVQKzBoV/6DGs/vavQq/INGe1XjfOSpqfGQSZiI++/O4Fqd73ybrwcFwfFzJX9cyHB8D8lc9aX999ajsjbyK5D1COKQ5j2U941eePyt7HX/A8CYNfq6J4spza2VvZyfDu+ZQ/D6WQZDh6zTprGP4UpHibzD8K4a3FlH8d2wh49dmittY+vcz/stSKF7sZOsczPlcm0LLe1BT3lqCWxPP3xW/cz/DizX4Swxv1eAnGa68P6DgU1IpXqHBb2L4Uk06axiuvD+h7OH8LMOV9zaUvZc/Y7jyPoaC4/MuxJX3HpQ9lhczXHnfQdmDup3hynsfyjP8Jxm+Y76a/0OGN2nwc9OZPjV4Sbq+nbsIf3I7vS6d1qOgWQfzMTxfg69iuHbd7FfptN4/0NT7owRP9huvsnTWatLZQ/iT/Y9RuXoJ/1DBomm/6Rn65RUM/MAwwp/sf3LJgtY5SfIXMVwrp4ukk+z3FmbgmCHZjy3N0D9vaqUB/gTBoZ0y/6/0+X9n+BuafuT5DP3zpkwW/fTHW/TPJZtmgDsN0lligN9qgD9B8OT+7q8G/LsM8JgBbhmgjxcY4AsNcL8B/oABvhXwcWZoX6xcyvrr3gH653GNGqifTv5A/XO6Fg7Ur5f/MxDHlH3jBGW+0mqQ/sMG+CsG+AGDfL8ZiGPtZDvPGGRwbuEg/XPPFhvwrxqkfy7ZfwzSP5/tZeQ3XyDs0MizyyD944P0zzcbMlif/9LBNP3tmvRnGPDPG0zbaRarFy/DbzDg32CAvzpY/9y5HgP+IUOQZ0SSHi4YYtAuhuifX1dvwB82wP/LAH/dAD82RN+u0jL1z8GbmKmfzkwDfLUB/qAB/mQm1Vu0Rq23vxnwnzTAs6z65+NdbdXnb7Lqn+/3sAH/c1ba7rT1+4JV//y9QwbpXJGlj5cb4Dcb4HcY4Ouy9M8n3GjAv9MAP26ADxhqcL7lUNruuth4o4sNoCcRXGe+Njng98uTm1a4ZY+/xhuY3BTwVzd4G4OTg+7GpgbvZHe1J79wulQ6GU+hyvM0NZGTqPi18fwkxJ6ETBcSb90GQ9WSU0qkJl1v9Equ3S5J+DRArvdJkqug3O+jZ7+d8RvTs/Pp4V5n80rz94oz5QziFOBb32fEqby0/F2ihOT6BihvsM4d8NZIAW+ts1Ke3uz1yP6As7wyX6KpkbPvKt3OymmSw+FQBJh3JjonIs+oDfkwyUJ8l72h3uf1NDivXtCXPmFyYNJVnoZgoJ+UHIkkgk3ICpLVOGbU+gPL3YEaZ5XkqG0iIjbNryySzlhIRb5pTYF6n4zCacr+HaI5aMTvFGlGvyL15edpbmDnVboKJaneT5494dmHZ/Om/xnwa9/EP5Momo8DziCKzvvw3x2r76377+YtUheh8iy1VHn2Wqo8ey1Vfi8tVZ6FlirPSkuLzlJLi85eS4vOVHhPQA7KodraPI8gSVeXLpBczsoqSRL6DrCV5EbJgwfVBgUdSJJq/NKyBn+1u0GqgXYclNyhFsHjx85H9tbkTS8qnKLPJPU9hpVA8YEVAn2UWxNqbFwBUThK6nt6y1glac6CkjKH5CifjcfwEsnZb1bq+XPmVDqqpKqSWS4HcqiSqFED5JxGQZp9XXlJmbNUwOe+CqY9NLS4mD+Csf9DVjW89ExITzBESi4kcjjL80a1EugexavN+rtPLSZHZiaVjj+YU6fo/ZwzrOLGoytZqfUP91SnTc7hZBA7IDPpRE3N7X5PTtVKnnQGqVZdfed8JmdjcN5vcrUYns2blBu+wgH11tAgJU4y/n4nF2vUiIeX6hQg+WRjjUT9nmA9XyLf70mhoLcm+URj3fZhdMqwmpmesqqRt58Ds7XN1PBMbD3DTTpGVldwvbOwddqIzkm3Wi6dw5O1ZgDFU3xY0tHRydZFThxOhrmzsLXp1wT9Uh30jaA8esStbgtD/8QGPf/CM7vV3qBIOShXa5zqM6e1pUs+rVlbxOpgkLOIxIHlSZVxRqcYFxdzp/Imn72s6zOSDmJOTkR9WLVeKuoD39Up6B4Tb3DsujptemCxjjv4fsePa1yN11+rNafEIe3qEpDe9/sdAa7Jk3y9m2RCZ3wCt05HOoPvSEllNhs1d4PTzfXqkzseXaMK8oaZ3rnmyWbzLzi/W6cb1Ckd68+SHJ3q0Gy4xw60JsJNR7OH+XFyV8Idb56cFzugXEcI7entyabctKKv5u0FyYeAa2LgGdzUr/1fJ9U4jzOLAAA='
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    t0 = 0
    x0 = 0
    y0 = 0
    for _ in range(N):
        t1, x1, y1 = map(int, stdin.readline().split())
        t = t1 - t0
        r = abs(x1 - x0) + abs(y1 - y0)
        if t < r or t & 1 != r & 1:
            print('No')
            return
    print('Yes')
'''

Measured memory_bytes: 5932