说明

在平原国，流经大平原的富饶大河——大平河。多年前，这条河流被划分给了 $n$ 个渔业企业，每个企业最初得到了一个连续的河段。对于第 $i$ 个企业（按从上游到下游的顺序），最初的河段长度为 $a_i$。

多年来，河流上的渔业企业经历了 $k$ 次变化事件。每个事件的类型有两种：破产和分裂。

事件类型：

• 事件 1：破产 某个企业破产，其所占用的河段将转交给相邻的企业。如果破产的企业只有一个相邻企业，则该相邻企业完全接管该河段。如果破产的企业有两个相邻企业，则该河段将被分为两部分，分割方式如下：

  • 如果河段的长度是偶数，则将其均匀地分为两段。
  • 如果河段的长度是奇数，则将其分为两段，差距为 $1$，且更靠近上游的部分较小。

• 事件 2：分裂 某个企业的河段分裂成两个。假设原企业的河段长度为 $a$，且 $a \geq 2$，则按照以下规则进行分裂：

  • 如果河段的长度是偶数，则将其均匀地分为两段。
  • 如果河段的长度是奇数，则将其分为两段，差距为 $1$，且更靠近上游的部分较小。

每次企业发生破产或分裂后，企业的数量都会发生变化。破产事件导致一个企业消失，分裂事件会产生两个新的企业。

因此，经过每次事件后，每个企业都拥有一个新的河段。

财政部建议对渔业企业征收与其所拥有的河段长度的平方成正比的税。为了分析该税如何运作，财政部长希望通过现有的数据了解，在每次事件后，所有企业所拥有的河段长度的平方和是如何变化的。

任务：编写程序，根据给定的初始河段划分和随后的 $k$ 次事件，计算在每次事件发生后，所有企业拥有的河段长度的平方和。

输入格式

第一行输入两个整数：$n$ 和 $p$ —— 初始的企业数量（$2 \leq n \leq 100 000$）以及任务编号（$0 \leq p \leq 4$）。

第二行输入 $n$ 个整数：$a_1, a_2, ..., a_n$，表示每个企业所拥有的初始河段长度。

第三行输入一个整数 $k$ —— 事件的数量（$1 \leq k \leq 100 000$）。

接下来 $k$ 行，每行描述一个事件。每个事件由两个整数 $e_i$ 和 $v_i$ 组成，其中：

• $e_i = 1$ 表示第 $v_i$ 个企业破产。
• $e_i = 2$ 表示第 $v_i$ 个企业发生了分裂。

保证每次事件后，涉及的企业编号在当前企业列表中有效。

输出格式

输出文件应包含 $k + 1$ 个整数，第一个整数表示初始时刻所有企业河段长度的平方和，之后的每一行表示事件发生后所有企业河段长度的平方和。

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

75
105
73
101
83
113

提示

示例说明

在每一个事件发生后，企业之间的河段分配如下图所示：

任务评价系统与子任务说明

子任务 1（30分）

$2 \leq n \leq 100$，$1 \leq k \leq 100$，$1 \leq a_i \leq 100$，$p = 1$。

子任务 2（30分）

$2 \leq n \leq 100 000$，$1 \leq k \leq 100 000$，$1 \leq a_i \leq 10^4$，$p = 2$。

子任务 3（20分）

$2 \leq n \leq 100 000$，$1 \leq k \leq 100 000$，$1 \leq a_i \leq 10^4$，$p = 3$。

所有事件类型 $e_i = 1$（即只有企业破产，没有分裂）。

子任务 4（20分）

$2 \leq n \leq 100 000$，$1 \leq k \leq 100 000$，$1 \leq a_i \leq 10^4$，$p = 4$。

翻译来源：GPT 5.2。