You are given an array of integers. Then there will be commands of the following type:
Change the value of -th index to . This is represented by
Answer the summations of distinct numbers between indices and (inclusive) that are multiples of 3. This is represented by the command .
Each case contains two integers () and (). The next line will contain elements of the initial array, Then each of the next lines contains a task in one of the following form:
The array elements will be between 0 and .
For each query , print the required sum between and , on a line by itself.
5 3 1 2 3 9 1 1 1 5 0 3 9 1 1 5
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 for the first query.
The data set is huge, please use fast I/O methods.