Raphael has developed a new operating system. A new file is created in it in two ways: copy a previously created file and add some number to it, or copy a previously created file and delete the last number from it. If the file being copied is empty and a delete operation is applied to it, then an empty file is created again.

At the very beginning Raphael's operating system contains only one empty file "root". File "root" has number 0.

Raphael wants to create files one after another. i-th file can be created in one of two ways:

1) "push id x" - create the copy of file with number id (id < i) and to the end of a new file add number x (0 ≤ x ≤ 109). Print the amount of numbers in the newly created file (it has number i).

2) "pop id" - create the copy of file with number id (id < i) and from the new file delete the last number (if it exists). Print the deleted number (or "-1" if it does not exist).

Input

The first line contains the number n (1 < n ≤ 3 * 105) of created files. The following lines contain ways to create files: i - th line describes one of two ways to create the i - th file.

Output

Each time you create a new file print the desired result.