题目描述

在上课时，小女孩 Alyona 正在使用著名的电子表格程序学习如何编辑表格。

现在她有一个由整数填充的表格。该表格共有 $n$ 行 $m$ 列。我们用 $a_{i,j}$ 表示第 $i$ 行第 $j$ 列的整数。称某一列 $j$ 按非递减顺序排序是指对于每个 $i$ 从 $1$ 到 $n-1$，都有 $a_{i,j} \leq a_{i+1,j}$。

老师给了 Alyona $k$ 个任务。对于每个任务，会给定两个整数 $l$ 和 $r$，Alyona 需要回答这样一个问题：如果仅保留第 $l$ 行到第 $r$ 行（包含两端），删除其它所有行，能否使表格在至少一列上按非递减顺序排序？形式化地说，是否存在某个 $j$，使得对于所有的 $i$ 从 $l$ 到 $r-1$，都有 $a_{i,j} \leq a_{i+1,j}$。

Alyona 太小，无法独自完成这个任务，于是请求你的帮助！

输入格式

第一行包含两个正整数 $n$ 和 $m$（$1 \leq n \cdot m \leq 100000$），表示表格的行数和列数。注意，你得到的约束是这两个数的乘积的上界，也就是表格中元素的个数。

接下来的 $n$ 行，每行包含 $m$ 个整数。第 $i$ 行第 $j$ 个整数为 $a_{i,j}$（$1 \leq a_{i,j} \leq 10^{9}$）。

接下来一行，包含一个整数 $k$（$1 \leq k \leq 100000$），表示老师给 Alyona 的任务数量。

接下来的 $k$ 行，每行包含两个整数 $l_{i}$ 和 $r_{i}$（$1 \leq l_{i} \leq r_{i} \leq n$）。

输出格式

对于每个任务，如果保留第 $l_{i}$ 行到第 $r_{i}$ 行组成的表格，在至少一列上是非递减排序的，则输出 “Yes”；否则输出 “No”。每个答案占一行。

说明/提示

在样例数据中，整个表格没有任何一列是完全非递减的。然而，第 $1$ 到第 $3$ 行在第 $1$ 列上是非递减的，第 $4$ 到第 $5$ 行在第 $3$ 列上是非递减的。

由 ChatGPT 5 翻译

样例

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