题目背景

注意：本场比赛提交时不开启文件输入输出，与正常的梦熊周赛保持一致。

题目描述

现在有 $n$ 个垃圾桶，它们对 youyou 发起攻击。第 $i$ 个垃圾桶的初始攻击力为正整数 $a_i$。youyou 的初始生命值为正整数 $W$。

定义如下流程为一场战斗：

• 从第 $1$ 个垃圾桶开始，每个垃圾桶依次进行攻击。第 $i$ 个垃圾桶发起攻击时，youyou 的生命值 $W$ 减去 $a_i$，然后本次战斗第 $i$ 个垃圾桶的攻击力 $a_i$ 翻倍。在第 $n$ 个垃圾桶攻击完后，重复执行此流程。

当 $W\le 0$ 时，也即 youyou 死亡时，本场战斗立刻结束。然后重置 youyou 的生命值 $W$ 以及所有垃圾桶的攻击力 $a_i$ 为本场战斗之前的值。

定义本次战斗的评分为受到垃圾桶攻击的次数（不包括恰好使 youyou 死亡的垃圾桶的攻击）。

现在一共要进行 $q$ 场战斗，每场战斗给出三个数 $l,r,d$，表示先对第 $[l,r]$ 只垃圾桶进行强化，使这些垃圾桶的初始攻击力 $a_i$ 增加 $d$，然后进行一场战斗。你需要告诉 youyou 此次战斗的评分。

每场战斗前对垃圾桶初始攻击力的增加会对之后所有的战斗产生影响。

输入格式

第一行为三个整数 $n,q,W$，分别表示垃圾桶个数、战斗次数、生命值。

第二行为 $n$ 个整数，第 $i$ 个数表示进行所有战斗之前第 $i$ 个垃圾桶的攻击力 $a_i$。

下面 $q$ 行，第 $i$ 行为三个整数 $l,r,d$，表示第 $i$ 场战斗前强化的参数。

输出格式

输出共 $q$ 行，第 $i$ 行输出一个数 $s_i$ 表示第 $i$ 次战斗的评分。

样例

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

样例 1 解释

四场战斗前的强化分别是：

• 对 $[1,1]$ 的垃圾桶增加 $1$ 点攻击力。
• 对 $[3,5]$ 的垃圾桶增加 $3$ 点攻击力。
• 对 $[3,5]$ 的垃圾桶增加 $1$ 点攻击力。
• 对 $[3,5]$ 的垃圾桶增加 $3$ 点攻击力。

第一场战斗，垃圾桶的初始攻击力分别为 $10,1,4,5,1,4$。

youyou 首先分别依次受到这些垃圾桶的攻击各一次，此时剩余生命值 $50$。垃圾桶攻击力变为 $20,2,8,10,2,8$。

接着 youyou 受到第一只垃圾桶的攻击，剩余生命值为 $30$。

受到第二只垃圾桶攻击，剩余生命值 $28$。

受到第三只垃圾桶攻击，剩余生命值 $20$。

依次类推，受到第六只垃圾桶攻击时，剩余生命值为 $0$。因为不包括致命攻击，所以共接受了 $6+5=11$ 次攻击。

第二场战斗，垃圾桶的初始攻击力分别为 $10,1,7,8,4,4$。

第三场战斗，垃圾桶的初始攻击力分别为 $10,1,8,9,5,4$。

第四场战斗，垃圾桶的初始攻击力分别为 $10,1,11,12,8,4$。

可以得出第 $2\sim 4$ 场战斗的评分分别为 $9,8,8$。

样例 2

见下发文件中的 wxyt/wxyt2.in 与 wxyt/wxyt2.ans。

该组样例满足测试点 $1\sim 4$ 的约束条件。

样例 3

见下发文件中的 wxyt/wxyt3.in 与 wxyt/wxyt3.ans。

该组样例满足测试点 $13\sim 14$ 的约束条件。

样例 4

见下发文件中的 wxyt/wxyt4.in 与 wxyt/wxyt4.ans。

该组样例满足测试点 $15\sim 20$ 的约束条件。

数据范围

本题共 $20$ 个测试点，每个 $5$ 分。

测试点编号	$n$	$q$
$1 \sim 4$	$\le 2 \times 10^5$	$\le 10$
$5 \sim 7$		$\le 10^3$
$8 \sim 10$		$\le 10^5$
$11 \sim 12$	$\le 3 \times 10^3$
$13 \sim 14$		$\le10^6$
$15 \sim 20$	$\le 2 \times 10^5$

对于全部数据，保证：$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}$。

下发文件

通过点击此链接下载下发文件。