C. Омкар и определение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Условие задачи вырисовывается ниже, наполняя вас определенностью.

Рассмотрим таблицу, в которой некоторые клетки пустые, а некоторые заполнены. Назовем клетку в этой таблице хорошей, если, начиная с этой клетки, вы можете выйти из таблицы, двигаясь вверх и влево только через пустые клетки. Это касается и стартовой клетки, поэтому все заполненные клетки не являются хорошими. Обратите внимание, вы можете покинуть таблицу из любой крайней левой клетки (в первом столбце), двигаясь влево, а также из любой крайней верхней клетки (в первой строке) — двигаясь вверх.

Назовем таблицу определяемой, если, зная только то, какие клетки являются хорошими, а какие — нет, мы можем точно определить, какие клетки заполнены, а какие нет.

Вам дана таблица $$$a$$$ размером $$$n \times m$$$, т. е. таблица с $$$n$$$ строками и $$$m$$$ столбцами. Вам нужно ответить на $$$q$$$ запросов ($$$1 \leq q \leq 2 \cdot 10^5$$$). Каждый запрос задается двумя целыми числами $$$x_1, x_2$$$ ($$$1 \leq x_1 \leq x_2 \leq m$$$) и спрашивает, является ли часть таблицы $$$a$$$, состоящая из столбцов $$$x_1, x_1 + 1, \ldots, x_2 - 1, x_2$$$, определяемой.

Входные данные

Первая строка содержит два целых числа $$$n, m$$$ ($$$1 \leq n, m \leq 10^6$$$, $$$nm \leq 10^6$$$)  — размеры таблицы $$$a$$$.

Далее следуют $$$n$$$ строк. В $$$y$$$-й строке содержится $$$m$$$ символов, $$$x$$$-й из которых «X», если клетка на пересечении $$$y$$$-й строки и $$$x$$$-го столбца заполнена, и «.», если она пуста.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$)  — количество запросов.

Далее следуют строки по $$$q$$$. Каждая строка содержит два целых числа $$$x_1$$$ и $$$x_2$$$ ($$$1 \leq x_1 \leq x_2 \leq m$$$), представляющих запрос, спрашивающий, является ли часть таблицы $$$a$$$, содержащая только столбцы $$$x_1, x_1 + 1, \ldots, x_2 - 1, x_2$$$, определяемой.

Выходные данные

Для каждого запроса выведите одну строку, содержащую «YES», если часть таблицы, указанная в запросе, определяемая, и «NO» в противном случае. Вывод не чувствителен к регистру (поэтому «YEs» и «No» также будут приняты).

Пример
Входные данные
4 5
..XXX
...X.
...X.
...X.
5
1 3
3 3
4 5
5 5
1 5
Выходные данные
YES
YES
NO
YES
NO
Примечание

Для каждого запроса из примера соответствующая часть таблицы изображена дважды: сначала в исходном формате, затем с каждой клеткой, помеченной как «E», если она хорошая, и «N» в противном случае.

Для первого запроса: 


..X EEN
... EEE
... EEE
... EEE


Для второго запроса: 


X N
. E
. E
. E

Обратите внимание, что вы можете выйти из таблицы, пройдя влево из любой крайней левой клетки (или вверх из любой крайней верхней клетки); вам не нужно достигать левой верхней угловой клетки, чтобы выйти из таблицы.



Для третьего запроса: 


XX NN
X. NN
X. NN
X. NN

Эта часть таблицы не может быть определена только по тому, является ли каждая клетка хорошей, потому что таблица, показанная ниже, также производит показанную выше «таблицу выходимости клеток»: 


XX
XX
XX
XX


Для четвертого запроса: 


X N
. E
. E
. E


Для пятого запроса: 


..XXX EENNN
...X. EEENN
...X. EEENN
...X. EEENN

Этот запрос — это просто вся таблица. Она не может быть определена только по тому, является ли каждая клетка хорошей, потому что таблица, показанная ниже, также производит показанную выше «таблицу выходимости клеток»: 


..XXX
...XX
...XX
...XX