B. Минимизируйте подмассивы с одинаковой суммой
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Как известно Фермер Джон любит перестановки, но мне они тоже нравятся!
— Сунь-Цзы, Искусство построения перестановок

Вам дана перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$.

Найдите перестановку $$$q$$$ длины $$$n$$$, которая минимизирует количество пар ($$$i, j$$$) ($$$1 \leq i \leq j \leq n$$$) таких, что $$$p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

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

Первая строка каждого набора входных данных содержит число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

Следующая строка содержит $$$n$$$ разделенных пробелом целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — перестановка $$$p$$$ длины $$$n$$$.

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

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

Для каждого набора входных данных выведите одну строку, содержащую любую перестановку $$$q$$$ длины $$$n$$$ такую, что $$$q$$$ минимизирует количество пар.

Пример
Входные данные
3
2
1 2
5
1 2 3 4 5
7
4 7 5 1 2 6 3
Выходные данные
2 1
3 5 4 2 1
6 2 1 4 7 3 5
Примечание

В первом наборе входных данных существует только одна пара ($$$i, j$$$) ($$$1 \leq i \leq j \leq n$$$) такая, что $$$p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j$$$: пара ($$$1, 2$$$). Можно доказать, что не существует перестановки $$$q$$$, для которой не существует пар.