MST 카메라

최근 팀 대회에서 우리 팀이 최우수상을 받았고, 상품은 카메라였다. 평범한 카메라가 아니다. 제조사 "MST"는 이 카메라에 특별한 기능이 있다고 주장한다. 무방향 그래프의 간선 집합을 카메라로 찍으면, 그 간선으로 트리를 만들 수 있는지 판정한다. 간선에 가중치가 있으면 간선 가중치의 합이 최소인 트리도 찾는다. $R$행 $C$열의 행렬이 있고, 그래프의 노드는 $N$개다. 행렬의 $(i,j)$ 칸마다 무방향 간선이 하나씩 있다. 이 간선은 노드 $U_{i,j}$와 $V_{i,j}$를 잇고, 가중치는 $W_{i,j}$다. 쿼리는 부분 행렬로 주어진다. 각 쿼리마다 노드 $N$개와 부분 행렬 안의 간선으로 그래프를 만든다. 이 그래프에 최소 신장 트리가 존재하면 간선 가중치의 합을 출력하고, 존재하지 않으면 "-1"을 출력한다. 모든 쿼리는 $\frac{2}{3} \leq \frac{X_2-X_1+1}{Y_2-Y_1+1} \leq \frac{3}{2}$을 만족한다.

첫 줄에 $N$, $R$, $C$, $Q$가 주어진다($2 \leq N \leq 40$, $1 \leq R,C \leq 250$, $1 \leq Q \leq 200000$). 이어지는 $R$개의 줄은 행렬을 나타낸다. $i$번째 줄에는 $U_{i,1}, V_{i,1}, W_{i,1}, \dots, U_{i,C}, V_{i,C}, W_{i,C}$ 순서로 $3C$개의 수가 있다($0 \leq W_{i,j} \leq 65535$). 마지막 $Q$개의 줄에는 각각 쿼리 $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$). 부분 행렬의 왼쪽 위 모서리는 $(X_1,Y_1)$이고, 오른쪽 아래 모서리는 $(X_2,Y_2)$다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 쿼리의 답을 출력한다. 최소 신장 트리가 존재하면 간선 가중치의 합을, 존재하지 않으면 "-1"을 출력한다.