Problem: Notes

Template in C

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 1000
* 1 ≤ timei ≤ 50000
* 1 ≤ length of namei ≤ 10
* 1 ≤ Sum of timei ≤ 1000000

Input

n q
name1 time1
name2 time2
...
namen timen


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. namei and timei are separated by a single space.

Output

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

Example

Input

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


Output

p2 180
p5 400
p1 450
p3 550
p4 800

Solution (in JAVA):

Solution:
import java.util.Scanner;
class Queue{
	String name="";
	int time;
	public Queue(String str,int t) {
		name=str;
		time=t;
	}
	public void Show() {
		System.out.println(name+" "+time);
	}
}

public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int i,j,n,q,t,count=0;
        String str="";
        n=scan.nextInt();
        q=scan.nextInt();
        Queue[] queue=new Queue[n];
        for(i=0;i<n;i++) {
        	str=scan.next();
        	t=scan.nextInt();
        	queue[i]=new Queue(str,t);
        }
        i=0;
        t=0;
        while(n>=0) {
        	if(queue[i].time>q) {
        		queue[i].time-=q;
        		t+=q;
        	}
        	else {
        		t+=queue[i].time;
            	System.out.println(queue[i].name+" "+t);
        		for(j=i;j<n-1;j++) {
        			queue[j]=queue[j+1];
        		}
        		i--;
        		n--;
        	}
        	if(count==n)break;
        	i++;
        	if(i>=n) {
        		i=0;
        	}
        }
	}
}