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 to find out for each query how many blocks are visited?

n <= 1e9
m <= 2 * 1e5
input 
6 5 
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