Problem Description

The Trisolarans will launch an attack on Earth. To defend against the attack, humans have deployed $A\times B\times C$ battleships, arranged in space as a cube with $A$ layers, $B$ rows, and $C$ columns. The battleship in layer $i$, row $j$, column $k$ (denoted as battleship $(i, j, k)$) has health $d(i, j, k)$.

The Trisolarans will carry out $m$ rounds of “cube attacks”. Each attack deals the same damage to all battleships inside a smaller cuboid region. Specifically, the $t$-th attack is described by $7$ parameters $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t$.

All battleships $(i, j, k)$ satisfying $i\in [la_t, ra_t],j\in [lb_t, rb_t],k\in [lc_t, rc_t]$ will receive damage $h_t$. If the total accumulated damage on a battleship exceeds its defense (health), then the battleship will explode.

The Earth commander wants you to tell him after which round of attack the first battleship explodes.

Input Format

Read input from standard input.

The first line contains $4$ positive integers $A$, $B$, $C$, $m$.

The second line contains $A\times B\times C$ integers, where the $((i − 1)\times B + (j − 1)) \times C + (k − 1)+1$-th number is $d(i, j, k)$.

Lines $3$ to $m + 2$: the $(t + 2)$-th line contains $7$ positive integers $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t$.

Output Format

Output to standard output.

Output the round number after which the first exploding battleship explodes. It is guaranteed that such a battleship exists.

2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2

2

Hint

Sample Explanation

After the $2$-nd round of attack, battleship $(1,1,1)$ has received a total of $2$ damage, which exceeds its defense and causes it to explode.

Constraints

For $10\%$ of the testdata, $B = C = 1$.

For $20\%$ of the testdata, $C = 1$.

For $40\%$ of the testdata, $A\times B \times C, m\le10000$.

For $70\%$ of the testdata, $A, B, C \le 200$.

For all testdata, $1\le A\times B\times C \le 10^6$, $1\le m \le 10^6$, $0 \le  (i, j, k)$, $h_t\le 10^9$。

Translated by ChatGPT 5