Это интерактивная задача. Не забывайте при выводе запросов сбрасывать буфер с помощью cout.flush() или fflush(stdout) в C++ и аналогичных функций в других языках программирования.
На столе стоят \(n\) коробок с подарками, пронумерованные от \(1\) по \(n\) слева направо. Известно, что ровно в \(k\) из них лежат ценные подарки — в остальных просто камешки на удачу. Выглядят все коробки одинаково и отличить их можно только по весу. Все коробки с камнями весят одинаково и строго больше, чем коробки с ценными подарками. Массы коробок с подарками же могут как совпадать, так и различаться между собой.
Вы можете сделать не более \(50\) запросов (без учета вывода ответа). Каждым запросом вы можете сравнить массы двух непересекающихся подмножеств коробок \(a_1, a_2, \dots, a_{k_a}\) и \(b_1, b_2, \dots, b_{k_b}\) на чашечных весах. В ответ вы получите один из четырех вариантов:
- FIRST, если подмножество \(a_1, a_2, \dots, a_{k_a}\) тяжелее;
- SECOND, если подмножество \(b_1, b_2, \dots, b_{k_b}\) тяжелее;
- EQUAL, если массы подмножеств совпадают;
- WASTED, если запрос некорректен или превышено количество запросов.
Используя данные запросы (или просто интуицию), определите коробку с ценным подарком с минимальным номером.
Выходные данные
Для каждого набора входных данных выведите минимальный номер коробки, содержащей ценный подарок, в следующем формате: «! \(x\)», где \(x\) (\(1 \le x \le n\)) — искомый номер.
Протокол взаимодействия
Выводите каждый запрос в три строки. В первой строке выводите размеры подмножеств в следующем формате: «? \(k_a\) \(k_b\)», где \(k_a\) и \(k_b\) (\(1 \le k_a, k_b \le n\); \(k_a + k_b \le n\)) — их соответствующие размеры.
Во второй строке выведите \(k_a\) целых чисел \(a_1, a_2, \dots, a_{k_a}\) (\(1 \le a_i \le n\); \(a_i \neq a_j\) при \(i \neq j\)) — номера коробок в первом подмножестве.
В третьей строке выведите \(k_b\) целых чисел \(b_1, b_2, \dots, b_{k_b}\) (\(1 \le b_i \le n\); \(b_i \neq b_j\) при \(i \neq j\)) — номера коробок во втором подмножестве.
Подмножества не должны пересекаться, то есть \(a_i \neq b_j\) для всех \(i\) и \(j\).
В ответ будет получен один из четырех вариантов, описанных выше. В случае получения WASTED завершите работу программы во избежание получения вердиктов тестирования, отличных от Wrong Answer.
Примечание
Дополнительные разделители «–» в примере использованы только для наглядности самого примера. При отправке запросов и получении ответов не должно быть никаких лишних символов или переводов строк.
Взломы в данной задаче запрещены.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1
-
-
-
FIRST
-
5 2
-
-
-
FIRST
-
-
-
SECOND
-
-
-
EQUAL
-
|
-
-
? 1 1
1
2
-
! 2
-
? 1 1
1
2
-
? 2 3
4 2
1 3 5
-
? 1 1
4
5
-
! 1
|