import java.util.*;
import java.io.*;
import java.util.function.*;

final class FastInputStream {
	private static final int BUF_SIZE = 1 << 14;
	private final InputStream in;
	private final byte buf[] = new byte[BUF_SIZE];
	private int pos = 0;
	private int count = 0;
	private static final int TOKEN_SIZE = 1 << 20;
	private final byte tokenBuf[] = new byte[TOKEN_SIZE];

	public FastInputStream(final InputStream in) {
		this.in = in;
	}
	private final void readBuf() {
		pos = 0;
		try { count = in.read(buf); }
		catch(IOException e) { e.printStackTrace(); }
	}
	private final boolean hasNextByte() {
		if(pos < count) return true;
		readBuf();
		return count > 0;
	}
	private final byte read() { if(hasNextByte()) return buf[pos ++]; else throw new NoSuchElementException(); }
	private final boolean isPrintableChar(final byte c) { return 33 <= c && c <= 126; }
	private final boolean isNumber(final byte c) { return 48 <= c && c <= 57; }
	private final void skipUnprintable() {
		while(true) {
			for(int i = pos; i < count; i ++) {
				if(isPrintableChar(buf[i])) { pos = i; return; }
			}
			readBuf();
			if(count <= 0) throw new NoSuchElementException();
		}
	}
	private final boolean readEOL() {
		if(!hasNextByte()) return true;
		if(buf[pos] == 13) {
			pos ++;
			if(hasNextByte() && buf[pos] == 10) pos ++;
			return true;
		}
		if(buf[pos] == 10) {
			pos ++;
			return true;
		}
		return false;
	}

	public final char nextChar() {
		skipUnprintable();
		return (char)buf[pos ++];
	}
	public final String next() {
		skipUnprintable();
		int tokenCount = 0;
		outer: while(count > 0) {
			for(int i = pos; i < count; i ++) {
				final byte b = buf[i];
				if(!isPrintableChar(b)) { pos = i; break outer; }
				tokenBuf[tokenCount ++] = b;
			}
			readBuf();
		}
		return new String(tokenBuf, 0, tokenCount);
	}
	public final String nextLine() {
		readEOL();
		if(!hasNextByte()) throw new NoSuchElementException();
		int tokenCount = 0;
		while(!readEOL()) tokenBuf[tokenCount ++] = read();
		return new String(tokenBuf, 0, tokenCount);
	}
	public final int nextInt() {
		skipUnprintable();
		int n = 0;
		boolean minus = false;
		if(buf[pos] == 45) {
			minus = true;
			pos ++;
			if(!hasNextByte() || !isNumber(buf[pos])) throw new InputMismatchException();
		}
		outer: while(count > 0) {
			for(int i = pos; i < count; i ++) {
				final byte b = buf[i];
				if(!isPrintableChar(b)) { pos = i; break outer; }
				if(!isNumber(b)) throw new InputMismatchException();
				if(minus) {
					if(n < - 214748364) throw new ArithmeticException("int overflow");
					if(n == - 214748364 && b > 56) throw new ArithmeticException("int overflow");
					n = (n << 3) + (n << 1) + 48 - b;
				}else {
					if(n > 214748364) throw new ArithmeticException("int overflow");
					if(n == 214748364 && b >= 56) throw new ArithmeticException("int overflow");
					n = (n << 3) + (n << 1) - 48 + b;
				}
			}
			readBuf();
		}
		return n;
	}
	public final long nextLong() {
		skipUnprintable();
		long n = 0;
		boolean minus = false;
		if(buf[pos] == 45) {
			minus = true;
			pos ++;
			if(!hasNextByte() || !isNumber(buf[pos])) throw new InputMismatchException();
		}
		outer: while(count > 0) {
			for(int i = pos; i < count; i ++) {
				final byte b = buf[i];
				if(!isPrintableChar(b)) { pos = i; break outer; }
				if(!isNumber(b)) throw new InputMismatchException();
				if(minus) {
					if(n < - 922337203685477580l) throw new ArithmeticException("long overflow");
					if(n == - 922337203685477580l && b > 56) throw new ArithmeticException("long overflow");
					n = (n << 3) + (n << 1) + 48 - b;
				}else {
					if(n > 922337203685477580l) throw new ArithmeticException("long overflow");
					if(n == 922337203685477580l && b >= 56) throw new ArithmeticException("long overflow");
					n = (n << 3) + (n << 1) - 48 + b;
				}
			}
			readBuf();
		}
		return n;
	}
	public final double nextDouble() { return Double.parseDouble(next()); }

