There is a building with floors but only elevator. Initially, the elevator is on the -th floor.
There are people waiting for the elevator. The -th person is currently on the -th floor and wants to take the elevator to the -th floor (). Because the elevator is so small, it can carry at most person at a time.
It costs unit of electric energy to move the elevator floor upwards. No energy is needed if the elevator moves downwards. That is to say, it costs units of electric energy to move the elevator from the -th floor to the -th floor.
Find the optimal order to take all people to their destinations so that the total electric energy cost is minimized.
More formally, let be a permutation of where indicates that the -th person to take the elevator is . The total electric energy cost can be calculated as
where for convenience.
Recall that a sequence of length is a permutation of if and only if each integer from to (both inclusive) appears exactly once in the sequence.
输入格式
There are multiple test cases. The first line of the input contains an integer () indicating the number of test cases. For each test case:
The first line contains two integers and (, ) indicating the number of people and the initial position of the elevator.
For the following lines, the -th line contains two integers and () indicating that the -th person wants to go from the -th floor to the -th floor by elevator.
It's guaranteed that the sum of of all test cases will not exceed .
输出格式
For each test case, first output one line containing one integer indicating the minimum total electric energy, then output another line containing integers separated by a space indicating the optimal order to carry all people. Note that these integers must form a permutation of . If there are multiple optimal orders, you can print any of them.
