바뀌는 구간 합

첫 줄에 수의 개수 n 과 연산의 수 q (각각 1 이상 4000 이하) 가 주어집니다. 둘째 줄에 n개의 수가 주어집니다 (0 이상 1000000 이하). 이어서 q개의 줄에 연산이 주어집니다.

• 1 i v : i번째 수를 v 로 바꾼다
• 2 l r : l번째부터 r번째까지의 합을 출력한다

(모두 1번부터 셉니다.) 2 연산마다 한 줄에 하나씩 답을 출력하세요.

예시

입력

5 5
1 2 3 4 5
2 1 5
1 3 10
2 1 5
2 2 4
1 1 100

출력

15
22
16