Это интерактивная задача.
Вам даны два целых числа \(c\) и \(n\). У жюри есть случайно сгенерированное множество \(A\) различных положительных чисел, не превосходящих \(c\) (оно выбирается из всех таких возможных множеств с равной вероятностью). Размер \(A\) равен \(n\).
Ваша задача угадать множество \(A\). Для того, чтобы это сделать, вы можете сделать не более \(\lceil 0.65 \cdot c \rceil\) запросов.
В каждом запросе вы можете выбрать одно целое число \(1 \le x \le c\). В качестве ответа на этот запрос вы получите побитовое исключающее ИЛИ всех таких \(y\), что \(y \in A\) и \(gcd(x, y) = 1\) (т.е. \(x\) и \(y\) взаимно просты). Если таких \(y\) не существует, то такое побитовое ИЛИ равно \(0\).
Вы можете задать все вопросы в самом начале и получить ответы на все запросы. После этого у вас не будет возможности делать запросы.
Вы должны найти любое множество \(A'\) такое, что \(|A'| = n\) и \(A'\) и \(A\) дают одинаковые ответы для всех \(c\) возможных запросов.
Протокол взаимодействия
В первой строке вы должны вывести целое число \(q\) \((0 \le q \le \lceil 0.65 \cdot c \rceil)\) — количество запросов, которые вы хотите сделать. После этого в той же строке выведите \(q\) целых чисел \(x_1, x_2, \ldots, x_q\) \((1 \le x_i \le c)\) — сами запросы.
Для этих запросов вы должны считать \(q\) целых чисел, \(i\)-е из них — это ответ на вышеописанный запрос для \(x = x_i\).
После этого во второй строке вы должны вывести \(n\) целых чисел \(A'_1, A'_2, \ldots, A'_n\) — найденное множество \(A'\).
Если существуют разные множества \(A'\), для которых ответы на все возможные запросы совпадают, то выведите любое из них.
Если вы сделаете более \(\lceil 0.65 \cdot c \rceil\) запросов, или запросы будут некорректными, интерактор немедленно завершит работу, а ваша программа получит вердикт Неправильный ответ.
После вывода запросов не забудьте вывести символ перевода строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Вы не можете делать взломы по этой задаче.
Примечание
Тест из условия сделан только для того, чтобы вы поняли протокол взаимодействия. Ваше решение не будет запускаться на тесте из условия.
В тесте из условия \(A = \{1, 4, 5, 6, 8, 10\}\). Делается \(7\) запросов, \(7 \le \lceil 0.65 \cdot 10 \rceil = 7\), поэтому ограничение на количество запросов не превышено.
Ответы на запросы:
- Для \(10\): \(1\) — единственное число в множестве \(A\), взаимно простое с \(10\), поэтому ответ \(1\)
- Для \(2\): \(1_{10} \oplus 5_{10} = 001_2 \oplus 101_2 = 4_{10}\), где \(\oplus\) — побитовое исключающее ИЛИ
- Для \(3\): \(1_{10} \oplus 4_{10} \oplus 5_{10} \oplus 8_{10} \oplus 10_{10} = 0001_2 \oplus 0100_2 \oplus 0101_2 \oplus 1000_2 \oplus 1010_2 = 2_{10}\)
- Для \(5\): \(1_{10} \oplus 4_{10} \oplus 6_{10} \oplus 8_{10} = 0001_2 \oplus 0100_2 \oplus 0110_2 \oplus 1000_2 = 11_{10}\)
- Для \(7\): \(1_{10} \oplus 4_{10} \oplus 5_{10} \oplus 6_{10} \oplus 8_{10} \oplus 10_{10} = 0001_2 \oplus 0100_2 \oplus 0101_2 \oplus 0110_2 \oplus 1000_2 \oplus 1010_2 = 4_{10}\)
- Для \(1\): \(1_{10} \oplus 4_{10} \oplus 5_{10} \oplus 6_{10} \oplus 8_{10} \oplus 10_{10} = 0001_2 \oplus 0100_2 \oplus 0101_2 \oplus 0110_2 \oplus 1000_2 \oplus 1010_2 = 4_{10}\)
- Для \(6\): \(1_{10} \oplus 5_{10} = 0001_2 \oplus 0101_2 = 4_{10}\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 6
1 4 2 11 4 4 4
|
7 10 2 3 5 7 1 6
1 4 5 6 8 10
|