在一次生日聚会上，你收到了一个整数数组 a1, a2, ..., an，她打算对它进行一些操作。

具体来说，你将执行 m 个操作，每个操作属于以下两种类型之一：

• + l r：给定两个整数 l 和 r，对所有 1 ≤ i ≤ n 使得 l ≤ ai ≤ r 的 ai 进行加 1 操作，即 ai := ai + 1。
• - l r：给定两个整数 l 和 r，对所有 1 ≤ i ≤ n 使得 l ≤ ai ≤ r 的 ai 进行减 1 操作，即 ai := ai - 1。

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

你想知道每次操作后的数组最大值。请找出在每个操作之后的最大值。

输入

每个测试包含多个测试用例。第一行包含一个整数 t（1≤t≤20,000）——测试用例的数量。每个测试用例的描述如下：

• 每个测试用例的第一行包含两个整数 n 和 m（1≤n≤100,000，1≤m≤100,000）——数组的长度和操作的数量。
• 每个测试用例的第二行包含 n 个整数 a1, a2, ..., an——初始数组 a。
• 接下来的 m 行中，每行描述一个操作，格式为 c l r（c∈{+,-}，l 和 r 是整数，1≤l≤r≤1,000,000,000）——操作的描述。

注意：在某些操作之后，元素 ai 可能不满足 1 ≤ ai ≤ 1,000,000,000 的条件，如示例所示。

输出

对于每个测试用例，输出一行包含 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