	public final void close() {
		try { in.close(); }
		catch(IOException e) { e.printStackTrace(); }
	}
}

final class FastOutputStream {
	private static final int BUF_SIZE = 1 << 13;
	private final byte buf[] = new byte[BUF_SIZE];
	private final OutputStream out;
	private int count = 0;
	private static final byte TRUE_BYTES[] = {116, 114, 117, 101};
	private static final byte FALSE_BYTES[] = {102, 97, 108, 115, 101};
	private static final byte INT_MIN_BYTES[] = {45, 50, 49, 52, 55, 52, 56, 51, 54, 52, 56};
	private static final byte LONG_MIN_BYTES[] = {45, 57, 50, 50, 51, 51, 55, 50, 48, 51,
												54, 56, 53, 52, 55, 55, 53, 56, 48, 56};
	private static final int TOKEN_SIZE = 20;
	private final byte tokenBuf[] = new byte[TOKEN_SIZE];
	private static final int PRECISION = 10;
	public FastOutputStream(OutputStream out) {
		this.out = out;
	}
	public final void print() {  }
	public final void write(final byte b) {
		if(count == BUF_SIZE) internalFlush();
		buf[count ++] = b;
	}
	public final void print(final char c) { write((byte) c); }
	public final void print(final boolean b) {
		if(b) {
			if(count + 4 > BUF_SIZE) internalFlush();
			System.arraycopy(TRUE_BYTES, 0, buf, count, TRUE_BYTES.length);
			count += TRUE_BYTES.length;
		}else {
			if(count + 5 > BUF_SIZE) internalFlush();
			System.arraycopy(FALSE_BYTES, 0, buf, count, FALSE_BYTES.length);
			count += FALSE_BYTES.length;
		}
	}
	public final void print(int x) {
		if(count + 11 > BUF_SIZE) internalFlush();
		if(x == Integer.MIN_VALUE) {
			System.arraycopy(INT_MIN_BYTES, 0, buf, count, INT_MIN_BYTES.length);
			count += INT_MIN_BYTES.length;
			return;
		}
		if(x == 0) {
			buf[count ++] = 48;
			return;
		}
		if(x < 0) {
			buf[count ++] = 45;
			x = - x;
		}
		int tokenCount = 11;
		while(x > 0) {
			final int y = x / 10;
			tokenBuf[-- tokenCount] = (byte) (x - (y << 3) - (y << 1) + 48);
			x = y;
		}
		System.arraycopy(tokenBuf, tokenCount, buf, count, 11 - tokenCount);
		count += 11 - tokenCount;
	}
	public final void print(long x) {
		if(count + 20 > BUF_SIZE) internalFlush();
		if(x == Long.MIN_VALUE) {
			System.arraycopy(LONG_MIN_BYTES, 0, buf, count, LONG_MIN_BYTES.length);
			count += LONG_MIN_BYTES.length;
			return;
		}
		if(x == 0) {
			buf[count ++] = 48;
			return;
		}
		if(x < 0) {
			buf[count ++] = 45;
			x = - x;
		}
		int tokenCount = 20;
		while(x > 0) {
			final long y = x / 10;
			tokenBuf[-- tokenCount] = (byte) (x - (y << 3) - (y << 1) + 48);
			x = y;
		}
		System.arraycopy(tokenBuf, tokenCount, buf, count, 20 - tokenCount);
		count += 20 - tokenCount;
	}
	public final void print(final double d) { print(d, PRECISION); }
	public final void print(double d, final int precision) {
		if(count == BUF_SIZE) internalFlush();
		if(d < 0) {
			buf[count ++] = 45;
			d = - d;
		}
		d += Math.pow(10, - precision) / 2;
		print((long)d);
		if(precision == 0) return;
		if(count + precision + 1 > BUF_SIZE) internalFlush();
		buf[count ++] = 46;
		d -= (long)d;
		for(int i = 0; i < precision; i ++) {
			d *= 10;
			buf[count ++] = (byte)((int)d + 48);
			d -= (int) d;
		}
	}
	public final void print(final String s) { print(s.getBytes()); }
	public final void print(final Object o) { print(o.toString()); }
	public final void print(final byte[] a) {
		if(count + a.length > BUF_SIZE) internalFlush();
		System.arraycopy(a, 0, buf, count, a.length);
		count += a.length;
	}
	public final void print(final char[] a) {
		if(count + a.length > BUF_SIZE) internalFlush();
		for(int i = 0; i < a.length; i ++) buf[count + i] = (byte)a[i];
		count += a.length;
	}
	public final void println() { print('\n'); }
	public final void println(final char c) { print(c); println(); }
	public final void println(final boolean b) { print(b); println(); }
	public final void println(final int x) { print(x); println(); }
	public final void println(final long x) { print(x); println(); }
	public final void println(final double d) { print(d); println(); }
	public final void println(final double d, final int precision) { print(d, precision); println(); }
	public final void println(final String s) { print(s); println(); }
	public final void println(final Object o) { print(o); println(); }
	public final void println(final char[] a) { print(a); println(); }
	public final void println(final int[] a) {
		for(int i = 0; i < a.length; i ++) {
			print(a[i]);
			print(i == a.length - 1 ? '\n' : ' ');
		}
	}
	public final void println(final long[] a) {
		for(int i = 0; i < a.length; i ++) {
			print(a[i]);
			print(i == a.length - 1 ? '\n' : ' ');
		}
	}
	public final void println(final double[] a) {
		for(int i = 0; i < a.length; i ++) {
			print(a[i]);
			print(i == a.length - 1 ? '\n' : ' ');
		}
	}
	public final void println(final double[] a, final int precision) {
		for(int i = 0; i < a.length; i ++) {
			print(a[i], precision);
			print(i == a.length - 1 ? '\n' : ' ');
		}
	}
	public final void println(final String[] a) {
		for(int i = 0; i < a.length; i ++) {
			print(a[i]);
			print(i == a.length - 1 ? '\n' : ' ');
		}
	}
	public final void println(final Object[] a) {
		for(int i = 0; i < a.length; i ++) {
			print(a[i]);
			print(i == a.length - 1 ? '\n' : ' ');
		}
	}
	private final void internalFlush() {
		try {
			out.write(buf, 0, count);
			count = 0;
		}
		catch(IOException e) { e.printStackTrace(); }
	}
	public final void flush() {
		try {
			out.write(buf, 0, count);
			out.flush();
			count = 0;
		}
		catch(IOException e) { e.printStackTrace(); }
	}
	public final void close() {
		try { out.close(); }
		catch(IOException e) { e.printStackTrace(); }
	}
}

