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

public class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n, q, time, i;
		queue que = new queue();
		
		n = sc.nextInt();
		q = sc.nextInt();
		
		for(i = 0; i < n; i++){
			String name = new String(sc.next());
			time = sc.nextInt();
			
			que.enqueue(name, time);
		}
		
		que.simulate(q);
	}
}

class data{
	String name;
	int time;
	
	data(String name, int time){
		this.name = name;
		this.time = time;
	}
}

class queue{
	ArrayList<data> Q;
	int head, tail;
	
	queue(){
		Q = new ArrayList<data>();
		head = tail = 0;
	}
	
	void enqueue(String name, int time){
		data process = new data(name, time);
		
		Q.add(process);
		tail ++;
	}
	
	data dequeue(){
		data process = Q.get(head);
		
		head ++;
		
		return process;
	}
	
	boolean isEmpty(){
		if(head == tail){
			return true;
		}
		else{
			return false;
		}
	}
	
	void simulate(int q){
		int sum = 0, cnt = 0, t;
		ArrayList<data> finish = new ArrayList<data>();
		
		while(!isEmpty()){
			data temp = dequeue();
			if(temp.time <= q){
				sum += temp.time;
				temp.time = sum;
				finish.add(temp);
				
				cnt ++;
			}
			else{
				sum += q;
				enqueue(temp.name, temp.time - q);
			}
		}
		
		for(int i = 0; i < cnt; i++){
			System.out.println(finish.get(i).name.toString() + " " + finish.get(i).time);
		}
	}
}