관측소

N개의 관측소가 일렬로 있으며, 각 관측소의 초기 온도가 주어진다. 다음 두 가지 연산을 수행해야 한다.

• 연산 1: a번째 관측소부터 b번째 관측소까지의 온도 합을 구한다.
• 연산 2: c번째 관측소의 온도를 d로 변경한다.

Q개의 연산이 주어질 때, 각 연산 1에 대한 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 관측소 수 N과 연산 수 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 100,000) 둘째 줄에 N개의 정수(초기 온도)가 공백으로 구분되어 주어진다. (각 온도 ≤ 100,000) 셋째 줄부터 Q개의 줄에 연산 정보가 주어진다.

• 연산 1: "1 a b" (a ≤ b)
• 연산 2: "2 c d"

출력

각 연산 1의 결과를 한 줄에 하나씩 출력한다.

입출력 예시

입력 1

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

출력 1

9

입력 2

6 4
5 3 7 2 8 1
1 1 6
2 4 9
1 3 5
2 2 6

출력 2

26
24