Условие задачи вырисовывается ниже, наполняя вас определенностью.
Рассмотрим таблицу, в которой некоторые клетки пустые, а некоторые заполнены. Назовем клетку в этой таблице хорошей, если, начиная с этой клетки, вы можете выйти из таблицы, двигаясь вверх и влево только через пустые клетки. Это касается и стартовой клетки, поэтому все заполненные клетки не являются хорошими. Обратите внимание, вы можете покинуть таблицу из любой крайней левой клетки (в первом столбце), двигаясь влево, а также из любой крайней верхней клетки (в первой строке) — двигаясь вверх.
Назовем таблицу определяемой, если, зная только то, какие клетки являются хорошими, а какие — нет, мы можем точно определить, какие клетки заполнены, а какие нет.
Вам дана таблица \(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\), определяемой.
Выходные данные
Для каждого запроса выведите одну строку, содержащую «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
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
..XXX
...X.
...X.
...X.
5
1 3
3 3
4 5
5 5
1 5
|
YES
YES
NO
YES
NO
|