# 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 $N$ integers. Then there will be $Q$ commands of the following type:

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

2. 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

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.

### Statistics

52% Solution Ratio

nfssdqEarliest, Feb '16

tcm200403Fastest, 0.5s

bonfireLightest, 5.1 MB

Sara_HasanShortest, 1474B

### Submit 