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 
{
	final static int MAX=100005;
	static Pp[] object=new Pp[MAX];
	static int head,tail;
	public static void main(String[]args)
	{
		
		Scanner scanner=new Scanner(System.in);
		int sum=0,c;
		int q,n;
		Pp u;
		n=scanner.nextInt();
		q=scanner.nextInt();

		for(int i=1;i<=n;i++ )
		{
			object[i]=new Main().new Pp();
			object[i].name=scanner.next();
			object[i].t=scanner.nextInt();
		}
		
		head=1;tail=n+1;
		while(head!=tail)
		{
			u=dequeue();
			c=min(q,u.t);
			u.t-=c;
			sum+=c;
			if(u.t>0)
			{
				enqueue(u);
			}else {
				System.out.println(u.name+" "+sum);
			}
		}
		
		
		
		
	}
	
	static void enqueue(Pp x)
	{
		object[tail]=x;
		tail=(tail+1)%MAX;
		
	}
	
	static Pp dequeue()
	{
		Pp x=object[head];
		head=(head+1)%MAX;
		return x;
	}
	
	static int min(int a,int b)
	{
		return a<b?a:b;
	}
	
	public  class Pp
	{
		 String name;
		 int t;		
	}
	




}