题目描述

三体人将对地球发起攻击。为了抵御攻击，地球人派出了 $A\times B\times C$ 艘战舰，在太空中排成一个 $A$ 层 $B$ 行 $C$ 列的立方体。其中，第 $i$ 层第 $j$ 行第 $k$ 列的战舰（记为战舰 $(i, j, k)$）的生命值为 $d(i, j, k)$。

三体人将会对地球发起 $m$ 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第 $t$ 轮攻击用 $7$ 个参数 $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t$ 描述；

所有满足 $i\in [la_t, ra_t],j\in [lb_t, rb_t],k\in [lc_t, rc_t]$ 的战舰 $(i, j, k)$ 会受到 $h_t$ 的伤害。如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。

地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

输入格式

从标准输入读入数据。

第一行包括 $4$ 个正整数 $A$，$B$，$C$，$m$；

第二行包含 $A\times B\times C$ 个整数，其中第 $((i − 1)\times B + (j − 1)) \times C + (k − 1)+1$ 个数为 $d(i, j, k)$；

第 $3$ 到第 $m + 2$ 行中，第 $(t + 2)$ 行包含 $7$ 个正整数 $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t$。

输出格式

输出到标准输出。

输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。

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

提示

【样例解释】

在第 $2$ 轮攻击后，战舰 $(1,1,1)$ 总共受到了 $2$ 点伤害，超出其防御力导致爆炸。

【数据约定】

对于 $10\%$ 的数据，$B = C = 1$；

对于 $20\%$ 的数据，$C = 1$；

对于 $40\%$ 的数据，$A\times B \times C, m\le10000$；

对于 $70\%$ 的数据，$A, B, C \le 200$；

对于所有数据，$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$。