The martial art Taekwondo is very popular in Taiwan, although it originated in Korea. Taekwondo is known for its emphasis on high kicking and fast hand techniques, which distinguishes it from martial arts such as Karate or southern styles of Kung Fu.

In Taipei City there is a huge Taekwondo center that has many Dojangs (training halls) aligned in a straight line. Every Dojang has the same distance to the neighboring Dojangs (to the left and to the right), if there are any. The exit is on the very left side. Dojangs are numbered from 1 to $m$ from left to right.

Many training groups use different Dojangs at the same time. A group can book a Dojang for a certain duration, and in doing so, can only specify the starting and ending time, not the actual number of the Dojang. When more than one Dojangs are currently free, groups always choose the free hall that is furthest away from any occupied Dojang. By «away» we mean the minimum of the distance to the nearest occupied Dojang to the right and the distance to the nearest occupied Dojang to the left. If there isn't any occupied Dojang to the left (or to the right, respectively), this distance would simply be infinite. If there are many options, groups always choose the leftmost hall among these (since that's closest to the exit).

So, if all Dojangs are free, the first Dojang chosen is always the leftmost one. If all are free but the leftmost one, then the rightmost is always chosen next.

Given the starting and ending time schedule of the groups, your task is to predict what Dojangs will be used by which groups.


On the first line you are given two integers $n$ and $m$, the number of groups and the number of Dojangs in Taipei's Taekwondo center. The following $n$ lines contain two integers $s_i$ and $e_i$ ($ 0 \leq s_i < e_i \leq 10^9$), the starting and ending times (in minutes) of the different training groups. The $i$th entry corresponds to the $i$th group.

No two groups start at the same time. If a group ends at time 60 (minutes) using Dojang number $x$, the next earliest time another group can use Dojang number $x$ is at time 60 (minutes). This may lead to short collisions, but this decision was made by the management to increase revenue.


Print $n$ lines. The $i$-th line should correspond to the Dojang number that the $i$-th group will use. It is guaranteed that there always is a solution.


  • For 50% of the points it holds that $1 \leq n,m \leq 1\,000$.
  • For all testcases it holds that $1 \leq n,m \leq 100\,000$.



9  8
30 60
60 180
59 119
0 100
10 90
15 30
45 60
110 140
210 240


This schedule corresponds to the sample above.


Sample Files


If you have any questions feel free to ask in the forum or send us an email at info[at]soi[dot]ch