JOI 도시에는 무한히 긴 동서 방향 도로 H개와 무한히 긴 남북 방향 도로 W개로 구성된 격자형 도로망이 있습니다. 교차점 (i, j) (1 ≤ i ≤ H, 1 ≤ j ≤ W)은 북쪽에서 i번째 동서 방향 도로와 서쪽에서 j번째 남북 방향 도로가 교차하는 지점입니다.

현재 도로 상태가 좋지 않아 일부 도로가 폐쇄되었습니다. 구체적으로, 도로 상태는 다음과 같습니다:

북쪽에서 i번째 동서 방향 도로 (1 ≤ i ≤ H)에서 교차점 (i, j)와 교차점 (i, j + 1) (1 ≤ j ≤ W − 1)을 연결하는 도로 구간은 Ai,j = 0일 때 폐쇄되고, Ai,j = 1일 때 통행 가능합니다.

서쪽에서 j번째 남북 방향 도로 (1 ≤ j ≤ W)에서 교차점 (i, j)와 교차점 (i + 1, j) (1 ≤ i ≤ H − 1)을 연결하는 도로 구간은 Bi,j = 0일 때 폐쇄되고, Bi,j = 1일 때 통행 가능합니다.

H × W 교차점 이외의 도로는 모두 폐쇄되었습니다.

JOI 도시의 시장인 K 대통령은 도로망 수리 계획을 세우기로 했습니다. 수리 계획은 하나 이상의 수리로 구성됩니다. 수리는 1 ≤ i ≤ H를 만족하는 정수 i를 선택하여 다음 작업을 수행하는 것입니다:

1 ≤ j ≤ W − 1를 만족하는 모든 정수 j에 대해, 북쪽에서 i번째 동서 방향 도로에서 교차점 (i, j)와 교차점 (i, j + 1)을 연결하는 구간을 통행 가능하게 만듭니다 (폐쇄된 경우).

이 수리는 Ci일이 걸리며, Ci는 1 또는 2 중 하나입니다.

수리 계획은 동시에 수행될 수 없으므로, 수리 계획의 기간은 수리에 소요되는 시간의 합과 동일합니다.

K 대통령은 도시 시설 간 경로 확보가 중요하다고 생각하여 여러분에게 Q개의 질문을 했습니다. k번째 질문 (1 ≤ k ≤ Q)은 다음과 같습니다:

주어진 Tk개의 교차점 (Xk,1, Yk,1), (Xk,2, Yk,2), ..., (Xk,Tk, Yk,Tk)를 서로 도달 가능하게 만드는 수리 계획이 존재합니까? 그렇다면, 그러한 수리 계획의 최소 기간은 몇 일입니까?

도로망 상태, 각 동서 방향 도로의 수리에 소요되는 시간, K 대통령의 질문 내용을 입력받아 모든 질문에 답하는 프로그램을 작성하세요.

#8061 upload - done - how_to_reg - call_split Subtask

도로 서비스 2 timer 1s memory 1024MB

#8061
Subtask

도로 서비스 2 1s 1024MB