Problem J
Test Scheduling

“It’s like this. Stan works as a P.I. and the local cops have hired him as a night watchman over at Walker’s warehouse. The Walkers have been printing counterfeit fifty dollar bills and they were raided last night. There are 2005 sacks but there may be a few with real money, because they had managed to sell some of it at $50 for ten fake $50 bills. The police don’t know that some bags may have real money, but I know a test...”

“So you want to grab a sack of green and skip town?,” you say. “So what’s keeping you? Just test one bill from each sack!”

“No, that’s no good. I only have enough chemicals down at the lab where I work to do 76 tests. The good thing is I can grab bills from many sacks and do a single test. If at least one of the bills is real, the test comes out positive, otherwise it comes out negative, but I don’t know how to find the real money with only 76 tests. That’s your kind of problem.”

“Well, that’s real’ easy. First you take bills from half the sacks and run a test, then if it comes out positive, you run another test on bills from half of those sacks and then... Look, you’ll only need eleven tests total.” Somehow you can tell from Anna’s expression that this isn’t helpful.

“The FBI will be here to burn it in three days. The test takes about 6 hours and must be run at night, when the lab’s deserted. So each night I can run a batch of tests in parallel, but I won’t know the results until early in the morning.”

“OK, but if there is exactly one sack of real money, then you could still...”

“Look, Matty Walker told Stan that there may be none, one, two, or three sacks of real money, and we want them all. If you can figure out how to do this with at most 76 tests and be done in three nights, we’ll split it with you!”

Problem

Write a program that schedules three rounds of testing. You will find out the result of round $1$ before you schedule round $2$, and you will find out the result of round $2$ before you schedule round $3$. There are $n \le 2005$ sacks of money. Each sack is full of counterfeit bills except for at most three that are full of real money. The total number of tests in the three rounds combined cannot be more than $76$. After round $3$ your program should output which bags have real money in them (if any). Bags are numbered from $1$ to $n$.

Interaction

There are five rounds of interaction (numbered $0$–$4$):

0, read:

Read a single integer $n$ ($1 \le n \le 2005$), the number of bags of money, from standard input.

1, write:

Write the first test batch to standard output (and make sure you flush the buffer), see the format below.

1, read:

Read the results of the first batch from standard input, see the format below.

2, write:

Write the second test batch to standard output.

2, read:

Read the results of the second batch from standard input.

3, write:

Write the third test batch to standard output.

3, read:

Read the results of the third batch from standard input.

4, write:

Output a single line. It should consist of an integer $r$ ($0 \le r \le 3$, the number of sacks with real money) followed by $r$ integers giving the indices of the sacks of real money in ascending order. Consecutive integers are to be separated by a single space.

The format of a test batch is as follows. First write a line with an integer $t \ge 0$. This is the number of tests in this batch. Then write $t$ lines, each describing a test. Each line is a string of length $n$ (excluding the newline character) of the characters ‘0’ and ‘1’. The $i$’th character (numbered $1$ through $n$) indicates if a bill from the $i$’th sack is used in this test or not (‘1’ means it is used).

The results of the test batch is a line of length $n$ (excluding the newline character) of the characters ‘0’ and ‘1’. The $j$’th character indicates whether the $j$’th test involved at least one real bill (‘1’ for yes and ‘0’ for no).

To facilitate testing of your solutions, we provide a simple testing tool that you can download from the problem statement page on Kattis.

NB! It is vital that you flush standard output after each round schedule has been written!

6

3
111000
010101
000011

111

2
000010
000001

11

4
000100
100000
010000
001000

0010

3 2 5 6