There is a farm that may be treated as two-dimensional Euclidean plane. There are ~n~ trees numbered ~1, 2, \dots, n~. Each tree may be treated as a point on the plane, and the ~i~-th tree has coordinates ~(x_i,y_i)~. The coordinates of trees are pairwise distinct.

Mr. P will drive from the origin ~(0,0)~. In one round, Mr. P will choose a direction from left, right, up, 45 degrees upper left, and 45 degrees upper right such that if driving in the selected direction Mr. P can arrive at a tree he has never visited. Mr. P will drive straight along the selected direction and will arrive at the nearest unvisited tree in that direction. If there is no available direction, Mr. P will stop. Mr. P will follow the optimal route in the sense Mr. P will visit the most trees possible. If the optimal route is not unique, Mr. P may choose any one of them.

Unfortunately, Mr. S found that Mr. P's car will leave a rut on the farm. A rut may be treated as a line segment between two trees or between the origin and a tree.

There are a lot of visitors to the farm besides Mr. P, and they will choose an optimal route when visiting the trees. Mr. S believes ruts in directions other than left and right (i.e. up, 45 degrees upper left, or 45 degrees upper right) are not beautiful. Therefore, he will rent some road rollers to reinforce areas that might have ruts not in the left or right direction. More formally, the area that might have ruts not in the left or right direction are segments on the farm such that each segment is contained in some optimal route. The road rollers work as follows:

• The road roller starts from the origin or any tree.

• The road roller may move upwards, 45 degrees upper left, or 45 degrees upper right. The road roller may only stop or change direction under a tree.

• The road roller may only pass through areas that may have ruts not in the left or right direction, but a given area may be passed by multiple road rollers.

Mr. P and Mr. S asks the following question: (1) find an optimal route for Mr. P (2) tell Mr. S the minimum number of road rollers required.

Input Specification

The first line of the input contains an integer ~n~ denoting the number of trees. In the following ~n~ lines, the ~(i+1)~-th line has two integers ~x_i, y_i~ separated by a single space denoting the coordinate of ~i~-th tree.

Output Specification

The output contains 3 lines. The first line is an input ~m~ denoting the maximum number of trees Mr. P may visit. The second line contains ~m~ integers separated by a single space denoting the trees Mr. P shall visit. The third line contains a single integer denoting the minimum number of road rollers required.

Sample Input 1

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

Sample Output 1

3
2 1 3
3

Explanation for Sample Output 1

There are two optimal routes that visit 3 trees: ~(0,0) \to (1,1) \to (-1,1) \to (-2,2)~ or ~(0,0) \to (0,8) \to (0,9) \to (0,10)~. Three road rollers are required. The routes of the road rollers are ~(0,0) \to (1,1)~, ~(-1, 1) \to (-2,2)~, and ~(0,0) \to (0,8) \to (0,9) \to (0,10)~ respectively.

Sample Input 2

4
0 1
-2 1
2 1
3 2

Sample Output 2

4
1 2 3 4
2

Explanation for Sample Output 2

The optimal route is unique: ~(0,0) \to (0,1) \to (-2,1) \to (2,1) \to (3,2)~. It is possible to visit four trees. After visiting ~(0,1)~, since the closest unvisited tree after departing from ~(-2,1)~ and moving right is ~(2,1)~, we may reach ~(2,1)~. But if we move along the route ~(0,0) \to (0,1) \to (2,1) \to (-2,1)~, since all trees to the right of ~(-2,1)~ have been visited, we will stop.

Since moving along ~(0,0) \to (0,1)~ and ~(2,1) \to (3,2)~ will leave ruts that are not in the left or right direction, we need two road rollers.

Constraints

Test Case	~n~	~x_i, y_i~	Additional Constraints
1	~n=5~	~|x_i| \le 100~ ~0 < y_i \le 100~
2	~n=10~
3	~n=100~	~|x_i| \le 10\,000~ ~0 < y_i \le 10\,000~
4	~n=1000~
5	~n=5000~	~|x_i| \le 1\,000\,000~ ~0 < y_i \le 1\,000\,000~	The optimal route is unique.
6
7	~n=50\,000~
8	~n=5000~	~|x_i| \le 1\,000\,000~ ~0 < y_i \le 1\,000\,000~	All ~y_i~ are unique.
9	~n=50\,000~
10
11	~n=5000~	~|x_i| \le 1\,000\,000~ ~0 < y_i \le 1\,000\,000~	For any integer ~Y~, at most ~1000~ trees satisfy ~y_i = Y~. Additionally, there exists an optimal solution such that the road rollers won't pass through the same place twice.
12
13	~n=50\,000~
14
15	~n=10\,000~	~|x_i| \le 1\,000\,000\,000~ ~0 < y_i \le 1\,000\,000\,000~	For any integer ~Y~, at most ~1000~ trees satisfy ~y_i = Y~.
16
17	~n=30\,000~
18
19	~n=50\,000~
20

Scoring

For each test case:

• If the first line of the output is correct, ~20\%~ of points will be awarded;
• If the first two lines are correct, ~40\%~ of points will be awarded;
• If the output is completely correct, ~100\%~ of points will be awarded.