eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Криптекс

Криптекс

Лимит времени 8 секунд
Лимит использования памяти 512 MiB

Роберт Ленгдон найшёл древний криптекс, на котором вместо букв в каждой клеточке записано некоторое число. Криптекс - это цилиндр, у которого M строк и N столбиков. Строки нумеруются от 0 до M-1 и столбики от 0 до N-1. В каждой клеточке криптекса записаны натуральные числа. Каждая строка криптекса крутится влево и вправо. Чтобы открыть криптекс Роберту нужно уметь быстро крутить строки, а также быстро подсчитывать сумму чисел на некотором прямоугольнике.

Для каждого запроса о подсчёте суммы на прямоуголике вывести указанную сумму на экран.

Входные данные

В первой строке задано 2 числа: N, M – размеры криптекса (1N, M1000). В последующих M строках в каждой строке по N чисел – числа, записанные в начальной конфигурации криптекса (матрица А, 0A_ij1000). В следующей строке Q – количество запросов (1Q1000). Всього есть 3 типа запросов:

  • ? a b c d – посчитать сумму на прямоугольнике: ai ≤ b, cjd: a, b – номера строк, c, d – номера столбиков (1abM, 1c, dN. Если 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 позиций вправо (1lrM, 1val1000).

Выходные данные

Для всех запросов типа "?" вывести ответ на этот запрос.

Пример

Входные данные #1
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
7
? 0 3 0 3
? 1 3 1 3
ml 1 2 2
? 1 3 1 3
? 0 3 1 2
mr 2 3 1
? 0 3 1 2
Выходные данные #1
136
99
95
68
68
Автор Остап Столярчук
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года