CF2007B Index and Maximum Value

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

In the first test case, the process of the operations is listed below: - After the first operation, the array becomes equal $ [2,3,4,3,2] $ . The maximum value is $ 4 $ . - After the second operation, the array becomes equal $ [1,2,4,2,1] $ . The maximum value is $ 4 $ . - After the third operation, the array becomes equal $ [2,3,4,3,2] $ . The maximum value is $ 4 $ . - After the fourth operation, the array becomes equal $ [3,4,5,4,3] $ . The maximum value is $ 5 $ . - After the fifth operation, the array becomes equal $ [3,4,5,4,3] $ . The maximum value is $ 5 $ . In the second test case, the process of the operations is listed below: - After the first operation, the array becomes equal $ [2,4,4,5,5] $ . The maximum value is $ 5 $ . - After the second operation, the array becomes equal $ [3,4,4,5,5] $ . The maximum value is $ 5 $ . - After the third operation, the array becomes equal $ [3,3,3,4,4] $ . The maximum value is $ 4 $ . - After the fourth operation, the array becomes equal $ [2,2,2,4,4] $ . The maximum value is $ 4 $ . - After the fifth operation, the array becomes equal $ [1,1,1,3,3] $ . The maximum value is $ 3 $ .