В стране Колбасляндия находится огромное хранилище колбас. Палки колбасы в нём хранятся в стеллаже высотой N полок по М штук на полке, места на полках нумеруются с единицы слева направо, полки тоже нумеруются с единицы сверху вниз. В хранилище работает не самый честный охранник. Зовут его Жуль Ворн. Он каждый день утаскивает со своей работы колбасу. Естественно, Жуль Ворн не хочет, чтобы его поймали, поэтому для своего воровства он выбрал очень своеобразную схему:
Утром приходит смотритель хранилища колбас и видя, что какой-то палки колбасы не хватает, ставит на её место новую палку колбасы той же длины. Таким образом, к приходу Жуля Ворна вся колбаса уже на месте, и он снова забирает себе колбасу по отработанной схеме. Такое беззаконие не могло длиться слишком долго, поэтому через Q дней бессовестного охранника вычислили и он понёс суровое наказание, ну а Вам предлагается выяснить и сообщить директору хранилища колбас: палки колбасы какой длины утащил Жуль Ворн за Q дней?
В первой строке указаны два числа N и M (1 ≤ N, M ≤ 103) – количество полок на стеллаже и количество палок колбас на одной полке. Далее следуют N строк по М натуральных чисел в каждой, где aij – длина колбасы, находящейся на i-ой полке на j-ом месте. Длина каждой палки колбасы не превосходит 109. Далее дано число дней Q (1 ≤ Q ≤ 105).
В следующих Q строках записано по четыре числа: n1, n2, m1 и m2 (1 ≤ n1, n2 ≤ N; 1 ≤ m1, m2 ≤ M). Причём сумма площадей всех выделенных за Q дней областей не превышает 106.
Для каждого дня выведите на отдельной строке число – длину колбасы, которую унёс Жуль Ворн в этот день.
## Входные Данные
В первой строке указаны два числа N и M (1 ≤ N, M ≤ 103) – количество полок на стеллаже и количество палок колбас на одной полке. Далее следуют N строк по М натуральных чисел в каждой, где aij – длина колбасы, находящейся на i-ой полке на j-ом месте. Длина каждой палки колбасы не превосходит 109. Далее дано число дней Q (1 ≤ Q ≤ 105).В следующих Q строках записано по четыре числа: n1, n2, m1 и m2 (1 ≤ n1, n2 ≤ N; 1 ≤ m1, m2 ≤ M). Причём сумма площадей всех выделенных за Q дней областей не превышает 106.
## Выходные Данные
Для каждого дня выведите на отдельной строке число – длину колбасы, которую унёс Жуль Ворн в этот день.
## Примеры
Входные данные3 31 2 34 5 67 8 941 3 1 31 2 2 32 3 1 31 1 1 1Выходные данные5361
[samples]
**Definitions**
Let $ N, M \in \mathbb{Z}^+ $ denote the number of shelves and sausages per shelf, respectively.
Let $ A = (a_{i,j}) \in \mathbb{Z}^{N \times M} $ be the matrix of sausage lengths, where $ a_{i,j} $ is the length of the sausage on shelf $ i $, position $ j $.
Let $ Q \in \mathbb{Z}^+ $ be the number of days.
For each day $ k \in \{1, \dots, Q\} $, let $ (n_{1,k}, n_{2,k}, m_{1,k}, m_{2,k}) $ define a rectangular region:
- Rows from $ n_{1,k} $ to $ n_{2,k} $ (inclusive),
- Columns from $ m_{1,k} $ to $ m_{2,k} $ (inclusive).
**Constraints**
1. $ 1 \leq N, M \leq 10^3 $
2. $ 1 \leq a_{i,j} \leq 10^9 $
3. $ 1 \leq Q \leq 10^5 $
4. For each day $ k $: $ 1 \leq n_{1,k} \leq n_{2,k} \leq N $, $ 1 \leq m_{1,k} \leq m_{2,k} \leq M $
5. Total area of all queried rectangles: $ \sum_{k=1}^Q (n_{2,k} - n_{1,k} + 1)(m_{2,k} - m_{1,k} + 1) \leq 10^6 $
**Objective**
For each day $ k \in \{1, \dots, Q\} $, compute the sum of sausage lengths in the rectangle:
$$
S_k = \sum_{i = n_{1,k}}^{n_{2,k}} \sum_{j = m_{1,k}}^{m_{2,k}} a_{i,j}
$$