在课程中,小女孩 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 列中排序。