Шахматы с Говоруном
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Птица Говорун отличается умом и сообразительностью, умом и сообразительностью.

Во время утомительного полёта Алиса решила сыграть со своим новым другом Говоруном в шахматы. Попугай Говорун слишком умён для классических шахмат, поэтому он предложил обновлённую версию.

Игра ведётся на доске $$$n \times n$$$. Сначала Говорун тайно расставляет $$$n$$$ ладей, чтобы они не били друг друга, запоминает их позиции и убирает с доски. Затем Алиса расставляет $$$n$$$ ладей, чтобы они не били друг друга.

Алиса хочет, чтобы количество её ладей, совпавших с ладьями Говоруна по позиции, было чётным. Если девочка не справляется, Говорун сообщает ей позиции угаданных ладей и даёт вторую попытку.

Помогите Алисе выиграть своего умного друга.

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

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

В каждом наборе содержится единственное целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — размер доски.

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

Протокол взаимодействия

Вы можете выполнить не более двух ходов.

Чтобы сделать ход, выведите $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le n$$$) — вертикали ладей, которые выставляет Алиса.

После каждого хода вы должны считать строку, содержащую вердикт.

Существуют три вердикта:

- «WIN» — вы выиграли, ваша программа должна перейти к обработке следующего набора входных данных;
- «LOSE» — вы проиграли, ваша программа должна немедленно завершиться;
- «AGAIN» — вы не выиграли первым ходом, но у вас остался ещё один. Во второй строке дано целое число $$$k$$$ ($$$1 \le k \le n$$$) — количество угаданных ладей Говоруна. В третьей строке даны $$$k$$$ целых чисел — вертикали, на которых вы угадали ладей Говоруна.

Не забывайте сбрасывать буфер после каждого вывода. Для этого можете использовать std::endl в C++ или стандартную функцию print в Python. Не используйте ios_base::sync_with_stdio(false) в C++.

Обратите внимание, что из-за особенностей тестирующей системы вы можете получить вердикт «Ошибка во времени исполнения» вместо вердикта «Неправильный ответ».

Пример

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

    1
    4
    AGAIN
    1
    1
    WIN

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

    1 2 3 4
    1 3 4 2