在生日聚会上收到另一个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 后,Index 决定对其执行一些操作。
正式来说,她将按顺序执行 $$$m$$$ 个操作。它们中的每一个都属于以下两种类型之一:
- $$$\texttt{+ l r}$$$。给定两个整数 $$$l$$$ 和 $$$r$$$,对于所有 $$$1 \leq i \leq n$$$ 使得 $$$l \leq a_i \leq r$$$,设置 $$$a_i := a_i + 1$$$。
- $$$\texttt{- l r}$$$。给定两个整数 $$$l$$$ 和 $$$r$$$,对于所有 $$$1 \leq i \leq n$$$ 使得 $$$l \leq a_i \leq r$$$,设置 $$$a_i := a_i - 1$$$。
例如,如果初始数组$$$a = [7, 1, 3, 4, 3]$$$,执行$$$\texttt{+} \space 2 \space 4$$$操作后,数组$$$a = [7, 1, 4, 5, 4]$$$。然后,执行$$$\texttt{-} \space 1 \space 10$$$操作后,数组$$$a = [6, 0, 3, 4, 3]$$$。
索引对数组$$$a$$$中的最大值感到好奇。请在每次 $$$m$$$ 操作后帮助她找到它。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$) - 数组的长度和操作数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 初始数组 $$$a$$$。
接下来是 $$$m$$$ 行,每行对应运算,格式如下: $$$\texttt{c l r}$$$ ($$$c \in \{\texttt +, \texttt -\}$$$、$$$l$$$ 和 $$$r$$$ 为整数,$$$1 \leq l \leq r \leq 10^9$$$) — 操作的描述。
请注意,元素 $$$a_i$$$ 经过一些操作后可能不满足 $$$1\le a_i\le 10^9$$$,如示例所示。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,所有测试用例的$$$m$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出一行包含 $$$m$$$ 整数,其中第 $$$i$$$ 描述第 $$$i$$$ 操作后数组的最大值。
示例
输入 #1
5 5 5 1 2 3 2 1 + 1 3 - 2 3 + 1 2 + 2 4 - 6 8 5 5 1 3 3 4 5 + 1 4 + 2 3 - 4 5 - 3 3 - 2 6 5 5 1 1 1 1 1 + 2 3 - 4 5 + 1 6 - 2 5 + 1 8 1 1 1 - 1 1 1 1 1000000000 + 1000000000 1000000000
输出 #1
4 4 4 5 5 5 5 4 4 3 1 1 2 1 2 0 1000000001
注意
在第一个测试用例中,操作过程如下:
- 第一次操作后,数组变得等于 $$$[2,3,4,3,2]$$$。最大值为 $$$4$$$。
- 第二次操作后,数组变得等于 $$$[1,2,4,2,1]$$$。最大值为 $$$4$$$。
- 第三次操作后,数组变得等于 $$$[2,3,4,3,2]$$$。最大值为 $$$4$$$。
- 第四次操作后,数组变得等于 $$$[3,4,5,4,3]$$$。最大值为 $$$5$$$。
- 第五次操作后,数组变得等于 $$$[3,4,5,4,3]$$$。最大值为 $$$5$$$。
在第二个测试用例中,操作过程如下:
- 第一次操作后,数组变得等于 $$$[2,4,4,5,5]$$$。最大值为 $$$5$$$。
- 第二次操作后,数组变得等于 $$$[3,4,4,5,5]$$$。最大值为 $$$5$$$。
- 第三次操作后,数组变得等于 $$$[3,3,3,4,4]$$$。最大值为 $$$4$$$。
- 第四次操作后,数组变得等于 $$$[2,2,2,4,4]$$$。最大值为 $$$4$$$。
- 第五次操作后,数组变得等于 $$$[1,1,1,3,3]$$$。最大值为 $$$3$$$。