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

class Main{
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        myQueue que=new myQueue();
        
        int n=in.nextInt(),limit=in.nextInt(),sum=0;
        for(int i=0;i<n;i++)que.push(new process(in.next(), in.nextInt()));

        while(!que.isEmpty()){
            process p=que.pop();
            if(p.time<=limit){
                sum+=p.time;
                System.out.println(p.p+" "+sum);
            }
            else{
                sum+=limit;
                p.time-=limit;
                que.push(p);
            }
        }
    }
}

class process{
    String p;
    int time;

    process(String p,int time){
        this.p=p;
        this.time=time;
    }
}

class myQueue{
    process array[];
    int top,tail;

    myQueue(){
        array=new process[1000000];
        top=1; tail=1;
    }

    boolean isEmpty(){
        if(top==tail)return true;
        else return false;
    }

    void push(process x){
        array[tail]=x;
        tail++;
    }

    process pop(){
        process res=array[top];
        top++;
        return res;
    }
}