Криптекс#4467
Роберт Ленґдон знайшов стародавній криптекс — циліндр, у чарунках якого замість букв містяться числа. Криптекс має форму сітки з рядків і стовпців. Рядки нумеруються від до M - 1, а стовпці — від до N - 1. У кожній чарунці цієї сітки знаходиться натуральне число.
Кожен рядок криптексу можна циклічно зсунути вліво або вправо. Щоб відкрити криптекс, Роберту потрібно швидко виконувати два типи операцій: обертання рядків і знаходження суми чисел у вказаних прямокутних ділянках сітки.
Для кожного запиту на обчислення суми у прямокутнику виведіть отриману суму.
У першому рядку задано два цілі числа і (1 \leq N, M \leq 1000) — розміри криптексу. Далі у наступних рядках міститься по чисел — початковий стан криптексу, тобто матриця (0 \leq A_{ij} \leq 1000).
У наступному рядку задано (1 \leq Q \leq 1000) — кількість запитів. Далі йдуть рядків, кожен із яких описує один із трьох типів запитів:
- ? — знайти суму чисел у підматриці, заданій умовами a \leq i \leq b та c \leq j \leq d, де — індекси рядків, — індекси стовпців (0 \leq a \leq b \leq M - 1, 0 \leq c, d \leq N - 1). Якщо c > d, знайти суму елементів у двох прямокутниках: (a, b, c, N - 1) та (a, b, 0, d), тобто просумувати елементи, у яких індекс стовпця задовольняє c \leq j \leq N - 1 або 0 \leq j \leq d у рядках з по . - ml — циклічно зсунути всі рядки з індексами від до включно вліво на позицій. - mr — циклічно зсунути всі рядки з індексами від до включно вправо на позицій (0 \leq l \leq r \leq M - 1, 1 \leq val \leq 1000).
Для кожного запиту типу ? (запит на суму) виведіть відповідь на окремому рядку.
Приклад 1