К-мерная частичная сумма

Задана k-мерная таблица чисел a_{i1,i2,...,ik}, где 1 ≤ i_j ≤ n_j для j от 1 до k. Для заданных l_1, ..., l_k, r_1, ..., r_k найдите:

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

В первой строке записано число k (1 ≤ k ≤ 6).

Во второй строке записаны размеры таблицы - nj (1 ≤ Πn_j ≤ 10^6). Далее записано строк по n_k чисел, не превосходящих 1000, описывающих таблицу.

В очередной строке записано число q (1 ≤ q ≤ 10^6) - количество запросов. В следующих q строках описаны запросы:

l_1, ..., l_k, r_1, ..., r_k (1 ≤ l_j ≤ r_j ≤ n_j).

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

Выведите q чисел в отдельных строках - ответы на запросы.

Примеры