Жавхар --- лінивий кіт
Limits: 2 sec., 256 MiB
Жавхар — кіт. Не просто кіт, а лінивий кіт.
У домі Жавхара є робот-порохотяг, якого кіт використовує як транспортний засіб.
Кімната, у якій перебуває кіт, є прямокутником з висотою \(h\) клітинок та шириною \(w\) клітинок. Кіт хоче, починаючи з будь-якої клітинки кімнати, зробити собі екскурсію кімнатою та повернутися у початкову клітинку. Обов’язкова умова — побувати в кожній клітинці кімнати рівно один раз (за винятком початкової, у якій кіт побуває двічі).
Робот вміє робити наступне:
Поїхати на одну клітинку вверх (команда
U).Поїхати на одну клітинку вправо (команда
R).Поїхати на одну клітинку вниз (команда
D).Поїхати на одну клітинку вліво (команда
L).
Скажіть, будь ласка, чи здійсненна мрія кота-Жавхара. А якщо так — виведіть клітинку, з якої може почати робот-порохотяг, та його маршрут по кімнаті.
Input
У першому рядку задано два цілі числа \(h\) та \(w\) — розміри кімнати, у якій перебуває кіт-Жавхар.
Output
Якщо мрія кота-Жавхара нездійсненна — виведіть -1.
Якщо ж мрія кота може здійснитися, то в першому рядку виведіть два
цілі числа \(r\) та \(c\) — номери рядка та стовпця клітинки, з
якої робот буде починати свій маршрут. У другому рядку виведіть можливий
маршрут робота-порохотяга — рядок довжини \(h*w\), який складається із символів
U, R, D, L.
Constraints
\(1 < h * w \le 10^5\),
\(1 \le r \le h\),
\(1 \le c \le w\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 4 | 4 3 RULLURRULLLDDDRR |
| Input (stdin) | Output (stdout) |
|---|---|
| 2 3 | 2 3 LLURRD |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|