Rotating Odd-Order Submatrix

Scarlet has learned an interesting array magic. Given an n \times n matrix filled with integers from 1 to \(n^2\) in row-major order, she performs a sequence of magic operations. In each operation, she selects an odd-order square submatrix of size \(k\) (with \(k\) being an odd integer) starting at position \((r, c)\) (1-indexed) and rotates it by \(90^\circ\) either clockwise or anticlockwise.

The rotation formulas are as follows:

• Clockwise: \( new[i][j] = original[k-1-j][i] \).
• Anticlockwise: \( new[i][j] = original[j][k-1-i] \).

Your task is to output the final matrix after performing all the magic operations.

inputFormat

The first line contains an integer \(n\), which represents the dimension of the matrix.

The second line contains an integer \(m\), the number of magic operations.

Each of the following \(m\) lines contains four values in the format:

r c k d

where:

• \(r\) and \(c\) denote the starting row and column (1-indexed) of the submatrix,
• \(k\) is the odd size of the submatrix,
• \(d\) is a character that is either 'C' (for clockwise) or 'A' (for anticlockwise).

outputFormat

Output the final state of the matrix after performing all operations.

Each line represents a row of the matrix, with numbers separated by a single space.

sample

3
1
1 1 3 C

7 4 1
8 5 2
9 6 3