Codeforces Round 969 (Div. 2) |
---|
Finished |
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:
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.
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$$$.
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.
55 51 2 3 2 1+ 1 3- 2 3+ 1 2+ 2 4- 6 85 51 3 3 4 5+ 1 4+ 2 3- 4 5- 3 3- 2 65 51 1 1 1 1+ 2 3- 4 5+ 1 6- 2 5+ 1 81 11- 1 11 11000000000+ 1000000000 1000000000
4 4 4 5 5 5 5 4 4 3 1 1 2 1 2 0 1000000001
In the first test case, the process of the operations is listed below:
In the second test case, the process of the operations is listed below:
Name |
---|