火星探路者号航天器的实时软件曾遭遇过一个被称为优先级反转（priority inversion）的问题。解决此问题的一种技术是使用优先级天花板协议（Priority Ceiling Protocol）。

在本题中，你将根据该协议模拟多个任务的执行过程。这些任务共享一组资源，每个资源在同一时刻只能被一个任务使用。为了确保这一点，资源必须在使用前锁定，并在使用后解锁。每个任务由开始时间、唯一的基准优先级以及一系列指令定义。每个任务还有一个当前优先级，它可能会在执行过程中发生变化。指令分为三种类型：

• compute – 执行一微秒的计算
• lock k – 锁定资源 $k$（不消耗处理器时间）
• unlock k – 解锁资源 $k$（不消耗处理器时间）

在锁定资源后，称该任务拥有该资源，直到任务将其解锁。任务只会解锁其最近锁定的已拥有资源，不会锁定其已经拥有的资源，并且在完成时不会拥有任何资源。

每个资源都有一个固定的优先级天花板，即包含锁定该资源指令的所有任务中，最高的基准优先级。

有一个单处理器执行这些任务。当处理器启动时，它将时钟初始化为零，然后运行一个包含以下步骤的无限循环：

步骤 1. 识别运行中的任务。如果一个任务的开始时间小于或等于当前处理器时钟，且并非所有指令都已执行完毕，则该任务处于运行状态。

步骤 2. 确定运行中任务的当前优先级，并判断哪些运行中的任务处于阻塞状态。如果运行中的任务 $T$ 的下一条指令是锁定资源 $k$，且资源 $k$ 已经被占用，或者至少有另一个任务拥有一个资源 $\ell$，其优先级天花板大于或等于 $T$ 的当前优先级，则称任务 $T$ 被阻塞。如果 $T$ 被阻塞，则称其被所有拥有此类 $k$ 或 $\ell$ 的任务所阻塞。任务 $T$ 的当前优先级是 $T$ 的基准优先级与 $T$ 所阻塞的所有任务的当前优先级的最大值。

步骤 3. 执行具有最高当前优先级的非阻塞运行任务（如果有）的下一条指令。如果没有这样的任务，或者执行的是 compute 指令，则将处理器时钟增加一微秒。如果执行的是 lock 或 unlock 指令，则不增加时钟。

上述优先级天花板协议具有以下特性：

• 当前优先级是根据当前优先级和阻塞定义的，而阻塞又是根据当前优先级定义的。虽然这看起来是循环定义的，但总会存在一组满足定义的唯一当前优先级。
• 所有任务最终都会完成。
• 步骤 3 中永远不会出现平局。

输入格式

输入的第一行包含两个整数 $t$ ($1 \le t \le 20$)，表示任务数量，以及 $r$ ($1 \le r \le 20$)，表示资源数量。接下来有 $t$ 行，其中第 $i$ 行描述第 $i$ 个任务。任务描述以三个整数开头：任务的开始时间 $s$ ($1 \le s \le 10\,000$)、基准优先级 $b$ ($1 \le b \le t$) 以及整数 $a$ ($1 \le a \le 100$)。任务描述以 $a$ 个描述指令的字符串结束。每个字符串由一个字母（C、L 或 U）后跟一个整数组成。字符串 Cn ($1 \le n \le 100$) 表示 $n$ 个 compute 指令的序列。字符串 Lk 和 Uk ($1 \le k \le r$) 分别表示锁定和解锁资源 $k$ 的指令。

没有两个任务具有相同的基准优先级。

输出格式

对于每个任务，按照输入中给出的顺序，显示其完成执行的时间。

样例

样例输入 1

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

样例输出 1

106
107
71

样例输入 2

3 3
5 3 5 C1 L1 C1 U1 C1
3 2 9 C1 L2 C1 L3 C1 U3 C1 U2 C1
1 1 9 C1 L3 C3 L2 C1 U2 C1 U3 C1

样例输出 2

8
15
16