Imagine, that you are employed by a software development company. You work now on the famous "D++ project", which is devoted to the creation of a new generation programming language. Your particular task is quite prosaic, though. You are to develop the memory manager being able to work with a large number of stacks.

### Input

The first line of the input contains the total number of stack operations *N*, 0 < *N* ≤ 100000. Each of the next *N* lines contains a description of a stack operation, either in the form PUSH *A* *B* (meaning to push *B* into stack *A*), or in the form POP *A* (meaning to pop an element from stack *A*), where *A* is the number of stack (1 ≤ *A* ≤ 1000), and *B* is an integer (0 ≤ *B* ≤ 10^{9}). You may assume, that every operation is correct (i.e., before each POP operation, the respective stack is not empty).

### Output

For each POP operation, described in the input, output the value, which this POP operation gets from the top of that stack, to which it is applied. Numbers should appear according to the order of the POP operations in the input. Each number should be output in a separate line.

### Sample

input | output |
---|

7
PUSH 1 100
PUSH 1 200
PUSH 2 300
PUSH 2 400
POP 2
POP 1
POP 2 | 400
200
300 |

**Problem Author: **Pavel Atnashev

**Problem Source: **The Seventh Ural State University collegiate programming contest