B. Индекс и максимальное значение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Получив на свой день рождения ещё один массив целых чисел $$$a_1, a_2, \ldots, a_n$$$, Индекс решает выполнить некоторые операции над ним.

Формально, она собирается выполнить $$$m$$$ операций по порядку. Каждая из них относится к одному из двух типов:

  • $$$\texttt{+ l r}$$$. Даны два целых числа $$$l$$$ и $$$r$$$, для всех $$$1 \leq i \leq n$$$, таких что $$$l \leq a_i \leq r$$$, присвоить $$$a_i := a_i + 1$$$.
  • $$$\texttt{- l r}$$$. Даны два целых числа $$$l$$$ и $$$r$$$, для всех $$$1 \leq i \leq n$$$, таких что $$$l \leq a_i \leq r$$$, присвоить $$$a_i := a_i - 1$$$.

Например, если начальный массив $$$a = [7, 1, 3, 4, 3]$$$, после выполнения операции $$$\texttt{+} \space 2 \space 4$$$, массив $$$a = [7, 1, 4, 5, 4]$$$. Затем, после выполнения операции $$$\texttt{-} \space 1 \space 10$$$, массив $$$a = [6, 0, 3, 4, 3]$$$.

Индекс интересует максимальное значение в массиве $$$a$$$. Пожалуйста, помогите ей найти его после каждой из $$$m$$$ операций.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$) — длина массива и количество операций.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — начальный массив $$$a$$$.

Затем следуют $$$m$$$ строк, каждая строка соответствует операции в следующем формате: $$$\texttt{c l r}$$$ ($$$c \in \{\texttt +, \texttt -\}$$$, $$$l$$$ и $$$r$$$ — целые числа, $$$1 \leq l \leq r \leq 10^9$$$) — описание операции.

Обратите внимание, что элементы $$$a_i$$$ могут не удовлетворять $$$1\le a_i\le 10^9$$$ после некоторых операций, как показано в примере.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$, и сумма $$$m$$$ по всем наборам входных данных не превышает $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую $$$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
Примечание

В первом наборе входных данных процесс операций представлен ниже:

  • После первой операции массив становится равным $$$[2,3,4,3,2]$$$. Максимальное значение $$$4$$$.
  • После второй операции массив становится равным $$$[1,2,4,2,1]$$$. Максимальное значение $$$4$$$.
  • После третьей операции массив становится равным $$$[2,3,4,3,2]$$$. Максимальное значение $$$4$$$.
  • После четвёртой операции массив становится равным $$$[3,4,5,4,3]$$$. Максимальное значение $$$5$$$.
  • После пятой операции массив становится равным $$$[3,4,5,4,3]$$$. Максимальное значение $$$5$$$.

Во втором наборе входных данных процесс операций представлен ниже:

  • После первой операции массив становится равным $$$[2,4,4,5,5]$$$. Максимальное значение $$$5$$$.
  • После второй операции массив становится равным $$$[3,4,4,5,5]$$$. Максимальное значение $$$5$$$.
  • После третьей операции массив становится равным $$$[3,3,3,4,4]$$$. Максимальное значение $$$4$$$.
  • После четвёртой операции массив становится равным $$$[2,2,2,4,4]$$$. Максимальное значение $$$4$$$.
  • После пятой операции массив становится равным $$$[1,1,1,3,3]$$$. Максимальное значение $$$3$$$.