Out of 100,100 cows numbered 1 to 100,100, 100 cows have disappeared. The remaining cows are split equally between Alice and Bob, with each receiving 50,000 cows. Alice can send 100 bits to Bob. Bob needs to identify the number of any one of the missing cows based on the information provided by Alice.

Implementation Details

You need to implement two functions, farm1 and farm2, with the following signatures:

void farm1(char *msg, int *cows);
int farm2(char *msg, int *cows);

farm1 represents Alice's operation: cows points to an int array of length 50,000, from which you can read the numbers of the cows Alice received. msg points to a char array of length 100. You must fill each position with either '0' or '1', representing the 100 bits Alice sends to Bob.

farm2 represents Bob's operation: cows is similar to the parameter in farm1, also pointing to an int array of length 50,000, from which you can read the numbers of the cows Bob received. msg points to a char array of length 100, where each character is '0' or '1', representing the 100 bits sent by Alice to Bob. * The function should return an int representing the number of a missing cow found by Bob.

Local Testing

The provided file missing_driver.cpp is for local testing. You need to compile it together with your answer file to generate an executable for local testing. For example, if your answer file is named missing.cpp, you can use:

g++ missing_driver.cpp missing.cpp -o missing

The generated executable missing will read 100,000 distinct numbers from 1 to 100,100 from standard input. The first 50,000 numbers are the cow IDs received by Alice, and the next 50,000 are the cow IDs received by Bob. It will call your farm1 and farm2 functions and output the corresponding information. Specifically, if it outputs OK, the local test is passed.

Note: During online testing, using global variables or similar means to secretly communicate between Alice and Bob will not be effective. However, you can still use global variables normally.

Examples

A simplified example is given below, where there are 10 cows initially, 2 have disappeared, and Alice and Bob each receive 4 of the remaining 8 cows. You can change the constants N to 10, and N1 and N2 to 4 in missing_driver.cpp to use this example.

Input

1
3
5
7
2
4
6
8

Note

In this case, Alice receives cows 1, 3, 5, and 7, while Bob receives 2, 4, 6, and 8. The remaining cows 9 and 10 have disappeared. During program execution:

1. farm1 will be called once. The parameter msg is a buffer to be filled, and cows points to an int array of length 4 with the content [1, 3, 5, 7].
2. If farm1 executes correctly, farm2 will also be called once. The parameter msg is the bit string written by farm1 previously, and cows points to an int array of length 4 with the content [2, 4, 6, 8]. If farm2 returns 9 or 10, this example is passed.

Provided Files

• missing_driver.cpp: As described above.
• missing.cpp: Provides a sample answer where Alice outputs 100 '0's or '1's based on whether she received cow 1, and Bob outputs 1 if he determines cow 1 is missing based on this information, otherwise he outputs 2.