题目内容

在线大模型推理服务用特征平台缓存特征的 Embedding：显存只留给"热特征"，冷特征需要时再从主机内存拉取。系统为每个特征维护若干条热度记录，热度按半衰期衰减；调度器周期性查询当前热度最高的若干条记录，用来决定哪些特征常驻显存、哪些被换出。

一条热度记录由一次访问产生，记为三元组 $(\mathrm{id}, v, t_x)$：$\mathrm{id}$ 是特征编号，$v$ 是本次访问注入的初始热度，$t_x$ 是注入时刻。add 指令按出现先后从 $1$ 开始编号，第 $i$ 条 add 指令的注入序号就是 $i$，与它是否合法无关。指令名为 add 且本行字段数为 $4$ 的指令才占用编号；因时间戳乱序、编号越界或热度越界被判非法的 add 同样占用一个序号，只是不产生记录（因此序号会出现跳号）。

设半衰期为 $H$。第 $x$ 条记录在时刻 $t\ (t \ge t_x)$ 的热度为

即每经过 $H$ 个时间单位热度减半。指数、除法与大小比较均使用双精度浮点。

系统按时间顺序收到 $n$ 条指令，每条指令带一个时间戳 $t$，共三种：

• add id v：特征 $\mathrm{id}$ 被访问，注入初始热度 $v$，产生一条新记录（注入时刻为 $t$，注入序号为它是第几条 add 指令）。同一特征可以有多条记录。
• del id：特征 $\mathrm{id}$ 被主动下线，删除它注入序号最小的那条尚未删除的记录。
• query K：查询当前热度最大的 $K$ 条记录，按热度从大到小排列，热度相同时注入序号小的排在前面，输出这 $K$ 条记录的注入序号。

指令流中可能存在非法指令。若某条指令非法，系统不执行它（记录集合与时间戳基准都不改变），只输出 -1。判为非法的情况如下：

1. 时间戳小于上一条合法指令的时间戳；
2. 指令名不是 add、del、query 之一，或本行字段个数与指令名不匹配；
3. add 的特征编号不在 $[1,M]$ 之内，或初始热度 $v$ 不在 $[1,10^{6}]$ 之内；
4. del 的特征编号当前没有任何尚未删除的记录；
5. query 的 $K$ 不在 $[1,$ 当前尚未删除的记录总数 $]$ 之内。

第一行的 $n,H,M$ 保证合法。

输入描述

第一行三个整数 $n,H,M$，分别是指令条数、半衰期、特征编号上界。

接下来 $n$ 行，每行一条指令：

t add id v
t del id
t query K

约束

• $1 \le n \le 2\times 10^{5}$，$1000 \le H \le 10^{5}$，$1 \le M \le 10^{5}$；
• 时间戳 $0 \le t \le 10^{5}$，为整数；
• 特征编号 $1 \le \mathrm{id} \le M$，初始热度 $1 \le v \le 10^{6}$；
• add 指令的总条数不超过 $2\times 10^{5}$；
• 所有合法 query 指令的 $K$ 之和不超过 $2\times 10^{5}$；
• 输入均为整数，不含多余空格。

输出描述

输出 $n$ 行，第 $i$ 行对应第 $i$ 条指令：

• 指令非法：输出 -1；
• add 或 del 合法：输出一个整数，即执行后结构中尚未删除的记录总条数；
• query 合法：输出 $K$ 个整数，依次为这 $K$ 条记录的注入序号（按热度从大到小，热度相同按注入序号从小到大），同一行内用一个空格分隔。

样例1

输入

9 1000 100
0 add 1 8
0 add 2 4
500 query 2
500 add 200 6
500 add 1 12
1000 query 3
1000 del 2
1500 query 1
900 add 3 5

输出

1
2
1 2
-1
3
4 1 2
2
4
-1

说明

第 1、2 条指令注入序号 1：$(\mathrm{id}=1,v=8,t=0)$ 与序号 2：$(\mathrm{id}=2,v=4,t=0)$。

第 3 条在 $t=500$ 查询，只经过半个半衰期：

输出 $1\ 2$。

第 4 条 add 200 6 的特征编号超出 $[1,100]$，非法，输出 $-1$；它是第 3 条 add 指令，注入序号 3 因此被跳过，不对应任何记录。第 5 条是第 4 条 add 指令，注入序号为 4：$(\mathrm{id}=1,v=12,t=500)$。

第 6 条在 $t=1000$ 查询：

输出 $4\ 1\ 2$，其中不存在序号 3。

第 7 条删除特征 2 的记录（序号 2），剩余 2 条，输出 $2$。第 8 条在 $t=1500$ 查询：$h_4(1500)=12\cdot 2^{-1}=6$，$h_1(1500)=8\cdot 2^{-1.5}\approx 2.828427$，输出 $4$。

第 9 条时间戳 $900$ 小于上一条合法指令的 $1500$，乱序非法，输出 $-1$。

样例2

输入

7 1000 5
0 add 3 5
0 add 3 5
500 query 2
1000 add 4 9
1500 query 2
1500 del 3
1500 query 1

输出

1
2
1 2
3
3 1
2
3

说明

第 3 条查询时两条记录热度相同：$5\cdot 2^{-0.5}\approx 3.535534$，按注入序号从小到大输出 $1\ 2$。

第 4 条注入序号 3：$(\mathrm{id}=4,v=9,t=1000)$。第 5 条在 $t=1500$ 查询：

后两条并列，取注入序号小的，输出 $3\ 1$。

第 6 条删除特征 3 中注入序号最小的一条（序号 1），序号 2 仍保留，剩余 2 条；第 7 条查询输出 $3$。