Kryptex
Robert Langdon has discovered an ancient cryptex, which is a cylindrical device with numbers instead of letters. The cryptex is structured as a grid with M rows and N columns. Rows are indexed from 0 to M-1, and columns from 0 to N-1. Each cell in this grid contains a natural number. The rows of the cryptex can be rotated either to the left or to the right. To unlock the cryptex, Robert needs to efficiently rotate the rows and quickly compute the sum of numbers within specified rectangular sections.
For each query that requests the sum of numbers within a rectangle, you should output the calculated sum.
Input
The first line contains two integers: N and M, representing the dimensions of the cryptex (1 ≤ N, M ≤ 1000). The following M lines each contain N integers, which represent the initial configuration of the cryptex (matrix A, where 0 ≤ A_ij ≤ 1000). The next line contains Q, the number of queries (1 ≤ Q ≤ 1000). There are three types of queries:
? a b c d – Calculate the sum of numbers in the rectangle defined by: a ≤ i ≤ b, c ≤ j ≤ d. Here, a and b are row indices, and c and d are column indices (1 ≤ a ≤ b ≤ M, 1 ≤ c, d ≤ N). If c > d, compute the sum over two rectangles: (a, b, c, N-1) and (a, b, 0, d).
ml l r val – Rotate all rows from l to r inclusive to the left by val positions.
mr l r val – Rotate all rows from l to r inclusive to the right by val positions (1 ≤ l ≤ r ≤ M, 1 ≤ val ≤ 1000).
Output
For each query of type "?", output the result of the query.