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;


public class Main {

	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);

		int n = stdIn.nextInt();
		int q = stdIn.nextInt();
        String [] a = new String[n];
        int [] b = new int[n];
        String [] aa = new String[n];
        int [] bb = new int[n];

        for(int i = 0; i < n; i++){
        	a[i] = stdIn.next();
        	b[i] = stdIn.nextInt();
        }
        stdIn.close();

    	int index =0;
    	int basictime=0;
        int ansIndex=0;
        while(true) {
        	if(b[index]==0) {
        		index++;
            	if(index==n){
            		//初期値へ
            		index=0;
            	}
        		continue;
        	}
        	int remaining =b[index]-q;
        	if(remaining >0){
        		b[index] = remaining;
        		basictime+= q;
        	} else {
        		b[index] = 0;
        		aa[ansIndex]=a[index];
        		bb[ansIndex]=q + basictime + remaining;
        		ansIndex++;
        		basictime+= q + remaining;
        		//全チェックし、全てMapにあれば終了
        		if(ansIndex==n){
        			break;
        		}
        	}
        	index++;
        	if(index==n){
        		//初期値へ
        		index=0;
        	}
        }
        for(int i = 0; i < ansIndex; i++){
        	System.out.println(aa[i] + " " + bb[i]);
        }
    }
}