The God of Death is a famous assassin. As his student, you are assigned to keep track of ~N~ targets, numbered ~1, 2, \dots, N~. The God of Death will then give you ~Q~ queries.

1. C x y: The ~x~-th target moves to location ~y~. This action marks the beginning of a new day.
2. 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?

Input Specification

The first line will contain ~N~.
The next line will contain ~N~ integers, ~L_1, L_2, \dots, L_N~, the locations of the ~N~ targets on day 0.
The next line will contain ~Q~.
The next ~Q~ lines will each contain a valid query, as described above.

Output Specification

Output the answer to each Q query on a new line.

Constraints

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~

Sample Input

3
2 3 1
6
C 3 2
C 2 1
Q 1 1
Q 2 2
C 1 3
Q 3 3

Sample Output

2
1
2