23500번 - MST Camera 다국어

문제

On a recent team contest your team was the best, and therefore won the best award. A camera. But it's not an ordinary camera, manufacturer of the camera, the famous "MST" company claims that this camera has unique capability. If you use it to picture some set of undirected edges of some graph, it is capable of calculating wheter it is possible to form a tree with these edges, and even better, if edges are weighted it is capable of finding a tree with minimum possible sum of weights of edges.

Your task is to check whether your camera works or not. You have a matrix with $R$ rows and $C$ columns, as well as the number $N$ - the number of nodes in the graph. In every field of the matrix, you have one undirected edge of the graph. You should answer on $Q$ queries, where each query is some submatrix of the original matrix. Answer to that query is the sum of weights of edges of minimum spanning tree, formed with edges in the given submatrix.

Formally, in field which is in row $i$ and column $j$ (1ドル \leq i \leq R,ドル 1ドル \leq j \leq C$), you have three numbers $U_{i,j},ドル $V_{i,j}$ and $W_{i,j},ドル which means that in the field $(i,j),ドル there is an edge between node $U_{i,j}$ and $V_{i,j},ドル with weight $W_{i,j}$. After that you have $Q$ queries. Each query is described by four numbers $X_{1},Y_{1},X_{2},Y_{2}$ (1ドル \leq X_{1} \leq X_{2} \leq R,ドル 1ドル \leq Y_{1} \leq Y_{2} \leq C$), where $(X_{1},Y_{1})$ is the upper left corner of the given submatrix, and $(X_{2},Y_{2})$ is the bottom right corner of the submatrix. For each query consider graph with all $N$ nodes and edges from the given submatrix. If there exists minimum spanning tree, you should print the sum of weights of tree edges. If spanning tree doesn't exist, you should print "$-1$" (quotes for clarity). For each query, condition: $\frac{2}{3} \leq \frac{X_{2}-X_{1}+1}{Y_{2}-Y_{1}+1} \leq \frac{3}{2}$ holds.

입력

In first line, there are numbers $N,ドル $R,ドル $C$ and $Q$ (2ドル \leq N \leq 40,ドル 1ドル \leq R,C \leq 250,ドル 1ドル \leq Q \leq 200000$).

$R$ rows follow and in each of them 3ドルC$ numbers. In $i$th row the numbers are: $U_{i,1},ドル $V_{i,1},ドル $W_{i,1},ドル $U_{i,2},ドル $V_{i,2},ドル $W_{i,2},ドル...,$U_{i,C},ドル $V_{i,C},ドル $W_{i,C}$ (0ドル \leq W_{i,j} \leq 65535,ドル for each 1ドル \leq j \leq C$).

$Q$ rows follow and in each of them 4ドル$ numbers - $X_{1},ドル $Y_{1},ドル $X_{2}$ and $Y_{2}$.

출력

Print $Q$ rows, in $i$th row answer to the $i$th query.

제한

힌트