import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static point board[][]; static Set visited; static Map parent; static class point{ int x,y; String name; long dist; public point(int x,int y){ this.x=x; this.y=y; dist=-1; } public point(int x,int y,String name){ this.x=x; this.y=y; this.name=name; } } public static boolean isValid(point p,int n){ if(p.x>n-1||p.x<0||p.y>n-1||p.y<0) return false; return true; } public static Set getN(point p,int n){ Set res = new HashSet<>(); point UL = new point((p.x)-2,(p.y)-1); point L = new point((p.x),(p.y)-2); point R = new point((p.x),(p.y)+2); point UR = new point((p.x)-2,(p.y)+1); point LL = new point((p.x)+2,(p.y)-1); point LR = new point((p.x)+2,(p.y)+1); if(isValid(UL,n)){ board[UL.x][UL.y].name="UL"; res.add(board[UL.x][UL.y]); } if(isValid(L,n)){ board[L.x][L.y].name="L"; res.add(board[L.x][L.y]); } if(isValid(R,n)){ board[R.x][R.y].name="R"; res.add(board[R.x][R.y]); } if(isValid(UR,n)){ board[UL.x][UR.y].name="UR"; res.add(board[UL.x][UR.y]); } if(isValid(LL,n)){ board[LL.x][LL.y].name="LL"; res.add(board[LL.x][LL.y]); } if(isValid(LR,n)){ board[LR.x][LR.y].name="LR"; res.add(board[LR.x][LR.y]); } /*for(point i:res){ System.out.println(i.x+" "+i.y+" "); }*/ return res; } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. point src = board[i_start][j_start]; point dest = board[i_end][j_end]; src.name="src"; // int moves=0; boolean found=false; visited = new HashSet<>(); parent = new HashMap<>(); Queue q = new ArrayDeque<>(); src.dist=0; q.add(src); //visited.add(src); while(!q.isEmpty()){ point curr = q.poll(); // System.out.println("current is "+curr.x+" "+curr.y+" "); if(curr==dest){ found=true; System.out.println(curr.dist); printPath(src,curr); break; } visited.add(curr); for(point p:getN(curr,n)){ // System.out.println(p.x+" "+p.y+" "); if(!visited.contains(p)){ q.add(p); p.dist=curr.dist+1; parent.put(p,curr); visited.add(p); } } } if(found==false){ System.out.println("Impossible"); } } static void printPath(point x,point y){ point curr = parent.get(y); while(curr!=x){ System.out.print(curr.name+" "); curr=parent.get(curr); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); board = new point[n][n]; for(int i=0;i