Вещи собраны, такси вызвано, и вот Александр уже на вокзале в ожидании своих друзей. Совсем скоро они поедут в Могилев на свою последнюю респу. Подходя к своему поезду, они проходили мимо других поездов, на каждом из которых был свой номер. И вдруг с Александром решил поспорить его так себе друг Егор. Егор сказал, что Александр не сможет из номера поезда вычислить абсолютный номер.
Номер поезда представляет из себя массив натуральных чисел $$$a$$$ размера $$$n$$$.
Абсолютный номер поезда — это количество подпоследовательностей по модулю $$$10^9+7$$$, которые являются перестановками.
Помогите нашему герою победить в этом споре, посчитайте для каждого поезда его абсолютный номер.
Каждый тест содержит несколько наборов входных данных. Первая строка теста содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Затем следуют описания наборов.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — длина массива, который представляет номер поезда соответственно.
Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), разделенных пробелами — номер поезда.
Пусть $$$S$$$ — это сумма $$$n$$$ по всем наборам входных данных.
Тогда гарантируется, что $$$S$$$ не превосходит $$$2\cdot10^6$$$.
Для каждого набора входных данных выведите абсолютный номер поезда.
| № | Дополнительные ограничения | Баллы за подзадачу | Необходимые подзадачи |
| $$$1$$$ | $$$S \le 18$$$ | $$$7$$$ | |
| $$$2$$$ | $$$a_i \leq a_{i+1}-1$$$ | $$$11$$$ | |
| $$$3$$$ | $$$a_i \neq a_j$$$ для $$$i \neq j$$$ | $$$4$$$ | $$$2$$$ |
| $$$4$$$ | $$$a_i \le 10$$$ | $$$18$$$ | |
| $$$5$$$ | $$$S \le 5000$$$ | $$$8$$$ | $$$1$$$ |
| $$$6$$$ | Нет дополнительных ограничений | $$$52$$$ | $$$1$$$ — $$$5$$$ |
2 3 1 2 1 3 1 2 3
4 3
Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов.
Перестановка — это последовательность длины $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$, в которой все числа встречаются ровно по одному разу. Например, $$$[1]$$$, $$$[4, 3, 5, 1, 2]$$$, $$$[3, 2, 1]$$$ — перестановки, а $$$[1, 1]$$$, $$$[4, 3, 1]$$$, $$$[2, 3, 4]$$$ — нет.
Оставалась одна ночь до первого тура респы. Михаил немного нервничал, ведь боялся, что не войдет в топ $$$3$$$ респы, поэтому он решил принять душ перед сном. Придя в ванну, он увидел, что на каждой плитке одной из стен было написано какое-то целое число. Посчитав, что граффити это не самое худшее в этом общежитии, Михаил спокойно пошел мыться.
Выйдя из душа, Михаил дернул ручку двери, но она не открывалась. Походя туда-сюда, наш герой зацепился ушами за лампочку на проводе, откуда выпала записка и маркер. На записке было написано, что он должен написать на каждой плитке пола какое-то целое число по особому правилу — и дверь откроется.
Стену можно представить в виде таблицы $$$a$$$ из $$$n$$$ строк и $$$m$$$ столбцов. Плитку стены — как ячейку в $$$i$$$-й строке и $$$j$$$-м столбце, а целое число на плитке — как $$$a_{i, j}$$$.
Аналогично, пол можно представить в виде таблицы $$$b$$$ из $$$n+2$$$ строк и $$$m+2$$$ столбцов.
Особое правило гласило, что Михаил должен в каждую ячейку $$$b_{i, j}$$$ записать целое число, чтобы выполнялось: $$$a_{i, j} =$$$ $$$b_{i+1, j+1}$$$ $$$xor$$$ $$$b_{i, j+1}$$$ $$$xor$$$ $$$b_{i+1, j}$$$ $$$xor$$$ $$$b_{i+2, j+1}$$$ $$$xor$$$ $$$b_{i+1, j+2}$$$ — для $$$1 \le i \le n$$$ и $$$1 \le j \le m$$$. В данном случае $$$xor$$$ — обозначает операцию побитового исключающего ИЛИ.
Помогите Михаилу найти такую таблицу $$$b$$$, иначе он нормально не выспится и плохо напишет первый тур.
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^3$$$) — количество строк и столбцов в таблице $$$a$$$.
В следующих $$$n$$$ строках заданы ячейки в соответствующей строке $$$a_{i, 1}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 2^{30}-1$$$).
Выведите таблицу $$$b$$$ из $$$n+2$$$ строк и $$$m+2$$$ столбцов, для которой выполняется особое правило.
То есть, в первых $$$n+2$$$ строках выведите ячейки в соответствующей строке $$$b_{i, 1}, \dots, b_{i, m}$$$ ($$$0 \le b_{i, j} \le 2^{30}-1$$$).
| № | Дополнительные ограничения | Баллы за подзадачу | Необходимые подзадачи |
| $$$1$$$ | $$$(n+2)\cdot(m+2) \le 18$$$ | $$$7$$$ | |
| $$$2$$$ | $$$n = 1$$$ | $$$16$$$ | |
| $$$3$$$ | Все $$$a_{i, j}$$$ равны | $$$12$$$ | |
| $$$4$$$ | $$$a_{i, j} \le 1$$$ | $$$17$$$ | |
| $$$5$$$ | $$$n, m \le 10^3$$$ | $$$21$$$ | $$$1, 2$$$ |
| $$$6$$$ | Нет дополнительных ограничений | $$$27$$$ | $$$1$$$ — $$$5$$$ |
2 2 2 0 4 3
0 0 0 0 2 0 0 0 4 0 0 3 0 0 0 0
Роман очень любит спать и опаздывать. Из-за таких качеств он проснулся только в $$$9$$$:$$$42$$$. Понимая, что он явно немного опаздывает и все уже уехали без него, он решил вызвать такси.
Выйдя из общежития, Роман увидел таксиста, который уже заждался его. И вот они уже собирались поехать, но машина не заводилась. К счастью, Роман разбирается в машинах и сразу понял, что кто-то слил все топливо из бака.
Но оказалось, что у машины был НОДовый двигатель, представляющий из себя массив натуральных чисел $$$a$$$ размером $$$n$$$. А его топливом были верные ответы на $$$q$$$ запросов вида:
В первой строке заданы два целых положительных числа $$$n$$$ и $$$q$$$ ($$$1 \leq n,q \leq 5 \cdot 10^5$$$).
Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^5$$$), разделенных пробелами — описание массива $$$a$$$.
Последние $$$q$$$ строк содержат три целых числа $$$l, r$$$ и $$$k$$$ ($$$1 \leq l \le r \leq n$$$, $$$1 \le k \le 5 \cdot 10^5$$$) — описание запросов.
Для каждого запроса выведите в отдельной строке ответ на него.
| № | Дополнительные ограничения | Баллы за подзадачу | Необходимые подзадачи |
| $$$1$$$ | $$$n, q \le 10^3$$$ | $$$3$$$ | |
| $$$2$$$ | $$$a_i \le 10$$$ | $$$8$$$ | |
| $$$3$$$ | Все $$$k_i$$$ равны | $$$11$$$ | |
| $$$4$$$ | Все $$$a_i$$$ различны | $$$12$$$ | |
| $$$5$$$ | Все $$$k_i$$$ различны | $$$16$$$ | |
| $$$6$$$ | $$$l_i = 1$$$ | $$$9$$$ | |
| $$$7$$$ | $$$n, a_i \le 3 \cdot 10^4$$$ | $$$20$$$ | |
| $$$8$$$ | Нет дополнительных ограничений | $$$21$$$ | $$$1$$$ — $$$7$$$ |
5 3 2 4 3 16 8 3 5 4 1 5 2 1 3 1
8 2 1
Нашим друзьям стало скучно ждать второго тура, и они решили порыскать по шкафчикам, которые находились в комнате. В одном из шкафчиков Максим нашел бордово-белую коробку, на которой было написано "BOBR".
Это оказалась настольная игра. Игра проходила на карте, которая представляла собой связный граф без циклов из $$$n$$$ вершин и $$$n-1$$$ ребер, то есть представляло дерево с корнем в вершине $$$1$$$. На каждой вершине $$$i$$$ изначально записано целое неотрицательное число $$$a_i$$$.
Пусть $$$pr_{v, 0}$$$ — сама вершина $$$v$$$, $$$pr_{v, 1}$$$ — прямой предок вершины $$$v$$$, тогда $$$pr_{v, k}$$$ — $$$k$$$-ый предок вершины $$$v$$$.
Не вникая сильно в правила игры, игрок может делать $$$2$$$ типа операций с этим деревом:
Поскольку друзья устали после первого тура, выполните за них $$$q$$$ операций.
Первая строка содержит два целых числа $$$n$$$, $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 10^5$$$) — количество вершин в дереве и количество операций соответственно.
Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$, обозначающие две вершины, соединённые ребром ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$). Гарантируется, что данные рёбра образуют дерево.
Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$0 \leq a_i \leq 5 \cdot 10^3$$$), разделенных пробелами — описание изначальных значений вершин.
Далее следуют $$$q$$$ строк, задающих запросы. Каждая строка задается одним из следующих форматов:
На каждый запрос второго типа выведите одно целое число — значение в вершине $$$v$$$.
| № | Дополнительные ограничения | Баллы за подзадачу | Необходимые подзадачи |
| $$$1$$$ | $$$n, q \le 10^3$$$ | $$$4$$$ | |
| $$$2$$$ | $$$u_i = i, v_i = i+1$$$ | $$$22$$$ | |
| $$$3$$$ | $$$k = 1$$$ | $$$10$$$ | |
| $$$4$$$ | Все запросы $$$1$$$ типа идут после запросов $$$2$$$ | $$$24$$$ | |
| $$$5$$$ | $$$n \le 10^5$$$ | $$$11$$$ | $$$1$$$ |
| $$$6$$$ | Нет дополнительных ограничений | $$$29$$$ | $$$1$$$ — $$$5$$$ |
5 5 1 2 2 3 3 4 1 5 1 2 4 8 11 + 3 2 5 ? 1 ? 2 + 5 1 7 ? 1
6 2 13