import java.io.EOFException; import java.io.File; import java.io.FileDescriptor; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.UncheckedIOException; import java.lang.reflect.Field; import java.nio.CharBuffer; import java.nio.charset.CharacterCodingException; import java.nio.charset.CharsetEncoder; import java.nio.charset.StandardCharsets; import java.util.Arrays; import java.util.Iterator; import java.util.List; import java.util.Objects; import java.util.PrimitiveIterator; import java.util.function.IntUnaryOperator; 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(); } public static void solve(ExtendedScanner sc, FastPrintStream pw) { int n = sc.nextInt(); int q = sc.nextInt(); long[] a = sc.longs(n); long[] s = CumulativeSum.build(a); DynamicIntArray b = new DynamicIntArray(n + 1, i -> i); for (int i = 0; i < q; i++) { int t = sc.nextInt(); int l = sc.nextInt(); int r = sc.nextInt(); if (t == 1) { b.eraseRange(l, r); } else { pw.println(s[b.get(r)] - s[b.get(l - 1)]); } } } } /** * @author https://atcoder.jp/users/suisen */ final class CumulativeSum { public static int[] build(int[] a) { int n = a.length; int[] s = new int[n + 1]; for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1]; return s; } public static int[][] build(int[][] a) { int n = a.length, m = a[0].length; int[][] s = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) System.arraycopy(a[i - 1], 0, s[i], 1, m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { s[i][j] += s[i - 1][j]; } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { s[i][j] += s[i][j - 1]; } return s; } public static int[][][] build(int[][][] a) { int n = a.length, m = a[0].length, l = a[0][0].length; int[][][] s = new int[n + 1][m + 1][l + 1]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) System.arraycopy(a[i - 1][j - 1], 0, s[i][j], 1, l); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= l; k++) { s[i][j][k] += s[i - 1][j][k]; } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= l; k++) { s[i][j][k] += s[i][j - 1][k]; } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= l; k++) { s[i][j][k] += s[i][j][k - 1]; } return s; } public static long[] build(long[] a) { int n = a.length; long[] s = new long[n + 1]; for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1]; return s; } public static long[][] build(long[][] a) { int n = a.length; int m = a[0].length; long[][] s = new long[n + 1][m + 1]; for (int i = 1; i <= n; i++) System.arraycopy(a[i - 1], 0, s[i], 1, m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { s[i][j] += s[i - 1][j]; } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { s[i][j] += s[i][j - 1]; } return s; } public static long[][][] build(long[][][] a) { int n = a.length, m = a[0].length, l = a[0][0].length; long[][][] s = new long[n + 1][m + 1][l + 1]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) System.arraycopy(a[i - 1][j - 1], 0, s[i][j], 1, l); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= l; k++) { s[i][j][k] += s[i - 1][j][k]; } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= l; k++) { s[i][j][k] += s[i][j - 1][k]; } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= l; k++) { s[i][j][k] += s[i][j][k - 1]; } return s; } public static int sum(int[] s, int l, int r) { return s[r] - s[l]; } public static long sum(long[] s, int l, int r) { return s[r] - s[l]; } public static int sum(int[][] s, int y1, int x1, int y2, int x2) { return s[y2][x2] - s[y1][x2] - s[y2][x1] + s[y1][x1]; } public static long sum(long[][] s, int y1, int x1, int y2, int x2) { return s[y2][x2] - s[y1][x2] - s[y2][x1] + s[y1][x1]; } public static int sum(int[][][] s, int i1, int j1, int k1, int i2, int j2, int k2) { int p0 = s[i2][j2][k2]; int n1 = s[i1][j2][k2] + s[i2][j1][k2] + s[i2][j2][k1]; int p2 = s[i1][j1][k2] + s[i2][j1][k1] + s[i1][j2][k1]; int n3 = s[i1][j1][k1]; return p0 - n1 + p2 - n3; } public static long sum(long[][][] s, int i1, int j1, int k1, int i2, int j2, int k2) { long p0 = s[i2][j2][k2]; long n1 = s[i1][j2][k2] + s[i2][j1][k2] + s[i2][j2][k1]; long p2 = s[i1][j1][k2] + s[i2][j1][k1] + s[i1][j2][k1]; long n3 = s[i1][j1][k1]; return p0 - n1 + p2 - n3; } } class DynamicIntArray implements Cloneable { private static final Object DUMMY = new Object(); private IntRandomizedBinarySearchTree root; public DynamicIntArray() {} public DynamicIntArray(int n, IntUnaryOperator generator) { for (int i = 0; i < n; i++) addLast(generator.applyAsInt(i)); } public DynamicIntArray(int n, int initialValue) { this(n, i -> initialValue); } public DynamicIntArray(int[] a) { this(a.length, i -> a[i]); } private DynamicIntArray(IntRandomizedBinarySearchTree root) { this.root = root; } public int size() { return IntRandomizedBinarySearchTree.size(root); } public int get(int index) { return IntRandomizedBinarySearchTree.getKthKey(root, index); } public int set(int index, int newVal) { indexBoundsCheck(index); return IntRandomizedBinarySearchTree.setKthKey(root, index, newVal); } public void addLast(int val) { root = IntRandomizedBinarySearchTree.insert(root, size(), val, DUMMY); } public void eraseRange(int l, int r) { root = IntRandomizedBinarySearchTree.eraseRange(root, l, r); } public Pair split(int k) { Pair, IntRandomizedBinarySearchTree> p = IntRandomizedBinarySearchTree.split(root, k); DynamicIntArray fst = new DynamicIntArray(p.fst); DynamicIntArray snd = new DynamicIntArray(p.snd); return new Pair<>(fst, snd); } public void mergeRight(DynamicIntArray a) { root = IntRandomizedBinarySearchTree.merge(root, a.root); } public void mergeLeft(DynamicIntArray a) { root = IntRandomizedBinarySearchTree.merge(a.root, root); } private void indexBoundsCheck(int i) { if (i < 0 || i >= size()) throw new IndexOutOfBoundsException( String.format("index %d out of bounds for the length %d.", i, size()) ); } public PrimitiveIterator.OfInt iterator() { return IntRandomizedBinarySearchTree.keyIterator(root); } @Override public String toString() { StringBuilder sb = new StringBuilder().append('['); int n = size(); for (PrimitiveIterator.OfInt it = iterator(); it.hasNext();) { sb.append(it.nextInt()); if (0 <-- n) sb.append(','); } return sb.append(']').toString(); } @Override public DynamicIntArray clone() { return new DynamicIntArray(size(), i -> get(i)); } } class IntRandomizedBinarySearchTree extends IntEntry { IntRandomizedBinarySearchTree l, r; int size; IntRandomizedBinarySearchTree(int key, V val) {super(key, val); this.size = 1;} private IntRandomizedBinarySearchTree update() { size = size(l) + size(r) + 1; return this; } private static final Random rnd = new Random(); static int getKthKey(IntRandomizedBinarySearchTree t, int k) { int c = IntRandomizedBinarySearchTree.size(t.l); if (k < c) return getKthKey(t.l, k); if (k == c) return t.key; return getKthKey(t.r, k - c - 1); } static int setKthKey(IntRandomizedBinarySearchTree t, int k, int newKey) { int c = IntRandomizedBinarySearchTree.size(t.l); if (k < c) return setKthKey(t.l, k, newKey); if (k == c) { int oldKey = t.key; t.key = newKey; return oldKey; } return setKthKey(t.r, k - c - 1, newKey); } static IntRandomizedBinarySearchTree merge(IntRandomizedBinarySearchTree l, IntRandomizedBinarySearchTree r) { if (l == null) return r; if (r == null) return l; if (rnd.nextInt(l.size + r.size) < l.size) { l.r = merge(l.r, r); return l.update(); } else { r.l = merge(l, r.l); return r.update(); } } static Pair, IntRandomizedBinarySearchTree> split(IntRandomizedBinarySearchTree x, int k) { if (k < 0 || k > size(x)) { throw new IndexOutOfBoundsException( String.format("index %d is out of bounds for the length of %d", k, size(x)) ); } if (x == null) return new Pair<>(null, null); Pair, IntRandomizedBinarySearchTree> p; if (k <= size(x.l)) { p = split(x.l, k); x.l = p.snd; p.snd = x.update(); } else { p = split(x.r, k - size(x.l) - 1); x.r = p.fst; p.fst = x.update(); } return p; } static IntRandomizedBinarySearchTree insert(IntRandomizedBinarySearchTree t, int k, int key, V val) { Pair, IntRandomizedBinarySearchTree> p = split(t, k); return merge(merge(p.fst, new IntRandomizedBinarySearchTree<>(key, val)), p.snd); } static IntRandomizedBinarySearchTree erase(IntRandomizedBinarySearchTree t, int k) { Pair, IntRandomizedBinarySearchTree> p = split(t, k); IntRandomizedBinarySearchTree l = p.fst; IntRandomizedBinarySearchTree r = split(p.snd, 1).snd; return merge(l, r); } static IntRandomizedBinarySearchTree eraseRange(IntRandomizedBinarySearchTree t, int from, int to) { Pair, IntRandomizedBinarySearchTree> p = split(t, from); IntRandomizedBinarySearchTree l = p.fst; IntRandomizedBinarySearchTree r = split(p.snd, to - from).snd; return merge(l, r); } static int size(IntRandomizedBinarySearchTree nd) {return nd == null ? 0 : nd.size;} static Iterator> iterator(IntRandomizedBinarySearchTree nd) { return nd == null ? IterUtil.emptyIterator() : nd.iterator(); } static PrimitiveIterator.OfInt keyIterator(IntRandomizedBinarySearchTree nd) { return nd == null ? IterUtil.emptyIntIterator() : nd.keyIterator(); } private Iterator> iterator() { Iterator> it = List.>of(this).iterator(); if (l != null) it = IterUtil.concatIterators(l.iterator(), it); if (r != null) it = IterUtil.concatIterators(it, r.iterator()); return it; } private PrimitiveIterator.OfInt keyIterator() { PrimitiveIterator.OfInt it = IterUtil.ofIntIterator(key); if (l != null) it = IterUtil.concatIntIterators(l.keyIterator(), it); if (r != null) it = IterUtil.concatIntIterators(it, r.keyIterator()); return it; } } /** * @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 Field strField; private final CharsetEncoder encoder; private final OutputStream out; public FastPrintStream(OutputStream out) { this.out = out; Field f; try { f = String.class.getDeclaredField("value"); f.setAccessible(true); } catch (NoSuchFieldException | SecurityException e) { f = null; } this.strField = f; this.encoder = StandardCharsets.US_ASCII.newEncoder(); } public FastPrintStream(File file) throws IOException { this(new FileOutputStream(file)); } public FastPrintStream(String filename) throws IOException { this(new File(filename)); } public FastPrintStream() { this(new FileOutputStream(FileDescriptor.out)); } public FastPrintStream println() { if (ptr == BUF_SIZE) internalFlush(); buf[ptr++] = (byte) '\n'; return this; } public FastPrintStream println(Object o) { return print(o).println(); } public FastPrintStream println(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 (IOException e) { throw new UncheckedIOException(e); } } else { System.arraycopy(bytes, 0, buf, ptr, n); ptr += n; } return this; } public FastPrintStream print(Object o) { return print(o.toString()); } public FastPrintStream print(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(CharBuffer.wrap(s)).array()); } catch (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 (IOException e) { throw new UncheckedIOException(e); } } public void flush() { try { out.write(buf, 0, ptr); out.flush(); ptr = 0; } catch (IOException e) { throw new UncheckedIOException(e); } } public void close() { try { out.close(); } catch (IOException e) { throw new UncheckedIOException(e); } } private static int len(int x) { return x >= 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) { return x >= 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; } } /** * @author https://atcoder.jp/users/suisen */ class FastScanner implements AutoCloseable { private final ByteBuffer tokenBuf = new ByteBuffer(); public final InputStream in; private final byte[] rawBuf = new byte[1 << 14]; private int ptr = 0; private int buflen = 0; public FastScanner(InputStream in) { this.in = in; } public FastScanner() { this(new FileInputStream(FileDescriptor.in)); } private int readByte() { if (ptr < buflen) return rawBuf[ptr++]; ptr = 0; try { buflen = in.read(rawBuf); if (buflen > 0) { return rawBuf[ptr++]; } else { throw new EOFException(); } } catch (IOException e) { throw new UncheckedIOException(e); } } private 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 (IOException e) { throw new UncheckedIOException(e); } } private int skipUnprintableChars() { int b = readByte(); while (b <= 32 || b >= 127) b = readByte(); return b; } private 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 - 9223372036854775807 if (n >= 922337203685477580L) { if (n > 922337203685477580L) { throw new ArithmeticException("long overflow"); } if (isNegative) { if (b >= '9') { throw new ArithmeticException("long overflow"); } n = -n - (b - '0'); } 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 (IOException e) { throw new UncheckedIOException(e); } } @SuppressWarnings("UnusedReturnValue") private static final class ByteBuffer { private static final int DEFAULT_BUF_SIZE = 1 << 12; private byte[] buf; private int ptr = 0; private ByteBuffer(@SuppressWarnings("SameParameterValue") 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; } } } final class Random { private static final double DOUBLE_UNIT = 0x1.0p-53; private int x = 123456789; private int y = 362436069; private int z = 521288629; private int w = 88675123; public int nextInt() { int t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } public long nextLong() { return ((long) (nextInt()) << 32) + nextInt(); } public int nextInt(int bound) { return nextInt() % bound; } public boolean nextBoolean() { return (nextInt() & 1) == 0; } public double nextDouble() { return (((long) (next(26)) << 27) + next(27)) * DOUBLE_UNIT; } private int next(int bits) { int mask = bits == 32 ? -1 : (1 << bits) - 1; return nextInt() & mask; } } class IterUtil { private static final Iterator EMPTY_ITERATOR = new Iterator<>(){ public boolean hasNext() {return false;} public Object next() {throw new UnsupportedOperationException();} }; private static final PrimitiveIterator.OfInt EMPTY_INT_ITERATOR = new PrimitiveIterator.OfInt(){ public boolean hasNext() {return false;} public int nextInt() {throw new UnsupportedOperationException();} }; private static final PrimitiveIterator.OfLong EMPTY_LONG_ITERATOR = new PrimitiveIterator.OfLong(){ public boolean hasNext() {return false;} public long nextLong() {throw new UnsupportedOperationException();} }; private static final PrimitiveIterator.OfDouble EMPTY_DOUBLE_ITERATOR = new PrimitiveIterator.OfDouble(){ public boolean hasNext() {return false;} public double nextDouble() {throw new UnsupportedOperationException();} }; @SuppressWarnings("unchecked") private static final Iterable EMPTY_ITERABLE = () -> (Iterator) EMPTY_ITERATOR; public static PrimitiveIterator.OfInt emptyIntIterator() {return EMPTY_INT_ITERATOR;} public static PrimitiveIterator.OfLong emptyLongIterator() {return EMPTY_LONG_ITERATOR;} public static PrimitiveIterator.OfDouble emptyDoubleIterator() {return EMPTY_DOUBLE_ITERATOR;} @SuppressWarnings("unchecked") public static Iterator emptyIterator() {return (Iterator) EMPTY_ITERATOR;} @SuppressWarnings("unchecked") public static Iterable emptyIterable() {return (Iterable) EMPTY_ITERABLE;} private static Iterator concatIterators(Iterator> iterIterator) { return new Iterator(){ Iterator it = emptyIterator(); public boolean hasNext() { while (!it.hasNext()) { if (!iterIterator.hasNext()) return false; it = iterIterator.next(); } return true; } public V next() {return it.next();} }; } private static PrimitiveIterator.OfInt concatIntIterators(Iterator iterIterator) { return new PrimitiveIterator.OfInt(){ PrimitiveIterator.OfInt it = emptyIntIterator(); public boolean hasNext() { while (!it.hasNext()) { if (!iterIterator.hasNext()) return false; it = iterIterator.next(); } return true; } public int nextInt() {return it.nextInt();} }; } private static PrimitiveIterator.OfLong concatLongIterators(Iterator iterIterator) { return new PrimitiveIterator.OfLong(){ PrimitiveIterator.OfLong it = emptyLongIterator(); public boolean hasNext() { while (!it.hasNext()) { if (!iterIterator.hasNext()) return false; it = iterIterator.next(); } return true; } public long nextLong() {return it.nextLong();} }; } private static PrimitiveIterator.OfDouble concatDoubleIterators(Iterator iterIterator) { return new PrimitiveIterator.OfDouble(){ PrimitiveIterator.OfDouble it = emptyDoubleIterator(); public boolean hasNext() { while (!it.hasNext()) { if (!iterIterator.hasNext()) return false; it = iterIterator.next(); } return true; } public double nextDouble() {return it.nextDouble();} }; } private static Iterable concatIterables(Iterator> iterIterator) { return () -> new Iterator(){ Iterator it = emptyIterator(); public boolean hasNext() { while (!it.hasNext()) { if (!iterIterator.hasNext()) return false; it = iterIterator.next().iterator(); } return true; } public V next() {return it.next();} }; } public static Iterator concatIterators(Iterator it1, Iterator it2) { return concatIterators(List.of(it1, it2).iterator()); } public static Iterator concatIterators(Iterator it1, Iterator it2, Iterator it3) { return concatIterators(List.of(it1, it2, it3).iterator()); } public static Iterator concatIterators(Iterator it1, Iterator it2, Iterator it3, Iterator it4) { return concatIterators(List.of(it1, it2, it3, it4).iterator()); } public static Iterator concatIterators(Iterable> its) { return concatIterators(its.iterator()); } public static PrimitiveIterator.OfInt concatIntIterators(PrimitiveIterator.OfInt it1, PrimitiveIterator.OfInt it2) { return concatIntIterators(List.of(it1, it2).iterator()); } public static PrimitiveIterator.OfInt concatIntIterators(PrimitiveIterator.OfInt it1, PrimitiveIterator.OfInt it2, PrimitiveIterator.OfInt it3) { return concatIntIterators(List.of(it1, it2, it3).iterator()); } public static PrimitiveIterator.OfInt concatIntIterators(PrimitiveIterator.OfInt it1, PrimitiveIterator.OfInt it2, PrimitiveIterator.OfInt it3, PrimitiveIterator.OfInt it4) { return concatIntIterators(List.of(it1, it2, it3, it4).iterator()); } public static PrimitiveIterator.OfInt concatIntIterators(Iterable its) { return concatIntIterators(its.iterator()); } public static PrimitiveIterator.OfLong concatLongIterators(PrimitiveIterator.OfLong it1, PrimitiveIterator.OfLong it2) { return concatLongIterators(List.of(it1, it2).iterator()); } public static PrimitiveIterator.OfLong concatLongIterators(PrimitiveIterator.OfLong it1, PrimitiveIterator.OfLong it2, PrimitiveIterator.OfLong it3) { return concatLongIterators(List.of(it1, it2, it3).iterator()); } public static PrimitiveIterator.OfLong concatLongIterators(PrimitiveIterator.OfLong it1, PrimitiveIterator.OfLong it2, PrimitiveIterator.OfLong it3, PrimitiveIterator.OfLong it4) { return concatLongIterators(List.of(it1, it2, it3, it4).iterator()); } public static PrimitiveIterator.OfLong concatLongIterators(Iterable its) { return concatLongIterators(its.iterator()); } public static PrimitiveIterator.OfDouble concatDoubleIterators(PrimitiveIterator.OfDouble it1, PrimitiveIterator.OfDouble it2) { return concatDoubleIterators(List.of(it1, it2).iterator()); } public static PrimitiveIterator.OfDouble concatDoubleIterators(PrimitiveIterator.OfDouble it1, PrimitiveIterator.OfDouble it2, PrimitiveIterator.OfDouble it3) { return concatDoubleIterators(List.of(it1, it2, it3).iterator()); } public static PrimitiveIterator.OfDouble concatDoubleIterators(PrimitiveIterator.OfDouble it1, PrimitiveIterator.OfDouble it2, PrimitiveIterator.OfDouble it3, PrimitiveIterator.OfDouble it4) { return concatDoubleIterators(List.of(it1, it2, it3, it4).iterator()); } public static PrimitiveIterator.OfDouble concatDoubleIterators(Iterable its) { return concatDoubleIterators(its.iterator()); } public static Iterable concatIterables(Iterable it1, Iterable it2) { return concatIterables(List.of(it1, it2)); } public static Iterable concatIterables(Iterable it1, Iterable it2, Iterable it3) { return concatIterables(List.of(it1, it2, it3)); } public static Iterable concatIterables(Iterable it1, Iterable it2, Iterable it3, Iterable it4) { return concatIterables(List.of(it1, it2, it3, it4)); } public static Iterable concatIterables(Iterable> its) { return concatIterables(its.iterator()); } public static PrimitiveIterator.OfInt ofIntIterator(int e) { return new PrimitiveIterator.OfInt(){ boolean seen; public boolean hasNext() {return !seen;} public int nextInt() {seen = true; return e;} }; } public static PrimitiveIterator.OfLong ofLongIterator(long e) { return new PrimitiveIterator.OfLong(){ boolean seen; public boolean hasNext() {return !seen;} public long nextLong() {seen = true; return e;} }; } public static PrimitiveIterator.OfDouble ofIntIterator(double e) { return new PrimitiveIterator.OfDouble(){ boolean seen; public boolean hasNext() {return !seen;} public double nextDouble() {seen = true; return e;} }; } } class IntEntry { public int key; public V val; public IntEntry(int key, V val) { this.key = key; this.val = val; } public int getKey() {return key;} public V getValue() {return val;} public V setValue(V val) { V oldValue = this.val; this.val = val; return oldValue; } public boolean equals(Object o) { if (!(o instanceof IntEntry)) return false; IntEntry e = (IntEntry) o; return key == e.getKey() && Objects.equals(val, e.val); } public int hashCode() { int keyHash = key; int valueHash = (val == null ? 0 : val.hashCode()); return keyHash ^ valueHash; } public String toString() {return key + "=" + val;} } /** * @author https://atcoder.jp/users/suisen */ final class Pair { public E0 fst; public E1 snd; public Pair(final E0 fst, final E1 snd) {this.fst = fst; this.snd = snd;} @Override @SuppressWarnings("all") public boolean equals(final Object o) { if (this == o) return true; if (!(o instanceof Pair)) return false; final Pair p = (Pair) o; return this.fst.equals(p.fst) && this.snd.equals(p.snd); } @Override public int hashCode() {return Objects.hash(this.fst, this.snd);} @Override public String toString() {return "(" + this.fst.toString() + ", " + this.snd.toString() + ")";} }