Nikita has a stack. A stack in this problem is a data structure that supports two operations. Operation push(x) puts an integer x on the top of the stack, and operation pop() deletes the top integer from the stack, i. e. the last added. If the stack is empty, then the operation pop() does nothing.

Nikita made m operations with the stack but forgot them. Now Nikita wants to remember them. He remembers them one by one, on the i-th step he remembers an operation he made pi-th. In other words, he remembers the operations in order of some permutation p1, p2, ..., pm. After each step Nikita wants to know what is the integer on the top of the stack after performing the operations he have already remembered, in the corresponding order. Help him!

Input

The first line contains the integer m (1 ≤ m ≤ 105) — the number of operations Nikita made.

The next m lines contain the operations Nikita remembers. The i-th line starts with two integers pi and ti (1 ≤ pi ≤ m, ti = 0 or ti = 1) — the index of operation he remembers on the step i, and the type of the operation. ti equals 0, if the operation is pop(), and 1, is the operation is push(x). If the operation is push(x), the line also contains the integer xi (1 ≤ xi ≤ 106) — the integer added to the stack.

It is guaranteed that each integer from 1 to m is present exactly once among integers pi.

Output

Print m integers. The integer i should equal the number on the top of the stack after performing all the operations Nikita remembered on the steps from 1 to i. If the stack is empty after performing all these operations, print -1.

Examples

Input

2
2 1 2
1 0


Output

2
2


Input

3
1 1 2
2 1 3
3 0


Output

2
3
2


Input

5
5 0
4 0
3 1 1
2 1 1
1 1 2


Output

-1
-1
-1
-1
2

Note

In the first example, after Nikita remembers the operation on the first step, the operation push(2) is the only operation, so the answer is 2. After he remembers the operation pop() which was done before push(2), answer stays the same.

In the second example, the operations are push(2), push(3) and pop(). Nikita remembers them in the order they were performed.

In the third example Nikita remembers the operations in the reversed order.
/**
 * DA-IICT
 * Author : Savaliya Sagar
 */
import java.io.*;
import java.math.*;
import java.util.*;

public class E {

	public static int mod = 1000000007;
	public static FasterScanner in = new FasterScanner();
	public static PrintWriter o = new PrintWriter(System.out);
	public static long value[];
	public static void main(String[] args) {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					Solve();
					o.close();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	public static void Solve() {
		int m = in.nextInt();
		SegmentTree s = new SegmentTree(m);
		value = new long[m + 1];
		for(int i=0;i<m;i++) {
			int p = in.nextInt();
			int t = in.nextInt();
			if (t == 1) {
				value[p] = in.nextInt();
				s.updateRange(1, 1, m, 1, p, +1);
			} else {
				s.updateRange(1, 1, m, 1, p, -1);
			}
				o.println(s.queryRange(1, 1, m));
		}
	}

	static class SegmentTree {
		long tree[];
		long lazy[];

		public SegmentTree(int n) {
			tree = new long[4 * n];
			lazy = new long[4 * n]; // Memory allocation
		}

		void updateRange(int node, int start, int end, int l, int r, int val) {
			if (lazy[node] != 0) {
				// This node needs to be updated
				tree[node] += lazy[node]; // Update it
				if (start != end) {
					lazy[node * 2] += lazy[node]; // Mark child as lazy
					lazy[node * 2 + 1] += lazy[node]; // Mark child as lazy
				}
				lazy[node] = 0; // Reset it
			}
			if (start > end || start > r || end < l) // Current segment is not
														// within range [l, r]
				return;
			if (start >= l && end <= r) {
				// Segment is fully within range
				tree[node] += val;
				if (start != end) {
					// Not leaf node
					lazy[node * 2] += val;
					lazy[node * 2 + 1] += val;
				}
				return;
			}
			int mid = (start + end) / 2;
			updateRange(node * 2, start, mid, l, r, val); // Updating left child
			updateRange(node * 2 + 1, mid + 1, end, l, r, val); // Updating
																// right child
			tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]); // Updating
																		// root
			// with max
			// value
		}

		long queryRange(int node, int start, int end) {
			if (lazy[node] != 0) {
				// This node needs to be updated
				tree[node] += lazy[node]; // Update it
				if (start != end) {
					lazy[node * 2] += lazy[node]; // Mark child as lazy
					lazy[node * 2 + 1] += lazy[node]; // Mark child as lazy
				}
				lazy[node] = 0; // Reset it
			}
			if(tree[node]<=0)
				return -1;
			if (start == end)
				return value[start];
			int mid = (start + end) / 2;
			if (tree[2 * node + 1] + lazy[2 * node + 1] > 0) {
				return queryRange(node * 2 + 1, mid + 1, end);
			} else {
				return queryRange(node * 2, start, mid);
			}
		}
	}

	public static long gcd(long n1, long n2) {
		long r;
		while (n2 != 0) {
			r = n1 % n2;
			n1 = n2;
			n2 = r;
		}
		return n1;
	}

	public static long pow(long x, long n, long mod) {
		long res = 1;
		x %= mod;
		while (n > 0) {
			if (n % 2 == 1) {
				res = (res * x) % mod;
			}
			x = (x * x) % mod;
			n /= 2;
		}
		return res;
	}

	public static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	static class FasterScanner {
		private byte[] buf = new byte[1024];
		private int curChar;
		private int snumChars;

		public int read() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = System.in.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}
			return a;
		}

		public long[] nextLongArray(int n) {
			long a[] = new long[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextLong();
			}
			return a;
		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
	}
}
