체스판 모임

체스 규칙을 알 필요는 없다.

무한한 체스판(2차원 격자) 위에 킹 $N$개가 있고, 각 킹은 좌표 $(X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N)$ 칸에 있다. $N$과 킹들의 좌표는 모두 알려져 있지 않다. 다만 다음 사실은 알고 있다.

• $N$은 1 이상 $N_{\max}$ 이하이다.
• 어떤 킹의 좌표 $X$ 또는 $Y$도 절댓값이 $M$을 넘지 않는다.
• 킹 $N$개는 서로 다른 $N$개의 칸에 있다.

킹들은 체스판의 한 칸에서 만나려 한다. 만남의 칸을 $(X, Y)$로 정하면, $i$번째 킹이 그 칸까지 가는 데 필요한 이동 횟수는 $\max(|X-X_i|, |Y-Y_i|)$이다. 모든 킹이 쓰는 총 이동 횟수는 이 값들을 모든 $i$에 대해 더한 값이다. 킹이 실제로 어떻게 움직이는지는 이 문제와 무관하다. 출발 칸과 도착 칸만 중요하며, 이동 횟수는 위 식으로 항상 계산할 수 있다.

첫 번째 단계에서는 다음 과정을 여러 번 반복할 수 있다. 만남 위치 $(A, B)$를 제안한다($A$와 $B$는 각각 $-10 \times M$ 이상 $10 \times M$ 이하이다). 그러면 심판은 그 위치로 모이는 데 드는 총 이동 횟수, 즉 모든 $i$에 대한 $\max(|X_i-A|, |Y_i-B|)$의 합을 알려 준다. 이런 교환은 최대 $R$번까지 할 수 있으며, 매번 $A$와 $B$ 값은 자유롭게 고른다. 킹들은 실제로 움직이지 않으므로, 한 테스트 케이스 안에서 모든 요청에 대해 $(X_i, Y_i)$는 그대로이다.

두 번째 단계에서는 역할이 바뀐다. 심판이 만남 위치 $(C, D)$를 주면($C$와 $D$는 각각 $-10 \times M$ 이상 $10 \times M$ 이하이다), 같은 킹 위치를 가정하고 그 칸으로 모이는 데 드는 총 이동 횟수를 답해야 한다. 이런 교환은 최대 $R$번이며, 심판의 요청에 모두 올바르게 답해야 한다.

• $1 \le T \le 15$.
• $M = 10^6$.
• 모든 $i$에 대해 $-M \le X_i \le M$.
• 모든 $i$에 대해 $-M \le Y_i \le M$.
• 좌표 쌍 $(X_i, Y_i)$는 서로 다르다.
• 모든 $i$에 대해 $-10 \times M \le C_i \le 10 \times M$.
• 모든 $i$에 대해 $-10 \times M \le D_i \le 10 \times M$.
• $R = 1000$.