题目背景

转眼已经开学两月之久了 , 为了考察一下大家的基础算法能力 , 我们来做一道练习题 .

题目描述

小明有 t 个工作日 , 对于每个工作日他有 $x$ 任务 , 初始第 $i$ 件任务的工作量为 $a_i$ . 但是计划总是赶不上变化 , 即使小明在最开始已经知道了每件任务的工作量 , 但每次开会都会使一些任务的工作量发生变化 . 会议有两种形式 :

1. $+$ L R , 意味着所有 $L \le a_i \le R$ 的任务 , 工作量都加 $1$.
2. $-$ L R , 意味着所有 $L \le a_i \le R$ 的任务 , 工作量都减 $1$. $( 1 \le L,R \le 10^9)$

今天一共会举办 $y$ 场会议 , 求每举办一次会议后 , 小明工作量最大的任务的工作量是多少 。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 2 \times 10^4)$ 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $x$ 和 $y$ $( 1 \le x ,y \le 10^5)$ 第二行包含 $x$个正整数 $a_1, a_2, \cdots , a_x$ $(1 \le a_i \le 10^9)$ ,表示每件任务的初始工作量, 接下来 $y$ 行，描述每场会议的形式和范围。

输出格式

对于每个测试用例，分别输出每次会议结束后小明最大的任务工作量。

测试样例

1
5 2
1 2 3 4 5
+ 2 4
- 2 5

5 4

2
5 5
1 2 3 2 1
+ 1 3
- 2 3
+ 1 2
+ 2 4
- 6 8
1 1
1000000000
+ 1000000000 1000000000

4 4 4 5 5
1000000001

题目限制

1s, 256MB.