#215519. [USACO26FEB] Milk Buckets S

There are () buckets in a stack where the -th bucket from the top has capacity gallons (). A tap above the top bucket sends one gallon of milk per second into the first bucket per second. There is also a pool below bucket .

When a bucket reaches its capacity after seconds, at the start of the th second it flips to dump its contents into either the bucket below if it is not the last bucket or the pool otherwise (it reverts back to filling at the end of the th second). A bucket cannot collect milk while it is flipped; any milk arriving at the bucket above during this second is lost. Additionally, any amount of milk exceeding the capacity of the bucket below is lost.

Handle () queries, each specified by three integers , , and :

• First, set ().
• Then answer the following question: Suppose that at time , all buckets as well as the pool are empty. Determine the number of gallons of milk in the pool after seconds ().

The updates persist through later queries.

The first line contains .

The second line contains .

The next line contains .

Then the following lines contain three integers , , and . This means that you should set and then answer the question for .

Output the answer to each question on a separate line.

样例输入 1

3
1 1 1
30
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 10

样例输出 1

0
0
0
1
1
2
2
3
3
4
0
0
0
0
1
1
1
2
2
2
0
0
0
0
1
1
1
2
2
2

样例输入 2

2
1 2
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10

样例输出 2

0
0
0
0
2
2
2
2
4
4

样例输入 3

3
1 1 1
1
1 1 1000000000000000000

样例输出 3

499999999999999999

Sample 1 Explanation

When ,

• Bucket flips at times
• Bucket flips at times
• Bucket flips at times

When ,

• Bucket flips at times
• Bucket flips at times
• Bucket flips at times

When ,

• Bucket flips at times
• Bucket flips at times
• Bucket flips at times

SCORING:

• Inputs 4-5: , and all
• Inputs 6-11:
• Inputs 12-23: No additional constraints.

Problem credits: Akshaj Arora