# Original solution
import base64

exec(base64.b64decode(b'aW1wb3J0IHN1YnByb2Nlc3MKaW1wb3J0IHN5cwoKY29kZSA9IHIiIiIjcHJhZ21hIEdDQyBvcHRpbWl6ZSgidW5yb2xsLWxvb3BzIikKCiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8Y2N0eXBlPgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjb21wbGV4PgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGRlcXVlPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8bnVtZXJpYz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDx0dXBsZT4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDx2ZWN0b3I+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdXNpbmcgaW50NjQgPSBsb25nIGxvbmc7CgojZGVmaW5lIGFsbChfKSBiZWdpbihfKSwgZW5kKF8pCiNkZWZpbmUgcmFsbChfKSByYmVnaW4oXyksIHJlbmQoXykKCmludDY0IGRwWzMwMDBdWzMwMDBdWzRdOwoKbmFtZXNwYWNlIEZhc3RJTyB7CmNsYXNzIFNjYW5uZXIgewogIHN0YXRpYyBjb25zdGV4cHIgaW50IGJ1Zl9zaXplID0gKDEgPDwgMTgpOwogIHN0YXRpYyBjb25zdGV4cHIgaW50IGludGVnZXJfc2l6ZSA9IDIwOwogIHN0YXRpYyBjb25zdGV4cHIgaW50IHN0cmluZ19zaXplID0gMTAwMDsgLy8gZGVmYXVsdAogIGNoYXIgYnVmW2J1Zl9zaXplXSA9IHt9OwogIGNoYXIgKmN1ciA9IGJ1ZiwgKmVkID0gYnVmOwoKIHB1YmxpYzoKICBTY2FubmVyKCkge30KCiAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgaW5saW5lIFNjYW5uZXImIG9wZXJhdG9yPj4oVCYgdmFsKSB7CiAgICByZWFkKHZhbCk7CiAgICByZXR1cm4gKnRoaXM7CiAgfQoKIHByaXZhdGU6CiAgaW5saW5lIHZvaWQgcmVsb2FkKCkgewogICAgc2l6ZV90IGxlbiA9IGVkIC0gY3VyOwogICAgbWVtbW92ZShidWYsIGN1ciwgbGVuKTsKICAgIGNoYXIqIHRtcCA9IGJ1ZiArIGxlbjsKICAgIGVkID0gdG1wICsgZnJlYWQodG1wLCAxLCBidWZfc2l6ZSAtIGxlbiwgc3RkaW4pOwogICAgKmVkID0gMDsKICAgIGN1ciA9IGJ1ZjsKICB9CgogIGlubGluZSB2b2lkIHNraXBfc3BhY2UoKSB7CiAgICB3aGlsZSAodHJ1ZSkgewogICAgICBpZiAoY3VyID09IGVkKSByZWxvYWQoKTsKICAgICAgd2hpbGUgKCpjdXIgPT0gJyAnIHx8ICpjdXIgPT0gJ1xuJykgKytjdXI7CiAgICAgIGlmIChfX2J1aWx0aW5fZXhwZWN0KGN1ciAhPSBlZCwgMSkpIHJldHVybjsKICAgIH0KICB9CgogIHRlbXBsYXRlIDxjbGFzcyBULCBzdGQ6OmVuYWJsZV9pZl90PHN0ZDo6aXNfc2FtZTxULCBpbnQ+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBudW0pIHsKICAgIHNraXBfc3BhY2UoKTsKICAgIGlmIChjdXIgKyBpbnRlZ2VyX3NpemUgPj0gZWQpIHJlbG9hZCgpOwogICAgYm9vbCBuZWcgPSBmYWxzZTsKICAgIG51bSA9IDA7CiAgICBpZiAoKmN1ciA9PSAnLScpIG5lZyA9IHRydWUsICsrY3VyOwogICAgd2hpbGUgKCpjdXIgPj0gJzAnKSBudW0gPSBudW0gKiAxMCArICgqY3VyIF4gNDgpLCArK2N1cjsKICAgIGlmIChuZWcpIG51bSA9IC1udW07CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgaW50NjQ+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBudW0pIHsKICAgIHNraXBfc3BhY2UoKTsKICAgIGlmIChjdXIgKyBpbnRlZ2VyX3NpemUgPj0gZWQpIHJlbG9hZCgpOwogICAgYm9vbCBuZWcgPSBmYWxzZTsKICAgIG51bSA9IDA7CiAgICBpZiAoKmN1ciA9PSAnLScpIG5lZyA9IHRydWUsICsrY3VyOwogICAgd2hpbGUgKCpjdXIgPj0gJzAnKSBudW0gPSBudW0gKiAxMCArICgqY3VyIF4gNDgpLCArK2N1cjsKICAgIGlmIChuZWcpIG51bSA9IC1udW07CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwKICAgICAgICAgICAgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgc3RkOjpzdHJpbmc+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBzdHIpIHsKICAgIHNraXBfc3BhY2UoKTsKICAgIGlmIChjdXIgKyBzdHIuc2l6ZSgpID49IGVkKSByZWxvYWQoKTsKICAgIGF1dG8gaXQgPSBjdXI7CiAgICB3aGlsZSAoISgqY3VyID09ICcgJyB8fCAqY3VyID09ICdcbicpKSArK2N1cjsKICAgIHN0ciA9IHN0ZDo6c3RyaW5nKGl0LCBjdXIpOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsIHN0ZDo6ZW5hYmxlX2lmX3Q8c3RkOjppc19zYW1lPFQsIGNoYXI+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBjKSB7CiAgICBza2lwX3NwYWNlKCk7CiAgICBpZiAoY3VyICsgMSA+PSBlZCkgcmVsb2FkKCk7CiAgICBjID0gKmN1ciwgKytjdXI7CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgZG91YmxlPjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSB2b2lkIHJlYWQoVCYgbnVtKSB7CiAgICBza2lwX3NwYWNlKCk7CiAgICBpZiAoY3VyICsgaW50ZWdlcl9zaXplID49IGVkKSByZWxvYWQoKTsKICAgIGJvb2wgbmVnID0gZmFsc2U7CiAgICBudW0gPSAwOwogICAgaWYgKCpjdXIgPT0gJy0nKSBuZWcgPSB0cnVlLCArK2N1cjsKICAgIHdoaWxlICgqY3VyID49ICcwJyAmJiAqY3VyIDw9ICc5JykgbnVtID0gbnVtICogMTAgKyAoKmN1ciBeIDQ4KSwgKytjdXI7CiAgICBpZiAoKmN1ciAhPSAnLicpIHJldHVybjsKICAgICsrY3VyOwogICAgVCBiYXNlID0gMC4xOwogICAgd2hpbGUgKCpjdXIgPj0gJzAnICYmICpjdXIgPD0gJzknKSB7CiAgICAgIG51bSArPSBiYXNlICogKCpjdXIgXiA0OCk7CiAgICAgICsrY3VyOwogICAgICBiYXNlICo9IDAuMTsKICAgIH0KICAgIGlmIChuZWcpIG51bSA9IC1udW07CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwKICAgICAgICAgICAgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgbG9uZyBkb3VibGU+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBudW0pIHsKICAgIHNraXBfc3BhY2UoKTsKICAgIGlmIChjdXIgKyBpbnRlZ2VyX3NpemUgPj0gZWQpIHJlbG9hZCgpOwogICAgYm9vbCBuZWcgPSBmYWxzZTsKICAgIG51bSA9IDA7CiAgICBpZiAoKmN1ciA9PSAnLScpIG5lZyA9IHRydWUsICsrY3VyOwogICAgd2hpbGUgKCpjdXIgPj0gJzAnICYmICpjdXIgPD0gJzknKSBudW0gPSBudW0gKiAxMCArICgqY3VyIF4gNDgpLCArK2N1cjsKICAgIGlmICgqY3VyICE9ICcuJykgcmV0dXJuOwogICAgKytjdXI7CiAgICBUIGJhc2UgPSAwLjE7CiAgICB3aGlsZSAoKmN1ciA+PSAnMCcgJiYgKmN1ciA8PSAnOScpIHsKICAgICAgbnVtICs9IGJhc2UgKiAoKmN1ciBeIDQ4KTsKICAgICAgKytjdXI7CiAgICAgIGJhc2UgKj0gMC4xOwogICAgfQogICAgaWYgKG5lZykgbnVtID0gLW51bTsKICB9CgogIHRlbXBsYXRlIDxjbGFzcyBUPgogIGlubGluZSB2b2lkIHJlYWQoc3RkOjp2ZWN0b3I8VD4mIHZlYykgewogICAgZm9yIChUJiBlIDogdmVjKSByZWFkKGUpOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsIGNsYXNzIFU+CiAgaW5saW5lIHZvaWQgcmVhZChzdGQ6OnBhaXI8VCwgVT4mIHApIHsKICAgIHJlYWQocC5maXJzdCwgcC5zZWNvbmQpOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFR1cGxlLCBzdGQ6OnNpemVfdC4uLiBJcz4KICBpbmxpbmUgdm9pZCB0dXBsZV9zY2FuKFR1cGxlJiB0cCwgc3RkOjppbmRleF9zZXF1ZW5jZTxJcy4uLj4pIHsKICAgIChyZWFkKHN0ZDo6Z2V0PElzPih0cCkpLCAuLi4pOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzLi4uIEFyZ3M+CiAgaW5saW5lIHZvaWQgcmVhZChzdGQ6OnR1cGxlPEFyZ3MuLi4+JiB0cCkgewogICAgdHVwbGVfc2Nhbih0cCwgc3RkOjppbmRleF9zZXF1ZW5jZV9mb3I8QXJncy4uLj57fSk7CiAgfQoKICBpbmxpbmUgdm9pZCByZWFkKCkge30KCiAgdGVtcGxhdGUgPGNsYXNzIEhlYWQsIGNsYXNzLi4uIFRhaWw+CiAgaW5saW5lIHZvaWQgcmVhZChIZWFkJiYgaGVhZCwgVGFpbCYmLi4uIHRhaWwpIHsKICAgIHJlYWQoaGVhZCk7CiAgICByZWFkKHN0ZDo6Zm9yd2FyZDxUYWlsPih0YWlsKS4uLik7CiAgfQp9OwoKY2xhc3MgUHJpbnRlciB7CiAgc3RhdGljIGNvbnN0ZXhwciBpbnQgYnVmX3NpemUgPSAoMSA8PCAxOCk7CiAgc3RhdGljIGNvbnN0ZXhwciBpbnQgaW50ZWdlcl9zaXplID0gMjA7CiAgc3RhdGljIGNvbnN0ZXhwciBpbnQgc3RyaW5nX3NpemUgPSAoMSA8PCA2KTsKICBzdGF0aWMgY29uc3RleHByIGludCBtYXJnaW4gPSAxOwogIHN0YXRpYyBjb25zdGV4cHIgaW50IG4gPSAxMDAwMDsKICBjaGFyIGJ1ZltidWZfc2l6ZSArIG1hcmdpbl0gPSB7fTsKICBjaGFyIHRhYmxlW24gKiA0XSA9IHt9OwogIGNoYXIqIGN1ciA9IGJ1ZjsKCiBwdWJsaWM6CiAgY29uc3RleHByIFByaW50ZXIoKSB7IGJ1aWxkKCk7IH0KCiAgflByaW50ZXIoKSB7IGZsdXNoKCk7IH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgaW5saW5lIFByaW50ZXImIG9wZXJhdG9yPDwoVCB2YWwpIHsKICAgIHdyaXRlKHZhbCk7CiAgICByZXR1cm4gKnRoaXM7CiAgfQoKICB0ZW1wbGF0ZTxjbGFzcyBUPgogIGlubGluZSB2b2lkIHByaW50bG4oVCB2YWwpIHsKICAgIHdyaXRlKHZhbCk7CiAgICB3cml0ZSgnXG4nKTsKICB9CgogcHJpdmF0ZToKICBjb25zdGV4cHIgdm9pZCBidWlsZCgpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTAwMDA7ICsraSkgewogICAgICBpbnQgdG1wID0gaTsKICAgICAgZm9yIChpbnQgaiA9IDM7IGogPj0gMDsgLS1qKSB7CiAgICAgICAgdGFibGVbaSAqIDQgKyBqXSA9IHRtcCAlIDEwICsgJzAnOwogICAgICAgIHRtcCAvPSAxMDsKICAgICAgfQogICAgfQogIH0KCiAgaW5saW5lIHZvaWQgZmx1c2goKSB7CiAgICBmd3JpdGUoYnVmLCAxLCBjdXIgLSBidWYsIHN0ZG91dCk7CiAgICBjdXIgPSBidWY7CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgaW50Pjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSBpbnQgZ2V0X2RpZ2l0KFQgbikgewogICAgaWYgKG4gPj0gKGludCkxZTUpIHsKICAgICAgaWYgKG4gPj0gKGludCkxZTgpIHJldHVybiA5OwogICAgICBpZiAobiA+PSAoaW50KTFlNykgcmV0dXJuIDg7CiAgICAgIGlmIChuID49IChpbnQpMWU2KSByZXR1cm4gNzsKICAgICAgcmV0dXJuIDY7CiAgICB9IGVsc2UgewogICAgICBpZiAobiA+PSAoaW50KTFlNCkgcmV0dXJuIDU7CiAgICAgIGlmIChuID49IChpbnQpMWUzKSByZXR1cm4gNDsKICAgICAgaWYgKG4gPj0gKGludCkxZTIpIHJldHVybiAzOwogICAgICBpZiAobiA+PSAoaW50KTFlMSkgcmV0dXJuIDI7CiAgICAgIHJldHVybiAxOwogICAgfQogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsIHN0ZDo6ZW5hYmxlX2lmX3Q8c3RkOjppc19zYW1lPFQsIGludDY0Pjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSBpbnQgZ2V0X2RpZ2l0KFQgbikgewogICAgaWYgKG4gPj0gKGludDY0KTFlMTApIHsKICAgICAgaWYgKG4gPj0gKGludDY0KTFlMTQpIHsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxOCkgcmV0dXJuIDE5OwogICAgICAgIGlmIChuID49IChpbnQ2NCkxZTE3KSByZXR1cm4gMTg7CiAgICAgICAgaWYgKG4gPj0gKGludDY0KTFlMTYpIHJldHVybiAxNzsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxNSkgcmV0dXJuIDE2OwogICAgICAgIHJldHVybiAxNTsKICAgICAgfSBlbHNlIHsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxNCkgcmV0dXJuIDE1OwogICAgICAgIGlmIChuID49IChpbnQ2NCkxZTEzKSByZXR1cm4gMTQ7CiAgICAgICAgaWYgKG4gPj0gKGludDY0KTFlMTIpIHJldHVybiAxMzsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxMSkgcmV0dXJuIDEyOwogICAgICAgIHJldHVybiAxMTsKICAgICAgfQogICAgfSBlbHNlIHsKICAgICAgaWYgKG4gPj0gKGludDY0KTFlNSkgewogICAgICAgIGlmIChuID49IChpbnQ2NCkxZTkpIHJldHVybiAxMDsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWU4KSByZXR1cm4gOTsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWU3KSByZXR1cm4gODsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWU2KSByZXR1cm4gNzsKICAgICAgICByZXR1cm4gNjsKICAgICAgfSBlbHNlIHsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWU0KSByZXR1cm4gNTsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUzKSByZXR1cm4gNDsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUyKSByZXR1cm4gMzsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxKSByZXR1cm4gMjsKICAgICAgICByZXR1cm4gMTsKICAgICAgfQogICAgfQogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsIHN0ZDo6ZW5hYmxlX2lmX3Q8c3RkOjppc19zYW1lPFQsIGludD46OnZhbHVlLCBpbnQ+ID0gMD4KICBpbmxpbmUgdm9pZCB3cml0ZShUIG51bSkgewogICAgaWYgKF9fYnVpbHRpbl9leHBlY3QoY3VyICsgaW50ZWdlcl9zaXplID49IGJ1ZiArIGJ1Zl9zaXplLCAwKSkgZmx1c2goKTsKICAgIGlmIChudW0gPT0gMCkgewogICAgICB3cml0ZSgnMCcpOwogICAgICByZXR1cm47CiAgICB9CiAgICBpZiAobnVtIDwgMCkgewogICAgICB3cml0ZSgnLScpOwogICAgICBudW0gPSAtbnVtOwogICAgfQogICAgaW50IGxlbiA9IGdldF9kaWdpdChudW0pOwogICAgaW50IGRpZ2l0cyA9IGxlbjsKICAgIHdoaWxlIChudW0gPj0gMTAwMDApIHsKICAgICAgbWVtY3B5KGN1ciArIGxlbiAtIDQsIHRhYmxlICsgKG51bSAlIDEwMDAwKSAqIDQsIDQpOwogICAgICBudW0gLz0gMTAwMDA7CiAgICAgIGxlbiAtPSA0OwogICAgfQogICAgbWVtY3B5KGN1ciwgdGFibGUgKyBudW0gKiA0ICsgKDQgLSBsZW4pLCBsZW4pOwogICAgY3VyICs9IGRpZ2l0czsKICB9CgogIHRlbXBsYXRlIDxjbGFzcyBULCBzdGQ6OmVuYWJsZV9pZl90PHN0ZDo6aXNfc2FtZTxULCBpbnQ2ND46OnZhbHVlLCBpbnQ+ID0gMD4KICBpbmxpbmUgdm9pZCB3cml0ZShUIG51bSkgewogICAgaWYgKF9fYnVpbHRpbl9leHBlY3QoY3VyICsgaW50ZWdlcl9zaXplID49IGJ1ZiArIGJ1Zl9zaXplLCAwKSkgZmx1c2goKTsKICAgIGlmIChudW0gPT0gMCkgewogICAgICB3cml0ZSgnMCcpOwogICAgICByZXR1cm47CiAgICB9CiAgICBpZiAobnVtIDwgMCkgewogICAgICB3cml0ZSgnLScpOwogICAgICBudW0gPSAtbnVtOwogICAgfQogICAgaW50IGxlbiA9IGdldF9kaWdpdChudW0pOwogICAgaW50IGRpZ2l0cyA9IGxlbjsKICAgIHdoaWxlIChudW0gPj0gMTAwMDApIHsKICAgICAgbWVtY3B5KGN1ciArIGxlbiAtIDQsIHRhYmxlICsgKG51bSAlIDEwMDAwKSAqIDQsIDQpOwogICAgICBudW0gLz0gMTAwMDA7CiAgICAgIGxlbiAtPSA0OwogICAgfQogICAgbWVtY3B5KGN1ciwgdGFibGUgKyBudW0gKiA0ICsgKDQgLSBsZW4pLCBsZW4pOwogICAgY3VyICs9IGRpZ2l0czsKICB9CgogIHRlbXBsYXRlIDxjbGFzcyBULCBzdGQ6OmVuYWJsZV9pZl90PHN0ZDo6aXNfc2FtZTxULCBjaGFyPjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSB2b2lkIHdyaXRlKFQgYykgewogICAgaWYgKF9fYnVpbHRpbl9leHBlY3QoY3VyICsgMSA+PSBidWYgKyBidWZfc2l6ZSwgMCkpIGZsdXNoKCk7CiAgICAqY3VyID0gYzsKICAgICsrY3VyOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsCiAgICAgICAgICAgIHN0ZDo6ZW5hYmxlX2lmX3Q8c3RkOjppc19zYW1lPFQsIHN0ZDo6c3RyaW5nPjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSB2b2lkIHdyaXRlKFQgc3RyKSB7CiAgICBpZiAoX19idWlsdGluX2V4cGVjdChjdXIgKyBzdHIuc2l6ZSgpID49IGJ1ZiArIGJ1Zl9zaXplLCAwKSkgZmx1c2goKTsKICAgIGZvciAoY2hhciBjIDogc3RyKSB3cml0ZShjKTsKICB9CgogIHRlbXBsYXRlIDxjbGFzcyBULAogICAgICAgICAgICBzdGQ6OmVuYWJsZV9pZl90PHN0ZDo6aXNfc2FtZTxULCBjb25zdCBjaGFyKj46OnZhbHVlLCBpbnQ+ID0gMD4KICBpbmxpbmUgdm9pZCB3cml0ZShUIHN0cikgewogICAgaWYgKF9fYnVpbHRpbl9leHBlY3QoY3VyICsgc3RyaW5nX3NpemUgPj0gYnVmICsgYnVmX3NpemUsIDApKSBmbHVzaCgpOwogICAgZm9yIChpbnQgaSA9IDA7IHN0cltpXTsgKytpKSB3cml0ZShzdHJbaV0pOwogIH0KfTsKfSAgLy8gbmFtZXNwYWNlIEZhc3RJTwoKRmFzdElPOjpTY2FubmVyIGZpbjsKRmFzdElPOjpQcmludGVyIGZvdXQ7CgoKaW50IG1haW4oKSB7CiAgaW50IHIsIGMsIGs7IGZpbiA+PiByID4+IGMgPj4gazsKICBpbnQgdmFsW3JdW2NdOwogIGZpbGwodmFsWzBdLCB2YWxbcl0sIDApOwogIGZvciAoaW50IGkgPSAwOyBpIDwgazsgKytpKSB7CiAgICBpbnQgeCwgeSwgejsgZmluID4+IHggPj4geSA+PiB6OwogICAgLS14OyAtLXk7CiAgICB2YWxbeF1beV0gPSB6OwogIH0KCiAgaWYgKHZhbFswXVswXSAhPSAwKSBkcFswXVswXVsxXSA9IHZhbFswXVswXTsKCiAgZm9yIChpbnQgaSA9IDA7IGkgPCByOyArK2kpIHsKICAgIGZvciAoaW50IGogPSAwOyBqIDwgYzsgKytqKSB7CiAgICAgIGlmIChpID09IDAgJiYgaiA9PSAwKSBjb250aW51ZTsKCiAgICAgIGlmICh2YWxbaV1bal0gIT0gMCkgewogICAgICAgIGlmIChpID4gMCkgewogICAgICAgICAgZm9yIChpbnQgbCA9IDA7IGwgPCA0OyArK2wpIGRwW2ldW2pdWzBdID0gbWF4KGRwW2ldW2pdWzBdLCBkcFtpIC0gMV1bal1bbF0pOwogICAgICAgICAgZm9yIChpbnQgbCA9IDA7IGwgPCA0OyArK2wpIGRwW2ldW2pdWzFdID0gbWF4KGRwW2ldW2pdWzFdLCBkcFtpIC0gMV1bal1bbF0gKyB2YWxbaV1bal0pOwogICAgICAgIH0KICAgICAgICBpZiAoaiA+IDApIHsKICAgICAgICAgIGRwW2ldW2pdWzBdID0gbWF4KGRwW2ldW2pdWzBdLCBkcFtpXVtqIC0gMV1bMF0pOwogICAgICAgICAgZm9yIChpbnQgbCA9IDE7IGwgPCA0OyArK2wpIHsKICAgICAgICAgICAgZHBbaV1bal1bbF0gPSBtYXgoe2RwW2ldW2pdW2xdLCBkcFtpXVtqIC0gMV1bbF0sIGRwW2ldW2ogLSAxXVtsIC0gMV0gKyB2YWxbaV1bal19KTsKICAgICAgICAgIH0KICAgICAgICB9CiAgICAgIH0gZWxzZSB7CiAgICAgICAgaWYgKGkgPiAwKSB7CiAgICAgICAgICBmb3IgKGludCBsID0gMDsgbCA8IDQ7ICsrbCkgZHBbaV1bal1bMF0gPSBtYXgoZHBbaV1bal1bMF0sIGRwW2kgLSAxXVtqXVtsXSk7CiAgICAgICAgfQogICAgICAgIGlmIChqID4gMCkgewogICAgICAgICAgZm9yIChpbnQgbCA9IDA7IGwgPCA0OyArK2wpIGRwW2ldW2pdW2xdID0gbWF4KGRwW2ldW2pdW2xdLCBkcFtpXVtqIC0gMV1bbF0pOwogICAgICAgIH0KICAgICAgfQogICAgfQogIH0KCiAgaW50NjQgYW5zID0gMDsKICBmb3IgKGludCBpID0gMDsgaSA8IDQ7ICsraSkgYW5zID0gbWF4KGFucywgZHBbciAtIDFdW2MgLSAxXVtpXSk7CiAgZm91dC5wcmludGxuKGFucyk7CgogIHJldHVybiAwOwp9CiIiIgoKd2l0aCBvcGVuKCdzb2wuY3BwJywgJ3cnKSBhcyBmOgogICAgZi53cml0ZShjb2RlKQoKc3VicHJvY2Vzcy5Qb3BlbihbJ2crKycsICctc3RkPWMrKzE3JywgJy1PMicsICdzb2wuY3BwJ10pLmNvbW11bmljYXRlKCkKc3VicHJvY2Vzcy5Qb3BlbihbJy4vYS5vdXQnXSwgc3RkaW49c3lzLnN0ZGluLCBzdGRvdXQ9c3lzLnN0ZG91dCkuY29tbXVuaWNhdGUoKQ=='))

