Garbage Bin Attack

You are given (n) garbage bins, each with an initial attack power (a_i), and an enemy named (youyou) with an initial health (W). The battle proceeds as follows:

• The bins attack sequentially in order from bin 1 to bin \(n\). When bin \(i\) attacks, \(youyou\)'s health decreases by \(a_i\), and then \(a_i\) doubles (i.e. \(a_i \leftarrow 2a_i\)).
• After the \(n\)th bin attacks, the process repeats starting from bin 1.
• The battle stops immediately when \(W \le 0\) — note that the attack which causes \(W \le 0\) (i.e. the killing blow) is not counted toward the score.

The score of a battle is defined as the total number of attacks that (youyou) successfully withstands (all attacks before the killing blow).

There are (q) battles to simulate. In each battle, you are given three integers (l), (r), and (d). Before the battle, the initial attack powers of bins (l) to (r) (inclusive) are permanently increased by (d) (i.e. these updates affect subsequent battles). Then, using (youyou)'s initial health (W) and the current state of the bins, simulate the battle and output its score.

inputFormat

The first line contains three integers (n), (q), and (W) ((1 \le n, q \le 10^5, 1 \le W \le 10^9)). The second line contains (n) positive integers (a_1, a_2, \ldots, a_n) ((1 \le a_i \le 10^9)), representing the initial attack powers of the garbage bins. Each of the next (q) lines contains three integers (l), (r), and (d) ((1 \le l \le r \le n, -10^9 \le d \le 10^9)), describing a battle query. Note that the update to the attack powers is permanent across queries.

outputFormat

For each query, output one line containing a single integer: the battle score (i.e. the number of attacks absorbed before (youyou) dies).

sample

3 1 100
10 20 30
1 2 5

3