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 PYTHON):

Solution:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B
# Queue
# Result:
import sys

class Process:
    def __init__(self, name, time):
        self.name = name
        self.time = time

    def __str__(self):
        return '%s(%d)' % (self.name, self.time)


class Queue:
    def __init__(self):
        self.store = []

    def __str__(self):
        """From head to tail"""
        str_val = ''
        for var in self.store:
            str_val += str(var) + '\n'
        return str_val.rstrip()

    def enqueue(self, v):
        self.store.append(v)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.store.pop(0)

    def is_empty(self):
        if len(self.store) == 0:
            return True
        else:
            return False


### main
vals = sys.stdin.readline().rstrip().split(' ')
n, q = map(int, vals)

queue = Queue()
for i in range(0, n):
    pname, ptime = sys.stdin.readline().rstrip().split(' ')
    queue.enqueue(Process(pname, int(ptime)))

time = 0
while not queue.is_empty():
    p = queue.dequeue()
    if p.time > q:
        p.time -= q
        queue.enqueue(p)
        time += q
    else:
        time += p.time
        print '%s %d' % (p.name, time)