Problem J
Which Bits?
The year is $2025$, and Eirdria has just purchased the greatest new computer model, now with $2^{63}$ bits ($1$ exbibyte) of RAM! The dramatic increase in RAM size from previous models is certainly welcomed, but along with it comes some technical quirks. One issue is that the (rather slow!) CPU was manufactured in $2005$, which is unfortunately the best model available due to the ongoing COVID-induced CPU famine. To work around this, a feature was added to the RAM enabling the CPU to query exactly how many bits are set between a given range of memory addresses.
Eirdria has just performed a computation which set at most $2^{10}$ bits throughout the RAM and would like to recover their addresses, but she needs to head out to the Council meeting now. The CPU is fast enough to perform $2^{16}$ queries to the RAM while she is out. Can you help her collect the bits by interactively performing queries?
Interaction
You may output up to $2^{16}$ queries followed by a single answer. After each query the judge will respond with the result of your query. After you output your answer, your program must terminate immediately. It is important that you flush your output stream after each query, so that the judge receives your output. In Python, for example, this can be done with sys.stdout.flush() or in C++ you can use cout << flush.
A query is performed by printing a line containing q $a$ $b$, where $a$ and $b$ are integers with $0\le a\le b\le 2^{63}-1$. The judge will then output a line containing a single integer indicating the number of bits set between RAM addresses $a$ and $b$ inclusive.
Your final answer is output by printing a line containing a $n$ $x_1$ $\dots $ $x_ n$ where $n$ is the number of bits set and $x_1,\dots ,x_ n$ are the RAM addresses of each set bit, in ascending order.
| Read | Sample Interaction 1 | Write |
|---|
q 0 9223372036854775807
3
q 0 5
3
q 0 2
2
q 0 0
0
q 3 4
0
a 3 1 2 5
