You are given an array of N integers. Then there will be Q commands of the following type:
Change the value of A-th index to V. This is represented by 0 A V
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). 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:
0 A V (1≤A≤N,0≤V≤109)
1 A B (1≤A≤B≤N)
The array elements will be between 0 and 109.
Output
For each query 1 A B, print the required sum between A and B, on a line by itself.
Sample
Input
Output
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.