2D-переворот
You are given a matrix A containing N rows numbered from 1 to N and M columns numbered from 1 to M. Initially the element in row i, column j is A_{i,j} = (i - 1) · 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 ≤ X_1 ≤ X_2 ≤ N and 1 ≤ Y_1 ≤ Y_{2 }≤ M.
After the horizontal reverse the element in row i, column j becomes equal to A^{'}_{i,j} = A_{i,Y2-j+Y1} iff X_1 ≤ i ≤ X_2 and Y_1 ≤ j ≤ Y_2, otherwise it remains the same (A^{'}_{i,j} = A_{i,j}). After the vertical reverse the element in row i, column j becomes equal to A^{'}_{i,j} = A_{X2-i+X1,j} iff X_1 ≤ i ≤ X_2 and Y_1 ≤ j ≤ 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 N, M and a sequence of operations, will be able to find the resulting matrix.
Input
The first line contains two space-separated integers N and M (1 ≤ N, M ≤ 2000). The next line contains the number of operations K (1 ≤ K ≤ 2000). Each of the next K 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.
Output
The first lines hould contain N space-separated integers corresponding to the sum of the elements in the first, second, ..., N-th row of the matrix after applying all the operations. Similarly, the second line should contain M space-separated integers the sum of the elements in the first, second, ..., M-th column of the resulting matrix.