有理解的设计师

时间限制：1000ms

空间限制：256MB

题目描述

仁人鱼去偷完 xlpj 的理解后，发现了做设计师的一点想法：

已知有 $k$ 个角色，第 $i$ 个角色的属性为 $i$ ，即这 $k$ 个角色的属性分别为 $1$ ~ $k$ 。

该游戏有 $n$ 项数值，第 $i$ 项数值为 $a_i$ ，权值为 $b_i$ （权值由你自由设定，可以为任意的整数，包括负数）；

$m$ 种玩法，第 $i$ 种玩法有一个 $l_i$ 和 $r_i$ ，即这种玩法仅涉及到第 $a_{l_i}$ 到 $a_{r_i}$ 项的数值；

以及 $p_i$ 个数，表示第 $i$ 个玩法相较于第 ( $i$ - $1$ ) 个玩法数值发生的变动（第 $1$ 个玩法没有相较于之前的玩法变动）。而你能做的是修改参数，最后的总属性为

$$\sum_{i=l_i}^{r_i} a_i\times b_i$$

如果最后的总属性刚好为 $j$ ，则为第 $j$ 个角色的优势区间。仁人鱼想知道，对于第 $i$ 个玩法，他不断修改每一项数值的权值，最终会有多少个角色有优势区间。

输入格式

第一行 $3$ 个正整数 $n$ , $m$ , $k$ ，分别表示数值数，玩法数和角色数。

第二行 $n$ 个数，表示第 $1$ 种玩法的各项数值

接下来 $1$ 行两个数 $l$ ， $r$ ，表示第 $1$ 种玩法会用第 $l$ 到第 $r$ 项数值

接下来为第 $2$ 到第 $m$ 种玩法对于 $a_j$ 的修改信息

先为 $1$ 个数，表示该玩法有 $p$ 条修改信息

接下来 $p$ 行，每行两个数 $pos$ , $x$ 表示将上一种玩法的 $a_{pos}$ 改为 $x$

接下来 $1$ 行两个数， $l$ ， $r$ 表示该玩法会用第 $l$ 种数值到第 $r$ 种数值

输出格式

$m$ 行,每行一个整数表示第 $i$ 种玩法会有优势区间的角色的数量

样例输入1

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

样例输出1

9
4
9
9

样例1解释

共有 $3$ 种数值

第 $1$ 个玩法的每项数值为 $1$

第一种数值权值取 $1$ ，第二，三种数值权值取 $0$ , $1 \times 1+1 \times 0+1 \times 0=1$ ，为1号角色的优势区间，第一种数值权值取 $4$ ，第二，三种数值权值取 $-1$ , $1 \times 4+1 \times (-1)+1 \times (-1)=2$ ，可为 $2$ 号角色优势区间，以此类推，可以证明每个角色都有优势区间，由于 $k$ = $9$ ，答案为 $9$ 。（权值取法不唯一，上述只提供 $1$ 种可行解）

第 $2$ 个玩法

该玩法会用第一种和第二种数值，均为 $2$

可以证明， $2$ , $4$ , $6$ , $8$ 号角色有优势区间，答案为 $4$。

第 $3$ 个玩法

该玩法每个角色均有优势区间，展示 $1$ 种 $7$ 号优势区间取法

第一号数值权值取 $0$ ，第二权值取 $2$ ，第三种权值取 $1$ ， $2 \times 0+2 \times 2+3 \times 1=7$ 第四个玩法和第三个一样，不做解释

数据范围及约定

$$n \leq 10^{5},m\leq 3 \times 10^{5},1\leq k \leq 10^{15},1 \leq a_i \leq 10^{15}, 所有修改操作的总和不超过3\times 10^{5} $$