package gcj2013.template;
import java.io.*;
import java.util.*;
import java.util.concurrent.*;
import java.math.*;
import static java.
lang.
Math.
*; import static java.
util.
Arrays.
*;
public class Template
implements Runnable { private static final char PROB = Template.class.getSimpleName().charAt(0);
private static final boolean isPractice = false;
private static final Mode mode = Mode.SAMPLE;
private static class Solver implements Callable<String> {
private static final double EPS = 1e-12;
private static final int INF = 1 << 20;
private static final int[] di = { -1, 0, 0, 1 };
private static final int[] dj = { 0, -1, 1, 0 };
// shared table
static {
// :TODO
}
// parse
public Solver(final Scanner sc) {
// :TODO
}
// solve
@Override
// :TODO
throw null;
}
}
// Template
@Override
public void run() {
try (final Scanner sc
= new Scanner
(System.
in)) { final List<Future<String>> list = new ArrayList<>();
final int T = sc.nextInt();
for (int i = 0; i < T; i++)
list.add(es.submit(new Solver(sc)));
for (int t = 1; t <= T; t++) {
debugf("Case #%s%n", t);
System.
out.
printf("Case #%s: %s%n", t, list.
get(t
- 1).
get()); }
debug("done.");
e.printStackTrace();
}
}
public static void main
(String...
args) { final Template t = new Template();
switch (mode) {
case SAMPLE:
t.run();
break;
case SMALL: {
String in
= PROB
+ "-small" + (isPractice
? "-practice" : "-attempt" + 0) + ".in"; String out
= PROB
+ "-small.out"; if (!isPractice)
for (int i
= 1; new File(PROB
+ "-small" + "-attempt" + i
+ ".in").
exists(); i
++) in = PROB + "-small" + "-attempt" + i + ".in";
try {
t.run();
e.printStackTrace();
}
break;
}
case SMALL_ALL: {
try {
if (!isPractice)
for (int i
= 0; new File(PROB
+ "-small" + "-attempt" + i
+ ".in").
exists(); i
++) { final String in
= PROB
+ "-small" + "-attempt" + i
+ ".in"; t.run();
}
else {
t.run();
}
e.printStackTrace();
}
break;
}
case LARGE: {
try {
final String in
= PROB
+ "-large" + (isPractice
? "-practice" : "") + ".in"; final String out
= PROB
+ "-large.out"; t.run();
e.printStackTrace();
}
break;
}
case LARGE1: {
try {
final String in
= PROB
+ "-large" + (isPractice
? "-practice" : "") + "-1.in"; final String out
= PROB
+ "-large-1.out"; t.run();
e.printStackTrace();
}
break;
}
case LARGE2: {
try {
final String in
= PROB
+ "-large" + (isPractice
? "-practice" : "") + "-2.in"; final String out
= PROB
+ "-large-2.out"; t.run();
e.printStackTrace();
}
break;
}
default:
throw null;
}
es.shutdown();
}
private static final int DEFAULT_PARARELL
= Runtime.
getRuntime().
availableProcessors() + 1; private static final ExecutorService es = Executors.newFixedThreadPool(DEFAULT_PARARELL);
private static enum Mode {
SAMPLE, SMALL, SMALL_ALL, LARGE, LARGE1, LARGE2
}
System.
err.
printf(format, os
); }
private static void debug
(Object...
os) { System.
err.
println(deepToString
(os
)); }
}
cGFja2FnZSBnY2oyMDEzLnRlbXBsYXRlOwoKaW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS51dGlsLmNvbmN1cnJlbnQuKjsKaW1wb3J0IGphdmEubWF0aC4qOwoKaW1wb3J0IHN0YXRpYyBqYXZhLmxhbmcuTWF0aC4qOwppbXBvcnQgc3RhdGljIGphdmEubGFuZy5DaGFyYWN0ZXIuKjsKaW1wb3J0IHN0YXRpYyBqYXZhLnV0aWwuQXJyYXlzLio7CmltcG9ydCBzdGF0aWMgamF2YS51dGlsLkNvbGxlY3Rpb25zLio7CmltcG9ydCBzdGF0aWMgamF2YS5tYXRoLkJpZ0ludGVnZXIuKjsKCnB1YmxpYyBjbGFzcyBUZW1wbGF0ZSBpbXBsZW1lbnRzIFJ1bm5hYmxlIHsKCXByaXZhdGUgc3RhdGljIGZpbmFsIGNoYXIgUFJPQiA9IFRlbXBsYXRlLmNsYXNzLmdldFNpbXBsZU5hbWUoKS5jaGFyQXQoMCk7Cglwcml2YXRlIHN0YXRpYyBmaW5hbCBib29sZWFuIGlzUHJhY3RpY2UgPSBmYWxzZTsKCXByaXZhdGUgc3RhdGljIGZpbmFsIE1vZGUgbW9kZSA9IE1vZGUuU0FNUExFOwoKCXByaXZhdGUgc3RhdGljIGNsYXNzIFNvbHZlciBpbXBsZW1lbnRzIENhbGxhYmxlPFN0cmluZz4gewoJCXByaXZhdGUgc3RhdGljIGZpbmFsIGRvdWJsZSBFUFMgPSAxZS0xMjsKCQlwcml2YXRlIHN0YXRpYyBmaW5hbCBpbnQgSU5GID0gMSA8PCAyMDsKCQlwcml2YXRlIHN0YXRpYyBmaW5hbCBpbnRbXSBkaSA9IHsgLTEsIDAsIDAsIDEgfTsKCQlwcml2YXRlIHN0YXRpYyBmaW5hbCBpbnRbXSBkaiA9IHsgMCwgLTEsIDEsIDAgfTsKCgkJLy8gc2hhcmVkIHRhYmxlCgkJc3RhdGljIHsKCQkJLy8gOlRPRE8KCQl9CgoJCS8vIHBhcnNlCgkJcHVibGljIFNvbHZlcihmaW5hbCBTY2FubmVyIHNjKSB7CgkJCS8vIDpUT0RPCgkJfQoKCQkvLyBzb2x2ZQoJCUBPdmVycmlkZQoJCXB1YmxpYyBTdHJpbmcgY2FsbCgpIHsKCQkJLy8gOlRPRE8KCQkJdGhyb3cgbnVsbDsKCQl9Cgl9CgoJLy8gVGVtcGxhdGUKCUBPdmVycmlkZQoJcHVibGljIHZvaWQgcnVuKCkgewoJCXRyeSAoZmluYWwgU2Nhbm5lciBzYyA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbikpIHsKCQkJZmluYWwgTGlzdDxGdXR1cmU8U3RyaW5nPj4gbGlzdCA9IG5ldyBBcnJheUxpc3Q8PigpOwoJCQlmaW5hbCBpbnQgVCA9IHNjLm5leHRJbnQoKTsKCQkJZm9yIChpbnQgaSA9IDA7IGkgPCBUOyBpKyspCgkJCQlsaXN0LmFkZChlcy5zdWJtaXQobmV3IFNvbHZlcihzYykpKTsKCQkJZm9yIChpbnQgdCA9IDE7IHQgPD0gVDsgdCsrKSB7CgkJCQlkZWJ1Z2YoIkNhc2UgIyVzJW4iLCB0KTsKCQkJCVN5c3RlbS5vdXQucHJpbnRmKCJDYXNlICMlczogJXMlbiIsIHQsIGxpc3QuZ2V0KHQgLSAxKS5nZXQoKSk7CgkJCX0KCQkJZGVidWcoImRvbmUuIik7CgkJfSBjYXRjaCAoRXhjZXB0aW9uIGUpIHsKCQkJZS5wcmludFN0YWNrVHJhY2UoKTsKCQl9Cgl9CgoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nLi4uIGFyZ3MpIHsKCQlmaW5hbCBUZW1wbGF0ZSB0ID0gbmV3IFRlbXBsYXRlKCk7CgkJc3dpdGNoIChtb2RlKSB7CgkJY2FzZSBTQU1QTEU6CgkJCXQucnVuKCk7CgkJCWJyZWFrOwoJCWNhc2UgU01BTEw6IHsKCQkJU3RyaW5nIGluID0gUFJPQiArICItc21hbGwiICsgKGlzUHJhY3RpY2UgPyAiLXByYWN0aWNlIiA6ICItYXR0ZW1wdCIgKyAwKSArICIuaW4iOwoJCQlTdHJpbmcgb3V0ID0gUFJPQiArICItc21hbGwub3V0IjsKCQkJaWYgKCFpc1ByYWN0aWNlKQoJCQkJZm9yIChpbnQgaSA9IDE7IG5ldyBGaWxlKFBST0IgKyAiLXNtYWxsIiArICItYXR0ZW1wdCIgKyBpICsgIi5pbiIpLmV4aXN0cygpOyBpKyspCgkJCQkJaW4gPSBQUk9CICsgIi1zbWFsbCIgKyAiLWF0dGVtcHQiICsgaSArICIuaW4iOwoJCQl0cnkgewoJCQkJU3lzdGVtLnNldEluKG5ldyBCdWZmZXJlZElucHV0U3RyZWFtKG5ldyBGaWxlSW5wdXRTdHJlYW0oaW4pKSk7CgkJCQlTeXN0ZW0uc2V0T3V0KG5ldyBQcmludFN0cmVhbShvdXQpKTsKCQkJCXQucnVuKCk7CgkJCX0gY2F0Y2ggKEV4Y2VwdGlvbiBlKSB7CgkJCQllLnByaW50U3RhY2tUcmFjZSgpOwoJCQkJU3lzdGVtLmV4aXQoMCk7CgkJCX0KCQkJYnJlYWs7CgkJfQoJCWNhc2UgU01BTExfQUxMOiB7CgkJCXRyeSB7CgkJCQlpZiAoIWlzUHJhY3RpY2UpCgkJCQkJZm9yIChpbnQgaSA9IDA7IG5ldyBGaWxlKFBST0IgKyAiLXNtYWxsIiArICItYXR0ZW1wdCIgKyBpICsgIi5pbiIpLmV4aXN0cygpOyBpKyspIHsKCQkJCQkJZmluYWwgU3RyaW5nIGluID0gUFJPQiArICItc21hbGwiICsgIi1hdHRlbXB0IiArIGkgKyAiLmluIjsKCQkJCQkJU3lzdGVtLnNldEluKG5ldyBCdWZmZXJlZElucHV0U3RyZWFtKG5ldyBGaWxlSW5wdXRTdHJlYW0oaW4pKSk7CgkJCQkJCXQucnVuKCk7CgkJCQkJfQoJCQkJZWxzZSB7CgkJCQkJU3lzdGVtLnNldEluKG5ldyBCdWZmZXJlZElucHV0U3RyZWFtKG5ldyBGaWxlSW5wdXRTdHJlYW0oUFJPQiArICItc21hbGwtcHJhY3RpY2UuaW4iKSkpOwoJCQkJCXQucnVuKCk7CgkJCQl9CgkJCX0gY2F0Y2ggKEV4Y2VwdGlvbiBlKSB7CgkJCQllLnByaW50U3RhY2tUcmFjZSgpOwoJCQkJU3lzdGVtLmV4aXQoMCk7CgkJCX0KCQkJYnJlYWs7CgkJfQoJCWNhc2UgTEFSR0U6IHsKCQkJdHJ5IHsKCQkJCWZpbmFsIFN0cmluZyBpbiA9IFBST0IgKyAiLWxhcmdlIiArIChpc1ByYWN0aWNlID8gIi1wcmFjdGljZSIgOiAiIikgKyAiLmluIjsKCQkJCWZpbmFsIFN0cmluZyBvdXQgPSBQUk9CICsgIi1sYXJnZS5vdXQiOwoJCQkJU3lzdGVtLnNldEluKG5ldyBCdWZmZXJlZElucHV0U3RyZWFtKG5ldyBGaWxlSW5wdXRTdHJlYW0oaW4pKSk7CgkJCQlTeXN0ZW0uc2V0T3V0KG5ldyBQcmludFN0cmVhbShvdXQpKTsKCQkJCXQucnVuKCk7CgkJCX0gY2F0Y2ggKEV4Y2VwdGlvbiBlKSB7CgkJCQllLnByaW50U3RhY2tUcmFjZSgpOwoJCQkJU3lzdGVtLmV4aXQoMCk7CgkJCX0KCQkJYnJlYWs7CgkJfQoJCWNhc2UgTEFSR0UxOiB7CgkJCXRyeSB7CgkJCQlmaW5hbCBTdHJpbmcgaW4gPSBQUk9CICsgIi1sYXJnZSIgKyAoaXNQcmFjdGljZSA/ICItcHJhY3RpY2UiIDogIiIpICsgIi0xLmluIjsKCQkJCWZpbmFsIFN0cmluZyBvdXQgPSBQUk9CICsgIi1sYXJnZS0xLm91dCI7CgkJCQlTeXN0ZW0uc2V0SW4obmV3IEJ1ZmZlcmVkSW5wdXRTdHJlYW0obmV3IEZpbGVJbnB1dFN0cmVhbShpbikpKTsKCQkJCVN5c3RlbS5zZXRPdXQobmV3IFByaW50U3RyZWFtKG91dCkpOwoJCQkJdC5ydW4oKTsKCQkJfSBjYXRjaCAoRXhjZXB0aW9uIGUpIHsKCQkJCWUucHJpbnRTdGFja1RyYWNlKCk7CgkJCQlTeXN0ZW0uZXhpdCgwKTsKCQkJfQoJCQlicmVhazsKCQl9CgkJY2FzZSBMQVJHRTI6IHsKCQkJdHJ5IHsKCQkJCWZpbmFsIFN0cmluZyBpbiA9IFBST0IgKyAiLWxhcmdlIiArIChpc1ByYWN0aWNlID8gIi1wcmFjdGljZSIgOiAiIikgKyAiLTIuaW4iOwoJCQkJZmluYWwgU3RyaW5nIG91dCA9IFBST0IgKyAiLWxhcmdlLTIub3V0IjsKCQkJCVN5c3RlbS5zZXRJbihuZXcgQnVmZmVyZWRJbnB1dFN0cmVhbShuZXcgRmlsZUlucHV0U3RyZWFtKGluKSkpOwoJCQkJU3lzdGVtLnNldE91dChuZXcgUHJpbnRTdHJlYW0ob3V0KSk7CgkJCQl0LnJ1bigpOwoJCQl9IGNhdGNoIChFeGNlcHRpb24gZSkgewoJCQkJZS5wcmludFN0YWNrVHJhY2UoKTsKCQkJCVN5c3RlbS5leGl0KDApOwoJCQl9CgkJCWJyZWFrOwoJCX0KCQlkZWZhdWx0OgoJCQl0aHJvdyBudWxsOwoJCX0KCQllcy5zaHV0ZG93bigpOwoJfQoKCXByaXZhdGUgc3RhdGljIGZpbmFsIGludCBERUZBVUxUX1BBUkFSRUxMID0gUnVudGltZS5nZXRSdW50aW1lKCkuYXZhaWxhYmxlUHJvY2Vzc29ycygpICsgMTsKCXByaXZhdGUgc3RhdGljIGZpbmFsIEV4ZWN1dG9yU2VydmljZSBlcyA9IEV4ZWN1dG9ycy5uZXdGaXhlZFRocmVhZFBvb2woREVGQVVMVF9QQVJBUkVMTCk7CgoJcHJpdmF0ZSBzdGF0aWMgZW51bSBNb2RlIHsKCQlTQU1QTEUsIFNNQUxMLCBTTUFMTF9BTEwsIExBUkdFLCBMQVJHRTEsIExBUkdFMgoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgZGVidWdmKFN0cmluZyBmb3JtYXQsIE9iamVjdC4uLiBvcykgewoJCVN5c3RlbS5lcnIucHJpbnRmKGZvcm1hdCwgb3MpOwoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgZGVidWcoT2JqZWN0Li4uIG9zKSB7CgkJU3lzdGVtLmVyci5wcmludGxuKGRlZXBUb1N0cmluZyhvcykpOwoJfQp9Cg==