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

class Main {

  public static class Process {

    public String name;
    public int time;

    public Process(String name, int time) {
      this.name = name;
      this.time = time;
    }

  }

  public static void process(Queue<Process> q, int quantum) {

    int curr_time = 0;

    while (q.isEmpty() == false) {

      Process curr_ps = q.remove();

      int time_passed = Math.min(quantum, curr_ps.time);
      curr_time += time_passed;
      curr_ps.time -= time_passed;

      if (curr_ps.time == 0)
        System.out.println(curr_ps.name + " " + curr_time);
      else
        q.add(curr_ps);
    }

  }

  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    int quantum = s.nextInt();
    Queue<Process> processes = new LinkedList<Process>();
    for (int i = 0; i < n; i++) {
      processes.add(new Process(s.next(), s.nextInt()));
    }
    process(processes, quantum);
  }
}