ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1220. Stacks

Time limit: 0.5 second
Memory limit: 0.75 MB
Language limit: C, C++, Pascal
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 ≤ 109). 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

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

Notes

In C++, it is recommended to use stdio instead of iostream to save a reasonable amount of memory.
Problem Author: Pavel Atnashev
Problem Source: The Seventh Ural State University collegiate programming contest