This is an interactive problem.

Xiao Q likes to play a game called "Spot the Difference" when he is bored.

The rules of the game are as follows: In each round, the system displays a pair of images to the player. There are only a few differences between these two images, and the player needs to find as many differences as possible within a specified time. If the player finds all the differences before the time runs out, the round is considered a "challenge success"; otherwise, the game ends when the time runs out, and the round is a "challenge failure".

Recently, the game introduced a new mode: Survival Mode. In Survival Mode, the system prepares $m$ sets of images and displays them to the player one by one. When the system displays a set of images, the player needs to "spot the differences". In this mode, the game provides a "Next Image" button: the player does not need to find all the differences in the current set of images before clicking this button to process the next image. In fact, if the player does not click the "Next Image" button, the system will not automatically switch to the next image even if the player has already found all the differences in the current one. Note that once the "Next Image" button is clicked, it is impossible to return to process the current image. When the allotted time runs out, the system automatically ends the game. In this mode, the game result changes from a simple success/failure to a score: the player's score in a round is defined as the number of differences correctly identified by the player within the allotted time; incorrect reports or missed differences do not result in point deductions.

With a new mode launched, the first thing to do is, naturally, to farm points. As a computer engineering geek, Xiao Q is not naive enough to farm points manually. After analyzing the game program using technical means, Xiao Q discovered that the game uses the following strategy when generating images for the player: first, it prepares two large images and records the positions of all $n$ differences between them; every time a set of images needs to be generated, it takes a corresponding rectangular region from these two large images.

Specifically, these two large images are divided into $U \times U$ small blocks, each with coordinates $(x, y)$, where $0 \leq x, y < U$. Among these blocks, $n$ blocks are differences, and the rest are not. Every time a set of images needs to be generated, the system generates two coordinates $(x_1, y_1)$ and $(x_2, y_2)$ where $x_1 \leq x_2, y_1 \leq y_2$, and uses the rectangular region $(x_1, y_1)-(x_2, y_2)$ as the result of this generation.

The resourceful Xiao Q soon obtained the coordinates of all $n$ differences and found a way to intercept the coordinate information $(x_1, y_1), (x_2, y_2)$ for each set of images. The rest is simple: just find those points among the $n$ differences that lie within the rectangle $(x_1, y_1)-(x_2, y_2)$. Kind-hearted Xiao Q has entrusted this simple task to you so that you can share the joy of farming points.

Interaction

You need to implement spots.cpp. At the beginning of this file, you should use #include "spots.h" to include the header file spots.h. Next, you need to implement the two functions spots_init and spots. Details are as follows:

void spots_init(std::vector< std::pair<int, int> > points); Before Xiao Q wants to start a game, he will call this function. The parameter points is a vector containing the coordinates of all differences. You should initialize the data you need within this function.

void spots(int x1, int y1, int x2, int y2); When the system gives Xiao Q a new set of images $(x_1, y_1)-(x_2, y_2)$, Xiao Q will call this function. The four parameters have the meanings described above. In this function, you need to find as many differences within this rectangular region as possible. You can call the following function to report the differences you have found:

bool report(int x); The parameter x represents the index of the difference you found. The index of a point is equal to its index in the vector passed to spots_init. If this function returns true, it means the difference is correct; otherwise, it means the difference is incorrect. When you have finished processing this set of images, you should return from the spots function.

It should be noted that you are not allowed to read any information from standard input or any files, nor are you allowed to output any information to standard output or any files.

The file spots_sample.cpp in the contestant directory provides an example of spots.cpp.

Constraints

There are 10 test cases in this problem. The scale of each test case is as follows:

The "Sum of Points" column represents the total number of points in all queried regions.

For each test case, we will score it as follows:

First, we will call your spots_init function. You will have 1 second to complete the initialization. If your spots_init function does not return within 1 second, the test case will receive 0 points.

After that, you have 1 second to process the queries. We will continuously call your spots function within this 1 second until the time runs out. If we find that the time has run out during a report call, we will calculate the score immediately and terminate the program. Note that calls to the report function during this process are also counted towards the time, but you can assume that the report function is fast enough to execute at least $10^8$ times within 1 second.

Please ensure that each call to your spots function returns within 1 second; otherwise, the test case may be judged as 0 points.

If your program uses more than $512\texttt{MB}$ of memory at any point, the test case will receive 0 points. (Note that the interaction library also consumes memory; you can assume it uses no more than $64\texttt{MB}$.)

If your program does not trigger any of the above conditions for 0 points, we will score your program according to the following rules: Let $\mathrm{UserCnt}$ be the number of results correctly reported by your program within 1 second, and $\mathrm{StdCnt}$ be the number of results correctly reported by our reference program within 1 second. If $\mathrm{UserCnt} \geq \mathrm{StdCnt}$, the test case receives 10 points; otherwise, the score for the test case is:

\begin{equation} 10 \cdot \sqrt{\frac{\mathrm{UserCnt}}{\mathrm{StdCnt}}} \end{equation}

In addition to the above limits, there is a total time limit of 20 seconds, but this limit is only set to ensure that the program can terminate; contestants do not need to worry about it.

Examples

A sample grader program grader.cpp is provided in the contestant directory.

This program reads point and query information from standard input and interacts with your program. The specific format for reading information is described below. When the program finishes running, it will print the result to standard output.

To use this sample grader, you need to compile it together with your spots.cpp. The reference command line is:

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

It should be noted that the sample grader does not provide the functionality to test execution time.

Evaluation Method for the Sample Grader

The first line contains two integers $n, m$.

The next $n$ lines each contain two integers $x, y$, describing the coordinates of a difference.

The next $m$ lines each contain four integers $x_1, y_1, x_2, y_2$, describing a query.

Example:

5 3
1 1
2 2
3 3
4 4
5 5
0 0 1 3
2 2 3 3
10 10 11 12