You've just been hired to be a quality assurance (QA) tester for Software Company Inc. to help test their new circle drawing algorithm. Thankfully, other QA testers at the company have already written the code that reads the display and produces an easier to process output which you have decided you will use to feed your program. The input to your program will provide you with the radius of the circle, ~R~, and the coordinates of each pixel the circle drawing algorithm fills in with the circle centered at ~(0, 0)~. In addition to this the developers have left the following documentation on which pixels should be filled in:

1. Start at the rightmost point of the circle.
2. Fill in an adjacent pixel whose distance from the center of the circle is closest to the radius (ties are broken by choosing the pixel that is clockwise).
3. Repeat step 2 on the newly filled in circle until a cycle is achieved.

Can you write a program to tell the developers which pixels they've incorrectly filled in?

Input Specification

The first line contains a single integer ~R~, ~(1 \le R \le 1000)~, the radius of the circle.

The second line contains a single integer ~Q~, ~(1 \le Q \le 10^{4})~, the number of pixels filled in.

The next ~Q~ lines will each contain a pair of space separated integers ~x_i~, ~y_i~, ~(-10^{4} \le x_i, y_i \le 10^{4})~, the coordinates of a pixel that was filled in.

Output Specification

A single line containing a space separated list of the incorrectly filled in pixel ~i~ values (the first query has ~i=0~).

Sample Input

10
5
0 0
10 0
-10 0
7 8
-6 -8

Sample Output

0 3

Sample Explanation

See the image below of the circle with radius ~10~ and with the ~i~ values of each query plotted in red: