import zlib
exec zlib.decompress('x\x9cER\xdbj\xdb@\x10}\xf7W\x0c\x0b\x06\xa9\x91ElJ\x0bm\xd5\x87\xc6\xf4\x02\xb6\x13\xd7\x81<8z\x98Xck\x9a\xbd\x98\xddu\x1cQ\xfa\xef\x9d\x95\x9a\x06\x84\xe6\x9c\xb3s\xdb\x99est>B\x83\x91"\x1b\x02\x0c\xd0\x8cVUS\xbe(\xa5u\xe7,\xff8/\x96\xd5J\xc4\xaeX\x95\xc6\xd9\xd8\x8e\xd6\x95\xc1\xe7,[V\xd5t\x96\xbf\xc9\xe6\x93\xd9\xdb\xbc\xe8ib\x9f\xde\xa5\xff\xc5\xfb<\x1f\x1d=\xdb\xb8Uw\xa4\xf5\xef\xcb?w-Y\x88-\xc1#7\x01BD\xa9\x1e\xd8\x1e\xe4\x03\xb4M\x7f\xf4\x90\xc0\x03\x89\x16 :8j\xec\xee\xedu+\xd1\x1b\x07\x9a\xe2\xe0$\xf9\x02\xf8\x14\xe7N\x11\xf6\xce\xc3U\xeb9D\x83A\x95B\r\xc6L\xc1\x0f8sh\x81#\xec\xdcI\xa7\xb4\xafn@O\xe4;\xb9\xbc\xa4Wy\xa1\xae\x87\xce\xc6!I\xe0\xf6\xaf\x9e\xf7\xd6t\x10\xfd\x89@\xbb\'\x82@6\xa6\xce\x0c}\x90\xc8\xf1V\xed\xd9\x87\xa8\n\x15h\xe7l# \xb6\xec\x93\xdd\xbb\x93\x8fm\x02\xbc\xefm\xe0\xe7\xc1Jm\xdb#\xe2C\xdb\x03\xcb\x96z\x10_N\xf4\x7f\xa7x&-\xa0\xde\xae\'\xd3\xfaBI\xd5\xf2\x97c\x9b\xa9q#\xfd\xaaq\xc6\xc5V\xddJ-M0\x97\x16\x83\xc4|\xf5dw-|\'\x9b\xd8\x15j\x9d\x86\xf5E\x1aK\xfc\x9b\xd3\x8d\xac\xe2\xa7h=%\n\xb2~X`\'\x8a\x08\x9b3\xca\xf8\x116g6f\x90\x96\x98v\x86\xb0d\xfd8(\x0bl\x98\x02\xcc\xd1\xee\xfe\t\xce\xf7.\x0b\xc2\xe3\xa0\xdc\xf0\x91|\x001\x03\x9f\xfb\x931I\xe9A\xd2\xea-Ofu\x9e6\xc8\xc0\x16<\xda\x03e\xebbZL\xa6y\x9e.\x9b\xde\x03\xc2\x8d\xbc\x15\xcf\xcd\x81\x92\x93PB\x0f\xb7\x9e(M\xe5\xf3e\xfd\x17\xc0\x10\xeaG')
 

aW1wb3J0IHpsaWIKZXhlYyB6bGliLmRlY29tcHJlc3MoJ3hceDljRVJceGRialx4ZGJAXHgxMH1ceGY3V1x4MGNceDBiXHgwNlx4YTlceDkxRWxKXHgwYm1ceGQ1XHg4N1x4YzZceGY0XHgwMlx4YjZceDEzXHhkN1x4ODE8OHpceDk4WGNrXHg5YVx4YmRceDk4XHhkZHVceDFjUVx4ZmFceGVmXHg5ZFx4OTVceDlhXHgwNlx4ODRceGU2XHg5Y1x4YjNzXHhkYlx4OTllc3Q+Qlx4ODNceDkxIlx4MWJceDAyXHgwY1x4ZDBceDhjVlVTXHhiZShceGE1dVx4ZTcsXHhmZjgvXHg5Nlx4ZDVKXHhjNFx4YWVYXHg5NVx4YzZceGQ5XHhkOFx4OGVceGQ2XHg5NVx4YzFceGU3LFtWXHhkNXRceDk2XHhiZlx4YzlceGU2XHg5M1x4ZDlceGRiXHhiY1x4ZThpYlx4OWZceGRlXHhhNVx4ZmZceGM1XHhmYjxceDFmXHgxZD1ceGRiXHhiOFV3XHhhNFx4ZjVceGVmXHhjYj93LVlceDg4LVx4YzEjN1x4MDFCRFx4YTlceDFlXHhkOFx4MWVceGU0XHgwM1x4YjRNXHg3Zlx4ZjRceDkwXHhjMFx4MDNceDg5XHgxNiA6OGpceGVjXHhlZVx4ZWR1K1x4ZDFceDFiXHgwN1x4OWFceGUyXHhlMCRceGY5XHgwMlx4ZjhceDE0XHhlN05ceDExXHhmNlx4Y2VceGMzVVx4ZWI5RFx4ODNBXHg5NUJcclx4YzZMXHhjMVx4MGY4c2hceDgxI1x4ZWNceGRjSVx4YTdceGI0XHhhZm5AT1x4ZTQ7XHhiOVx4YmNceGE0V3lceGExXHhhZVx4ODdceGNlXHhjNiFJXHhlMFx4ZjZceGFmXHg5ZVx4ZjdceGQ2dFx4MTBceGZkXHg4OUBceGJiXCdceDgyQDZceGE2XHhjZVx4MGN9XHg5MFx4YzhceGYxVlx4ZWRceGQ5XHg4N1x4YThcblx4MTVoXHhlN2wjIFx4YjZceGVjXHg5M1x4ZGRceGJiXHg5M1x4OGZtXHgwMlx4YmNceGVmbVx4ZTBceGU3XHhjMUptXHhkYiNceGUyQ1x4ZGJceDAzXHhjYlx4OTZ6XHgxMF9OXHhmNFx4N2ZceGE3eCYtXHhhMFx4ZGVceGFlXCdceGQzXHhmYUJJXHhkNVx4ZjJceDk3Y1x4OWJceGE5cSNceGZkXHhhYXFceGM2XHhjNVZceGRkSi1NMFx4OTdceDE2XHg4M1x4YzR8XHhmNWR3LXxcJ1x4OWJceGQ4XHgxNWpceDlkXHg4Nlx4ZjVFXHgxYUtceGZjXHg5Ylx4ZDNceDhkXHhhY1x4ZTJceGE3aD0lXG5ceGIyflhgXCdceDhhXHgwOFx4OWIzXHhjYVx4ZjhceDExNmc2Zlx4OTBceDk2XHg5OHZceDg2XHhiMGRceGZkOChceDBibFx4OThceDAyXHhjY1x4ZDFceGVlXHhmZVx0XHhjZVx4ZjcuXHgwYlx4YzJceGUzXHhhMFx4ZGNceGYwXHg5MXxceDAwMVx4MDNceDlmXHhmYlx4OTMxSVx4ZTlBXHhkMlx4ZWEtT2Z1XHg5ZTZceGM4XHhjMFx4MTY8XHhkYVx4MDNlXHhlYmJaTFx4YTZ5XHg5ZS5ceDliXHhkZVx4MDNceGMyXHg4ZFx4YmNceDE1XHhjZlx4Y2RceDgxXHg5Mlx4OTNQQlx4MGZceGI3XHg5ZShNXHhlNVx4ZjNlXHhmZFx4MTdceGMwXHgxMFx4ZWFHJykK