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

Add Tag

Discuss