Нечітке Сортування Перестановок

Це інтерактивна задача.

Ви маєте приховану перестановку $a[1],a[2],\dots ,a[n]$ з цілих чисел від $1$ до $n$.

Ваше завдання — відсортувати цю перестановку у зростаючому порядку, використовуючи порівняння та обмін пар елементів. Задача могла б бути простою, але автор задачі, захоплений арифметикою з плаваючою комою в задачах G і J, реалізував "неточний" компаратор:

• якщо $\frac{|a[i]-a[j]|}{max(a[i],a[j])}\le 0.01$, повертається $0$;

• інакше, якщо $a[i]<a[j]$, повертається $-1$;

• інакше, повертається $1$.

Ваша програма може робити запити для порівняння будь-яких двох елементів за допомогою цього компаратора або для обміну будь-яких двох елементів. Після кожного обміну буде повідомлено, чи стала перестановка відсортованою.

Відсортуйте перестановку розміром до $16384$, використовуючи не більше ніж $300000$ запитів.

Протокол взаємодії

Отримайте ціле число $n$ від програми журі — розмір перестановки ($1\le n\le 16384$). Потім виводьте запити та отримуйте відповіді від програми журі. Після кожного запиту вихід повинен бути очищений, а потім має бути прочитане одне ціле число — відповідь на цей запит.

Запити на порівняння мають формат "C i j", а запити на обмін мають формат "S i j", де $i$ та $j$ — індекси двох елементів ($1\le i,j\le n$). Запити з $i=j$ дозволені.

Відповідь на запит на порівняння — це $0$, якщо $a[i]$ "приблизно дорівнює" $a[j]$, інакше: $-1$, якщо $a[i]<a[j]$, і $1$, якщо $a[i]>a[j]$.

Запит на обмін змінює місцями значення в $a[i]$ та $a[j]$, і відповідь на запит на обмін — це $1$, якщо після цього обміну масив став відсортованим у зростаючому порядку, і $0$ в іншому випадку.

Ваша програма повинна завершити роботу, як тільки отримає $1$ як відповідь на запит на обмін.

Програма повинна зробити принаймні один запит на обмін. Наприклад, якщо прихована перестановка вже відсортована, вона може зробити запит "S 1 1", отримати $1$ і завершити роботу.

Інтерактор не є адаптивним. Початкова перестановка обирається програмою журі заздалегідь, до того, як ви зробите свій перший запит.

Приклади