К-мірна часткова сума

Задано 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 чисел в окремих рядках - відповіді на запити.

Приклади