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

when i run my code in my os it has no problem but when i run it in custom test in cf and give single even or odd integer above runtime happen is there any one can help me? this program is magic square for all kind of number

include <bits/stdc++.h>

using namespace std; const int maxn=1e3+100; int jadval[maxn][maxn]; bool used[maxn]; ////////////////////////////////////////////////////////// int** generate_odd_square(int n) { int value = 0; int squareSize = n * n; int c = n / 2, r = 0,i;

int** result = new int *[1000];

for(i=0;i<n;i++)
    result[i] = new int [1000];

while (++value <= squareSize) {
    result[r][c] = value;
    if (r == 0) {
        if (c == n - 1) {
            r++;
        } else {
            r = n - 1;
            c++;
        }
    } else if (c == n - 1) {
        r--;
        c = 0;
    } else if (result[r - 1][c + 1] == 0) {
        r--;

        c++;
    } else {
        r++;
    }
}
return result;

} ////////////////////////////////////////////// void generate_double_even_square(int n){ int counter=1; fill_n(used,n*n+100,true); for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ if (i>=0 and i<n/4 and j<n/4 and j>=0) jadval[i][j]=counter++; else if (i>=(n/4)*3 and i<=n and j>=0 and j<n/4) jadval[i][j]=counter++; else if (i>=(n/4)*3 and i<=n and j>=(n/4)*3 and j<=n) jadval[i][j]=counter++; else if (j>=(n/4)*3 and j<=n and i>=0 and i<n/4) jadval[i][j]=counter++; else if (j>=n/4 and j<(n/4)*3 and i>=n/4 and i<(n/4)*3) jadval[i][j]=counter++; else{ counter++; used[counter-1]=false; } } } counter=n*n; for (int i=0; i<n; i++) for (int j=0; j<n; j++){ if (used[counter]==true) counter--; else jadval[i][j]=counter--; } for (int i=0; i<n; i++){ for (int j=0; j<n; j++) cout<<jadval[i][j]<<" "; cout<<endl; } } ///////////////////////////////////////////////////////// int** generate_single_even_square(int n) {

int size = n * n;
int halfN = n / 2;
int zirmatricSize = size / 4, i;

int** zirmatric = generate_odd_square(halfN);
int gridFactors[] = {0, 2, 3, 1};
int** result = new int *[1000];

for(i=0;i<n;i++)
    result[i] = new int [1000];

for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
        int grid = (r / halfN) * 2 + (c / halfN);
        result[r][c] = zirmatric[r % halfN][c % halfN];
        result[r][c] += gridFactors[grid] * zirmatricSize;
    }
}

int nColsLeft = halfN / 2;
int nColsRight = nColsLeft - 1;

for (int r = 0; r < halfN; r++)
    for (int c = 0; c < n; c++) {
        if (c < nColsLeft || c >= n - nColsRight
                || (c == nColsLeft && r == nColsLeft)) {

            if (c == 0 && r == nColsLeft)
                continue;

            int tmp = result[r][c];
            result[r][c] = result[r + halfN][c];
            result[r + halfN][c] = tmp;
        }
    }

return result;

} int main(){ int n; cin>>n; if (n%2==1){ int **matrice=generate_odd_square(n); for (int i=0; i<n; i++){ for (int j=0; j<n; j++) cout<<matrice[i][j]<<" "; cout<<endl; } } else if (n%4==0) generate_double_even_square(n); else{ int **matrice=generate_single_even_square(n); for (int i=0; i<n; i++){ for (int j=0; j<n; j++) cout<<matrice[i][j]<<" "; cout<<endl; } } return 0; }