시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB0000.000%

문제

There are N points of interest in Jakarta, positioned west to east on a straight line. These points are numbered from 1 to N, where the 1st point is the west-most point, and the Nth point is the east-most point.

There is a bus stop at each of the point. At the ith point, you can buy a westbound bus ticket for Wi rupiahs. With this ticket, you can go to and visit any point to the west of point i. Similarly, you can also buy an eastbound bus ticket for Ei rupiahs. With this ticket, you can go to and visit any point to the east of point i.

You are at point S and want to visit the rest N − 1 points one by one for your trip. Each point must be visited exactly once. You can choose any point to be your last point. However, at the last point, you must buy either an eastbound or westbound bus ticket to go out from that point. In other words, if your last point is x, you must pay additional min(Wx, Ex) for your trip.

Determine the order of points visited to minimize the total cost for your trip. If there are more than one order of points with minimum total cost, you can choose any one of them.

입력

Input begins with two integers: N S (2 ≤ N ≤ 100000; 1 ≤ S ≤ N) representing the number of points of interest and your initial location, respectively. The next N lines, each contains two integers: Wi Ei (0 ≤ Wi, Ei ≤ 109) representing the cost of the westbound and eastbound bus ticket from point i, respectively.

출력

Output in a line N integers (each separated by a single space) representing the order of points visited to minimize the total cost for your trip.

예제 입력 1

4 2
1 2
3 4
10 10
4 1

예제 출력 1

2 1 3 4

If you visit the points with the order described in the sample output, the following is the costs for your trip:

  • You pay 3 rupiahs to go from point 2 to point 1.
  • You pay 2 rupiahs to go from point 1 to point 3.
  • You pay 10 rupiahs to go from point 3 to point 4.
  • You pay min(4, 1) = 1 rupiah to go out from point 4.

Therefore, you pay a total of 16 rupiahs. There is no order of points visited such that the total cost for your trip is less than 16.

예제 입력 2

5 5
4 2
1 10
9 8
3 7
6 5

예제 출력 2

5 4 2 1 3