축사 건설

농부 존은 소들을 기를 새 축사를 짓기 위해 $N$행 $M$열 격자 모양의 토지를 매입했다. 존은 이 토지 안에 세로축과 가로축이 토지의 축과 평행한 직사각형 축사를 지을 계획이다.

토지 일부에는 나무나 바위 같은 장애물이 있어 축사를 지을 수 없다. 따라서 장애물을 포함하지 않는 직사각형 영역을 축사 위치로 정해야 한다.

존은 소 $Q$마리에게 원하는 축사의 세로 길이 $a_i$와 가로 길이 $b_i$를 물어보았다.

본격적으로 건설하기 전에, 존은 소들이 원하는 크기의 축사를 지을 수 있는지 모두 확인하려 한다.

농사로 바쁜 존을 대신해서, 주어진 토지에 $Q$마리 소 각각이 원하는 크기의 축사를 지을 수 있는지 판별하는 프로그램을 작성하라.

첫째 줄에 토지의 행 수 $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$번째 줄에는 $i$번째 소가 원하는 크기의 축사를 지을 수 있으면 YES, 없으면 NO를 출력한다.