CF521D Shop

Vasya 玩一款非常著名且极受欢迎的 MMORPG 游戏。他的游戏角色拥有 $k$ 项技能，目前第 $i$ 项技能的数值为 $a_{i}$。在游戏中，有一个通用的排名表，参与者根据所有技能的乘积进行降序排名。 Vasya 决定通过游戏商店“升级”他的角色。该商店提供了 $n$ 种可用的提升方式；每种提升方式属于以下三类之一： 1. 将第 $i$ 项技能赋值为 $b$； 2. 给第 $i$ 项技能增加 $b$； 3. 将第 $i$ 项技能乘以 $b$。 遗憾的是：（a）每种提升只能使用一次；（b）Vasya 卡里的钱只够最多购买 $m$ 个提升。请帮助 Vasya 获取最高排名。具体来说，请告诉 Vasya 应该购买哪些提升，以及应用这些提升的顺序，使得最终他的评级最大。如果有多种方案都能取得最大排名，输出任意一种即可。

第一行包含三个整数 $k,n,m$（$1 \leq k \leq 10^{5}$，$0 \leq m \leq n \leq 10^{5}$）——技能数、可出售的提升数量，以及 Vasya 能负担的最大提升数。 第二行包含 $k$ 个以空格分隔的整数 $a_{i}$（$1 \leq a_{i} \leq 10^{6}$），表示各项技能的初始数值。 接下来 $n$ 行，每行包含三个以空格分隔的整数 $t_{j},i_{j},b_{j}$（$1 \leq t_{j} \leq 3, 1 \leq i_{j} \leq k, 1 \leq b_{j} \leq 10^{6}$）——表示第 $j$ 个提升的类型（1 代表赋值，2 代表加法，3 代表乘法）、对应的技能编号及该次提升的参数 $b$。提升按输入顺序从 $1$ 开始编号。

第一行输出一个整数 $l$（$0 \leq l \leq m$）——应使用的提升数量。 第二行输出 $l$ 个不同的空格分隔的正整数 $v_{i}$（$1 \leq v_{i} \leq n$）——所选用提升的编号，按应被依次应用的顺序输出。提升编号按输入从 $1$ 开始。

由 ChatGPT 5 翻译