Valentine's day is coming up, and Larry is shopping for a gift to impress his crush!
In the gifts store, there are gifts lined up in a row, each with sizes respectively, and Larry only has boxes of size (a box of size can fit any number of gifts as long as their total size is ). 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, 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 and consider them for purchase (he doesn't actually buy them). He would like to group the gifts into contiguous groups such that the sum of all gift sizes in each group is . Your job is to tell him the minimum possible , or to tell him
-1if it's impossible.
U x_i v_i: The gift at index undergoes spontaneous molecular restructuring and changes size to .
For 3 of 15 available marks, .
The first line of input will contain , , and .
The second line of input will contain the initial values of .
The next lines will contain an event in one of the above specified forms.
Output the answer to each type
Q event, each on its own line.
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
3 2 2 5 -1
Here are the groups for each query:
[, , ]for
Q 1 3
[[3, 1], ]for
Q 1 3(second time)
[, [3, 1]]for
Q 4 6
[[3, 1], , , [3, 1], ]for
Q 1 7
Q 1 8is impossible