题目来自第 42 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛上，小 F 的团队每天都在忙碌着。他们在解决了进程与接口的通信问题后，开始着手进行进程间资源使用与调度系统的开发。项目开展一段时间后，他们又把你这个资深测试员叫了过来。按照惯例，他们给出了这次资源调度系统的运行模型，并请求你为其编写程序进行模拟。

题目描述

模型中需要考虑的对象有 $n$ 个进程与 $m$ 种资源。进程由 $1,2,\cdots,n$ 依次标号，资源由 $1,2,\cdots,m$ 依次标号。

该系统运行的时间单位称作段。每一段分为“申请”“处理”“释放”三个部分（本题亦称其“段首”“段中”“段末”），在时间轴上体现如下：

申请部分（段首）专门处理进程对资源的申请行为，在处理部分（段中）每个进程会产生各自的收益，释放部分（段末）专门负责将资源从进程中释放到待使用区。

系统会依次运行第 $1,2,\cdots,10^{100}$ 段（视为足够多）。每一段内会依次运行申请部分、处理部分与释放部分。初始所有资源都处于待使用状态。

属性说明

第 $i$ 个进程会从第 $st_i$ 段首开始活动。

第 $i$ 个进程有一个长度为 $k_i$ 的运行任务列表，列表可以由长度为 $k_i$ 的二元组序列表示：$(a_{i,1},t_{i,1}),(a_{i,2},t_{i,2}),\cdots,(a_{i,k_i},t_{i,k_i})$。其中 $a_{i,j}$ 表示 $i$ 号进程第 $j$ 次运行任务前会申请的资源编号，$t_{i,j}$ 表示 $i$ 号进程第 $j$ 次运行任务的持续段数。保证对于同一个 $i$，$a_{i,j}$ 两两不同。

单进程行为与收益

一个进程分为资源申请状态和任务运行状态。刚从某段首开始活动的进程初始为资源申请状态。

• 在某一段首，一个处于资源申请状态的进程会向其当前所需的某资源发起申请。
• 在某一段中，一个处于任务运行状态的进程会获得收益，收益量等于其在该段段首运行完毕后拥有的资源数量。

在没有任何干扰，资源可以由某 $i$ 号进程任意自由使用的情况下，其理想行为如下：

• $i$ 号进程于第 $st_i$ 段首开始活动，并同时对 $a_{i,1}$ 号资源发起申请。由于没有任何干扰，资源 $a_{i,1}$ 被其占有。同时 $i$ 号进程切换为任务运行状态。
• 接下来的（包括段首申请成功的这一段） $t_{i,1}$ 段里，$i$ 号进程处于任务运行状态。根据定义，每一段中其会获得 $1$ 的收益，该阶段在第 $st_i+t_{i,1}-1$ 段末结束，同时 $i$ 号进程切换为资源申请状态。
• 在第 $st_i+t_{i,1}$ 段首对 $a_{i,2}$ 号资源发起申请，资源 $a_{i,2}$ 被 $i$ 号进程占有。同时 $i$ 号进程再次切换为任务运行状态。同理，进程继续运行 $t_{i,2}$ 段并获得收益。以此类推，$i$ 号进程可以顺利执行所有 $k_i$ 个任务，过程中不断切换自身状态。
• 最终 $i$ 号进程会在第 $st_i+\sum\limits_{j=1}^{k_i} t_{i,j}-1$ 段末完成所有运行任务并停止活动。在这一段末，$i$ 号进程会释放所有其使用的资源，也即资源 $a_{i,1},a_{i,2},\cdots,a_{i,k_i}$ 均不再被占有，而是变为待使用状态。

根据定义，上述过程 $i$ 号进程从开始活动到结束的理想总收益为 $\sum\limits_{j=1}^{k_i}j\times t_{i,j}$，因为从第 $j$ 次申请成功开始到第 $j+1$ 次申请前，共 $t_{i,j}$ 段，进程 $i$ 在每一段的段中都会获得 $j$ 的收益。

下面图 $2$ 给出了一个 $m=4,st_1=2,k_1=3$，运行任务列表为 $(1,3),(3,4),(4,3)$ 的 $1$ 号进程的运行示例，你可以借助图 $2$ 理解上述过程。为了不让段首段末的分隔显得杂乱，图中时间轴上每一个小区间表示一个完整的段。

协同运行

然而，任何资源在任意一段都只能被至多一个进程占有。敏锐的你注意到，当多个进程同时活动时，可能在同一段首对同一资源发起申请，就会产生冲突。对此，小 F 针对模型进行了说明：

