Organizing a competition in informatics is a difficult task, especially because it involves the effort of a lot of people. The Junior Balkan Olympiad in Informatics is no exception, with a lot of committees being involved in the planning and execution of the competition.

The two strangest committees of JBOI 2015 are the Scientific Committee and the Technical Committee. Because they are responsible for a lot of things, the people in those committees are fighting all the time over how things should be handled, which committee deserves to go to the beach, which committee should get the best food, etc.

Today, the organizers of the Olympiad will receive N packages of drinks (N is always an even number), and these packages should be equally distributed between the two committees: N/2 packages should be given to the Scientific Committee and N/2 packages should be given to the Technical Committee. But, the packages contain different kinds of drinks, and one of the committees may like some of the packages more than they like something else. For each package, we know the happiness value of the Scientific Committee for that package, and the happiness value of the Technical Committee for that package. As an example, let's say that we have 4 packages, and the values in the table indicate the happiness values of each of the committees for the respective packages.

The total happiness of a committee is equal to the sum of the happiness values of all the packages that they will receive. Can you help the organizers of JBOI 2015, and split the N packages between the two committees so that the difference between the total happiness of the first committee and the total happiness of the second committee is minimized? In other words, you should try to split the N packages between the committees, such that each committee receives N/2 of the packages, and their total happiness is as equal as possible.

In the above example, if we decide to give the first and the second package to the Scientific Committee, its total happiness will be equal to 10 + 10 = 20, and the third and the fourth package will be for the Technical Committee, so its total happiness will be equal to 10 + 5 = 15. The difference between the total happiness of the two committees will be equal to |20 - 15| = 5.

On the other hand, if we give the first and the third package to the Scientific Committee (10 + 25 = 35), and the second and the fourth package to the Technical Committee (30 + 5 = 35), the difference will be equal to |35 - 35| = 0.

Input

The first line of input contains a single integer N, the number of packages. In each of the next N lines, there will be exactly two integers Ai and Bi (1 <= Ai, Bi <= 10 000 000 000 000), denoting the happiness value of the Scientific Committee for the i-th package (Ai), and the happiness value of the Technical Committee for the i-th package (Bi).

Constraints on N will be given in the Scoring section.

Output

The output consists of three lines. In the first line, you should output the minimum difference.

In the second line, there should be exactly N/2 integers denoting which packages should be taken by the Scientific Committee (you can print the numbers in any order). In the third line, there should be exactly N/2 integers denoting which packages should be taken by the Technical Committee (again, in any order).

Constraints

Time limit: 2 seconds
Memory limit: 256 megabytes

Examples

input
4
10 20
10 30
25 10
30 5

output
0
1 3
4 2

Scoring

- In test cases worth at least 20% of all points, 2 <= N <= 20, 1 <= Ai <= 1000 and 1 <= Bi <= 1000.

- In test cases worth an additional 40% of all points, 2 <= N <= 36.

- For the remaining test cases N will be between 40 and 100. Due to the large constraint on N, you should implement as good an algorithm as you can, which still produces a result in the given time limit. Even an approximate value for the minimum difference can be accepted. Better solutions (those who can split the packages with a smaller difference between the happiness of the two committees) will score more points.

A note about testing

The original task given at JBOI 2015 had 100 test cases. In order to speed up the testing when you practice on MENDO, this task (in the training section) has 20 test cases, which let's you see the results for your submission much faster.