The God of Death is a famous assassin. As his student, you are assigned to keep track of ~N~ targets, numbered ~1, 2, \ldots N~. The God of Death will then give you ~Q~ queries.
C x y: The ~x~-th target moves to location ~y~. This action marks the beginning of a new day.
Q x y: Return the location of the ~x~-th target on the ~y~-th day. It is guaranteed that if it is currently day ~d~, ~y \le d~.
Can you answer the God of Death's queries?
The first line will contain ~N~.
The next line will contain ~N~ integers, ~L_1, L_2, \ldots, L_N~, the locations of the ~N~ targets on day 0.
The next line contains ~Q~.
The next ~Q~ lines will each contain a valid query, as described above.
Output the answer to each
Q query on a new line.
For all subtasks,
~1 \le L_i \le 10^9~
~1 \le x \le N~
~1 \le Q \le 10^5~
Subtask 1 [30%]:
~1 \le N \le 10^3~
Subtask 2 [70%]:
~1 \le N \le 10^6~
3 2 3 1 6 C 3 2 C 2 1 Q 1 1 Q 2 2 C 1 3 Q 3 3
2 1 2