• 考察在第 $s$ 段首，处于资源申请状态的若干进程（一个或多个）同时对某资源 $x$ 发起了申请。
  • 如果资源 $x$ 不处于待使用状态（正在被其它进程占有），则所有进程均申请失败。
    • 否则资源 $x$ 处于待使用状态。设在这些进程中编号最小者的编号为 $i$，则进程 $i$ 申请成功并占有资源 $x$，其它进程均申请失败。
• 如果一个进程申请成功，则它会自然切换到任务运行状态并继续接下来的任务。
• 如果一个进程申请失败，它不会切换到任务运行状态，根据定义该段段中不产生收益。它会在第 $s+1$ 段首继续对资源 $x$ 发起申请。

在上例基础上，下图展示了当新增一个 $st_2=3,k_2=2$，运行任务列表为 $(2,6),(4,2)$ 的 $2$ 号进程后，整个系统的运行情况，你可以借助该图理解上述过程。

死锁优化方案

小 F 指出，如果只是这样设计资源的调配会导致死锁现象的发生，也即两个进程分别占有两种资源，在未释放这两种资源的情况下，又同时对对方占有的另一种资源发起申请，就会导致死循环，永远无法正常运行下去。

为了解决这个问题，小 F 设计了 A，B，C 共 3 种不同的优化方案，每个进程最多采取一种方案。我们将不采取任何方案的进程与采取 A/B/C 三种方案的进程依次称为 X/A/B/C 类进程。前者称为普通进程，后三者称为特殊进程。

每一个 A/B/C 类进程都会拥有一个额外属性 $w_i$，称作忍耐限度。

• 设某进程 $i$ 刚开始活动或刚运行完上一任务，在第 $s$ 段段首首次对某资源 $x$ 发起申请。如果第 $s$ 段段首至第 $s+w_i-1$ 段段首发起的共 $w_i$ 次申请均失败，则根据类型的不同，进程 $i$ 会有如下行为：
  • 如果进程 $i$ 为 A 类，其会在第 $s+w_i-1$ 段末释放目前占有的所有资源，令其变成待使用状态，自身仍保持资源申请状态持续索要资源 $x$，直到申请成功的某一段首切换为当前任务的任务运行状态。
    • 值得说明的是，在之后某一段首终于获得资源 $x$ 之后，$i$ 号进程执行任务的收益显然会因为其放弃行为大打折扣，但是其并不会重新申请之前放弃的资源，而是以低收益继续运行自身接下来的任务。如果之后仍然有“卡住”的情况，其仍会按照 A 类进程特性选择放弃。
    • 如果进程 $i$ 为 B 类，其会在第 $s+w_i-1$ 段首申请失败后直接放弃资源 $x$，并将自身切换为任务运行状态，从该段段中直接开始进入对应的 $t_{i,*}$ 段运行。显然，该放弃行为也会导致进程 $i$ 最终收益低于其理想收益。
    • 如果进程 $i$ 为 C 类，其会在第 $s+w_i$ 段首直接无视资源 $x$ 当前的归属，直接强行申请成功并将资源 $x$ 占有（同时原来占有资源 $x$ 的进程不再占有资源 $x$），同时切换为任务运行状态运行下去。
    • 设原来占有资源 $x$ 的进程为 $j$（可能为任意进程，例如是上一段首刚刚抢到 $x$ 的另一 C 类进程，或者某因为申请另一资源正卡住的普通进程等等），该抢夺行为除了可能会影响进程 $j$ 的收益以外，不会打断或影响其任何运行状态。 - 如果在同一段首对某资源 $x$ 同时有多个 C 类进程的抢夺行为发生，则恰有编号最大的 C 类进程的抢夺行为成功，其它 C 类进程的抢夺行为均失败。抢夺失败的 C 类进程不占有资源 $x$，但也切换为任务运行状态运行下去。 - 如果资源 $x$ 在同一段首还有其它任何类型进程的申请需求，则响应 C 类进程的抢夺行为，其它申请均失败。

题目的样例中涉及了特殊进程的行为，你可以结合样例解释与相应图片理解上述关键信息。

当所有进程均执行完全部任务并停止活动时，系统运行结束。注意，如果系统没有在第 $10^{100}$ 段末前运行结束，其会强行结束自身运行，所有进程的运行收益不受影响。

现在，小 F 给你提供了 $n,m$ 以及 $n$ 个进程的所有信息。请你对上述过程进行模拟并最终输出各个进程的运行收益与运行段数。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n,m$，表示进程数量与资源种类数。

接下来的 $n$ 行，第 $i$ 行输入第 $i$ 个进程的全部信息。每行首先输入一个 X，A，B，C 中的字符表示进程类型。

如果输入为字符 X 代表进程 $i$ 为普通进程。接下来输入两个正整数 $st_i,k_i$，然后输入 $2k_i$ 个正整数，依次代表 $a_{i,1},t_{i,1},a_{i,2},t_{i,2},\cdots,a_{i,k_i},t_{i,k_i}$。

