A deployment manifest keeps the full version history of each key. It processes q operations, each one of:

• PUT key val — append val as a new version of key. Versions of a key are numbered from 1 in the order they are put. Report the version number just assigned.
• GET key v — report the value stored at version v of key. It is guaranteed that version v of that key already exists.

Keys and values are non-empty tokens of lowercase letters and digits.

Input format

Line 1: an integer q. Next q lines: PUT key val or GET key v.

Output format

For every PUT (print the new version number) and every GET (print the recalled value), in order, print one value per line.

Constraints

• 1 <= q <= 40
• 1 <= v <= number of versions of the key
• 1 <= length of key, val <= 12

5
PUT doc a
PUT doc b
GET doc 1
PUT doc c
GET doc 3

1
2
a
3
c

4
PUT k x
GET k 1
PUT k y
GET k 2

1
x
2
y