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

import java.util.Scanner;
class Main{
    static public void  main(String[] av){
        int sum=0;

        Scanner sc =new Scanner(System.in);
       // int n =sc.nextInt();
int ch =1;
int[] a= new int[100];

    //String s= sc.next();
    int n = sc.nextInt();
    int q =sc.nextInt();
    List<String> list = new ArrayList<String>();
    List<Integer> intlist = new ArrayList<Integer>();
    List<String> sl = new ArrayList<String>();
    List<Integer> il = new ArrayList<Integer>();
for(int k=0;k<n;k++){
    list.add(sc.next());
    intlist.add(sc.nextInt());
}     
int q2= q;
int t=0;
    while ( list.size() !=0){
   if (q2==0){
       q2=q;
   }
        if ( intlist.get(0) <=q2){
            t+=intlist.get(0);
q2=q2-intlist.get(0);
sl.add(list.get(0));
il.add(t);

intlist.remove(0);
list.remove(0);
q2=q;
        }
        else{
       t+=q2;     
intlist.set(0,intlist.get(0)-q2);
q2=0;
int x=intlist.get(0);
String y=list.get(0);
intlist.remove(0);
list.remove(0);
intlist.add(x);
list.add(y);
        }

    }
    for (int i=0;i<n;i++){
        System.out.println(sl.get(i)+ " "+ il.get(i));
    }
}
    }