# Единичный прямоугольник

Ограничение времени | 1 секунда
Ограничение памяти | 256 Мб
Ввод | стандартный ввод или input.txt
Вывод | стандартный вывод или output.txt

##

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

## Формат ввода

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

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

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

## Формат вывода

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

## Система оценивания

Решения, верно работающие при n , m , q ≤ 10 n, m, q \le 10 n,m,q≤10 будут получать не менее 20 20 20 баллов.

Решения верно работающие при n ⋅ m ≤ 1 0 6 , q ≤ 100 n \cdot m \le 10^6, q \le 100 n⋅m≤1 0 6,q≤100 будут получать не менее 50 50 50 баллов.

Решения, верно работающие при n ⋅ m ≤ 1 0 6 n \cdot m \le 10^6 n⋅m≤1 0 6, U n i q u e ( w ) ≤ 20 Unique(w) \le 20 U ni q u e(w)≤20 будут получать не менее 20 20 20 баллов, где U n i q u e ( w ) Unique(w) U ni q u e(w), кол-во различных широт в запросах.

### Пример 1

Ввод | Вывод
--- | ---
    3 4 2
    1110
    1110
    0000
    3 2
    3 3
    YES
    NO

### Пример 2

Ввод | Вывод
--- | ---
    4 2 3
    11
    10
    11
    11
    1 4
    2 1
    2 2
    YES
    YES
    YES