The trimex of an array is defined as the three smallest, non-negative integers that don't exist in an array.

For example, for the array ~[0, 1, 3, 4, 6]~ the trimex is ~[2, 5, 7]~.

Given an array ~A~ containing ~n~ numbers, you perform ~m~ "update" operations in the form ~[i, x]~. This means that you must set the ~i~-th element of the (0-indexed) to be ~x~.

After each operation, output the trimex of the array. It's time to mex it up!

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 10^5)~, the number elements in the array.

The second line contains the ~n~ elements of the array ~A_i~ ~(0 \leq A_i \leq 10^8)~.

The next line contains an integer ~m~ ~(1 \leq m \leq 10^5)~, the number of operations to perform.

The next ~m~ lines contain data for the operations, in the form ~{i, x}~ ~(0 \leq i \leq n)~, ~(0 \leq x \leq 10^8)~.

Output

Output the trimex of the array after each operation.

Example

Input

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

Output

0 2 4
0 2 6
2 5 6

• The array starts as ~A = [1, 2, 5, 7]~.
• After the first operation, ~A = [1, 3, 5, 7]~. The trimex is ~[0, 2, 4]~.
• After the first operation, ~A = [1, 3, 5, 4]~. The trimex is ~[0, 2, 6]~.
• After the first operation, ~A = [1, 3, 0, 4]~. The trimex is ~[2, 5, 6]~.