在最近的一次团队竞赛中，你们队表现优异，赢得了最好的奖品——一台相机。但这可不是普通的相机，该相机的制造商，著名的“MST”公司声称这台相机具有独特的功能。如果你用它拍摄某个图中的一组无向边，它能够计算出是否可以用这些边构成一棵树，甚至更好的是，如果边带有权重，它还能找到权重之和最小的树。

你的任务是验证这台相机是否工作正常。你有一个 $R$ 行 $C$ 列的矩阵，以及图中的节点数 $N$。矩阵的每个单元格中都有一条图的无向边。你需要回答 $Q$ 个查询，每个查询对应原矩阵的一个子矩阵。该查询的答案是使用给定子矩阵中的边所构成的最小生成树的权重之和。

形式化地，在第 $i$ 行第 $j$ 列（$1 \le i \le R, 1 \le j \le C$）的单元格中，有三个数字 $U_{i,j}, V_{i,j}$ 和 $W_{i,j}$，这意味着在单元格 $(i, j)$ 中，存在一条连接节点 $U_{i,j}$ 和 $V_{i,j}$ 的边，其权重为 $W_{i,j}$。之后有 $Q$ 个查询。每个查询由四个数字 $X_1, Y_1, X_2, Y_2$（$1 \le X_1 \le X_2 \le R, 1 \le Y_1 \le Y_2 \le C$）描述，其中 $(X_1, Y_1)$ 是给定子矩阵的左上角，$(X_2, Y_2)$ 是子矩阵的右下角。对于每个查询，考虑包含所有 $N$ 个节点以及来自给定子矩阵中所有边的图。如果存在最小生成树，你应该输出树边的权重之和。如果不存在生成树，你应该输出 "-1"（引号仅为清晰起见）。对于每个查询，满足条件：$\frac{2}{3} \le \frac{X_2-X_1+1}{Y_2-Y_1+1} \le \frac{3}{2}$。

输入格式

第一行包含数字 $N, R, C$ 和 $Q$（$2 \le N \le 40, 1 \le R, C \le 250, 1 \le Q \le 200000$）。

接下来 $R$ 行，每行包含 $3C$ 个数字。在第 $i$ 行中，数字依次为：$U_{i,1}, V_{i,1}, W_{i,1}, U_{i,2}, V_{i,2}, W_{i,2}, \dots, U_{i,C}, V_{i,C}, W_{i,C}$（对于每个 $1 \le j \le C$，$0 \le W_{i,j} \le 65535$）。

接下来 $Q$ 行，每行包含 4 个数字：$X_1, Y_1, X_2$ 和 $Y_2$。

输出格式

输出 $Q$ 行，第 $i$ 行对应第 $i$ 个查询的答案。

样例

样例输入 1

4 3 4 3
1 2 1 1 2 2 1 2 3 1 2 100
2 3 2 2 3 3 2 3 1 2 3 101
3 4 3 3 4 1 3 4 2 3 4 102
1 1 3 4
1 2 3 3
3 4 3 4

样例输出 1

3
4
-1