// Author: Tulba-Lecu Theodor Gabriel
// Student at Politehnica Universiy of Bucharest, group 311CA
// Email: gabi_tulba_lecu@yahoo.com
// Task: star_dust

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// free a dinamically allocated 2D array
void free_matrix(int rows, int **mat) {
    for (int i = 0; i < rows; i++) {
        free(mat[i]);
    }

    free(mat);
}

// swap the values of two bytes
void swap_bytes(char *a, char *b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

// read until a letter is found
void read_alpha(char *a) {
    *a = 0;

    while (!isalpha(*a)) {
        scanf("%c", a);
    }
}

// check if a coordinate is inside the matrix
int in_bounds(int x, int y, int x_max, int *v) {
    if (x < 0 || x >= x_max)
        return 0;
    if (y < 0 || y >= 4 * v[x])
        return 0;

    return 1;
}

// allocate and read the initial matrix
void read(int *n_addr, int **v_addr, int ***mat_addr) {
    int n;
    int *v = NULL;
    int **mat = NULL;

    // read the number of rows
    scanf("%d", &n);

    // allocate the row length array
    v = (int *) malloc(n * sizeof(int));
    if (v == NULL) {
        printf("Error! Unable to allocate memory.\n");
        exit(1);
    }

    // allocate the matrix's rows
    mat = (int **) malloc(n * sizeof(int *));
    if (mat == NULL) {
        free(v);

        printf("Error! Unable to allocate memory.\n");

        exit(1);
    }

    for (int i = 0; i < n; i++) {
        // read the length of the i-th row
        scanf("%d", &v[i]);

        // allocate the matrix's i-th row
        mat[i] = (int *) malloc(v[i] * sizeof(int));
        if (mat[i] == NULL) {
            printf("Error! Unable to allocate memory.\n");
            free_matrix(i, mat);
            free(v);

            exit(1);
        }

        // read the i-th row
        for (int j = 0; j < v[i]; j++) {
            scanf("%x", &mat[i][j]);
        }
    }

    // pass the read input
    *n_addr = n;
    *v_addr = v;
    *mat_addr = mat;
}

// solve the first task
void solve_task1(int n, int *v, int **mat) {
    printf("task 1\n");

    int total = 0;
    int score = 0;
    double mean = 0.0;

    // add the bytes on the frist row
    for (int i = 0; i < 4 * v[0]; i++) {
            score += ((char *) mat[0])[i];
            total++;
    }

    // add the first and last bytes of each row from 1 to n-1
    for (int i = 1; i < n - 1; i++) {
        if (v[i] > 0) {
            score += ((char *) mat[i])[0];
            score += ((char *) mat[i])[4 * v[i] - 1];
            total += 2;
        }
    }

    // add the bytes on the last row
    for (int i = 0; i < 4 * v[n - 1]; i++) {
            score += ((char *) mat[n - 1])[i];
            total++;
    }

    // calculate the arithmetic mean
    mean = (double) score / (double) total;

    printf("%.10f\n", mean);
}

// read an update for the second task
void read_update(char *op, char *type, int *row, int *index, int *value) {
    *value = 0;

    read_alpha(op);
    read_alpha(type);

    scanf("%d", row);
    scanf("%d", index);

    if (*op == 'M') {
        scanf("%x", value);
    }
}

// apply a modify update on the matrix
void modify(int n, int *v, int **mat, int row, char type, int idx, int val) {
    int int_block_index;

    // get the int block in which the modification will take place
    switch (type) {
        case 'I':
            int_block_index = idx;
            break;

        case 'S':
            int_block_index = idx / 2;
            break;

        case 'C':
            int_block_index = idx / 4;
            break;
    }

    // if the block is outside the allocated memory of the row, extend the row
    if (int_block_index >= v[row]) {
        int *p = realloc(mat[row], (int_block_index + 1) * sizeof(int));
        if (p == NULL) {
            printf("Error! Unable to reallocate memory.\n");

            free_matrix(n, mat);
            free(v);

            exit(1);
        }

        mat[row] = p;
        // set the newly allocated memory to 0
        for (int i = v[row]; i <= int_block_index; i++) {
            mat[row][i] = 0;
        }

        // remember the new length of the array
        v[row] = int_block_index + 1;
    }

    // based on the type of modification, set the memory to new value
    // for simplicty for the 'S' and 'C' types the row is casted to
    // short int and char respectively
    switch (type) {
        case 'I':
            mat[row][idx] = val;
            break;

        case 'S':
            ((short int *)mat[row])[idx] = (short int) val;
            break;

        case 'C':
            ((char *)mat[row])[idx] = (char) val;
            break;
    }
}

// swap the order of the bytes of a int/short int
void swap_order(int *v, char type, int index) {
    short int *v_short = (short int *) v;
    char *byte_arr = NULL;

    switch (type) {
        case 'I':
            byte_arr = (char *) &v[index];
            swap_bytes(&byte_arr[0], &byte_arr[3]);
            swap_bytes(&byte_arr[1], &byte_arr[2]);

            break;

        case 'S':
            byte_arr = (char *) &v_short[index];
            swap_bytes(&byte_arr[0], &byte_arr[1]);

            break;
    }
}

// solve the second task
void solve_task2(int n, int *v, int **mat) {
    int k, row, index, value;
    char op, type;

    printf("task 2\n");

    // read the number of updates
    scanf("%d", &k);

    for (int i = 0; i < k; i++) {
        read_update(&op, &type, &row, &index, &value);

        switch (op) {
            case 'M':
                modify(n, v, mat, row, type, index - 1, value);
                break;

            case 'D':
                // the delete operation is equivalent to modify with value = 0
                modify(n, v, mat, row, type, index - 1, 0);
                break;

            case 'S':
                swap_order(mat[row], type, index);
                break;
        }
    }

    // print the matrix after all the updates
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < v[i]; j++) {
            printf("%08X ", mat[i][j]);
        }
        printf("\n");
    }
}

