Waldo

The cows are playing their own version of "Where's Waldo?". Specifically, there are $k$ pictures in an album ($k$ is an even number), and many cows are scattered across each picture. There are $n$ cows in total that appear in these pictures. Waldo appears in every picture, while every other cow appears in exactly half of the pictures.

The cows were supposed to identify Waldo in each picture. The problem is that the cows lost the cover of the album, so they cannot recognize which cow is Waldo, and the nature of the game has changed. They decided to check the pictures separately: each cow finds useful information from a picture, and another cow aggregates this information. The cows are very smart, and they hope to minimize the amount of information transmitted while finding Waldo.

Implementation Details

You need to implement two functions, send_picture and find_waldo, with the following signatures:

string send_picture(int n, int k, vector<int> &picture);
int find_waldo(int n, vector<string> &messages);

Where string and vector are the corresponding types from the standard library.

send_picture represents the workflow of the cow checking a picture. $n$ is the total number of cows appearing in all pictures; $k$ is the total number of pictures; picture is the list of cow IDs appearing in the picture assigned to this cow, where each number is guaranteed to be between $0$ and $n-1$ and distinct; You need to return a string consisting only of '0' and '1', representing the information this cow wants to transmit to the aggregating cow.

find_waldo represents the workflow of the aggregating cow. $n$ is the total number of cows appearing in all pictures; messages is a list of strings of length $k$, where each member is a string consisting only of '0' and '1', representing the information transmitted by each cow that checked a picture; * You need to return an integer between $0$ and $n-1$, representing the ID of the identified Waldo.

In a single test case, send_picture will be called $k$ times, letting cows check each picture, and find_waldo will be called once, with its messages parameter being the return values of each send_picture call. It is guaranteed that each number from $0$ to $n-1$ appears exactly $k/2$ times in the picture parameters of send_picture, except for the number representing Waldo's ID, which appears in every picture call. find_waldo needs to return this number.

Local Testing

The provided file waldo_driver.cpp is for local testing. You need to compile it with your answer file to generate an executable for local testing. For example, if your answer file is named waldo.cpp, you can generate the executable waldo via:

g++ waldo_driver.cpp waldo.cpp -o waldo

The input format for the generated executable is as follows: The first line contains an integer, which is a secret code and is irrelevant to the answer. The second line contains two integers $n$ and $k$, representing the total number of cows and the number of pictures. The next $k$ lines each start with an integer $c$ ($1 \le c \le n$), representing the number of cows appearing in this picture. Next are $c$ distinct integers from $0$ to $n-1$, representing the IDs of the cows appearing in this picture. The last line contains an integer, representing the answer, which is Waldo's ID.

The executable will output a real number in $[0, 1]$, representing the score percentage of your program on the test case.

Note: Using global variables or similar means to communicate between cows during online testing will not be effective. However, you can still use global variables normally.

Scoring

Based on a correct functional implementation, if the average length of the transmitted strings (i.e., the number of bits) in a test case is $b$, meaning the total length is $b \cdot k$, where $b$ is a non-negative real number, the score will be the maximum of $(100 - b)\%$ of the test case's total points and $0$. In other words, the score decreases linearly with the average length of the transmitted information until the average length reaches $100$ bits, at which point no points are awarded.

Examples

Input 1

123
5 4
4 0 2 3 4
3 0 1 2
3 1 2 3
2 2 4
2

Output 1

2

Note 1

There are 5 cows appearing in 4 pictures, where cow 2 (Waldo) appears in every picture, and other cows appear in only half (2) of the pictures.

Constraints

$1 \le n \le 10^4$, $2 \le k \le 50$, and $k$ is an even number.

Provided Files

• waldo_driver.cpp is as described above.
• waldo.cpp provides a sample answer. The cow checking the picture returns "1" or "0" based on whether cow 0 appears, and the aggregating cow returns 0 if it determines cow 0 is Waldo based on this information, otherwise it returns 1.