結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 Yu_212
|
| 提出日時 | 2023-04-29 17:01:49 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 1,659 ms / 2,000 ms |
| コード長 | 28,276 bytes |
| コンパイル時間 | 5,877 ms |
| コンパイル使用メモリ | 106,728 KB |
| 実行使用メモリ | 87,056 KB |
| スコア | 20,517,831,870 |
| 平均クエリ数 | 400.00 |
| 最終ジャッジ日時 | 2023-04-29 17:07:05 |
| 合計ジャッジ時間 | 87,339 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,477 ms
72,116 KB |
| testcase_01 | AC | 1,447 ms
86,552 KB |
| testcase_02 | AC | 1,387 ms
72,108 KB |
| testcase_03 | AC | 1,659 ms
85,716 KB |
| testcase_04 | AC | 1,566 ms
72,928 KB |
| testcase_05 | AC | 1,491 ms
86,352 KB |
| testcase_06 | AC | 1,478 ms
72,248 KB |
| testcase_07 | AC | 1,363 ms
72,848 KB |
| testcase_08 | AC | 1,554 ms
86,016 KB |
| testcase_09 | AC | 1,445 ms
72,304 KB |
| testcase_10 | AC | 1,349 ms
86,400 KB |
| testcase_11 | AC | 1,461 ms
72,068 KB |
| testcase_12 | AC | 1,514 ms
84,104 KB |
| testcase_13 | AC | 1,486 ms
72,744 KB |
| testcase_14 | AC | 1,516 ms
84,792 KB |
| testcase_15 | AC | 1,422 ms
72,248 KB |
| testcase_16 | AC | 1,463 ms
84,984 KB |
| testcase_17 | AC | 1,413 ms
72,408 KB |
| testcase_18 | AC | 1,381 ms
86,168 KB |
| testcase_19 | AC | 1,522 ms
71,624 KB |
| testcase_20 | AC | 1,507 ms
84,372 KB |
| testcase_21 | AC | 1,528 ms
71,848 KB |
| testcase_22 | AC | 1,537 ms
85,856 KB |
| testcase_23 | AC | 1,547 ms
71,884 KB |
| testcase_24 | AC | 1,516 ms
84,176 KB |
| testcase_25 | AC | 1,420 ms
72,440 KB |
| testcase_26 | AC | 1,439 ms
83,044 KB |
| testcase_27 | AC | 1,531 ms
71,684 KB |
| testcase_28 | AC | 1,437 ms
86,412 KB |
| testcase_29 | AC | 1,510 ms
73,196 KB |
| testcase_30 | AC | 1,437 ms
86,548 KB |
| testcase_31 | AC | 1,396 ms
72,452 KB |
| testcase_32 | AC | 1,626 ms
86,164 KB |
| testcase_33 | AC | 1,503 ms
73,796 KB |
| testcase_34 | AC | 1,455 ms
86,508 KB |
| testcase_35 | AC | 1,514 ms
72,464 KB |
| testcase_36 | AC | 1,361 ms
86,416 KB |
| testcase_37 | AC | 1,522 ms
72,568 KB |
| testcase_38 | AC | 1,422 ms
87,056 KB |
| testcase_39 | AC | 1,462 ms
86,152 KB |
| testcase_40 | AC | 1,478 ms
84,980 KB |
| testcase_41 | AC | 1,567 ms
72,116 KB |
| testcase_42 | AC | 1,364 ms
86,068 KB |
| testcase_43 | AC | 1,380 ms
72,044 KB |
| testcase_44 | AC | 1,498 ms
85,120 KB |
| testcase_45 | AC | 1,384 ms
72,920 KB |
| testcase_46 | AC | 1,492 ms
86,644 KB |
| testcase_47 | AC | 1,528 ms
72,376 KB |
| testcase_48 | AC | 1,544 ms
86,804 KB |
| testcase_49 | AC | 1,426 ms
72,832 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 long[] TABLE = new long[364];
public static final int[] COST = {0,10000000,7071067,5773502,5000000,4472135,4082482,3779644,3535533,3333333,3162277,3015113,2886751,2773500,2672612,2581988,2500000,2425356,2357022,2294157,2236067,2182178,2132007,2085144,2041241,2000000,1961161,1924500,1889822,1856953,1825741,1796053,1767766,1740776,1714985,1690308,1666666,1643989,1622214,1601281,1581138,1561737,1543033,1524985,1507556,1490711,1474419,1458649,1443375,1428571,1414213,1400280,1386750,1373605,1360827,1348399,1336306,1324532,1313064,1301889,1290994,1280368,1270001,1259881,1250000,1240347,1230914,1221694,1212678,1203858,1195228,1186781,1178511,1170411,1162476,1154700,1147078,1139605,1132277,1125087,1118033,1111111,1104315,1097642,1091089,1084652,1078327,1072112,1066003,1059997,1054092,1048284,1042572,1036951,1031421,1025978,1020620,1015346,1010152,1005037,1000000,995037,990147,985329,980580,975900,971285,966736,962250,957826,953462,949157,944911,940720,936585,932504,928476,924500,920574,916698,912870,909090,905357,901669,898026,894427,890870,887356,883883,880450,877058,873704,870388,867109,863868,860662,857492,854357,851256,848188,845154,842151,839181,836242,833333,830454,827605,824786,821994,819231,816496,813788,811107,808452,805822,803219,800640,798086,795557,793051,790569,788110,785674,783260,780868,778498,776150,773823,771516,769230,766964,764719,762492,760285,758098,755928,753778,751646,749531,747435,745355,743294,741249,739221,737209,735214,733235,731272,729324,727392,725476,723574,721687,719815,717958,716114,714285,712470,710669,708881,707106,705345,703597,701862,700140,698430,696733,695048,693375,691714,690065,688428,686802,685188,683585,681994,680413,678844,677285,675737,674199,672672,671156,669649,668153,666666,665190,663723,662266,660818,659380,657951,656532,655121,653720,652328,650944,649569,648203,646846,645497,644156,642824,641500,640184,638876,637576,636284,635000,633724,632455,631194,629940,628694,627455,626224,625000,623782,622572,621369,620173,618984,617802,616626,615457,614295,613139,611990,610847,609710,608580,607456,606339,605227,604122,603022,601929,600841,599760,598684,597614,596549,595491,594438,593390,592348,591312,590281,589255,588235,587220,586210,585205,584206,583211,582222,581238,580258,579284,578314,577350,576390,575435,574484,573539,572598,571661,570730,569802,568880,567961,567047,566138,565233,564332,563436,562543,561655,560772,559892,559016,558145,557278,556414,555555,554700,553848,553001,552157,551317,550481,549649,548821,547996,547175,546358,545544,544734,543928,543125,542326,541530,540738,539949,539163,538381,537603,536828,536056,535287,534522,533760,533001,532246,531494,530744,529998,529256,528516,527779,527046,526315,525588,524863,524142,523423,522708,521995,521286,520579,519875,519174,518475,517780,517087,516397,515710,515026,514344,513665,512989,512315,511644,510976,510310,509647,508986,508328,507673,507020,506369,505721,505076,504433,503792,503154,502518,501885,501254,500626,500000};
public static final int S = 14;
public static final int SS = 196;
public static final int N = 3000;
public static final int T = 400;
int curTurn;
int corCollabo = 1;
int corMoney = 1000000;
long solve(int seed) {
startTime = System.currentTimeMillis();
Arrays.setAll(TABLE, i -> rand.next());
in();
// 80 10 424367600
// 80 20 450836500
// 80 30 439329940
// 80 50 416846380
// 50 50 404948590
// 70 50 416677250
// 90 50 417352330
// 100 50 402903920
// 150 50 344831110
int u1 = 80;
State2 state = new State2();
int nj = 0;
int lastU = 0;
Action next = null;
if (!isLocal) {
corMoney = in.nextInt();
in.nextInt();
}
while (curTurn < T) {
if (next == null) {
for (Action ac : state.actions()) {
ac.open();
if (next == null || next.score < ac.score) {
next = ac;
}
}
}
boolean c1 = corMoney >= COST[corCollabo];
int cd = COST[corCollabo] - COST[corCollabo + 1];
int ud = (next.opened.score - lastU) * 60;
int e1 = !c1 ? -iinf : (T - curTurn) * ud - cd - 50000 - COST[corCollabo];
int e2 = Math.max(1, u1 - nj) * cd - ud - 50000;
int e3 = 50000 - cd - ud;
// debug(e1, e2, e3);
// debug(corMoney);
if (e2 > e1 && e2 > e3) {
corCollabo++;
corMoney += 60 * lastU;
ask2();
} else if (c1 && e1 > e3) {
// debug(corCollabo, COST[corCollabo], corMoney);
lastU = next.opened.score;
corMoney += 60 * lastU - COST[corCollabo];
nj++;
ask1(next.x, next.v);
state = next.opened;
next = null;
} else {
corMoney += 50000 + 60 * lastU;
ask3();
}
}
// int u2 = 50;
// State2 state = new State2();
// // State2 result = beamSearch(new State2(), trace, 10, 100000);
// // debug(result.score);
// if (!isLocal) {
// corMoney = in.nextInt();
// in.nextInt();
// }
// // int money = 1000000;
// int lastU = 0;
// int nj = 0;
// for (int i = 1; i < u2; i++) {
// corCollabo++;
// ask2();
// }
// while (true) {
// while (corMoney < COST[corCollabo]) {
// corMoney += 50000 + 60 * lastU;
// ask3();
// }
//
// Action best = null;
// for (Action next : state.actions()) {
// next.open();
// if (best == null || best.score < next.score) {
// best = next;
// }
// }
// state = best.opened;
//
// // debug(k++, pos(action.x), action.v, action.opened.score);
// if ((best.opened.score - lastU) * 60 * (T - curTurn) < 900000) {
// debug(nj);
// break;
// }
//// debug((best.opened.score - lastU) * (T - curTurn));
// lastU = best.opened.score;
// corMoney += 60 * lastU - COST[corCollabo];
// nj++;
// ask1(best.x, best.v);
// if (curTurn >= T) {
// break;
// }
// }
// while (curTurn < T) {
// corMoney += 60 * lastU;
// ask3();
// }
//
// int u1 = 80;
// int[] u2 = {30, 20};
//
// Trace trace = new Trace();
// State2 result = greedy(new State2(), trace, u1);
//// State2 result = beamSearch(new State2(), trace, 10, 100000);
//// debug(result.score);
// if (!isLocal) {
// corMoney = in.nextInt();
// in.nextInt();
// }
//// int money = 1000000;
// int lastU = 0;
// int nj = 0;
// List<Action> actions = trace.trace(result.id);
// for (Action action : actions) {
// for (int i = 0; nj < u2.length && i < u2[nj]; i++) {
// corCollabo++;
// ask2();
// }
// while (corMoney < COST[corCollabo]) {
// corMoney += 50000 + 60 * lastU;
// ask3();
// }
//// debug(k++, pos(action.x), action.v, action.opened.score);
// if ((action.opened.score - lastU) * (T - curTurn) < 30000) {
// break;
// }
// debug((action.opened.score - lastU) * (T - curTurn));
// lastU = action.opened.score;
// corMoney += 60 * lastU - COST[corCollabo];
// nj++;
// ask1(action.x, action.v);
// if (curTurn >= T) {
// break;
// }
// }
// while (curTurn < T) {
// corMoney += 60 * lastU;
// ask3();
// }
return isLocal ? corMoney : 0;
}
int px(int x, boolean v) {
return v ? x : x % S * S + x / S;
}
int py(int x, boolean v) {
return v ? x + S : x % S * S + x / S + 1;
}
void ask1(int x, boolean v) {
Pos px = pos(px(x, v));
Pos py = pos(py(x, v));
out.println("1 " + (px.x+1) + " " + (px.y+1) + " " + (py.x+1) + " " + (py.y+1));
out.flush();
curTurn++;
if (!isLocal && curTurn < T) {
corMoney = in.nextInt();
in.nextInt();
}
}
void ask2() {
out.println(2);
out.flush();
curTurn++;
if (!isLocal && curTurn < T) {
corMoney = in.nextInt();
in.nextInt();
}
}
void ask3() {
out.println(3);
out.flush();
curTurn++;
if (!isLocal && curTurn < T) {
corMoney = in.nextInt();
in.nextInt();
}
}
Pos[] fs, ts;
void in() {
Pos.init(S);
in.nextInt();
in.nextInt();
fs = new Pos[N];
ts = new Pos[N];
for (int i = 0; i < N; i++) {
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;
int c = in.nextInt() - 1;
int d = in.nextInt() - 1;
fs[i] = pos(a, b);
ts[i] = pos(c, d);
}
}
Pos pos(int x, int y) {
return Pos.instances[y * S + x];
}
Pos pos(int z) {
return Pos.instances[z];
}
static class Pos implements Comparable<Pos> {
static Pos[] instances = new Pos[SS];
static Pos[] moved = new Pos[4 * SS];
static void init(int 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);
}
}
// class State {
// int collabo;
// int money;
// BitSet vert;
// BitSet hori;
//
// int constructCost() {
// return COST[collabo];
// }
// }
State2 initialState() {
return new State2();
}
class State2 implements Comparable<State2> {
int id;
State2 prev;
int score;
long hash;
BitSet vert; // |
BitSet hori; // -
int[] dist;
int[] uses;
State2() {
this.id = -1;
this.hash = 0;
this.vert = new BitSet(SS);
this.hori = new BitSet(SS);
this.dist = new int[N];
this.uses = new int[N];
for (int i = 0; i < N; i++) {
dist[i] = Math.abs(fs[i].x - ts[i].x) + Math.abs(fs[i].y - ts[i].y);
}
}
State2(State2 prev) {
this.id = prev.id;
this.prev = prev;
this.score = prev.score;
this.hash = prev.hash;
this.vert = (BitSet)prev.vert.clone();
this.hori = (BitSet)prev.hori.clone();
this.dist = prev.dist.clone();
this.uses = prev.uses.clone();
}
boolean highway(Pos p, int d) {
if ((d & 1) == 0) { // LURD
return hori.get(p.z - (d>>1^1));
} else {
return vert.get(p.z - (d>>1^1) * S);
}
}
int dist(int d, int u) {
return d * 1000 - u * 777;
}
void update(int x, boolean v) {
int px = px(x, v);
int py = py(x, v);
(v ? vert : hori).set(px);
hash ^= TABLE[x + (v ? 182 : 0)];
Deque<Pos> deque1 = new ArrayDeque<>();
Deque<Pos> deque2 = new ArrayDeque<>();
BitSet fromY = new BitSet(SS);
deque1.add(pos(px));
deque1.add(pos(py));
deque2.add(pos(px));
deque2.add(pos(py));
fromY.set(py);
int[] ds = new int[SS];
int[] us = new int[SS];
Arrays.fill(ds, 30);
ds[px] = 0;
ds[py] = 0;
while (!deque1.isEmpty() || !deque2.isEmpty()) {
Pos p1 = deque1.isEmpty() ? null : deque1.peekFirst();
Pos p2 = deque2.isEmpty() ? null : deque2.peekFirst();
Pos p;
boolean h = p2 == null || p1 != null && dist(ds[p1.z], us[p1.z]) < dist(ds[p2.z], us[p2.z]);
if (h) {
p = deque1.removeFirst();
} else {
p = deque2.removeFirst();
}
for (int i = 0; i < 4; i++) {
Pos q = p.moved(i);
if (q == null || highway(p, i) != h) {
continue;
}
int nd = ds[p.z] + 1;
int nu = us[p.z] + (h ? 1 : 0);
if (dist(ds[q.z], us[q.z]) > dist(nd, nu)) {
ds[q.z] = nd;
us[q.z] = nu;
fromY.set(q.z, fromY.get(p.z));
deque1.addLast(q);
deque2.addLast(q);
}
}
}
for (int i = 0; i < N; i++) {
if (fromY.get(fs[i].z) == fromY.get(ts[i].z)) {
continue;
}
int nd = ds[fs[i].z] + ds[ts[i].z] + 1;
int nu = us[fs[i].z] + us[ts[i].z] + 1;
if (dist(dist[i], uses[i]) > dist(nd, nu)) {
score += nu - uses[i];
dist[i] = nd;
uses[i] = nu;
}
}
}
static int[] ord = new int[182];
static {
Arrays.setAll(ord, i -> i);
}
List<Action> actions() {
List<Action> nexts = new ArrayList<>();
for (int ii = 0; ii < 60; ii++) {
int j = ii + rand.next(182 - ii);
int i = ord[j];
ord[j] = ord[ii];
ord[ii] = i;
if (!vert.get(i)) {
nexts.add(new Action(this, hash ^ TABLE[i + 182], i, true));
}
if (!hori.get(i)) {
nexts.add(new Action(this, hash ^ TABLE[i], i, false));
}
}
return nexts;
}
void advance(Trace trace, Action action) {
hash = action.hash;
score = action.score;
id = trace.add(action, id);
}
State2 copy() {
return new State2(this);
}
@Override
public int compareTo(State2 o) {
return Integer.compare(score, o.score);
}
}
class Action implements Comparable<Action> {
State2 prev;
State2 opened;
long hash;
int score;
int x;
boolean v;
Action(State2 prev, long hash, int x, boolean v) {
this.prev = prev;
this.hash = hash;
this.x = x;
this.v = v;
}
void open() {
opened = prev.copy();
opened.update(x, v);
score = opened.score;
}
@Override
public int compareTo(Action o) {
return Integer.compare(o.score, score);
}
}
static class Trace {
List<Action> log = new ArrayList<>();
List<Integer> prev = new ArrayList<>();
int add(Action action, int pi) {
log.add(action);
prev.add(pi);
return log.size() - 1;
}
List<Action> trace(int id) {
List<Action> actions = new ArrayList<>();
while (id != -1) {
actions.add(log.get(id));
id = prev.get(id);
}
Collections.reverse(actions);
return actions;
}
Action first(int id) {
Action first = null;
while (id != -1) {
first = log.get(id);
id = prev.get(id);
}
return first;
}
void clear() {
log.clear();
prev.clear();
}
}
State2 beamSearch(State2 initialState, Trace trace, int beamWidth, long timeLimit, int maxTurn) {
long[] hashes = new long[1 << 20];
initialState.id = -1;
State2[] beam = {initialState};
State2 best = null;
for (int turn = 1; ; turn++) {
boolean sorted = false;
int numCand = 0;
Action[] cand = new Action[beamWidth * 2];
for (State2 state : beam) {
if (state == null) {
break;
}
for (Action action : state.actions()) {
int key = (int)(action.hash & 0xfffff);
if (hashes[key] != action.hash) {
hashes[key] = action.hash;
action.open();
if (sorted && cand[beamWidth - 1].score > action.score) {
continue;
}
cand[numCand++] = action;
if (numCand == cand.length) {
Arrays.sort(cand, Comparator.reverseOrder());
numCand = beamWidth;
sorted = true;
}
}
}
}
Arrays.sort(cand);
int size = Math.min(beamWidth, numCand);
State2[] next = new State2[size];
int j = 0;
State2 found = null;
for (int i = 0; i < numCand && j < size; i++) {
Action action = cand[i];
State2 copy = action.opened;
copy.advance(trace, action);
if (best == null || best.score < copy.score) {
best = copy;
}
if (turn == maxTurn) {
if (found == null || found.score < copy.score) {
found = copy;
}
continue;
}
next[j++] = copy;
}
if (found != null) {
return found;
}
if (j == 0 || elapsed(timeLimit)) {
throw new RuntimeException();
}
beam = next;
}
}
State2 greedy(State2 state, Trace trace, int maxTurn) {
state.id = -1;
for (int turn = 1; ; turn++) {
Action best = null;
for (Action next : state.actions()) {
next.open();
if (best == null || best.score < next.score) {
best = next;
}
}
state = best.opened;
state.advance(trace, best);
if (turn == maxTurn) {
return state;
}
}
}
static void debug(Object... args) {
if (!isLocal) {
return;
}
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 BinarySearchTree<E extends Comparable<E>> implements Iterable<E> {
private final int n;
private final Object[] a;
private int size;
public BinarySearchTree(int n) {
this.n = n;
this.a = new Object[n];
}
public int size() {
return size;
}
public void add(E element) {
if (size < n) {
int i = size++;
while (i > 0) {
int parent = (i - 1) / 2;
if (get(parent).compareTo(element) <= 0) {
break;
}
a[i] = a[parent];
i = parent;
}
a[i] = element;
} else if (n > 0 && get(0).compareTo(element) < 0) {
int i = 0;
while (i * 2 + 1 < n) {
int child = i * 2 + 1;
if (child + 1 < n && get(child).compareTo(get(child + 1)) > 0) {
child++;
}
if (get(child).compareTo(element) >= 0) {
break;
}
a[i] = a[child];
i = child;
}
a[i] = element;
}
}
@SuppressWarnings("unchecked")
private E get(int index) {
return (E)a[index];
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
private int i = 0;
@Override
public boolean hasNext() {
return i < size;
}
@Override
public E next() {
return get(i++);
}
};
}
}
static class Random {
private long x, y, z, w;
Random() {
this(ThreadLocalRandom.current().nextLong());
}
Random(long seed) {
this.x = seed;
for (int i = 0; i < 20; i++) {
rand();
}
}
private long rand() {
long t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ t ^ (t >>> 8);
return x & 0x7fffffff;
}
long next() {
return rand() << 31 | rand();
}
int next(int n) {
return (int)(rand() % n);
}
int next(int l, int r) {
return (int)(rand() % (r - l) + l);
}
double nextDouble() {
return rand() / 2147483647.0;
}
}
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;
}
}
}