## Mock CCC '20 S4 - Valentine's Day Shopping

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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 -1 if it's impossible.
• U x_i v_i: The gift at index undergoes spontaneous molecular restructuring and changes size to .

#### Constraints

For 3 of 15 available marks, .

#### Input Specification

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 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