Given n*n matrix with m query, standing in one of sub-diameter block in the matrix and each step can go only up or left(according to given direction) until you reached a block which visited earlier. what is the best algorithm? n <= 1e9 m <= 2 * 1e5 input \n 6 5 \n 3 4 U 6 1 L 2 5 L 1 6 U 4 3 U output 4 3 2 1 2

input 10 6 2 9 U 10 1 U 1 10 U 8 3 L 10 1 L 6 5 U output 9 1 10 6 0 2