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

На уроке информатики маленькая девочка Алёна осваивает редактирование таблиц в одной очень известной программе.

Сейчас у неё есть таблица из целых чисел, состоящая из n строк и m столбцов. Через ai, j будем обозначать число в i-й строке и j-м столбце. Будем говорить, что таблица отсортирована по неубыванию по j-му столбцу, если ai, j ≤ ai + 1, j для всех i от 1 до n - 1.

Учительница дала Алёне k заданий. Для каждого из заданий известны два числа l и r и требуется ответить на вопрос: если от таблицы оставить только строки с l по r включительно, то будет ли она отсортирована по неубыванию хотя бы по одному столбцу? Другими словами, существует ли такое j, что ai, j ≤ ai + 1, j для всех i от l до r - 1 включительно.

Алёна ещё слишком маленькая, чтобы справиться с заданием самостоятельно — помогите ей!

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

В первой строке входных данных записаны два целых положительных числа n и m (1 ≤ n·m ≤ 100 000) — количество строк и столбцов в таблице соответственно. Обратите внимание, что дано ограничение только на произведение этих чисел, то есть на количество элементов таблицы.

В каждой из следующих n строк записаны m целых чисел, j-e число в i-й из этих строк соответствует значению ai, j (1 ≤ ai, j ≤ 109).

В следующей строке входных данных задано число k (1 ≤ k ≤ 100 000) — количество заданий учительницы, которые нужно выполнить Алёне.

В i-й из последующих k строк числа li и ri (1 ≤ li ≤ ri ≤ n).

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

В i-й строке выведите "Yes", если в таблице, полученной из исходной оставлением строк с li по ri включительно будет столбец, по которому она отсортирована по неубыванию, и "No" в противном случае.

Пример
Входные данные
5 4
1 2 3 5
3 1 3 2
4 5 2 3
5 5 3 2
4 4 3 4
6
1 1
2 5
4 5
3 5
1 3
1 5
Выходные данные
Yes
No
Yes
Yes
Yes
No
Примечание

В приведенном примере таблица не отсортирована ни по одному столбцу, но, например, строки 1–3 отсортированы по столбцу 1, а строки 4–5 по столбцу 3.