Задача A3. Полоса препятствий ≡

Условие

Одно из заданий на соревнованиях по подводной робототехнике — полоса препятствий. Полоса состоит из n подряд идущих стен, высота i-й стены h_i.

Цель робота — преодолеть все стены, достать флаг, который находится в конце полосы за всеми стенами, и вернуться обратно. Стену можно преодолеть двумя способами: подняться, проплыть над ней и опуститься обратно или сделать подкоп. Если стена была преодолена с помощью подкопа, то в при проходе в обратную сторону можно воспользоваться уже готовым подкопом. Всего разрешается сделать не более m подкопов.

Робот имеет ограниченный заряд батареи. Изначально он способен подняться над стеной высотой k или меньше, далее после каждого подъёма максимальная высота стены, которую может преодолеть робот, снижается на 1.

Робот поддерживает две команды: D — идти через подкоп (если подкопа ещё нет, то робот выкапывает его), U — проплыть над препятствием.

Формат входного файла

Первая строка входного файла содержит целые числа n m k. Следующая строка содержат n целых чисел h_i - высоты стен.

Формат выходного файла

Выходной файл должен содержать строку NO, если задание выполнить невозможно. В противном случае — две строки: строку YES и строку из 2n символов U и D — последовательность команд робота, которая позволит ему преодолеть полосу препятствий и вернуться обратно. Первые n символов содержат описание прохождение от стены с номером 1 до стены с номером n, следующие n символов содержат описание прохождения от стены с номером n до стены с номером 1.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ n, m ≤ 10⁵, 1 ≤ k, h_i ≤ 10⁹

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

10 5 10
10 1 4 2 4 3 4 4 8 9

YES
DUDUDUUUDDDDUUUDUDUD

5 1 1
5 5 5 5 5

NO

10 10 10000
13123 141323 213323 3213 213213 321 323213 1323 213 1232113

YES
DDDDDDDDDDDDDDDDDDDD