在她的生日派对上收到又一个整数数组 $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$（即 $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_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$ 中的最大值非常好奇。请帮助她在每次 $m$ 次操作后找出该最大值。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $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$ 次操作后数组的最大值。

样例

输入样例 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$。