화성에서 실제로 일어난 일

화성 탐사선 마스 패스파인더의 실시간 소프트웨어는 우선순위 역전이라는 문제를 겪었다. 이 문제를 다루는 방법 중 하나가 우선순위 상한 프로토콜이다.

이 문제에서는 여러 태스크가 이 프로토콜에 따라 실행되는 과정을 시뮬레이션한다. 태스크는 자원 여러 개를 공유하고, 자원 하나는 한 번에 태스크 하나만 사용한다. 이를 지키려고 태스크는 자원을 쓰기 전에 잠그고 다 쓴 뒤에 푼다. 각 태스크에는 시작 시각, 다른 태스크와 겹치지 않는 기본 우선순위, 명령어 수열이 주어진다. 또 태스크마다 현재 우선순위가 있으며, 이 값은 실행 도중에 바뀔 수 있다. 명령어는 세 종류다.

• compute, 1마이크로초 동안 계산을 수행한다
• lock $k$, 자원 $k$를 잠근다 (프로세서 시간을 쓰지 않는다)
• unlock $k$, 자원 $k$의 잠금을 푼다 (프로세서 시간을 쓰지 않는다)

자원을 잠근 태스크는 그 잠금을 풀 때까지 자원을 소유한다. 태스크는 자신이 소유한 자원 가운데 가장 나중에 잠근 것만 풀고, 이미 소유한 자원을 다시 잠그지 않으며, 실행을 마치는 시점에는 소유한 자원이 없다.

자원마다 우선순위 상한이 하나씩 정해져 있다. 상한은 그 자원을 잠그는 명령어를 포함한 태스크의 기본 우선순위 중 가장 큰 값이다.

태스크는 프로세서 하나가 실행한다. 프로세서는 시작할 때 시계를 0으로 맞춘 뒤 다음 단계를 무한히 반복한다.

1단계. 실행 중인 태스크를 찾는다. 시작 시각이 현재 시계 값보다 작거나 같고 명령어를 아직 다 실행하지 않은 태스크가 실행 중인 태스크다.

2단계. 실행 중인 태스크의 현재 우선순위와, 그중 어느 태스크가 막혀 있는지를 정한다. 실행 중인 태스크 $T$의 다음 명령어가 자원 $k$를 잠그는 명령어이고, 자원 $k$를 이미 어떤 태스크가 소유하고 있거나, 다른 태스크가 우선순위 상한이 $T$의 현재 우선순위 이상인 자원 $\ell$을 소유하고 있으면 $T$는 막힌다. 이때 그런 $k$나 $\ell$을 소유한 태스크 모두가 $T$를 막고 있다고 말한다. 태스크 $T$의 현재 우선순위는 $T$의 기본 우선순위와 $T$가 막고 있는 모든 태스크의 현재 우선순위 중 최댓값이다.

3단계. 막혀 있지 않은 실행 중인 태스크 가운데 현재 우선순위가 가장 높은 태스크의 다음 명령어를 실행한다. 그런 태스크가 없었거나 compute 명령어를 실행했으면 시계를 1마이크로초 늘린다. lock이나 unlock 명령어를 실행했으면 시계를 그대로 둔다.

위 프로토콜에는 다음 성질이 있다.

• 현재 우선순위는 현재 우선순위와 막힘으로 정의되고, 막힘은 현재 우선순위로 정의된다. 정의가 순환하는 것처럼 보이지만, 이 정의를 만족하는 현재 우선순위 조합은 언제나 하나뿐이다.
• 모든 태스크는 언젠가 실행을 마친다.
• 3단계에서 동점은 생기지 않는다.

첫째 줄에 태스크의 수 $t$ ($1 \le t \le 20$)와 자원의 수 $r$ ($1 \le r \le 20$)가 주어진다. 다음 $t$개 줄에 태스크가 하나씩 주어지며, 그중 $i$번째 줄이 태스크 $i$를 설명한다. 각 줄은 시작 시각 $s$ ($1 \le s \le 10000$), 기본 우선순위 $b$ ($1 \le b \le t$), 명령어 문자열의 개수 $a$ ($1 \le a \le 100$)로 시작하고, 이어서 명령어를 나타내는 문자열 $a$개가 주어진다. 각 문자열은 문자 C, L, U 중 하나 뒤에 정수가 붙은 형태다. 문자열 C$n$ ($1 \le n \le 100$)은 연속한 compute 명령어 $n$개를 뜻한다. 문자열 L$k$와 U$k$ ($1 \le k \le r$)는 각각 자원 $k$를 잠그는 명령어와 자원 $k$의 잠금을 푸는 명령어를 뜻한다.

기본 우선순위가 같은 태스크는 없다.

각 태스크가 실행을 마치는 시각을 입력에 주어진 순서대로 출력한다.