Это интерактивная задача.

Хлоя хочет проверить свои навыки сортировки. У нее есть $$$n$$$ карточек с различными целыми числами от $$$1$$$ до $$$n$$$, записанными на них. Она просит своего младшего брата Коннора сначала закрыть ей глаза, а затем расположить все карточки в ряд в некотором порядке. Позиции карточек нумеруются от $$$1$$$ до $$$n$$$ слева направо.

Хлоя не знает порядок карточек, но она хочет отсортировать их так, чтобы самая левая карточка имела номер $$$1$$$, а самая правая карточка имела номер $$$n$$$. Формально, для каждого $$$i$$$ она хочет, чтобы карточка на позиции $$$i$$$ имела на себе число $$$i$$$. Чтобы достичь цели, Хлоя может попросить Коннора выполнить одну или несколько операций.

Каждая операция может быть обозначена двумя целыми числами $$$pos_i$$$ и $$$pos_j$$$ ($$$1 \le pos_i \lt pos_j \le n$$$). Коннор смотрит на карточки на позициях $$$pos_i$$$ и $$$pos_j$$$, и если карточка на позиции $$$pos_i$$$ имеет большее число, чем карточка на позиции $$$pos_j$$$, он меняет их местами. В противном случае он ничего не делает. Коннор также сообщает Хлое, поменял он карточки или нет.

Чтобы сделать игру более интересной, после каждых $$$2n$$$ операций Коннор выбирает две различные карточки равновероятно и меняет их местами, не сообщая Хлое ничего об этом.

Если после некоторых операций Хлои все карточки становятся отсортированными, Хлоя побеждает. Помогите Хлое отсортировать все карточки, используя не более $$$10\ 000$$$ операций.

Ваша программа должна начать с чтения одного целого числа $$$n$$$ ($$$2 \le n \le 50$$$) — количество карточек.

Ваша программа может попросить выполнить указанную операцию один или несколько раз. Чтобы выполнить операцию, ваша программа должна вывести ее описание в формате "$$$pos_i$$$ $$$pos_j$$$" — два различных числа, обозначающих позиции карточек ($$$1 \le pos_i \lt pos_j \le n$$$). Не забудьте очистить вывод после печати каждого описания операции. Затем ваша программа должна прочитать результат операции — это будет одно слово SWAPPED, если карточки были поменяны местами, или одно слово STAYED, если ничего не изменилось.

Если вместо результата операции ваша программа получает одно слово WIN, это означает, что карточки стали отсортированными. Ваша программа должна тихо завершиться после этого, запрещается выводить дополнительные операции.

После каждых $$$2n$$$ операций две различные карточки выбираются случайным образом и меняются местами, не сообщая вашей программе ничего об этом. Каждая пара карточек имеет одинаковую вероятность быть выбранной. Этот обмен не считается операцией.