結果
| 問題 | No.1308 ジャンプビーコン |
| ユーザー |
 suisen
|
| 提出日時 | 2020-12-05 07:31:11 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 37,641 bytes |
| コンパイル時間 | 4,202 ms |
| コンパイル使用メモリ | 96,416 KB |
| 実行使用メモリ | 37,568 KB |
| 最終ジャッジ日時 | 2024-09-15 11:37:02 |
| 合計ジャッジ時間 | 6,967 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge6 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 3 |
| other | RE * 37 |
ソースコード
import java.io.InputStream;import java.util.Arrays;import java.util.function.Consumer;import java.util.function.IntUnaryOperator;import java.util.function.LongBinaryOperator;import java.util.function.LongUnaryOperator;public class Main {public static void main(String[] args) throws Exception {ExtendedScanner sc = new ExtendedScanner();FastPrintStream pw = new FastPrintStream();solve(sc, pw);sc.close();pw.flush();pw.close();}@SuppressWarnings("unchecked")public static void solve(ExtendedScanner sc, FastPrintStream pw) {int n = sc.nextInt();int q = sc.nextInt();int c = sc.nextInt();AdjacentList<SimpleEdge> adj = new AdjacentList<>(n, n - 1, false);for (int i = 1; i < n; i++) {int u = sc.nextInt() - 1;int v = sc.nextInt() - 1;long l = sc.nextLong();adj.addEdge(new SimpleEdge(u, v, l));}int[] x = sc.ints(q, e -> e - 1);long[][] d = new long[n][n];DFS<SimpleEdge>[] dfs = new DFS[n];Arrays.setAll(dfs, i -> {long[] di = d[i];return new DFS<>(adj, i, e -> di[e.to] = di[e.from] + e.cost);});long[] pdp = new long[n];long[] dp = new long[n];Arrays.fill(pdp, Const.LINF);int s = x[0], t = x[1];long dst = d[s][t];for (int v = s, par[] = dfs[t].par;; v = par[v]) {pdp[v] = dst;if (v == t) break;}long[] dat = new long[n];long min = dst;for (int i = 2; i < q; i++) {s = x[i - 1]; t = x[i];long[] dt = d[t]; dst = dt[s];DFS<SimpleEdge> dfst = dfs[t];for (int j = 0; j < n; j++) {dat[dfst.beg[j]] = pdp[j] + dt[j];dp[j] = Longs.min(pdp[j] + dst, pdp[j] + c + dt[j], Const.LINF);}for (int j = s, par[] = dfs[t].par;; j = par[j]) {dp[j] = Longs.min(dp[j], min + dst);if (j == t) break;}LongSegmentTree seg = new LongSegmentTree(dat, Long::min, Const.LINF);for (int j = 0; j < n; j++) {int l = dfst.beg[j], r = dfst.end[j];dp[j] = Longs.min(dp[j], seg.prod(l, r) + c + dt[j]);}min = LongArrays.min(dp);long[] tmp = dp; dp = pdp; pdp = tmp;}pw.println(min);}}class AdjacentList<T extends AbstractEdge> {public final boolean directed;public final int V;public final int E;private final int[] latest;private final int[] prev;private final T[] edge;int edgeCount;@SuppressWarnings("unchecked")public AdjacentList(int n, int m, boolean directed) {this.directed = directed;this.V = n;this.E = directed ? m : m << 1;this.latest = new int[V + 1];this.prev = new int[E + 1];this.edge = (T[]) new AbstractEdge[E + 1];}@SuppressWarnings("unchecked")public void addEdge(T edge) {addDirectedEdge(edge);if (!directed) {addDirectedEdge((T) edge.reverse());}}private void addDirectedEdge(T e) {edgeCount++;prev[edgeCount] = latest[e.from];latest[e.from] = edgeCount;edge[edgeCount] = e;}public void forEach(int u, Consumer<T> con) {for (int edgeId = latest[u]; edgeId > 0; edgeId = prev[edgeId]) {con.accept(edge[edgeId]);}}}class DFS<T extends AbstractEdge> {public final int V;public final int root;private final AdjacentList<T> adj;public final int[] par;public final int[] beg;public final int[] end;public DFS(AdjacentList<T> treeAdj, int root, Consumer<T> dfs) {this.V = treeAdj.V;this.root = root;this.adj = treeAdj;this.par = new int[V];this.beg = new int[V];this.end = new int[V];build(dfs);}private static final class Stack {private final int[] stack;private int ptr;Stack(int n) {this.stack = new int[n];}void push(int v) {stack[ptr++] = v;}int pop() {return stack[--ptr];}int size() {return ptr;}}private void build(Consumer<T> dfs) {Arrays.fill(par, -1);Stack stack = new Stack(V << 1);stack.push(~root);stack.push( root);int idx = 0;while (stack.size() > 0) {int u = stack.pop();if (u >= 0) {beg[u] = idx++;adj.forEach(u, e -> {int v = e.to;if (v != par[u]) {par[v] = u;stack.push(~v);stack.push( v);dfs.accept(e);}});} else {end[~u] = idx;}}}}class LongSegmentTree {final int MAX;final int N;final java.util.function.LongBinaryOperator op;final long E;final long[] data;public LongSegmentTree(int n, java.util.function.LongBinaryOperator op, long e) {this.MAX = n;int k = 1;while (k < n) k <<= 1;this.N = k;this.E = e;this.op = op;this.data = new long[N << 1];java.util.Arrays.fill(data, E);}public LongSegmentTree(long[] dat, java.util.function.LongBinaryOperator op, long e) {this(dat.length, op, e);build(dat);}private void build(long[] dat) {int l = dat.length;System.arraycopy(dat, 0, data, N, l);for (int i = N - 1; i > 0; i--) {data[i] = op.applyAsLong(data[i << 1 | 0], data[i << 1 | 1]);}}public void set(int p, long x) {exclusiveRangeCheck(p);data[p += N] = x;p >>= 1;while (p > 0) {data[p] = op.applyAsLong(data[p << 1 | 0], data[p << 1 | 1]);p >>= 1;}}public long get(int p) {exclusiveRangeCheck(p);return data[p + N];}public long prod(int l, int r) {if (l > r) {throw new IllegalArgumentException(String.format("Invalid range: [%d, %d)", l, r));}inclusiveRangeCheck(l);inclusiveRangeCheck(r);long sumLeft = E;long sumRight = E;l += N; r += N;while (l < r) {if ((l & 1) == 1) sumLeft = op.applyAsLong(sumLeft, data[l++]);if ((r & 1) == 1) sumRight = op.applyAsLong(data[--r], sumRight);l >>= 1; r >>= 1;}return op.applyAsLong(sumLeft, sumRight);}public long allProd() {return data[1];}public int maxRight(int l, java.util.function.LongPredicate f) {inclusiveRangeCheck(l);if (!f.test(E)) {throw new IllegalArgumentException("Identity element must satisfy the condition.");}if (l == MAX) return MAX;l += N;long sum = E;do {l >>= Integer.numberOfTrailingZeros(l);if (!f.test(op.applyAsLong(sum, data[l]))) {while (l < N) {l = l << 1;if (f.test(op.applyAsLong(sum, data[l]))) {sum = op.applyAsLong(sum, data[l]);l++;}}return l - N;}sum = op.applyAsLong(sum, data[l]);l++;} while ((l & -l) != l);return MAX;}public int minLeft(int r, java.util.function.LongPredicate f) {inclusiveRangeCheck(r);if (!f.test(E)) {throw new IllegalArgumentException("Identity element must satisfy the condition.");}if (r == 0) return 0;r += N;long sum = E;do {r--;while (r > 1 && (r & 1) == 1) r >>= 1;if (!f.test(op.applyAsLong(data[r], sum))) {while (r < N) {r = r << 1 | 1;if (f.test(op.applyAsLong(data[r], sum))) {sum = op.applyAsLong(data[r], sum);r--;}}return r + 1 - N;}sum = op.applyAsLong(data[r], sum);} while ((r & -r) != r);return 0;}private void exclusiveRangeCheck(int p) {if (p < 0 || p >= MAX) {throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for the range [%d, %d).", p, 0, MAX));}}private void inclusiveRangeCheck(int p) {if (p < 0 || p > MAX) {throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for the range [%d, %d].", p, 0, MAX));}}// **************** DEBUG **************** //private int indent = 6;public void setIndent(int newIndent) {this.indent = newIndent;}@Overridepublic String toString() {return toSimpleString();}public String toDetailedString() {return toDetailedString(1, 0);}private String toDetailedString(int k, int sp) {if (k >= N) return indent(sp) + data[k];String s = "";s += toDetailedString(k << 1 | 1, sp + indent);s += "\n";s += indent(sp) + data[k];s += "\n";s += toDetailedString(k << 1 | 0, sp + indent);return s;}private static String indent(int n) {StringBuilder sb = new StringBuilder();while (n --> 0) sb.append(' ');return sb.toString();}public String toSimpleString() {StringBuilder sb = new StringBuilder();sb.append('[');for (int i = 0; i < N; i++) {sb.append(data[i + N]);if (i < N - 1) sb.append(',').append(' ');}sb.append(']');return sb.toString();}}/*** @author https://atcoder.jp/users/suisen*/final class LongArrays {private LongArrays(){}public static void swap(long[] a, int u, int v) {long tmp = a[u]; a[u] = a[v]; a[v] = tmp;}public static void reverse(long[] a, int l, int r) {while (r - l > 1) swap(a, l++, --r);}public static void reverse(long[] a) {reverse(a, 0, a.length);}public static long sum(long[] a) {long sum = 0;for (long e : a) sum += e;return sum;}public static long max(long[] a) {long max = a[0];for (long e : a) max = Math.max(max, e);return max;}public static long min(long[] a) {long min = a[0];for (long e : a) min = Math.min(min, e);return min;}public static int argmax(long[] a) {long max = a[0];int argmax = 0;for (int i = 0; i < a.length; i++) if (max < a[i]) max = a[argmax = i];return argmax;}public static int argmin(long[] a) {long min = a[0];int argmin = 0;for (int i = 0; i < a.length; i++) if (min > a[i]) min = a[argmin = i];return argmin;}public static int find(long[] a, long v) {for (int i = 0; i < a.length; i++) if (a[i] == v) return i;return -1;}public static void permute(int[] p, long[] a) {int n = p.length;boolean[] settled = new boolean[n];for (int i = 0; i < n; i++) {for (int j = i; !settled[j]; j = p[j]) {if (p[j] == i) {settled[j] = true; break;}swap(a, j, p[j]);settled[j] = true;}}}public static void permute2(int[] p, long[] a, long[] b) {int n = p.length;boolean[] settled = new boolean[n];for (int i = 0; i < n; i++) {for (int j = i; !settled[j]; j = p[j]) {if (p[j] == i) {settled[j] = true; break;}swap(a, j, p[j]); swap(b, j, p[j]);settled[j] = true;}}}public static void permute3(int[] p, long[] a, long[] b, long[] c) {int n = p.length;boolean[] settled = new boolean[n];for (int i = 0; i < n; i++) {for (int j = i; !settled[j]; j = p[j]) {if (p[j] == i) {settled[j] = true; break;}swap(a, j, p[j]); swap(b, j, p[j]); swap(c, j, p[j]);settled[j] = true;}}}public static void permuteN(int[] p, long[]... as) {int n = p.length;boolean[] settled = new boolean[n];for (int i = 0; i < n; i++) {for (int j = i; !settled[j]; j = p[j]) {if (p[j] == i) {settled[j] = true; break;}for (long[] a : as) swap(a, j, p[j]);settled[j] = true;}}}public static int lowerBound(long[] sorted, long key) {int n = sorted.length;int l = -1, r = n;while (r - l > 1) {int m = (l + r) >> 1;if (sorted[m] < key) l = m;else r = m;}return r;}public static int upperBound(long[] sorted, long key) {int n = sorted.length;int l = -1, r = n;while (r - l > 1) {int m = (l + r) >> 1;if (sorted[m] <= key) l = m;else r = m;}return r;}public static int countOfRange(long[] sorted, long from, long to) {return lowerBound(sorted, to) - lowerBound(sorted, from);}public static String join(long[] a, String sep) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {sb.append(a[i]);if (i < a.length - 1) sb.append(sep);}return sb.toString();}public static String join(long[] a, char sep) {StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {sb.append(a[i]);if (i < a.length - 1) sb.append(sep);}return sb.toString();}}/*** @author https://atcoder.jp/users/suisen*/class FastScanner implements AutoCloseable {private final ByteBuffer tokenBuf = new ByteBuffer();private final java.io.InputStream in;private final byte[] rawBuf = new byte[1 << 14];private int ptr = 0;private int buflen = 0;public FastScanner(java.io.InputStream in) {this.in = in;}public FastScanner() {this(new java.io.FileInputStream(java.io.FileDescriptor.in));}private final int readByte() {if (ptr < buflen) return rawBuf[ptr++];ptr = 0;try {buflen = in.read(rawBuf);if (buflen > 0) {return rawBuf[ptr++];} else {throw new java.io.EOFException();}} catch (java.io.IOException e) {throw new java.io.UncheckedIOException(e);}}private final int readByteUnsafe() {if (ptr < buflen) return rawBuf[ptr++];ptr = 0;try {buflen = in.read(rawBuf);if (buflen > 0) {return rawBuf[ptr++];} else {return -1;}} catch (java.io.IOException e) {throw new java.io.UncheckedIOException(e);}}private final int skipUnprintableChars() {int b = readByte();while (b <= 32 || b >= 127) b = readByte();return b;}private final void loadToken() {tokenBuf.clear();for (int b = skipUnprintableChars(); 32 < b && b < 127; b = readByteUnsafe()) {tokenBuf.append(b);}}public final boolean hasNext() {for (int b = readByteUnsafe(); b <= 32 || b >= 127; b = readByteUnsafe()) {if (b == -1) return false;}--ptr;return true;}public final String next() {loadToken();return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());}public final String nextLine() {tokenBuf.clear();for (int b = readByte(); b != '\n'; b = readByteUnsafe()) {if (b == -1) break;tokenBuf.append(b);}return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());}public final char nextChar() {return (char) skipUnprintableChars();}public final char[] nextChars() {loadToken();return tokenBuf.toCharArray();}public final long nextLong() {long n = 0;boolean isNegative = false;int b = skipUnprintableChars();if (b == '-') {isNegative = true;b = readByteUnsafe();}if (b < '0' || '9' < b) throw new NumberFormatException();while ('0' <= b && b <= '9') {// -9223372036854775808 - 9223372036854775807if (n >= 922337203685477580l) {if (n > 922337203685477580l) {throw new ArithmeticException("long overflow");}if (isNegative) {if (b >= '9') {throw new ArithmeticException("long overflow");}n = -n - (b + '0');b = readByteUnsafe();if ('0' <= b && b <= '9') {throw new ArithmeticException("long overflow");} else if (b <= 32 || b >= 127) {return n;} else {throw new NumberFormatException();}} else {if (b >= '8') {throw new ArithmeticException("long overflow");}n = n * 10 + b - '0';b = readByteUnsafe();if ('0' <= b && b <= '9') {throw new ArithmeticException("long overflow");} else if (b <= 32 || b >= 127) {return n;} else {throw new NumberFormatException();}}}n = n * 10 + b - '0';b = readByteUnsafe();}if (b <= 32 || b >= 127) return isNegative ? -n : n;throw new NumberFormatException();}public final int nextInt() {long value = nextLong();if ((int) value != value) {throw new ArithmeticException("int overflow");}return (int) value;}public final double nextDouble() {return Double.parseDouble(next());}public final void close() {try {in.close();} catch (java.io.IOException e) {throw new java.io.UncheckedIOException(e);}}private static final class ByteBuffer {private static final int DEFAULT_BUF_SIZE = 1 << 12;private byte[] buf;private int ptr = 0;private ByteBuffer(int capacity) {this.buf = new byte[capacity];}private ByteBuffer() {this(DEFAULT_BUF_SIZE);}private ByteBuffer append(int b) {if (ptr == buf.length) {int newLength = buf.length << 1;byte[] newBuf = new byte[newLength];System.arraycopy(buf, 0, newBuf, 0, buf.length);buf = newBuf;}buf[ptr++] = (byte) b;return this;}private char[] toCharArray() {char[] chs = new char[ptr];for (int i = 0; i < ptr; i++) {chs[i] = (char) buf[i];}return chs;}private byte[] getRawBuf() {return buf;}private int size() {return ptr;}private void clear() {ptr = 0;}}}/*** @author https://atcoder.jp/users/suisen*/final class ExtendedScanner extends FastScanner {public ExtendedScanner() {super();}public ExtendedScanner(InputStream in) {super(in);}public int[] ints(final int n) {final int[] a = new int[n];Arrays.setAll(a, $ -> nextInt());return a;}public int[] ints(final int n, final IntUnaryOperator f) {final int[] a = new int[n];Arrays.setAll(a, $ -> f.applyAsInt(nextInt()));return a;}public int[][] ints(final int n, final int m) {final int[][] a = new int[n][];Arrays.setAll(a, $ -> ints(m));return a;}public int[][] ints(final int n, final int m, final IntUnaryOperator f) {final int[][] a = new int[n][];Arrays.setAll(a, $ -> ints(m, f));return a;}public long[] longs(final int n) {final long[] a = new long[n];Arrays.setAll(a, $ -> nextLong());return a;}public long[] longs(final int n, final LongUnaryOperator f) {final long[] a = new long[n];Arrays.setAll(a, $ -> f.applyAsLong(nextLong()));return a;}public long[][] longs(final int n, final int m) {final long[][] a = new long[n][];Arrays.setAll(a, $ -> longs(m));return a;}public long[][] longs(final int n, final int m, final LongUnaryOperator f) {final long[][] a = new long[n][];Arrays.setAll(a, $ -> longs(m, f));return a;}public char[][] charArrays(final int n) {final char[][] c = new char[n][];Arrays.setAll(c, $ -> nextChars());return c;}public double[] doubles(final int n) {final double[] a = new double[n];Arrays.setAll(a, $ -> nextDouble());return a;}public double[][] doubles(final int n, final int m) {final double[][] a = new double[n][];Arrays.setAll(a, $ -> doubles(m));return a;}public String[] strings(final int n) {final String[] s = new String[n];Arrays.setAll(s, $ -> next());return s;}}/*** @author https://atcoder.jp/users/suisen*/class FastPrintStream implements AutoCloseable {private static final int INT_MAX_LEN = 11;private static final int LONG_MAX_LEN = 20;private int precision = 9;private static final int BUF_SIZE = 1 << 14;private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN;private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN;private final byte[] buf = new byte[BUF_SIZE];private int ptr = 0;private final java.lang.reflect.Field strField;private final java.nio.charset.CharsetEncoder encoder;private final java.io.OutputStream out;public FastPrintStream(java.io.OutputStream out) {this.out = out;java.lang.reflect.Field f;try {f = java.lang.String.class.getDeclaredField("value");f.setAccessible(true);} catch (NoSuchFieldException | SecurityException e) {f = null;}this.strField = f;this.encoder = java.nio.charset.StandardCharsets.US_ASCII.newEncoder();}public FastPrintStream(java.io.File file) throws java.io.IOException {this(new java.io.FileOutputStream(file));}public FastPrintStream(java.lang.String filename) throws java.io.IOException {this(new java.io.File(filename));}public FastPrintStream() {this(new java.io.FileOutputStream(java.io.FileDescriptor.out));}public FastPrintStream println() {if (ptr == BUF_SIZE) internalFlush();buf[ptr++] = (byte) '\n';return this;}public FastPrintStream println(java.lang.Object o) {return print(o).println();}public FastPrintStream println(java.lang.String s) {return print(s).println();}public FastPrintStream println(char[] s) {return print(s).println();}public FastPrintStream println(char c) {return print(c).println();}public FastPrintStream println(int x) {return print(x).println();}public FastPrintStream println(long x) {return print(x).println();}public FastPrintStream println(double d, int precision) {return print(d, precision).println();}public FastPrintStream println(double d) {return print(d).println();}private FastPrintStream print(byte[] bytes) {int n = bytes.length;if (ptr + n > BUF_SIZE) {internalFlush();try {out.write(bytes);} catch (java.io.IOException e) {throw new java.io.UncheckedIOException(e);}} else {System.arraycopy(bytes, 0, buf, ptr, n);ptr += n;}return this;}public FastPrintStream print(java.lang.Object o) {return print(o.toString());}public FastPrintStream print(java.lang.String s) {if (strField == null) {return print(s.getBytes());} else {try {Object value = strField.get(s);if (value instanceof byte[]) {return print((byte[]) value);} else {return print((char[]) value);}} catch (IllegalAccessException e) {return print(s.getBytes());}}}public FastPrintStream print(char[] s) {try {return print(encoder.encode(java.nio.CharBuffer.wrap(s)).array());} catch (java.nio.charset.CharacterCodingException e) {byte[] bytes = new byte[s.length];for (int i = 0; i < s.length; i++) {bytes[i] = (byte) s[i];}return print(bytes);}}public FastPrintStream print(char c) {if (ptr == BUF_SIZE) internalFlush();buf[ptr++] = (byte) c;return this;}public FastPrintStream print(int x) {if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush();if (-10 < x && x < 10) {if (x < 0) {buf[ptr++] = '-';x = -x;}buf[ptr++] = (byte) ('0' + x);return this;}int d;if (x < 0) {if (x == Integer.MIN_VALUE) {buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4';buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3';buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8';return this;}d = len(x = -x);buf[ptr++] = '-';} else {d = len(x);}int j = ptr += d;while (x > 0) {buf[--j] = (byte) ('0' + (x % 10));x /= 10;}return this;}public FastPrintStream print(long x) {if ((int) x == x) return print((int) x);if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush();int d;if (x < 0) {if (x == Long.MIN_VALUE) {buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2';buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2';buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8';buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7';buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8';return this;}d = len(x = -x);buf[ptr++] = '-';} else {d = len(x);}int j = ptr += d;while (x > 0) {buf[--j] = (byte) ('0' + (x % 10));x /= 10;}return this;}public FastPrintStream print(double d, int precision) {if (d < 0) {print('-');d = -d;}d += Math.pow(10, -precision) / 2;print((long) d).print('.');d -= (long) d;for(int i = 0; i < precision; i++){d *= 10;print((int) d);d -= (int) d;}return this;}public FastPrintStream print(double d) {return print(d, precision);}public void setPrecision(int precision) {this.precision = precision;}private void internalFlush() {try {out.write(buf, 0, ptr);ptr = 0;} catch (java.io.IOException e) {throw new java.io.UncheckedIOException(e);}}public void flush() {try {out.write(buf, 0, ptr);out.flush();ptr = 0;} catch (java.io.IOException e) {throw new java.io.UncheckedIOException(e);}}public void close() {try {out.close();} catch (java.io.IOException e) {throw new java.io.UncheckedIOException(e);}}private static int len(int x) {returnx >= 1000000000 ? 10 :x >= 100000000 ? 9 :x >= 10000000 ? 8 :x >= 1000000 ? 7 :x >= 100000 ? 6 :x >= 10000 ? 5 :x >= 1000 ? 4 :x >= 100 ? 3 :x >= 10 ? 2 : 1;}private static int len(long x) {returnx >= 1000000000000000000l ? 19 :x >= 100000000000000000l ? 18 :x >= 10000000000000000l ? 17 :x >= 1000000000000000l ? 16 :x >= 100000000000000l ? 15 :x >= 10000000000000l ? 14 :x >= 1000000000000l ? 13 :x >= 100000000000l ? 12 :x >= 10000000000l ? 11 : 10;}}final class SimpleEdge extends AbstractEdge {public SimpleEdge(int from, int to, long cost) {super(from, to, cost);}public SimpleEdge(int from, int to) {super(from, to);}@Overridepublic SimpleEdge reverse() {return new SimpleEdge(to, from, cost);}}class Const {public static final long LINF = 1l << 59;public static final int IINF = (1 << 30) - 1;public static final double DINF = 1e150;public static final double SMALL = 1e-12;public static final double MEDIUM = 1e-9;public static final double LARGE = 1e-6;public static final long MOD1000000007 = 1000000007;public static final long MOD998244353 = 998244353 ;public static final long MOD754974721 = 754974721 ;public static final long MOD167772161 = 167772161 ;public static final long MOD469762049 = 469762049 ;public static final int[] dx8 = {1, 0, -1, 0, 1, -1, -1, 1};public static final int[] dy8 = {0, 1, 0, -1, 1, 1, -1, -1};public static final int[] dx4 = {1, 0, -1, 0};public static final int[] dy4 = {0, 1, 0, -1};}abstract class AbstractEdge implements Comparable<AbstractEdge> {public final int from, to;public final long cost;public AbstractEdge(int from, int to, long cost) {this.from = from;this.to = to;this.cost = cost;}public AbstractEdge(int from, int to) {this(from, to, 1l);}public abstract AbstractEdge reverse();public int compareTo(AbstractEdge o) {return Long.compare(cost, o.cost);}}/*** @author https://atcoder.jp/users/suisen*/final class Longs {private Longs(){}public static long max(long a, long b) {return Math.max(a, b);}public static long max(long a, long b, long c) {return Math.max(Math.max(a, b), c);}public static long max(long a, long b, long c, long d) {return Math.max(Math.max(Math.max(a, b), c), d);}public static long max(long a, long b, long c, long d, long e) {return Math.max(Math.max(Math.max(Math.max(a, b), c), d), e);}public static long max(long a, long b, long c, long d, long e, long f) {return Math.max(Math.max(Math.max(Math.max(Math.max(a, b), c), d), e), f);}public static long max(long a, long b, long c, long d, long e, long f, long g) {return Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(a, b), c), d), e), f), g);}public static long max(long a, long b, long c, long d, long e, long f, long g, long h) {return Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(Math.max(a, b), c), d), e), f), g), h);}public static long max(long a, long... vals) {long ret = a; for (long e : vals) ret = Math.max(ret, e);return ret;}public static long min(long a, long b) {return Math.min(a, b);}public static long min(long a, long b, long c) {return Math.min(Math.min(a, b), c);}public static long min(long a, long b, long c, long d) {return Math.min(Math.min(Math.min(a, b), c), d);}public static long min(long a, long b, long c, long d, long e) {return Math.min(Math.min(Math.min(Math.min(a, b), c), d), e);}public static long min(long a, long b, long c, long d, long e, long f) {return Math.min(Math.min(Math.min(Math.min(Math.min(a, b), c), d), e), f);}public static long min(long a, long b, long c, long d, long e, long f, long g) {return Math.min(Math.min(Math.min(Math.min(Math.min(Math.min(a, b), c), d), e), f), g);}public static long min(long a, long b, long c, long d, long e, long f, long g, long h) {return Math.min(Math.min(Math.min(Math.min(Math.min(Math.min(Math.min(a, b), c), d), e), f), g), h);}public static long min(long a, long... vals) {long ret = a; for (long e : vals) ret = Math.min(ret, e);return ret;}public static long fold(final LongBinaryOperator func, final long... a) {long ret = a[0]; for (int i = 1; i < a.length; i++) ret = func.applyAsLong(ret, a[i]);return ret;}public static boolean isPowerOfTwo(final long n) {return n != 0 && (-n & n) == n;}public static int ceilExponent(final long n) {return 63 - Long.numberOfLeadingZeros(n) + (isPowerOfTwo(n) ? 0 : 1);}public static int floorExponent(final long n) {return 63 - Long.numberOfLeadingZeros(n) + (n == 0 ? 1 : 0);}public static int ceilExponent(final long n, final int base) {if (base == 2) return ceilExponent(n);int i = 0;long m = 1;while (m < n) {i++;final long r = m * base;if ((m | base) >> 31 != 0 && r / base != m) break;m = r;}return i;}/*** @return ceil(a / b)*/public static long cld(long a, long b) {if (a > 0 && b > 0) return (a - 1) / b + 1;if (a < 0 && b < 0) return (a + 1) / b + 1;return a / b;}/*** @return floor(a / b)*/public static long fld(long a, long b) {if (a < 0 && b > 0) return (a + 1) / b - 1;if (a > 0 && b < 0) return (a - 1) / b - 1;return a / b;}/*** @return a * b <= c*/public static boolean mulLeq(long a, long b, long c) {if (a > 0) return b <= fld(c, a);if (a < 0) return b >= cld(c, a);return c >= 0;}/*** @return a * b < c*/public static boolean mulLt(long a, long b, long c) {if (a > 0) return b < cld(c, a);if (a < 0) return b > fld(c, a);return c > 0;}/*** @return a * b >= c*/public static boolean mulGeq(long a, long b, long c) {if (a > 0) return b >= cld(c, a);if (a < 0) return b <= fld(c, a);return c <= 0;}/*** @return a * b > c*/public static boolean mulGt(long a, long b, long c) {if (a > 0) return b > fld(c, a);if (a < 0) return b < cld(c, a);return c < 0;}/*** @return max{v | v <= a / b}*/public static long leqDiv(long a, long b) {return fld(a, b);}/*** @return max{v | v < a / b}*/public static long ltDiv(long a, long b) {return cld(a, b) - 1;}/*** @return min{v | v >= a / b}*/public static long geqDiv(long a, long b) {return cld(a, b);}/*** @return min{v | v > a / b}*/public static long gtDiv(long a, long b) {return fld(a, b) + 1;}public static String join(final String sep, final long... a) {final StringBuilder sb = new StringBuilder();for (int i = 0; i < a.length; i++) {sb.append(a[i]);if (i < a.length - 1) sb.append(sep);}return sb.toString();}}