This is an interactive problem.

There are $n+1$ people, numbered from $0$ to $n$. The $i$-th person ($0 \le i \le n-1$) has an integer $a_i$ in the range $[0, 2^m-1]$.

The person numbered $n$ wishes to know the value of $a_0+a_1+\cdots+a_{n-1}$. To achieve this, they can communicate as follows:

1. First, select the number of seconds $N$ for communication.
2. For each of the next $N$ seconds, all $i$ ($0 \le i \le n-1$) simultaneously send one bit of information to $(i+1)$.
   • The message is received before the start of the next second. Specifically, the message sent in the last second is not received.
   • No other form of communication is allowed.

You need to complete this task using as few communication seconds as possible.

Implementation Details

Ensure that your program starts with #include "mpc.h".

You do not need to, and should not, implement the main function. You need to implement the following two functions:

int precalc(int n, int m);

• n represents the number of people, and m represents the range of the integers.
• You need to return the number of communication seconds $N$.

bool transmit(player &player, int round, int position);

• round represents the current second of communication, taking an integer value in $[1, N]$;
• position represents the index of the person currently transmitting information, taking an integer value in $[0, n]$;
• player is a struct type that describes the person currently transmitting. This struct is implemented in mpc.h and contains the following two member variables:
  • A boolean variable last_message, representing the information transmitted by the previous person in the previous second. If position is $0$ or round is $1$, the value of last_message is always $0$;
  • An integer array memory of size $4096$, describing the "memory" of the person currently transmitting.
    • In the transmit function, this array can be modified arbitrarily.
    • player.memory can only be modified within the transmit function. If player.memory is not modified in the transmit function, the same person will store the same values when transmitting multiple times.
    • The initial values of player.memory are set according to the following rules:
      • When position is not $n$, bits $0$ to $m-1$ of memory take values in $\{0, 1\}$, describing the binary representation of $a_{\text{position}}$ from least significant to most significant (i.e., the $i$-th bit corresponds to the weight $2^i$), and all other positions are $0$;
      • Otherwise, all positions in the array are $0$.
• You need to return the information this person transmits to the next person in this second.
  • When position is $n$ or round is $N$, this return value has no effect.

After all transmit calls are completed, you must ensure that the first $2200$ bits of the player.memory of the person numbered $n$ are in $\{0, 1\}$, and the corresponding binary number is the sum of all $a_i$.

Under the conditions and constraints of the problem, the interactive library consumes at most $0.15$ seconds of time and $128\text{MiB}$ of space.

Using other forms of communication in the program, including but not limited to using global variables, will be considered an attack on the interactive library.

Testing Your Program

A reference implementation of the interactive library, grader.cpp, is provided in the problem directory. The actual interactive library used for final testing may differ from this implementation, so the contestant's solution should not rely on the specific implementation of the interactive library.

You need to use the following compilation command in the problem directory to obtain the executable:

g++ mpc.cpp grader.cpp -o mpc -O2 -std=c++17 -lm

The executable will read data from standard input in the following format:

• The first line contains two integers $n, m$.
• The next $n$ lines each contain $m$ integers ($0$ or $1$), representing the binary representation of each person's integer from least significant to most significant, with each integer separated by a space.

After reading, the interactive library will first call the init(n, m) function to get $N$, then perform $\max(0, N)$ rounds of calls. The $k$-th round ($1 \le k \le \max(0, N)$) will call the transmit function for all round = $k$, and update the corresponding player.last_message after the calls.

• If $N \le 0$, no calls will be made, and all player.memory will remain at their initial values.

If your program runs correctly, the executable will output data in the following format:

• The first line is a string of length $2200$, representing the sum of all $a_i$, output in binary from least significant to most significant.
• The second line is a string outputting the values of the first $2200$ positions in the player.memory of the person numbered $n$ after all interactions, with no spaces between adjacent numbers.
• The third line will inform you if the answer is incorrect if the two strings above differ; otherwise, it will output your score for this test case.

The sample files 1.in, 1.ans, and a sample program mpc.cpp are provided in the problem directory. The sample program can pass the provided sample.

Subtasks

For all test data, $1 \le n, m \le 2000$.

There are 10 subtasks in this problem, each worth 10 points.

Scoring

This problem is subject to the same constraints as traditional problems; for example, compilation errors result in 0 points for the entire problem, while runtime errors, time limit exceeded, or memory limit exceeded result in 0 points for the corresponding test cases.

Beyond the above conditions, for a test case, if $N > n+m+100$, or if the binary number corresponding to the first $2200$ bits of the player.memory of the person numbered $n$ after all transmit calls is not the sum of all $a_i$, you will receive 0 points. Otherwise, your score for that test case is calculated based on the value of $(N - n - m)$ according to the following table:

Your score for a subtask is the minimum score among all test cases in that subtask.