Единичный прямоугольник
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана таблица размером $$$N \times M$$$, состоящая из нулей и единиц. Вам необходимо ответить на $$$Q$$$ запросов. Каждый запрос представляет собой два целых числа $$$W$$$ и $$$H$$$. Требуется определить, существует ли в данной таблице прямоугольник, полностью состоящий из единиц, шириной ровно $$$W$$$ и высотой ровно $$$H$$$. Стороны прямоугольника должны быть параллельны сторонам таблицы.

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

В первой строке через пробел вводятся три целых числа: $$$N, M, Q$$$ ($$$1 \le N, M \le 10^6, N \cdot M \le 10^6, 1 \le Q \le 10^5$$$).

В следующих $$$N$$$ строках вводится сама таблица.

Каждая строка содержит $$$M$$$ символов ('0' или '1') без пробелов. В следующих $$$Q$$$ строках вводятся пары целых чисел $$$W$$$ и $$$H$$$ ($$$1 \le W \le M, 1 \le H \le N$$$).

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

Для каждого запроса выведите в отдельной строке "YES", если такой прямоугольник существует, и "NO" в противном случае.

Примеры

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

    3 4 2
    1110
    1110
    0000
    3 2
    3 3

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

    YES
    NO

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

    4 2 3
    11
    10
    11
    11
    1 4
    2 1
    2 2

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

    YES
    YES
    YES