Задача №113367. Красивые клеточки
На прошлый новый год друзья подарили Мише клетчатое поле из n строк и m столбцов, в каждой клетке которого записано некоторое целое число c i , j , где i определяет номер строки, а j — номер столбца. Строки пронумерованы сверху вниз, а столбцы — слева направо. Строки и столбцы занумерованы целыми числами, начиная с единицы.
Подарок Мише очень понравился, и он сразу же решил показать его Маше. Вместе они долго изучали поле и обсуждали его красоту, а потом Маша заявила, что хочет часть поля забрать себе. Она пока не решила, какую именно, поэтому она назвала Мише k прямоугольных областей и предложила отдать ей любую. Миша оценивает крутизну области как сумму всех чисел, находящихся внутри неё. Перед тем как принять решение, какую же область подарить Маше, Миша хочет вычислить крутизну всех предложенных вариантов.
Задача была бы практически невыполнима, если бы Миша не прочитал прилагавшуюся к клетчатому полю инструкцию. В ней было сказано, что на самом деле число c i , j равняется a i & b j , где a и b — две последовательности чисел, любезно указанных в инструкции, а операция & означает побитовое умножение или побитовое «И» (определение операции смотрите в разделе «Замечание»).
В первой строке ввода записаны числа n , m и k ( 1 ≤ n , m , k ≤ 200 000 ) — размеры клетчатого поля и количество областей, названных Машей, соответственно. Во второй строке содержатся n чисел a i ( 0 ≤ a i ≤ 1 000 000 ) — элементы первой последовательности. В третьей строке содержатся m чисел b i ( 0 ≤ b i ≤ 1 000 000 ) — элементы второй последовательности.
Следующие k строк описывают варианты, предложенные Машей, каждая из них содержит 4 числа u i , l i , d i , r i ( 1 ≤ u i ≤ d i ≤ n , 1 ≤ l i ≤ r i ≤ m ) — координаты левой верхней и правой нижней клетки соответствующей области.
Выведите k строк, i -я строка должна содержать крутизну i -й области.
Рассмотрим записи чисел x и y в двоичной системе исчисления (возможно, с ведущими нулями) x = x k ... x 1 x 0 и y = y k ... y 1 y 0 . Тогда z = x & y определяется как z = z k ... z 1 z 0 , где z i = 1 , если x i = 1 и y i = 1 , иначе z i = 0 . Иными словами, единицы в побитовом «И» чисел находятся в тех разрядах, в которых у обоих чисел находятся единицы.
3 3 3 4 0 3 1 2 1 1 1 3 3 1 1 1 3 1 2 3 2
4 0 2
1 2 2 7 1 12 1 1 1 2 1 1 1 1
5 1