K-ölçülü qismən cəmi

Verilmiş k-ölçülü cədvəl a_{i1,i2,...,ik} ədədlərindən ibarətdir, burada hər bir j üçün 1 ≤ i_j ≤ n_j və j 1-dən k-ya qədər dəyişir. Verilmiş l_1, ..., l_k, r_1, ..., r_k üçün aşağıdakıları tapın:

Giriş verilənləri

Birinci sətirdə k (1 ≤ k ≤ 6) ədədi verilir.

İkinci sətirdə cədvəlin ölçüləri - n_j (1 ≤ Πn_j ≤ 10^6) verilir. Daha sonra n_k ədəd olan sətirlər verilir ki, bu ədədlər 1000-dən çox olmayan cədvəli təsvir edir.

Növbəti sətirdə q (1 ≤ q ≤ 10^6) ədədi verilir - sorğuların sayı. Sonrakı q sətirdə sorğular təsvir edilir:

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

Çıxış verilənləri

Hər bir sorğunun cavabını ayrı-ayrı sətirlərdə çıxarın.

Nümunələr