What Really Happened on Mars?

The real-time software of the Mars Pathfinder spacecraft ran into a fault called priority inversion. One way to deal with it is the priority ceiling protocol.

In this problem you simulate several tasks executing under that protocol. The tasks share a set of resources, and each resource is used by at most one task at a time. To enforce this, a task locks a resource before it uses the resource and unlocks it afterwards. Each task is given a start time, a base priority that no other task shares, and a sequence of instructions. Each task also has a current priority, which may change while the task runs. There are three kinds of instructions:

• compute, performs one microsecond of computation
• lock $k$, locks resource $k$ (this takes no processor time)
• unlock $k$, unlocks resource $k$ (this takes no processor time)

After locking a resource, a task owns that resource until the task unlocks it. A task unlocks only the owned resource it locked most recently, never locks a resource it already owns, and owns no resource when it finishes.

Every resource has a fixed priority ceiling, the largest base priority among the tasks whose instruction sequence contains an instruction locking that resource.

One processor executes the tasks. When the processor starts, it sets its clock to zero and then repeats the following steps forever.

Step 1. Identify the running tasks. A task is running if its start time is at most the current clock value and not all of its instructions have been executed.

Step 2. Determine the current priority of every running task and which of the running tasks are blocked. A running task $T$ is blocked if the next instruction of $T$ locks resource $k$ and either resource $k$ is already owned, or at least one other task owns a resource $\ell$ whose priority ceiling is greater than or equal to the current priority of $T$. In that case every task owning such a $k$ or $\ell$ blocks $T$. The current priority of a task $T$ is the maximum of the base priority of $T$ and the current priorities of all tasks that $T$ blocks.

Step 3. Execute the next instruction of the non-blocked running task with the highest current priority, if such a task exists. If there was no such task, or if a compute instruction was executed, increase the clock by one microsecond. If a lock or an unlock instruction was executed, leave the clock unchanged.

The protocol above has the following properties.

• The current priority is defined from current priorities and from blocking, and blocking is defined from current priorities. The definition looks circular, but exactly one set of current priorities satisfies it.
• Every task eventually finishes.
• Step 3 never produces a tie.

The first line contains two integers $t$ ($1 \le t \le 20$), the number of tasks, and $r$ ($1 \le r \le 20$), the number of resources. Each of the next $t$ lines describes one task, the $i$-th of these lines describing task $i$. A task description begins with three integers, the start time $s$ ($1 \le s \le 10000$), the base priority $b$ ($1 \le b \le t$), and a count $a$ ($1 \le a \le 100$). It ends with $a$ strings that describe the instructions. Each string is a letter (C or L or U) followed by an integer. The string C$n$ ($1 \le n \le 100$) stands for $n$ compute instructions in a row. The strings L$k$ and U$k$ ($1 \le k \le r$) stand for the instruction locking resource $k$ and the instruction unlocking resource $k$.

No two tasks have the same base priority.

For each task, print the time at which it finishes execution, in the order the tasks are given in the input.