give a optimum time and space efficient code for the folloing problem : 
Index and Maximum Value
time limit per test1 second
memory limit per test256 megabytes
After receiving yet another integer array a1,a2,…,an
 at her birthday party, Index decides to perform some operations on it.

Formally, there are m
 operations that she is going to perform in order. Each of them belongs to one of the two types:

+ l r
. Given two integers l
 and r
, for all 1≤i≤n
 such that l≤ai≤r
, set ai:=ai+1
.
- l r
. Given two integers l
 and r
, for all 1≤i≤n
 such that l≤ai≤r
, set ai:=ai−1
.
For example, if the initial array a=[7,1,3,4,3]
, after performing the operation + 2 4
, the array a=[7,1,4,5,4]
. Then, after performing the operation - 1 10
, the array a=[6,0,3,4,3]
.

Index is curious about the maximum value in the array a
. Please help her find it after each of the m
 operations.

Input
Each test consists of multiple test cases. The first line contains a single integer t
 (1≤t≤2⋅104
) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n
 and m
 (1≤n≤105
, 1≤m≤105
) — the length of the array and the number of operations.

The second line of each test case contains n
 integers a1,a2,…,an
 (1≤ai≤109
) — the initial array a
.

Then m
 lines follow, each line corresponds to the operation, in the following format: c l r
 (c∈{+,-}
, l
 and r
 are integers, 1≤l≤r≤109
) — the description of the operation.

Note that the elements ai
 may not satisfy 1≤ai≤109
 after some operations, as it is shown in the example.

It is guaranteed that the sum of n
 over all test cases does not exceed 105
, and the sum of m
 over all test cases does not exceed 105
.

Output
For each test case, output one single line containing m
 integers, with the i
-th of them describing the maximum value of the array after the i
-th operation.

Example
InputCopy
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
OutputCopy
4 4 4 5 5
5 5 4 4 3
1 1 2 1 2
0
1000000001
Note
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
.