The gardener, Mr. S, is in charge of a field, which can be viewed as a two-dimensional plane. There are $n$ wishing trees in the field, numbered $1, 2, 3, \dots, n$. Each tree can be considered a point on the plane, where the $i$-th tree ($1 \le i \le n$) is located at coordinates $(x_i, y_i)$. The coordinates of any two trees are distinct.
The experienced driver, Mr. P, starts driving from the origin $(0,0)$ and performs several rounds of movement. In each round, Mr. P first chooses any direction that satisfies the following conditions: 1. The direction is one of the five: left, right, up, up-left 45°, or up-right 45°. 2. Moving in this direction leads to a tree that he has not yet made a wish at.
After making the choice, Mr. P moves in a straight line in that direction, must reach the nearest tree in that direction that he has not yet made a wish at, makes a wish under that tree, and continues to the next round. If there is no direction that satisfies the conditions, he stops. He will adopt an optimal strategy to make wishes at as many trees as possible. If the optimal strategy is not unique, he may choose any one of them.
Unfortunately, the gardener, Mr. S, discovered that because the soil in the field is soft, Mr. P's car leaves a rut on the field during each round of movement. A rut can be viewed as a line segment with two trees (or the origin and a tree) as its endpoints.
After Mr. P, many other wishers plan to drive to the field to make wishes, and these wishers will all choose an optimal strategy like Mr. P. Mr. S believes that ruts in non-horizontal directions (i.e., up, up-left 45°, and up-right 45°) are unsightly. To maintain the image of the field, he intends to rent some road rollers to compact all the ground that "could potentially leave a non-horizontal rut" before these wishers arrive. The ground that "could potentially leave a non-horizontal rut" consists of several line segments in the field, where each segment is contained in some optimal strategy's path. Each road roller operates according to the following three conditions: 1. It starts from the origin or any tree. 2. It can only move in one of the three directions: up, up-left 45°, or up-right 45°, and can only change direction or stop under a tree. 3. It can only pass over ground that "could potentially leave a non-horizontal rut," but the same piece of ground can be passed over by multiple road rollers.
Now, Mr. P and Mr. S have each asked you a question: 1. Please point out any one optimal route for Mr. P. 2. Please tell Mr. S the minimum number of road rollers he needs to rent.
Input
The first line of the input contains a single positive integer $n$, representing the number of wishing trees. The next $n$ lines each contain two integers $x_i, y_i$, separated by a single space, representing the coordinates of the $i$-th wishing tree.
Output
The output includes 3 lines. The first line outputs a single integer $m$, representing the maximum number of trees Mr. P can make a wish at. The second line outputs $m$ integers, separated by single spaces, representing the trees Mr. P should make a wish at in order. The third line outputs a single integer, representing the minimum number of road rollers Mr. S needs to rent.
Examples
Input 1
6 -1 1 1 1 -2 2 0 8 0 9 0 10
Output 1
3 2 1 3 3
Note 1
There are 2 optimal routes that allow for 3 wishes: $(0,0) \to (1,1) \to (-1,1) \to (-2,2)$ or $(0,0) \to (0,8) \to (0,9) \to (0,10)$. At least 3 road rollers are needed; the routes are $(0,0) \to (1,1)$, $(-1,1) \to (-2,2)$, and $(0,0) \to (0,8) \to (0,9) \to (0,10)$.
Input 2
4 0 1 -2 1 2 1 3 2
Output 2
4 1 2 3 4 2
Note 2
There is a unique optimal route: $(0,0) \to (0,1) \to (-2,1) \to (2,1) \to (3,2)$, allowing for 4 wishes. After making a wish at $(0,1)$, the nearest unvisited tree reachable from $(-2,1)$ by moving right is $(2,1)$, so it is possible to reach $(2,1)$. If one moves in the direction $(0,0) \to (0,1) \to (2,1) \to (-2,1)$, at this point all trees to the right of $(-2,1)$ have already been visited, so according to the problem conditions, movement stops. Thus, the optimal solution cannot be achieved. $(0,0) \to (0,1)$ and $(2,1) \to (3,2)$ will leave non-horizontal ruts, requiring 2 road rollers.
Input 3
See farm/farm.in and farm/farm.ans in the contestant's directory.
Constraints
The range and characteristics of all test data are shown in the table below:
| Test Case ID | $n$ Scale | $x_i, y_i$ Scale | Note | ||
|---|---|---|---|---|---|
| 1 | $n = 5$ | $ | x_i | \le 100$ | |
| 2 | $n = 10$ | $0 < y_i \le 100$ | |||
| 3 | $n = 100$ | $ | x_i | \le 10,000$ | |
| 4 | $n = 1,000$ | $0 < y_i \le 10,000$ | |||
| 5 | $n = 5,000$ | $ | x_i | \le 1,000,000$ | Guaranteed unique optimal route |
| 6 | $n = 50,000$ | $0 < y_i \le 1,000,000$ | |||
| 7 | $n = 5,000$ | $ | x_i | \le 1,000,000$ | |
| 8 | $n = 5,000$ | $ | x_i | \le 1,000,000$ | Guaranteed $y_i$ are distinct |
| 9 | $n = 50,000$ | $0 < y_i \le 1,000,000$ | |||
| 10 | $n = 50,000$ | $0 < y_i \le 1,000,000$ | |||
| 11 | $n = 5,000$ | $ | x_i | \le 1,000,000$ | Guaranteed that for any integer $Y$, there are at most 1,000 trees with $y_i = Y$. There exists an optimal solution such that road rollers do not pass over the same ground repeatedly |
| 12 | $n = 5,000$ | $ | x_i | \le 1,000,000$ | |
| 13 | $n = 50,000$ | $0 < y_i \le 1,000,000$ | |||
| 14 | $n = 50,000$ | $0 < y_i \le 1,000,000$ | |||
| 15 | $n = 10,000$ | $ | x_i | \le 1,000,000,000$ | Guaranteed that for any integer $Y$, there are at most 1,000 trees with $y_i = Y$ |
| 16 | $n = 10,000$ | $ | x_i | \le 1,000,000,000$ | |
| 17 | $n = 30,000$ | $0 < y_i \le 1,000,000,000$ | |||
| 18 | $n = 30,000$ | $0 < y_i \le 1,000,000,000$ | |||
| 19 | $n = 50,000$ | $0 < y_i \le 1,000,000,000$ | |||
| 20 | $n = 50,000$ | $0 < y_i \le 1,000,000,000$ |
Scoring
For each test case: If the first line of the output file is correct, you receive 20% of the points for that test case; If the first two lines of the output file are correct, you receive 40% of the points for that test case; If the output file is completely correct, you receive 100% of the points for that test case.