class SimpleUtil {
	public static boolean DEBUG;

	private static final FastInputStream in = new FastInputStream(System.in);
	public static final String nline() { return in.nextLine(); }
	public static final String[] nline(final int n) { final String a[] = new String[n]; for(int i = 0; i < n; i ++) a[i] = nline(); return a; }
	public static final char nc() { return in.nextChar(); }
	public static final char[] nc(int n) {
		final String str = nline();
		if(n < 0) n = str.length();
		final char a[] = new char[n];
		for(int i = 0; i < n; i ++) a[i] = str.charAt(i);
		return a;
	}
	public static final char[][] nc(final int n, final int m) { final char a[][] = new char[n][m]; for(int i = 0; i < n; i ++) a[i] = nc(m); return a; }
	public static final boolean[] nb(int n, final char t) {
		final char c[] = nc(-1);
		if(n < 0) n = c.length;
		final boolean a[] = new boolean[n];
		for(int i = 0; i < n; i ++) a[i] = c[i] == t;
		return a;
	}
	public static final boolean[][] nb(final int n, final int m, final char t) { final boolean a[][] = new boolean[n][]; for(int i = 0; i < n; i ++) a[i] = nb(m, t); return a; }
	public static final int ni() { return in.nextInt(); }
	public static final int[] ni(final int n) { final int a[] = new int[n]; for(int i = 0; i < n; i ++) a[i] = ni(); return a; }
	public static final int[][] ni(final int n, final int m) { final int a[][] = new int[n][]; for(int i = 0; i < n; i ++) a[i] = ni(m); return a; }
	public static final long nl() { return in.nextLong(); }
	public static final long[] nl(final int n) { final long a[] = new long[n]; for(int i = 0; i < n; i ++) a[i] = nl(); return a; }
	public static final long[][] nl(final int n, final int m) { final long a[][] = new long[n][]; for(int i = 0; i < n; i ++) a[i] = nl(m); return a; }
	public static final double nd() { return in.nextDouble(); }
	public static final double[] nd(final int n) { final double a[] = new double[n]; for(int i = 0; i < n; i ++) a[i] = nd(); return a; }
	public static final double[][] nd(final int n, final int m) { final double a[][] = new double[n][]; for(int i = 0; i < n; i ++) a[i] = nd(m); return a; }
	public static final String ns() { return in.next(); }
	public static final String[] ns(final int n) { final String a[] = new String[n]; for(int i = 0; i < n; i ++) a[i] = ns(); return a; }
	public static final String[][] ns(final int n, final int m) { final String a[][] = new String[n][]; for(int i = 0; i < n; i ++) a[i] = ns(m); return a; }

