Kryptex#4467
Robert Langdon has discovered an ancient cryptex, a cylinder whose cells contain numbers instead of letters. The cryptex is structured as a grid with rows and columns. Rows are indexed from to M - 1, and columns from to N - 1. Every cell in this grid contains a natural number.
Each row of the cryptex can be rotated to the left or to the right. To unlock the cryptex, Robert must quickly perform two types of operations: rotating row sequences and computing the sum of numbers within specified rectangular areas of the grid.
For each query that requests the sum of numbers within a rectangle, output the computed sum.
The first line contains two integers: and (1 \leq N, M \leq 1000), representing the dimensions of the cryptex. Each of the next lines contains integers—the initial configuration of the cryptex, forming a matrix (0 \leq A_{ij} \leq 1000).
The next line contains (1 \leq Q \leq 1000)—the number of queries. Each query is one of the following three types:
- ? — Calculate the sum of numbers in the submatrix defined by a \leq i \leq b and c \leq j \leq d, where , are row indices and , are column indices (0 \leq a \leq b \leq M - 1, 0 \leq c, d \leq N - 1). If c > d, compute the sum over two rectangles: (a, b, c, N - 1) and (a, b, 0, d), i.e., sum the elements where the column index either satisfies c \leq j \leq N - 1 or 0 \leq j \leq d within rows to . - ml — Rotate all rows with indices from to inclusive to the left by positions. - mr — Rotate all rows with indices from to inclusive to the right by positions (0 \leq l \leq r \leq M - 1, 1 \leq val \leq 1000).
For each query of type ? (sum query), output the answer to the query on a separate line.
Example 1