A171746.Yuilice 的打印店

Yuilice 的打印店有 $p$ 台打印机，编号为 $1$ 到 $p$。第 $j$ 台打印机打印一页需要 $s_j$ 个时间单位。

所有打印机共用一个先进先出的等待队列。初始时队列为空，所有打印机均空闲且允许接单。每台打印机同时只能处理一个订单；订单开始后不会被中断、拆分或转移。

有以下四类操作：

操作编号	参数	含义
$1$	页数 $x$	提交一个订单并加入队尾。订单按提交顺序依次编号为 $1,2,\ldots$
$2$	订单编号 $x$	如果该订单仍在等待，则取消；若正在打印、已完成或已取消，则不产生影响
$3$	打印机编号 $x$	暂停该打印机接收新订单，当前订单仍正常打印
$4$	打印机编号 $x$	恢复该打印机接收新订单

重复暂停或重复恢复均不产生额外影响。取消操作引用的订单一定已经提交。

接单规则： 空闲且允许接单的打印机，按编号从小到大依次领取队列中最早的未取消订单。若在时刻 $t$ 把一个 $a$ 页的订单交给打印机 $j$，它在时刻 $t+a s_j$ 完成。

同一时刻的处理顺序：

1. 结算这一时刻所有完成的订单，使对应打印机空闲。
2. 按输入顺序执行这一时刻的全部操作，操作之间不分配订单。
3. 按接单规则统一分配等待订单。

没有外部操作的订单完成时刻，也需要执行结算和分配。最后一条操作处理完后，打印店仍按相同规则运行。请输出每个订单最终的结果。

第一行包含两个整数 $p,q$，分别表示打印机数量和操作数量。

第二行包含 $p$ 个整数 $s_1,\ldots,s_p$，其中 $s_j$ 表示第 $j$ 台打印机打印一页所需的时间。

接下来 $q$ 行，每行包含三个整数 $t,op,x$，其中 $t$ 表示操作发生的时刻，$op$ 表示操作类型编号，$x$ 表示该类操作的参数。各类型的具体含义如下：

• $op=1$：提交订单，$x$ 表示该订单的页数。
• $op=2$：取消订单，$x$ 表示要取消的已提交订单编号。
• $op=3$：暂停接单，$x$ 表示要暂停接单的打印机编号。
• $op=4$：恢复接单，$x$ 表示要恢复接单的打印机编号。

操作按时刻不减的顺序给出；同一时刻的输入顺序就是执行顺序。

设共有 $n$ 次提交操作，按订单编号从小到大输出 $n$ 行：

• 如果订单完成，输出完成时刻。
• 如果订单被取消，输出 $-1$。
• 如果订单最终始终没有开始，输出 $-2$。

最后一种情况是指：所有操作均已处理、所有正在打印的订单均已完成，而等待队列仍有订单且全部打印机都已暂停接单。

样例解释

样例 $1$：时刻 $0$，打印机 $1$、$2$ 分别领取订单 $1$、$2$，完成时刻为 $6$、$4$。订单 $3$ 在时刻 $1$ 入队。时刻 $4$ 先完成订单 $2$，随后暂停打印机 $2$、取消订单 $3$、提交订单 $4$，此时无法接新单。时刻 $6$，订单 $1$ 完成，打印机 $2$ 恢复；按编号顺序，订单 $4$ 由打印机 $1$ 领取，在时刻 $8$ 完成。

样例 $2$：时刻 $0$ 的全部操作执行完才接单，所以订单 $1$ 在开始前就被取消。订单 $2$ 在时刻 $1$ 完成。随后打印机暂停，订单 $3$ 一直等待。

数据范围

对于所有测试数据，满足：

• $1\le p\le20$，$1\le q\le2\times10^5$。
• $1\le s_j\le10^6$，操作时刻满足 $0\le t\le10^9$。
• $1\le op\le4$；提交操作的页数满足 $1\le x\le10^6$。
• 取消操作的 $x$ 是此前已提交的某个订单编号；暂停、恢复操作满足 $1\le x\le p$。
• 至少包含一次提交操作。

测试点	分值	额外限制
1–2	10	$p=1$，且只有提交操作
3–6	20	只有提交操作
7–10	20	只有提交、取消操作
11–20	50	无额外限制