	private static final FastOutputStream out = new FastOutputStream(System.out);
	private static final FastOutputStream err = new FastOutputStream(System.err);
	public static final void prt() { out.print(); }
	public static final void prt(final char c) { out.print(c); }
	public static final void prt(final boolean b) { out.print(b); }
	public static final void prt(final int x) { out.print(x); }
	public static final void prt(final long x) { out.print(x); }
	public static final void prt(final double d) { out.print(d); }
	public static final void prt(final String s) { out.print(s); }
	public static final void prt(final Object o) { out.print(o); }
	public static final void prtln() { out.println(); }
	public static final void prtln(final char c) { out.println(c); }
	public static final void prtln(final boolean b) { out.println(b); }
	public static final void prtln(final int x) { out.println(x); }
	public static final void prtln(final long x) { out.println(x); }
	public static final void prtln(final double d) { out.println(d); }
	public static final void prtln(final String s) { out.println(s); }
	public static final void prtln(final Object o) { out.println(o); }
	public static final void prtln(final char... a) { out.println(a); }
	public static final void prtln(final boolean... a) { out.println(booleanToChar(a)); }
	public static final void prtln(final int... a) { out.println(a); }
	public static final void prtln(final long... a) { out.println(a); }
	public static final void prtln(final double... a) { out.println(a); }
	public static final void prtln(final double[] a, int precision) { out.println(a, precision); }
	public static final void prtln(final String... a) { out.println(a); }
	public static final void prtln(final Object[] a) { out.println(a); }
	public static final void prtlns(final char... a) { for(char ele : a) prtln(ele); }
	public static final void prtlns(final boolean... a) { for(boolean ele : a) prtln(ele); }
	public static final void prtlns(final int... a) { for(int ele : a) prtln(ele); }
	public static final void prtlns(final long... a) { for(long ele : a) prtln(ele); }
	public static final void prtlns(final double... a) { for(double ele : a) prtln(ele); }
	public static final void prtlns(final Object[] a) { for(Object ele : a) prtln(ele); }
	public static final void prtln(final char[][] a) { for(char[] ele : a) prtln(ele); }
	public static final void prtln(final boolean[][] a) { for(boolean[] ele : a) prtln(ele); }
	public static final void prtln(final int[][] a) { for(int[] ele : a) prtln(ele); }
	public static final void prtln(final long[][] a) { for(long[] ele : a) prtln(ele); }
	public static final void prtln(final double[][] a) { for(double[] ele : a) prtln(ele); }
	public static final void prtln(final double[][] a, int precision) { for(double[] ele : a) prtln(ele, precision); }
	public static final void prtln(final String[][] a) { for(String[] ele : a) prtln(ele); }
	public static final void prtln(final Object[][] a) { for(Object[] ele : a) prtln(ele); }

