18830번 - 하이퍼 수열과 하이퍼 쿼리 서브태스크

문제

모양이 m × n × o × p × q × r × s × t × u × v × w인 하이퍼 수열 A_11111111111, A_11111111112, ..., A_mnopqrstuvw가 주어진다. 이 때, 다음 하이퍼 쿼리를 수행하는 프로그램을 작성하시오.

• a1 b1 c1 d1 e1 f1 g1 h1 i1 j1 k1 a2 b2 c2 d2 e2 f2 g2 h2 i2 j2 k2: a₁ ≤ α ≤ a₂, b₁ ≤ β ≤ b₂, c₁ ≤ γ ≤ c₂, d₁ ≤ δ ≤ d₂, e₁ ≤ ε ≤ e₂, f₁ ≤ ζ ≤ f₂, g₁ ≤ η ≤ g₂, h₁ ≤ θ ≤ h₂, i₁ ≤ ι ≤ i₂, j₁ ≤ κ ≤ j₂, k₁ ≤ λ ≤ k₂인 모든 (α, β, γ, δ, ε, ζ, η, θ, ι, κ, λ)에 대해서 A_{αβγδεζηθικλ}의 합을 출력한다.

입력

첫째 줄에 하이퍼 수열의 모양 m, n, o, p, q, r, s, t, u, v, w가 주어진다. (1 ≤ m, n, o, p, q, r, s, t, u, v, w, mnopqrstuvw ≤ 10⁶)

둘째 줄부터는 A_11111111111, A_11111111112, ..., A_mnopqrstuvw가 아래와 같이 주어진다. (1 ≤ A_{αβγδεζηθικλ} ≤ 10⁹)

• 둘째 줄에는 A_11111111111, A_11111111112, ..., A_1111111111w의 수 w개가 주어진다.
• 이러한 줄이 v번 반복되어 A_11111111111, A_11111111112, ..., A_111111111vw의 수 vw개가 주어진다.
• 이러한 v개의 줄이 u번 반복되어 A_11111111111, A_11111111112, ..., A_11111111uvw의 수 uvw개가 주어진다.
• 이러한 uv개의 줄이 t번 반복되어 A_11111111111, A_11111111112, ..., A_1111111tuvw의 수 tuvw개가 주어진다.
• ⋯ 이와 같은 방법으로 mnopqrstuv개의 줄에 걸쳐 A_11111111111, A_11111111112, ..., A_mnopqrstuvw가 주어진다.

(2 + mnopqrstuv)째 줄에는 하이퍼 쿼리의 개수 з가 주어진다. (1 ≤ з ≤ 4 × 10⁴)

(3 + mnopqrstuv)째 줄부터 з개의 줄에는 하이퍼 쿼리 a₁, b₁, c₁, d₁,e₁, f₁, g₁, h₁, i₁, j₁, k₁, a₂, b₂, c₂, d₂, e₂, f₂, g₂, h₂, i₂, j₂, k₂가 한 줄에 하나씩 주어진다.

출력

각각의 하이퍼 쿼리마다 정답을 한 줄에 하나씩 출력한다.

제한

서브태스크 1 (11점)

m = n = o = p = q = r = s = t = u = v = 1, w ≤ 4 × 10⁴

서브태스크 2 (11100점)

m = n = o = p = q = r = s = t = u =1, vw ≤ 4 × 10⁴

서브태스크 3 (1111100000점)

mnopqrstuvw ≤ 4 × 10⁴.

서브태스크 4 (1036372536점)

추가 제약 조건이 없다.

힌트