Description

You stand on a magic cell in the beginning. And there must be exactly one interger on every magic cell and exactly four portals on its top-side, right-side, bottom-side and left-side, respectively. The integer on the magic cell where you stand in the beginning is 0.

Now you need to do Q operations. There are 4 kinds of operations:

1. Create a new magic cell. And the specific portal A on the magic cell where you stand will connect to the corresponding portal B on new magic cell(top-side is corresponding to bottom-side and vice versa; left-side is corresponding to right-side and vice versa). B will also connect to A. If A has connected to some portal before this operation, then output "Invalid" and ignore this operation(i.e do not create a new magic cell).
2. Go into the specific portal C on the magic cell where you stand(i.e move to the magic cell whose some portal is connected to portal C which is on the magic cell where you stand). If C doesn't connect to any portal, then output "Invalid" and ignore this operation(i.e do not move to other magic cell).
3. Change the integer on the magic cell where you stand.
4. Output the integer on the magic cell where you stand.

Input

The first line contains one integer Q (1 ≤ Q ≤ 10⁵) – the number of operations you need to do.

Then Q lines follow. The i+1-th line first contains one integers type_i (1 ≤ type_i ≤ 4) – the type of operations you need to execute. If the operation is one of the first three operations, then there are still some integers you need to read:

1. type_i = 1: two integers dir, val (0 ≤ dir ≤ 3, 0 ≤ val ≤ 10⁹) follow – which portal will connect to some portal on new magic cell(0 for top-side; 1 for right-side; 2 for bottom-side; 3 for left-side) and the interger on new magic cell.
2. type_i = 2: one integer dir (0 ≤ dir ≤ 3) follows – which portal you need to go into.
3. type_i = 3: one integer val (0 ≤ val ≤ 10⁹) follows – the new value for the integer on the magic cell where you stand.

Output

For every invalid operation output "Invalid" and for every type fourth operations ouput the integer on the magic cell where you stand then.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given N integers a₁, a₂, ..., a_N, may contains same integers.

You need to answer Q queries: output how many integers of a₁, a₂, ..., a_N is less than or equal to x_i.

Note: Be careful of the efficiency of your strategy.

Input

The first line contains one integer N (1 ≤ N ≤ 10⁵) – the number of integers you are given.

The second line contains N integers a₁, a₂, ..., a_N (-2 x 10⁹ ≤ a_i ≤ 2 x 10⁹).

The third line contains one integer Q (1 ≤ Q ≤ 10⁵) – the number of queries you need to answer.

Then Q lines follow. The i+3-th line contains one integer x_i (-2 x 10⁹ ≤ x_i ≤ 2 x 10⁹) – the i-th query.

It's guaranteed that:

• For every i < N,  x_i ≥ x_i+1(i.e every x_i must be less than or equal to the previous x_i).
• For the first five testcases: 1 ≤ N ≤ 1000

Output

For every query output how many integers of a₁, a₂, ..., a_N is less than or equal to x_i.

Sample Input  Download

Sample Output  Download

Tags

Discuss