Matrix Transformations (APCS 2016-03 Intermediate)

A matrix arranges elements in a rectangle. Its horizontal lines are rows and its vertical lines are columns. We write \(X_{i,j}\) for the element in row \(i\), column \(j\) of matrix \(X\). For example, \(X_{3,2}=6\) in Figure 1.

We define two matrix operations:

• Flip: exchange the first and last rows, the second and second-to-last rows, and so on.
• Rotate: rotate the entire matrix \(90\) degrees clockwise.

Figure 1 shows that flipping \(X\) produces \(Y\), and then rotating \(Y\) produces \(Z\).

A sequence of flips and rotations transforms an original matrix \(A\) into a new matrix \(B\). In Figure 2, \(A\) is flipped and then rotated twice to obtain \(B\).

You are given the final matrix \(B\) and the operations that were originally applied to \(A\), in their original order. Recover matrix \(A\).

Input

The first line contains three integers \(R\), \(C\), and \(M\): the number of rows of \(B\), the number of columns of \(B\), and the number of operations.

The next \(R\) lines each contain \(C\) integers. The \(j\)-th integer on the \(i\)-th line is \(B_{i,j}\).

The last line contains \(M\) integers \(m_1,m_2,\ldots,m_M\), describing the operations originally applied to \(A\) in order:

• \(m_k=0\): rotate \(90\) degrees clockwise.
• \(m_k=1\): flip vertically by reversing the order of the rows.

Constraints

• \(1 \le R,C,M \le 10\)
• \(0 \le B_{i,j} \le 9\)
• \(m_k\in\{0,1\}\)
• All input values are integers.

Output

On the first line, print two integers \(R'\) and \(C'\), the number of rows and columns of the original matrix \(A\).

Then print the \(R'\) rows of \(A\), with \(C'\) integers on each row. Separate adjacent integers by exactly one space and do not print a trailing space at the end of a row.

This problem uses strict output comparison, so follow the required format exactly.

Scoring

The two sample cases are judged but worth 0 points. There are exactly \(20\) scored groups worth \(5\) points each:

• In \(6\) groups (\(30\) points), every operation is a flip.
• The remaining \(14\) groups (\(70\) points) have no additional constraints.

Sample Input 1

3 2 3
1 1
3 1
1 2
1 0 0

Sample Output 1

3 2
1 1
1 3
2 1

Sample Explanation 1

The transformation is shown in Figure 2.

Sample Input 2

3 2 2
3 3
2 1
1 2
0 1

Sample Output 2

2 3
2 1 3
1 2 3

Sample Explanation 2

To recover the original matrix, undo the operations starting from the last one, as shown below.

Source

APCS March 2016 implementation problem 2; statement and figures referenced from ZeroJudge b965 “Matrix Transformations”.