Molly, having finished the DMOPC, decides to go to a carnival! Noticing the candy apples on sale, Molly checks a map and finds the distance from the entrance to each stand, as well as which candy apples they're selling. Using the skills she has acquired from the DMOPC, she decides to model the stores as such:

• A x k: The stand ~x~ now sells candy apple ~k~.
• S x k: The stand ~x~ no longer sells candy apple ~k~, if it was previously doing so.
• E x k: The stand ~x~ has decided to move locations, and is now a distance of ~k~ from the entrance. In addition, it is no longer selling any candy apples.
• Q k: Print the closest stand that sells candy apple ~k~, or -1 if it doesn't exist.

While Molly is perfectly capable of doing this herself, you also want some candy apples, and this might just be the perfect bribe...

Input Specification

Line ~1~: Two separated integers, ~N~, and ~S~, the number of stalls, and number of stalls that sell candy apples.

Line ~2~: ~N~ space separated integers ~d_i~, the distance from the entrance to stall ~i~.

Lines ~3 \dots S + 2~ : Two space separated integers, ~s_i~ and ~a_i~, indicating that stall ~s_i~ sells candy apples of flavour ~a_i~.

Line ~S + 3~: An integer, ~Q~, the number of queries Molly has.

Lines ~S + 4 \dots S + Q + 3~: Any valid query, as described above.

Output Specification

For each Q query, print the answer on a new line.

Constraints

~1 \le N, S \le 10^5~

~1 \le d_i \le 10^9~

~1 \le s_i \le N~

~0 \le a_i < 100~

~1 \le Q \le 10^4~

In the case of ties, print the stand with the smaller id.

Sample Input

5 3
1 2 3 4 5
2 1
3 1
5 3
4
Q 1
Q 3
S 2 1
Q 1

Sample Output

2
5
3