Valentine's day is coming up, and Larry is shopping for a gift to impress his crush!

In the gifts store, there are $N$ gifts lined up in a row, each with sizes $s_1,s_2,\dots ,s_N$ respectively, and Larry only has boxes of size $B$ (a box of size $B$ can fit any number of gifts as long as their total size is $\le B$). As he is very stingy and wants to use as few boxes as possible, he wants you to help him minimize the number of boxes. Additionally, $Q$ times during his shopping trip, one of the two following events will happen:

• Q l_i r_i: Larry will look at the subarray of gifts $s_{l_i},s_{l_i+1},\dots ,s_{r_i}$ and consider them for purchase (he doesn't actually buy them). He would like to group the gifts into $x$ contiguous groups such that the sum of all gift sizes in each group is $\le B$. Your job is to tell him the minimum possible $x$, or to tell him -1 if it's impossible.
• U x_i v_i: The gift at index $x$ undergoes spontaneous molecular restructuring and changes size to $v$.

Constraints

$1\le N,Q\le {10}^5$

$1\le l_i\le r_i\le N$

$1\le x_i\le N$

$1\le B,s_i,v_i\le {10}^9$

For 3 of 15 available marks, $1\le N,Q\le 100$.

Input Specification

The first line of input will contain $N$, $Q$, and $B$.

The second line of input will contain the initial values of $s_1,s_2,\dots ,s_N$.

The next $Q$ lines will contain an event in one of the above specified forms.

Output Specification

Output the answer to each type Q event, each on its own line.

Sample Input

8 6 4
3 2 3 3 3 1 1 99
Q 1 3
U 2 1
Q 1 3
Q 4 6
Q 1 7
Q 1 8

Sample Output

3
2
2
5
-1

Sample Explanation

Here are the groups for each query:

• [[3], [2], [3]] for Q 1 3
• [[3, 1], [3]] for Q 1 3 (second time)
• [[3], [3, 1]] for Q 4 6
• [[3, 1], [3], [3], [3, 1], [1]] for Q 1 7
• Q 1 8 is impossible