Dynamic Range Sum Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

You are given an array of $n$ integers and $q$ operations. Each operation either assigns a new value to one position or asks for the sum on a contiguous range.

Input

• The first line contains two integers $n$ and $q$.
• The second line contains $n$ integers $x_1,x_2,\ldots,x_n$.
• Each of the next $q$ lines is either 1 k u, which sets $x_k=u$, or 2 a b, which asks for $x_a+x_{a+1}+\cdots+x_b$.

Output

For every operation of type 2, print the requested range sum on its own line.

Subtasks

• Subtask 1 — 20%: $1 \le n,q \le 1000$, $1 \le x_i,u \le 10^6$.
• Subtask 2 — 30%: $1 \le n,q \le 50000$, $1 \le x_i,u \le 10^9$.
• Subtask 3 — 50%: $1 \le n,q \le 2\cdot10^5$, $1 \le x_i,u \le 10^9$.

Examples

Input

8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 3 1
2 1 4

Output

14
2
11

Explanation

Initially, the sum on $[1,4]$ is $3+2+4+5=14$, and the sum on $[5,6]$ is $1+1=2$. After 1 3 1, the third value changes from $4$ to $1$, so the new sum on $[1,4]$ is $3+2+1+5=11$.