Жавхар --- лінивий кіт
Обмеження: 2 сек., 256 МіБ
Жавхар — кіт. Не просто кіт, а лінивий кіт.
У домі Жавхара є робот-порохотяг, якого кіт використовує як транспортний засіб.
Кімната, у якій перебуває кіт, є прямокутником з висотою \(h\) клітинок та шириною \(w\) клітинок. Кіт хоче, починаючи з будь-якої клітинки кімнати, зробити собі екскурсію кімнатою та повернутися у початкову клітинку. Обов’язкова умова — побувати в кожній клітинці кімнати рівно один раз (за винятком початкової, у якій кіт побуває двічі).
Робот вміє робити наступне:
Поїхати на одну клітинку вверх (команда
U).Поїхати на одну клітинку вправо (команда
R).Поїхати на одну клітинку вниз (команда
D).Поїхати на одну клітинку вліво (команда
L).
Скажіть, будь ласка, чи здійсненна мрія кота-Жавхара. А якщо так — виведіть клітинку, з якої може почати робот-порохотяг, та його маршрут по кімнаті.
Вхідні дані
У першому рядку задано два цілі числа \(h\) та \(w\) — розміри кімнати, у якій перебуває кіт-Жавхар.
Вихідні дані
Якщо мрія кота-Жавхара нездійсненна — виведіть -1.
Якщо ж мрія кота може здійснитися, то в першому рядку виведіть два
цілі числа \(r\) та \(c\) — номери рядка та стовпця клітинки, з
якої робот буде починати свій маршрут. У другому рядку виведіть можливий
маршрут робота-порохотяга — рядок довжини \(h*w\), який складається із символів
U, R, D, L.
Обмеження
\(1 < h * w \le 10^5\),
\(1 \le r \le h\),
\(1 \le c \le w\).
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 4 4 | 4 3 RULLURRULLLDDDRR |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 2 3 | 2 3 LLURRD |
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|