You are given N numbers. You have to perform two kinds of operations:
U x y - x-th number becomes equal to y.
Q x y - calculate the sum of distinct numbers from x-th to y-th. It means that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7).

Input

The first line of input contains an integer N. 1<=N<=50000
The second line consists of N numbers.
The third line consists of an integer Q. 1<=Q<=100000
The following Q lines will consist of queries of the form described in the task description.
All numbers in input will fit in the signed 32-bit type.

Output

Output an answer for every query of the second type.

Example

Input:
5
1 2 4 2 3
3
Q 2 4
U 4 7
Q 2 4

Output:
6
13

Hint: Time limit is ~ 1.5*(my program's execution time in the worst case)