import java.util.*;
import java.io.*;
import java.math.*;
import java.util.function.*;
public class Main implements Runnable {
	static boolean DEBUG;
	public static void main(String[] args) {
		DEBUG = args.length > 0 && args[0].equals("-DEBUG");
		Thread.setDefaultUncaughtExceptionHandler((t, e) -> { e.printStackTrace(); System.exit(1); });
		new Thread(null, new Main(), "", 1 << 31).start();
	}

	public void run() { Solver solver = new Solver(); solver.solve(); solver.exit(); }

	static class FastScanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int pointer = 0;
		private int buflen = 0;
		private boolean hasNextByte() {
			if(pointer < buflen) return true;
			else {
				pointer = 0;
				try { buflen = in.read(buffer);
				}catch (IOException e) { e.printStackTrace(); }
				return buflen > 0;
			}
		}
		private int readByte() { if(hasNextByte()) return buffer[pointer ++]; else return -1; }
		private boolean isPrintableChar(int c) { return isPrintableChar(c, false); }
		private boolean isPrintableChar(int c, boolean includingSpace) { return (includingSpace ? 32 : 33) <= c && c <= 126; }
		private void skipUnprintable() { skipUnprintable(false); }
		private void skipUnprintable(boolean includingSpace) { while(hasNextByte() && !isPrintableChar(buffer[pointer], includingSpace)) pointer ++; }
		private boolean hasNext() { return hasNext(false); }
		private boolean hasNext(boolean includingSpace) { skipUnprintable(includingSpace); return hasNextByte(); }
		private StringBuilder sb = new StringBuilder();
		public String next() { return next(false); }
		public String next(boolean includingSpace) {
			if(!hasNext(includingSpace)) throw new NoSuchElementException();
			sb.setLength(0);
			int b = readByte();
			while(isPrintableChar(b, includingSpace)) { sb.appendCodePoint(b); b = readByte(); }
			return sb.toString();
		}
		public long nextLong() {
			if(!hasNext()) throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if(b == '-') { minus = true; b = readByte(); }
			if(b < '0' || '9' < b) throw new NumberFormatException();
			while(true) {
				if('0' <= b && b <= '9') n = n * 10 + b - '0';
				else if(b == -1 || !isPrintableChar(b)) return minus ? - n : n;
				else throw new NumberFormatException();
				b = readByte();
			}
		}
	}

	static class Solver {
		final FastScanner sc = new FastScanner();
		public Solver() { }

		final String ns() { return ns(false); }
		final String ns(boolean includingSpace) { return sc.next(includingSpace); }
		final String[] ns(int n) { return ns(n, false); }
		final String[] ns(int n, boolean includingSpace) { String a[] = new String[n]; for(int i = 0; i < n; i ++) a[i] = ns(includingSpace); return a; }
		final String[][] ns(int n, int m) { return ns(n, m, false); }
		final String[][] ns(int n, int m, boolean includingSpace) { String a[][] = new String[n][m]; for(int i = 0; i < n; i ++) a[i] = ns(m, includingSpace); return a; }
		final char nc() { return ns().charAt(0); }
		final char[] nc(int n) {
			String str = ns();
			if(n < 0) n = str.length();
			char a[] = new char[n];
			for(int i = 0; i < n; i ++) a[i] = str.charAt(i);
			return a;
		}
		final char[][] nc(int n, int m) { char a[][] = new char[n][m]; for(int i = 0; i < n; i ++) a[i] = nc(m); return a; }
		final boolean[] nb(int n, char t) {
			char c[] = nc(-1);
			if(n < 0) n = c.length;
			boolean a[] = new boolean[n];
			for(int i = 0; i < n; i ++) a[i] = c[i] == t;
			return a;
		}
		final boolean[][] nb(int n, int m, char t) { boolean a[][] = new boolean[n][m]; for(int i = 0; i < n; i ++) a[i] = nb(m, t); return a; }
		final int ni() { return Math.toIntExact(sc.nextLong()); }
		final int[] ni(int n) { int a[] = new int[n]; for(int i = 0; i < n; i ++) a[i] = ni(); return a; }
		final int[][] ni(int n, int m) { int a[][] = new int[n][m]; for(int i = 0; i < n; i ++) a[i] = ni(m); return a; }
		final long nl() { return sc.nextLong(); }
		final long[] nl(int n) { long a[] = new long[n]; for(int i = 0; i < n; i ++) a[i] = nl(); return a; }
		final long[][] nl(int n, int m) { long a[][] = new long[n][m]; for(int i = 0; i < n; i ++) a[i] = nl(m); return a; }
		final double nd() { return Double.parseDouble(sc.next()); }
		final double[] nd(int n) { double a[] = new double[n]; for(int i = 0; i < n; i ++) a[i] = nd(); return a; }
		final double[][] nd(int n, int m) { double a[][] = new double[n][m]; for(int i = 0; i < n; i ++) a[i] = nd(m); return a; }

		final String booleanToString(boolean b) { return b ? "#" : "."; }

		final PrintWriter out = new PrintWriter(System.out);
		final PrintWriter err = new PrintWriter(System.err);
		final StringBuilder sb4prtln = new StringBuilder();
		final void prt() { out.print(""); }
		final <T> void prt(T a) { out.print(a); }
		final void prtln() { out.println(""); }
		final <T> void prtln(T a) { out.println(a); }
		final void prtln(int... a) { sb4prtln.setLength(0); for(int ele : a) { sb4prtln.append(ele); sb4prtln.append(" "); } prtln(sb4prtln.toString().trim()); }
		final void prtln(long... a) { sb4prtln.setLength(0); for(long ele : a) { sb4prtln.append(ele); sb4prtln.append(" "); } prtln(sb4prtln.toString().trim()); }
		final void prtln(double... a) { sb4prtln.setLength(0); for(double ele : a) { sb4prtln.append(ele); sb4prtln.append(" "); } prtln(sb4prtln.toString().trim()); }
		final void prtln(String... a) { sb4prtln.setLength(0); for(String ele : a) { sb4prtln.append(ele); sb4prtln.append(" "); } prtln(sb4prtln.toString().trim()); }
		final void prtln(char... a) { sb4prtln.setLength(0); for(char ele : a) sb4prtln.append(ele); prtln(sb4prtln.toString()); }
		final void prtln(boolean... a) { sb4prtln.setLength(0); for(boolean ele : a) sb4prtln.append(booleanToString(ele)); prtln(sb4prtln.toString()); }
		final void prtlns(int... a) { sb4prtln.setLength(0); for(int ele : a) { sb4prtln.append(ele); sb4prtln.append("\n"); } prt(sb4prtln.toString()); }
		final void prtlns(long... a) { sb4prtln.setLength(0); for(long ele : a) { sb4prtln.append(ele); sb4prtln.append("\n"); } prt(sb4prtln.toString()); }
		final void prtlns(double... a) { sb4prtln.setLength(0); for(double ele : a) { sb4prtln.append(ele); sb4prtln.append("\n"); } prt(sb4prtln.toString()); }
		final void prtlns(String... a) { sb4prtln.setLength(0); for(String ele : a) { sb4prtln.append(ele); sb4prtln.append("\n"); } prt(sb4prtln.toString()); }
		final void prtlns(char... a) { sb4prtln.setLength(0); for(char ele : a) { sb4prtln.append(ele); sb4prtln.append("\n"); } prt(sb4prtln.toString()); }
		final void prtlns(boolean... a) { sb4prtln.setLength(0); for(boolean ele : a) { sb4prtln.append(booleanToString(ele)); sb4prtln.append("\n"); } prt(sb4prtln.toString()); }
		final void prtln(int[][] a) { for(int[] ele : a) prtln(ele); }
		final void prtln(long[][] a) { for(long[] ele : a) prtln(ele); }
		final void prtln(double[][] a) { for(double[] ele : a) prtln(ele); }
		final void prtln(String[][] a) { for(String[] ele : a) prtln(ele); }
		final void prtln(char[][] a) { for(char[] ele : a) prtln(ele); }
		final void prtln(boolean[][] a) { for(boolean[] ele : a) prtln(ele); }

		final String errconvert(int a) { return isINF(a) ? "_" : String.valueOf(a); }
		final String errconvert(long a) { return isINF(a) ? "_" : String.valueOf(a); }
		final void errprt(int a) { if(DEBUG) err.print(errconvert(a)); }
		final void errprt(long a) { if(DEBUG) err.print(errconvert(a)); }
		final void errprt() { if(DEBUG) err.print(""); }
		final <T> void errprt(T a) { if(DEBUG) err.print(a); }
		final void errprt(boolean a) { if(DEBUG) errprt(booleanToString(a)); }
		final void errprtln() { if(DEBUG) err.println(""); }
		final void errprtln(int a) { if(DEBUG) err.println(errconvert(a)); }
		final void errprtln(long a) { if(DEBUG) err.println(errconvert(a)); }
		final <T> void errprtln(T a) { if(DEBUG) err.println(a); }
		final void errprtln(boolean a) { if(DEBUG) errprtln(booleanToString(a)); }
		final void errprtln(int... a) { if(DEBUG) { sb4prtln.setLength(0); for(int ele : a) { sb4prtln.append(errconvert(ele)); sb4prtln.append(" "); } errprtln(sb4prtln.toString().trim()); } }
		final void errprtln(long... a) { if(DEBUG) { sb4prtln.setLength(0); for(long ele : a) { sb4prtln.append(errconvert(ele)); sb4prtln.append(" "); } errprtln(sb4prtln.toString().trim()); } }
		final void errprtln(double... a) { if(DEBUG) { sb4prtln.setLength(0); for(double ele : a) { sb4prtln.append(ele); sb4prtln.append(" "); } errprtln(sb4prtln.toString().trim()); } }
		final void errprtln(String... a) { if(DEBUG) { sb4prtln.setLength(0); for(String ele : a) { sb4prtln.append(ele); sb4prtln.append(" "); } errprtln(sb4prtln.toString().trim()); } }
		final void errprtln(char... a) { if(DEBUG) { sb4prtln.setLength(0); for(char ele : a) sb4prtln.append(ele); errprtln(sb4prtln.toString()); } }
		final void errprtln(boolean... a) { if(DEBUG) { sb4prtln.setLength(0); for(boolean ele : a) sb4prtln.append(booleanToString(ele)); errprtln(sb4prtln.toString()); } }
		final void errprtlns(int... a) { if(DEBUG) { sb4prtln.setLength(0); for(int ele : a) { sb4prtln.append(errconvert(ele)); sb4prtln.append("\n"); } errprt(sb4prtln.toString()); } }
		final void errprtlns(long... a) { if(DEBUG) { sb4prtln.setLength(0); for(long ele : a) { sb4prtln.append(errconvert(ele)); sb4prtln.append("\n"); } errprt(sb4prtln.toString()); } }
		final void errprtlns(double... a) { if(DEBUG) { sb4prtln.setLength(0); for(double ele : a) { sb4prtln.append(ele); sb4prtln.append("\n"); } errprt(sb4prtln.toString()); } }
		final void errprtlns(String... a) { if(DEBUG) { sb4prtln.setLength(0); for(String ele : a) { sb4prtln.append(ele); sb4prtln.append("\n"); } errprt(sb4prtln.toString()); } }
		final void errprtlns(char... a) { if(DEBUG) { sb4prtln.setLength(0); for(char ele : a) { sb4prtln.append(ele); sb4prtln.append("\n"); } errprt(sb4prtln.toString()); } }
		final void errprtlns(boolean... a) { if(DEBUG) { sb4prtln.setLength(0); for(boolean ele : a) { sb4prtln.append(booleanToString(ele)); sb4prtln.append("\n"); } errprt(sb4prtln.toString()); } }
		final void errprtln(Object[] a) { if(DEBUG) for(Object ele : a) errprtln(ele); }
		final void errprtln(int[][] a) { if(DEBUG) for(int[] ele : a) errprtln(ele); }
		final void errprtln(long[][] a) { if(DEBUG) for(long[] ele : a) errprtln(ele); }
		final void errprtln(double[][] a) { if(DEBUG) for(double[] ele : a) errprtln(ele); }
		final void errprtln(String[][] a) { if(DEBUG) for(String[] ele : a) errprtln(ele); }
		final void errprtln(char[][] a) { if(DEBUG) for(char[] ele : a) errprtln(ele); }
		final void errprtln(boolean[][] a) { if(DEBUG) for(boolean[] ele : a) errprtln(ele); }
		final void errprtln(Object[][] a) { if(DEBUG) for(Object ele : a) { errprtln(ele); errprtln(); } }

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

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

		final void exit() { flush(); System.exit(0); }
		final <T> void exit(T a) { prtln(a); exit(); }
		final void exit(int... a) { prtln(a); exit(); }
		final void exit(long... a) { prtln(a); exit(); }
		final void exit(double... a) { prtln(a); exit(); }
		final void exit(String... a) { prtln(a); exit(); }
		final void exit(char... a) { prtln(a); exit(); }
		final void exit(boolean... a) { prtln(a); exit(); }
		final void exit(int[][] a) { prtln(a); exit(); }
		final void exit(long[][] a) { prtln(a); exit(); }
		final void exit(double[][] a) { prtln(a); exit(); }
		final void exit(String[][] a) { prtln(a); exit(); }
		final void exit(char[][] a) { prtln(a); exit(); }
		final void exit(boolean[][] a) { prtln(a); exit(); }


		final long INF = (long)1e18 + 7;
		final boolean isPlusINF(long a) { return a > INF / 10; }
		final boolean isMinusINF(long a) { return isPlusINF(- a); }
		final boolean isINF(long a) { return isPlusINF(a) || isMinusINF(a); }
		final int I_INF = (int)1e9 + 7;
		final boolean isPlusINF(int a) { return a > I_INF / 10; }
		final boolean isMinusINF(int a) { return isPlusINF(- a); }
		final boolean isINF(int a) { return isPlusINF(a) || isMinusINF(a); }


		final int min(int a, int b) { return Math.min(a, b); }
		final long min(long a, long b) { return Math.min(a, b); }
		final double min(double a, double b) { return Math.min(a, b); }
		final <T extends Comparable<T>> T min(T a, T b) { return a.compareTo(b) <= 0 ? a : b; }
		final int min(int... x) { int min = x[0]; for(int val : x) min = min(min, val); return min; }
		final long min(long... x) { long min = x[0]; for(long val : x) min = min(min, val); return min; }
		final double min(double... x) { double min = x[0]; for(double val : x) min = min(min, val); return min; }
		final int max(int a, int b) { return Math.max(a, b); }
		final long max(long a, long b) { return Math.max(a, b); }
		final double max(double a, double b) { return Math.max(a, b); }
		final <T extends Comparable<T>> T max(T a, T b) { return a.compareTo(b) >= 0 ? a : b; }
		final int max(int... x) { int max = x[0]; for(int val : x) max = max(max, val); return max; }
		final long max(long... x) { long max = x[0]; for(long val : x) max = max(max, val); return max; }
		final double max(double... x) { double max = x[0]; for(double val : x) max = max(max, val); return max; }
		final <T extends Comparable<T>> T max(T[] x) { T max = x[0]; for(T val : x) max = max(max, val); return max; }
		final int max(int[][] a) { int max = a[0][0]; for(int[] ele : a) max = max(max, max(ele)); return max; }
		final long max(long[][] a) { long max = a[0][0]; for(long[] ele : a) max = max(max, max(ele)); return max; }
		final double max(double[][] a) { double max = a[0][0]; for(double[] ele : a) max = max(max, max(ele)); return max; }
		final <T extends Comparable<T>> T max(T[][] a) { T max = a[0][0]; for(T[] ele : a) max = max(max, max(ele)); return max; }
		final long sum(int... a) { long sum = 0; for(int ele : a) sum += ele; return sum; }
		final long sum(long... a) { long sum = 0; for(long ele : a) sum += ele; return sum; }
		final double sum(double... a) { double sum = 0; for(double ele : a) sum += ele; return sum; }
		final long sum(boolean... a) { long sum = 0; for(boolean ele : a) sum += ele ? 1 : 0; return sum; }
		final long[] sums(int[] a) { long sum[] = new long[a.length + 1]; sum[0] = 0; for(int i = 0; i < a.length; i ++) sum[i + 1] = sum[i] + a[i]; return sum; }
		final long[] sums(long[] a) { long sum[] = new long[a.length + 1]; sum[0] = 0; for(int i = 0; i < a.length; i ++) sum[i + 1] = sum[i] + a[i]; return sum; }
		final double[] sums(double[] a) { double sum[] = new double[a.length + 1]; sum[0] = 0; for(int i = 0; i < a.length; i ++) sum[i + 1] = sum[i] + a[i]; return sum; }
		final long[] sums(boolean[] a) { long sum[] = new long[a.length + 1]; sum[0] = 0; for(int i = 0; i < a.length; i ++) sum[i + 1] = sum[i] + (a[i] ? 1 : 0); return sum; }

		final int constrain(int x, int l, int r) { return min(max(x, min(l, r)), max(l, r)); }
		final long constrain(long x, long l, long r) { return min(max(x, min(l, r)), max(l, r)); }
		final double constrain(double x, double l, double r) { return min(max(x, min(l, r)), max(l, r)); }
		final int abs(int x) { return x >= 0 ? x : - x; }
		final long abs(long x) { return x >= 0 ? x : - x; }
		final double abs(double x) { return x >= 0 ? x : - x; }
		final int signum(int x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }
		final int signum(long x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }
		final int signum(double x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }
		final long round(double x) { return Math.round(x); }
		final long floor(double x) { return (long)Math.floor(x); }
		final int divfloor(int a, int b) { return signum(a) == signum(b) ? a / b : - divceil(abs(a), abs(b)); }
		final long divfloor(long a, long b) { return signum(a) == signum(b) ? a / b : - divceil(abs(a), abs(b)); }
		final long ceil(double x) { return (long)Math.ceil(x); }
		final int divceil(int a, int b) { return a >= 0 && b > 0 ? (a + b - 1) / b : a < 0 && b < 0 ? divceil(abs(a), abs(b)) : - divfloor(abs(a), abs(b)); }
		final long divceil(long a, long b) { return a >= 0 && b > 0 ? (a + b - 1) / b : a < 0 && b < 0 ? divceil(abs(a), abs(b)) : - divfloor(abs(a), abs(b)); }
		final boolean mulGreater(long a, long b, long c) { return b == 0 ? c < 0 : b < 0 ? mulLess(a, - b, - c) : a > divfloor(c, b); } // a * b > c
		final boolean mulGreaterEquals(long a, long b, long c) { return b == 0 ? c <= 0 : b < 0 ? mulLessEquals(a, - b, - c) : a >= divceil(c, b); } // a * b >= c
		final boolean mulLess(long a, long b, long c) { return !mulGreaterEquals(a, b, c); } // a * b < c
		final boolean mulLessEquals(long a, long b, long c) { return !mulGreater(a, b, c); } // a * b <= c
		final double sqrt(int x) { return Math.sqrt((double)x); }
		final double sqrt(long x) { return Math.sqrt((double)x); }
		final double sqrt(double x) { return Math.sqrt(x); }
		final long fact(int n) { long ans = 1; for(int i = 1; i <= n; i ++) ans = Math.multiplyExact(ans, i); return ans; }
		final long naiveP(long n, long r) { long ans = 1; for(int i = 0; i < r; i ++) ans = Math.multiplyExact(ans, n - i); return ans; }
		final long naiveC(long n, long r) { long ans = 1; for(int i = 0; i < r; i ++) { ans = Math.multiplyExact(ans, n - i); ans /= (i + 1); } return ans; }
		final double pow(double x, double y) { return Math.pow(x, y); }
		final long pow(long x, long y) {
			long ans = 1;
			while(true) {
				if((y & 1) != 0) ans = Math.multiplyExact(ans, x);
				y /= 2;
				if(y <= 0) return ans;
				x = Math.multiplyExact(x, x);
			}
		}
		final int gcd(int a, int b) { while(true) { if(b == 0) return a; int tmp = a; a = b; b = tmp % b; } }
		final long gcd(long a, long b) { while(true) { if(b == 0) return a; long tmp = a; a = b; b = tmp % b; } }
		final long lcm(long a, long b) { return a / gcd(a, b) * b; }
		final int gcd(int... a) { int gcd = 0; for(int i = 0; i < a.length; i ++) gcd = gcd(gcd, a[i]); return gcd; }
		final long gcd(long... a) { long gcd = 0; for(int i = 0; i < a.length; i ++) gcd = gcd(gcd, a[i]); return gcd; }
		final double random() { return Math.random(); }
		final int random(int max) { return (int)floor(random() * max); }
		final long random(long max) { return floor(random() * max); }
		final double random(double max) { return random() * max; }
		final int random(int min, int max) { return random(max - min) + min; }
		final long random(long min, long max) { return random(max - min) + min; }
		final double random(double min, double max) { return random(max - min) + min; }


		final void fill(int[] a, int x) { Arrays.fill(a, x); }
		final void fill(long[] a, long x) { Arrays.fill(a, x); }
		final void fill(double[] a, double x) { Arrays.fill(a, x); }
		final void fill(char[] a, char x) { Arrays.fill(a, x); }
		final void fill(boolean[] a, boolean x) { Arrays.fill(a, x); }
		final void fill(int[][] a, int x) { for(int[] ele : a) fill(ele, x); }
		final void fill(long[][] a, long x) { for(long[] ele : a) fill(ele, x); }
		final void fill(double[][] a, double x) { for(double[] ele : a) fill(ele, x); }
		final void fill(char[][] a, char x) { for(char[] ele : a) fill(ele, x); }
		final void fill(boolean[][] a, boolean x) { for(boolean[] ele : a) fill(ele, x); }
		final void fill(int[][][] a, int x) { for(int[][] ele : a) fill(ele, x); }
		final void fill(long[][][] a, long x) { for(long[][] ele : a) fill(ele, x); }
		final void fill(double[][][] a, double x) { for(double[][] ele : a) fill(ele, x); }
		final void fill(char[][][] a, char x) { for(char[][] ele : a) fill(ele, x); }
		final void fill(boolean[][][] a, boolean x) { for(boolean[][] ele : a) fill(ele, x); }

		final int[] resize(int[] a, int m, int x) { nonNegativeCheck(m); int resized[] = new int[m]; for(int i = max(0, - x); i < a.length && i + x < m; i ++) resized[i + x] = a[i]; return resized; }
		final long[] resize(long[] a, int m, int x) { nonNegativeCheck(m); long resized[] = new long[m]; for(int i = max(0, - x); i < a.length && i + x < m; i ++) resized[i + x] = a[i]; return resized; }
		final double[] resize(double[] a, int m, int x) { nonNegativeCheck(m); double resized[] = new double[m]; for(int i = max(0, - x); i < a.length && i + x < m; i ++) resized[i + x] = a[i]; return resized; }
		final char[] resize(char[] a, int m, int x) { nonNegativeCheck(m); char resized[] = new char[m]; for(int i = max(0, - x); i < a.length && i + x < m; i ++) resized[i + x] = a[i]; return resized; }
		final boolean[] resize(boolean[] a, int m, int x) { nonNegativeCheck(m); boolean resized[] = new boolean[m]; for(int i = max(0, - x); i < a.length && i + x < m; i ++) resized[i + x] = a[i]; return resized; }
		final Object[] resize(Object[] a, int m, int x) { nonNegativeCheck(m); Object resized[] = new Object[m]; for(int i = max(0, - x); i < a.length && i + x < m; i ++) resized[i + x] = a[i]; return resized; }


public void solve() {
	SegTree st = new SegTree(1_000_000_100,
			0, (ele1, ele2) -> ele1 + ele2);
	int q = ni();
	long ans = 0;
	for(int query = 0; query < q; query ++) {
		switch(ni()) {
		case 0: st.update(nl(), nl()); break;
		case 1: ans += st.find(nl(), nl() + 1); break;
		}
	}
	prtln(ans);
}

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

	long n;
	long e;
	LongBinaryOperator f;

	NodeST root = new NodeST();

	// O(N)
	SegTree(long len, long e, LongBinaryOperator f) { this.n = len; this.e = e; this.f = f; }

	// O(logN)
	void update(long i, long val) { set(i, val, true); }
	void set(long i, long val) { set(i, val, false); }
	void set(long i, long val, boolean update) { set(root, 0, n, i, val, update); }
	NodeST set(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 = set(t.l, l, mid, i, val, update);
		else t.r = set(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) { 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) { return find(root, 0, n, l0, r0); }
	long find(NodeST t, long l, long r, long l0, long r0) {
		assertion(l <= r, "l is larger than r.");
		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));
	}
}

		// mods
		Mod md = new Mod();
		// class Mod107 extends Mod { Mod107() { super(1_000_000_007); } } Mod107 md = new Mod107();
		// class Mod998 extends Mod { Mod998() { super(998244353); } } Mod998 md = new Mod998();
		class Mod {
			// final long MOD = 1_000_000_007; Mod() { MH = 0; ML = 0; IS_MOD_CONST = true; }
			final long MOD = 998244353; Mod() { MH = 0; ML = 0; IS_MOD_CONST = true; }
			// final long MOD; Mod(long mod) { MOD = mod; IS_MOD_CONST = false; long a = (1l << 32) / MOD; long b = (1l << 32) % MOD; long m = a * a * MOD + 2 * a * b + (b * b) / MOD; MH = m >>> 32; ML = m & MASK; }

			static final long MASK = 0xffff_ffffl;
			final long MH;
			final long ML;
			final boolean IS_MOD_CONST;

			long reduce(long x) {
				if(x < 0) return (x = reduce(- x)) == 0 ? 0 : MOD - x;
				long z = (x & MASK) * ML;
				z = (x & MASK) * MH + (x >>> 32) * ML + (z >>> 32);
				z = (x >>> 32) * MH + (z >>> 32);
				x -= z * MOD;
				return x < MOD ? x : x - MOD;
			}

			final long mod(long x) {
				if(0 <= x && x < MOD) return x;
				if(- MOD <= x && x < 0) return x + MOD;
				return IS_MOD_CONST ? ((x %= MOD) < 0 ? x + MOD : x) : reduce(x);
			}
			final void mod(long[] a) { for(int i = 0; i < a.length; i ++) a[i] = mod(a[i]); }
			final void mod(long[][] a) { for(int i = 0; i < a.length; i ++) mod(a[i]); }
			final void mod(long[][][] a) { for(int i = 0; i < a.length; i ++) mod(a[i]); }

			final long add(long x, long y) { return (x += y) >= MOD ? x - MOD : x; }
			final long sub(long x, long y) { return (x -= y) < 0 ? x + MOD : x; }
			final long pow(long x, long y) {
				nonNegativeCheck(y);
				x = mod(x);
				long ans = 1;
				for(; y > 0; y /= 2) {
					if((y & 1) != 0) ans = mul(ans, x);
					x = mul(x, x);
				}
				return ans;
			}
			final long mul(long x, long y) {
				if(x >= 0 && x < MOD && y >= 0 && y < MOD) return IS_MOD_CONST ? (x * y) % MOD : reduce(x * y);
				x = mod(x);
				y = mod(y);
				return IS_MOD_CONST ? (x * y) % MOD : reduce(x * y);
			}
			final long div(long x, long y) { return mul(x, inv(y)); }

			final long[] pows(long x, int max) {
				x = mod(x);
				long pow[] = new long[max + 1];
				pow[0] = 1;
				for(int i = 0; i < max; i ++) pow[i + 1] = mul(pow[i], x);
				return pow;
			}
			final long fact(int n) { nonNegativeCheck(n); long ans = 1; for(int i = 1; i <= n; i ++) ans = mul(ans, i); return ans; }

			static final int MAX_INV_SIZE = 100_100;
			final Map<Long, Long> invMap = new HashMap<>();
			final long inv(long x) {
				x = mod(x);
				if(invMap.containsKey(x)) return invMap.get(x);
				if(invMap.size() >= MAX_INV_SIZE) return calInv(x);
				invMap.put(x, calInv(x));
				return invMap.get(x);
			}
			final long calInv(long x) { // O(logM)
				PairLL s = new PairLL(MOD, 0);
				PairLL t = new PairLL(mod(x), 1);
				while(t.a > 0) {
					long tmp = s.a / t.a;
					PairLL u = new PairLL(s.a - t.a * tmp, s.b - t.b * tmp);
					s = t;
					t = u;
				}
				if(s.b < 0) s.b += MOD / s.a;
				return s.b;
			}
			final long[] invs(int n) { // O(N)
				positiveCheck(n);
				long inv[] = new long[n + 1];
				inv[1] = 1;
				for(int i = 2; i <= n; i ++) inv[i] = mul(inv[(int)(MOD % i)], (MOD - MOD / i));
				return inv;
			}

			static final int MAX_FACT1 = 5_000_100;
			static final int MAX_FACT2 = 500_100;
			static final int MAX_FACT_MAP_SIZE = 100;
			long fact[];
			long invFact[];
			boolean isFactPrepared = false;
			final Map<Long, long[]> factMap = new HashMap<>();
			final void prepareFact() {
				fact = new long[MAX_FACT1];
				invFact = new long[MAX_FACT1];
				fill(fact, 0);
				fill(invFact, 0);
				fact[0] = 1;
				int maxIndex = min(MAX_FACT1, (int)MOD);
				for(int i = 1; i < maxIndex; i ++) fact[i] = mul(fact[i - 1], i);
				invFact[maxIndex - 1] = inv(fact[maxIndex - 1]);
				for(int i = maxIndex - 1; i > 0; i --) invFact[i - 1] = mul(invFact[i], i);

				isFactPrepared = true;
			}

			final long P(long n, long r) {
				if(!isFactPrepared) prepareFact();
				if(n < 0 || r < 0 || n < r) return 0;
				if(n < MAX_FACT1) return mul(fact[(int)n], invFact[(int)(n - r)]);
				if(!factMap.containsKey(n)) {
					long largeFact[] = new long[MAX_FACT2];
					factMap.put(n, largeFact);
					fill(largeFact, -1);
					largeFact[0] = 1;
				}
				long largeFact[] = factMap.get(n);
				if(r >= MAX_FACT2) {
					long ans = 1;
					for(long i = n - r + 1; i <= n; i ++) ans = mul(ans, i);
					return ans;
				}else {
					int i = (int)r;
					while(largeFact[i] < 0) i --;
					for(; i < r; i ++) largeFact[i + 1] = mul(largeFact[i], n - i);
					if(factMap.size() > MAX_FACT_MAP_SIZE) factMap.remove(n);
					return largeFact[(int)r];
				}
			}
			final long C(long n, long r) {
				if(!isFactPrepared) prepareFact();
				if(n < 0) return mod(C(- n + r - 1, - n - 1) * ((r & 1) == 0 ? 1 : -1));
				if(r < 0 || n < r) return 0;
				r = min(r, n - r);
				return mul(P(n, r), r < MAX_FACT1 ? invFact[(int)r] : inv(fact((int)r)));
			}
			final long H(long n, long r) { return C(n - 1 + r, r); }

			final long sqrt(long x) {
				x = mod(x);
				long p = (MOD - 1) >> 1;
				if(pow(x, p) != 1) return -1;
				long q = MOD - 1;
				int m = 1;
				while(((q >>= 1) & 1) == 0) m ++;
				long z = 1;
				while(pow(z, p) == 1) z = random(1, MOD);
				long c = pow(z, q);
				long t = pow(x, q);
				long r = pow(x, (q + 1) >> 1);
				if(t == 0) return 0;
				m -= 2;
				while(t != 1) {
					long pows[] = new long[m + 1];
					pows[0] = t;
					for(int i = 0; i < m; i ++) pows[i + 1] = mul(pows[i], pows[i]);
					while(pows[m --] == 1) c = mul(c, c);
					r = mul(r, c);
					c = mul(c, c);
					t = mul(t, c);
				}
				return r;
			}
		}

				// Pair
				class Pair<T extends Comparable<? super T>, U extends Comparable<? super U>> implements Comparable<Pair<T, U>> {
					T a; U b;
					Pair() { }
					Pair(T a, U b) { this.a = a; this.b = b; }
		
					@Override public String toString() { return "("+a.toString()+", "+b.toString()+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						Pair that = (Pair) obj;
						if(this.a.getClass() != that.a.getClass()) return false;
						if(this.b.getClass() != that.b.getClass()) return false;
						if(!this.a.equals(that.a)) return false;
						if(!this.b.equals(that.b)) return false;
						return true;
					}
					@Override public int compareTo(Pair<T, U> that) { int c = (this.a).compareTo(that.a); if(c == 0) c = (this.b).compareTo(that.b); return c; }
				}
				class PairII implements Comparable<PairII> {
					int a; int b;
					PairII() { }
					PairII(int a, int b) { this.a = a; this.b = b; }
					@Override public String toString() { return "("+a+", "+b+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						PairII that = (PairII) obj;
						if(this.a != that.a || this.b != that.b) return false;
						return true;
					}
					@Override public int compareTo(PairII that) { int c = Integer.compare(this.a, that.a); if(c == 0) c = Integer.compare(this.b, that.b); return c; }
				}
				class PairIL implements Comparable<PairIL> {
					int a; long b;
					PairIL() { }
					PairIL(int a, long b) { this.a = a; this.b = b; }
					@Override public String toString() { return "("+a+", "+b+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						PairIL that = (PairIL) obj;
						if(this.a != that.a || this.b != that.b) return false;
						return true;
					}
					@Override public int compareTo(PairIL that) { int c = Integer.compare(this.a, that.a); if(c == 0) c = Long.compare(this.b, that.b); return c; }
				}
				class PairID implements Comparable<PairID> {
					int a; double b;
					PairID() { }
					PairID(int a, double b) { this.a = a; this.b = b; }
					@Override public String toString() { return "("+a+", "+b+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						PairID that = (PairID) obj;
						if(this.a != that.a || this.b != that.b) return false;
						return true;
					}
					@Override public int compareTo(PairID that) { int c = Integer.compare(this.a, that.a); if(c == 0) c = Double.compare(this.b, that.b); return c; }
				}
				class PairLI implements Comparable<PairLI> {
					long a; int b;
					PairLI() { }
					PairLI(long a, int b) { this.a = a; this.b = b; }
					@Override public String toString() { return "("+a+", "+b+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						PairLI that = (PairLI) obj;
						if(this.a != that.a || this.b != that.b) return false;
						return true;
					}
					@Override public int compareTo(PairLI that) { int c = Long.compare(this.a, that.a); if(c == 0) c = Integer.compare(this.b, that.b); return c; }
				}
				class PairLL implements Comparable<PairLL> {
					long a; long b;
					PairLL() { }
					PairLL(long a, long b) { this.a = a; this.b = b; }
					@Override public String toString() { return "("+a+", "+b+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						PairLL that = (PairLL) obj;
						if(this.a != that.a || this.b != that.b) return false;
						return true;
					}
					@Override public int compareTo(PairLL that) { int c = Long.compare(this.a, that.a); if(c == 0) c = Long.compare(this.b, that.b); return c; }
				}
				class PairLD implements Comparable<PairLD> {
					long a; double b;
					PairLD() { }
					PairLD(long a, double b) { this.a = a; this.b = b; }
					@Override public String toString() { return "("+a+", "+b+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						PairLD that = (PairLD) obj;
						if(this.a != that.a || this.b != that.b) return false;
						return true;
					}
					@Override public int compareTo(PairLD that) { int c = Long.compare(this.a, that.a); if(c == 0) c = Double.compare(this.b, that.b); return c; }
				}
				class PairDI implements Comparable<PairDI> {
					double a; int b;
					PairDI() { }
					PairDI(double a, int b) { this.a = a; this.b = b; }
					@Override public String toString() { return "("+a+", "+b+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						PairDI that = (PairDI) obj;
						if(this.a != that.a || this.b != that.b) return false;
						return true;
					}
					@Override public int compareTo(PairDI that) { int c = Double.compare(this.a, that.a); if(c == 0) c = Integer.compare(this.b, that.b); return c; }
				}
				class PairDL implements Comparable<PairDL> {
					double a; long b;
					PairDL() { }
					PairDL(double a, long b) { this.a = a; this.b = b; }
					@Override public String toString() { return "("+a+", "+b+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						PairDL that = (PairDL) obj;
						if(this.a != that.a || this.b != that.b) return false;
						return true;
					}
					@Override public int compareTo(PairDL that) { int c = Double.compare(this.a, that.a); if(c == 0) c = Long.compare(this.b, that.b); return c; }
				}
				class PairDD implements Comparable<PairDD> {
					double a; double b;
					PairDD() { }
					PairDD(double a, double b) { this.a = a; this.b = b; }
					@Override public String toString() { return "("+a+", "+b+")"; }
					@Override public int hashCode() { return Objects.hash(a, b); }
					@Override
					public boolean equals(Object obj) {
						if(this == obj) return true;
						if(obj == null) return false;
						if(this.getClass() != obj.getClass()) return false;
						PairDD that = (PairDD) obj;
						if(this.a != that.a || this.b != that.b) return false;
						return true;
					}
					@Override public int compareTo(PairDD that) { int c = Double.compare(this.a, that.a); if(c == 0) c = Double.compare(this.b, that.b); return c; }
				}

	}
}