402431: GYM100771 D Похищения колбасы

D. Похищения колбасыограничение по времени на тест1.5 секундограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

В стране Колбасляндия находится огромное хранилище колбас. Палки колбасы в нём хранятся в стеллаже высотой N полок по М штук на полке, места на полках нумеруются с единицы слева направо, полки тоже нумеруются с единицы сверху вниз. В хранилище работает не самый честный охранник. Зовут его Жуль Ворн. Он каждый день утаскивает со своей работы колбасу. Естественно, Жуль Ворн не хочет, чтобы его поймали, поэтому для своего воровства он выбрал очень своеобразную схему:

• Каждый вечер он выбирает область на стеллаже колбас, рассматривая палки колбасы, которые находятся на полках с n1 по n2 и номер которых на полке больше либо равен m1 и меньше либо равен m2.
• Далее он находит палку колбасы длинной k такую, что |X-Y| минимально, где Х – количество палок колбасы из выделенной области, которые короче либо равны k, а Y – количество палок колбасы из выделенной области, которые строго длиннее k. Если таких палок колбасы несколько, то он забирает самую длинную.
• С чувством собственного превосходства он забирает эту палку колбасы себе и уходит домой под покровом ночи.

Утром приходит смотритель хранилища колбас и видя, что какой-то палки колбасы не хватает, ставит на её место новую палку колбасы той же длины. Таким образом, к приходу Жуля Ворна вся колбаса уже на месте, и он снова забирает себе колбасу по отработанной схеме. Такое беззаконие не могло длиться слишком долго, поэтому через Q дней бессовестного охранника вычислили и он понёс суровое наказание, ну а Вам предлагается выяснить и сообщить директору хранилища колбас: палки колбасы какой длины утащил Жуль Ворн за Q дней?

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

В первой строке указаны два числа N и M (1 ≤ N, M ≤ 10³) – количество полок на стеллаже и количество палок колбас на одной полке. Далее следуют N строк по М натуральных чисел в каждой, где a_ij – длина колбасы, находящейся на i-ой полке на j-ом месте. Длина каждой палки колбасы не превосходит 10⁹. Далее дано число дней Q (1 ≤ Q ≤ 10⁵).

В следующих Q строках записано по четыре числа: n1, n2, m1 и m2 (1 ≤ n1, n2 ≤ N; 1 ≤ m1, m2 ≤ M). Причём сумма площадей всех выделенных за Q дней областей не превышает 10⁶.

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

Для каждого дня выведите на отдельной строке число – длину колбасы, которую унёс Жуль Ворн в этот день.

ПримерыВходные данные

3 3
1 2 3
4 5 6
7 8 9
4
1 3 1 3
1 2 2 3
2 3 1 3
1 1 1 1

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

5
3
6
1