34559번 - 건물 측량

문제

관우는 땅과 건물이 그려져 있는 $N \times M$ 크기의 지도를 갖고 있습니다.

지도의 가장 왼쪽 위는 $(1, 1),ドル 오른쪽 아래는 $(N, M)$입니다.

지도에서 다음과 같은 칸들은 건물에 속합니다.

• 1ドル$로 표현된 칸
• 0ドル$으로 표현된 칸 중에서 상하좌우 인접한 0ドル$으로 이동해 지도의 테두리에 도달할 수 없는 칸

지도의 테두리란 1ドル$번째 행, $N$번째 행, 1ドル$번째 열, $M$번째 열 중 하나 이상에 포함되는 칸을 의미하고 지도의 테두리와 위 기준에 포함되지 않는 모든 칸은 땅을 의미합니다.

어느 날 고객들이 관우에게 찾아와 임의의 두 좌표를 알려준 뒤 두 좌표로 만들어지는 직사각형 모양의 범위에 새 건물을 지을 수 있는지 물어보기 시작했습니다.

새 건물을 짓기 위해서는 직사각형에 포함되는 모든 칸에 건물이 포함되지 않아야 합니다.

너무 많은 고객이 찾아와 힘들어하는 관우를 대신해 고객들에게 새 건물을 지을 수 있는지 알려주세요.

입력

첫째 줄에 지도의 크기 $N, M$이 주어집니다. (1ドル \leq N, M \leq 1,000円$)

둘째 줄부터 $N + 1$번째 줄까지 지도가 주어집니다. 지도는 0ドル$과 1ドル$로 이루어져 있고 지도의 테두리에는 0ドル$만 주어집니다.

$N + 2$번째 줄에는 찾아올 고객의 수 $Q$가 주어집니다. (1ドル \leq Q \leq 10^6$)

이후 $Q$줄에 걸쳐 고객들이 새 건물을 짓기 원하는 범위의 두 좌표 $(r1, c1),ドル $(r2, c2)$가 주어집니다. (1ドル \leq r1 \leq r2 \leq N; 1 \leq c1 \leq c2 \leq M$)

출력

각각의 고객이 원하는 범위에 새 건물을 지을 수 있으면 Yes를 출력하고, 지을 수 없으면 No를 출력한 뒤 건물을 지을 수 없는 칸이 몇 칸 포함되었는지 출력하세요.

제한

노트