Distinct Dishting

Limits 6s, 1.0 GB

You are given an array of NN integers. Then there will be QQ commands of the following type:

  1. Change the value of AA-th index to VV. This is represented by 0 A V\texttt{0 A V}

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

Input

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

The array elements will be between 0 and 10910^9.

Output

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

Sample

InputOutput
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=123 + 9 = 12 for the first query.


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