結果
| 問題 | No.5015 Escape from Labyrinth |
| ユーザー |
 Yu_212
|
| 提出日時 | 2023-04-16 18:23:24 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 2,821 ms / 3,000 ms |
| コード長 | 26,576 bytes |
| コンパイル時間 | 3,932 ms |
| コンパイル使用メモリ | 87,636 KB |
| 実行使用メモリ | 72,680 KB |
| スコア | 162,090 |
| 最終ジャッジ日時 | 2023-04-16 18:28:21 |
| 合計ジャッジ時間 | 289,649 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,777 ms
70,572 KB |
| testcase_01 | AC | 2,746 ms
69,900 KB |
| testcase_02 | AC | 2,746 ms
70,052 KB |
| testcase_03 | AC | 2,718 ms
70,156 KB |
| testcase_04 | AC | 2,706 ms
70,328 KB |
| testcase_05 | AC | 2,764 ms
70,316 KB |
| testcase_06 | AC | 2,730 ms
70,140 KB |
| testcase_07 | AC | 2,728 ms
70,436 KB |
| testcase_08 | AC | 2,719 ms
70,372 KB |
| testcase_09 | AC | 2,690 ms
70,192 KB |
| testcase_10 | AC | 2,773 ms
70,584 KB |
| testcase_11 | AC | 2,751 ms
70,488 KB |
| testcase_12 | AC | 2,727 ms
69,720 KB |
| testcase_13 | AC | 2,752 ms
70,352 KB |
| testcase_14 | AC | 2,720 ms
70,144 KB |
| testcase_15 | AC | 2,765 ms
70,260 KB |
| testcase_16 | AC | 2,756 ms
70,824 KB |
| testcase_17 | AC | 2,757 ms
70,532 KB |
| testcase_18 | AC | 2,735 ms
70,316 KB |
| testcase_19 | AC | 2,728 ms
70,556 KB |
| testcase_20 | AC | 2,751 ms
70,512 KB |
| testcase_21 | AC | 2,760 ms
70,048 KB |
| testcase_22 | AC | 2,740 ms
70,212 KB |
| testcase_23 | AC | 2,759 ms
70,084 KB |
| testcase_24 | AC | 2,737 ms
70,736 KB |
| testcase_25 | AC | 2,811 ms
70,784 KB |
| testcase_26 | AC | 2,757 ms
70,508 KB |
| testcase_27 | AC | 2,772 ms
70,240 KB |
| testcase_28 | AC | 2,733 ms
68,192 KB |
| testcase_29 | AC | 2,721 ms
69,980 KB |
| testcase_30 | AC | 2,808 ms
70,316 KB |
| testcase_31 | AC | 2,739 ms
70,184 KB |
| testcase_32 | AC | 2,768 ms
70,688 KB |
| testcase_33 | AC | 2,732 ms
70,548 KB |
| testcase_34 | AC | 2,724 ms
70,624 KB |
| testcase_35 | AC | 2,760 ms
70,040 KB |
| testcase_36 | AC | 2,758 ms
70,192 KB |
| testcase_37 | AC | 2,799 ms
70,760 KB |
| testcase_38 | AC | 2,732 ms
70,428 KB |
| testcase_39 | AC | 2,749 ms
70,500 KB |
| testcase_40 | AC | 2,749 ms
70,208 KB |
| testcase_41 | AC | 2,751 ms
70,172 KB |
| testcase_42 | AC | 2,739 ms
69,976 KB |
| testcase_43 | AC | 2,723 ms
70,832 KB |
| testcase_44 | AC | 2,710 ms
70,396 KB |
| testcase_45 | AC | 2,749 ms
70,340 KB |
| testcase_46 | AC | 2,740 ms
70,508 KB |
| testcase_47 | AC | 2,741 ms
70,556 KB |
| testcase_48 | AC | 2,730 ms
72,072 KB |
| testcase_49 | AC | 2,713 ms
70,248 KB |
| testcase_50 | AC | 2,821 ms
70,520 KB |
| testcase_51 | AC | 2,749 ms
70,360 KB |
| testcase_52 | AC | 2,738 ms
70,404 KB |
| testcase_53 | AC | 2,735 ms
70,528 KB |
| testcase_54 | AC | 2,743 ms
70,416 KB |
| testcase_55 | AC | 2,773 ms
70,424 KB |
| testcase_56 | AC | 2,760 ms
70,480 KB |
| testcase_57 | AC | 2,743 ms
70,380 KB |
| testcase_58 | AC | 2,722 ms
70,420 KB |
| testcase_59 | AC | 2,715 ms
69,976 KB |
| testcase_60 | AC | 2,740 ms
70,624 KB |
| testcase_61 | AC | 2,759 ms
70,092 KB |
| testcase_62 | AC | 2,754 ms
70,524 KB |
| testcase_63 | AC | 2,722 ms
70,672 KB |
| testcase_64 | AC | 2,753 ms
70,512 KB |
| testcase_65 | AC | 2,778 ms
70,532 KB |
| testcase_66 | AC | 2,769 ms
70,460 KB |
| testcase_67 | AC | 2,743 ms
70,328 KB |
| testcase_68 | AC | 2,746 ms
70,092 KB |
| testcase_69 | AC | 2,708 ms
70,028 KB |
| testcase_70 | AC | 2,750 ms
70,384 KB |
| testcase_71 | AC | 2,766 ms
70,124 KB |
| testcase_72 | AC | 2,762 ms
70,516 KB |
| testcase_73 | AC | 2,746 ms
70,300 KB |
| testcase_74 | AC | 2,733 ms
70,500 KB |
| testcase_75 | AC | 2,755 ms
70,744 KB |
| testcase_76 | AC | 2,760 ms
70,200 KB |
| testcase_77 | AC | 2,734 ms
70,236 KB |
| testcase_78 | AC | 2,759 ms
70,376 KB |
| testcase_79 | AC | 2,721 ms
70,188 KB |
| testcase_80 | AC | 2,751 ms
70,208 KB |
| testcase_81 | AC | 2,730 ms
69,896 KB |
| testcase_82 | AC | 2,758 ms
70,112 KB |
| testcase_83 | AC | 2,772 ms
70,544 KB |
| testcase_84 | AC | 2,723 ms
70,008 KB |
| testcase_85 | AC | 2,763 ms
70,128 KB |
| testcase_86 | AC | 2,751 ms
70,352 KB |
| testcase_87 | AC | 2,757 ms
70,648 KB |
| testcase_88 | AC | 2,719 ms
70,596 KB |
| testcase_89 | AC | 2,722 ms
72,680 KB |
| testcase_90 | AC | 2,753 ms
70,388 KB |
| testcase_91 | AC | 2,740 ms
70,648 KB |
| testcase_92 | AC | 2,751 ms
70,468 KB |
| testcase_93 | AC | 2,732 ms
68,504 KB |
| testcase_94 | AC | 2,732 ms
70,896 KB |
| testcase_95 | AC | 2,747 ms
70,364 KB |
| testcase_96 | AC | 2,756 ms
70,408 KB |
| testcase_97 | AC | 2,747 ms
70,840 KB |
| testcase_98 | AC | 2,731 ms
70,320 KB |
| testcase_99 | AC | 2,720 ms
70,164 KB |
ソースコード
import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;
public class Main {
static boolean isLocal;
Random rand = new Random();
In in = new In(System.in);
PrintStream out = System.out;
long inf = 0x1fffffffffffffffL;
int iinf = 0x3fffffff;
long startTime;
public static final int N = 60;
public int D;
public static final int H = 1500;
public int M;
public int J;
public char[] grid;
public Pos[] ps;
public int[] ds;
public Pos[] jps;
int[][] distances;
int[][] beam = new int[60][N * N];
int[] avgWait = new int[N * N];
int[] jid = new int[N * N];
public static final String[] ss = {"M L", "M U", "M R", "M D", "S"};
long solve(int seed) {
startTime = System.currentTimeMillis();
in();
distances = new int[J+3][J+3];
for (int i = 0; i < J + 3; i++) {
Arrays.fill(distances[i], iinf);
}
for (int i = 0; i < M; i++) {
for (int d = 0; d < 4; d++) {
Pos cur = ps[i];
while (true) {
cur = cur.moved(d);
if (cur == null || grid[cur.z] == '#') {
break;
}
for (int j = 0; j < 60; j += ds[i]) {
beam[j][cur.z]++;
}
}
}
}
for (int i = 0; i < N * N; i++) {
int c = 1;
for (int j = 0; j < 60; j++) {
if (beam[j][i] > 0) {
c++;
} else {
c = 1;
}
avgWait[i] += c;
}
}
for (int i = 0; i < J + 3; i++) {
calcDist(i);
}
// BitSet visited = new BitSet(J + 3);
// visited.set(J);
// visited.set(J + 1);
// visited.set(J + 2);
// List<Integer> routes = new ArrayList<>();
// routes.add(J);
// routes.add(J + 1);
// routes.add(J + 2);
// int dsum = distances[J][J+1] + distances[J+1][J+2];
// int c = 0;
// while (elapsed() < 2000) {
// int p;
// do {
// p = rand.next(0, J);
// } while (visited.get(p));
// int bi = -1;
// int bd = iinf;
// for (int i = 1; i < routes.size(); i++) {
// int f = routes.get(i - 1);
// int t = routes.get(i);
// int diff = distances[f][p] + distances[p][t] - distances[f][t];
// if (bd > diff) {
// bd = diff;
// bi = i;
// }
// }
// if (bi == -1) {
// continue;
// }
//// debug(p, bi, bd, dsum);
// if (routes.size() >= 200) {
// break;
// }
//// if (dsum + bd * MUL[D] >= 60 * 500) {
////// c++;
////// if (c >= 100) {
////// break;
////// } else {
////// continue;
////// }
//// continue;
//// }
// visited.set(p);
// dsum += bd;
// routes.add(bi, p);
// }
debug("?", elapsed());
State result = annealing(new State(), 180*10, 180, 2500);
List<Integer> routes = result.routes;
debug("?", elapsed());
Pos p = jps[J];
int tt = 0;
int ds1 = 0;
int ds2 = 0;
totalCost = 0;
List<Result> results = new ArrayList<>();
BitSet aa = new BitSet(J);
for (int i = 1; i < routes.size(); i++) {
Result res = route(jps[routes.get(i - 1)], jps[routes.get(i)], tt);
// debug(distances[routes.get(i - 1)][routes.get(i)], res.damage * 60);
ds1 += distances[routes.get(i - 1)][routes.get(i)];
ds2 += res.damage;
// debug(p, res.from, res.to, res.damage, (tt+res.time)%60);
results.add(res);
tt = (tt + res.time) % 60;
p = res.to;
if (i > 1 && aa.get(routes.get(i - 1))) {
debug("!!");
throw new RuntimeException();
}
aa.set(routes.get(i - 1));
}
debug(D, result.dsum, ds1, result.dsum/60, ds1/60, ds2, ds2*60./result.dsum);
if (ds2 >= 1500) {
throw new RuntimeException();
// debug("!!!!");
// p = jps[J];
// tt = 0;
// int dm = 0;
// for (Result res : results) {
// if (res.from == jps[J + 1]) {
// Result v = route(res.from, jps[J + 2], tt);
// v.out(p, tt);
// break;
// }
// dm += res.damage;
// res.out(p, tt);
// tt = (tt + res.time) % 60;
// p = res.to;
// }
} else {
p = jps[J];
tt = 0;
for (Result res : results) {
res.out(p, tt);
tt = (tt + res.time) % 60;
p = res.to;
}
}
debug(ds2, totalCost, routes.size() * 10);
return routes.size() * 10L;
// List<Result> routes = new ArrayList<>();
// routes.add(route(jps[J], jps[J + 1], 0));
// routes.add(route(jps[J + 1], jps[J + 2], routes.get(0).time));
// int dsum = routes.get(0).damage + routes.get(1).damage;
// while (true) {
// int p;
// do {
// p = rand.next(0, J);
// } while (visited.get(p));
// int tt = 0;
// int bi = 0;
// int bd = iinf;
// Result br1 = null, br2 = null;
// for (int i = 0; i < routes.size(); i++) {
// Result r = routes.get(i);
// Result r1 = route(r.from, jps[p], tt);
// Result r2 = route(jps[p], r.to, (tt + r.time) % 60);
// int diff = r1.damage + r2.damage - r.damage;
// if (bd > diff) {
// bd = diff;
// bi = i;
// br1 = r1;
// br2 = r2;
// }
// tt = (tt + r.time) % 60;
// }
// debug(p, bi, bd, dsum);
// if (dsum + bd >= 700) {
// break;
// }
// visited.set(p);
// dsum += bd;
// routes.set(bi, br1);
// routes.add(bi + 1, br2);
// }
// Pos p = jps[J];
// int tt = 0;
// for (Result res : routes) {
// debug(p, res.from, res.to);
// res.out(p, tt);
// tt = (tt + res.time) % 60;
// p = res.to;
// }
// visited.set(J + 2);
// visited.set(J);
// tt = moveTo(J, J+1, tt, visited);
// visited.clear(J + 2);
// tt = moveTo(J+1, J+2, tt, visited);
}
//1678
int totalCost = 0;
// int moveTo(int s, int g, int tt, BitSet visited) {
// int cur = s;
// int ds = 0;
// while (cur != g) {
// int md = iinf;
// int mi = -1;
// for (int i = 0; i < J + 3; i++) {
// if (visited.get(i)) {
// continue;
// }
//// debug(i, cur, jps[i].dist(jps[g]), distances[cur * (J + 3) + i]);
// int d = distances[cur * (J + 3) + i] + jps[i].dist(jps[g]) * 50;
// if (md > d) {
// md = d;
// mi = i;
// }
// }
// ds += distances[cur * (J + 3) + mi];
// visited.set(mi);
// tt = moveStraight(cur, mi, tt);
// cur = mi;
// }
// debug(ds, totalCost);
// return tt;
// }
public static final double[] MUL = {0, 0, 0, 1.25, 1.33, 1.4, 1.6, 1.8};
class State {
BitSet visited = new BitSet(J + 3);
List<Integer> routes = new ArrayList<>();
int dsum;
double score;
boolean hasScore;
State prevCopy;
State() {
visited.set(J);
visited.set(J + 1);
visited.set(J + 2);
routes.add(J);
routes.add(J + 1);
routes.add(J + 2);
dsum = distances[J][J+1] + distances[J+1][J+2];
}
State(State prev) {
this.visited = (BitSet)prev.visited.clone();
this.routes = new ArrayList<>(prev.routes);
this.dsum = prev.dsum;
this.score = prev.score;
this.hasScore = true;
}
int real() {
int damage = 0;
int tt = 0;
for (int i = 1; i < routes.size(); i++) {
Result res = route(jps[routes.get(i - 1)], jps[routes.get(i)], tt);
// debug(distances[routes.get(i - 1)][routes.get(i)], res.damage * 60);
damage += res.damage;
// debug(p, res.from, res.to, res.damage);
tt = (tt + res.time) % 60;
}
return damage;
}
State rollback() {
return prevCopy;
}
int neighbor0(double stage) {
while (true) {
int p;
do {
p = rand.next(0, J);
} while (visited.get(p));
int bi = -1;
int bd = iinf;
for (int i = 1; i < routes.size(); i++) {
int f = routes.get(i - 1);
int t = routes.get(i);
int diff = distances[f][p] + distances[p][t] - distances[f][t];
if (bd > diff) {
bd = diff;
bi = i;
}
}
if (bi == -1) {
continue;
}
visited.set(p);
dsum += bd;
routes.add(bi, p);
score = calcScore(0);
break;
}
return 0;
}
int neighbor1(double stage) {
int bd = -iinf;
int bp = 0;
for (int p = 1; p + 1 < routes.size(); p++) {
int f = routes.get(p - 1);
int t = routes.get(p + 1);
int r = routes.get(p);
if (r >= J) {
continue;
}
int diff = distances[f][r] + distances[r][t] - distances[f][t];
if (bd < diff) {
bd = diff;
bp = p;
}
}
visited.clear(routes.get(bp));
dsum -= bd;
routes.remove(bp);
score = calcScore(0);
return 1;
}
int neighbor(double stage, double rs) {
hasScore = false;
prevCopy = copy();
if (routes.size() >= 60 && rand.next(3) == 0 || dsum * MUL[D] >= 60 * 1000 * rs) {
// debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 1);
return neighbor1(stage);
} else {
// debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 0);
return neighbor0(stage);
}
}
State copy() {
return new State(this);
}
double getScore(double stage) {
if (!hasScore) {
score = calcScore(stage);
hasScore = true;
}
return score;
}
double calcScore(double stage) {
double score = (routes.size() - 3) * 180*5 - dsum * MUL[D];
return score;
}
long realScore() {
int score = 0;
return score;
}
}
State annealing(State state, double startTemp, double endTemp, long timeLimit) {
State bestState = state.copy();
double bestScore = state.getScore(0);
int itr = 0;
int rb = 0;
int c0 = 0;
double rs = 1;
boolean calc = false;
while (true) {
long nowTime = System.currentTimeMillis() - startTime;
if (nowTime >= timeLimit) {
break;
}
double stage = (double)nowTime / timeLimit;
if (stage > 0.95 && !calc) {
calc = true;
rs = 1300. / state.real();
debug("??", rs);
}
itr++;
double prevScore = state.getScore(stage);
double temp = startTemp + (endTemp - startTemp) * nowTime / timeLimit;
double thres = prevScore + rand.nextLog() * temp;
int nid = state.neighbor(stage, rs);
if (nid == -1) {
continue;
}
if (nid == 0) {
c0++;
}
if (bestScore < state.getScore(stage)) {
bestScore = state.getScore(stage);
bestState = state.copy();
}
if (state.getScore(stage) <= thres) {
state = state.rollback();
rb++;
}
}
debug(itr, rb, c0);
return bestState;
}
class Result {
List<Integer> route;
int damage;
int time;
Pos from;
Pos to;
public Result(List<Integer> route, int damage, Pos from, Pos to) {
this.route = route;
this.damage = damage;
this.time = route.size() % 60;
this.from = from;
this.to = to;
}
public void out(Pos p, int tt) {
for (int v : route) {
if (v < 4) p = p.moved(v);
tt = (tt + 1) % 60;
totalCost += D * beam[tt][p.z];
totalCost++;
out.println(ss[v]);
}
}
}
Result route(Pos s, Pos g, int tt) {
class S {
private final Pos p;
private final int t;
private final int d;
public S(Pos p, int t, int d) {
this.p = p;
this.t = t;
this.d = d;
}
}
PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
queue.add(new S(s, tt, 0));
int[][] dist = new int[60][N * N];
int[][] prev = new int[60][N * N];
for (int i = 0; i < 60; i++) {
Arrays.fill(dist[i], iinf);
Arrays.fill(prev[i], -1);
}
dist[tt][s.z] = 0;
while (!queue.isEmpty()) {
S v = queue.remove();
if (dist[v.t][v.p.z] < v.d) {
continue;
}
if (v.p.z == g.z) {
List<Integer> route = new ArrayList<>();
Pos cur = v.p;
int ct = v.t;
int damage = dist[ct][cur.z];
while (prev[ct][cur.z] != -1) {
route.add(prev[ct][cur.z]);
if (prev[ct][cur.z] < 4) {
cur = cur.moved((prev[ct][cur.z] + 2) % 4);
}
ct = (ct + 59) % 60;
}
Collections.reverse(route);
return new Result(route, damage, s, g);
}
int nt = (v.t + 1) % 60;
for (int d = 0; d < 4; d++) {
Pos q = v.p.moved(d);
if (q == null || grid[q.z] == '#') {
continue;
}
int cost = dist[v.t][v.p.z] + 1 + beam[nt][q.z] * D;
if (dist[nt][q.z] > cost) {
dist[nt][q.z] = cost;
prev[nt][q.z] = d;
queue.add(new S(q, nt, cost));
}
}
int cost = dist[v.t][v.p.z] + 1 + beam[nt][v.p.z] * D;
if (dist[nt][v.p.z] > cost) {
dist[nt][v.p.z] = cost;
prev[nt][v.p.z] = 4;
queue.add(new S(v.p, nt, cost));
}
}
throw new RuntimeException();
}
void calcDist(int s) {
class S {
private final Pos p;
private final int d;
public S(Pos p, int d) {
this.p = p;
this.d = d;
}
}
PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
queue.add(new S(jps[s], 0));
int[] dist = new int[N * N];
Arrays.fill(dist, iinf);
dist[jps[s].z] = 0;
while (!queue.isEmpty()) {
S v = queue.remove();
if (dist[v.p.z] < v.d) {
continue;
}
if (jid[v.p.z] != -1) {
distances[s][jid[v.p.z]] = v.d;
}
for (int d = 0; d < 4; d++) {
Pos q = v.p.moved(d);
if (q == null || grid[q.z] == '#') {
continue;
}
int cost = dist[v.p.z] + avgWait[q.z];
if (dist[q.z] > cost) {
dist[q.z] = cost;
queue.add(new S(q, cost));
}
}
}
}
void in() {
in.nextInt();
D = in.nextInt();
in.nextInt();
grid = new char[N * N];
int jc = 0;
for (int i = 0; i < N; i++) {
char[] s = in.nextCharArray();
for (int j = 0; j < N; j++) {
grid[i * N + j] = s[j];
if (grid[i * N + j] == 'J') {
jc++;
}
}
}
M = in.nextInt();
J = jc;
jps = new Pos[J + 3];
ps = new Pos[M];
ds = new int[M];
for (int i = 0; i < M; i++) {
int y = in.nextInt();
int x = in.nextInt();
int d = in.nextInt();
ps[i] = pos(x, y);
ds[i] = d;
}
jc = 0;
Arrays.fill(jid, -1);
for (int i = 0; i < N * N; i++) {
if (grid[i] == 'S') {
jps[J] = pos(i);
jid[i] = J;
grid[i] = '.';
} else if (grid[i] == 'K') {
jps[J + 1] = pos(i);
jid[i] = J + 1;
grid[i] = '.';
} else if (grid[i] == 'G') {
jps[J + 2] = pos(i);
jid[i] = J + 2;
grid[i] = '.';
} else if (grid[i] == 'J') {
jid[i] = jc;
jps[jc++] = pos(i);
} else if (grid[i] == 'E') {
grid[i] = '#';
}
}
}
static Pos pos(int x, int y) {
return Pos.instances[y * N + x];
}
static Pos pos(int z) {
return Pos.instances[z];
}
static class Timing {
Pos p;
int t, z;
public Timing(Pos p, int t) {
this.p = p;
this.t = t;
this.z = p.z * 60 + t;
}
}
static class Pos implements Comparable<Pos> {
static Pos[] instances;
static Pos[] moved;
static {
instances = new Pos[N * N];
moved = new Pos[4 * N * N];
for (int i = 0; i < N * N; i++) {
instances[i] = new Pos(i % N, i / N, i);
}
for (int i = 0; i < N * N; i++) {
for (int d = 0; d < 4; d++) { // LURD
int nx = i % N + (d - 1) % 2;
int ny = i / N + (d - 2) % 2;
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
moved[i * 4 + d] = instances[ny * N + nx];
}
}
}
}
final int x, y, z;
private Pos(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
Pos moved(int d) {
return moved[z * 4 + d];
}
int dist(Pos o) {
return Math.abs(x - o.x) + Math.abs(y - o.y);
}
Pos[] neighbors() {
Pos[] p = new Pos[4];
int i = 0;
if ((p[i] = moved(0)) != null) i++;
if ((p[i] = moved(1)) != null) i++;
if ((p[i] = moved(2)) != null) i++;
if ((p[i] = moved(3)) != null) i++;
return i == 4 ? p : Arrays.copyOf(p, i);
}
@Override
public int compareTo(Pos o) {
return Integer.compare(z, o.z);
}
@Override
public boolean equals(Object o) {
return o instanceof Pos && z == ((Pos)o).z;
}
@Override
public int hashCode() {
return z;
}
@Override
public String toString() {
return String.format("(%d, %d)", x, y);
}
}
static void debug(Object... args) {
if (args == null || args.getClass() != Object[].class) {
args = new Object[] {args};
}
System.err.println(Arrays.stream(args).map(obj -> {
Class<?> clazz = obj == null ? null : obj.getClass();
return clazz == byte[].class ? Arrays.toString((byte[])obj) :
clazz == short[].class ? Arrays.toString((short[])obj) :
clazz == int[].class ? Arrays.toString((int[])obj) :
clazz == long[].class ? Arrays.toString((long[])obj) :
clazz == char[].class ? Arrays.toString((char[])obj) :
clazz == float[].class ? Arrays.toString((float[])obj) :
clazz == double[].class ? Arrays.toString((double[])obj) :
clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
String.valueOf(obj);
}).collect(Collectors.joining(" ")));
}
long elapsed() {
return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1));
}
boolean elapsed(long timeLimit) {
return elapsed() >= timeLimit;
}
public static void main(String[] args) {
new Main().solve(0);
}
static class Random {
private long a, b, c, d;
Random() {
this(ThreadLocalRandom.current().nextLong());
}
Random(long seed) {
this.a = seed;
for (int i = 0; i < 20; i++) {
rand();
}
}
private int rand() {
long t = a ^ (a << 11);
a = b;
b = c;
c = d;
d = d ^ (d >>> 19) ^ t ^ (t >>> 8);
return (int)(a & 0x7fffffff);
}
long next() {
return (long)rand() << 31 | rand();
}
int next(int n) {
return rand() % n;
}
int next(int l, int r) {
return rand() % (r - l) + l;
}
double nextDouble() {
return rand() / 2147483648.0;
}
double nextLog() {
return Math.log(rand() + 1) - 21.487562597358306;
}
}
static class In {
private final BufferedReader reader;
private StringTokenizer tokenizer;
In(InputStream input) {
this.reader = new BufferedReader(new InputStreamReader(input), 0x10000);
}
String next() {
try {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
} catch (IOException ignored) {
}
return tokenizer.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
char[] nextCharArray() {
return next().toCharArray();
}
String[] nextStringArray(int n) {
String[] s = new String[n];
for (int i = 0; i < n; i++) {
s[i] = next();
}
return s;
}
char[][] nextCharGrid(int n, int m) {
char[][] a = new char[n][m];
for (int i = 0; i < n; i++) {
a[i] = next().toCharArray();
}
return a;
}
int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
int[] nextIntArray(int n, IntUnaryOperator op) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = op.applyAsInt(nextInt());
}
return a;
}
int[][] nextIntMatrix(int h, int w) {
int[][] a = new int[h][w];
for (int i = 0; i < h; i++) {
a[i] = nextIntArray(w);
}
return a;
}
long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = nextLong();
}
return a;
}
long[] nextLongArray(int n, LongUnaryOperator op) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = op.applyAsLong(nextLong());
}
return a;
}
long[][] nextLongMatrix(int h, int w) {
long[][] a = new long[h][w];
for (int i = 0; i < h; i++) {
a[i] = nextLongArray(w);
}
return a;
}
List<List<Integer>> nextEdges(int n, int m, boolean directed) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
res.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int u = nextInt() - 1;
int v = nextInt() - 1;
res.get(u).add(v);
if (!directed) {
res.get(v).add(u);
}
}
return res;
}
}
}