# 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!!

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 **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 **1 A B**.

### Input

Each case contains two integers **N** **(1 ≤ n ≤ 10 ^{5})** and

**q**

**(1 ≤ Q ≤ 10**. Next line will contain

^{5})**N**elements of the initial array, Then each of the next

**Q**lines contains a task in one of the following form:

0 A V

1 A B

**1 ≤ A ≤ B ≤ N**,
**0 ≤ V ≤ 10 ^{9}**

The array elements will be between **0** and **10 ^{9}**.

### Output

For each query **1 A B**, print the required sum between **x** and **y**, on a line by itself.

### Samples

Input | Output |
---|---|

5 3 1 2 3 9 1 1 1 5 0 3 9 1 1 5 | 12 9 |

#### Explanation

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.

N.B: Dataset is huge, use **faster IO**.

#### faiyaz26

Faiyaz refers to himself as a lazy software engineer. He likes coffee, sleep and solving problems. He qualified to ACM-ICPC World Finals 2016 from North South University and secured top ranks in numerous national contests. →