import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { enum Move { UL, UR, R, LR, LL, L } static void printList (List list) { for (Move m : list) { System.out.print(m + " "); } System.out.println(); } static boolean isInBound(int n, int i) { return !(i < 0 || i > n); } static void printShortestPath(int n, int i, int j, int k, int l) { int numMoves = 0; List moves = new ArrayList<>(); while(true) { if (!isInBound(n,i) || !isInBound(n,j) || !isInBound(n,k) || !isInBound(n,l)) { System.out.println("Impossible"); break; } if (i==k && j==l) { // done Collections.sort(moves); System.out.println(numMoves); printList(moves); break; } if (Math.abs(i-k) <= 1 && Math.abs(j-l) <= 1) { // right next to finish -> impossible System.out.println("Impossible"); break; } if (i == k) { // in same row if (j < l) { // if (i,j) ------ (k,l). Go Right. moves.add(Move.R); j+=2; } else { // if (k,l) ------ (i,j). Go Left. moves.add(Move.L); j-=2; } numMoves++; continue; } if (j == l) { // in same col // for these, you need to worry about going off the board // since you aren't going straight up or straight down! if (i>k) { // (i,j) above (k,l). Go Up. if (j >= 1) { // checking for bounds moves.add(Move.UL); i-=2; j-=1; } else { moves.add(Move.UR); i-=2; j+=1; } } else { // (i,j) is below (k,l). Go Down. if (j < n-1) { moves.add(Move.LR); i+=2; j+=1; } else { moves.add(Move.LL); i+=2; j-=1; } } numMoves++; continue; } if (i==k || j==l) throw new AssertionError(); if (i>k) { // go up if (j