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){
    Queue<String> queue = new ArrayDeque<String>();
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); //処理する数
    int q = sc.nextInt(); //クオンタム
    int sum = 0;          //処理した数
    int sumTime = 0;      //合計処理時間
    for(int i = 0; i < 2*n; i++){
        String x = sc.next();
        queue.add(x);
    }
    /*処理部分*/
    while(sum != n){
        String name = queue.poll();
        int time = Integer.parseInt(queue.poll());
        if(time > q){
            sumTime += q;
            time -= q;
            queue.add(name);
            queue.add(String.valueOf(time));  //intをInteger経由でStringに変換している
        }
        else{
            sumTime += time;
            sum++;
            System.out.println(name +" "+sumTime);
        }
    }

    }
}