На экзамене на мага первого ранга две команды по три мага проводят три поединка один на один. Каждый маг задается двумя параметрами: $$$s_{i,j}$$$ — сила заклинаний и $$$m_{i,j}$$$ — объем маны ($$$1 \le i \le 2$$$ — номер команды, $$$1 \le j \le 3$$$ — номер мага).

Считаем, что маг $$$X$$$ гарантированно побеждает мага $$$Y$$$, если выполнено хотя бы одно из условий:

1. $$$s_X \gt s_Y$$$ и $$$m_X \gt m_Y$$$;
2. $$$\bigl(s_X \ge 2 s_Y \ \text{или}\ m_X \ge 2 m_Y\bigr)$$$ и при этом неверно, что $$$\bigl(s_Y \ge 2 s_X \ \text{или}\ m_Y \ge 2 m_X\bigr)$$$.

Первая команда выбирает разбиение на три пары так, чтобы каждый маг сражался ровно один раз. Определите, может ли первая команда гарантированно выиграть все три поединка.

Баллы за подзадачи начисляются только в случае, если все тесты соответствующей подзадачи и необходимых подзадач успешно пройдены.

Прошли годы после победы над Королём демонов. Люди меняются быстро — у них короткая жизнь и ещё короче терпение к хаосу в архивах. Фрирен это, конечно, не волнует... пока не начинает волновать.

Во втором путешествии она всё чаще сталкивается с последствиями собственных обещаний. Десятки гильдий до сих пор хранят её старые записи о заклинаниях, артефактах и магических исследованиях. Чтобы закрыть один из долгов, Фрирен должна объединить два независимых каталога заклинаний в единый официальный свиток.

В архивах лежат две хроники:

• Хроника $$$A$$$ — записи самой Фрирен, представленные массивом $$$a$$$ длины $$$n$$$;
• Хроника $$$B$$$ — записи гильдии магов, представленные массивом $$$b$$$ длины $$$m$$$.

Каждая запись — это неотрицательное целое число, обозначающее магический индекс заклинания. Необходимо составить массив $$$c$$$ длины $$$n+m$$$, являющийся «переплетением» массивов $$$a$$$ и $$$b$$$, то есть содержащий каждый элемент массива $$$a$$$ и каждый элемент массива $$$b$$$, строго в том же порядке, в котором они следовали в $$$a$$$ и в $$$b$$$.

Более формально, требуется выбрать $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_n \le n + m$$$, после чего, определив $$$c_{i_j} = a_j$$$, а остальные индексы массива $$$c$$$ заполнить последовательно элементами массива $$$b$$$.

Определим оптимальность массива $$$c$$$ следующим образом.

1. Рассмотрим префиксы массива $$$c$$$: сначала только первый элемент, затем первые два элемента, затем первые три и так далее, вплоть до всего массива.
2. Для каждого такого префикса вычисляется его mex — минимальное целое неотрицательное число, отсутствующее среди элементов этого префикса.
3. Оптимальность массива $$$c$$$ — это сумма значений mex для всех его префиксов.

Требуется выбрать способ «переплетения» массивов $$$a$$$ и $$$b$$$, при котором оптимальность итогового массива $$$c$$$ будет наибольшей.

Баллы за группы начисляются только в случае, если все тесты соответствующей группы и необходимых групп успешно пройдены.

2 2 1
0 1
0 2

8

4 4 2
1 0 3 1
2 0 4 3

28
1 0 2 3 0 4 3 1

7 6 1
1 0 2 2 5 0 3
4 1 0 6 2 3

57

Во время экзамена магов первого ранга Ферн оказалась в коридоре многослойных иллюзий. Перед ней длинный коридор из $$$n$$$ участков, пронумерованных от $$$1$$$ до $$$n$$$. На $$$i$$$-м участке находится кристалл с энергией $$$a_i$$$. Изначально все участки полностью скрыты иллюзией.

Ферн умеет накладывать заклинания проявления на отрезки. Однако каждое заклинание действует не на все позиции отрезка.

При наложении заклинания на отрезок $$$[l, r]$$$ слой проявления добавляется на позиции, получающиеся из $$$l$$$ последовательным прибавлением шагов $$$2, 3, 2, 3, \ldots$$$ (по кругу), пока индекс не превысит $$$r$$$. То есть заклинание воздействует на позиции [ l,  l+2,  l+5,  l+7,  l+10,  ... ] (все такие позиции, не превосходящие $$$r$$$). Каждое заклинание добавляет ровно один слой проявления на каждую такую позицию.

Слои разных заклинаний на одной позиции суммируются. Если на участок действует хотя бы один слой проявления, кристалл считается доступным.

Однако Зайн вмешивается и может отменять заклинания Ферн. При отмене заклинания, наложенного на отрезок $$$[l, r]$$$, с каждой позиции, на которую действовало это заклинание, снимается ровно один слой проявления. Гарантируется, что каждая отмена соответствует одному из ранее наложенных и ещё не отменённых заклинаний Ферн на том же самом отрезке $$$[l, r]$$$.

Требуется обработать $$$q$$$ запросов трёх типов:

• + $$$l$$$ $$$r$$$ — Ферн накладывает заклинание проявления на отрезок $$$[l, r]$$$;
• - $$$l$$$ $$$r$$$ — Зайн отменяет одно активное заклинание Ферн, наложенное на отрезок $$$[l, r]$$$;
• ? $$$l$$$ $$$r$$$ — требуется определить суммарную энергию доступных кристаллов среди всех позиций от $$$l$$$ до $$$r$$$ включительно.

Для каждого запроса третьего типа выведите искомую сумму.

Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых для неё групп.