Có \( n \) tiến trình trong một hàng đợi.
Mỗi tiến trình có \( \text{name}_i \) (tên) và \( \text{time}_i \) (thời gian thực thi).
Thuật toán Round-Robin scheduling xử lý các tiến trình theo thứ tự trong hàng đợi.

Bộ lập lịch Round-Robin cấp cho mỗi tiến trình một quantum (khoảng thời gian xử lý).
Nếu tiến trình chưa hoàn thành sau khoảng thời gian đó, nó sẽ bị tạm dừng, chuyển ra cuối hàng đợi, và bộ lập lịch sẽ xử lý tiến trình kế tiếp.

Giả sử ta có hàng đợi ban đầu với \( \text{quantum} = 100\,\text{ms} \):
\(A(150) - B(80) - C(200) - D(200)\)

Tiến trình A được xử lý trong 100 ms, sau đó bị tạm dừng và chuyển ra cuối hàng đợi với thời gian còn lại 50 ms:
\(B(80) - C(200) - D(200) - A(50)\)

Tiến trình B được xử lý trong 80 ms và hoàn thành tại thời điểm 180 ms, sau đó bị loại khỏi hàng đợi:

\(C(200) - D(200) - A(50)\)

Hãy viết một chương trình mô phỏng thuật toán round-robin scheduling.

Input

• Dòng đầu chứa hai số nguyên: \( n \) và \( q \) — số lượng tiến trình và độ dài quantum (ms).

• \( n \) dòng tiếp theo: Mỗi dòng chứa \( \text{name}_i \) và \( \text{time}_i \), trong đó:

  • \( \text{name}_i \): tên của tiến trình
  • \( \text{time}_i \): thời gian cần để hoàn thành (ms)

Output

In ra tên và thời gian hoàn thành của tiến trình theo thứ tự

Constraint

• \( 1 \le n \le 100000 \)
• \( 1 \le q \le 1000 \)
• \( 1 \le \text{time}_i \le 50000 \)
• \( 1 \le \text{length}(\text{name}_i) \le 10 \)
• \( 1 \le \sum \text{time}_i \le 1000000 \)

5 100
p1 150
p2 80
p3 200
p4 350
p5 20

p2 180
p5 400
p1 450
p3 550
p4 800