하이퍼 수열과 하이퍼 쿼리

시간 제한2초메모리 제한512 MB

요약

11차원 배열의 모든 칸에 값이 주어질 때, 각 축에 대해 구간을 지정한 11차원 상자 영역의 합을 구한다.

난이도: 보통10점 중 6점
유형: 누적 합, 배열, 구현, 수학
정답자: 아직 제출이 없습니다

문제

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

a1 b1 c1 d1 e1 f1 g1 h1 i1 j1 k1 a2 b2 c2 d2 e2 f2 g2 h2 i2 j2 k2: a1 ≤ α ≤ a2, b1 ≤ β ≤ b2, c1 ≤ γ ≤ c2, d1 ≤ δ ≤ d2, e1 ≤ ε ≤ e2, f1 ≤ ζ ≤ f2, g1 ≤ η ≤ g2, h1 ≤ θ ≤ h2, i1 ≤ ι ≤ i2, j1 ≤ κ ≤ j2, k1 ≤ λ ≤ k2인 모든 (α, β, γ, δ, ε, ζ, η, θ, ι, κ, λ)에 대해서 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 ≤ 106)

둘째 줄부터는 A11111111111, A11111111112, ..., A**mnopqrstuvw가 아래와 같이 주어진다. (1 ≤ Aαβγδεζηθικλ ≤ 109)

둘째 줄에는 A11111111111, A11111111112, ..., A1111111111w의 수 w개가 주어진다.
이러한 줄이 v번 반복되어 A11111111111, A11111111112, ..., A111111111vw의 수 vw개가 주어진다.
이러한 v개의 줄이 u번 반복되어 A11111111111, A11111111112, ..., A11111111uvw의 수 uvw개가 주어진다.
이러한 uv개의 줄이 t번 반복되어 A11111111111, A11111111112, ..., A1111111tuvw의 수 tuvw개가 주어진다.
⋯ 이와 같은 방법으로 mnopqrstuv개의 줄에 걸쳐 A11111111111, A11111111112, ..., A**mnopqrstuvw가 주어진다.

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

(3 + mnopqrstuv)째 줄부터 з개의 줄에는 하이퍼 쿼리 a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, a2, b2, c2, d2, e2, f2, g2, h2, i2, j2, k2가 한 줄에 하나씩 주어진다.

출력

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

예제1

예제 1

입력

1 1 1 1 1 1 1 1 1 2 3
1 2 4
8 16 32
3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3
1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 3

예상 출력

63
2
36