After receiving yet another integer array $a_1, a_2, \ldots, a_n$ 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:

• $\texttt{+ l r}$. Given two integers $l$ and $r$, for all $1 \leq i \leq n$ such that $l \leq a_i \leq r$, set $a_i := a_i + 1$.
• $\texttt{- l r}$. Given two integers $l$ and $r$, for all $1 \leq i \leq n$ such that $l \leq a_i \leq r$, set $a_i := a_i - 1$.

For example, if the initial array $a = [7, 1, 3, 4, 3]$, after performing the operation $\texttt{+} \space 2 \space 4$, the array $a = [7, 1, 4, 5, 4]$. Then, after performing the operation $\texttt{-} \space 1 \space 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 \leq t \leq 2 \cdot 10^4$) — 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 \leq n \leq 10^5$, $1 \leq m \leq 10^5$) — the length of the array and the number of operations.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the initial array $a$.

Then $m$ lines follow, each line corresponds to the operation, in the following format: $\texttt{c l r}$ ($c \in \{\texttt +, \texttt -\}$, $l$ and $r$ are integers, $1 \leq l \leq r \leq 10^9$) — the description of the operation.

Note that the elements $a_i$ may not satisfy $1\le a_i\le 10^9$ 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 $10^5$, and the sum of $m$ over all test cases does not exceed $10^5$.

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.

见题面 Input 部分

见题面 Output 部分

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