import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static StringBuilder ans = new StringBuilder(); static int n; static int printShortestPath(int n, int sx, int sy, int ex, int ey) { if(impos(sx,sy,ex,ey)) return -1; int dt = md(sx,sy,ex,ey); int kdt=dt; while(kdt!=0) { kdt--; if(valid(sx-2,sy-1) && md(sx-2,sy-1,ex,ey)==kdt) { sx=sx-2; sy--; ans.append("UL "); } else if(valid(sx-2,sy+1) && md(sx-2,sy+1,ex,ey)==kdt) { sx=sx-2; sy++; ans.append("UR "); } else if(valid(sx,sy+2) && md(sx,sy+2,ex,ey)==kdt) { sy=sy+2; ans.append("R "); } else if(valid(sx+2,sy+1) && md(sx+2,sy+1,ex,ey)==kdt) { sx=sx+2; sy++; ans.append("LR "); } else if(valid(sx+2,sy-1) && md(sx+2,sy-1,ex,ey)==kdt) { sx=sx+2; sy--; ans.append("LL "); } else if(valid(sx,sy-2) && md(sx,sy-2,ex,ey)==kdt) { sy=sy-2; ans.append("L "); } } return dt; } static int md(int sx, int sy, int ex, int ey) { int dx=Math.abs(sx-ex); int dy=Math.abs(sy-ey); if(dx==0) return dy/2; int k=dx/2; if(k>=dy) return k; else return (dy-k)/2+k; } static boolean impos(int sx, int sy, int ex, int ey) { if(Math.abs(sx-ex)%2==1 || (Math.abs(sx-ex)%4==0 && Math.abs(sy-ey)%2==1) || (Math.abs(sx-ex)%4==2 && Math.abs(sy-ey)%2==0)) return true; else return false; } static boolean valid(int i,int j) { return (i>=0 && i=0 && j