For example, we have the following queue with the quantum of 100ms.

A(150) - B(80) - C(200) - D(200)

First, process A is handled for 100ms, then the process is moved to the end of the queue with the remaining time (50ms).

B(80) - C(200) - D(200) - A(50)

Next, process B is handled for 80ms. The process is completed with the time stamp of 180ms and removed from the queue.

C(200) - D(200) - A(50)

Your task is to write a program which simulates the round-robin scheduling .

Input

n q
name₁ time₁
name₂ time₂
...
name_n time_n

In the first line the number of processes n and the quantum q are given separated by a single space.

In the following n lines, names and times for the n processes are given. name_i and time_i are separated by a single space.

Output

For each process, prints its name and the time the process finished in order.

Constraints

• 1 ≤ n ≤ 100000
• 1 ≤ q ≤ 1000
• 1 ≤ time_i ≤ 50000
• 1 ≤ length of name_i ≤ 10
• 1 ≤ Sum of time_i ≤ 1000000

Sample Input 1

5 100
p1 150
p2 80
p3 200
p4 350
p5 20

Sample Output 1

p2 180
p5 400
p1 450
p3 550
p4 800

Notes

 1     #include <iostream>  
 2     #include <cstdio>  
 3     using namespace std;  
 4       
 5     const int maxn = 100000 + 5;  
 6       
 7     struct node{  
 8       char my_name[10];  
 9       int my_time;  
10     };  
11       
12     int n,q;  
13     int head,tail;  
14     int q_time = 0;  
15     node que[maxn];  
16       
17     void push_back(node& k){  
18       que[tail++] = k;  
19       tail %= (n+5);  
20     }  
21       
22     node pop_front(){  
23       node k = que[head++];  
24       head %= (n+5);  
25       return k;  
26     }  
27       
28     int main(){  
29       scanf("%d%d",&n,&q);  
30       head = 0;  
31       tail = 0;  
32       for(int i = 1;i <= n; i++){  
33         node Q;  
34         scanf("%s%d",Q.my_name,&Q.my_time);  
35         push_back(Q);  
36       }  
37       while(head != tail){  
38         node k = pop_front();  
39         if(k.my_time - q > 0){  
40           k.my_time -= q;  
41           push_back(k);  
42           q_time += q;  
43         }  
44         else{  
45           q_time += k.my_time;  
46           printf("%s %d\n",k.my_name,q_time);  
47         }  
48       }  
49     }