Problem Statement

RectJoin is the following single-player game played with square grid paper and pencil.

Let (0, 0) be the coordinates of the lower left corner of the grid paper, with the x-axis to the right and the y-axis to the top. The coordinates of the upper right corner of the grid paper are (N-1, N-1). Initially, M dots are placed on grid points, and you can repeat the following operations as many times as possible to place dots and draw rectangles on the grid paper.

In the i-th operation, choose a grid point p_{i,1} not containing a dot and three grid points p_{i,2}, p_{i,3}, p_{i,4} containing dots, which satisfy all of the following three conditions.

1. Connecting p_{i,1} p_{i,2} p_{i,3} p_{i,4} in this order forms a rectangle that is parallel to the axis or inclined at 45 degrees.
2. There are no dots other than p_{i,2}, p_{i,3}, p_{i,4} on the perimeter of this rectangle.
3. The perimeter of this rectangle does not share a common segment of positive length with the perimeter of an already drawn rectangle (intersecting at some points is allowed).

For the chosen four points, place a new dot on p_{i,1} and draw the perimeter of the rectangle p_{i,1} p_{i,2} p_{i,3} p_{i,4} on the grid paper.

Let (c,c)=((N-1)/2,(N-1)/2) be the coordinates of the center of the graph paper. We define the weight of each grid point as w(x,y)=(x-c)^2 + (y-c)^2 + 1 using the distance from the center. Let S=\sum_{x=0}^{N-1}\sum_{y=0}^{N-1} w(x,y) be the sum of the weights of all grid points. Let Q be the set of coordinates with dots in the final state (including the initially placed dots). Then you will get the following score.

\[\mathrm{round}\left(10^6 \cdot\frac{N^2}{M}\cdot\frac{\sum_{(x, y)\in Q} w(x, y)}{S}\right)\]

Create a program to play the game to get as high a score as possible.

Additional explanation of the rules

• You must choose p_{i,1} from the interior of the grid paper, i.e., from coordinates satisfying 0\leq x,y\leq N-1.
• Since a dot is placed on the grid point chosen as p_{i,1}, it cannot be chosen again as p_{j,1} in j(>i)-th operation, but it can be chosen again as p_{j,k} (k=2,3,4).
• Similarly, p_{i,k} (k=2,3,4) can be repeatedly chosen as p_{j,k'} (k'=2,3,4) in j(>i)-th operation.
• As stated in condition 2, there must be no other dots on the perimeter of the chosen rectangle, but conversely, you can choose a point on the perimeter of an already drawn rectangle as p_{i,1} and place a dot on it.

Number of test cases

• Provisional test: 50
• System test: 2000. We will publish seeds.txt (sha256=907b41fcba240515612a21798a10b0df7dda744b1268b74b3bbd41b93a73095e) after the contest is over.
• System test contains 125 inputs for each of N=31,33,35,\cdots,61.
• The input of seed=0 is manually created and is not included in the provisional or system test.

The score of a submission is the total scores for each test case. In the provisional test, if your submission produces illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In the system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero. The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.

About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.

Sample Input 1

33 58
13 24
14 24
15 24
16 24
17 24
12 23
18 23
11 22
19 22
10 21
20 21
9 20
21 20
8 19
15 19
18 19
22 19
8 18
12 18
15 18
18 18
22 18
8 17
12 17
15 17
18 17
22 17
8 16
12 16
15 16
18 16
22 16
8 15
12 15
15 15
18 15
22 15
9 14
12 14
15 14
18 14
21 14
10 13
12 13
15 13
18 13
20 13
22 13
11 12
12 12
15 12
18 12
19 12
23 12
12 11
15 11
18 11
24 11

Sample Output 1

20
9 15 12 12 15 15 12 18
15 20 12 17 15 14 18 17
23 22 19 22 19 12 23 12
23 14 22 15 21 14 22 13
10 14 10 13 12 13 12 14
11 11 12 11 12 12 11 12
18 20 15 20 15 19 18 19
19 16 22 19 21 20 18 17
12 19 12 18 15 18 15 19
15 22 12 19 15 16 18 19
14 22 15 22 15 24 14 24
15 8 18 11 15 14 12 11
10 15 9 15 9 14 10 14
11 18 12 19 10 21 9 20
22 23 20 21 21 20 23 22
21 15 18 15 18 14 21 14
15 26 13 24 15 22 17 24
20 20 16 24 14 22 18 18
21 17 18 20 15 17 18 14
11 14 10 13 11 12 12 13