/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
{
InputReader in
=new InputReader
(System.
in); //code from here. Use this InputReader just as you use Scanner.
// and use the out just as you use System.out
out.flush();
}
}
class InputReader{
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
this.stream = stream;
}
public int read() {
if (numChars == -1)
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
}
public long nextLong() {
return Long.
parseLong(next
()); }
return next();
}
int c = read();
while (isSpaceChar(c))
c = read();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
int c = read();
while (c != '\n' && c != -1) {
if (c != '\r')
buf.appendCodePoint(c);
c = read();
}
return buf.toString();
}
public int peek() {
if (numChars == -1)
return -1;
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
return -1;
}
if (numChars <= 0)
return -1;
}
return buf[curChar];
}
public boolean hasNext() {
int value;
while (isSpaceChar(value = peek()) && value != -1)
read();
return value != -1;
}
private boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KcHVibGljIGNsYXNzIE1haW4KewoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBqYXZhLmxhbmcuRXhjZXB0aW9uCgl7CgkJSW5wdXRSZWFkZXIgaW49bmV3IElucHV0UmVhZGVyKFN5c3RlbS5pbik7CgkJUHJpbnRXcml0ZXIgb3V0PW5ldyBQcmludFdyaXRlcihTeXN0ZW0ub3V0KTsKCQkvL2NvZGUgZnJvbSBoZXJlLiBVc2UgdGhpcyBJbnB1dFJlYWRlciBqdXN0IGFzIHlvdSB1c2UgU2Nhbm5lci4KCQkvLyBhbmQgdXNlIHRoZSBvdXQganVzdCBhcyB5b3UgdXNlIFN5c3RlbS5vdXQKCQkKCQkKCQkKCQkKCQlvdXQuZmx1c2goKTsKCX0KfQoKY2xhc3MgSW5wdXRSZWFkZXJ7CgkgICAgICAgIHByaXZhdGUgSW5wdXRTdHJlYW0gc3RyZWFtOwoJICAgICAgICBwcml2YXRlIGJ5dGVbXSBidWYgPSBuZXcgYnl0ZVsxMDI0XTsKCSAgICAgICAgcHJpdmF0ZSBpbnQgY3VyQ2hhcjsKCSAgICAgICAgcHJpdmF0ZSBpbnQgbnVtQ2hhcnM7CgkgCgkgICAgICAgIHB1YmxpYyBJbnB1dFJlYWRlcihJbnB1dFN0cmVhbSBzdHJlYW0pIHsKCSAgICAgICAgICAgIHRoaXMuc3RyZWFtID0gc3RyZWFtOwoJICAgICAgICB9CgkgCgkgICAgICAgIHB1YmxpYyBpbnQgcmVhZCgpIHsKCSAgICAgICAgICAgIGlmIChudW1DaGFycyA9PSAtMSkKCSAgICAgICAgICAgICAgICB0aHJvdyBuZXcgVW5rbm93bkVycm9yKCk7CgkgICAgICAgICAgICBpZiAoY3VyQ2hhciA+PSBudW1DaGFycykgewoJICAgICAgICAgICAgICAgIGN1ckNoYXIgPSAwOwoJICAgICAgICAgICAgICAgIHRyeSB7CgkgICAgICAgICAgICAgICAgICAgIG51bUNoYXJzID0gc3RyZWFtLnJlYWQoYnVmKTsKCSAgICAgICAgICAgICAgICB9IGNhdGNoIChJT0V4Y2VwdGlvbiBlKSB7CgkgICAgICAgICAgICAgICAgICAgIHRocm93IG5ldyBVbmtub3duRXJyb3IoKTsKCSAgICAgICAgICAgICAgICB9CgkgICAgICAgICAgICAgICAgaWYgKG51bUNoYXJzIDw9IDApCgkgICAgICAgICAgICAgICAgICAgIHJldHVybiAtMTsKCSAgICAgICAgICAgIH0KCSAgICAgICAgICAgIHJldHVybiBidWZbY3VyQ2hhcisrXTsKCSAgICAgICAgfQoJIAoJIAoJICAgICAgICBwdWJsaWMgaW50IG5leHRJbnQoKSB7CgkgICAgICAgICAgICByZXR1cm4gSW50ZWdlci5wYXJzZUludChuZXh0KCkpOwoJICAgICAgICB9CgkgCgkgICAgICAgIHB1YmxpYyBsb25nIG5leHRMb25nKCkgewoJICAgICAgICAgICAgcmV0dXJuIExvbmcucGFyc2VMb25nKG5leHQoKSk7CgkgICAgICAgIH0KCSAKCSAgICAgICAgcHVibGljIFN0cmluZyBuZXh0U3RyaW5nKCkgewoJICAgICAgICAgICAgcmV0dXJuIG5leHQoKTsKCSAgICAgICAgfQoJIAoJICAgICAgICBwdWJsaWMgU3RyaW5nIG5leHQoKSB7CgkgICAgICAgICAgICBpbnQgYyA9IHJlYWQoKTsKCSAgICAgICAgICAgIHdoaWxlIChpc1NwYWNlQ2hhcihjKSkKCSAgICAgICAgICAgICAgICBjID0gcmVhZCgpOwoJICAgICAgICAgICAgU3RyaW5nQnVmZmVyIHJlcyA9IG5ldyBTdHJpbmdCdWZmZXIoKTsKCSAgICAgICAgICAgIGRvIHsKCSAgICAgICAgICAgICAgICByZXMuYXBwZW5kQ29kZVBvaW50KGMpOwoJICAgICAgICAgICAgICAgIGMgPSByZWFkKCk7CgkgICAgICAgICAgICB9IHdoaWxlICghaXNTcGFjZUNoYXIoYykpOwoJIAoJICAgICAgICAgICAgcmV0dXJuIHJlcy50b1N0cmluZygpOwoJICAgICAgICB9CgkgCgkgICAgICAgIHB1YmxpYyBTdHJpbmcgbmV4dExpbmUoKSB7CgkgICAgICAgICAgICBTdHJpbmdCdWZmZXIgYnVmID0gbmV3IFN0cmluZ0J1ZmZlcigpOwoJICAgICAgICAgICAgaW50IGMgPSByZWFkKCk7CgkgICAgICAgICAgICB3aGlsZSAoYyAhPSAnXG4nICYmIGMgIT0gLTEpIHsKCSAgICAgICAgICAgICAgICBpZiAoYyAhPSAnXHInKQoJICAgICAgICAgICAgICAgICAgICBidWYuYXBwZW5kQ29kZVBvaW50KGMpOwoJICAgICAgICAgICAgICAgIGMgPSByZWFkKCk7CgkgICAgICAgICAgICB9CgkgICAgICAgICAgICByZXR1cm4gYnVmLnRvU3RyaW5nKCk7CgkgICAgICAgIH0KCQkJIHB1YmxpYyBpbnQgcGVlaygpIHsKCSAgICAgICAgICAgIGlmIChudW1DaGFycyA9PSAtMSkKCSAgICAgICAgICAgICAgICByZXR1cm4gLTE7CgkgICAgICAgICAgICBpZiAoY3VyQ2hhciA+PSBudW1DaGFycykgewoJICAgICAgICAgICAgICAgIGN1ckNoYXIgPSAwOwoJICAgICAgICAgICAgICAgIHRyeSB7CgkgICAgICAgICAgICAgICAgICAgIG51bUNoYXJzID0gc3RyZWFtLnJlYWQoYnVmKTsKCSAgICAgICAgICAgICAgICB9IGNhdGNoIChJT0V4Y2VwdGlvbiBlKSB7CgkgICAgICAgICAgICAgICAgICAgIHJldHVybiAtMTsKCSAgICAgICAgICAgICAgICB9CgkgICAgICAgICAgICAgICAgaWYgKG51bUNoYXJzIDw9IDApCgkgICAgICAgICAgICAgICAgICAgIHJldHVybiAtMTsKCSAgICAgICAgICAgIH0KCSAgICAgICAgICAgIHJldHVybiBidWZbY3VyQ2hhcl07CgkgICAgICAgIH0KCSAgICAgIAoJICAgICAgICBwdWJsaWMgYm9vbGVhbiBoYXNOZXh0KCkgewoJICAgICAgICAgICAgaW50IHZhbHVlOwoJICAgICAgICAgICAgd2hpbGUgKGlzU3BhY2VDaGFyKHZhbHVlID0gcGVlaygpKSAmJiB2YWx1ZSAhPSAtMSkKCSAgICAgICAgICAgICAgICByZWFkKCk7CgkgICAgICAgICAgICByZXR1cm4gdmFsdWUgIT0gLTE7CgkgICAgICAgIH0KCSAKCSAgICAgICAgcHJpdmF0ZSBib29sZWFuIGlzU3BhY2VDaGFyKGludCBjKSB7CgkgICAgICAgICAgICByZXR1cm4gYyA9PSAnICcgfHwgYyA9PSAnXG4nIHx8IGMgPT0gJ1xyJyB8fCBjID09ICdcdCcgfHwgYyA9PSAtMTsKCSAgICAgICAgfQoJICAgIH0=