Schoolboys Vasya and Pete travel a lot. They use baggage rooms really often. Baggage room has M windows, numbered 1 through M. When a lot of people come, there are big queues in front of windows. Newly come person stands in the queue with the least number of people. If there are several such queues than he or she chooses queue to the window with lowest number. When the queue is chosen, the decision will not further change. When next person comes to the window, he or she spends some time near the window to take or get his stuff, pay money, etc. (let's call it servicing time). This time is specific to each person and doesn't depend on the window. During this time the person is counted as standing in the queue. If new person come in the moment when one or several peoplehave just proceeded to their windows, he or she waits first until these people will leave their queues and then he or she chooses the queue to stand in. Vasya and Pet e wonder when each particular person will leave the queue. Please help them.

The first line of the input file contains two integer numbers N, M (1 ≤ N ≤ 100; 1 ≤ M ≤ 100), where N - number of people, M - number of windows in the baggage room. Next N lines contain pairs of integer numbers k_i, t_i (1 ≤ k_i ≤ 1000; 1 ≤ t_i ≤ 100), where k_i - time moment, when ith person came, t_i - servicing time of ith person. Persons are listed in order of increase of ki.

Print N lines. Print in the ith line two numbers - number of the queue, that would be chosen by ith person and moment of the time, when he or she will leave the queue.

sample input	sample output
5 2 1 2 3 4 4 1 5 2 6 1	1 3 1 7 2 5 2 7 1 8