#include <stdio.h>
#include <math.h>

#define NMAX 1000
char castigator(char matrice[][NMAX], int p, int q, int n_lin_col) {
    int i,j,n,ok,k;
    char x;
    n=n_lin_col;
    // varificare pe linii
    for (i=p; i<p+n; i++) {
        k=0;
        for (j=q; j<q+n-1; j++) {
            if (matrice[i][q]=='X' || matrice[i][q]=='0')
                x=matrice[i][q];
            else
                x = 'H';
            if (matrice[i][j+1]==x)
                k++;
            if (k==(n-1))
                return x;
        }
    }
    // verificare pe coloane
    for (j=q; j<q+n; j++) {
        k=0;
        for (i=p; i<p+n-1; i++) {
           if (matrice[p][j]=='X' || matrice[p][j]=='0')
                x=matrice[p][j];
           else
               x='H';
            if (matrice[i+1][j]==x)
                k++;
            if (k==(n-1))
                return x;
        }
    }
    // verificare diagonala principala
    k=0;
    if (matrice[p][q]=='X' || matrice[p][q]=='0') {
        x = matrice[p][q];
    }
    else {
        x='H';
    }
    for (i=0; i<n; i++) {
        if (matrice[p+i][q+i]==x)
            k++;
        if (k==n)
            return x;
    }
    /*k=0;
    if (matrice[p][q]=='X' || matrice[p][q]=='0') {
        x = matrice[p][q];
    }
    else {
        x='H';
    }
    for (i=p; i< p+n; i++) {
        for (j = q; j < q + n; j++) {
            if (i==j) {
                if (x == matrice[i][j]) {
                    k++;
                }
            }
            if (k == n) {
                return x;
            }
        }
    } */ // incercare nereuista
    // verificare diagonala secundara
    k=0;
    if (matrice[p][q+n-1]=='X' || matrice[p][q+n-1]=='0')
        x=matrice[p][q+n-1];
    else
        x='H';
    for (i=0; i<n; i++) {
        if (x==matrice[p+i][q+n-1-i])
        {
            k++;
        }
        if (k==n)
            return x;
    }
    /* k=0;
    if (matrice[p][q+n-1]=='X' || matrice[p][q+n-1]=='0')
        x=matrice[p][q+n-1];
    else
        x='H';
    for (i=p; i<p+n; i++) {
        for(j=q; j<q+n; j++) {
            if (j==(q+n)-1-i) {
                if (matrice[i][j]==x)
                    k++;
            }
            if (k==n)
                return x;
        }
    } */ //incercare esuata
    return '-';

}

void afisare_mini_matrice(char matrice[][NMAX], int p, int q, int n_lin_col) {
    int i,j,n;
    n=n_lin_col;
    for (i=p; i<p+n; i++) {
        for (j = q; j < q + n; j++) {
            printf(" %c", matrice[i][j]);
        }
        printf("\n");
    }
}

void minimatrice(char matrice[][NMAX], int n_lin_col, char v[NMAX]) {
    int p,q,n,k;
    // char x;
    p=0;
    q=0;
    n=n_lin_col;
    k=0;
    while (p < (n * n - n + 1)) {
        v[k]=castigator(matrice,p,q,n);
        k++;
       // printf("############ \n"); // TODO de facut contor pt vectorul cu castigatori
       //x=castigator(matrice,p,q,n);
       // printf(" %c", x);
        q = q + n;
        if (q > (n * n - n + 1)) {
            q = 0;
            p = p + n;
        }
    }

}

void verificare(char matrice[][NMAX], int n_lin_col) {
    int i,j,p=0,q=0,n, eror=0;
    int v[NMAX];
    n=n_lin_col;

    for (i=p; i < (p+n); i++) {
        for (j = q; j < (q + n); j++) {
            // functie castig
            printf("%c ", matrice[i][j]);
            // v[p+1/n][(q+1/n)] = functie castig;
            if (j == n * n - 1)
                eror = 1;
        }
        printf("\n");
        if (i == (p + n - 1) && eror == 0) {
            q = q + n;
            i = p;
        }
        if (i == (p + n - 1) && eror == 1) {
            p = p + n;
            i = p;
            q=0;
            eror = 0;
        }
        if (i == (n * n - 1) && eror == 1)
            break;

//        if (i==n*n-1)
//            break;
//        if (i==p+n-1)
//           p=p+n;

    }
}

