E1. Что останется в конце? (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное различие между двумя версиями заключается в наборе допустимых значений для начального массива и для $$$x$$$ в операциях типа $$$1$$$. В этой версии все эти значения принадлежат множеству $$$\{-1,0,1\}$$$. Совершать взломы можно только в том случае, если решены обе версии задачи.

Перед своей последней миссией Ктолли задаёт Виллему три вопроса.

Второй вопрос таков: что останется, если небо действительно достигнет своего конца?

Виллем не может ответить ей напрямую. Вместо этого он открывает хронику, содержащую $$$n$$$ записей, пронумерованных от $$$1$$$ до $$$n$$$. Каждая запись содержит целое число: положительное значение обозначает надежду, а отрицательное — отчаяние.

Начальное содержимое хроники образует массив $$$a_1,a_2,\ldots,a_n$$$, называемый версией $$$0$$$. Затем Ктолли выполняет $$$q$$$ операций. Для каждого $$$1\le i\le q$$$ $$$i$$$-я операция создаёт новую версию $$$i$$$ на основе версии $$$i-1$$$.

Каждая операция относится к одному из следующих четырёх типов:

  • $$$\texttt{1 l r x}$$$: установить $$$a_k\gets x$$$ для каждого $$$l\le k\le r$$$.
  • $$$\texttt{2 l r}$$$: установить $$$a_k\gets -a_k$$$ для каждого $$$l\le k\le r$$$.
  • $$$\texttt{3 l r}$$$: установить $$$a_k\gets\max(a_k,0)$$$ для каждого $$$l\le k\le r$$$.
  • $$$\texttt{4 p}$$$: рассмотрим значение в позиции $$$p$$$ в каждой предыдущей версии $$$0,1,\ldots, i-1$$$. Пусть эти значения будут $$$b_0,b_1,\ldots,b_{i-1}$$$. Найдите максимальную сумму по всем непустым подмассивам$$$^{\text{∗}}$$$ этой последовательности.

Если операция относится к типу $$$1$$$, $$$2$$$ или $$$3$$$, указанное изменение применяется к версии $$$i-1$$$ для получения версии $$$i$$$. Операция типа $$$4$$$ не изменяет массив, поэтому версия $$$i$$$ совпадает с версией $$$i-1$$$.

Операции закодированы и должны обрабатываться по порядку. Их декодирование зависит от $$$\mathrm{lastans}$$$ (ответа на предыдущий вопрос), который обновляется после каждой операции типа $$$4$$$.

Помогите Виллему ответить на каждую операцию типа $$$4$$$.

$$$^{\text{∗}}$$$Массив $$$c$$$ является подмассивом массива $$$b$$$, если $$$c$$$ может быть получен из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

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

В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$q$$$ ($$$1\le n,q\le5\cdot10^5$$$) — длина массива и количество операций.

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i\in\{-1,0,1\}$$$) — массив в версии $$$0$$$.

Каждая из следующих $$$q$$$ строк описывает одну операцию в одном из следующих кодированных форматов: Первое целое число в строке — тип операции.

  • $$$\texttt{1 u v x}$$$ ($$$0\le u,v \lt 2^{64}$$$, $$$x\in\{-1,0,1\}$$$);
  • $$$\texttt{2 u v}$$$ ($$$0\le u,v \lt 2^{64}$$$);
  • $$$\texttt{3 u v}$$$ ($$$0\le u,v \lt 2^{64}$$$);
  • $$$\texttt{4 u}$$$ ($$$0\le u \lt 2^{64}$$$).

Операции закодированы и должны обрабатываться по порядку. Их декодирование зависит от значения $$$\mathrm{lastans}$$$.

Изначально $$$\mathrm{lastans}=0$$$. После вычисления результата операции типа $$$4$$$ установите $$$\mathrm{lastans}$$$ равным остатку от деления её результата на $$$2^{64}$$$. Операции всех остальных типов оставляют $$$\mathrm{lastans}$$$ без изменений.