否则代表进程 $i$ 为对应的 A/B/C 类特殊进程。接下来输入三个正整数 $st_i,w_i,k_i$，然后输入 $2k_i$ 个正整数，依次代表 $a_{i,1},t_{i,1},a_{i,2},t_{i,2},\cdots,a_{i,k_i},t_{i,k_i}$。

所有同一行的不同信息均由一个空格分隔。

输出格式

输出到标准输出。

请你输出 $n$ 行，每行输出用空格隔开的两个整数。

第 $i$ 行的第一个整数表示系统运行结束后，进程 $i$ 的总运行收益。

第 $i$ 行的第二个整数表示进程 $i$ 从开始活动到停止活动的持续段数。如果进程 $i$ 未正常结束而是因为系统强行终止而结束，请输出 $-1$。

3 5
X 1 3 1 3 3 4 4 3
B 2 2 4 2 1 1 2 5 3 3 2
C 3 3 2 1 2 4 2

15 10
13 10
6 10

样例 1 解释

下面列出该样例中涉及的特殊事件：

第 $3\sim 4$ 段首 $2$ 号进程申请资源 $1$ 均失败，故其放弃申请 $1$ 号资源，从第 $4$ 段中起仅占用资源 $2$ 运行第二个任务至第 $5$ 段末。

第 $9\sim 10$ 段首 $2$ 号进程申请资源 $3$ 均失败，故其放弃申请 $3$ 号资源，从第 $10$ 段中起仅占用资源 $2,5$ 运行第四个任务至第 $11$ 段末。

第 $3\sim 5$ 段首，$3$ 号进程申请资源 $1$ 均失败，故于第 $6$ 段首将 $1$ 号资源抢夺并占有 $1$ 号资源运行第一个任务至第 $7$ 段末；第 $8$ 段首与 $1$ 号进程同时申请 $4$ 号资源因为编号较大失败，持续到第 $10$ 段首。第 $11$ 段首 $3$ 号进程抢夺了刚刚在第 $10$ 段末被 $1$ 号进程释放到待使用区的 $4$ 号资源，并占用资源 $1,4$ 运行第二个任务至第 $12$ 段末。

从图中可以看出三个进程的运行段数均为 $10$。

10 40
X 6 32 13 7 2 18 10 4 25 3 1 7 28 10 37 10 32 16 30 8 16 11 19 11 29 12 33 4 39 5 24 5 34 10 27 4 38 20 21 8 18 2 9 16 20 17 23 17 35 11 31 14 8 20 7 17 12 19 6 1 5 19 3 10 22 12
X 10 17 35 5 20 17 30 1 9 2 12 8 34 4 28 17 18 15 22 17 1 7 7 7 24 4 5 15 31 4 2 4 25 20 3 20
X 4 33 38 3 17 6 16 19 21 7 23 17 22 4 11 12 7 3 1 4 24 11 35 20 26 6 33 7 8 11 13 4 25 17 4 5 40 9 39 18 18 9 5 6 9 2 14 14 34 10 28 2 32 3 2 14 30 9 27 8 3 3 29 11 19 7 36 6
X 20 6 31 15 19 4 1 11 3 12 8 14 15 13
X 8 28 19 6 1 20 22 6 16 17 14 3 34 14 3 19 40 5 10 5 27 9 6 2 13 14 35 6 26 8 18 10 23 10 20 12 2 7 30 20 39 3 36 6 4 10 17 5 5 16 38 13 28 11 33 4 29 5
X 19 26 35 14 10 5 17 15 5 18 6 1 38 20 4 4 3 18 31 11 20 1 22 3 39 15 7 11 27 7 8 19 16 2 32 9 26 15 25 6 28 15 1 10 23 8 34 14 30 8 29 15 9 19
X 6 6 22 20 37 9 27 7 13 7 16 6 14 19
X 5 8 5 1 14 8 6 4 11 7 37 7 9 10 20 20 18 17
X 7 2 3 3 40 9
X 1 3 3 18 31 15 12 16

67 -1
42 -1
185 -1
15 -1
46 -1
0 -1
20 -1
152 -1
21 55
96 49

子任务

对于前 $40\%$ 的测试数据，保证不存在特殊类型的进程。

对于另外 $40\%$ 的测试数据，保证不存在 C 类进程。

对于 $100\%$ 的测试数据，保证 $1\leq n\leq 10,1\leq m\leq 40$。$\forall 1\leq i\leq n$ 有 $1\leq st_i\leq 20,1\leq w_i\leq 20,1\leq k_i\leq 40,1\leq t_{i,j}\leq 20,1\leq a_{i,j}\leq m$，且保证 $\forall j_1\neq j_2,a_{i,j_1}\neq a_{i,j_2}$。