import java.io.*;
import java.util.*;
public class Main {
public static void main
(String[] args
) { System.
out.
println("This is Fast Input Reader"); }
/*
* Don't see below
*/
static StringBuilder sb = new StringBuilder();
private int BUFFER_SIZE = 1 << 16;
private byte[] buffer = new byte[BUFFER_SIZE];
private int bufferPointer = 0, bytesRead = 0;
}
try {
e.printStackTrace();
}
}
private byte read() {
if (bufferPointer == bytesRead) {
bufferPointer = 0;
try {
bytesRead = rd.read(buffer, bufferPointer, BUFFER_SIZE);
e.printStackTrace();
}
if (bytesRead == -1) {
return -1;
}
}
return buffer[bufferPointer++];
}
public int nextInt() {
int number = 0;
int c = read();
while (c <= ' ') {
c = read();
}
boolean negative = (c == '-');
if (negative) {
c = read();
}
do {
number = number * 10 + (c - '0');
c = read();
} while (c >= '0' && c <= '9');
return negative ? -number : number;
}
public long nextLong() {
long number = 0L;
int c = read();
while (c <= ' ') {
c = read();
}
boolean negative = (c == '-');
if (negative) {
c = read();
}
do {
number = number * 10 + (c - '0');
c = read();
} while (c >= '0' && c <= '9');
return negative ? -number : number;
}
int c = read();
while (c <= ' ') {
c = read();
}
StringBuilder t = new StringBuilder();
do {
t.append((char) c);
c = read();
} while (c > ' ');
return t.toString();
}
int c = read();
while (c == '\n' || c == '\r') {
c = read();
}
StringBuilder t = new StringBuilder();
while (c != '\n' && c != '\r' && c != -1) {
t.append((char) c);
c = read();
}
return t.toString();
}
public double nextDouble() {
return Double.
parseDouble(next
()); }
public char nextChar() {
int c = read();
while (c <= ' ') {
c = read();
}
return (char) c;
}
}
}
aW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiVGhpcyBpcyBGYXN0IElucHV0IFJlYWRlciIpOwogICAgfQoKICAgIC8qCiAgICAgKiBEb24ndCBzZWUgYmVsb3cKICAgICAqLwogICAgc3RhdGljIFJlYWRlciBzYyA9IG5ldyBSZWFkZXIoKTsKICAgIHN0YXRpYyBTdHJpbmdCdWlsZGVyIHNiID0gbmV3IFN0cmluZ0J1aWxkZXIoKTsKICAgIHN0YXRpYyBSYW5kb20gcmQgPSBuZXcgUmFuZG9tKCk7CgogICAgc3RhdGljIGNsYXNzIFJlYWRlciB7CiAgICAgICAgcHJpdmF0ZSBpbnQgQlVGRkVSX1NJWkUgPSAxIDw8IDE2OwogICAgICAgIHByaXZhdGUgYnl0ZVtdIGJ1ZmZlciA9IG5ldyBieXRlW0JVRkZFUl9TSVpFXTsKICAgICAgICBwcml2YXRlIGludCBidWZmZXJQb2ludGVyID0gMCwgYnl0ZXNSZWFkID0gMDsKICAgICAgICBwcml2YXRlIElucHV0U3RyZWFtIHJkOwoKICAgICAgICBwdWJsaWMgUmVhZGVyKCkgewogICAgICAgICAgICB0aGlzLnJkID0gU3lzdGVtLmluOwogICAgICAgIH0KCiAgICAgICAgcHVibGljIFJlYWRlcihTdHJpbmcgbmFtZUZpbGUpIHsKICAgICAgICAgICAgdHJ5IHsKICAgICAgICAgICAgICAgIHRoaXMucmQgPSBuZXcgRmlsZUlucHV0U3RyZWFtKG5hbWVGaWxlKTsKICAgICAgICAgICAgfSBjYXRjaCAoRmlsZU5vdEZvdW5kRXhjZXB0aW9uIGUpIHsKICAgICAgICAgICAgICAgIGUucHJpbnRTdGFja1RyYWNlKCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHByaXZhdGUgYnl0ZSByZWFkKCkgewogICAgICAgICAgICBpZiAoYnVmZmVyUG9pbnRlciA9PSBieXRlc1JlYWQpIHsKICAgICAgICAgICAgICAgIGJ1ZmZlclBvaW50ZXIgPSAwOwogICAgICAgICAgICAgICAgdHJ5IHsKICAgICAgICAgICAgICAgICAgICBieXRlc1JlYWQgPSByZC5yZWFkKGJ1ZmZlciwgYnVmZmVyUG9pbnRlciwgQlVGRkVSX1NJWkUpOwogICAgICAgICAgICAgICAgfSBjYXRjaCAoSU9FeGNlcHRpb24gZSkgewogICAgICAgICAgICAgICAgICAgIGUucHJpbnRTdGFja1RyYWNlKCk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiAoYnl0ZXNSZWFkID09IC0xKSB7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIC0xOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIHJldHVybiBidWZmZXJbYnVmZmVyUG9pbnRlcisrXTsKICAgICAgICB9CgogICAgICAgIHB1YmxpYyBpbnQgbmV4dEludCgpIHsKICAgICAgICAgICAgaW50IG51bWJlciA9IDA7CiAgICAgICAgICAgIGludCBjID0gcmVhZCgpOwogICAgICAgICAgICB3aGlsZSAoYyA8PSAnICcpIHsKICAgICAgICAgICAgICAgIGMgPSByZWFkKCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgYm9vbGVhbiBuZWdhdGl2ZSA9IChjID09ICctJyk7CiAgICAgICAgICAgIGlmIChuZWdhdGl2ZSkgewogICAgICAgICAgICAgICAgYyA9IHJlYWQoKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBkbyB7CiAgICAgICAgICAgICAgICBudW1iZXIgPSBudW1iZXIgKiAxMCArIChjIC0gJzAnKTsKICAgICAgICAgICAgICAgIGMgPSByZWFkKCk7CiAgICAgICAgICAgIH0gd2hpbGUgKGMgPj0gJzAnICYmIGMgPD0gJzknKTsKICAgICAgICAgICAgcmV0dXJuIG5lZ2F0aXZlID8gLW51bWJlciA6IG51bWJlcjsKICAgICAgICB9CgogICAgICAgIHB1YmxpYyBsb25nIG5leHRMb25nKCkgewogICAgICAgICAgICBsb25nIG51bWJlciA9IDBMOwogICAgICAgICAgICBpbnQgYyA9IHJlYWQoKTsKICAgICAgICAgICAgd2hpbGUgKGMgPD0gJyAnKSB7CiAgICAgICAgICAgICAgICBjID0gcmVhZCgpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGJvb2xlYW4gbmVnYXRpdmUgPSAoYyA9PSAnLScpOwogICAgICAgICAgICBpZiAobmVnYXRpdmUpIHsKICAgICAgICAgICAgICAgIGMgPSByZWFkKCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZG8gewogICAgICAgICAgICAgICAgbnVtYmVyID0gbnVtYmVyICogMTAgKyAoYyAtICcwJyk7CiAgICAgICAgICAgICAgICBjID0gcmVhZCgpOwogICAgICAgICAgICB9IHdoaWxlIChjID49ICcwJyAmJiBjIDw9ICc5Jyk7CiAgICAgICAgICAgIHJldHVybiBuZWdhdGl2ZSA/IC1udW1iZXIgOiBudW1iZXI7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgU3RyaW5nIG5leHQoKSB7CiAgICAgICAgICAgIGludCBjID0gcmVhZCgpOwogICAgICAgICAgICB3aGlsZSAoYyA8PSAnICcpIHsKICAgICAgICAgICAgICAgIGMgPSByZWFkKCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgU3RyaW5nQnVpbGRlciB0ID0gbmV3IFN0cmluZ0J1aWxkZXIoKTsKICAgICAgICAgICAgZG8gewogICAgICAgICAgICAgICAgdC5hcHBlbmQoKGNoYXIpIGMpOwogICAgICAgICAgICAgICAgYyA9IHJlYWQoKTsKICAgICAgICAgICAgfSB3aGlsZSAoYyA+ICcgJyk7CiAgICAgICAgICAgIHJldHVybiB0LnRvU3RyaW5nKCk7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgU3RyaW5nIG5leHRMaW5lKCkgewogICAgICAgICAgICBpbnQgYyA9IHJlYWQoKTsKICAgICAgICAgICAgd2hpbGUgKGMgPT0gJ1xuJyB8fCBjID09ICdccicpIHsKICAgICAgICAgICAgICAgIGMgPSByZWFkKCk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgU3RyaW5nQnVpbGRlciB0ID0gbmV3IFN0cmluZ0J1aWxkZXIoKTsKICAgICAgICAgICAgd2hpbGUgKGMgIT0gJ1xuJyAmJiBjICE9ICdccicgJiYgYyAhPSAtMSkgewogICAgICAgICAgICAgICAgdC5hcHBlbmQoKGNoYXIpIGMpOwogICAgICAgICAgICAgICAgYyA9IHJlYWQoKTsKICAgICAgICAgICAgfQogICAgICAgICAgICByZXR1cm4gdC50b1N0cmluZygpOwogICAgICAgIH0KCiAgICAgICAgcHVibGljIGRvdWJsZSBuZXh0RG91YmxlKCkgewogICAgICAgICAgICByZXR1cm4gRG91YmxlLnBhcnNlRG91YmxlKG5leHQoKSk7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgY2hhciBuZXh0Q2hhcigpIHsKICAgICAgICAgICAgaW50IGMgPSByZWFkKCk7CiAgICAgICAgICAgIHdoaWxlIChjIDw9ICcgJykgewogICAgICAgICAgICAgICAgYyA9IHJlYWQoKTsKICAgICAgICAgICAgfQogICAgICAgICAgICByZXR1cm4gKGNoYXIpIGM7CiAgICAgICAgfQogICAgfQp9Cg==