Note: When evaluating on QOJ, to check if you are using global variables, your program may be run in several (up to 4) different processes. Each time, one process will be chosen to call the corresponding WereYouLast, and global variables cannot be shared between different processes. The time limit for this problem (14 seconds) refers to the sum of the time used in all processes, and the memory limit (1024 MB) refers to the maximum memory used in any single process.

Problem Update: In T3, "affected" means that as long as a position is queried or modified, it is considered affected. Recursive calls to WereYouLast are prohibited.

Special Reminder: Due to compilation issues, please add the following declarations before your code:

bool query(int);
void modify(int,bool);

This is an interactive problem.

In this problem, you do not need to implement the main function. You need to implement the function:

bool WereYouLast(int n,int m)

This function will be called exactly $n$ times, and you need to correctly return whether it is the last call.

The interactive library provides $m$ global bool storage units, numbered $1, 2, \dots, m$, which are initialized to False. Your program can call the following functions:

• bool query(int pos): This function returns the value of the pos-th storage unit.
• void modify(int pos,bool v): This function modifies the value of the pos-th storage unit to v.

Let $cnt_i$ be the number of distinct positions affected by your program's query/modify operations during the $i$-th call. You need to minimize:

$C_1 = \max\limits_{i=1}^n cnt_i$. In some test cases, minimizing $C_2 = \max\limits_{i=2}^n cnt_i$ can also earn partial points.

Note: Your program must not exchange information between multiple calls in any custom form. These prohibited forms include, but are not limited to, using global variables (global variables used as constants are allowed, i.e., you do not modify them to pass information) or variables containing the static keyword. Any form of attacking the interactive library is prohibited. These prohibited forms include, but are not limited to, modifying global variables in the interactive library or using a main function in your code. Programs that score points may be manually inspected. Participants may appeal against programs that perform prohibited actions; if the behavior is confirmed, the corresponding program's score for this problem will be canceled.

Note: To prevent excessive judging load, in a single call to WereYouLast, you cannot perform more than 5 query operations or more than 5 modify operations on the same position. If your program calls query or modify more than 5 times on a single position in one WereYouLast call, the operations exceeding the limit will be judged as an Invalid Operation, and your program will be judged as Wrong Answer.

Input

The executable reads data from standard input.

The input contains one line with two integers $n$ and $m$, representing the number of calls and the number of global storage units.

How to Test Your Program

The provided files include a reference program sample.cpp.

For the provided interactive library grader.cpp, assuming your code is named code.cpp, you can compile it using the following command:

g++ code.cpp -o code grader.cpp -O2 -std=c++11

You cannot gain points by modifying the interactive library.

You can assume that the running time of the final test interactive library will be within 0.1s of the sample interactive library, and the memory limit will be within 5MB.

Scoring

Each test case has a fixed $n$, $m$, and several scoring parameters $a_1, a_2, \dots, a_{10}$.

If your program does not complete the task correctly, you will receive 0 points.

After completing the task:

In test case 1, you receive 1 point for every $C_1 \leq$ a scoring parameter.

In test case 2, you receive 1 point for every $C_1 \leq$ a scoring parameter, and 1 point for every $C_2 \leq$ a scoring parameter.

In test case 3, you receive 2 points for every $C_1 \leq$ a scoring parameter, and 1 point for every $C_2 \leq$ a scoring parameter.

In test case 4, you receive 2 points for every $C_1 \leq$ a scoring parameter, and 2 points for every $C_2 \leq$ a scoring parameter.