Implement a persistent queue.

Input

The first line contains the number of operations n (1 ≤ n ≤ 200000). The line number i + 1 contains the description of action i:

• 1 t m - add number m to the end of queue number t (0 ≤ t < i);
• -1 t - remove th first element from the queue number t (0 ≤ t < i).

The result of action i (given in the line i + 1) is creation of a queue number i. Initially we have an empty queue number zero.

All input numbers are 32-bit signed integers.

Output

Для каждой операции удаления выведите удалённый элемент в отдельной строке.