結果
| 問題 | No.2606 Mirror Relay |
| ユーザー |
 uwi
|
| 提出日時 | 2024-01-12 22:25:56 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 553 ms / 2,000 ms |
| コード長 | 26,090 bytes |
| コンパイル時間 | 7,920 ms |
| コンパイル使用メモリ | 99,016 KB |
| 実行使用メモリ | 78,896 KB |
| 最終ジャッジ日時 | 2024-09-27 22:57:38 |
| 合計ジャッジ時間 | 29,163 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 69 |
ソースコード
package no2xxx;import java.io.*;import java.util.*;import java.util.function.IntUnaryOperator;import java.util.function.LongUnaryOperator;public class No2606 {InputStream is;FastWriter out;String INPUT = "";public void solve(){char[] s = ns().toCharArray();PalindromicTree pt = PalindromicTree.build(s);List<Node> ns = new ArrayList<>();// for(Node no : pt.nodes){// tr(no);// }int[] sa = suffixArray(s);int[] lcp = lcpArray(s, sa);int n = s.length;int[] isa = new int[n];for(int i = 0;i < n;i++){isa[sa[i]] = i;}SegmentTreeRMQ st = new SegmentTreeRMQ(lcp);// tr(sa);// tr(lcp);SegmentTreeRMQL stl = new SegmentTreeRMQL(n);Arrays.sort(pt.nodes, (l, r) -> l.len - r.len);long[] dp = new long[pt.nodes.length];for(int i = pt.nodes.length-1;i >= 2;i--){Node no = pt.nodes[i];int f = no.first;int l = st.lastle(isa[f]-1, no.len-1);int r = st.firstle(isa[f], no.len-1);if(r == -1)r = n-1;// (l,r]int ind = isa[f];// tr(l, r);dp[i] = -Math.min(0L, stl.min(l+1, r+1)) + (long)no.len * no.freq;stl.update(ind, -Math.max(dp[i], -stl.min(ind, ind+1)));}out.println(-stl.min(0, n));}public static class SegmentTreeRMQL {public final int M, H, N;public long[] vals;public static final long I = Long.MAX_VALUE;public SegmentTreeRMQL(int n){N = n;M = Integer.highestOneBit(Math.max(N-1, 1))<<2;H = M>>>1;vals = new long[M];Arrays.fill(vals, 0, M, I);}public SegmentTreeRMQL(int[] a){this(a.length);for(int i = 0;i < N;i++){vals[H+i] = a[i];}// Arrays.fill(vals, H+N, M, I);for(int i = H-1;i >= 1;i--)propagate(i);}public void update(int pos, long x){vals[H+pos] = x;for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);}private void propagate(int i){vals[i] = Math.min(vals[2*i], vals[2*i+1]);}public long min(int l, int r){long min = I;if(l >= r)return min;l += H; r += H;for(;l < r;l>>>=1,r>>>=1){if((l&1) == 1)min = Math.min(min, vals[l++]);if((r&1) == 1)min = Math.min(min, vals[--r]);}return min;}public int firstle(int l, long v) {if(l >= H)return -1;int cur = H+l;while(true){if(vals[cur] <= v){if(cur >= H)return cur-H;cur = 2*cur;}else{cur++;if((cur&cur-1) == 0)return -1;if((cur&1)==0)cur>>>=1;}}}public int lastle(int l, long v) {if(l < 0)return -1;int cur = H+l;while(true){if(vals[cur] <= v){if(cur >= H)return cur-H;cur = 2*cur + 1;}else{if((cur&cur-1) == 0)return -1;cur--;if((cur&1)==1)cur>>>=1;}}}}public static class SegmentTreeRMQ {public final int M, H, N;public int[] vals;public static final int I = Integer.MAX_VALUE;public SegmentTreeRMQ(int n){N = n;M = Integer.highestOneBit(Math.max(N-1, 1))<<2;H = M>>>1;vals = new int[M];Arrays.fill(vals, 0, M, I);}public SegmentTreeRMQ(int[] a){this(a.length);for(int i = 0;i < N;i++){vals[H+i] = a[i];}// Arrays.fill(vals, H+N, M, I);for(int i = H-1;i >= 1;i--)propagate(i);}public void update(int pos, int x){vals[H+pos] = x;for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);}private void propagate(int i){vals[i] = Math.min(vals[2*i], vals[2*i+1]);}public int min(int l, int r){int min = I;if(l >= r)return min;l += H; r += H;for(;l < r;l>>>=1,r>>>=1){if((l&1) == 1)min = Math.min(min, vals[l++]);if((r&1) == 1)min = Math.min(min, vals[--r]);}return min;}public int firstle(int l, int v) {if(l >= H)return -1;int cur = H+l;while(true){if(vals[cur] <= v){if(cur >= H)return cur-H;cur = 2*cur;}else{cur++;if((cur&cur-1) == 0)return -1;if((cur&1)==0)cur>>>=1;}}}public int lastle(int l, int v) {if(l < 0)return -1;int cur = H+l;while(true){if(vals[cur] <= v){if(cur >= H)return cur-H;cur = 2*cur + 1;}else{if((cur&cur-1) == 0)return -1;cur--;if((cur&1)==1)cur>>>=1;}}}}private static int[] saNaive(int[] s) {int n = s.length;int[] sa = new int[n];for(int i = 0;i < n;i++){sa[i] = i;}insertionsortUsingComparator(sa, (l, r) -> {while (l < n && r < n) {if (s[l] != s[r]) return s[l] - s[r];l++;r++;}return -(l - r);});return sa;}private static int[] saDoubling(int[] s) {int n = s.length;int[] sa = new int[n];for(int i = 0;i < n;i++){sa[i] = i;}int[] rnk = java.util.Arrays.copyOf(s, n);int[] tmp = new int[n];for (int k = 1; k < n; k *= 2) {final int _k = k;final int[] _rnk = rnk;java.util.function.IntBinaryOperator cmp = (x, y) -> {if (_rnk[x] != _rnk[y]) return _rnk[x] - _rnk[y];int rx = x + _k < n ? _rnk[x + _k] : -1;int ry = y + _k < n ? _rnk[y + _k] : -1;return rx - ry;};mergesortUsingComparator(sa, cmp);tmp[sa[0]] = 0;for (int i = 1; i < n; i++) {tmp[sa[i]] = tmp[sa[i - 1]] + (cmp.applyAsInt(sa[i - 1], sa[i]) < 0 ? 1 : 0);}int[] buf = tmp;tmp = rnk;rnk = buf;}return sa;}private static void insertionsortUsingComparator(int[] a, java.util.function.IntBinaryOperator comparator) {final int n = a.length;for (int i = 1; i < n; i++) {final int tmp = a[i];if (comparator.applyAsInt(a[i - 1], tmp) > 0) {int j = i;do {a[j] = a[j - 1];j--;} while (j > 0 && comparator.applyAsInt(a[j - 1], tmp) > 0);a[j] = tmp;}}}private static void mergesortUsingComparator(int[] a, java.util.function.IntBinaryOperator comparator) {final int n = a.length;final int[] work = new int[n];for (int block = 1; block <= n; block <<= 1) {final int block2 = block << 1;for (int l = 0, max = n - block; l < max; l += block2) {int m = l + block;int r = Math.min(l + block2, n);System.arraycopy(a, l, work, 0, block);for (int i = l, wi = 0, ti = m;; i++) {if (ti == r) {System.arraycopy(work, wi, a, i, block - wi);break;}if (comparator.applyAsInt(work[wi], a[ti]) > 0) {a[i] = a[ti++];} else {a[i] = work[wi++];if (wi == block) break;}}}}}private static final int THRESHOLD_NAIVE = 50;private static final int THRESHOLD_DOUBLING = 0;private static int[] sais(int[] s, int upper) {int n = s.length;if (n == 0) return new int[0];if (n == 1) return new int[]{0};if (n == 2) {if (s[0] < s[1]) {return new int[]{0, 1};} else {return new int[]{1, 0};}}if (n < THRESHOLD_NAIVE) {return saNaive(s);}// if (n < THRESHOLD_DOUBLING) {// return saDoubling(s);// }int[] sa = new int[n];boolean[] ls = new boolean[n];for (int i = n - 2; i >= 0; i--) {ls[i] = s[i] == s[i + 1] ? ls[i + 1] : s[i] < s[i + 1];}int[] sumL = new int[upper + 1];int[] sumS = new int[upper + 1];for (int i = 0; i < n; i++) {if (ls[i]) {sumL[s[i] + 1]++;} else {sumS[s[i]]++;}}for (int i = 0; i <= upper; i++) {sumS[i] += sumL[i];if (i < upper) sumL[i + 1] += sumS[i];}java.util.function.Consumer<int[]> induce = lms -> {java.util.Arrays.fill(sa, -1);int[] buf = new int[upper + 1];System.arraycopy(sumS, 0, buf, 0, upper + 1);for (int d : lms) {if (d == n) continue;sa[buf[s[d]]++] = d;}System.arraycopy(sumL, 0, buf, 0, upper + 1);sa[buf[s[n - 1]]++] = n - 1;for (int i = 0; i < n; i++) {int v = sa[i];if (v >= 1 && !ls[v - 1]) {sa[buf[s[v - 1]]++] = v - 1;}}System.arraycopy(sumL, 0, buf, 0, upper + 1);for (int i = n - 1; i >= 0; i--) {int v = sa[i];if (v >= 1 && ls[v - 1]) {sa[--buf[s[v - 1] + 1]] = v - 1;}}};int[] lmsMap = new int[n + 1];java.util.Arrays.fill(lmsMap, -1);int m = 0;for (int i = 1; i < n; i++) {if (!ls[i - 1] && ls[i]) {lmsMap[i] = m++;}}int[] lms = new int[m];{int p = 0;for (int i = 1; i < n; i++) {if (!ls[i - 1] && ls[i]) {lms[p++] = i;}}}induce.accept(lms);if (m > 0) {int[] sortedLms = new int[m];{int p = 0;for (int v : sa) {if (lmsMap[v] != -1) {sortedLms[p++] = v;}}}int[] recS = new int[m];int recUpper = 0;recS[lmsMap[sortedLms[0]]] = 0;for (int i = 1; i < m; i++) {int l = sortedLms[i - 1], r = sortedLms[i];int endL = (lmsMap[l] + 1 < m) ? lms[lmsMap[l] + 1] : n;int endR = (lmsMap[r] + 1 < m) ? lms[lmsMap[r] + 1] : n;boolean same = true;if (endL - l != endR - r) {same = false;} else {while (l < endL && s[l] == s[r]) {l++;r++;}if (l == n || s[l] != s[r]) same = false;}if (!same) {recUpper++;}recS[lmsMap[sortedLms[i]]] = recUpper;}int[] recSA = sais(recS, recUpper);for (int i = 0; i < m; i++) {sortedLms[i] = lms[recSA[i]];}induce.accept(sortedLms);}return sa;}public static int[] suffixArray(int[] s, int upper) {assert (0 <= upper);for (int d : s) {assert (0 <= d && d <= upper);}return sais(s, upper);}public static int[] suffixArray(int[] s){int n = s.length;int[] vals = Arrays.copyOf(s, n);java.util.Arrays.sort(vals);int p = 1;for(int i = 1;i < n;i++){if(vals[i] != vals[i-1]){vals[p++] = vals[i];}}int[] s2 = new int[n];for(int i = 0;i < n;i++){s2[i] = java.util.Arrays.binarySearch(vals, 0, p, s[i]);}return sais(s2, p);}public static int[] suffixArray(char[] s) {int n = s.length;int[] s2 = new int[n];for (int i = 0; i < n; i++) {s2[i] = s[i];}return sais(s2, 255);}public static int[] suffixArray(java.lang.String s) {return suffixArray(s.toCharArray());}public static int[] lcpArray(int[] s, int[] sa) {int n = s.length;assert (n >= 1);int[] rnk = new int[n];for (int i = 0; i < n; i++) {rnk[sa[i]] = i;}int[] lcp = new int[n - 1];int h = 0;for (int i = 0; i < n; i++) {if (h > 0) h--;if (rnk[i] == 0) {continue;}int j = sa[rnk[i] - 1];for (; j + h < n && i + h < n; h++) {if (s[j + h] != s[i + h]) break;}lcp[rnk[i] - 1] = h;}return lcp;}public static int[] lcpArray(char[] s, int[] sa) {int n = s.length;int[] s2 = new int[n];for (int i = 0; i < n; i++) {s2[i] = s[i];}return lcpArray(s2, sa);}public static int[] lcpArray(java.lang.String s, int[] sa) {return lcpArray(s.toCharArray(), sa);}public static int[] zAlgorithm(int[] s) {int n = s.length;if (n == 0) return new int[0];int[] z = new int[n];for (int i = 1, j = 0; i < n; i++) {int k = j + z[j] <= i ? 0 : Math.min(j + z[j] - i, z[i - j]);while (i + k < n && s[k] == s[i + k]) k++;z[i] = k;if (j + z[j] < i + z[i]) j = i;}z[0] = n;return z;}public static int[] zAlgorithm(char[] s) {int n = s.length;if (n == 0) return new int[0];int[] z = new int[n];for (int i = 1, j = 0; i < n; i++) {int k = j + z[j] <= i ? 0 : Math.min(j + z[j] - i, z[i - j]);while (i + k < n && s[k] == s[i + k]) k++;z[i] = k;if (j + z[j] < i + z[i]) j = i;}z[0] = n;return z;}public static int[] zAlgorithm(String s) {return zAlgorithm(s.toCharArray());}public static class Node{public int id, first, len, freq;public char c;public Node firstChild;public Node next;public Node link;private Node(int first, int len, char c, int id) {this.first = first;this.len = len;this.c = c;this.id = id;this.freq = 0;}public Node next(char x){for(Node ch = this.firstChild;ch != null;ch = ch.next){if(ch.c == x)return ch;}return null;}public void add(Node x){Node ch = this.firstChild;this.firstChild = x;x.next = ch;}@Overridepublic String toString() {return "Node [id=" + id + ", first=" + first + ", len=" + len + ", freq=" + freq + ", c=" + c+ ", firstChild=" + (firstChild != null ? firstChild.id : null) + ", sibling=" + (next != null ? next.id : null)+ ", link=" + (link != null ? link.id : null) + "]";}}public static class PalindromicTree {public Node[] nodes; // [0]=hell, [1]=len0public static PalindromicTree build(char[] s){int n = s.length;Node zero = new Node(-1, 0, (char)0, 1);Node hell = new Node(-1, -1, (char)0, 0);zero.link = hell;hell.link = hell;hell.add(zero);Node[] nodes = new Node[n+2];int p = 0;nodes[p++] = hell;nodes[p++] = zero;Node cur = zero; // current suffix palindromefor(int i = 0;i < n;i++){char x = s[i];while(i-cur.len-1 < 0 || s[i-cur.len-1] != x)cur = cur.link; // find xAxNode xax = cur.next(x); // already existsif(xax == null){// new subpalindromexax = new Node(i-cur.len-1, cur.len+2, x, p);nodes[p++] = xax;cur.add(xax);// make suffix linkif(xax.len == 1){xax.link = zero;}else{Node b = cur.link;while(true){while(i-b.len-1 < 0 || s[i-b.len-1] != x)b = b.link; // find xBxNode xbx = b.next(x);if(xbx != null){xax.link = xbx;break;}}}}// [i-cur.len-1, i]xax.freq++; // increment regardless new or notcur = xax;}for(int i = p-1;i >= 2;i--){nodes[i].link.freq += nodes[i].freq;}PalindromicTree pt = new PalindromicTree();pt.nodes = Arrays.copyOf(nodes, p);return pt;}public String toDot(boolean next, boolean suffixLink){StringBuilder sb = new StringBuilder("digraph{\n");sb.append("graph[rankdir=LR];\n");sb.append("node[shape=circle];\n");for(Node n : nodes){if(n != null){if(suffixLink && n.link != null){sb.append("\"" + n.id + "\"").append("->").append("\"" + n.link.id + "\"").append("[style=dashed];\n");}if(next){for(Node ch = n.firstChild;ch != null;ch = ch.next){sb.append("\"" + n.id + "\"").append("->").append("\"" + ch.id + "\"").append("[label=\"").append(ch.c == 0 ? ' ' : ch.c).append("\"];\n");}}}}sb.append("}\n");return sb.toString();}}public static void main(String[] args) {new No2606().run();}public void run(){long S = System.currentTimeMillis();is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new FastWriter(System.out);solve();out.flush();long G = System.currentTimeMillis();tr(G-S+"ms");// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){// @Override// public void run() {// long s = System.currentTimeMillis();// solve();// out.flush();// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// }// };// t.start();// t.join();}private boolean eof(){if(lenbuf == -1)return true;int lptr = ptrbuf;while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;try {is.mark(1000);while(true){int b = is.read();if(b == -1){is.reset();return true;}else if(!isSpaceChar(b)){is.reset();return false;}}} catch (IOException e) {return true;}}private final byte[] inbuf = new byte[1024];public int lenbuf = 0, ptrbuf = 0;private int readByte(){if(lenbuf == -1)throw new InputMismatchException();if(ptrbuf >= lenbuf){ptrbuf = 0;try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }if(lenbuf <= 0)return -1;}return inbuf[ptrbuf++];}private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }// private boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }private double nd() { return Double.parseDouble(ns()); }private char nc() { return (char)skip(); }private String ns(){int b = skip();StringBuilder sb = new StringBuilder();while(!(isSpaceChar(b))){sb.appendCodePoint(b);b = readByte();}return sb.toString();}private char[] ns(int n){char[] buf = new char[n];int b = skip(), p = 0;while(p < n && !(isSpaceChar(b))){buf[p++] = (char)b;b = readByte();}return n == p ? buf : Arrays.copyOf(buf, p);}private char[][] nm(int n, int m){char[][] map = new char[n][];for(int i = 0;i < n;i++)map[i] = ns(m);return map;}private int[][] nmi(int n, int m){int[][] map = new int[n][];for(int i = 0;i < n;i++)map[i] = na(m);return map;}private int[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private long[] nal(int n){long[] a = new long[n];for(int i = 0;i < n;i++)a[i] = nl();return a;}private int ni(){int num = 0, b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private long nl(){long num = 0;int b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}public static class FastWriter{private static final int BUF_SIZE = 1<<13;private final byte[] buf = new byte[BUF_SIZE];private final OutputStream out;private int ptr = 0;private FastWriter(){out = null;}public FastWriter(OutputStream os){this.out = os;}public FastWriter(String path){try {this.out = new FileOutputStream(path);} catch (FileNotFoundException e) {throw new RuntimeException("FastWriter");}}public FastWriter write(byte b){buf[ptr++] = b;if(ptr == BUF_SIZE)innerflush();return this;}public FastWriter write(char c){return write((byte)c);}public FastWriter write(char[] s){for(char c : s){buf[ptr++] = (byte)c;if(ptr == BUF_SIZE)innerflush();}return this;}public FastWriter write(String s){s.chars().forEach(c -> {buf[ptr++] = (byte)c;if(ptr == BUF_SIZE)innerflush();});return this;}private static int countDigits(int l) {if (l >= 1000000000) return 10;if (l >= 100000000) return 9;if (l >= 10000000) return 8;if (l >= 1000000) return 7;if (l >= 100000) return 6;if (l >= 10000) return 5;if (l >= 1000) return 4;if (l >= 100) return 3;if (l >= 10) return 2;return 1;}public FastWriter write(int x){if(x == Integer.MIN_VALUE){return write((long)x);}if(ptr + 12 >= BUF_SIZE)innerflush();if(x < 0){write((byte)'-');x = -x;}int d = countDigits(x);for(int i = ptr + d - 1;i >= ptr;i--){buf[i] = (byte)('0'+x%10);x /= 10;}ptr += d;return this;}private static int countDigits(long l) {if (l >= 1000000000000000000L) return 19;if (l >= 100000000000000000L) return 18;if (l >= 10000000000000000L) return 17;if (l >= 1000000000000000L) return 16;if (l >= 100000000000000L) return 15;if (l >= 10000000000000L) return 14;if (l >= 1000000000000L) return 13;if (l >= 100000000000L) return 12;if (l >= 10000000000L) return 11;if (l >= 1000000000L) return 10;if (l >= 100000000L) return 9;if (l >= 10000000L) return 8;if (l >= 1000000L) return 7;if (l >= 100000L) return 6;if (l >= 10000L) return 5;if (l >= 1000L) return 4;if (l >= 100L) return 3;if (l >= 10L) return 2;return 1;}public FastWriter write(long x){if(x == Long.MIN_VALUE){return write("" + x);}if(ptr + 21 >= BUF_SIZE)innerflush();if(x < 0){write((byte)'-');x = -x;}int d = countDigits(x);for(int i = ptr + d - 1;i >= ptr;i--){buf[i] = (byte)('0'+x%10);x /= 10;}ptr += d;return this;}public FastWriter write(double x, int precision){if(x < 0){write('-');x = -x;}x += Math.pow(10, -precision)/2;// if(x < 0){ x = 0; }write((long)x).write(".");x -= (long)x;for(int i = 0;i < precision;i++){x *= 10;write((char)('0'+(int)x));x -= (int)x;}return this;}public FastWriter writeln(char c){ return write(c).writeln(); }public FastWriter writeln(int x){ return write(x).writeln(); }public FastWriter writeln(long x){ return write(x).writeln(); }public FastWriter writeln(double x, int precision){ return write(x, precision).writeln(); }public FastWriter write(int... xs){boolean first = true;for(int x : xs) {if (!first) write(' ');first = false;write(x);}return this;}public FastWriter write(long... xs){boolean first = true;for(long x : xs) {if (!first) write(' ');first = false;write(x);}return this;}public FastWriter write(IntUnaryOperator f, int... xs){boolean first = true;for(int x : xs) {if (!first) write(' ');first = false;write(f.applyAsInt(x));}return this;}public FastWriter write(LongUnaryOperator f, long... xs){boolean first = true;for(long x : xs) {if (!first) write(' ');first = false;write(f.applyAsLong(x));}return this;}public FastWriter writeln(){return write((byte)'\n');}public FastWriter writeln(int... xs) { return write(xs).writeln(); }public FastWriter writeln(long... xs) { return write(xs).writeln(); }public FastWriter writeln(IntUnaryOperator f, int... xs) { return write(f, xs).writeln(); }public FastWriter writeln(LongUnaryOperator f, long... xs) { return write(f, xs).writeln(); }public FastWriter writeln(char[] line) { return write(line).writeln(); }public FastWriter writeln(char[]... map) { for(char[] line : map)write(line).writeln();return this; }public FastWriter writeln(String s) { return write(s).writeln(); }private void innerflush(){try {out.write(buf, 0, ptr);ptr = 0;} catch (IOException e) {throw new RuntimeException("innerflush");}}public void flush(){innerflush();try {out.flush();} catch (IOException e) {throw new RuntimeException("flush");}}public FastWriter print(byte b) { return write(b); }public FastWriter print(char c) { return write(c); }public FastWriter print(char[] s) { return write(s); }public FastWriter print(String s) { return write(s); }public FastWriter print(int x) { return write(x); }public FastWriter print(long x) { return write(x); }public FastWriter print(double x, int precision) { return write(x, precision); }public FastWriter println(char c){ return writeln(c); }public FastWriter println(int x){ return writeln(x); }public FastWriter println(long x){ return writeln(x); }public FastWriter println(double x, int precision){ return writeln(x, precision); }public FastWriter print(int... xs) { return write(xs); }public FastWriter print(long... xs) { return write(xs); }public FastWriter print(IntUnaryOperator f, int... xs) { return write(f, xs); }public FastWriter print(LongUnaryOperator f, long... xs) { return write(f, xs); }public FastWriter println(int... xs) { return writeln(xs); }public FastWriter println(long... xs) { return writeln(xs); }public FastWriter println(IntUnaryOperator f, int... xs) { return writeln(f, xs); }public FastWriter println(LongUnaryOperator f, long... xs) { return writeln(f, xs); }public FastWriter println(char[] line) { return writeln(line); }public FastWriter println(char[]... map) { return writeln(map); }public FastWriter println(String s) { return writeln(s); }public FastWriter println() { return writeln(); }}public static void trnz(int... o){for(int i = 0;i < o.length;i++)if(o[i] != 0)System.out.print(i+":"+o[i]+" ");System.out.println();}// print ids which are 1public static void trt(long... o){Queue<Integer> stands = new ArrayDeque<>();for(int i = 0;i < o.length;i++){for(long x = o[i];x != 0;x &= x-1)stands.add(i<<6|Long.numberOfTrailingZeros(x));}System.out.println(stands);}public static void tf(boolean... r){for(boolean x : r)System.out.print(x?'#':'.');System.out.println();}public static void tf(boolean[]... b){for(boolean[] r : b) {for(boolean x : r)System.out.print(x?'#':'.');System.out.println();}System.out.println();}public void tf(long[]... b){if(INPUT.length() != 0) {for (long[] r : b) {for (long x : r) {for (int i = 0; i < 64; i++) {System.out.print(x << ~i < 0 ? '#' : '.');}}System.out.println();}System.out.println();}}public void tf(long... b){if(INPUT.length() != 0) {for (long x : b) {for (int i = 0; i < 64; i++) {System.out.print(x << ~i < 0 ? '#' : '.');}}System.out.println();}}private void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }}