После очередного праздника у Никиты на кухне образовалась стопка грязных тарелок. Их надо помыть и поставить в сушилку, при этом в сушилке тарелки тоже должны стоять в стопке, причем размеры тарелок должны возрастать сверху вниз. Все размеры тарелок различны.
У Никиты не очень много свободного места, а именно, есть место только для еще одной стопки тарелок. Поэтому он может выполнять лишь две операции:
- Взять любое количество от 1 до a верхних тарелок из стопки с грязными тарелками, помыть их и положить в том же порядке на верх промежуточной стопки.
- Взять любое количество от 1 до b верхних тарелок из промежуточной стопки и положить в том же порядке на верх стопки в сушилке.
Обратите внимание, что при выполнении любой из операций тарелки кладутся на стопку в том же порядке, в каком они были перед выполнением операции.
Вам известны размеры тарелок s1, s2, ..., sn в порядке их лежания в стопке с грязными тарелками сверху вниз, а также числа a и b. Все размеры тарелок различны. Напишите программу, которая будет определять, может ли Никита расположить все тарелки в сушилке в возрастающем сверху вниз порядке, и если может, то найдите какой-нибудь, не обязательно оптимальный, порядок действий для этого.
Выходные данные
В первую строку выведите «YES», если решение существует. В этом случае во вторую строку выведите k — количество операций. Далее в k строках выведите сами операции по одной в строке. Каждая из них описывается двумя числами tj, cj, где tj = 1, если операция соответствует помывке cj тарелок и помещению их в промежуточную стопку, и tj = 2, если операция описывает перемещение cj тарелок из промежуточной стопки в сушилку. Если решений несколько, то выведите любое из них. Будьте внимательны: в задаче не требуется минимизировать количество операций.
Если решения не существует, то в единственную строку выведите «NO».
Примечание
В первом примере изначально тарелки были в порядке 2, 3, 6, 4, 1, 5. Рассмотрим то, что получалось после каждой операции:
- [1 2]: Грязная стопка: 6, 4, 1, 5. Промежуточная стопка: 2, 3. В сушилке пусто.
- [1 1]: Грязная стопка: 4, 1, 5. Промежуточная стопка: 6, 2, 3. В сушилке пусто.
- [2 1]: Грязная стопка: 4, 1, 5. Промежуточная стопка: 2, 3. Сушилка: 6.
- [1 2]: Грязная стопка: 5. Промежуточная стопка: 4, 1, 2, 3. Сушилка: 6.
- [1 1]: Грязных тарелок нет. Промежуточная стопка: 5, 4, 1, 2, 3. Сушилка: 6.
- [2 1]: Грязных тарелок нет. Промежуточная стопка: 4, 1, 2, 3. Сушилка: 5, 6.
- [2 1]: Грязных тарелок нет. Промежуточная стопка: 1, 2, 3. Сушилка: 4, 5, 6.
- [2 3]: Все тарелки в сушилке: 1, 2, 3, 4, 5, 6.
Во втором примере можно помыть сразу все тарелки и затем все вместе переставить в сушилку.
В третьем примере так сделать нельзя, т. к. нельзя переставлять более одной тарелки одновременно. Можно помыть все тарелки по одной, тогда в промежуточной стопке они будут в обратном порядке, а затем переставить все тарелки по одной. В итоге порядок в сушилке будет правильный.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2 3
2 3 6 4 1 5
|
YES
8
1 2
1 1
2 1
1 2
1 1
2 1
2 1
2 3
|
|
2
|
7 7 7
1 2 3 4 5 6 7
|
YES
2
1 7
2 7
|
|
3
|
7 1 1
1 2 3 4 5 6 7
|
YES
14
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
|
|
4
|
4 2 2
3 2 1 4
|
NO
|