Для каждой закодированной координаты $$$y$$$ определим $$$d(y)=\left(\left(y\oplus\mathrm{lastans}\right)\bmod n\right)+1$$$. Здесь, $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

  • Для операции $$$\texttt{1 u v x}$$$ вычисляются $$$l=\min(d(u),d(v))$$$ и $$$r=\max(d(u),d(v))$$$. Значение $$$x$$$ не кодируется.
  • Для операции $$$\texttt{2 u v}$$$ или $$$\texttt{3 u v}$$$ вычисляются $$$l=\min(d(u),d(v))$$$ и $$$r=\max(d(u),d(v))$$$.
  • Для операции $$$\texttt{4 u}$$$ вычисляется $$$p=d(u)$$$.

Тип операции не кодируется. Не забудьте обновить $$$\mathrm{lastans}$$$ после выполнения каждой операции типа $$$4$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5\cdot10^5$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$5\cdot10^5$$$.

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

Для каждой операции типа $$$4$$$ выведите одно целое число — максимальную сумму непустого подмассива последовательности значений в позиции $$$p$$$ во всех версиях, предшествующих этой операции.

Пример
Входные данные
2
4 8
1 -1 1 -1
4 1
2 18446744073709551615 18446744073709551613
4 18446744073709551614
3 0 3
1 0 2 -1
4 0
2 2 0
4 0
3 6
1 -1 1
4 0
1 0 3 -1
4 3
2 2 3
3 3 0
4 3
Выходные данные
-1
1
3
1
1
2
2
Примечание

В первом наборе входных данных для первой операции $$$\mathrm{lastans}=0$$$, поэтому закодированная координата $$$1$$$ декодируется в позицию $$$2$$$. Рассматривается только версия $$$0$$$. Значение в позиции $$$2$$$ равно $$$-1$$$, следовательно, ответ равен $$$-1$$$.

Теперь $$$\mathrm{lastans}=2^{64}-1=18\,446\,744\,073\,709\,551\,615$$$. Следовательно, закодированный интервал $$$[18\,446\,744\,073\,709\,551\,615,18\,446\,744\,073\,709\,551\,613]$$$ декодируется в $$$[1,3]$$$, а закодированная координата $$$18\,446\,744\,073\,709\,551\,614$$$ декодируется в позицию $$$2$$$.

До второго запроса значения в позиции $$$2$$$ в версиях $$$0$$$, $$$1$$$ и $$$2$$$ равны $$$-1$$$, $$$-1$$$ и $$$1$$$ соответственно. Максимальная сумма их непустых подмассивов равна $$$1$$$.

До третьего запроса значения в позиции $$$2$$$ в версиях $$$0,1,\ldots,5$$$ образуют последовательность $$$[-1,-1,1,1,1,-1]$$$. Три последовательных значения, равных $$$1$$$, образуют подмассив с суммой $$$3$$$.

Обратите внимание, что первый, второй и третий запросы создают версии $$$1$$$, $$$3$$$ и $$$6$$$ соответственно, хотя они и не изменяют массив.

Во втором наборе входных данных первый запрос касается позиции $$$1$$$, поэтому его ответом является $$$1$$$. Тогда $$$\mathrm{lastans}=1$$$, и закодированная операция $$$\texttt{1 0 3 -1}$$$ декодируется в $$$\texttt{1 2 3 -1}$$$.

Перед вторым запросом значения в позиции $$$3$$$ в версиях $$$0$$$, $$$1$$$ и $$$2$$$ равны соответственно $$$1$$$, $$$1$$$ и $$$-1$$$, поэтому ответ равен $$$2$$$.

После этого $$$\mathrm{lastans}=2$$$. Кодированные операции $$$\texttt{2 2 3}$$$ и $$$\texttt{3 3 0}$$$ декодируются в $$$\texttt{2 1 2}$$$ и $$$\texttt{3 2 3}$$$ соответственно. До последнего запроса значения в позиции $$$2$$$ в версиях $$$0,1,\ldots,5$$$ образуют последовательность $$$[-1,-1,-1,-1,1,1]$$$, максимальная сумма непустого подмассива которой равна $$$2$$$.