const SIDE_LEN: usize = 5; const DIFFS: [(usize, usize, char); 4] = [(!0, 0, 'U'), (0, !0, 'L'), (0, 1, 'R'), (1, 0, 'D')]; fn main() { let t = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.trim().parse::().unwrap() }; let dfs = |self_coord: (usize, usize), ghost_coord: (usize, usize)| { let mut stack = vec![(self_coord, vec![])]; while let Some((cur_self_coord, cur_move)) = stack.pop() { if cur_move.len() == 3 { if !is_checkmate(cur_self_coord, ghost_coord) { return Some((cur_self_coord, cur_move)); } else { continue; } } let (cur_self_x, cur_self_y) = cur_self_coord; for &(diff_x, diff_y, dir) in &DIFFS { let next_self_x = cur_self_x.wrapping_add(diff_x); let next_self_y = cur_self_y.wrapping_add(diff_y); if next_self_x >= SIDE_LEN || next_self_y >= SIDE_LEN { continue; } let next_self_coord = (next_self_x, next_self_y); if !is_found(next_self_coord, ghost_coord) { let mut next_move = cur_move.clone(); next_move.push(dir); stack.push((next_self_coord, next_move)); } } } None }; let mut history = ['R', 'L', 'R'].to_vec(); let mut prev_coord = (0, 0); let mut cur_coord = (0_usize, 1_usize); while history.len() < 1_000_000 { let (cur_x, cur_y) = cur_coord; for (diff_x, diff_y, dir) in DIFFS { let next_x = cur_x.wrapping_add(diff_x); let next_y = cur_y.wrapping_add(diff_y); if next_x >= SIDE_LEN || next_y >= SIDE_LEN { continue; } let next_coord = (next_x, next_y); if !is_found(next_coord, prev_coord) { if let Some((moved_coord, mut move_log)) = dfs(next_coord, prev_coord) { prev_coord = next_coord; cur_coord = moved_coord; history.push(dir); history.append(&mut move_log); break; } } } } let ans: String = history.iter().take(t).collect(); println!("{}", ans); } fn is_corner(coord: (usize, usize)) -> bool { let (x, y) = coord; (x == 0 || x == SIDE_LEN - 1) && (y == 0 || y == SIDE_LEN - 1) } fn abs_diff(x: usize, y: usize) -> usize { if x >= y { x - y } else { y - x } } fn check_diagonally_adjacent(coord1: (usize, usize), coord2: (usize, usize)) -> bool { let (x1, y1) = coord1; let (x2, y2) = coord2; abs_diff(x1, x2) == 1 && abs_diff(y1, y2) == 1 } fn is_checkmate(this_coord: (usize, usize), ghost_coord: (usize, usize)) -> bool { is_corner(this_coord) && check_diagonally_adjacent(this_coord, ghost_coord) } fn is_found(this_coord: (usize, usize), ghost_coord: (usize, usize)) -> bool { this_coord.0 == ghost_coord.0 || this_coord.1 == ghost_coord.1 }