Priority Ceiling Protocol Simulation

This problem involves simulating the execution of multiple tasks under the Priority Ceiling Protocol in a uniprocessor system. Each task is defined by a starting time, a unique base priority, and a list of instructions. The instructions include:

• compute – performs computation for one microsecond.
• lock k – locks resource k (this operation takes no processor time).
• unlock k – unlocks resource k (this operation takes no processor time).

When a task locks a resource, it owns the resource until it unlocks it. Tasks follow a last‐in first‐out discipline when unlocking resources. Each resource has a fixed priority ceiling which is defined as the maximum base priority of any task that attempts to lock that resource.

The processor simulator works in discrete microsecond steps and at each step it performs the following:

1. Identify running tasks: A task is running if its start time is less than or equal to the current clock and it has not finished executing all of its instructions.
2. Determine current priorities and blocking: For every running task, its current priority is defined as the maximum of its base priority and the current priorities of all tasks it is blocking. A task T is blocked if its next instruction is lock k and either resource k is already locked or there is at least one other running task owning a resource whose priority ceiling is \(\geq\) the current priority of T. If T is blocked, then every task owning a resource causing the block is said to block T and may have its current priority raised.
3. Execution: Among all running and non‐blocked tasks, the one with the highest current priority is chosen to execute its next instruction. If no such task exists, or if the instruction executed is compute, the processor clock is incremented by one microsecond. In contrast, lock and unlock instructions take no time.

It is guaranteed that:

• The interdependency between current priorities and blocking has a unique solution.
• All tasks eventually complete.
• There will never be a tie when choosing the next task to execute.

Task: Given the description of tasks and their instructions, simulate the execution and determine the finishing time (in microseconds) for each task. Output the finishing times in the order the tasks were given, separated by spaces.

inputFormat

The input begins with a single integer N (1 ≤ N ≤ 50) denoting the number of tasks. This is followed by N task descriptions.

For each task, the first line contains three integers: start (0 ≤ start ≤ 10⁹), base_priority (an integer where higher value means higher priority) and M (the number of instructions in the task, 1 ≤ M ≤ 1000). Each of the next M lines contains one instruction, which is either:

• compute
• lock k (1 ≤ k ≤ 100), or
• unlock k

It is guaranteed that each task will not attempt to lock a resource it already owns and will unlock resources in a LIFO order with no resource left locked at the end.

outputFormat

Output a single line containing N integers separated by spaces, where the i^th integer is the finishing time (in microseconds) of the i^th task.

sample

1
0 1 2
compute
compute

2

</p>