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

public class Main
{
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args)throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//Scanner sc = new Scanner(System.in);
		Deque<String> nameQue = new ArrayDeque<>();
		Deque<Integer> workQue = new ArrayDeque<>();
		String[] rem  = br.readLine().split(" "); 
		int n = Integer.parseInt(rem[0]);//Integer.parseInt(sc.next());
		int time = Integer.parseInt(rem[1]); //Integer.parseInt(sc.next());
		//int[][] data = new int[n][2];
		//String[] stemp ;
		for(int i= 0 ; i< n ; i++){
			rem = br.readLine().split(" "); 
			nameQue.offer(rem[0]);
			workQue.offer(Integer.parseInt(rem[1]));
		}
		roundSche(nameQue,workQue,time);
	}
	public static void roundSche(Deque<String> nameQ , Deque<Integer> workQ , int time)
	{
		int pos , prog = 0;
		int temp ;
		while(workQ.size() != 0)
		{
			temp =  workQ.poll();
			if(temp <= time){
				prog += temp;
				sb.append(nameQ.poll()).append(' ').append(prog).append('\n');
			}
			else 
			{
				workQ.offer(temp - time);
				nameQ.offer(nameQ.poll());
				prog += time;
			}
		}
		System.out.print(sb);
		
	}
	
}