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

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛上，小 F 的开发团队仍然在忙碌着。在解决了进程间资源使用与平衡的问题后，他们紧接着开始研究优化任务调度以便更高效利用 CPU 进行计算的问题。项目开展一段时间取得了多阶段的成果后，他们又把你这名元老级的测试员叫了过去。

题目描述

基础轮转调度逻辑

小 F 首先向你解释了单个 CPU 进行任务轮转调度的方案细节。

使用的 CPU 有一个基础的时间片属性 $t$，单位毫秒。其代表着无论何种任务，在该 CPU 上单次持续运行的时间均不会超过 $t$ 毫秒。并且任何时候 CPU 上都只能运行至多一个任务。

现有 $n$ 个待执行的任务，第 $i$ 个任务有 $a_i$ 单位的工作量需要完成。一个任务在 CPU 上运行时，每 $1$ 毫秒可以完成 $1$ 单位的工作量。

这 $n$ 个任务被放入了一个容量足够大的队列中，从队头到队尾的任务编号依次是 $1,2,\ldots,n$。系统启动后，CPU 会按照如下过程执行任务：

• 从队头取出一个任务，设其当前剩余工作量为 $x$。
• 按照标准效率执行任务，运行 $\min(t,x)$ 毫秒，使该任务的剩余工作量减少 $\min(t,x)$。
• 如果该任务被完成（剩余工作量变为 $0$），则从系统中移除该任务；否则会将其推入队列末尾。
• 重复该流程直到所有任务都被完成。

拿取、移除、放回任务的操作均视为瞬间完成，不消耗时间。

下图为一个 $t=3,n=3$，待执行任务工作量依次为 $4,3,2$ 的运行案例，你可以借助图示更好理解该过程（CPU 中间的大数字代表当前时间片剩余长度）：

同步轮转调度逻辑

小 F 接着说明了需要你来模拟的进阶模型：

现在有 $m$ 个 CPU，第 $i$ 个 CPU 的时间片为 $t_i$ 毫秒。还有 $m$ 个用来调度任务的队列，容量足够大。CPU 和队列均编号 $1\sim m$，初始时对每个 $1\leq i\leq m$，均有 $i$ 号 CPU 对应着 $i$ 号队列。

仍然给定 $n$ 个任务，$i$ 号任务需求的工作量为 $a_i$。为了提高效率，任务不会堆在一个调度队列中，而是采取如下图一样从左到右，从头到尾的平均分配的方式：

具体来说，对于每个 $1\leq i\leq n$，$i$ 号任务初始位于编号为 $(i-1)\bmod m+1$ 的队列中（$\rm mod$ 表示取模运算），且同一队列中从队头到队尾任务编号逐渐增大。

系统开始运转后，每个 CPU 会独立地按照基础的调度逻辑处理自身所对应的队列中的任务。

经过一定时间的研究后，小 F 发现了某些任务具有一些偏好特性。对于任务 $i$，有一个集合 $S_i\subseteq\{1,2,\ldots,m\}$ 表示任务 $i$ 的偏好位置集合。如果任务 $i$ 在 $j$ 号 CPU 上运行且 $j\in S_i$，则该任务的处理效率会变为原来的 $2$ 倍，也即 $1$ 毫秒可以完成 $2$ 工作量（请注意，如果任务只剩下 $1$ 单位的工作量，则这 $1$ 单位工作量仍然需要 $1$ 毫秒来完成）。

具体地讲，剩余工作量为 $x$ 的任务在时间片长度为 $t$ 毫秒的偏好 CPU 上运行时，该次运行时间会变为 $t'=\min(t,\lceil x/2 \rceil)$ 毫秒，其中 $\lceil x/2 \rceil$ 表示对 $x/2$ 向上取整的结果。

优化方案

为了更高效处理任务，小 F 提出了如下方案：

• 自整个系统开始运转起，每经过 $T$ 毫秒，各个 CPU 与队列的对应关系发生一次整体向左循环移位。具体来说，设变换前 $i$ 号 CPU 对应的队列编号是 $j$，那么变换后其对应的队列编号会变成 $j \bmod m + 1$。

小 F 针对该变换进行了细节说明：

• 每个队列中的任务编号和顺序不变，仅仅是 CPU 与队列的对应关系发生了变化。一个正在某 CPU 中执行的任务不属于任何队列，相应的运行过程不会中断。
• 各个 CPU 只按照预设的基础轮转调度方案进行任务处理，也即其取出任务和放回任务的操作都是针对操作进行时对应的队列来完成的。也就是说，一个任务有可能不会被放回到先前取出它的队列中。
• 队列对应关系的循环变换与任务的取出与放回一样，被视为瞬间完成。对于一个 CPU 来说，如果有任务的取出、放回操作和全局的循环移位事件在同一时刻发生，则遵循如下顺序：将任务放回到队尾的操作发生先于全局的循环移位事件，从队头取出任务的操作发生晚于全局的循环移位事件。

你可以结合如下图例，更好地理解某次循环移位变换先后，系统中各对象的关系：

以上便是小 F 对模型的全部说明。

现在给定一组初始情境，请你进行模拟。最终你需要对于每一项任务，输出从它被某 CPU 首次处理到它被处理完成，所经过的毫秒数。

输入格式

从标准输入读入数据。

第一行输入三个整数 $n,m,T$，依次代表任务数量，CPU 数量和全局循环队列调换的触发周期；

第二行输入 $m$ 个整数，第 $i$ 个整数代表 $t_i$；

接下来的 $n$ 行，每一行前两个整数 $a_i,k_i$ 表示任务 $i$ 的工作量（标准处理时长）以及集合 $S_i$ 的大小，即 $i$ 号任务的偏好运行位置数量；接下来紧跟着的 $k_i$ 个整数表示 $S_i$ 内的元素，保证这 $k_i$ 个元素两两不同。

输出格式

输出到标准输出。

输出一行 $n$ 个整数，第 $i$ 个数表示任务 $i$ 从第一次被处理到自身被处理完毕经过的时间。

4 2 2
2 1
2 1 2
3 2 1 2
1 1 2
3 0

2 3 1 4

样例 1 解释

题末的图完整展示了样例 $1$ 中整个系统的所有运行细节（交叉线表示偏好运行）。

子任务

对于前 $40\%$ 的测试数据，保证 $T=10^9$；

对于另外 $40\%$ 的测试数据，保证对于任意 $1\leq i\leq m$，有 $t_i=1$；

保证对于所有测试数据，均有 $1\leq n,m\leq 100,1\leq T\leq 10^9,\forall 1\leq i\leq m$ 有 $1\leq t_i\leq 100$，$\forall 1\leq i\leq n$ 有 $1\leq a_i\leq 100,0\leq k_i\leq m$，且 $\forall x\in S_i,1\leq x\leq m$。