2D Flip#4314
You are given a matrix containing rows numbered from to and columns numbered from to . Initially the element in row , column is A_{i,j} = (i - 1) \cdot M + j - 1.
Someone has done several transformations to the matrix. Each transformation was either a horizontal reverse or a vertical reverse. Each reverse is described by four integers X_1, Y_1, X_2 and Y_2 such that 1 \le X_1 \le X_2 \le N and 1 \le Y_1 \le Y_2 \le M.
After the horizontal reverse the element in row , column becomes equal to A'_{i,j} = A_{i,Y_2-j+Y_1} iff X_1 \le i \le X_2 and Y_1 \le j \le Y_2, otherwise it remains the same (A'_{i,j} = A_{i,j}). After the vertical reverse the element in row , column becomes equal to A'_{i,j} = A_{X_2-i+X_1,j} iff X_1 \le i \le X_2 and Y_1 \le j \le Y_2, otherwise it remains the same (A'_{i,j} = A_{i,j}).
Below you can see an example of applying a horizontal reverse and then a vertical reverse.
You should write a program that, given , and a sequence of operations, will be able to find the resulting matrix.
The first line contains two space-separated integers and (1 \le N, M \le 2000). The next line contains the number of operations (1 \le K \le 2000). Each of the next lines describes one operation. The first character of the line stands for the type of the operation (H for horizontal reverse or V for vertical reverse) after which there are four integers X_1, Y_1, X_2 and Y_2 - description of the selected rectangular range. Operations are given in order of their applying.
The first line should contain space-separated integers corresponding to the sum of the elements in the first, second, ..., -th row of the matrix after applying all the operations. Similarly, the second line should contain space-separated integers: the sum of the elements in the first, second, ..., -th column of the resulting matrix.
Example 1