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);
        IntOrderedSet set = new IntOrderedSet();
        for (int i = 0; i <= n; i++) {
            set.add(i);
        }
        for (int i = 0; i < q; i++) {
            int t = sc.nextInt();
            int x = sc.nextInt() - 1;
            int y = sc.nextInt() - 1;
            if (t == 1) {
                for (int j = 0; j < y - x; j++) {
                    set.remove(set.kthElement(x + 1));
                }
            } else {
                pw.println(s[set.kthElement(y + 1)] - s[set.kthElement(x)]);
            }
        }
    }
}

/**
 * @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 IntOrderedMultiSet implements Iterable<Integer> {
    private static final Object DUMMY = new Object();

    IntRandomizedBinarySearchTree<Object> root;
    static int kthElement(IntRandomizedBinarySearchTree<?> t, int k) {
        int c = IntRandomizedBinarySearchTree.size(t.l);
        if (k < c) return kthElement(t.l, k);
        if (k == c) return t.key;
        return kthElement(t.r, k - c - 1);
    }
    public int kthElement(int k) {
        if (k < 0 || k >= size()) throw new IndexOutOfBoundsException();
        return kthElement(root, k);
    }
    public int lowerElement(int key) {return kthElement(ltCount(key) - 1);}
    public int floorElement(int key) {return kthElement(leqCount(key) - 1);}
    public int higherElement(int key) {return kthElement(leqCount(key));}
    public int ceilingElement(int key) {return kthElement(ltCount(key));}
    public int first() {return kthElement(0);}
    public int last() {return kthElement(size() - 1);}
    public void add(int key) {root = IntRandomizedBinarySearchTree.insert(root, leqCount(root, key), key, DUMMY);}
    static IntRandomizedBinarySearchTree<Object> eraseEntry(IntRandomizedBinarySearchTree<Object> t, int key) {
        return IntRandomizedBinarySearchTree.erase(t, leqCount(t, key) - 1);
    }
    public boolean remove(int key) {
        if (contains(key)) {
            root = IntRandomizedBinarySearchTree.erase(root, leqCount(root, key) - 1);
            return true;
        }
        return false;
    }
    public boolean contains(int key) {
        IntRandomizedBinarySearchTree<Object> t = root;
        while (t != null) {
            if (t.key == key) return true;
            t = t.key > key ? t.l : t.r;
        }
        return false;
    }
    static int leqCount(IntRandomizedBinarySearchTree<?> t, int key) {
        if (t == null) return 0;
        if (key < t.key) return leqCount(t.l, key);
        return leqCount(t.r, key) + IntRandomizedBinarySearchTree.size(t.l) + 1;
    }
    public int leqCount(int key) {return leqCount(root, key);}
    static int ltCount(IntRandomizedBinarySearchTree<?> t, int key) {
        if (t == null) return 0;
        if (key <= t.key) return ltCount(t.l, key);
        return ltCount(t.r, key) + IntRandomizedBinarySearchTree.size(t.l) + 1;
    }
    public int ltCount(int key) { return ltCount(root, key); }
    public int geqCount(int key) { return size() - ltCount(key); }
    public int gtCount(int key) { return size() - leqCount(key); }
    public int count(int key) { return leqCount(key) - ltCount(key); }
    public int size() { return IntRandomizedBinarySearchTree.size(root); }
    public boolean isEmpty() { return size() == 0; }
    public void clear() { this.root = null; }
    public PrimitiveIterator.OfInt iterator() { return isEmpty() ? IterUtil.emptyIntIterator() : root.keyIterator(); }
}
class IntOrderedSet extends IntOrderedMultiSet {
    @Override public void add(int e) {if (!contains(e)) super.add(e);}
    @Override public int count(int key) {return contains(key) ? 1 : 0;}
}


class IntRandomizedBinarySearchTree<V> extends IntEntry<V> implements Iterable<IntEntry<V>> {
    IntRandomizedBinarySearchTree<V> l, r;
    int size;
    IntRandomizedBinarySearchTree(int key, V val) {super(key, val); this.size = 1;}
    private IntRandomizedBinarySearchTree<V> update() {
        size = size(l) + size(r) + 1;
        return this;
    }

    private static final Random rnd = new Random();

    static <V> IntRandomizedBinarySearchTree<V> merge(IntRandomizedBinarySearchTree<V> l, IntRandomizedBinarySearchTree<V> 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 <V> Pair<IntRandomizedBinarySearchTree<V>, IntRandomizedBinarySearchTree<V>> split(IntRandomizedBinarySearchTree<V> 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<V>, IntRandomizedBinarySearchTree<V>> 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 <V> IntRandomizedBinarySearchTree<V> insert(IntRandomizedBinarySearchTree<V> t, int k, int key, V val) {
        Pair<IntRandomizedBinarySearchTree<V>, IntRandomizedBinarySearchTree<V>> p = split(t, k);
        return merge(merge(p.fst, new IntRandomizedBinarySearchTree<>(key, val)), p.snd);
    }
    static <V> IntRandomizedBinarySearchTree<V> erase(IntRandomizedBinarySearchTree<V> t, int k) {
        Pair<IntRandomizedBinarySearchTree<V>, IntRandomizedBinarySearchTree<V>> p = split(t, k);
        IntRandomizedBinarySearchTree<V> l = p.fst;
        IntRandomizedBinarySearchTree<V> r = split(p.snd, 1).snd;
        return merge(l, r);
    }
    static int size(IntRandomizedBinarySearchTree<?> nd) {return nd == null ? 0 : nd.size;}

    public Iterator<IntEntry<V>> iterator() {
        Iterator<IntEntry<V>> it = List.<IntEntry<V>>of(this).iterator();
        if (l != null) it = IterUtil.concatIterators(l.iterator(), it);
        if (r != null) it = IterUtil.concatIterators(it, r.iterator());
        return it;
    }

    public 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<Object>) 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 <V> Iterator<V> emptyIterator() {return (Iterator<V>) EMPTY_ITERATOR;}
    @SuppressWarnings("unchecked")
    public static <V> Iterable<V> emptyIterable() {return (Iterable<V>) EMPTY_ITERABLE;}

    private static <V> Iterator<V> concatIterators(Iterator<? extends Iterator<V>> iterIterator) {
        return new Iterator<V>(){
            Iterator<V> 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<PrimitiveIterator.OfInt> 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<PrimitiveIterator.OfLong> 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<PrimitiveIterator.OfDouble> 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 <V> Iterable<V> concatIterables(Iterator<? extends Iterable<V>> iterIterator) {
        return () -> new Iterator<V>(){
            Iterator<V> 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 <V> Iterator<V> concatIterators(Iterator<V> it1, Iterator<V> it2) {
        return concatIterators(List.of(it1, it2).iterator());
    }
    public static <V> Iterator<V> concatIterators(Iterator<V> it1, Iterator<V> it2, Iterator<V> it3) {
        return concatIterators(List.of(it1, it2, it3).iterator());
    }
    public static <V> Iterator<V> concatIterators(Iterator<V> it1, Iterator<V> it2, Iterator<V> it3, Iterator<V> it4) {
        return concatIterators(List.of(it1, it2, it3, it4).iterator());
    }
    public static <V> Iterator<V> concatIterators(Iterable<? extends Iterator<V>> 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<PrimitiveIterator.OfInt> 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<PrimitiveIterator.OfLong> 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<PrimitiveIterator.OfDouble> its) {
        return concatDoubleIterators(its.iterator());
    }

    public static <V> Iterable<V> concatIterables(Iterable<V> it1, Iterable<V> it2) {
        return concatIterables(List.of(it1, it2));
    }
    public static <V> Iterable<V> concatIterables(Iterable<V> it1, Iterable<V> it2, Iterable<V> it3) {
        return concatIterables(List.of(it1, it2, it3));
    }
    public static <V> Iterable<V> concatIterables(Iterable<V> it1, Iterable<V> it2, Iterable<V> it3, Iterable<V> it4) {
        return concatIterables(List.of(it1, it2, it3, it4));
    }
    public static <V> Iterable<V> concatIterables(Iterable<? extends Iterable<V>> 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<V> {
    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<E0, E1> {
    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() + ")";}
}