Записи и циклы

В этой задаче Вам следует построить биекцию биекцию, отображающую каждую перестановку длины n с k циклами в перестановку длины n с k записями.

Перестановкой p длины n называется последовательность из n целых чисел p(1), p(2), ..., p(n) таких что каждое из чисел 1, 2, ..., n встречается в последовательности ровно один раз.

Циклом в перестановке p называется последовательность чисел c_1, c_2, ..., c_m таких что p(c_1) = c_2, p(c_2) = c_3, ..., p(c_m) = c_1. Особый случай представляет собой цикл единичной длины: p(i) = i. Можно показать, что каждая перестановка может быть представлена как объединение попарно непересекающихся циклов.

Записью, или значением записи в перестановке p называется такой ее элемент p_j, который больше всех ее предшествующих элементов: p_j > p_i для каждого i < j. Отметим, что p_1 всегда является записью по определению. Можно доказать, что для заданных n и k количество перестановок длины n с k циклами равно количеству перестановок длины n с k записями. Поэтому существует биекция, отображающая перестановки длины n с k циклами в перестановки длины n с k записями и наоборот. Биекцией называется функция, которая ставит во взаимно однозначное соответствие элементы двух множеств: каждому элементу первого множества поставлен в соответствие в точности один элемент второго множества, а каждому элементу второго множества поставлен в соответствие в точности один элемент первого множества. Вам следует найти и реализовать такую функцию.

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

Первая строка содержит количество перестановок t (1 ≤ t ≤ 300 000).

Каждая из следующих t строк содержит описание одной перестановки. Описание стартует числом n (1 ≤ n ≤ 300 000) - длиной перестановки, за которым следует символ “r” или “c” указывающий на тип перестановки. Далее следует последовательность из n целых чисел, задающих саму перестановку. Каждое число от 1 до n встречается в этой последовательности только один раз.

Последовательные элементы в строке разделены пробелами. Общая длина всех входных перестановок не превосходит 300 000.

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

Имеет такой же формат как и входные данные.

Первая строка содержит количество входных перестановок t.

Для каждой из t заданных перестановок вывести соответствующую ей перестановку в отдельной строке. Если тип входной перестановки “r”, найдите количество записей в ней и выведите соответствующую ей перестановку типа “c” с таким же количеством циклов. Если тип входной перестановки “c”, найдите количество циклов в ней и выведите соответствующую ей перестановку типа “r” с таким же количеством записей.

Каждая из t строк начинается числом n - длиной перестановки, за которой следует символ указывающий на тип. Далее следуют n чисел, описывающих саму перестановку. Последовательные токены в одной строке разделять одним пробелом.

Соответствие должно быть согласующимся: если перестановке p типа “r” соответствует перестановка q типа “c”, то обратное также должно быть верным, никакая другая перестановка типа “c” не может соответствовать p, и никакая другая перестановка типа “r” не может соответствовать q. Ваша биекция не обязательно должна быть согласующейся с различными тестами.

Примеры

Примечание

Длина первой перестановки n = 3. Первая перестановка имеет тип “r” и содержит три записи. Вторая перестановка имеет тип “c” и содержит три цикла. Эти две перестановки соответствуют друг другу. Третья и четвертая перестановки имеют тип “r” и содержат каждая по две записи. Пятая перестановка имеет тип “c” и содержит два цикла. Она соответствует третьей перестановке. Четвертая перестановка соответствует перестановке 3, 2, 1 типа “c”, содержащей два цикла.

Последняя перестановка имеет длину n = 2, тип “c” и состоит из одного цикла. Она соответствует перестановке 2, 1 типа “r” с одной записью.

Отметим, что это не единственная возможная биекция: в примере дан альтернативный вариан выхода. Для третьей входной перестановки (2, 1, 3 типа “r”) мы выбрали 3, 2, 1 типа “c” как соответствующую. Тогда четвертая перестановка (2, 3, 1 типа “r”) должна иметь другую соответствующую перестановку, поэтому выберем для нее перестановку 1, 3, 2 типа “c”. Для пятой перестановки (2, 1, 3 типа “c”) единственно воззможной является 1, 3, 2 типа “r”, так как две другие перестановки с двумя записями уже соответствуют другим перестановкам с двумя циклами.