// do a depth first search on the matrix to get the size of the component
int dfs(int n, int *v, char **mat, int x, int y, int **found) {
    int size = 0, next_x, next_y;
    // direction arrays
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    // set this cell as visited
    found[x][y] = 1;

    for (int i = 0; i < 4; i++) {
        next_x = x + dx[i];
        next_y = y + dy[i];
        // if the neighbour cell is inside the matrix and it wasn't
        // previously visited and the cell is 0, do a dfs on that cell
        if (in_bounds(next_x, next_y, n, v)) {
            if (!found[next_x][next_y] && mat[next_x][next_y] == 0) {
                    size += dfs(n, v, mat, next_x, next_y, found);
            }
        }
    }

    return size + 1;
}

// solve the third task
void solve_task3(int n, int *v, int **mat) {
    int max = 0, max_pos_x = -1, max_pos_y = -1;
    int **found = NULL;

    // allocate the visited cells matrix
    found = (int **) calloc(n, sizeof(int *));
    if (found == NULL) {
        printf("Error! Unable to allocate memory.\n");
        free_matrix(n, mat);
        free(v);

        exit(1);
    }

    for (int i = 0; i < n; i++) {
        found[i] = (int *) calloc(4 * v[i], sizeof(int));
        if (found[i] == NULL) {
            printf("Error! Unable to allocate memory.\n");
            free_matrix(i, found);
            free_matrix(n, mat);
            free(v);

            exit(1);
        }
    }

    for (int i = 0; i < n; i++) {
       for (int j = 0; j < 4 * v[i]; j++) {
           // if a new unvisited 0 cell is found get it's component size
           if (!found[i][j] && ((char *) mat[i])[j] == 0) {
               int size = dfs(n, v, (char **) mat, i, j, found);
               // it the current component size is bigger than the biggest
               // component, remember it as the best answer yet
               if (size > max) {
                   max = size;
                   max_pos_x = i;
                   max_pos_y = j;
               }
           }
       }
    }

    printf("task 3\n%d %d %d\n", max_pos_x, max_pos_y, max);

    // free allocated memory
    free_matrix(n, found);
}

int main() {
    int n; // number of rows
    int *row_width = NULL; // the array of row lengths
    int **map = NULL; // the matrix

    // read initial matrix
    read(&n, &row_width, &map);

    // solve tasks
    solve_task1(n, row_width, map);
    solve_task2(n, row_width, map);
    solve_task3(n, row_width, map);

    // free allocated memory
    free_matrix(n, map);
    free(row_width);

    return 0;
}