is doing a contest. He comes across the following problem:
You have an array of elements, indexed from to . There are operations you need to perform on it.
Each operation is one of the following:
C x vChange the -th element of the array to .
S l rOutput the sum of all the elements from the -th to the -th index, inclusive.
Q vOutput how many elements are less than or equal to in the array.
At any time, every element in the array is between and (inclusive).
knows that one fast solution uses a Binary Indexed Tree. He practices that data structure every day, but still somehow manages to get it wrong. Will you show him a working example?
The first line has and .
The second line has integers, the original array.
The next lines each contain an operation in the format described above.
Q operation, output the answer on its own line. Note that you may need to use 64-bit integers to store the answer.
10 10 4 8 4 5 6 3 2 2 8 1 C 7 6 Q 7 S 2 3 S 1 4 C 4 9 S 2 3 Q 6 C 3 9 S 6 7 Q 6
8 12 21 12 7 9 6