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 sc = new Scanner(System.in);

        int n = sc.nextInt();   //プロセス数
        int q = sc.nextInt();   //クオンタム
        int R_time = 0;   //実時間

        ArrayDeque<Proc> queue = new ArrayDeque<>();    //キュー
        Proc tmp;

        for(int i = 0;i < n;i++){
            String name = sc.next();    //プロセス名
            int P_time = sc.nextInt();    //プロセス時間
            queue.add(new Proc(name,P_time));
        }

        while(queue.size() > 0){
            //クオンタム以下
            if(queue.getFirst().num <= q){
                R_time += queue.getFirst().num;
                System.out.println(queue.getFirst().name+" "+R_time);
                queue.removeFirst();
            }
            else{
                R_time += q;
                tmp = queue.getFirst(); //先頭をコピー
                tmp.num -= q;   //プロセス時間からクオンタムを引く
                queue.addLast(tmp); //先頭を末尾に
                queue.removeFirst();    //先頭削除
            }
        }
    }
}

class Proc{
    String name;
    int num;

    Proc(String name,int num){
        this.name = name;
        this.num = num;
    }
}