SP27103 FN16MARS - What Really Happened on Mars?

火星探路者号航天器的实时软件曾遇到一个被称为优先级反转的问题。解决这一问题的方法之一是采用优先级天花板协议。 在这个问题中，你需要模拟多个任务在该协议下的执行过程。这些任务共享有限的资源，每个资源在任意时刻只能被一个任务使用。为了确保这一点，任务在使用资源之前需要先锁定资源，使用结束后再解锁。每个任务包含一个开始时间、一个唯一的「基础优先级」以及一系列指令。在执行过程中，任务的「当前优先级」可能会动态改变。指令类型包括： - _计算_ – 执行一微秒的计算任务 - _锁定 $ k $_ – 锁定资源 $ k $（不耗费处理器时间） - _解锁 $ k $_ – 解锁资源 $ k $（同样不耗费处理器时间） 一旦锁定某个资源，该任务便「拥有」此资源，直至资源被解锁。任务只会解锁其最近锁定且当前拥有的资源，且在任务完成时必须确保没有资源被锁定。 每种资源都有一个固定的「优先级天花板」，指的是所有有需求锁定该资源的任务中，基础优先级的最大值。 系统中有一个处理器来依次执行这些任务。当处理器启动时，时钟初始化为零，然后进入无限循环，按以下步骤执行： 1. 判断哪些任务正在运行。一个开始时间不晚于当前时钟，且尚未执行完其所有指令的任务会被认为是正在运行的任务。 2. 确定正在运行任务的当前优先级以及哪些任务会被阻塞。如果任务 $ T $ 的下一个操作是锁定资源 $ k $，且该资源已被占用，或者至少有一个其他任务占用的资源的优先级天花板大于等于任务 $ T $ 的当前优先级，则任务 $ T $ 被阻塞。如果任务 $ T $ 被阻塞，意味着它被每个拥有资源 $ k $ 或其他资源的任务阻塞。任务 $ T $ 的当前优先级为其基础优先级及所有被其阻塞的任务当前优先级的最大值。 3. 执行当前优先级最高的非阻塞运行任务的下一条指令（如果存在这样的任务）。如果没有这样的任务，或者此时执行了一条计算指令，则处理器时钟增加一微秒；如果是锁定或解锁指令，则时钟不增加。 上述优先级天花板协议的特点如下： - 当前优先级和阻塞规则是根据当前优先级来定义的。虽然看似有循环关系，但总能唯一地确定当前优先级。 - 所有任务最终都会完成。 - 在步骤 3 中执行时，永远不会出现优先级相同的情况。

输入包含多组测试数据，请处理到文件结束。每组测试数据包括： 第一行包含两个整数 $ t $ 和 $ r $，分别表示任务数和资源数，其中 $ 1 \leq t \leq 20 $，$ 1 \leq r \leq 20 $。接下来的 $ t $ 行描述每个任务。每个任务的描述从三个整数开始：开始时间 $ s $（$ 1 \leq s \leq 10,000 $）、基础优先级 $ b $（$ 1 \leq b \leq t $）以及整数 $ a $（$ 1 \leq a \leq 100 $），表示有 $ a $ 条指令。每条指令为一个字母（C、L 或 U）和一个整数。指令 C $ n $（$ 1 \leq n \leq 100 $）表示连续 $ n $ 次计算；指令 L $ k $ 和 U $ k $（$ 1 \leq k \leq r $）表示锁定和解锁资源 $ k $。 没有两个任务的基础优先级会重复。

对于每组测试数据： 按照输入顺序输出每个任务完成所有指令的时间。 **本翻译由 AI 自动生成**