CF777C Alyona and Spreadsheet

在上课时，小女孩 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 翻译