結果
| 問題 | No.2361 Many String Compare Queries |
| ユーザー |
 遭難者
|
| 提出日時 | 2023-01-13 14:34:11 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 35,193 bytes |
| コンパイル時間 | 4,593 ms |
| コンパイル使用メモリ | 98,324 KB |
| 実行使用メモリ | 71,984 KB |
| 最終ジャッジ日時 | 2024-06-30 20:39:38 |
| 合計ジャッジ時間 | 9,904 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 11 RE * 3 |
ソースコード
import java.util.*;import java.io.*;class Main {private static final void solve() throws IOException {final int n = ni(), q_ = ni(), n1 = n - 1;var s = sc.nextCharArray();var a = StringAlgorithm.suffixArray(s);var b = StringAlgorithm.lcpArray(s, a);var a_inv = new int[n];for (int i = 0; i < n; i++)a_inv[a[i]] = i;var len = new long[n];for (int i = 0; i < n; i++)len[i] = n - a[i];for (int i = 1; i < n; i++)len[i] += len[i - 1];var seg = new SegTree(b, n1);var p = new long[n1];for (int i = n1 - 1; i >= 0; i--) {int l = seg.minLeft(i + 1, b[i] + 1);p[i] = b[i];p[i] *= l - i;if (l != n1)p[i] += p[l];}// verified pfor (int qq = 0; qq < q_; qq++) {final int ll = ni() - 1, rr = ni();final int l = a_inv[ll], x = rr - ll;long ans1 = 1L, ans2 = 0L;if (l != 0) {int z = seg.maxRight(l - 1, x);if (z != -1)ans2 += len[z];ans1 += l - 1 - z;}if (l + 1 != n) {int y = seg.minLeft(l, x);if (y != n1)ans2 += p[y];ans1 += y - l;}ou.println(ans1 * (x - 1) + ans2);}}private static final int gu(char[] s, int l, int r, int n) {int ans = 0;int aa = r - l;var a = new char[aa];for (int k1 = 0, k2 = l; k1 < aa; k1++, k2++)a[k1] = s[k2];for (int j = 0; j <= n; j++) {for (int i = 0; i < j; i++) {final int m = j - i;var ss = new char[m];for (int k1 = 0, k2 = i; k1 < m; k1++, k2++)ss[k1] = s[k2];if (cmp(a, ss))ans++;}}return ans;}private static final boolean cmp(char[] s1, char[] s2) {int n = Math.min(s1.length, s2.length);for (int i = 0; i < n; i++)if (s1[i] != s2[i])return s1[i] > s2[i];return s1.length > s2.length;}public static void main(String[] args) throws IOException {solve();ou.flush();}private static final int ni() throws IOException {return sc.nextInt();}private static final int[] ni(int n) throws IOException {return sc.nextIntArray(n);}private static final long nl() throws IOException {return sc.nextLong();}private static final long[] nl(int n) throws IOException {return sc.nextLongArray(n);}private static final String ns() throws IOException {return sc.next();}private static final double nd() throws IOException {return sc.nextDouble();}private static final ContestInputStream sc = new ContestInputStream();private static final ContestOutputStream ou = new ContestOutputStream();}final class SegTree {private final int N, N2;private final int[] data;private final int INF;public SegTree(int n, int INF) {int n2 = 1;while (n2 < n)n2 <<= 1;N2 = n2;N = N2 << 1;data = new int[N];this.INF = INF;Arrays.fill(data, INF);}public SegTree(int[] d, int INF) {this(d.length, INF);int idx = N2;for (int i : d)data[idx++] = i;for (int i = N2 - 1; i > 0; i--) {final int ii = i << 1;data[i] = Math.min(data[ii], data[ii | 1]);}}private int prod(int a, int b, int k, int l, int r) {if (r <= a || b <= l)return INF;if (a <= l && r <= b)return data[k];final int ty = l + r >> 1;final int ii = k << 1;final int d1 = prod(a, b, ii, l, ty);final int d2 = prod(a, b, ii + 1, ty, r);return Math.min(d1, d2);}public int prod(int l, int r) {return prod(l, r, 1, 0, N2);}public void set(int i, int x) {i += N2;data[i] = x;while (i != 1) {i >>= 1;final int ii = i << 1;data[i] = Math.min(data[ii], data[ii | 1]);}}// min_{l<=i<=idx} A_i < jud を満たす最大の lpublic int maxRight(int idx, int jud) {return maxRight(idx, jud, 1, 0, N2);}private int maxRight(int idx, int jud, int k, int l, int r) {if (data[k] >= jud || idx < l)return -1;if (k >= N2)return k - N2;final int ii = k << 1;final int ty = l + r >> 1;int koh = maxRight(idx, jud, ii | 1, ty, r);if (koh != -1)return koh;return maxRight(idx, jud, ii, l, ty);}// min_{idx<=i<=r} A_i < jud を満たす最小のrpublic int minLeft(int idx, int jud) {return minLeft(idx, jud, 1, 0, N2);}private int minLeft(int idx, int jud, int k, int l, int r) {if (data[k] >= jud || r <= idx)return INF;if (k >= N2)return k - N2;final int ii = k << 1;final int ty = l + r >> 1;int koh = minLeft(idx, jud, ii, l, ty);if (koh != INF)return koh;return minLeft(idx, jud, ii | 1, ty, r);}}class StringAlgorithm {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());}}final class ContestInputStream extends FilterInputStream {protected final byte[] buf;protected int pos = 0;protected int lim = 0;private final char[] cbuf;public ContestInputStream() {super(System.in);this.buf = new byte[1 << 13];this.cbuf = new char[1 << 20];}boolean hasRemaining() throws IOException {if (pos < lim)return true;lim = in.read(buf);pos = 0;return lim > 0;}final int remaining() throws IOException {if (pos >= lim) {lim = in.read(buf);pos = 0;}return lim - pos;}@Overridepublic final int available() throws IOException {if (pos < lim)return lim - pos + in.available();return in.available();}@Overridepublic final long skip(long n) throws IOException {if (pos < lim) {int rem = lim - pos;if (n < rem) {pos += n;return n;}pos = lim;return rem;}return in.skip(n);}@Overridepublic final int read() throws IOException {if (hasRemaining())return buf[pos++];return -1;}@Overridepublic final int read(byte[] b, int off, int len) throws IOException {if (pos < lim) {int rem = Math.min(lim - pos, len);for (int i = 0; i < rem; i++)b[off + i] = buf[pos + i];pos += rem;return rem;}return in.read(b, off, len);}public final char[] readToken() throws IOException {int cpos = 0;int rem;byte b;l: while ((rem = remaining()) > 0) {for (int i = 0; i < rem; i++) {b = buf[pos + i];if (b <= 0x20) {pos += i + 1;cpos += i;if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;break l;}cbuf[cpos + i] = (char) b;}pos += rem;cpos += rem;}char[] arr = new char[cpos];for (int i = 0; i < cpos; i++)arr[i] = cbuf[i];return arr;}public final int readToken(char[] cbuf, int off) throws IOException {int cpos = off;int rem;byte b;l: while ((rem = remaining()) > 0) {for (int i = 0; i < rem; i++) {b = buf[pos + i];if (b <= 0x20) {pos += i + 1;cpos += i;if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;break l;}cbuf[cpos + i] = (char) b;}pos += rem;cpos += rem;}return cpos - off;}public final int readToken(char[] cbuf) throws IOException {return readToken(cbuf, 0);}public final String next() throws IOException {int cpos = 0;int rem;byte b;l: while ((rem = remaining()) > 0) {for (int i = 0; i < rem; i++) {b = buf[pos + i];if (b <= 0x20) {pos += i + 1;cpos += i;if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;break l;}cbuf[cpos + i] = (char) b;}pos += rem;cpos += rem;}return String.valueOf(cbuf, 0, cpos);}public final char[] nextCharArray() throws IOException {return readToken();}public final int nextInt() throws IOException {if (!hasRemaining())return 0;int value = 0;byte b = buf[pos++];if (b == 0x2d) {while (hasRemaining() && (b = buf[pos++]) > 0x20)value = value * 10 - b + 0x30;} else {do {value = value * 10 + b - 0x30;} while (hasRemaining() && (b = buf[pos++]) > 0x20);}if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;return value;}public final long nextLong() throws IOException {if (!hasRemaining())return 0L;long value = 0L;byte b = buf[pos++];if (b == 0x2d) {while (hasRemaining() && (b = buf[pos++]) > 0x20)value = value * 10 - b + 0x30;} else {do {value = value * 10 + b - 0x30;} while (hasRemaining() && (b = buf[pos++]) > 0x20);}if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;return value;}public final char nextChar() throws IOException {if (!hasRemaining())throw new EOFException();final char c = (char) buf[pos++];if (hasRemaining() && buf[pos++] == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;return c;}public final float nextFloat() throws IOException {return Float.parseFloat(next());}public final double nextDouble() throws IOException {return Double.parseDouble(next());}public final boolean[] nextBooleanArray(char ok) throws IOException {char[] s = readToken();int n = s.length;boolean[] t = new boolean[n];for (int i = 0; i < n; i++)t[i] = s[i] == ok;return t;}public final boolean[][] nextBooleanMatrix(int h, int w, char ok) throws IOException {boolean[][] s = new boolean[h][];for (int i = 0; i < h; i++) {char[] t = readToken();int n = t.length;s[i] = new boolean[n];for (int j = 0; j < n; j++)s[i][j] = t[j] == ok;}return s;}public final String[] nextStringArray(int len) throws IOException {String[] arr = new String[len];for (int i = 0; i < len; i++)arr[i] = next();return arr;}public final int[] nextIntArray(int len) throws IOException {int[] arr = new int[len];for (int i = 0; i < len; i++)arr[i] = nextInt();return arr;}public final int[] nextIntArray(int len, java.util.function.IntUnaryOperator map) throws IOException {int[] arr = new int[len];for (int i = 0; i < len; i++)arr[i] = map.applyAsInt(nextInt());return arr;}public final long[] nextLongArray(int len, java.util.function.LongUnaryOperator map) throws IOException {long[] arr = new long[len];for (int i = 0; i < len; i++)arr[i] = map.applyAsLong(nextLong());return arr;}public final int[][] nextIntMatrix(int h, int w) throws IOException {int[][] arr = new int[h][w];for (int i = 0; i < h; i++)for (int j = 0; j < w; j++)arr[i][j] = nextInt();return arr;}public final int[][] nextIntMatrix(int h, int w, java.util.function.IntUnaryOperator map) throws IOException {int[][] arr = new int[h][w];for (int i = 0; i < h; i++)for (int j = 0; j < w; j++)arr[i][j] = map.applyAsInt(nextInt());return arr;}public final long[] nextLongArray(int len) throws IOException {long[] arr = new long[len];for (int i = 0; i < len; i++)arr[i] = nextLong();return arr;}public final long[][] nextLongMatrix(int h, int w) throws IOException {long[][] arr = new long[h][w];for (int i = 0; i < h; i++)for (int j = 0; j < w; j++)arr[i][j] = nextLong();return arr;}public final float[] nextFloatArray(int len) throws IOException {float[] arr = new float[len];for (int i = 0; i < len; i++)arr[i] = nextFloat();return arr;}public final double[] nextDoubleArray(int len) throws IOException {double[] arr = new double[len];for (int i = 0; i < len; i++)arr[i] = nextDouble();return arr;}public final char[][] nextCharMatrix(int h, int w) throws IOException {char[][] arr = new char[h][];for (int i = 0; i < h; i++)arr[i] = readToken();return arr;}public final void nextThrow() throws IOException {next();return;}public final void nextThrow(int n) throws IOException {for (int i = 0; i < n; i++)nextThrow();return;}}final class ContestOutputStream extends FilterOutputStream implements Appendable {protected final byte[] buf;protected int pos = 0;public ContestOutputStream() {super(System.out);this.buf = new byte[1 << 13];}@Overridepublic void flush() throws IOException {out.write(buf, 0, pos);pos = 0;out.flush();}void put(byte b) throws IOException {if (pos >= buf.length)flush();buf[pos++] = b;}int remaining() throws IOException {if (pos >= buf.length)flush();return buf.length - pos;}@Overridepublic void write(int b) throws IOException {put((byte) b);}@Overridepublic void write(byte[] b, int off, int len) throws IOException {int o = off;int l = len;while (l > 0) {int rem = Math.min(remaining(), l);for (int i = 0; i < rem; i++)buf[pos + i] = b[o + i];pos += rem;o += rem;l -= rem;}}@Overridepublic ContestOutputStream append(char c) throws IOException {put((byte) c);return this;}@Overridepublic ContestOutputStream append(CharSequence csq, int start, int end) throws IOException {int off = start;int len = end - start;while (len > 0) {int rem = Math.min(remaining(), len);for (int i = 0; i < rem; i++)buf[pos + i] = (byte) csq.charAt(off + i);pos += rem;off += rem;len -= rem;}return this;}@Overridepublic ContestOutputStream append(CharSequence csq) throws IOException {return append(csq, 0, csq.length());}public ContestOutputStream append(char[] arr, int off, int len) throws IOException {int o = off;int l = len;while (l > 0) {int rem = Math.min(remaining(), l);for (int i = 0; i < rem; i++)buf[pos + i] = (byte) arr[o + i];pos += rem;o += rem;l -= rem;}return this;}public ContestOutputStream print(char[] arr) throws IOException {return append(arr, 0, arr.length).newLine();}public ContestOutputStream print(boolean value) throws IOException {if (value)return append("o");return append("x");}public ContestOutputStream println(boolean value) throws IOException {if (value)return append("o\n");return append("x\n");}public ContestOutputStream print(boolean[][] value) throws IOException {final int n = value.length, m = value[0].length;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++)print(value[i][j]);newLine();}return this;}public ContestOutputStream print(int value) throws IOException {return append(String.valueOf(value));}public ContestOutputStream println(int value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream print(long value) throws IOException {return append(String.valueOf(value));}public ContestOutputStream println(long value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream print(float value) throws IOException {return append(String.valueOf(value));}public ContestOutputStream println(float value) throws IOException {return append(String.valueOf(value)).newLine();}private ContestOutputStream dtos(double x, int n) throws IOException {if (x < 0) {append('-');x = -x;}x += Math.pow(10, -n) / 2;long longx = (long) x;print(longx);append('.');x -= longx;for (int i = 0; i < n; i++) {x *= 10;int intx = (int) x;print(intx);x -= intx;}return this;}public ContestOutputStream print(double value) throws IOException {return dtos(value, 20);}public ContestOutputStream println(double value) throws IOException {return dtos(value, 20).newLine();}public ContestOutputStream print(char value) throws IOException {return append(value);}public ContestOutputStream println(char value) throws IOException {return append(value).newLine();}public ContestOutputStream print(String value) throws IOException {return append(value);}public ContestOutputStream println(String value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream print(Object value) throws IOException {return append(String.valueOf(value));}public ContestOutputStream println(Object value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream printYN(boolean yes) throws IOException {if (yes)return println("Yes");return println("No");}public ContestOutputStream printAB(boolean yes) throws IOException {if (yes)return println("Alice");return println("Bob");}public ContestOutputStream print(CharSequence[] arr) throws IOException {if (arr.length > 0) {append(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').append(arr[i]);}return this;}public ContestOutputStream print(int[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}newLine();return this;}public ContestOutputStream print(int[] arr, int length) throws IOException {if (length > 0)print(arr[0]);for (int i = 1; i < length; i++)append('\u0020').print(arr[i]);newLine();return this;}public ContestOutputStream println(int[] arr) throws IOException {for (int i : arr)print(i).newLine();return this;}public ContestOutputStream println(int[] arr, int length) throws IOException {for (int i = 0; i < length; i++)println(arr[i]);return this;}public ContestOutputStream print(boolean[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}newLine();return this;}public ContestOutputStream print(long[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}newLine();return this;}public ContestOutputStream print(long[] arr, int length) throws IOException {if (length > 0)print(arr[0]);for (int i = 1; i < length; i++)append('\u0020').print(arr[i]);newLine();return this;}public ContestOutputStream println(long[] arr, int length) throws IOException {for (int i = 0; i < length; i++)println(arr[i]);return this;}public ContestOutputStream println(long[] arr) throws IOException {for (long i : arr)print(i).newLine();return this;}public ContestOutputStream print(float[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}return this;}public ContestOutputStream println(float[] arr) throws IOException {for (float i : arr)print(i).newLine();return this;}public ContestOutputStream print(double[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}return newLine();}public ContestOutputStream println(double[] arr) throws IOException {for (double i : arr)print(i).newLine();return this;}public ContestOutputStream print(java.util.ArrayList<?> arr) throws IOException {if (!arr.isEmpty()) {final int n = arr.size();print(arr.get(0));for (int i = 1; i < n; i++)print(" ").print(arr.get(i));}return newLine();}public ContestOutputStream println(java.util.ArrayList<?> arr) throws IOException {final int n = arr.size();for (int i = 0; i < n; i++)println(arr.get(i));return this;}public ContestOutputStream newLine() throws IOException {return append(System.lineSeparator());}public ContestOutputStream endl() throws IOException {newLine().flush();return this;}public ContestOutputStream print(int[][] arr) throws IOException {for (int[] i : arr)print(i);return this;}public ContestOutputStream print(long[][] arr) throws IOException {for (long[] i : arr)print(i);return this;}public ContestOutputStream print(char[][] arr) throws IOException {for (char[] i : arr)print(i);return this;}public ContestOutputStream print(Object[][] arr) throws IOException {for (Object[] i : arr)print(i);return this;}public ContestOutputStream println() throws IOException {return newLine();}public ContestOutputStream print(Object... arr) throws IOException {for (Object i : arr)print(i);return this;}public ContestOutputStream println(Object... arr) throws IOException {for (Object i : arr)print(i);return newLine();}}