Background

Original link: https://oier.team/problems/S4A。

Problem Description

There are $n$ trash cans, and they attack youyou. The initial attack power of the $i$-th trash can is a positive integer $a_i$. youyou's initial health is a positive integer $W$.

Define the following process as one battle:

• Starting from trash can $1$, each trash can attacks in order. When the $i$-th trash can attacks, youyou's health $W$ decreases by $a_i$, and then in this battle the $i$-th trash can's attack power $a_i$ doubles. After the $n$-th trash can finishes its attack, repeat this process.

When $W \le 0$, i.e. when youyou dies, this battle ends immediately. Then reset youyou's health $W$ and all trash cans' attack power $a_i$ to the values before this battle.

The score of this battle is defined as the number of times youyou is attacked by trash cans (not including the attack that kills youyou exactly).

Now there are $q$ battles in total. For each battle, three numbers $l, r, d$ are given, meaning that you first strengthen the trash cans in $[l, r]$, increasing their initial attack power $a_i$ by $d$, and then run a battle. You need to tell youyou the score of this battle.

The increases to the trash cans' initial attack power before each battle will affect all subsequent battles.

Input Format

The first line contains three integers $n, q, W$, representing the number of trash cans, the number of battles, and the health.

The second line contains $n$ integers. The $i$-th number represents the attack power $a_i$ of the $i$-th trash can before all battles.

The next $q$ lines each contain three integers $l, r, d$, representing the strengthening parameters before the $i$-th battle.

Output Format

Output $q$ lines in total. The $i$-th line outputs one number $s_i$, representing the score of the $i$-th battle.

6 4 75
9 1 4 5 1 4
1 1 1
3 5 3
3 5 1
3 5 3

11
9
8
8

Hint

Sample Explanation #1

The strengthenings before the four battles are:

• Increase the attack power of trash cans in $[1, 1]$ by $1$.
• Increase the attack power of trash cans in $[3, 5]$ by $3$.
• Increase the attack power of trash cans in $[3, 5]$ by $1$.
• Increase the attack power of trash cans in $[3, 5]$ by $3$.

In the first battle, the initial attack powers of the trash cans are $10, 1, 4, 5, 1, 4$.

youyou is first attacked once by each of these trash cans in order, and the remaining health is $50$. The trash cans' attack power becomes $20, 2, 8, 10, 2, 8$.

Next, youyou is attacked by the first trash can, and the remaining health is $30$.

After being attacked by the second trash can, the remaining health is $28$.

After being attacked by the third trash can, the remaining health is $20$.

And so on. When attacked by the sixth trash can, the remaining health becomes $0$. Since the lethal attack is not counted, youyou received a total of $6 + 5 = 11$ attacks.

In the second battle, the initial attack powers of the trash cans are $10, 1, 7, 8, 4, 4$.

In the third battle, the initial attack powers of the trash cans are $10, 1, 8, 9, 5, 4$.

In the fourth battle, the initial attack powers of the trash cans are $10, 1, 11, 12, 8, 4$.

It can be concluded that the scores of battles $2 \sim 4$ are $9, 8, 8$, respectively.

Sample #2

See the attached wxyt/wxyt2.in and wxyt/wxyt2.ans.

This sample satisfies the constraints of test points $1 \sim 4$.

Sample #3

See the attached wxyt/wxyt3.in and wxyt/wxyt3.ans.

This sample satisfies the constraints of test points $13 \sim 14$.

Sample #4

See the attached wxyt/wxyt4.in and wxyt/wxyt4.ans.

This sample satisfies the constraints of test points $15 \sim 20$.

Constraints

This problem has $20$ test points, each worth $5$ points.

For all data, it is guaranteed that $1 \le n \le 2 \times 10^5$, $1 \le q \le 10^6$, $1 \le W \le 10^{18}$, $1 \le a_i \le 10^{6}$, $1 \le l \le r \le n$, $1 \le d \le 2^{15}$。

Translated by ChatGPT 5