twins

Once again, the twins Reni and Nora managed to fool everybody by switching places. Alex was convinced that he had figured out a strategy for telling them apart. But it turns out he was wrong. Reni and Nora, knowing that he is hopelessly confused, decide to try one of their newly invented games. It consisted of the following:

They choose $N$ different pictures of themselves, numbered from $1$ to $N$, one or two of which are of Reni and the rest are of Nora. Alex is allowed to ask questions like: "Among the pictures with numbers $p_1,\ p_2,\ ...\ p_K\ (1 \leq K \leq N)$, is there at least one picture of Reni?". However, to make it more interesting, he can submit a whole group with several such questions and receive the answers to each of them at the same time.

The purpose of the game for Alex is to guess which pictures are of Reni and which are of Nora after some finite number of questions (which in itself would be an achievement for him), but also to minimize both the number of question groups and the total number of questions in them. He needs your help for this. Write a program that finds the required one or two pictures.

Task

Write a program that determines which of the pictures are of Reni and which are of Nora. It must contain the function play that will be compiled with the jury's program.

Implementation details

Your function play must have the following format:

std::vector<int> play (int N, int T);

It will be called only once during one execution of the program with two parameters: the number of pictures $N$ and the number of Reni's pictures - $T\ ( T\in \{1,2\} )$. The function should return the indices of the one or two Reni's pictures. Their order does not matter.

For communication with the jury's program you should use the following function:

std::string guess (std::vector< std::vector<int> >& questions);

As a parameter, it receives a group of questions, each containing a set of picture numbers. For example, if Alex wants to ask $2$ questions and the first one is about the pictures $1$ and $2$, and the second one is about the pictures $2$ and $3$, it should be given $\{\ \{1,2\},\ \{2,3\}\ \}$. It is allowed to have "empty"{} questions that ask nothing (passing $\{ \{\ \},\ \{2,3\}\ \}$ as a parameter). They will not count towards the total number of questions used.

The function returns a string composed of $0$ and $1$, indicating "no" and "yes" answers to the questions, respectively. Suppose you asked $M$ questions in a group. They are numbered with the numbers $0$ through $M-1$ in the order in which you submitted them, and correspond to the indices of answers in the string.

You must submit to the system a file twins.cpp that contains the function play. It can also contain other code, functions, and global variables, but it must not contain the main function. Also, you should not read from the standard input or print to the standard output. Your program must include the header file twins.h by instruction to the preprocessor:

#include "twins.h"

Scoring

Each test receives a score that is a fractional number between 0 and 1 inclusive. If a test has a positive score, it is considered a successful test for your solution. Because Nora and Reni encourage even suboptimal games, they use the following scoring system.

Let $C$ be the number of calls to the function guess. The evaluation with respect to $C$ for all tests is as follows:

Let $L$ be the total number of questions you used across all calls to the guess function.

Scoring when $T=1$

When $T=1$ there are two types of tests. In the first $N\in [15,30]$ (the first table), and in the second $N=50\ 000$ (the second table). The evaluation with respect to $L$ in tests when $T=1$ is as follows:

Scoring when $T=2$

When $T=2$ in all tests $N=50\ 000$. The evaluation with respect to $L$ in tests when $T=2$ is as follows:

If you make an invalid action or do not guess the pictures correctly, you will get score $0$ for the test. Otherwise, the score is equal to $P_C \times P_L$. For example, on a test with $T=2$, if $L = 2000$ and $P = 3$, your score will be $45\% \times 60\% = 0.27$.

Input data

The first line will contain two numbers, $a$ and $b$.

Output data

The first line will contain a single number, representing the sum of the two numbers.

Constraints and clarifications

• $15 \leq N \leq 50\ 000$
• $1 \leq T \leq 2$

Examples

Explanation

Let's look at the first example. After the first two questions which are asked at once, we know that the requested picture is among the first $3$. Similarly, with the last $3$ questions, we find out exactly which one it is.

Local Testing

The file Lgrader.cpp is provided for local testing. Put your twins.cpp file together with Lgrader.cpp and twins.h into one folder and compile the three files together. This will give you a program to check the correctness of your function. The program will require two numbers on the first line $- \ N$ and $T$. On the next line the program requires the numbers of the pictures that are of Reni. The program will display in detail the steps when performing this test. To change this, you can change the value of the DETAILS constant at the beginning of the code. You can modify this file as you wish.