Задачі
К-мірна часткова сума
К-мірна часткова сума
Задано \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} чисел в окремих рядках - відповіді на запити.
Вхідні дані #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
Вихідні дані #1
12 24 22 18 6