E. Elementary Data Structure Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Determined to improve her skills, Nikolle climbed the highest mountain known to humanity, going beyond the clouds. There, she found a monastery, where the great master Z lived. Training with him, Nikolle acquired powerful knowledge about competitive programming, such as Segment Tree Beats, Sweepline Mo, and 3D Hull Online.

After months of improvement, Nikolle returned to UnB and decided to share her knowledge with her peers. However, before delving into overly complex topics, she decided to propose a simpler challenge: to implement the weakest data structure she knows, the Serpistent Teg.

A Serpistent Teg maintains a list of stacks, initially with no stacks. The structure supports the following operations:

  • Type $$$1$$$: add an empty stack to the end of the list. If the list had $$$S$$$ stacks before this addition, the added stack receives the identifier $$$S+1$$$.
  • Type $$$2$$$: receive $$$i$$$ and $$$x$$$, and add the number $$$x$$$ to the top of stack $$$i$$$.
  • Type $$$3$$$: receive $$$i$$$ and $$$j$$$, and print the $$$j$$$-th number added to stack $$$i$$$ (if the stack has $$$T$$$ numbers, the top element was the $$$T$$$-th added).

Show Nikolle that you have what it takes to learn her techniques!

Input

The first line of the input contains an integer $$$Q$$$: the number of operations to be performed $$$(1 \leq Q \leq 100)$$$.

Each of the next $$$Q$$$ lines describes an operation to be performed, and the operations must be executed in the order they are given in the input. These lines start with an integer $$$t$$$, indicating the type of operation according to the statement $$$(1 \leq t \leq 3)$$$.

  • If $$$t = 1$$$, there are no other integers on this line.
  • If $$$t = 2$$$, two integers $$$i$$$ and $$$x$$$ follow on this line. It is guaranteed that, before performing this operation, the list has at least $$$i$$$ stacks and that $$$1 \leq x \leq 100$$$.
  • If $$$t = 3$$$, two integers $$$i$$$ and $$$j$$$ follow on this line. It is guaranteed that, before performing this operation, the list has at least $$$i$$$ stacks and that stack $$$i$$$ has at least $$$j$$$ numbers.
Output

For every operation of type $$$3$$$, print the $$$j$$$-th number added to stack $$$i$$$. Print only one number per line, in the order they appear in the input.

Example
Input
13
1
2 1 3
3 1 1
1
2 1 4
2 2 5
3 2 1
3 1 2
1
2 3 1
2 3 2
3 3 2
3 1 1
Output
3
5
4
2
3