第七届“腾讯云杯”上海高校金马程序设计联赛暨东华大学校赛邀请赛(网络同步赛)

G. 资源分配

单点时限: 1.0 sec

内存限制: 128 MB

一个系统中有 $n$ 个进程,$m$ 个资源。

有以下2种操作:

  1. 进程获取资源:p L rL为字母,是Lock的缩写)
  2. 如果资源r没有被任何进程占有,则进程p 占有该资源,打印占有消息。
  3. 如果资源r被进程p 占有,打印重复占有消息。
  4. 如果资源r被其他进程占有,则进程p进入该资源的等待队列,打印等待消息。
  5. 如果进程p已经在资源r等待队列中,打印重复等待消息。
  6. 进程退出p EE为字母,是Exit的缩写)
  7. 打印进程退出消息。
  8. 进程p申请的所有资源都在退出时释放,按照申请顺序倒序释放(注意:是进程提出申请的顺序,而不是进程占有资源的顺序)。
  9. 对于需要释放的资源r
    • 如果当前进程p 占有资源r,释放资源r,打印占有释放消息。
    • 如果资源r等待队列为空,打印空等待队列消息。
    • 否则按照“先来先服务”的原则,选取进程p'占有资源r,打印占有消息。
    • 如果进程p仍然在资源r等待队列中,则将进程p从资源r等待队列中移除,并打印直接释放消息。

消息列表:
- 占有{进程编号}: acquired: {资源编号}
- 重复占有{进程编号}: already acquired: {资源编号}
- 等待{进程编号}: pending: {资源编号}
- 重复等待{进程编号}: already in pending: {资源编号}
- 进程退出{进程编号}: exiting
- 占有释放{进程编号}: releasing: {资源编号}
- 直接释放{进程编号}: exit without acquiring: {资源编号}
- 空等待队列{资源编号}: no pending processes

更多输入输出格式,见样例。数据保证,每个进程的最后一个操作是退出

输入格式

第1行:样例数量$T (1\leq T \leq 20)$

后面有T组测试数据。

每组测试数据由$q+1$行构成:

第1行:进程数量$n$(进程编号:$0, 1, \cdots, n-1$),资源数量$m$(资源编号:$0, 1, \cdots, m-1$),操作数量 $q(1\leq n\leq 1000, 1\leq m\leq 1000, 1\leq q\leq 100000)$

第$2\sim (q+1)$行:2种操作之一。

输出格式

多行消息。

样例

Input
1
3 2 14
2 L 1
2 L 0
0 L 1
2 L 0
0 E
2 L 0
1 L 1
2 L 1
1 L 1
1 L 0
2 L 1
2 E
1 L 0
1 E
Output
2: acquired: 1
2: acquired: 0
0: pending: 1
2: already acquired: 0
0: exiting
0: exit without acquiring: 1
2: already acquired: 0
1: pending: 1
2: already acquired: 1
1: already in pending: 1
1: pending: 0
2: already acquired: 1
2: exiting
2: releasing: 0
1: acquired: 0
2: releasing: 1
1: acquired: 1
1: already acquired: 0
1: exiting
1: releasing: 0
0: no pending processes
1: releasing: 1
1: no pending processes