시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 512 MB119413035.294%

문제

농부 존은 소들을 기를 새 축사를 건설하기 위해 $N$행 $M$열로 구성된 직사각형 격자 모양의 토지를 매입하였다. 존은 이 토지의 내부에 직사각형 모양의 축사를, 세로축과 가로축이 토지의 축과 평행하도록 건설할 계획이다.

그런데 매입한 토지 중 일부 영역에는 나무나 바위 등 축사가 들어설 수 없는 장애물이 있어서, 이러한 장애물을 포함하지 않는 직사각형 영역을 축사의 위치로 정하려고 한다.

소들의 의견을 존중하는 존은 자신의 $Q$마리의 소들에게 각자가 희망하는 축사의 세로 길이 $a_i$와 가로 길이 $b_i$를 물어보았다.

본격적으로 건설을 시작하기 전에, 존은 소들이 원하는 크기의 축사를 건설하는 것이 가능한지를 모두 조사하고자 한다.

농사일로 너무 바쁜 존을 대신해서, 주어진 토지에 $Q$마리의 소들 각자가 희망하는 크기로 축사를 건설하는 것이 가능한지 판별하는 프로그램을 작성해보자.

입력

첫째 줄에 존이 매입한 토지의 크기를 나타내는 두 정수 $N$과 $M$이 주어진다. 여기에서 $N$은 행의 수, $M$은 열의 수를 의미한다. $(1\leq N \leq 2\,000, 1\leq M \leq 2\,000)$

둘째 줄부터 $N$개 줄에 걸쳐, 토지의 형태가 주어진다. 각 줄은 .#로 이루어진 $M$개의 문자로 구성된다. 여기에서 .은 축사를 건설할 수 있는 영역이고, #은 장애물이 있어 축사를 건설할 수 없는 영역이다.

$N+2$번째 줄에 존이 의견을 구한 소들의 수 $Q$가 주어진다. $(1\leq Q \leq 300\,000)$

$N+3$번째 줄부터 $Q$개 줄에 걸쳐, $1$번째 소부터 $Q$번째 소까지 각자가 희망하는 축사의 크기를 나타내는 두 정수 $a_i$와 $b_i$가 공백으로 나뉘어 한 줄 씩 주어진다. 여기에서 $a_i$는 축사의 세로 길이, $b_i$는 가로 길이를 의미한다. $(1\leq a_i \leq N, 1\leq b_i \leq M)$

출력

$Q$개의 줄을 출력한다. $i (1\leq i \leq Q)$번째 줄에 $i$번째 소가 희망한 크기로 축사를 건설할 수 있다면 YES, 그렇지 않다면 NO를 출력한다.

예제 입력 1

5 5
...##
#....
##...
.....
....#
3
5 1
3 3
4 3

예제 출력 1

YES
YES
NO

토지의 초기 상태. 회색 칸은 장애물이 있는 영역을 나타낸다.

1번 소가 원하는 축사를 건설하는 예

2번 소가 원하는 축사를 건설하는 예

3번 소가 원하는 축사는 어떻게 위치를 정해도 건설할 수 없다.

예제 입력 2

3 6
......
..##..
......
4
1 1
3 6
3 2
1 6

예제 출력 2

YES
NO
YES
YES