Interrupt

题目描述

在某单片机上运行的程序中, 有一个周期性触发的 SysTick_Handler 中断函数, 每隔 1 秒触发一次 (时间点 1s, 2s, 3s $\cdots$), 记其优先级为 P, 处理时间为 0 秒. SysTick_Handler 维护一个全局变量 time, 每次成功执行时 time 加 1.

除此之外, 单片机还会接收若干中断信号, 每个信号包含以下属性:

• 中断编号: 每个中断信号在产生时会被赋予一个编号 (正整数), 不同中断信号的编号均不相同;
• 优先级: 每个中断信号还存在一个优先级 (不为 P 的正整数), 优先级高的中断信号会抢占当前正在运行的优先级较低的中断函数进程 (抢占指使 CPU 暂停执行优先级低的进程, 转而执行优先级高的进程);
• 产生时间: 在此题中为了避免与 SysTick_Handler 的进程混淆, 假设中断信号均在 $c.5 \,\text{s}$ 产生, 其中 $c$ 为非负整数;
• 处理时间: 每次中断信号需要进入一个中断函数来处理, 这个处理需要一定的时间, 为了简化题目, 假定所用时间均为正整数.

中断进程调度规则如下：

1. 在任一时刻, 所有已产生的中断信号被存储在一个待执行队列中, 处理完毕后则退出队列.
2. 在任一时刻, 进程调度器总是选取待执行队列中优先级最高的进程占据 CPU 执行.
3. 当新来一个中断信号时, 如果该中断的优先级大于正在执行的进程的优先级, 则发生抢占, 正在执行的进程让出 CPU 给高优先级中断进程执行.
4. 如果两个进程的优先级相同, 则采取先到先得的方案, 创建时间小的先执行; 如果创建时间相同, 则进程号小的先执行.
5. 低优先级的中断被抢占时会保留已执行的状态, 下次继续执行剩余时间.
6. 如果高优先级中断产生时, 低优先级中断恰好处理完毕, 则该低优先级中断视为完成.
7. 优先级高于 P 的中断会直接屏蔽 SysTick_Handler 函数, 被屏蔽后即使到达该执行的时间, 也不会执行或加入待执行队列中.

你的任务是根据输入的中断信号及属性, 模拟整个中断进程调度过程, 并输出每个中断结束时的全局变量 time 值. 需要注意的是, time 只是维护的一个全局变量, 不代表正确的真实时间.

注: 本题目与实际的单片机系统有所差异, 仅作为模拟背景, 请不要作为单片机学习资料.

输入格式

第 1 行为两个正整数 P N, 分别表示 SysTick_Handler 的优先级与其它中断信号的总数目.

接下来 N 行, 每行为一个中断信号的属性, 格式为 n p c d , 分别表示

• n: 中断编号, 正整数, 唯一;
• p: 优先级, 正整数, 且不等于 P;
• c: 产生时间的整数部分, 即表示产生时间为 $c.5 \,\text{s}$ .
• d: 处理时间, 正整数.

保证给出的 N 个中断产生时间非减.

输出格式

共计 N 行, 第 i 行输出第 i 个完成的中断的编号及完成时的 time , 用空格隔开.

样例

样例输入

5 3
3 7 2 3
1 4 6 2
2 6 7 1

样例输出

3 2
2 4
1 5

说明

• 中断编号, 优先级, 产生时间, 处理时间, 完成时间在 int 范围内.
• 1 <= N <= 10^6 .

提示

优先级队列.