구간 합 (빈번한 갱신)

N개의 수에 대해 M개의 갱신과 K개의 구간 합 쿼리를 처리하여라. 누적합 방식으로는 시간 초과가 발생한다.

입력

첫째 줄에 N, 둘째 줄에 N개의 초기 값, 셋째 줄에 M+K, 이후 M+K개의 줄에 쿼리가 주어진다.

• 갱신: U i v (i번째 수를 v로 변경)
• 쿼리: Q l r (l부터 r까지의 합)

제약:

• 1 ≤ N ≤ 500,000
• M+K ≤ 500,000 (M: 갱신 수, K: 쿼리 수)
• 1 ≤ i ≤ N, -10^9 ≤ v ≤ 10^9
• 1 ≤ l ≤ r ≤ N

출력

각 Q 쿼리의 결과를 한 줄씩 출력한다.

예제 입력 1

10
1 2 3 4 5 6 7 8 9 10
4
Q 2 5
U 3 8
Q 2 5
Q 1 10

예제 출력 1

14
19
60