[HNOI2003]操作系统

编写一个程序，模拟只有一个 CPU 的操作系统进行进程调度。

每个进程的进程号、到达时间、执行时间和运行优先级均为已知。运行优先级用自然数表示，数值越大，优先级越高。

如果一个进程到达时 CPU 空闲，那么它将占用 CPU，直到执行结束，除非在此期间有优先级更高的进程到达。此时，新到达的高优先级进程将抢占 CPU，原进程暂停执行并进入等待状态。

如果一个进程到达时，CPU 正在执行优先级高于或等于它的进程，那么新到达的进程必须等待。

当 CPU 空闲且有进程正在等待时，选择优先级最高的进程执行。如果有多个进程具有相同的最高优先级，则选择到达时间最早的进程。

输入格式

输入包含若干行，每行包含四个自然数，依次表示进程号、到达时间、执行时间和运行优先级。

不同进程的进程号互不相同。输入数据已按到达时间从小到大排序，并且不会有两个优先级相同的进程同时到达。

输出格式

按照进程结束的先后顺序，输出每个进程的进程号和结束时间，每个进程占一行。

样例输入

1 1 5 3
2 10 5 1
3 12 7 2
4 20 2 3
5 21 9 4
6 22 2 4
7 23 5 2
8 24 2 4

样例输出

1 6
3 19
5 30
6 32
8 34
4 35
7 40
2 42

数据范围

• 输入中的所有数均为不超过 $10^8$ 的自然数；
• 任意时刻，等待队列中的进程数量不超过 $1.5\times 10^4$；
• 不同进程的进程号互不相同；
• 不会有两个优先级相同的进程同时到达；
• 输入数据按到达时间从小到大排序。

来源与许可

本题为 HNOI 2003 试题「操作系统」，题面与测试数据整理自 BZOJ。

样例 1

输入

1 1 5 3
2 10 5 1
3 12 7 2
4 20 2 3
5 21 9 4
6 22 2 4
7 23 5 2
8 24 2 4

输出

1 6
3 19
5 30
6 32
8 34
4 35
7 40
2 42