# Optimized solution
import base64

exec(base64.b64decode(b'aW1wb3J0IHN1YnByb2Nlc3MKaW1wb3J0IHN5cwoKY29kZSA9IHIiIiIjaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y29tcGxleD4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHJhbmRvbT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dHVwbGU+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnVzaW5nIGludDY0ID0gbG9uZyBsb25nOwoKI2RlZmluZSBhbGwoXykgYmVnaW4oXyksIGVuZChfKQojZGVmaW5lIHJhbGwoXykgcmJlZ2luKF8pLCByZW5kKF8pCgppbnQ2NCBkcFszMDAwXVszMDAwXVs0XTsKCmludCBtYWluKCkgewogIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogIGNpbi50aWUobnVsbHB0cik7CgogIGludCByLCBjLCBrOyBjaW4gPj4gciA+PiBjID4+IGs7CiAgaW50IHZhbFtyXVtjXTsKICBmaWxsKHZhbFswXSwgdmFsW3JdLCAwKTsKICBmb3IgKGludCBpID0gMDsgaSA8IGs7ICsraSkgewogICAgaW50IHgsIHksIHo7IGNpbiA+PiB4ID4+IHkgPj4gejsKICAgIC0teDsgLS15OwogICAgdmFsW3hdW3ldID0gejsKICB9CgogIGlmICh2YWxbMF1bMF0gIT0gMCkgZHBbMF1bMF1bMV0gPSB2YWxbMF1bMF07CgogIGZvciAoaW50IGkgPSAwOyBpIDwgcjsgKytpKSB7CiAgICBmb3IgKGludCBqID0gMDsgaiA8IGM7ICsraikgewogICAgICBpZiAoaSA9PSAwICYmIGogPT0gMCkgY29udGludWU7CgogICAgICBpZiAodmFsW2ldW2pdICE9IDApIHsKICAgICAgICBpZiAoaSA+IDApIHsKICAgICAgICAgIGZvciAoaW50IGwgPSAwOyBsIDwgNDsgKytsKSBkcFtpXVtqXVswXSA9IG1heChkcFtpXVtqXVswXSwgZHBbaSAtIDFdW2pdW2xdKTsKICAgICAgICAgIGZvciAoaW50IGwgPSAwOyBsIDwgNDsgKytsKSBkcFtpXVtqXVsxXSA9IG1heChkcFtpXVtqXVsxXSwgZHBbaSAtIDFdW2pdW2xdICsgdmFsW2ldW2pdKTsKICAgICAgICB9CiAgICAgICAgaWYgKGogPiAwKSB7CiAgICAgICAgICBkcFtpXVtqXVswXSA9IG1heChkcFtpXVtqXVswXSwgZHBbaV1baiAtIDFdWzBdKTsKICAgICAgICAgIGZvciAoaW50IGwgPSAxOyBsIDwgNDsgKytsKSB7CiAgICAgICAgICAgIGRwW2ldW2pdW2xdID0gbWF4KHtkcFtpXVtqXVtsXSwgZHBbaV1baiAtIDFdW2xdLCBkcFtpXVtqIC0gMV1bbCAtIDFdICsgdmFsW2ldW2pdfSk7CiAgICAgICAgICB9CiAgICAgICAgfQogICAgICB9IGVsc2UgewogICAgICAgIGlmIChpID4gMCkgewogICAgICAgICAgZm9yIChpbnQgbCA9IDA7IGwgPCA0OyArK2wpIGRwW2ldW2pdWzBdID0gbWF4KGRwW2ldW2pdWzBdLCBkcFtpIC0gMV1bal1bbF0pOwogICAgICAgIH0KICAgICAgICBpZiAoaiA+IDApIHsKICAgICAgICAgIGZvciAoaW50IGwgPSAwOyBsIDwgNDsgKytsKSBkcFtpXVtqXVtsXSA9IG1heChkcFtpXVtqXVtsXSwgZHBbaV1baiAtIDFdW2xdKTsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICB9CgogIGludDY0IGFucyA9IDA7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCA0OyArK2kpIGFucyA9IG1heChhbnMsIGRwW3IgLSAxXVtjIC0gMV1baV0pOwogIGNvdXQgPDwgYW5zIDw8IGVuZGw7CgogIHJldHVybiAwOwp9CiIiIgoKd2l0aCBvcGVuKCdzb2wuY3BwJywgJ3cnKSBhcyBmOgogICAgZi53cml0ZShjb2RlKQoKc3VicHJvY2Vzcy5Qb3BlbihbJ2crKycsICctc3RkPWMrKzE3JywgJy1PMicsICdzb2wuY3BwJ10pLmNvbW11bmljYXRlKCkKc3VicHJvY2Vzcy5Qb3BlbihbJy4vYS5vdXQnXSwgc3RkaW49c3lzLnN0ZGluLCBzdGRvdXQ9c3lzLnN0ZG91dCkuY29tbXVuaWNhdGUoKQ=='))