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