题目描述

火星探险者的飞船上的实时软件遇到了名为"优先级倒置"的问题。一种解决该难题的技术是"优先级置顶协议"。这 个问题中，你要模拟一些按照该协议执行的进程。这些进程共用一些资源，但每个资源同时只能被一个进程使用。 为了确保这点，资源在用前会被锁定，用完以后才解锁。每个进程用开始时间、基础优先级（两两不同）、一系列 指令来描述。执行过程中每个进程的优先级可能改变。指令分为3种： compute：进行计算，消耗一微秒。 lock k：锁定资源k（不耗时） unlock k：解锁资源k（不耗时） 锁定一个资源后，这个进程就拥有了这个资源，直到它解锁。每个进程只会解锁它拥有的资源中最近一次锁定的资 源，不会锁定它已经拥有的资源，结束时一定没有拥有任何资源。每个资源有着固定的"最高优先级"，即会发出指 令锁定该资源的进程中基础优先级最高的进程的基础优先级。一个处理器将处理这些进程。开始时，处理器将自身 时钟设为0，然后开始无限循环以下步骤： ①检测正在运行的进程。正在运行的进程是指开始时间小于等于当前处理器时间且指令未被全部执行完毕的进程。 ②决定所有进程的当前优先级，并决定哪些进程将被阻塞。如果进程T的下一个指令是锁定资源k，而k已经被其它 进程拥有，或者至少有一个其它进程拥有某个资源l，且l的最高优先级大于或等于T当前优先级，那么T将会被阻塞 。此时，我们称进程T被每一个拥有这样的k或l的进程阻塞。T的当前优先级是T的基础优先级和所有被T阻塞的进程 的当前优先级中取最大值。 ③执行当前优先级最高且没有被阻塞的进程的下一条指令（如果有的话）。如果当前没有这样的进程，或者处理器 执行了一条compute指令，则把处理器时钟增加1微秒。执行lock或unlock指令后不要增加时钟值。 优先级置顶协议认定以上的操作满足以下性质：当前优先级以当前优先级和进程阻塞来定义，而进程阻塞以当前优 先级定义。尽管这看起来似乎是循环的，一定存在一组唯一的当前优先级满足定义。所有进程最终会结束。第③步 中，优先级最高且没有被阻塞的进程一定只有一个。

输入格式

第一行有两个数t（1≤t≤20）、r(1≤r≤20)，分别表示进程数量和资源数量 接下来t行每行描述一个进程。开始有3个数： 进程开始时间s（1≤s≤10000）、它的基础优先级b（1≤b≤t）、一个整数a（1≤a≤100）。 接下来a个字符串描述指令。每个字符串为一个字母（C、L、U）加上一个整数。 Cn（1≤n≤100）表示n个compute操作。Lk和Uk（1≤k≤r）分别表示锁定和解锁资源k。 没有两个进程基础优先级相同。

输出格式

对于每个进程，输出它执行结束时的时间，按输入顺序输出。

3 1
50 2 5 C1 L1 C1 U1 C1
1 1 5 C1 L1 C100 U1 C1
70 3 1 C1

106
107
71

提示

没有写明提示

题目来源

鸣谢Shimakaze提供译文