	public static final void errprt() { if(DEBUG) err.print(); }
	public static final void errprt(final char c) { if(DEBUG) err.print(c); }
	public static final void errprt(final boolean b) { if(DEBUG) err.print(booleanToChar(b)); }
	public static final void errprt(final int x) { if(DEBUG) if(isINF(x)) err.print('_'); else err.print(x); }
	public static final void errprt(final long x) { if(DEBUG) if(isINF(x)) err.print('_'); else err.print(x); }
	public static final void errprt(final double d) { if(DEBUG) err.print(d); }
	public static final void errprt(final String s) { if(DEBUG) err.print(s); }
	public static final void errprt(final Object o) { if(DEBUG) err.print(o); }
	public static final void errprtln() { if(DEBUG) err.println(); }
	public static final void errprtln(final char c) { if(DEBUG) err.println(c); }
	public static final void errprtln(final boolean b) { if(DEBUG) err.println(booleanToChar(b)); }
	public static final void errprtln(final int x) { if(DEBUG) if(isINF(x)) err.println('_'); else err.println(x); }
	public static final void errprtln(final long x) { if(DEBUG) if(isINF(x)) err.println('_'); else err.println(x); }
	public static final void errprtln(final double d) { if(DEBUG) err.println(d); }
	public static final void errprtln(final String s) { if(DEBUG) err.println(s); }
	public static final void errprtln(final Object o) { if(DEBUG) err.println(o); }
	public static final void errprtln(final char... a) { if(DEBUG) err.println(a); }
	public static final void errprtln(final boolean... a) { if(DEBUG) err.println(booleanToChar(a)); }
	public static final void errprtln(final int... a) {
		if(DEBUG) {
			boolean start = false;
			for(int ele : a) {
				errprt(ele);
				if(!start) errprt(' ');
				start = false;
			}
			err.println();
		}
	}
	public static final void errprtln(final long... a) {
		if(DEBUG) {
			boolean start = false;
			for(long ele : a) {
				errprt(ele);
				if(!start) errprt(' ');
				start = false;
			}
			err.println();
		}
	}
	public static final void errprtln(final double... a) { if(DEBUG) err.println(a); }
	public static final void errprtln(final double[] a, final int precision) { if(DEBUG) err.println(a, precision); }
	public static final void errprtln(final String... a) { if(DEBUG) err.println(a); }
	public static final void errprtln(final Object[] a) { if(DEBUG) err.println(a); }
	public static final void errprtlns(final char... a) { if(DEBUG) for(char ele : a) errprtln(ele); }
	public static final void errprtlns(final boolean... a) { if(DEBUG) for(boolean ele : a) errprtln(ele); }
	public static final void errprtlns(final int... a) { if(DEBUG) for(int ele : a) errprtln(ele); }
	public static final void errprtlns(final long... a) { if(DEBUG) for(long ele : a) errprtln(ele); }
	public static final void errprtlns(final double... a) { if(DEBUG) for(double ele : a) errprtln(ele); }
	public static final void errprtlns(final Object[] a) { if(DEBUG) for(Object ele : a) errprtln(ele); }
	public static final void errprtln(final char[][] a) { if(DEBUG) for(char[] ele : a) errprtln(ele); }
	public static final void errprtln(final boolean[][] a) { if(DEBUG) for(boolean[] ele : a) errprtln(ele); }
	public static final void errprtln(final int[][] a) { if(DEBUG) for(int[] ele : a) errprtln(ele); }
	public static final void errprtln(final long[][] a) { if(DEBUG) for(long[] ele : a) errprtln(ele); }
	public static final void errprtln(final double[][] a) { if(DEBUG) for(double[] ele : a) errprtln(ele); }
	public static final void errprtln(final double[][] a, int precision) { if(DEBUG) for(double[] ele : a) errprtln(ele, precision); }
	public static final void errprtln(final String[][] a) { if(DEBUG) for(String[] ele : a) errprtln(ele); }
	public static final void errprtln(final Object[][] a) { if(DEBUG) for(Object[] ele : a) errprtln(ele); }
	public static final void errprtlns(final Object[][] a) { if(DEBUG) for(Object[] ele : a) { errprtlns(ele); errprtln(); } }

