• A
• B
• C
• D
• E
• F
• G
• H

小Q的SRTF 2656

Description

小Q非常喜欢ddd老师上的操作系统课程，有一天，ddd老师在讲第五章CPU调度的时候讲到了最短剩余时间优先调度算法。

该算法能够解决以下问题：
一共有$n$个进程，每个进程的到达时间为$t_i$, 运行时间为$r_i$，需要一种调度算法，来调度进程的执行。

此题中，我们要求模拟最短剩余时间优先调度算法调度这$n$个进程执行的过程。
该算法描述如下：

1. 令当前时刻$t = 0$。
2. 将所有在$t$时刻到达的进程加入队列。
3. 从当前队列中取出剩余运行时间最少的进程出来执行$1s$
    如果当前进程执行完毕，则什么都不做。
    否则将当前进程的剩余运行时间减$1s$，丢回队列。

4. 如果队列中没有进程，则结束，否则将当前时刻$t = t + 1$，回到步骤2。

如果两个进程有相同的剩余时间，按照到达时间调度。

Input

第一行包含一个正整数$T(1 \leq T \leq 10^3)$，表示有$T$组数据。
每一组的数据输入如下：
第一行包含一个正整数$n(1 \leq n \leq 9)$，表示有$n$个进程。
接下来$n$行，每行一个字符串$s_i(|s_i| = 2)$, 两个正整数$t_i, r_i(1 \leq r_i \leq 10)$ 。
输入数据保证$s_i = $"pi", $t_i = i - 1$。

Output

输出包含三部分内容：

第一部分(甘特图)：
这一部分一共三行，详情可以见样例。
此处披露几个细节：

• 一个时间区域内的---p1---, '-'的数量为该进程连续执行时间的数量。

                例如，p1在0 - 3内都在执行，那么'-'的数量就为$3$。
                注意，此处如果两个相邻的时间内都是同一个进程在执行，那么它们的执行区间是要合并的。
                例如，0 - 3内都是p1在执行，应该画成|---p1---|而不是|-p1-|-p1-|-p1-|

• 第二行中的竖线和第一行的竖线对齐
• 竖线的数量为那个竖线对应的时刻的数字的位数。比如3就是一个竖线，13就是两个竖线,133就是三个竖线

第二部分(等待时间)：
第一行输出"Waiting time:"
接下来$n$行，第$i$行输出$pi = x$，$x$表示等待的时间
其中进程等待时间的计算如下：
进程终止的时刻减去到达时刻和运行时间

第三部分(平均等待时间)：
第一行输出"Average waiting time:"
按样例的格式输出，输出结果向下取整，保留整数。
显然，当$n = 1$的时候，这个进程不会有等待时间，那么这一部分的输出为：
Average waiting time:
(0)/1 = 0(ms)

注意，此部分加法表达式中的第$i$个时间表示的是第$i$个进程的等待时间。

Samples