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.io.*;

class Main{
	public static void main(String[] args){
		try{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String wk[] = br.readLine().split(" ", 0);
			int n = Integer.parseInt(""+wk[0]);
			int q = Integer.parseInt(""+wk[1]);
			String name[] = new String[n+1];
			int time[] = new int[n+1];
			int i, ttime=0;
			int head=0, tail=n-1;
			for(i=0; i<n; i++){
				wk = br.readLine().split(" ", 0);
				name[i] = wk[0];
				time[i] = Integer.parseInt(""+wk[1]);
			}
			while(n>0){
				if(time[head]<=q){
					ttime += time[head];
					System.out.println(name[head]+" "+ttime);
					for(i=head; i<n-1; i++){
						name[i] = name[i+1];
						time[i] = time[i+1];
					}
					if(head==n-1) head=0;
					if(tail==n-1) tail=0;
					n--;
				} else{
					ttime += q;
					time[head] -= q;
					head++;
					if(head==n) head=0;
					tail++;
					if(tail==n) tail=0;
				}
			}
		} catch(IOException e){
			System.out.println("Exception :" + e);
		}
	}
}