Xor-quiz
Contest: Codeforces Global Round 16
Difficulty rating: 3200
Tags: constructive algorithms, dp, interactive, math, number theory

This is an interactive problem.

You are given two integers $$$c$$$ and $$$n$$$. The jury has a randomly generated set $$$A$$$ of distinct positive integers not greater than $$$c$$$ (it is generated from all such possible sets with equal probability). The size of $$$A$$$ is equal to $$$n$$$.

Your task is to guess the set $$$A$$$. In order to guess it, you can ask at most $$$\lceil 0.65 \cdot c \rceil$$$ queries.

In each query, you choose a single integer $$$1 \le x \le c$$$. As the answer to this query you will be given the bitwise xor sum of all $$$y$$$, such that $$$y \in A$$$ and $$$gcd(x, y) = 1$$$ (i.e. $$$x$$$ and $$$y$$$ are coprime). If there is no such $$$y$$$ this xor sum is equal to $$$0$$$.

You can ask all queries at the beginning and you will receive the answers to all your queries. After that, you won't have the possibility to ask queries.

You should find any set $$$A'$$$, such that $$$|A'| = n$$$ and $$$A'$$$ and $$$A$$$ have the same answers for all $$$c$$$ possible queries.

Input format:
Firstly you are given two integers $$$c$$$ and $$$n$$$ ($$$100 \le c \le 10^6$$$, $$$0 \le n \le c$$$).

Interaction format:
In the first line you should print an integer $$$q$$$ $$$(0 \le q \le \lceil 0.65 \cdot c \rceil)$$$ — the number of queries you want to ask. After that in the same line print $$$q$$$ integers $$$x_1, x_2, \ldots, x_q$$$ $$$(1 \le x_i \le c)$$$ — the queries.

For these queries you should read $$$q$$$ integers, $$$i$$$-th of them is the answer to the described query for $$$x = x_i$$$.

After that you should print $$$n$$$ distinct integers $$$A'_1, A'_2, \ldots, A'_n$$$ — the set $$$A'$$$ you found.

If there are different sets $$$A'$$$ that have the same answers for all possible queries, print any of them.

If you will ask more than $$$\lceil 0.65 \cdot c \rceil$$$ queries or if the queries will be invalid, the interactor will terminate immediately and your program will receive verdict Wrong Answer.

After printing the queries and answers do not forget to output end of line and flush the output buffer. Otherwise, you will get the Idleness limit exceeded verdict. To do flush use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- Read documentation for other languages.

Hacks

You cannot make hacks in this problem.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
The sample is made only for you to understand the interaction protocol. Your solution will not be tested on the sample.

In the sample $$$A = \{1, 4, 5, 6, 8, 10\}$$$. $$$7$$$ queries are made, $$$7 \le \lceil 0.65 \cdot 10 \rceil = 7$$$, so the query limit is not exceeded.

Answers for the queries:

- For $$$10$$$: $$$1$$$ is the only number in the set $$$A$$$ coprime with $$$10$$$, so the answer is $$$1$$$
- For $$$2$$$: $$$1_{10} \oplus 5_{10} = 001_2 \oplus 101_2 = 4_{10}$$$, where $$$\oplus$$$ is the bitwise xor
- For $$$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}$$$
- For $$$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}$$$
- For $$$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}$$$
- For $$$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}$$$
- For $$$6$$$: $$$1_{10} \oplus 5_{10} = 0001_2 \oplus 0101_2 = 4_{10}$$$

Example input:
10 6

1 4 2 11 4 4 4

Example output:
7 10 2 3 5 7 1 6

1 4 5 6 8 10

Editorial:
Let $$$f(x)$$$ be the multiplication of all prime divisors of $$$x$$$. Then let's make queries for all such $$$y$$$ that there is at least one such $$$x$$$, $$$1 \le x \le C$$$ and $$$f(x) = y$$$. For such constraints there will be at most $$$\lceil 0.65 \cdot C \rceil$$$ queries.
Let's group all numbers by $$$f(x)$$$. All numbers in one group in any query will be considered together. Let $$$ans(x)$$$ be the answer for the query with number $$$x$$$ and $$$g(x)$$$ be the $$$xor$$$ of all number that are not coprime with $$$x$$$. Then $$$g(x)=ans(x) \oplus ans(1)$$$. Now let's find out how to calculate the $$$xor$$$ of all such $$$x$$$ that $$$f(x)$$$ is divisible by an arbitrary $$$y$$$. Let's take $$$xor$$$ of all $$$g(k)$$$ where $$$k$$$ is a divisor of $$$y$$$ greater than $$$1$$$. Let's prove that by doing that we will get the needed value. If $$$f(x)$$$ is divisible by $$$y$$$ then such $$$x$$$ will be considered $$$2^l - 1$$$ times, where $$$l$$$ is the amount of prime divisors of $$$y$$$. It means that $$$x$$$ will be contained in the final value. Now let's prove that there will be no unintended $$$x$$$ values. Let $$$f(x)$$$ be not divisible by $$$y$$$. It means that there is suche prime $$$p$$$ that $$$y$$$ is divisible by $$$p$$$ and $$$x$$$ is not divisible by $$$p$$$. Then for each divisor $$$a$$$ of $$$y$$$ that is divisible by $$$p$$$ we will assign $$$b=a/p$$$. Then such $$$x$$$ will be considered either for both $$$a$$$ and $$$b$$$ or for none of them. It means that it will be considered an even amount of times. Now to find the $$$xor$$$ of all numbers with an arbitrary $$$f(x)$$$ we need to consider all $$$x$$$ from $$$C$$$ to $$$1$$$ and make $$$f(x) = f(x) \oplus f(2x) \oplus f(3x) \oplus \ldots$$$.
Now we only need to find $$$n$$$ distinct numbers from $$$1$$$ to $$$C$$$ such that $$$xor$$$ of numbers in each group is equal to a specific number. For each group of numbers with given $$$f(x)$$$ we will start the Gaussian elimination. Let $$$k$$$ be the size of a group and after the Gaussian elimination there are $$$b$$$ non-zero numbers. Then if $$$b=k$$$ there is a single way to obtain the needed $$$xor$$$. Else there are $$$2^{k-b}$$$ ways to obtain the needed $$$xor$$$. Now let's take some random sets of numbers with the needed $$$xor$$$ and calculate dp on these numbers to get take exactly $$$n$$$ numbers. If there are several ways we can choose any of them.