← 返回题目列表

Codeforces · 521/D

D. 店

中文机器翻译题面 查看原题

Vasya 玩一款非常知名且非常流行的 MMORPG 游戏。他的游戏角色有k技能;目前,其中第 i 个等于 ai。该游戏还有一个共同的评级表,其中参与者根据英雄所有技能的乘积按降序排列。

Vasya 决定通过游戏商店“升级”他的角色。这家商店提供了n种可能的方法来提高英雄的技能;这些方式中的每一种都属于以下三种类型之一:

1.将第i个技能分配给b;
2.第i个技能添加b;
3. 将第 i 个技能乘以 b。

不幸的是,a)每个改进只能使用一次; b) Vasya 卡上的钱仅够购买 n 项改进中的不超过 m 项。帮助瓦西亚达到游戏中的最高排名。为此,请告诉 Vasya 他必须购买哪些改进以及应该按什么顺序使用它们,以使他的评级尽可能高。如果有多种方法可以实现,请打印其中任何一种。

输入

第一行包含三个数字——k、n、m(1 ≤ k ≤ 105, 0 ≤ m ≤ n ≤ 105)——技能数量、出售的改进数量以及 Vasya 可以承受的数量。

第二行包含k个空格分隔的数字ai (1 ≤ ai ≤ 106),即技能的初始值。

接下来的 n 行包含 3 个空格分隔的数字 tj, ij, bj (1 ≤ tj ≤ 3, 1 ≤ ij ≤ k, 1 ≤ bj ≤ 106) — 第 j 个改进的类型(1 表示赋值,2 表示加法,3 表示乘法)、可应用的技能以及该改进的 b 值。

输出

第一行应包含数字 l (0 ≤ l ≤ m) — 您应使用的改进数量。

第二行应包含 l 个不同的空格分隔数字 vi (1 ≤ vi ≤ n) — 按应用顺序排列的改进索引。改进按照它们在输入中出现的顺序从 1 开始编号。

示例

输入 #1

2 4 3
13 20
1 1 14
1 2 30
2 1 6
3 2 2

输出 #1

3
2 3 4