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

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 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 ≤ 105) and q (1 ≤ Q ≤ 105). 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:

0 A V

1 A B

1 ≤ A ≤ B ≤ N, 0 ≤ V ≤ 109

The array elements will be between 0 and 109.

Output

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

Samples

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

Author
  • faiyaz26's Avatar

    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.
Discussion
Submit

Login to submit