Криптекс
Роберт Ленгдон найшёл древний криптекс, на котором вместо букв в каждой клеточке записано некоторое число. Криптекс - это цилиндр, у которого M строк и N столбиков. Строки нумеруются от 0 до M-1 и столбики от 0 до N-1. В каждой клеточке криптекса записаны натуральные числа. Каждая строка криптекса крутится влево и вправо. Чтобы открыть криптекс Роберту нужно уметь быстро крутить строки, а также быстро подсчитывать сумму чисел на некотором прямоугольнике.
Для каждого запроса о подсчёте суммы на прямоуголике вывести указанную сумму на экран.
Входные данные
В первой строке задано 2 числа: N, M – размеры криптекса (1 ≤ N, M ≤ 1000). В последующих M строках в каждой строке по N чисел – числа, записанные в начальной конфигурации криптекса (матрица А, 0 ≤ A_ij ≤ 1000). В следующей строке Q – количество запросов (1 ≤ Q ≤ 1000). Всього есть 3 типа запросов:
? a b c d – посчитать сумму на прямоугольнике: a ≤ i ≤ b, c ≤ j ≤ d: a, b – номера строк, c, d – номера столбиков (1 ≤ a ≤ b ≤ M, 1 ≤ c, d ≤ N. Если c > d то нужно посчитать сумму на двух прямоугольниках(a, b, c, n-1) та (a, b, 0, d));
ml l r val – прокрутить все строки от l до r включительно на val позиций влево;
mr l r val – прокрутить все строки от l до r включительно на val позиций вправо (1 ≤ l ≤ r ≤ M, 1 ≤ val≤ 1000).
Выходные данные
Для всех запросов типа "?" вывести ответ на этот запрос.