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.*;
import java.util.*;

class Main {
	final static BufferedReader br = new BufferedReader(new InputStreamReader(
			System.in));
	final static StringBuilder out = new StringBuilder();
	public static void main(String[] Args) throws IOException {
		Queue<Process> p = new ArrayDeque<Process>();
		Process work;
		int elapse = 0;
		String[] in = br.readLine().split("\\s+");
		int n = Integer.parseInt(in[0]);
		int q = Integer.parseInt(in[1]);
		for (int i = 0; i < n; i++) {
			work = new Process(br.readLine());
			p.add(work);
		}
		while ((work = p.poll()) != null) {
			if (work.time <= q) {
				elapse += work.time;
				out.append(work.name).append(' ').append(elapse).append('\n');
			} else {
				work.time -= q;
				elapse += q;
				p.add(work);
			}
		}
		System.out.print(out);
	}
}

class Process {
	String name;
	int time;
	public Process(String str) {
		String[] in = str.split("\\s+");
		name = in[0];
		time = Integer.parseInt(in[1]);
	}
	public Process(String name, int time) {
		this.name = name;
		this.time = time;
	}
}