Problems
К-мерная частичная сумма
К-мерная частичная сумма
Задана \textbf{k}-мерная таблица чисел \textbf{a_\{i1,i2,...,ik\}}, где \textbf{1} ≤ \textbf{i_j} ≤ \textbf{n_j} для \textbf{j} от \textbf{1} до \textbf{k}. Для заданных \textbf{l_1}, ..., \textbf{l_k}, \textbf{r_1}, ..., \textbf{r_k} найдите:
\includegraphics{https://static.e-olymp.com/content/21/21fede67418a04591dab2a20b346cddab8c477f0.jpg}
\InputFile
В первой строке записано число \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{6}).
\includegraphics{https://static.e-olymp.com/content/14/147c32cb072845f0079e100a7cb10cbb6f0bcb15.jpg}
Во второй строке записаны размеры таблицы - \textbf{nj} (\textbf{1} ≤ \textbf{Πn_j} ≤ \textbf{10^6}). Далее записано строк по \textbf{n_k} чисел, не превосходящих \textbf{1000}, описывающих таблицу.
\includegraphics{file:///C:/Temp/moz-screenshot-2.png}
\includegraphics{file:///C:/Temp/moz-screenshot-3.png}
В очередной строке записано число \textbf{q} (\textbf{1} ≤ \textbf{q} ≤ \textbf{10^6}) - количество запросов. В следующих \textbf{q} строках описаны запросы:
\textbf{l_1}, ..., \textbf{l_k}, \textbf{r_1}, ..., \textbf{r_k} (\textbf{1} ≤ \textbf{l_j} ≤ \textbf{r_j} ≤ \textbf{n_j}).
\OutputFile
Выведите \textbf{q} чисел в отдельных строках - ответы на запросы.
Input example #1
3 2 3 5 1 2 3 4 5 5 4 3 2 1 2 3 1 5 4 1 2 3 4 5 5 4 3 2 1 2 3 1 5 4 5 1 1 1 1 2 2 1 1 1 2 2 2 1 2 3 2 3 4 1 3 4 2 3 5 1 2 4 2 2 5
Output example #1
12 24 22 18 6