Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Distinct Dishting

By faiyaz26 · 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 AthA^{th} index to VV. This is represented by \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:

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

  • 1 A B\texttt{1 A B} (1ABN1 ≤ A ≤ B ≤ N)

The array elements will be between 00 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 = 12 for the first query.


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

Discussion

Statistics


52% Solution Ratio

nfssdqEarliest, Feb '16

tcm200403Fastest, 0.5s

bonfireLightest, 5.1 MB

Sara_HasanShortest, 1474B

Submit

Login to submit