筹备计划

题目描述

同学们现在分散在数轴上$1$~$n$的整点上，设整点$i$上的同学数量为$a_{i}$。

还有一个集合位置的候选集合$S$，初始为$\{1,2,\ldots,n\}$。

你还要处理$q$次操作，每次操作，可能发生以下事件：

• 在某个位置的同学增加$x$个或减少$x$个。
• 令某个区间$[l,r]$内的整点成为可以选择的整点（将$[l,r]$中不在$S$内的点加入$S$）。
• 令某个区间$[l,r]$内的整点成为不能选择的整点（将$S$中在$[l,r]$内的点删去）。

对于区间限制的操作，不保证操作前该区间的整点是否能选择。操作的影响都是会保留下来的。

每次操作过后，你都需要找到$S$中的一个整点$k$作为集合位置，最小化所有同学走到该点的距离总和。形式化地，你需要：

$$\min_{k \in S} \left\{ \sum_{i=1}^{n} a_{i} \times |i-k| \right\} $$

如果有多个满足条件的$k$，选择$k$最小的那个。

输入格式

第一行包含两个整数$n$，$q$，表示整点的范围和操作次数。

第二行包含$n$个整数，第$i$个整数$a_{i}$表示在初始时刻每个位置上的学生数量。

接下来$q$行，每行包含三个整数$type$，$x$，$y$：

• 若$type=1$，表示在$x$位置增加$y$名学生（保证$1 \leq x \leq n$，$1 \leq y \leq 2 \times 10^{5}$）；
• 若$type=2$，表示在$x$位置减少$y$名学生（保证$1 \leq x \leq n$，$1 \leq y \leq 2 \times 10^{5}$，$x$位置一定存在至少$y$名学生）；
• 若$type=3$，表示在$[x,y]$内的整点成为可以选择的整点（保证$1 \leq x \leq y \leq n$）；
• 若$type=4$，表示在$[x,y]$内的整点成为不能选择的整点（保证$1 \leq x \leq y \leq n$）。

输出格式

输出总共$q$行，第$i$行的数为第$i$个操作发生后，对应集合位置$k$。

无解输出$-1$。

数据范围与提示

• 对于$20\%$的数据，$n$，$q \leq 200$；
• 对于$50\%$的数据，$n$，$q \leq 2000$；
• 对于另外$30\%$的数据，不存在$type=3$和$type=4$的操作；
• 对于$100\%$的数据，$1 \leq n \leq 2 \times 10^{5}$，$1 \leq q \leq 2 \times 10^{5}$，$0 \leq a_{i} \leq 2 \times 10^{5}$。

样例

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

3
1
4
2

见position2.in

见position2.ans