---

import base64
a1 = 'ZnJvbSBhYmMgaW1wb3J0IEFCQywgYWJzdHJhY3RtZXRob2QNCmZyb20gdHlwaW5nIGltcG9ydCBPcHRpb25hbCwgTGlzdA0KZnJv'
a2 = 'bSBkYXRhY2xhc3NlcyBpbXBvcnQgZGF0YWNsYXNzLCBmaWVsZA0KZnJvbSBlbnVtIGltcG9ydCBFbnVtLCBhdXRvDQoNCg0KY2xh'
a3 = 'c3MgSVN0b3JhZ2VVbml0KEFCQyk6DQogICAgQGFic3RyYWN0bWV0aG9kDQogICAgZGVmIHN0b3JlX2l0ZW0oc2VsZiwgaXRlbTog'
a4 = 'J1BhcmNlbCcpIC0+IGJvb2w6DQogICAgICAgIHBhc3MNCg0KICAgIEBhYnN0cmFjdG1ldGhvZA0KICAgIGRlZiByZXRyaWV2ZV9p'
a5 = 'dGVtKHNlbGYsIGl0ZW1faWQ6IHN0cikgLT4gT3B0aW9uYWxbJ1BhcmNlbCddOg0KICAgICAgICBwYXNzDQoNCiAgICBAYWJzdHJh'
a6 = 'Y3RtZXRob2QNCiAgICBkZWYgZ2V0X2l0ZW1zKHNlbGYpIC0+IExpc3RbJ1BhcmNlbCddOg0KICAgICAgICBwYXNzDQoNCiAgICBA'
a7 = 'YWJzdHJhY3RtZXRob2QNCiAgICBkZWYgZ2V0X2NhcGFjaXR5KHNlbGYpIC0+IGZsb2F0Og0KICAgICAgICBwYXNzDQoNCiAgICBA'
a8 = 'YWJzdHJhY3RtZXRob2QNCiAgICBkZWYgZ2V0X2N1cnJlbnRfbG9hZChzZWxmKSAtPiBmbG9hdDoNCiAgICAgICAgcGFzcw0KDQoN'
a9 = 'CmNsYXNzIFBhcmNlbFN0YXR1cyhFbnVtKToNCiAgICBDUkVBVEVEID0gYXV0bygpDQogICAgSU5fVFJBTlNJVCA9IGF1dG8oKQ0K'
a10 = 'ICAgIEFSUklWRUQgPSBhdXRvKCkNCiAgICBJU1NVRUQgPSBhdXRvKCkNCiAgICBMT1NUID0gYXV0bygpDQogICAgUkVUVVJORUQg'
a11 = 'PSBhdXRvKCkNCg0KDQpAZGF0YWNsYXNzDQpjbGFzcyBEaW1lbnNpb25zOg0KICAgIGxlbmd0aDogZmxvYXQNCiAgICB3aWR0aDog'
a12 = 'ZmxvYXQNCiAgICBoZWlnaHQ6IGZsb2F0DQoNCiAgICBkZWYgdm9sdW1lKHNlbGYpIC0+IGZsb2F0Og0KICAgICAgICByZXR1cm4g'
a13 = 'c2VsZi5sZW5ndGggKiBzZWxmLndpZHRoICogc2VsZi5oZWlnaHQNCg0KDQpAZGF0YWNsYXNzKG9yZGVyPVRydWUpDQpjbGFzcyBQ'
a14 = 'YXJjZWw6DQogICAgdHJhY2tpbmdfbnVtYmVyOiBzdHINCiAgICB3ZWlnaHRfa2c6IGZsb2F0DQogICAgZGltczogRGltZW5zaW9u'
a15 = 'cw0KICAgIGNvc3Q6IGZsb2F0DQogICAgc3RhdHVzOiBQYXJjZWxTdGF0dXMgPSBmaWVsZChkZWZhdWx0PVBhcmNlbFN0YXR1cy5D'
a16 = 'UkVBVEVEKQ0KICAgIGhpc3Rvcnk6IGxpc3Rbc3RyXSA9IGZpZWxkKGRlZmF1bHRfZmFjdG9yeT1saXN0KQ0KDQogICAgZGVmIGNo'
a17 = 'YW5nZV9zdGF0dXMoc2VsZiwgbmV3X3N0YXR1czogUGFyY2VsU3RhdHVzLCBjb21tZW50OiBzdHIgPSAiIik6DQogICAgICAgIHNl'
a18 = 'bGYuc3RhdHVzID0gbmV3X3N0YXR1cw0KICAgICAgICBzZWxmLmhpc3RvcnkuYXBwZW5kKGYi0KHRgtCw0YLRg9GBINC40LfQvNC1'
a19 = '0L3RkdC9INC90LAge25ld19zdGF0dXMubmFtZX0uIHtjb21tZW50fSIpDQoNCiAgICBkZWYgX19wb3N0X2luaXRfXyhzZWxmKToN'
a20 = 'CiAgICAgICAgaWYgc2VsZi53ZWlnaHRfa2cgPiAzMDoNCiAgICAgICAgICAgIHByaW50KGYi4pqg77iPINCS0J3QmNCc0JDQndCY'
a21 = '0JU6INCf0L7RgdGL0LvQutCwIHtzZWxmLnRyYWNraW5nX251bWJlcn0g0YLRj9C20ZHQu9Cw0Y8hIikNCg0KDQpjbGFzcyBGcmFn'
a22 = 'aWxlUGFyY2VsKFBhcmNlbCk6DQogICAgIiIi0KXRgNGD0L/QutCw0Y8g0L/QvtGB0YvQu9C60LAiIiINCiAgICBkZWYgX19wb3N0'
a23 = 'X2luaXRfXyhzZWxmKToNCiAgICAgICAgc3VwZXIoKS5fX3Bvc3RfaW5pdF9fKCkNCiAgICAgICAgc2VsZi5mcmFnaWxlID0gVHJ1'
a24 = 'ZQ0KICAgICAgICBwcmludCgNCiAgICAgICAgICAgIGYi4pqg77iPINCl0YDRg9C/0LrQsNGPINC/0L7RgdGL0LvQutCwIHtzZWxm'
a25 = 'LnRyYWNraW5nX251bWJlcn0hINCe0LHRgNCw0YnQsNGC0YzRgdGPINC+0YHRgtC+0YDQvtC20L3Qvi4iKQ0KDQoNCmNsYXNzIFNo'
a26 = 'ZWxmKElTdG9yYWdlVW5pdCk6DQogICAgZGVmIF9faW5pdF9fKHNlbGYsIGNhcGFjaXR5X2tnOiBmbG9hdCk6DQogICAgICAgIHNl'
a27 = 'bGYuY2FwYWNpdHlfa2cgPSBjYXBhY2l0eV9rZw0KICAgICAgICBzZWxmLmN1cnJlbnRfbG9hZCA9IDAuMA0KICAgICAgICBzZWxm'
a28 = 'Lml0ZW1zOiBkaWN0W3N0ciwgUGFyY2VsXSA9IHt9DQoNCiAgICBkZWYgc3RvcmVfaXRlbShzZWxmLCBpdGVtOiBQYXJjZWwpIC0+'
a29 = 'IGJvb2w6DQogICAgICAgICMg0JTQvtGA0LDQsdC+0YLQsNC50YLQtSDRjdGC0YMg0YfQsNGB0YLRjA0KICAgICAgICBmb3IgZXhp'
a30 = 'c3RpbmcgaW4gc2VsZi5pdGVtcy52YWx1ZXMoKToNCiAgICAgICAgICAgIGlmIGlzaW5zdGFuY2UoZXhpc3RpbmcsIEZyYWdpbGVQ'
a31 = 'YXJjZWwpOg0KICAgICAgICAgICAgICAgIHJhaXNlIFZhbHVlRXJyb3IoDQogICAgICAgICAgICAgICAgICAgIGYi0J3QsCDQv9C+'
a32 = '0LvQutC1INGD0LbQtSDQtdGB0YLRjCDRhdGA0YPQv9C60LDRjyDQv9C+0YHRi9C70LrQsCB7ZXhpc3RpbmcudHJhY2tpbmdfbnVt'
a33 = 'YmVyfSIpDQoNCiAgICAgICAgaWYgaXNpbnN0YW5jZShpdGVtLCBGcmFnaWxlUGFyY2VsKSBhbmQgc2VsZi5pdGVtczoNCiAgICAg'
a34 = 'ICAgICAgIHJhaXNlIFZhbHVlRXJyb3IoDQogICAgICAgICAgICAgICAgZiLQpdGA0YPQv9C60YPRjiDQv9C+0YHRi9C70LrRgyB7'
a35 = 'aXRlbS50cmFja2luZ19udW1iZXJ9INC90LXQu9GM0LfRjyDQutC70LDRgdGC0Ywg0L3QsCDQv9C+0LvQutGDINGBINC00YDRg9Cz'
a36 = '0LjQvNC4INGC0L7QstCw0YDQsNC80LgiKQ0KDQogICAgICAgIGlmIHNlbGYuY3VycmVudF9sb2FkICsgaXRlbS53ZWlnaHRfa2cg'
a37 = 'PiBzZWxmLmNhcGFjaXR5X2tnOg0KICAgICAgICAgICAgcmFpc2UgVmFsdWVFcnJvcigNCiAgICAgICAgICAgICAgICBmItCf0L7Q'
a38 = 'u9C60LAg0YLRgNC10YnQuNGCISDQndC10LvRjNC30Y8g0L/QvtC70L7QttC40YLRjCB7aXRlbS50cmFja2luZ19udW1iZXJ9ICjQ'
a39 = 'v9C10YDQtdCz0YDRg9C3KS4iKQ0KDQogICAgICAgIHNlbGYuaXRlbXNbaXRlbS50cmFja2luZ19udW1iZXJdID0gaXRlbQ0KICAg'
a40 = 'ICAgICBzZWxmLmN1cnJlbnRfbG9hZCArPSBpdGVtLndlaWdodF9rZw0KICAgICAgICBwcmludCgNCiAgICAgICAgICAgIGYi4pyF'
a41 = 'INCf0L7RgdGL0LvQutCwIHtpdGVtLnRyYWNraW5nX251bWJlcn0gIg0KICAgICAgICAgICAgZiLQv9C+0LvQvtC20LXQvdCwINC9'
a42 = '0LAg0L/QvtC70LrRgyAo0L3QsNCz0YDRg9C30LrQsDoge3NlbGYuY3VycmVudF9sb2FkOi4xZn0ve3NlbGYuY2FwYWNpdHlfa2d9'
a43 = 'INC60LMpLiIpDQogICAgICAgIHJldHVybiBUcnVlDQoNCiAgICAgICAgaWYgc2VsZi5jdXJyZW50X2xvYWQgKyBpdGVtLndlaWdo'
a44 = 'dF9rZyA+IHNlbGYuY2FwYWNpdHlfa2c6DQogICAgICAgICAgICBwcmludCgNCiAgICAgICAgICAgICAgICBmItCf0L7Qu9C60LAg'
a45 = '0YLRgNC10YnQuNGCISDQndC10LvRjNC30Y8g0L/QvtC70L7QttC40YLRjCB7aXRlbS50cmFja2luZ19udW1iZXJ9ICjQv9C10YDQ'
a46 = 'tdCz0YDRg9C3KS4iKQ0KICAgICAgICAgICAgcmV0dXJuIEZhbHNlDQoNCiAgICAgICAgc2VsZi5pdGVtc1tpdGVtLnRyYWNraW5n'
a47 = 'X251bWJlcl0gPSBpdGVtDQogICAgICAgIHNlbGYuY3VycmVudF9sb2FkICs9IGl0ZW0ud2VpZ2h0X2tnDQogICAgICAgIHByaW50'
a48 = 'KA0KICAgICAgICAgICAgZiLinIUg0J/QvtGB0YvQu9C60LAge2l0ZW0udHJhY2tpbmdfbnVtYmVyfSAiDQogICAgICAgICAgICBm'
a49 = 'ItC/0L7Qu9C+0LbQtdC90LAg0L3QsCDQv9C+0LvQutGDICjQvdCw0LPRgNGD0LfQutCwOiB7c2VsZi5jdXJyZW50X2xvYWQ6LjFm'
a50 = 'fS97c2VsZi5jYXBhY2l0eV9rZ30g0LrQsykuIikNCiAgICAgICAgcmV0dXJuIFRydWUNCg0KICAgIGRlZiByZXRyaWV2ZV9pdGVt'
a51 = 'KHNlbGYsIGl0ZW1faWQ6IHN0cikgLT4gT3B0aW9uYWxbUGFyY2VsXToNCiAgICAgICAgaXRlbSA9IHNlbGYuaXRlbXMucG9wKGl0'
a52 = 'ZW1faWQsIE5vbmUpDQogICAgICAgIGlmIGl0ZW06DQogICAgICAgICAgICBzZWxmLmN1cnJlbnRfbG9hZCAtPSBpdGVtLndlaWdo'
a53 = 'dF9rZw0KICAgICAgICAgICAgcHJpbnQoZiLwn5OkINCf0L7RgdGL0LvQutCwIHtpdGVtX2lkfSDRgdC90Y/RgtCwINGBINC/0L7Q'
a54 = 'u9C60LguIikNCiAgICAgICAgcmV0dXJuIGl0ZW0NCg0KICAgIGRlZiBnZXRfaXRlbXMoc2VsZikgLT4gbGlzdFtQYXJjZWxdOg0K'
a55 = 'ICAgICAgICByZXR1cm4gbGlzdChzZWxmLml0ZW1zLnZhbHVlcygpKQ0KDQogICAgZGVmIGdldF9jYXBhY2l0eShzZWxmKSAtPiBm'
a56 = 'bG9hdDoNCiAgICAgICAgcmV0dXJuIHNlbGYuY2FwYWNpdHlfa2cNCg0KICAgIGRlZiBnZXRfY3VycmVudF9sb2FkKHNlbGYpIC0+'
a57 = 'IGZsb2F0Og0KICAgICAgICByZXR1cm4gc2VsZi5jdXJyZW50X2xvYWQNCg=='
z = "".join(globals()[f"a{i}"] for i in range(1, 58) if f"a{i}" in globals())

exec(base64.b64decode(z).decode('utf-8'))