void robin(char matrice[][NMAX], char jucator, int n_lin_col) {
    int i, control = 0, k;
    for (i = 0; i < n_lin_col; i++) {
        if ((matrice[i][i] != 'X') && matrice[i][i] != '0') {
            matrice[i][i] = jucator;
            control = 1;
            break;
        }
    }
    k = 1;
    while (control == 0) {
        for (i = 0; i < n_lin_col - k; i++) {
            if ((matrice[i][i + k] != 'X') && matrice[i][i + k] != '0') {
                matrice[i][i + k] = jucator;
                control = 1;
                break;
            }
        }
        if (control != 1) {
            for (i = 0; i < n_lin_col - k; i++) {
                if ((matrice[i + k][i] != 'X') && matrice[i + k][i] != '0') {
                    matrice[i + k][i] = jucator;
                    control = 1;
                    break;
                }
            }
        }
        k++;
    }
}

void incarcare_matrice(char matrice[][NMAX], int n_lin_col) {
    int i, j;
    for (i = 0; i < pow(n_lin_col, 2); i++)
        for (j = 0; j < pow(n_lin_col, 2); j++)
            matrice[i][j] = '*';
}

void afisare_matrice(char matrice[][NMAX], int n_lin_col) {
    int i, j;
    for (i = 0; i < pow(n_lin_col, 2); i++) {
        for (j = 0; j < pow(n_lin_col, 2); j++) {
            printf("%c ", matrice[i][j]);
        }
        printf("\n");
    }
}

void mutari(char matrice[][NMAX], int numar_mutari, int n_lin_col, char v[NMAX]) {
    int n = n_lin_col * n_lin_col, fullboard = 0;
    int i, x, y, erorr, k=1;
    char jucator;
    for (i = 1; i <= numar_mutari; i++) {
        if (k > n * n) {
            fullboard = 1;
            scanf(" %c %d %d", &jucator, &x, &y);
        } else {
            erorr = 0;
            scanf(" %c %d %d", &jucator, &x, &y);
            k++;
            if (i % 2 == 1 && jucator == 'X') {
                if (matrice[x][y] == 'X' || matrice[x][y] == '0') {
                    printf("NOT AN EMPTY CELL \n");
                    robin(matrice, jucator, n);
                } else {
                    if ((x < 0 || x >= n) || (y < 0 || y >= n)) {
                        printf("INVALID INDEX \n");
                        robin(matrice, jucator, n);
                    } else
                        matrice[x][y] = 'X';
                }
            }

            if (i % 2 == 1 && jucator != 'X') {
                printf("NOT YOUR TURN \n");
                erorr = 1;
            }

            if (i % 2 == 0 && jucator == '0') {
                if (matrice[x][y] == 'X' || matrice[x][y] == '0') {
                    printf("NOT AN EMPTY CELL \n");
                    robin(matrice, jucator, n);
                } else {
                    if ((x < 0 || x >= n) || (y < 0 || y >= n)) {
                        printf("INVALID INDEX \n");
                        robin(matrice, jucator, n);
                    } else
                        matrice[x][y] = '0';
                }
            }

            if (i % 2 == 0 && jucator != '0') {
                printf("NOT YOUR TURN \n");
                erorr = 1;
            }
            if (erorr == 1) {
                i++;
                numar_mutari++;
            }
            minimatrice(matrice, n_lin_col, v);
        }
    }
    if (fullboard == 1 )
        printf("Fullboard \n");
}

int main() {
    char c[NMAX][NMAX];
    char v[NMAX];
    int n, m, k;
    scanf("%d", &n);
    scanf("%d", &m);
    incarcare_matrice(c, n);
    mutari(c, m, n, v);
    printf("################## S U C C E S ################## \n");
    for (k=0; k<n*n; k++) {
        printf("%c ", v[k]);
        if ((k+1)%n==0)
            printf("\n");
    }
    afisare_matrice(c, n);

    return 0;
}