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.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.ConcurrentLinkedQueue;

class Main {

	/*
	 * 最初は10番目のテストケースでTLEになったのがショックでした
	 */

	public static void main(String[] args) throws Exception {
		//入力と準備
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner scanner = new Scanner(br.readLine());
		int n = Integer.parseInt(scanner.next());
		int quantum = Integer.parseInt(scanner.next());
		scanner.close();
		String name[] = new String[n];
		int time[] = new int[n];
		Queue<Integer> queue = new ConcurrentLinkedQueue<Integer>();
		for(int i=0; i<n; i++) {
			scanner = new Scanner(br.readLine());
			name[i] = scanner.next();
			time[i] = Integer.parseInt(scanner.next());
			scanner.close();
			queue.add(i);
		}
		int currentTime =  0;
		//順に処理
		for(;!queue.isEmpty();) {
			Integer taskNo = queue.poll();
			time[taskNo] -= quantum;
			currentTime += quantum;
			if(time[taskNo] <= 0) {
				currentTime += time[taskNo];//超過しているので戻す
				System.out.println(name[taskNo]+" "+String.valueOf(currentTime));
				continue;
			}
			queue.add(taskNo);
		}

	}

}