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

У цій задачі вам потрібно створити бієкцію, яка відображає кожну перестановку довжини n з k циклами в перестановку тієї ж довжини з k записами.

Перестановка p довжини n — це послідовність з n цілих чисел p(1), p(2), ..., p(n), де кожне число від 1 до 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”, оскільки дві інші перестановки з двома записами вже відповідають іншим перестановкам з двома циклами.