B. Index 与最大值

时间限制：1 秒
内存限制：256 MB

在生日派对上收到又一个整数数组 $a_1, a_2, \dots, a_n$ 后，Index 决定对它执行一些操作。

具体来说，她将按顺序执行 $m$ 个操作。每个操作属于以下两种类型之一：

• + l r：给定两个整数 $l$ 和 $r$，对于所有满足 $l \le a_i \le r$ 的 $1 \le i \le n$，执行 $a_i := a_i + 1$。
• - l r：给定两个整数 $l$ 和 $r$，对于所有满足 $l \le a_i \le r$ 的 $1 \le i \le n$，执行 $a_i := a_i - 1$。

例如，如果初始数组 $a = [7,1,3,4,3]$，在执行操作 + 2 4 后，数组变为 $a = [7,1,4,5,4]$。然后，在执行操作 - 1 10 后，数组变为 $a = [6,0,3,4,3]$。

Index 对数组 $a$ 中的最大值很好奇。请帮助她在每次操作后找出这个最大值。

---

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^5$，$1 \le m \le 10^5$）—— 数组的长度和操作的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 初始数组 $a$。

接下来的 $m$ 行，每行对应一个操作，格式为：c l r（$c \in \{+, -\}$，$l$ 和 $r$ 是整数，$1 \le l \le r \le 10^9$）—— 操作的描述。

注意：经过一些操作后，元素 $a_i$ 可能不再满足 $1 \le a_i \le 10^9$，如示例所示。

数据保证：所有测试用例的 $n$ 之和不超过 $10^5$，所有测试用例的 $m$ 之和不超过 $10^5$。

---

输出格式

对于每个测试用例，输出一行，包含 $m$ 个整数，第 $i$ 个整数表示第 $i$ 次操作后数组的最大值。

---

示例

输入

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

输出

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$。