You are given an array of $N$ integers. Then there will be $Q$ commands of the following type:

Change the value of $A^{th}$ index to $V$. This is represented by \texttt{0 A V}$

Answer the summations of distinct numbers between indices $A$ and $B$ (inclusive) that are multiples of 3. This is represented by the command $\texttt{1 A B}$.

Input

Each case contains two integers $N$ ($1 ≤ N ≤ 10^5$) and $Q$ ($1 ≤ Q ≤ 10^5$). The next line will contain $N$ elements of the initial array, Then each of the next $Q$ lines contains a task in one of the following form:

$\texttt{0 A V}$ ($1 ≤ A ≤ N, 0 ≤ V ≤ 10^9$)

$\texttt{1 A B}$ ($1 ≤ A ≤ B ≤ N$)

The array elements will be between $0$ and $10^9$.

Output

For each query $\texttt{1 A B}$, print the required sum between $A$ and $B$, on a line by itself.

Sample

Input

Output

5 3
1 2 3 9 1
1 1 5
0 3 9
1 1 5

12
9

For the first test case, distinct numbers between index 1 and 5 are 1, 2, 3, 9. Among this distinct numbers 3 and 9 are the multiple of 3, so the sum is 3 + 9 = 12 for the first query.

The data set is huge, please use fast I/O methods.