Криптекс
Роберт Ленгдон знайшов стародавній криптекс на якому замість літер в кожній клітинці записано деяке число. Криптекс - це циліндр у якого 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).
Вихідні дані
На всі запити типу "?" вивести відповідь на даний запит.