結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 Yu_212
|
| 提出日時 | 2022-06-12 15:28:35 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 28,795 bytes |
| コンパイル時間 | 2,611 ms |
| 実行使用メモリ | 114,120 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2022-06-12 15:29:52 |
| 合計ジャッジ時間 | 9,156 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
ソースコード
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
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 In in = new In();
static Out out = new Out(false);
static final long inf = 0x1fffffffffffffffL;
static final int iinf = 0x3fffffff;
static final double eps = 1e-9;
static long mod = 998244353;
double p;
int n = 20;
Pos[] instances = new Pos[n * n];
Pos[][] moved = new Pos[4][n * n];
String[] roads = new String[n * n];
double[][] walls = new double[4][n * n];
void solve() {
for (int i = 0; i < n * n; i++) {
instances[i] = new Pos(i % n, i / n, i);
}
for (int d = 0; d < 4; d++) {
for (int i = 0; i < n * n; i++) {
int nx = i % n + (d - 1) % 2;
int ny = i / n + (d - 2) % 2;
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
moved[d][i] = instances[ny * n + nx];
}
}
}
in.nextInt();
in.nextInt();
p = in.nextInt() / 100.0;
roads[0] = "";
for (int i = 0; i < 4; i++) {
for (int j = 0; j < n * n; j++) {
if (pos(j).moved(i) == null) {
walls[i][j] = 1;
} else {
walls[i][j] = 0.5;
}
}
}
while (true) {
// BitBoard visited = BitBoard.zeros(n);
// visited.set(0, 0);
String ask = bfs();
// StringBuilder ask = dfs(pos(0, 0), 0, visited).reverse();
ask(ask.toString());
}
// debug(w);
}
boolean[][] gen() {
boolean[][] w = new boolean[4][n * n];
int c = 0;
ThreadLocalRandom rand = ThreadLocalRandom.current();
int m = rand.nextInt(100, 200);
for (int i = 0; i < m; i++) {
if (rand.nextInt(2) == 0) {
int ii = rand.nextInt(0, 20);
int jj = rand.nextInt(0, 19);
w[2][ii * n + jj] = true;
w[0][ii * n + jj + 1] = true;
c++;
} else {
int ii = rand.nextInt(0, 19);
int jj = rand.nextInt(0, 20);
w[3][ii * n + jj] = true;
w[1][(ii + 1) * n + jj] = true;
c++;
}
}
return w;
}
int virtual(boolean[][] w, String moves) {
Pos cur = pos(0, 0);
for (int i = 0; i < moves.length(); i++) {
int dir = "LURD".indexOf(moves.charAt(i));
if (ThreadLocalRandom.current().nextInt(100) <= p) {
return i;
}
if (cur.moved(dir) == null) {
throw new RuntimeException();
}
if (w[dir][cur.z]) {
return i;
}
cur = cur.moved(dir);
}
if (cur == pos(n - 1, n - 1)) {
return -1;
}
return moves.length();
}
String bfs() {
class State implements Comparable<State> {
final Pos pos;
final int dist;
final double prob;
State(Pos pos, int dist, double prob) {
this.pos = pos;
this.dist = dist;
this.prob = prob;
}
@Override
public int compareTo(State o) {
if (dist == o.dist) {
return -Double.compare(prob, o.prob);
} else {
return Integer.compare(dist, o.dist);
}
}
}
PriorityQueue<State> queue = new PriorityQueue<>();
queue.add(new State(pos(0, 0), 0, 1));
int[] prev = new int[n * n];
int[] dist = new int[n * n];
double[] prob = new double[n * n];
Arrays.fill(dist, iinf);
Arrays.fill(prob, 0);
prev[0] = -1;
dist[0] = 0;
prob[0] = 1;
Pos best = null;
while (!queue.isEmpty()) {
State state = queue.remove();
Pos cur = state.pos;
if (dist[cur.z] < state.dist) {
continue;
}
if (best == null || dist[best.z] < dist[cur.z] || dist[best.z] == dist[cur.z] && prob[best.z] < prob[cur.z]) {
best = cur;
}
for (int dir = 0; dir < 4; dir++) {
Pos nei = cur.moved(dir);
if (nei == null) {
continue;
}
double pp = state.prob * (1 - walls[dir][cur.z]);
if (dist[nei.z] > state.dist + 1 || dist[nei.z] == state.dist + 1 && prob[nei.z] < pp) {
dist[nei.z] = state.dist + 1;
prev[nei.z] = dir;
prob[nei.z] = pp;
queue.add(new State(nei, state.dist + 1, pp));
}
}
}
StringBuilder bb = new StringBuilder();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
bb.append(dist[i * n + j]).append(", ");
}
bb.append('\n');
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
bb.append(String.format("%2.2f", prob[i * n + j])).append(", ");
}
bb.append('\n');
}
StringBuilder ret = new StringBuilder();
while (best.z != 0) {
ret.append("LURD".charAt(prev[best.z]));
best = best.moved((prev[best.z] + 2) % 4);
}
return ret.reverse().toString();
}
// StringBuilder dfs(Pos cur, int depth, BitBoard visited) {
// List<Integer> cand = new ArrayList<>();
// for (int dir = 0; dir < 4; dir++) {
// Pos nei = cur.moved(dir);
// if (nei == null || visited.get(nei.x, nei.y) || walls[dir][cur.z] > 0.9) {
// continue;
// }
// cand.add(dir);
// }
// if (cand.isEmpty()) {
// return new StringBuilder();
// }
// cand.sort(Comparator.comparingDouble(i -> walls[i][cur.z]));
// int dir = cand.get(0);
// Pos nei = cur.moved(dir);
// visited.set(nei.x, nei.y);
// String ret = bfs();
// visited.clear(nei.x, nei.y);
// ret.append("LURD".charAt(dir));
// double prob = (1 - walls[dir][cur.z]) * ret.length();
// return ret;
// }
void debug(boolean[][] w) {
char[][] c = new char[n][n * 2 - 1];
for (int i = 0; i < n; i++) {
Arrays.fill(c[i], ' ');
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (w[2][i * n + j]) {
c[i][j * 2 + 1] = '|';
}
if (w[3][i * n + j]) {
c[i][j * 2] = '_';
}
}
}
for (int i = 0; i < n; i++) {
out.println(String.valueOf(c[i]));
}
}
// boolean[][] w = gen();
int ask(String moves) {
Pos cur = pos(0, 0);
out.println(moves);
out.flush();
int k = in.nextInt();
// int k = virtual(w, moves);
out.debug(k);
if (k == -1) {
System.exit(0);
}
int len = moves.length();
for (int i = 0; i <= k && i < len; i++) {
int dir = "LURD".indexOf(moves.charAt(i));
if (i == k) {
walls[dir][cur.z] = walls[dir][cur.z] / (walls[dir][cur.z] + p);
} else {
String sub = moves.substring(0, i);
if (roads[cur.z] == null || roads[cur.z].length() > sub.length()) {
roads[cur.z] = sub;
}
walls[dir][cur.z] = 0;
}
cur = cur.moved(dir);
}
return k;
}
Pos pos(int x, int y) {
return instances[y * n + x];
}
Pos pos(int z) {
return instances[z];
}
class Pos implements Comparable<Pos> {
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[d][z];
}
int dist(Pos o) {
return Math.abs(x - o.x) + Math.abs(y - o.y);
}
int euclid(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 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 abstract class BitBoard {
private static final long[] MASKS = {0, 0x1L, 0x3L, 0x7L, 0xFL, 0x1FL, 0x3FL, 0x7FL, 0xFFL, 0x1FFL, 0x3FFL, 0x7FFL, 0xFFFL, 0x1FFFL, 0x3FFFL, 0x7FFFL, 0xFFFFL, 0x1FFFFL, 0x3FFFFL, 0x7FFFFL, 0xFFFFFL, 0x1FFFFFL, 0x3FFFFFL, 0x7FFFFFL, 0xFFFFFFL, 0x1FFFFFFL, 0x3FFFFFFL, 0x7FFFFFFL, 0xFFFFFFFL, 0x1FFFFFFFL, 0x3FFFFFFFL, 0x7FFFFFFFL, 0xFFFFFFFFL, 0x1FFFFFFFFL, 0x3FFFFFFFFL, 0x7FFFFFFFFL, 0xFFFFFFFFFL, 0x1FFFFFFFFFL, 0x3FFFFFFFFFL, 0x7FFFFFFFFFL, 0xFFFFFFFFFFL, 0x1FFFFFFFFFFL, 0x3FFFFFFFFFFL, 0x7FFFFFFFFFFL, 0xFFFFFFFFFFFL, 0x1FFFFFFFFFFFL, 0x3FFFFFFFFFFFL, 0x7FFFFFFFFFFFL, 0xFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFL, 0x3FFFFFFFFFFFFL, 0x7FFFFFFFFFFFFL, 0xFFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFFL, 0x1FFFFFFFFFFFFFFFL, 0x3FFFFFFFFFFFFFFFL, 0x7FFFFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFFFFL};
private static class BitBoard8 extends BitBoard { // [][][][][][][][] x1
private final static long[] ONES = {0, 0x1L, 0x101L, 0x10101L, 0x1010101L, 0x101010101L, 0x10101010101L, 0x1010101010101L, 0x101010101010101L};
private BitBoard8(int size) {
super(size, new long[1]);
}
private BitBoard8(int size, long[] board) {
super(size, board);
}
public BitBoard copy() {
return new BitBoard8(size, board);
}
protected int x(int x, int y) {
return y << 3 | x;
}
protected int y(int x, int y) {
return 0;
}
public long line(int y) {
return board[0] >>> (y << 3) & 0xFF;
}
public int countOne() {
return Long.bitCount(board[0]);
}
public void fillOnes() {
board[0] = ONES[size] * MASKS[size];
}
public void spread() {
board[0] |= spread(board[0], 8, ONES[size]) & MASKS[size * 8];
}
private static BitBoard compress(long[] lines) {
long board = 0;
for (long line : lines) {
board = board << 8 | line;
}
return new BitBoard8(lines.length, new long[] {board});
}
}
private static class BitBoard16 extends BitBoard { // [ ][ ][ ][ ] x4
private final static long[] ONES = {0x1000100010001L, 0x1L, 0x10001L, 0x100010001L};
private BitBoard16(int size) {
super(size, new long[(size + 3) >> 2]);
}
private BitBoard16(int size, long[] board) {
super(size, board);
}
public BitBoard copy() {
return new BitBoard16(size, board);
}
protected int x(int x, int y) {
return (y & 3) << 4 | x;
}
protected int y(int x, int y) {
return y >> 2;
}
public long line(int y) {
return board[y >> 2] >>> ((y & 3) << 4) & 0xFFFF;
}
public int countOne() {
if (board.length == 3) {
return Long.bitCount(board[0]) + Long.bitCount(board[1]) + Long.bitCount(board[2]);
} else {
return Long.bitCount(board[0]) + Long.bitCount(board[1]) + Long.bitCount(board[2]) + Long.bitCount(board[3]);
}
}
public void fillOnes() {
board[0] = ONES[0] * MASKS[size];
board[1] = ONES[0] * MASKS[size];
if (board.length == 3) {
board[2] = ONES[size & 3] * MASKS[size];
} else {
board[2] = ONES[0] * MASKS[size];
board[3] = ONES[size & 3] * MASKS[size];
}
}
public void spread() {
long old0 = board[0];
long old1 = board[1];
long old2 = board[2];
board[0] |= spread(old0, 16, ONES[0]) | old1 << 48;
board[1] |= spread(old1, 16, ONES[0]) | old2 << 48 | old0 >>> 48;
if (board.length == 3) {
board[2] |= spread(old2, 16, ONES[0]) & MASKS[(size - 8) * 16] | old1 >>> 48;
} else {
long old3 = board[3];
board[2] |= spread(old2, 16, ONES[0]) | old3 << 48 | old1 >>> 48;
board[3] |= spread(old3, 16, ONES[0]) & MASKS[(size - 12) * 16] | old2 >>> 48;
}
}
private static BitBoard compress(long[] lines) {
long[] board = new long[lines.length >> 2];
for (int i = 0; i < lines.length; i++) {
board[i >> 2] = board[i >> 2] << 16 | lines[i];
}
return new BitBoard16(lines.length, board);
}
}
private static class BitBoard32 extends BitBoard { // [ ][ ] x16
private BitBoard32(int size) {
super(size, new long[(size + 1) >> 1]);
}
private BitBoard32(int size, long[] board) {
super(size, board);
}
public BitBoard copy() {
return new BitBoard32(size, board);
}
protected int x(int x, int y) {
return (y & 1) << 5 | x;
}
protected int y(int x, int y) {
return y >> 1;
}
public long line(int y) {
return board[y >> 1] >>> ((y & 1) << 5) & 0xFFFFFFFFL;
}
public void fillOnes() {
Arrays.fill(board, MASKS[size] << 16 | MASKS[size]);
if ((size & 1) == 1) {
board[board.length - 1] = MASKS[size];
}
}
public void spread() {
long old = 0;
for (int i = 0; i < board.length; i++) {
if (i > 0) {
board[i - 1] |= board[i] << 32;
}
long old2 = board[i];
board[i] |= spread(board[i], 32, 0x100000001L) | old >>> 32;
old = old2;
}
if ((size & 1) == 1) {
board[board.length - 1] &= 0xFFFFFFFFL;
}
}
private static BitBoard compress(long[] lines) {
long[] board = new long[lines.length >> 2];
for (int i = 0; i < lines.length; i++) {
board[i >> 2] = board[i >> 2] << 16 | lines[i];
}
return new BitBoard32(lines.length, board);
}
}
private static class BitBoard64 extends BitBoard { // [ ] x64
private BitBoard64(int size) {
super(size, new long[size]);
}
private BitBoard64(int size, long[] board) {
super(size, board);
}
public BitBoard copy() {
return new BitBoard64(size, board);
}
protected int x(int x, int y) {
return x;
}
protected int y(int x, int y) {
return y;
}
public long line(int y) {
return board[y];
}
public void fillOnes() {
Arrays.fill(board, MASKS[size]);
}
public void spread() {
long old = 0;
for (int i = 0; i < board.length; i++) {
if (i > 0) {
board[i - 1] |= board[i];
}
long old2 = board[i];
board[i] |= old | board[i] >>> 1 | board[i] << 1 & MASKS[size];
old = old2;
}
}
private static BitBoard compress(long[] lines) {
return new BitBoard64(lines.length, lines);
}
}
protected final long[] board;
protected final byte size;
private BitBoard(int size, long[] board) {
this.size = (byte)size;
this.board = board;
}
public static BitBoard of(long[] lines) {
int size = lines.length;
if (size <= 8) {
return BitBoard8.compress(lines);
} else if (size <= 16) {
return BitBoard16.compress(lines);
} else if (size <= 32) {
return BitBoard32.compress(lines);
} else if (size <= 64) {
return BitBoard64.compress(lines);
}
throw new IllegalArgumentException();
}
public static BitBoard zeros(int size) {
if (0 <= size) {
if (size <= 8) {
return new BitBoard8(size);
} else if (size <= 16) {
return new BitBoard16(size);
} else if (size <= 32) {
return new BitBoard32(size);
} else if (size <= 64) {
return new BitBoard64(size);
}
}
throw new IllegalArgumentException();
}
public static BitBoard ones(int size) {
BitBoard board = zeros(size);
board.fillOnes();
return board;
}
protected long spread(long a, int b, long ones) {
long shiftLeft = (a & ~ones) >>> 1;
long shiftRight = (a & ~(ones << size - 1)) << 1;
return shiftLeft | shiftRight | a << b | a >>> b;
}
protected abstract int x(int x, int y);
protected abstract int y(int x, int y);
public abstract BitBoard copy();
public abstract long line(int y);
public abstract void fillOnes();
public abstract void spread();
public BitBoard subboard(int sx, int sy, int size) {
long[] lines = new long[size];
for (int i = 0; i < size; i++) {
lines[i] = line(sy + i) >> sx & MASKS[size];
}
return BitBoard.of(lines);
}
public void set(int x, int y) {
Objects.checkIndex(x, size);
Objects.checkIndex(y, size);
board[y(x, y)] |= 1L << x(x, y);
}
public void set(int x, int y, boolean value) {
if (value) {
set(x, y);
} else {
clear(x, y);
}
}
public void flip(int x, int y) {
Objects.checkIndex(x, size);
Objects.checkIndex(y, size);
board[y(x, y)] ^= 1L << x(x, y);
}
public void clear(int x, int y) {
Objects.checkIndex(x, size);
Objects.checkIndex(y, size);
board[y(x, y)] &= ~(1L << x(x, y));
}
public boolean get(int x, int y) {
Objects.checkIndex(x, size);
Objects.checkIndex(y, size);
return (line(y) >>> x & 1) == 1;
}
public void and(BitBoard o) {
for (int i = 0; i < board.length; i++) {
board[i] &= o.board[i];
}
}
public void or(BitBoard o) {
for (int i = 0; i < board.length; i++) {
board[i] |= o.board[i];
}
}
public void xor(BitBoard o) {
for (int i = 0; i < board.length; i++) {
board[i] ^= o.board[i];
}
}
public void andNot(BitBoard o) {
for (int i = 0; i < board.length; i++) {
board[i] &= ~o.board[i];
}
}
public int size() {
return size;
}
public int countOne() {
int count = 0;
for (long bits : board) {
count += Long.bitCount(bits);
}
return count;
}
public int countZero() {
return size * size - countOne();
}
@Override
public int hashCode() {
long h = 1234;
for (int i = 0; i < board.length; i++) {
h ^= board[i] * (i + 1);
}
return (int)(h >> 32 ^ h);
}
@Override
public boolean equals(Object o) {
return this == o || o instanceof BitBoard && Arrays.equals(board, ((BitBoard)o).board);
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
builder.append(get(j, i) ? 'o' : '.');
}
if (i + 1 < size) {
builder.append('\n');
}
}
return builder.toString();
}
}
public static void main(String... args) {
new Main().solve();
out.flush();
}
}
class In {
private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 0x10000);
private StringTokenizer tokenizer;
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;
}
}
class Out {
private final PrintWriter out = new PrintWriter(System.out);
private final PrintWriter err = new PrintWriter(System.err);
boolean autoFlush = false;
boolean enableDebug;
Out(boolean enableDebug) {
this.enableDebug = enableDebug;
}
void println(Object... args) {
if (args == null || args.getClass() != Object[].class) {
args = new Object[] {args};
}
out.println(Arrays.stream(args).map(obj -> {
Class<?> clazz = obj == null ? null : obj.getClass();
return clazz == Double.class ? String.format("%.10f", obj) :
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(" ")));
if (autoFlush) {
out.flush();
}
}
void debug(Object... args) {
if (!enableDebug) {
return;
}
if (args == null || args.getClass() != Object[].class) {
args = new Object[] {args};
}
err.println(Arrays.stream(args).map(obj -> {
Class<?> clazz = obj == null ? null : obj.getClass();
return clazz == Double.class ? String.format("%.10f", obj) :
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(" ")));
err.flush();
}
void println(char[] s) {
out.println(String.valueOf(s));
if (autoFlush) {
out.flush();
}
}
void println(int[] a) {
StringJoiner joiner = new StringJoiner(" ");
for (int i : a) {
joiner.add(Integer.toString(i));
}
out.println(joiner);
if (autoFlush) {
out.flush();
}
}
void println(long[] a) {
StringJoiner joiner = new StringJoiner(" ");
for (long i : a) {
joiner.add(Long.toString(i));
}
out.println(joiner);
if (autoFlush) {
out.flush();
}
}
void flush() {
err.flush();
out.flush();
}
}