← 返回题目列表

Codeforces · 920/D

D. 坦克

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

Petya 有时必须给他的田地浇水。为了给田地浇水,Petya 需要一个装有 V 毫升水的水箱。

Petya 有 N 个水箱,其中第 i 个水箱最初装有 ai 毫升的水。这些水箱非常大,任何一个都可以容纳任意数量的水(无论这个量有多大)。

此外,Petya 有一个勺子,最多可容纳 K 毫升水(勺子最初是空的)。这个勺子可以用来从某个水箱中取一些水,然后将其全部倒入某个水箱中(不可能从多个水箱中取水而不倒水,或者倒水时在勺子里留下一些水)。当 Petya 尝试从水箱中取水时,他会得到 min(v, K) 水,其中 v 是水箱中当前的水量。

使用这些操作是否可以获得一个恰好装有 V ml 水的水箱?如果可能,请打印允许执行此操作的操作序列。如果有多种方法可以在某个水箱中获取所需的水量,请打印其中任何一种。

输入

第一行包含 3 个整数:N (2 ≤ N ≤ 5000)、K (1 ≤ K ≤ 5000) 和 V (0 ≤ V ≤ 109) — 分别是水箱的数量、勺子可容纳的最大水量以及某个水箱中所需的水量。

第二行包含 N 个整数 ai (0 ≤ ai ≤ 105),其中 ai 是第 i 个水箱中的初始水体积。

输出

如果不可能获得恰好装有 V 毫升水的水箱,请打印 NO。

否则在第一行打印 YES,并从第二行开始,按以下格式打印操作序列:

每行必须包含 3 个表示压缩操作的数字:“cnt x y”(1 ≤ cnt ≤ 109, 1 ≤ x, y ≤ N),其中 x 是我们取水的水箱的索引,y 是我们倒水的水箱的索引,cnt 是我们将水从水箱 x 传输到水箱 y 的次数。

这些行的数量不得超过 N + 5。

示例

输入 #1

2 3 5
2 3

输出 #1

YES
1 2 1

输入 #2

2 3 4
2 3

输出 #2

NO

输入 #3

5 2 0
1 3 5 7 9

输出 #3

YES
2 2 1
3 3 1
4 4 1
5 5 1