Problem Description

Mr. S, the gardener, is in charge of a field that can be considered as a two-dimensional plane. There are $n$ wishing trees in the field, numbered $1, 2, 3, \dots, n$. Each tree can be represented as a point on the plane, where the $i$-th tree ($1 \leq i \leq n$) is located at coordinates $(x_i, y_i)$. No two trees share the same coordinates.

Mr. P, the old driver, starts his journey from the origin $(0,0)$ and conducts several rounds of actions. In each round, Mr. P first selects any direction that meets the following conditions:

1. It is one of the five directions: left, right, up, upper left $45\degree$, or upper right $45\degree$.
2. Moving in this direction will reach a tree he has not yet wished at.

After making the selection, Mr. P moves straight in that direction to the nearest tree he has not wished at, makes a wish under the tree, and continues to the next round. If there are no valid directions to choose from, he stops his actions. He will adopt the optimal strategy to make wishes under as many trees as possible. If the optimal strategy is not unique, he can choose any one.

Unfortunately, Mr. S discovers that due to the soft soil in the field, Mr. P's car leaves a track on the field during each round of travel. A track can be considered as a line segment with two trees (or the origin and a tree) as its endpoints.

After Mr. P, many wish-makers plan to drive to the field to make wishes, and they will all follow an optimal strategy like Mr. P. Mr. S thinks that tracks in directions other than left and right (i.e., up, upper left $45\degree$, and upper right $45\degree$) are unsightly. To maintain the appearance of the field, he plans to rent some rollers to compact all the ground that "may leave tracks in non-left-right directions" before these wish-makers arrive. The ground that "may leave tracks in non-left-right directions" should be several line segments, each of which is included in some optimal strategy's travel route. Each roller operates under the following three conditions:

1. Starts from the origin or any tree.
2. Can only move in one of the three directions: up, upper left $45\degree$, or upper right $45\degree$, and can only change direction or stop at a tree.
3. Can only pass through the ground that "may leave tracks in non-left-right directions," but the same ground can be passed by multiple rollers.

Now, Mr. P and Mr. S each ask you a question:

1. Please indicate an optimal route for Mr. P.
2. Please tell Mr. S the minimum number of rollers needed.

Input Format

The first line contains one positive integer $n$, representing the number of wishing trees.

The next $n$ lines, the $(i+1)$-th line contains two integers $x_i, y_i$, separated by a single space, representing the coordinates of the $i$-th wishing tree.

Output Format

Include three lines.

The first line outputs one integer $m$, representing the maximum number of trees Mr. P can make wishes under.

The second line outputs $m$ integers, separated by a single space, indicating the sequence of trees Mr. P should make wishes under.

The third line outputs one integer, representing the minimum number of rollers Mr. S needs to rent.

Sample Input and Output

Input Sample #1

6
-1 1
1 1
-2 2
0 8
0 9
0 10

Output Sample #1

3
2 1 3
3

Input Sample #2

4
0 1
-2 1
2 1
3 2

Output Sample #2

4
1 2 3 4
2

Notes

Sample 1 Explanation

There are two optimal routes, each allowing three wishes: $(0,0) \rightarrow (1,1) \rightarrow (-1,1) \rightarrow (-2,2)$ or $(0,0) \rightarrow (0,8) \rightarrow (0,9) \rightarrow (0,10)$.

At least three rollers are needed, with routes being $(0,0) \rightarrow (1,1)$, $(-1,1) \rightarrow (-2,2)$, and $(0,0) \rightarrow (0,8) \rightarrow (0,9) \rightarrow (0,10)$.

Sample 2 Explanation

The only optimal route is $(0,0) \rightarrow (0,1) \rightarrow (-2,1) \rightarrow (2,1) \rightarrow (3,2)$, allowing four wishes. After wishing at $(0,1)$, the nearest unwished tree to the right of $(-2,1)$ is $(2,1)$, so it can reach $(2,1)$.

If moving in the direction of $(0,0) \rightarrow (0,1) \rightarrow (2,1) \rightarrow (-2,1)$, all trees to the right of $(-2,1)$ are wished at, and it stops according to the rules. Thus, it cannot achieve the optimal solution.

Tracks from $(0,0) \rightarrow (0,1)$ and $(2,1) \rightarrow (3,2)$ are in non-left-right directions, requiring two rollers.

见题面 Input 部分

见题面 Output 部分