보드 미팅 timer 60s memory 1024MB

이 문제를 풀기 위해 체스 규칙을 알 필요는 없다.

무한한 체스판(2차원 격자) 위에 N개의 킹(king)이 있고, 각 킹은 (X₁, Y₁), (X₂, Y₂), ..., (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에 대해 이 최댓값을 합한 값이 된다. 킹이 실제로 체스판에서 어떻게 움직이는지는 이 문제에서 중요하지 않다 — 출발 칸과 도착 칸만 중요하며, 이동 횟수는 위 식으로 항상 계산할 수 있다.

이 문제는 두 단계로 이루어진다. 1단계에서 당신은 다음을 반복할 수 있다: 만남 위치 (A, B)를 제안한다(각각 -10×M 이상 10×M 이하, 포함). 그러면 심판은 킹들이 그곳으로 가기 위해 사용할 총 이동 횟수, 즉 (모든 i에 대해) max(|X_i-A|,|Y_i-B|)의 합을 알려 준다. 이런 질의-응답을 최대 R번까지 할 수 있으며, 매번 A와 B를 선택할 수 있다. 킹들은 실제로 움직이지 않으므로, 한 테스트 케이스 내에서 모든 질의에 대해 킹들의 위치 (X_i, Y_i)는 동일하게 유지된다는 점에 유의하라.

2단계에서는 역할이 바뀐다: 심판이 만남 위치 (C, D)를 준다(각각 -10×M 이상 10×M 이하, 포함). 당신은 1단계와 같은 킹들의 위치를 가정하고, 킹들이 그곳으로 가기 위해 사용할 총 이동 횟수를 답해야 한다. 이런 질의가 최대 R번 주어지며, 심판의 모든 질의에 대해 정확히 답해야 한다.