| Codeforces Beta Round 71 |
|---|
| Закончено |
Наконец лиса Кейл вернулась в свой замок. Однако, что-то не так с системой безопасности замка: сенсоры системы безопасности реагируют на хозяйку!
В настоящий момент лиса находится в точке (1, 1) замка и хочет переместиться в точку (n, n), где находится ее спальня. За один ход Кейл может переместиться из точки (x, y) либо в точку (x + 1, y) (направо) либо в точку (x, y + 1) (вверх).
Всего в ее замке установлено c2 сенсоров, которые расположены в точках (a + i, b + j) (для всех целых i и j таких что: 0 ≤ i < c, 0 ≤ j < c).
Каждый сенсор хранит в себе счетчик и уменьшает его каждый раз при передвижении Кейл. В начале счетчик на каждом сенсоре равен t. Каждый раз, когда Кейл перемещается в точку (x, y), значение счетчика в сенсоре (u, v) уменьшается на (|u - x| + |v - y|). Когда хотя бы один счетчик достигает отрицательного значения, срабатывает система перехвата.
Определите, может ли Кейл переместиться из (1, 1) в (n, n) так, что система перехвата не будет задействована. Если это возможно, выведите ее путь. Лиса может перемещаться в точку замка, даже если в этой точке установлен сенсор.
Первая строка содержит пять целых чисел n, t, a, b, c (2 ≤ n ≤ 2·105, 0 ≤ t ≤ 1014, 1 ≤ a ≤ n - c + 1, 1 ≤ b ≤ n - c + 1, 1 ≤ c ≤ n).
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout (также вы можете использовать спецификатор %I64d).
Если цель Кейл выполнима, то выведите в первую строку 2n - 2 символа, которые кодируют ее возможный путь, i-ый символ в пути равен R если i-ый шаг она сделала, переместившись направо, если она переместилась вверх, то выведите символ U. Если возможных путей несколько, то выведите лексикографически минимальный. Учтите, что символ R лексикографически меньше символа U.
Если пути не существует, то выведите Impossible.
5 25 2 4 1
RRUURURU
3 6 1 2 2
URUR
3 5 1 2 2
Impossible
20 492 11 4 8
RRRRRRRRRRRRRRRRUUUUURUUUUURRUUUUUUUUU
Пути для примеров 1 и 2 показаны на рисунках:
