Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Грязные тарелки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После очередного праздника у Никиты на кухне образовалась стопка грязных тарелок. Их надо помыть и поставить в сушилку, при этом в сушилке тарелки тоже должны стоять в стопке, причем размеры тарелок должны возрастать сверху вниз. Все размеры тарелок различны.

У Никиты не очень много свободного места, а именно, есть место только для еще одной стопки тарелок. Поэтому он может выполнять лишь две операции:

  • Взять любое количество от 1 до a верхних тарелок из стопки с грязными тарелками, помыть их и положить в том же порядке на верх промежуточной стопки.
  • Взять любое количество от 1 до b верхних тарелок из промежуточной стопки и положить в том же порядке на верх стопки в сушилке.

Обратите внимание, что при выполнении любой из операций тарелки кладутся на стопку в том же порядке, в каком они были перед выполнением операции.

Вам известны размеры тарелок s1, s2, ..., sn в порядке их лежания в стопке с грязными тарелками сверху вниз, а также числа a и b. Все размеры тарелок различны. Напишите программу, которая будет определять, может ли Никита расположить все тарелки в сушилке в возрастающем сверху вниз порядке, и если может, то найдите какой-нибудь, не обязательно оптимальный, порядок действий для этого.

Входные данные

В первой строке записаны три целых числа n, a и b (1 ≤ n ≤ 2000, 1 ≤ a, b ≤ n). Вторая строка содержит последовательность целых чисел s1, s2, ..., sn (1 ≤ si ≤ n) — размеры тарелок в порядке их следования сверху вниз. Все размеры различны.

Выходные данные

В первую строку выведите «YES», если решение существует. В этом случае во вторую строку выведите k — количество операций. Далее в k строках выведите сами операции по одной в строке. Каждая из них описывается двумя числами tj, cj, где tj = 1, если операция соответствует помывке cj тарелок и помещению их в промежуточную стопку, и tj = 2, если операция описывает перемещение cj тарелок из промежуточной стопки в сушилку. Если решений несколько, то выведите любое из них. Будьте внимательны: в задаче не требуется минимизировать количество операций.

Если решения не существует, то в единственную строку выведите «NO».

Примеры
Входные данные
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
Входные данные
7 7 7
1 2 3 4 5 6 7
Выходные данные
YES
2
1 7
2 7
Входные данные
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 2 2
3 2 1 4
Выходные данные
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.

Во втором примере можно помыть сразу все тарелки и затем все вместе переставить в сушилку.

В третьем примере так сделать нельзя, т. к. нельзя переставлять более одной тарелки одновременно. Можно помыть все тарелки по одной, тогда в промежуточной стопке они будут в обратном порядке, а затем переставить все тарелки по одной. В итоге порядок в сушилке будет правильный.