Чтобы содержать свое поле в идеальном состоянии, Пете необходимо иногда поливать его. Чтобы полить поле, Пете необходимо ровно V мл воды.
Также у Пети есть N емкостей, i-я первоначально заполнена на ai мл. Емкости достаточно большие и любая из них позволяет хранить в себе любой объем воды.
Чтобы переливать воду между емкостями, у Пети имеется ковш объемом K мл. Данным ковшом можно зачерпывать воду из одной емкости и выливать в какую-то емкость (нельзя зачерпнуть воду одновременно из нескольких емкостей, и выливать ее необходимо полностью). При этом зачерпнуть можно min(v, K), где v — текущий объем воды в выбранной емкости.
Можно ли с помощью данного ковша получить в одной из емкостей объем, строго равный V? Если возможно, выведите необходимую последовательность операций. Если способов получить искомый объем несколько — выведите любой.
Выходные данные
Если невозможно получить объем 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
|
YES
1 2 1
|
|
2
|
2 3 4
2 3
|
NO
|
|
3
|
5 2 0
1 3 5 7 9
|
YES
2 2 1
3 3 1
4 4 1
5 5 1
|