Problem Update: It is forbidden to define any variables or functions outside the two defined namespaces, Alice and Bob.

Alice and Bob are playing a game with Eve. Eve has a multiset of non-negative integers $S$, where all numbers are less than $M=2^{21}$. She divides this set into two parts, $A$ and $B$, and gives them to Alice and Bob, respectively. For the convenience of information transmission, she guarantees that each number appears at most once in each part. She gives Alice and Bob a task: find the $c$-th smallest number in $S$. However, this is too simple, so Eve requires them to transmit as few bits of information as possible.

Implementation Details

This problem only supports C++ 11 or higher.

You must include the statement #include "nth.h" at the beginning of your file.

Within the namespace Alice, you need to implement:

void initA(std::bitset<M> A, unsigned S, unsigned c), where $A$ describes the set given to Alice: the $i$-th bit is $1$ if and only if $i$ is in the set; $S$ is the size of Eve's multiset (if a number appears multiple times, each occurrence contributes to this value); the meaning of $c$ is as described in the problem statement.

void receiveA(bool x), which indicates that Alice has received 1 bit of information from Bob: the value of the information is $x$.

You may call: void sendA(bool x) to send the information $x$ to Bob.

Similarly, within the namespace Bob, you need to implement initB and receiveB, and you may call sendB.

In both namespaces, you may call the function void report(unsigned ans), which indicates that either Alice or Bob is reporting the answer to Eve.

Note:

• You do not need to and should not define or declare a main function.
• You may define global variables within the namespaces, but any communication between the two namespaces via variables, addresses, etc., will be considered cheating.
• It is forbidden to define any variables or functions outside the two defined namespaces, Alice and Bob.

Testing Program

In the testing program, for each test case: initA and initB will each be called once in an arbitrary order. The program maintains two queues representing messages sent from one person to the other that have not yet been received; calling send only stores the information in the corresponding queue. The testing program will continuously select an arbitrary non-empty queue, retrieve the message at the front, and call the corresponding receive function. When report is called, it will check the answer and terminate the program.

You can obtain an executable file by compiling your program together with sample_grader.cpp.

The program reads two lines of $0/1$ strings of length $M$ and one integer from standard input.

• The $(i+1)$-th character of the first line is $1$ if and only if $i$ is in the set received by Alice.
• The $(i+1)$-th character of the second line is $1$ if and only if $i$ is in the set received by Bob.
• The third line represents $c$.

The program writes one line containing three numbers to standard output, representing the expected answer, the actual answer, and the amount of information transmitted in bits (i.e., the total number of times sendA and sendB were called).

How to test interactive problems locally

Examples

Input 1

0111000110...
0010101000...
4

Where ... represents $M-10$ zeros (the full sample is included in the package).

In this case, Alice's set is $\{1,2,3,7,8\}$, Bob's set is $\{2,4,6\}$, and Eve's set is $\{1,2,2,3,4,6,7,8\}$, where the $4$-th smallest number is $3$.

Constraints and Scoring

$1 \le c \le S$.

If an incorrect answer is returned for any test case, you will receive 0 points for this problem.

If the correct answer is returned for all test cases:

• For each $L=2^i, i \in \{11, 13, 15, 17, 19, 21\}$, if the total number of bits transmitted across all test cases does not exceed $L$, you receive 3 points.
• For each $L=100i, i \in \{2, 3, 4, 5, 6, 7, 8, 9, 10\}$, if the total number of bits transmitted across all test cases does not exceed $L$, you receive 3 points.
• For each $L=10i, i \in \{9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19\}$, if the total number of bits transmitted across all test cases does not exceed $L$, you receive 5 points.

It is guaranteed that the interaction library will run within 50ms and use no more than 6MB of memory when processing up to $2097152$ communications.

Note

Although QOJ supports the evaluation of communication-style problems, no modifications have been made here to preserve the original implementation method. Please do not attack the interaction library.