집값 상승

버추얼 카운티(VC)의 집값이 계속 오르고 있다. 버추얼 카운티 세금징수청은 집값 변동을 추적하는 데 도움이 필요하다.

VC의 집은 1번부터 n번까지 번호가 붙어 있다. 즉 집 번호는 1, 2, 3, ..., n이다. VC는 집값이 오를 때마다 기록하고, 4번 집부터 15번 집까지처럼 구역별 집값 합계를 알고 싶어 한다.

첫 줄에 집의 개수를 나타내는 정수 n ($1 \le n \le 5 \times 10^5$)이 주어진다. 다음 n개 줄에는 집 하나의 초기 가격을 나타내는 정수가 한 줄에 하나씩 주어지며, 값은 1 이상 $10^9$ 이하다. 첫 번째 정수는 1번 집의 가격, 두 번째 정수는 2번 집의 가격이다.

그다음 줄에는 거래 수를 나타내는 정수 t ($1 \le t \le 10^5$)가 주어진다. 이어지는 t개 줄은 다음 두 종류 중 하나다.

• 갱신: 줄의 첫 글자가 U이고, 집 번호 i와 정수 x (1 이상 $10^9$ 이하)가 공백으로 구분되어 있다. 집 i의 가격을 x만큼 올린다.
• 조회: 줄의 첫 글자가 R이고, 시작 집 번호 l과 끝 집 번호 r이 공백으로 구분되어 있다. 집 l부터 집 r까지의 가격 합을 구한다. 구간은 항상 유효하여 r은 l보다 작지 않다.

갱신 거래에는 출력하지 않는다. 조회 거래마다 요청한 구간의 가격 합을 한 줄에 하나씩 출력한다.