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