Cube Attack: Identify the Round of First Explosion

In this problem, Earth is under attack by the Trisolarans. Earth has deployed A×B×C warships arranged in a cube with A layers, B rows, and C columns. The warship at position \( (i, j, k) \) has a defense value (or health) of \( d(i,j,k) \).

The Trisolarans perform \( m \) rounds of "cube attacks". In the \( t\)-th round, they use 7 parameters \( la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t \). In that round, every warship \( (i, j, k) \) satisfying

[ la_t \le i \le ra_t, \quad lb_t \le j \le rb_t, \quad lc_t \le k \le rc_t ]

receives \( h_t \) damage. When the total damage inflicted on a warship becomes \( > d(i,j,k) \) (i.e. strictly exceeds its defense), it explodes immediately.

Your task is to determine the round after which the first warship explodes. If no warship explodes after all \( m \) rounds, output \( -1 \).

inputFormat

The first line contains four integers \( A, B, C, m \) representing the dimensions of the cube and the number of attack rounds.

The second line contains \( A \times B \times C \) integers representing the defense values \( d(i,j,k) \) of the warships. The values are given in the order: layer by layer (from 1 to \( A \)), and within each layer, in row-major order (from row 1 to \( B \)) and column 1 to \( C \)).

Then follow \( m \) lines. The \( t\)-th line contains 7 integers: \( la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t \), describing the parameters of the \( t\)-th attack.

outputFormat

Output a single integer representing the round after which the first explosion occurs. If no warship explodes, output \( -1 \).

sample

2 2 2 2
10 10 10 10 10 10 10 10
1 1 1 2 1 2 5
1 2 1 2 1 2 6

2