← 返回题目列表

Codeforces · 777/C

C. Alyona 和电子表格

中文机器翻译题面 查看原题

在课程中,小女孩 Alyona 使用一个著名的电子表格计算机程序并学习如何编辑表格。

现在她有一个充满整数的表格。该表由 n 行和 m 列组成。 ai、j 表示位于第 i 行、第 j 列的整数。如果 ai, j ≤ ai + 1, j 对于从 1 到 n - 1 的所有 i,我们说表在 j 列中按非降序排序。

老师给了 Alyona k 个任务。对于每个任务,给出两个整数 l 和 r,Alyona 必须回答以下问题:如果保留从 l 到 r 的行并删除所有其他行,则表是否会在至少一列中按非降序排序?形式上,对于从 l 到 r - 1 的所有 i,是否存在这样的 j , ai, j ≤ ai + 1, j 。

阿廖娜太小了,无法处理这个任务,请你帮忙!

输入

输入的第一行包含两个正整数 n 和 m (1 ≤ n·m ≤ 100 000) - 分别是表中的行数和列数。请注意,您被赋予了一个约束,该约束限制了这两个整数的乘积,即表中的元素数量。

以下 n 行每一行包含 m 个整数。这些行的第 i 行中的第 j 个整数代表 ai, j (1 ≤ ai, j ≤ 109)。

输入的下一行包含一个整数 k (1 ≤ k ≤ 100 000) – 老师给 Alyona 的任务数量。

接下来 k 行的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n)。

输出

如果包含从 li 到 ri 的行的表在至少一列中按非降序排序,则在输出的第 i 行打印“Yes”。否则,打印“否”。

示例

输入 #1

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

输出 #1

Yes
No
Yes
Yes
Yes
No

注意

在示例中,整个表未在任何列中排序。但是,第 1-3 行在第 1 列中排序,而第 4-5 行在第 3 列中排序。