	public static final void reply(final boolean b) { prtln(b ? "Yes" : "No"); }
	public static final void REPLY(final boolean b) { prtln(b ? "YES" : "NO"); }

	public static final void flush() { out.flush(); if(DEBUG) err.flush(); }
	public static final void assertion(final boolean b) { if(!b) { flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final char c) { if(!b) { errprtln(c); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final boolean b2) { if(!b) { errprtln(b2); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final int x) { if(!b) { errprtln(x); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final long x) { if(!b) { errprtln(x); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final double d) { if(!b) { errprtln(d); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final String s) { if(!b) { errprtln(s); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final Object o) { if(!b) { errprtln(o); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final char... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final boolean... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final int... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final long... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final double... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final String... a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final Object[] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final char[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final boolean[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final int[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final long[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final double[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final String[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void assertion(final boolean b, final Object[][] a) { if(!b) { errprtln(a); flush(); throw new AssertionError(); } }
	public static final void inclusiveRangeCheck(final int i, final int max) { inclusiveRangeCheck(i, 0, max); }
	public static final void inclusiveRangeCheck(final int i, final int min, final int max) { rangeCheck(i, min, max + 1); }
	public static final void inclusiveRangeCheck(final long i, final long max) { inclusiveRangeCheck(i, 0, max); }
	public static final void inclusiveRangeCheck(final long i, final long min, final long max) { rangeCheck(i, min, max + 1); }
	public static final void rangeCheck(final int i, final int max) { rangeCheck(i, 0, max); }
	public static final void rangeCheck(final int i, final int min, final int max) { if(i < min || i >= max) throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, max)); }
	public static final void rangeCheck(final long i, final long max) { rangeCheck(i, 0, max); }
	public static final void rangeCheck(final long i, final long min, final long max) { if(i < min || i >= max) throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, max)); }
	public static final void nonNegativeCheck(final long x) { nonNegativeCheck(x, "the argument"); }
	public static final void nonNegativeCheck(final long x, final String attribute) { if(x < 0) throw new IllegalArgumentException(String.format("%s %d is negative", attribute, x)); }
	public static final void positiveCheck(final long x) { positiveCheck(x, "the argument"); }
	public static final void positiveCheck(final long x, final String attribute) { if(x <= 0) throw new IllegalArgumentException(String.format("%s %d is negative", attribute, x)); }

	public static final void exit() { flush(); System.exit(0); }
	public static final void exit(final char c) { prtln(c); exit(); }
	public static final void exit(final boolean b) { prtln(b); exit(); }
	public static final void exit(final int x) { prtln(x); exit(); }
	public static final void exit(final long x) { prtln(x); exit(); }
	public static final void exit(final double d) { prtln(d); exit(); }
	public static final void exit(final String s) { prtln(s); exit(); }
	public static final void exit(final Object o) { prtln(o); exit(); }
	public static final void exit(final char... a) { prtln(a); exit(); }
	public static final void exit(final boolean... a) { prtln(a); exit(); }
	public static final void exit(final int... a) { prtln(a); exit(); }
	public static final void exit(final long... a) { prtln(a); exit(); }
	public static final void exit(final double... a) { prtln(a); exit(); }
	public static final void exit(final String... a) { prtln(a); exit(); }
	public static final void exit(final Object[] a) { prtln(a); exit(); }
	public static final void exit(final char[][] a) { prtln(a); exit(); }
	public static final void exit(final boolean[][] a) { prtln(a); exit(); }
	public static final void exit(final int[][] a) { prtln(a); exit(); }
	public static final void exit(final long[][] a) { prtln(a); exit(); }
	public static final void exit(final double[][] a) { prtln(a); exit(); }
	public static final void exit(final String[][] a) { prtln(a); exit(); }
	public static final void exit(final Object[][] a) { prtln(a); exit(); }


	public static final char booleanToChar(final boolean b) { return b ? '#' : '.'; }
	public static final char[] booleanToChar(final boolean... a) {
		final char c[] = new char[a.length];
		for(int i = 0; i < a.length; i ++) c[i] = booleanToChar(a[i]);
		return c;
	}
	public static final long INF = (long)4e18;
	public static final boolean isPlusINF(final long x) { return x > INF / 10; }
	public static final boolean isMinusINF(final long x) { return isPlusINF(- x); }
	public static final boolean isINF(final long x) { return isPlusINF(x) || isMinusINF(x); }
	public static final int I_INF = (int)1e9 + 1000;
	public static final boolean isPlusINF(final int x) { return x > I_INF / 10; }
	public static final boolean isMinusINF(final int x) { return isPlusINF(- x); }
	public static final boolean isINF(final int x) { return isPlusINF(x) || isMinusINF(x); }
}

abstract class Solver extends SimpleUtil implements Runnable {
	public static void main(final String[] args, Runnable solver) {
		DEBUG = args.length > 0 && args[0].equals("-DEBUG");
		Thread.setDefaultUncaughtExceptionHandler((t, e) -> { flush(); e.printStackTrace(); System.exit(1); });
		new Thread(null, solver, "", 1 << 31).start();
	}
	@Override
	public void run() { solve(); flush(); }
	abstract public void solve();
}

public class Main extends Solver {
	public static void main(final String[] args) { main(args, new Main()); }

	public void solve() {
		int n = ni();
		DynamicSegmentTree st = new DynamicSegmentTree(1_000_000_001,
				0, (ele1, ele2) -> ele1 + ele2);
		long ans = 0;
		for(int i = 0; i < n; i ++) {
			if(ni() == 0) st.update(ni(), nl());
			else ans += st.find(ni(), ni() + 1);
		}
		prtln(ans);
	}
}

class DynamicSegmentTree {
	class NodeST {
		long val;
		NodeST l = null;
		NodeST r = null;
		NodeST() { this(e); }
		NodeST(long val) { this.val = val; }
	}

	long n;
	long e;
	LongBinaryOperator f;

	NodeST root;

	// O(1)
	DynamicSegmentTree(long len, long e, LongBinaryOperator f) {
		SimpleUtil.nonNegativeCheck(len);
		this.n = len;
		this.e = e;
		this.f = f;
		root = new NodeST();
	}

	// O(logN)
	void set(long i, long val) { SimpleUtil.rangeCheck(i, n); update(i, val, false); }
	void update(long i, long val) { SimpleUtil.rangeCheck(i, n); update(i, val, true); }
	void update(long i, long val, boolean update) { update(root, 0, n, i, val, update); }
	NodeST update(NodeST t, long l, long r, long i, long val, boolean update) {
		if(t == null) t = new NodeST();
		if(r - l == 1) { t.val = update ? f.applyAsLong(t.val, val) : val; return t; }
		long mid = (l + r) >> 1;
		if(i < mid) t.l = update(t.l, l, mid, i, val, update);
		else t.r = update(t.r, mid, r, i, val, update);
		t.val = e;
		if(t.l != null) t.val = f.applyAsLong(t.val, t.l.val);
		if(t.r != null) t.val = f.applyAsLong(t.val, t.r.val);
		return t;
	}

	// O(logN)
	long get(long i) { SimpleUtil.rangeCheck(i, n); return get(root, 0, n, i); }
	long get(NodeST t, long l, long r, long i) {
		if(t == null) return e;
		if(r - l == 1) return t.val;
		long mid = (l + r) >> 1;
		return i < mid ? get(t.l, l, mid, i) : get(t.r, mid, r, i);
	}
	long find(long l0, long r0) {
		SimpleUtil.inclusiveRangeCheck(l0, n);
		SimpleUtil.inclusiveRangeCheck(r0, n);
		SimpleUtil.assertion(l0 <= r0, "l is larger than r.");
		return find(root, 0, n, l0, r0);
	}
	long find(NodeST t, long l, long r, long l0, long r0) {
		if(l == r || t == null || r0 <= l || r <= l0) return e;
		if(l0 <= l && r <= r0) return t.val;
		long mid = (l + r) >> 1;
		return f.applyAsLong(find(t.l, l, mid, l0, r0), find(t.r, mid, r, l0, r0));
	}
}