Description

UPD(2020/12/25 22:40): We update the description to make the problem clearer("puzzle floor mat" has been replaced by "magic cell"). Sorry for the inconvenience.

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 and there is a DP(dynamic portal) on the magic cell where you stand in the beginning.

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

1. Create a new magic cell. And some 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.
2. Go into some 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).
3. Change the integer on the magic cell where you stand.
4. Output the integer on the magic cell where you stand.
5. Create a new DP on the magic cell where you stand. And remove the previous DP(so there must be exactly one DP at the same time).
6. Move to the magic cell where DP is.

It's guaranteed that:

• For every time you do operation 1, portal A must not connect to any portal.
• For every time you do operation 2, portal C must connect to some portal.

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 ≤ 6) – 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 fourth operations output the integer on the magic cell where you stand then.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss