题目描述

Index 在生日派对上收到了另一个整数数组 $a_1,a_2,\dots,a_n$。随后，她准备对这个数组进行一些操作。

形式化地，她决定对这个数组执行 $m$ 次操作。有两种操作类型：

• 第一种操作形如 $\texttt{+ l r}$。给定两个正整数 $l,r$，将所有满足 $1\le i\le n,l\le a_i\le r$ 的 $a_i$ 的值改为 $a_i+1$。
• 第二种操作形如 $\texttt{- l r}$。给定两个正整数 $l,r$，将所有满足 $1\le i\le n,l\le a_i\le r$ 的 $a_i$ 的值改为 $a_i-1$。

举个例子，如果给定的数组 $a$ 初始为 $[7,1,3,4,3]$，在执行操作 $\texttt{+ 2 4}$ 后，数组变为 $a=[7,1,4,5,4]$。然后，在执行操作 $\texttt{- 1 10}$ 后，数组变为 $a=[6,0,3,4,3]$。

Index 对 $a$ 数组的最大值很好奇。在每次操作之后，请告诉她 $a$ 数组中的最大值。

输入格式

每个测试点有多组数据。

第一行有一个正整数 $t$，表示数据的组数。

每组数据的第一行有两个整数 $n$ 和 $m(1\le n\le10^5,1\le m\le10^5)$，分别代表数组的长度和操作的次数。

每组数据的第二行有 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示数组 $a$ 的初始值。

接下来 $m$ 行，每行描述一个操作，格式如下： $\texttt{c l r}$ （$c\in\{\texttt{+,-}\}$，$l$ 和 $r$ 是整数，满足 $1\le l\le r\le10^9$）。

注意在若干次操作后，$a$ 数组中的某些元素可能不满足 $1\le a_i\le10^9$，就像样例中给出的那样。

保证 $\sum n\le10^5,\sum m\le 10^5$。

输出格式

对于每组数据，输出一行 $m$ 个整数，第 $i$ 个整数为第 $i$ 次操作后 $a$ 数组中的最大值。

样例解释翻译

在第一组数据中，操作过程如下：

• 在第一次操作后，数组变为 $[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$。

样例

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