During the lesson small girl Alyona works with one famous spreadsheet computer program and learns how to edit tables.

Now she has a table filled with integers. The table consists of n rows and m columns. By a_{i}, j we will denote the integer located at the i-th row and the j-th column. We say that the table is sorted in non-decreasing order in the column j if a_{i}, j ≤ a_{i} + 1, j for all i from 1 to n - 1.

Teacher gave Alyona k tasks. For each of the tasks two integers l and r are given and Alyona has to answer the following question: if one keeps the rows from l to r inclusive and deletes all others, will the table be sorted in non-decreasing order in at least one column? Formally, does there exist such j that a_{i}, j ≤ a_{i} + 1, j for all i from l to r - 1 inclusive.

Alyona is too small to deal with this task and asks you to help!


-----Input-----

The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 100 000) — the number of rows and the number of columns in the table respectively. Note that your are given a constraint that bound the product of these two integers, i.e. the number of elements in the table.

Each of the following n lines contains m integers. The j-th integers in the i of these lines stands for a_{i}, j (1 ≤ a_{i}, j ≤ 10^9).

The next line of the input contains an integer k (1 ≤ k ≤ 100 000) — the number of task that teacher gave to Alyona.

The i-th of the next k lines contains two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n).


-----Output-----

Print "Yes" to the i-th line of the output if the table consisting of rows from l_{i} to r_{i} inclusive is sorted in non-decreasing order in at least one column. Otherwise, print "No".


-----Example-----
Input
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

Output
Yes
No
Yes
Yes
Yes
No



-----Note-----

In the sample, the whole table is not sorted in any column. However, rows 1–3 are sorted in column 1, while rows 4–5 are sorted in column 3.

Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms

Dynamic programming

Data structures
Skill types: Sorting

Amortized analysis

Greedy algorithms

Dynamic programming

Data structures

Starter code:

Solutions:
import sys

def debug(x, table):
	for (name, val) in table.items():
		if x is val:
			print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
			return None

def solve():
	(n, m) = map(int, sys.stdin.readline().split())
	A = [[int(i) for i in sys.stdin.readline().split()] for j in range(n)]
	q = int(sys.stdin.readline().rstrip())
	querys = [tuple(map(int, sys.stdin.readline().split())) for i in range(q)]
	f = [i for i in range(n)]
	for j in range(m):
		s = 0
		for i in range(n):
			if i == n - 1 or A[i][j] > A[i + 1][j]:
				for k in range(s, i + 1):
					f[k] = max(f[k], i)
				s = i + 1
	ans = []
	for (l, r) in querys:
		if r - 1 <= f[l - 1]:
			ans.append('Yes')
		else:
			ans.append('No')
	print(*ans, sep='\n')
solve()


import sys
rr = sys.stdin.readline
(n, m) = map(int, rr().split())
table = []
for _ in range(n):
	table.append(list(map(int, rr().split())))
depth = [[1] * m for _ in range(n)]
for c in range(m):
	for r in range(1, n):
		if table[r][c] >= table[r - 1][c]:
			depth[r][c] = depth[r - 1][c] + 1
max_depth = [max(row) for row in depth]
for _ in range(int(rr())):
	(l, r) = map(int, rr().split())
	if l == r:
		print('Yes')
	elif max_depth[r - 1] >= r - l + 1:
		print('Yes')
	else:
		print('No')


from __future__ import print_function
from collections import *
from sys import stdin
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, m) = gil()
mat = [gil() for _ in range(n)]
p = set()
for j in range(m):
	(l, r) = (0, 0)
	while r + 1 < n:
		if mat[r + 1][j] < mat[r][j]:
			if l != r:
				p.add((l + 1, r + 1))
			l = r + 1
		r += 1
	if l != r:
		p.add((l + 1, r + 1))
p = list(p)
p.sort(reverse=True)
endMax = [i for i in range(n + 1)]
h = []
for start in range(1, n + 1):
	while p and p[-1][0] == start:
		heappush(h, -p.pop()[1])
	while h and -h[0] <= start:
		heappop(h)
	if h:
		endMax[start] = -h[0]
ans = []
for _ in range(gil()[0]):
	(l, r) = gil()
	ans.append('Yes' if endMax[l] >= r else 'No')
print('\n'.join(ans))


def ri():
	return map(int, input().split())
(n, m) = ri()
a = []
for i in range(n):
	a.append(list(ri()))
t = [[0 for i in range(m)] for j in range(n)]
T = [0 for i in range(n)]
for i in range(m):
	for j in range(n - 1):
		if a[j][i] > a[j + 1][i]:
			t[j + 1][i] = 0
		else:
			t[j + 1][i] = t[j][i] + 1
for i in range(n):
	T[i] = max(t[i])
k = int(input())
ans = []
for i in range(k):
	(l, r) = ri()
	l = l - 1
	r = r - 1
	if T[r] >= r - l:
		ans.append('Yes')
	else:
		ans.append('No')
print('\n'.join(ans))


(n, m) = map(int, input().split())
M = [list(map(int, input().split())) for i in range(n)]
depth = [[1] * m for i in range(n)]
for col in range(m):
	for row in range(1, n):
		if M[row][col] >= M[row - 1][col]:
			depth[row][col] = depth[row - 1][col] + 1
max_depth = [max(row) for row in depth]
ans = ''
k = int(input())
for i in range(k):
	(l, r) = map(int, input().split())
	if max_depth[r - 1] >= r - l + 1:
		ans += 'Yes\n'
	else:
		ans += 'No\n'
print(ans)


import sys
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
arr = []
for i in range(n):
	arr.append(list(map(int, input().split())))
ans = [n + 3] * n
ans[0] = 0
dp = [0] * m
for i in range(1, n):
	for j in range(m):
		if arr[i][j] < arr[i - 1][j]:
			dp[j] = i
		ans[i] = min(ans[i], dp[j])
for i in range(int(input())):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	if ans[r] <= l:
		print('Yes')
		continue
	print('No')


(n, m) = map(int, input().split())
Table = []
for r in range(n):
	row = list(map(int, input().split()))
	Table.append(row)
k = int(input())
Tasklist = []
for task in range(k):
	(l, r) = map(int, input().split())
	Tasklist.append([l, r])
locate = [0] * (n + 1)
for c in range(m):
	start = 0
	for r in range(0, n - 1):
		if Table[r][c] <= Table[r + 1][c]:
			pass
		else:
			for index in range(start, r + 1):
				if locate[index] < r:
					locate[index] = r
			start = r + 1
	for index in range(start, n):
		if locate[index] < n - 1:
			locate[index] = n - 1
for task in range(k):
	Task = Tasklist[task]
	l = Task[0]
	r = Task[1]
	if locate[l - 1] >= r - 1:
		print('Yes')
	else:
		print('No')


import sys
(n, m) = map(int, sys.stdin.readline().rstrip().split())
matrix = []
for _ in range(n):
	row = list(map(int, sys.stdin.readline().rstrip().split()))
	matrix.append(row)
A = [[1 for _ in range(m)] for _ in range(n)]
for i in range(n - 2, -1, -1):
	for j in range(m):
		if matrix[i][j] <= matrix[i + 1][j]:
			A[i][j] = A[i + 1][j] + 1
rows = [max(row) for row in A]
ans = ''
k = int(sys.stdin.readline().rstrip())
for _ in range(k):
	(l, r) = map(int, sys.stdin.readline().rstrip().split())
	if rows[l - 1] >= r - l + 1:
		ans += 'Yes\n'
	else:
		ans += 'No\n'
sys.stdout.write(ans)


(n, m) = [int(x) for x in input().split()]
arr = [[int(x) for x in input().split()] for i in range(0, n)]
v = [[1] * m for i in range(0, n)]
for i in range(0, m):
	for j in range(1, n):
		if arr[j][i] >= arr[j - 1][i]:
			v[j][i] = v[j - 1][i] + 1
best = [max(i) for i in v]
ans = ''
t = int(input())
for i in range(0, t):
	(x, y) = [int(s) for s in input().split()]
	if best[y - 1] >= y - x + 1:
		ans += 'Yes\n'
	else:
		ans += 'No\n'
print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
v = [[1] * m for i in range(n)]
for j in range(m):
	for i in range(n - 1)[::-1]:
		if a[i][j] <= a[i + 1][j]:
			v[i][j] = v[i + 1][j] + 1
max_l = [max(arr) for arr in v]
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	if max_l[l - 1] >= r - l + 1:
		print('Yes')
	else:
		print('No')


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
(n, m) = mp()
ml = [lmp() for i in range(n)]
maxEnd = dd(int)
for j in range(m):
	c = 1
	for i in range(1, n):
		if ml[i][j] < ml[i - 1][j]:
			for x in range(i - c, i):
				maxEnd[x] = max(i, maxEnd[x])
			c = 1
		else:
			c += 1
	for x in range(n - c, n):
		maxEnd[x] = max(n, maxEnd[x])
k = iinp()
for i in range(k):
	(l, r) = mp()
	l -= 1
	print('Yes' if maxEnd[l] >= r else 'No')


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7

def LI():
	return list(map(int, input().split()))

def II():
	return int(input())

def LS():
	return input().split()

def S():
	return input()

def main():
	(n, m) = LI()
	a = [LI() for _ in range(n)] + [[-1] * m]
	rr = list(range(n))
	for j in range(m):
		l = 0
		for r in range(1, n + 1):
			if a[r][j] < a[r - 1][j]:
				while l < r:
					if rr[l] < r - 1:
						rr[l] = r - 1
					else:
						l = r
						break
					l += 1
	k = II()
	(l, r) = LI()
	t = ''
	if rr[l - 1] >= r - 1:
		t = 'Yes'
	else:
		t = 'No'
	for _ in range(k - 1):
		(l, r) = LI()
		if rr[l - 1] >= r - 1:
			t += '\nYes'
		else:
			t += '\nNo'
	return t
print(main())


from sys import stdin
(n, m) = [int(i) for i in stdin.readline().split()]
arr = [[int(i) for i in stdin.readline().split()] for _ in range(n)]
temp = [[1 for i in range(m)] for _ in range(n)]
for i in range(m):
	for j in range(n - 2, -1, -1):
		if arr[j][i] <= arr[j + 1][i]:
			temp[j][i] += temp[j + 1][i]
l = [0] * (n + 1)
for i in range(n):
	for j in range(m):
		l[i + 1] = max(l[i + 1], temp[i][j])
k = int(input())
for i in range(k):
	(l1, r) = [int(i) for i in stdin.readline().split()]
	if l[l1] >= r - l1 + 1:
		print('Yes')
	else:
		print('No')


(n, m) = [int(x) for x in input().split()]
arr = [[int(x) for x in input().split()] for i in range(0, n)]
p = [i for i in range(0, n + 1)]
for j in range(0, m):
	cur = 0
	for i in range(0, n - 1):
		if arr[i][j] <= arr[i + 1][j]:
			p[i + 1] = min(cur, p[i + 1])
		else:
			cur = i + 1
q = int(input())
res = ''
for _ in range(0, q):
	(a, b) = [int(x) for x in input().split()]
	b -= 1
	a -= 1
	if p[b] <= a:
		res += 'Yes'
	else:
		res += 'No'
	if _ != q - 1:
		res += '\n'
print(res)


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
grid = []
for r in range(n):
	grid.append([int(z) for z in input().split()])
furthest = [[1] * m for i in range(n)]
for y in range(m):
	for x in reversed(range(n - 1)):
		if not grid[x][y] > grid[x + 1][y]:
			furthest[x][y] = furthest[x + 1][y] + 1
last_l = []
for l in range(n):
	last_l.append(max(furthest[l]) + l)
k = int(input())
for query in range(k):
	(l, r) = map(int, input().split())
	if last_l[l - 1] >= r:
		print('Yes')
	else:
		print('No')


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
M = [list(map(int, stdin.readline().split())) for i in range(n)]
depth = [[1] * m for i in range(n)]
for col in range(m):
	for row in range(1, n):
		if M[row][col] >= M[row - 1][col]:
			depth[row][col] = depth[row - 1][col] + 1
max_depth = [max(row) for row in depth]
ans = ''
k = int(input())
for i in range(k):
	(l, r) = map(int, stdin.readline().split())
	if max_depth[r - 1] >= r - l + 1:
		ans += 'Yes\n'
	else:
		ans += 'No\n'
stdout.write(ans)


(n, m) = [int(x) for x in input().split()]
arr = [[int(x) for x in input().split()] for i in range(n)]
val = [[1] * m for i in range(n)]
for i in range(m):
	for j in range(1, n):
		if arr[j][i] >= arr[j - 1][i]:
			val[j][i] = val[j - 1][i] + 1
best = [max(i) for i in val]
ans = ''
t = int(input())
for i in range(t):
	(c, d) = [int(x) for x in input().split()]
	if best[d - 1] >= d - c + 1:
		ans += 'Yes\n'
	else:
		ans += 'No\n'
print(ans)


from sys import stdin, stdout

def main():
	(n, m) = map(int, stdin.readline().split())
	k = []
	for i in range(n):
		k.append(list(map(int, stdin.readline().split())))
	ans = []
	BASE = [1 for i in range(m)]
	ans.append(list(BASE))
	for i in range(1, n):
		ans.append(list(BASE))
		for j in range(m):
			if k[i][j] >= k[i - 1][j]:
				ans[i][j] = ans[i - 1][j] + 1
			else:
				ans[i][j] = 1
	max_ans = [0 for i in range(n)]
	for i in range(n):
		max_ans[i] = max(ans[i])
	k = int(stdin.readline())
	answer = []
	for i in range(k):
		(l, r) = map(int, stdin.readline().split())
		if max_ans[r - 1] >= r - l + 1:
			answer.append('Yes\n')
		else:
			answer.append('No\n')
	stdout.write(''.join(answer))
main()


from sys import stdin
(n, m) = list(map(int, stdin.readline().rstrip().split()))
data = []
for i in range(0, n):
	data.append(list(map(int, stdin.readline().rstrip().split())))
sorted_data = [0] * n
for col in range(0, m):
	mark_r = 0
	cur_r = 1
	st = []
	while cur_r < n:
		if data[cur_r][col] < data[cur_r - 1][col]:
			st.extend([cur_r - 1] * (cur_r - mark_r))
			mark_r = cur_r
		cur_r += 1
	st.extend([cur_r - 1] * (cur_r - mark_r))
	for (index, item) in enumerate(st):
		if sorted_data[index] < st[index]:
			sorted_data[index] = st[index]
q_count = int(stdin.readline().rstrip())
for _ in range(0, q_count):
	(l, r) = [int(x) - 1 for x in stdin.readline().rstrip().split()]
	if sorted_data[l] >= r:
		print('Yes')
	else:
		print('No')


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
dp = [[0 for i in range(m)] for i in range(n)]
k = int(input())
for j in range(m):
	dp[n - 1][j] = n - 1
	a = n - 1
	for i in range(n - 2, -1, -1):
		if l[i][j] > l[i + 1][j]:
			a = i
		dp[i][j] = a
z = [0 for i in range(n)]
for i in range(n):
	for j in range(m):
		z[i] = max(z[i], dp[i][j])
for i in range(k):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if z[a] >= b:
		print('Yes')
	else:
		print('No')


import sys
from math import log2, floor, ceil, sqrt
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
(n, m) = Ri()
arr = []
for i in range(n):
	temp = Ri()
	arr.append(temp)
dp = list2d(n, m, 1)
for i in range(1, n):
	for j in range(m):
		if arr[i][j] >= arr[i - 1][j]:
			dp[i][j] = dp[i - 1][j] + 1
tdp = [0] * n
for i in range(n):
	for j in range(m):
		tdp[i] = max(tdp[i], dp[i][j])
qq = int(ri())
for q in range(qq):
	(a, b) = Ri()
	a -= 1
	b -= 1
	if b - tdp[b] + 1 <= a:
		Yes()
	else:
		No()


from sys import stdin
lines = stdin.readlines()
n = int(lines[0].split(' ')[0])
m = int(lines[0].split(' ')[1])
base_dict = {i + 1: i + 1 for i in range(n)}

def yes_or_no(max_array, ll):
	l = int(ll[0])
	r = int(ll[1])
	if max_array[l - 1] >= r:
		return 'Yes'
	return 'No'
a = [[int(i) for i in x.split(' ')] for x in lines[1:n + 1]]
for i in range(m):
	prev_minimum = 1
	for j in range(1, n):
		if a[j][i] >= a[j - 1][i]:
			if base_dict[prev_minimum] < j + 1:
				base_dict[prev_minimum] = j + 1
		else:
			prev_minimum = j + 1
max_array = [base_dict[i + 1] for i in range(n)]
for i in range(1, n):
	max_array[i] = max(base_dict[i + 1], max_array[i - 1])
k = lines[n + 1]
b = [yes_or_no(max_array, x.split(' ')) for x in lines[n + 2:]]
print('\n'.join(b))


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
ans = [float('infinity')] * n
cou = [0] * m
A = [0] * n
A[0] = list(map(int, stdin.readline().split()))
ans[0] = 0
for j in range(1, n):
	A[j] = list(map(int, stdin.readline().split()))
	for i in range(m):
		if A[j][i] < A[j - 1][i]:
			cou[i] = j
		ans[j] = min(ans[j], cou[i])
k = int(stdin.readline())
for j in range(k):
	(per1, per2) = map(int, stdin.readline().split())
	if ans[per2 - 1] + 1 <= per1:
		stdout.write('Yes')
	else:
		stdout.write('No')
	stdout.write('\n')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
count = [[1 for i in range(m)] for j in range(n)]
for i in range(1, n):
	for j in range(m):
		if a[i][j] >= a[i - 1][j]:
			count[i][j] = count[i - 1][j] + 1
maxx = []
for i in range(n):
	maxx.append(max(count[i]))
for i in range(int(input())):
	(l, r) = map(int, input().split())
	if l == r:
		print('Yes')
		continue
	if maxx[r - 1] >= r - l + 1:
		print('Yes')
	else:
		print('No')


from sys import stdin
(n, m) = map(int, input().split())
a = [list(map(int, stdin.readline().split())) for i in range(n)]
val = [[1] * m for i in range(n)]
for i in range(m):
	for j in range(n - 2, -1, -1):
		if a[j][i] <= a[j + 1][i]:
			val[j][i] = val[j + 1][i] + 1
best = [max(x) for x in val]
k = int(input())
for _ in range(k):
	(l, r) = map(int, stdin.readline().split())
	if best[l - 1] >= r - l + 1:
		print('Yes')
	else:
		print('No')


from sys import stdin
input = stdin.readline
(n, m) = map(int, input().split())
arr = list((list(map(int, input().split())) for _ in range(n)))
dp = [[1 for i in range(m)] for j in range(n)]
for i in range(1, n):
	for j in range(m):
		if arr[i][j] >= arr[i - 1][j]:
			dp[i][j] = dp[i - 1][j] + 1
(dp, all_res) = ([max(i) for i in dp], [])
k = int(input())
quries = list((list(map(int, input().split())) for _ in range(k)))
for (l, r) in quries:
	all_res.append('Yes' if dp[r - 1] >= r - l + 1 else 'No')
print('\n'.join(all_res))


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
M = [[] for i in range(m)]
for i in range(n):
	z = list(map(int, input().split()))
	for i in range(len(z)):
		M[i].append(z[i])
dp = [0 for i in range(n)]
dp[-1] = 1
for i in range(len(M)):
	x = M[i]
	temp = [0 for i in range(len(x))]
	temp[0] = 1
	for i in range(1, len(x)):
		if x[i] >= x[i - 1]:
			temp[i] = 1
		else:
			temp[i] = 2
	re = [0 for i in range(len(temp))]
	re[-1] = 1
	for i in range(len(re) - 2, -1, -1):
		if temp[i + 1] == 2:
			re[i] = 1
		else:
			re[i] = re[i + 1] + 1
	for i in range(len(dp)):
		dp[i] = max(dp[i], re[i])
r = int(input())
dp[-1] = 1
for i in range(r):
	(l, r) = list(map(int, input().split()))
	if dp[l - 1] >= r - l + 1:
		print('Yes')
	else:
		print('No')


(n, m) = map(int, input().split())
l = []
ans = []
for i in range(n):
	k = list(map(int, input().split()))
	l.append(k)
	c = [1] * len(k)
	ans.append(c)
hash = {}
for j in range(m):
	count = 0
	for i in range(1, n):
		if l[i][j] >= l[i - 1][j]:
			ans[i][j] = ans[i - 1][j]
		else:
			ans[i][j] = i + 1
bo = []
q = int(input())
for i in range(n):
	mini = 10 ** 18
	for j in range(m):
		mini = min(ans[i][j], mini)
	bo.append(mini)
lo = []
for i in range(q):
	(a, b) = map(int, input().split())
	try:
		hash[a, b]
	except:
		if a == b:
			lo.append('Yes')
			hash[a, b] = 'Yes'
		elif bo[b - 1] <= a:
			lo.append('Yes')
			hash[a, b] = 'Yes'
		else:
			lo.append('No')
			hash[a, b] = 'No'
	else:
		lo.append(hash[a, b])
print(*lo)


(n, m) = map(int, input().split())
A = []
for _ in range(n):
	A.append(list(map(int, input().split())))
dp = [[1 for _ in range(m)] for _ in range(n)]
best = [1 for _ in range(n)]
for i in range(1, n):
	for j in range(m):
		if A[i][j] >= A[i - 1][j]:
			dp[i][j] = dp[i - 1][j] + 1
			best[i] = max(best[i], dp[i][j])
ans = ''
k = int(input())
for _ in range(k):
	(l, r) = map(int, input().split())
	if best[r - 1] >= r - l + 1:
		ans += 'Yes\n'
	else:
		ans += 'No\n'
print(ans)


import sys
(N, M) = list(map(int, input().split()))
G = [list(map(int, input().split())) for i in range(N)]
rmaxv = [0 for i in range(N)]
for i in range(M):
	reach = [0 for j in range(N)]
	for j in range(N - 1, -1, -1):
		if j + 1 == N or not G[j][i] <= G[j + 1][i]:
			reach[j] = 1
		else:
			reach[j] = reach[j + 1] + 1
		rmaxv[j] = max(rmaxv[j], reach[j])
Q = int(input())
ans = []
for qi in range(Q):
	(L, R) = list(map(int, input().split()))
	if rmaxv[L - 1] >= R - L + 1:
		ans.append('Yes\n')
	else:
		ans.append('No\n')
sys.stdout.write(''.join(ans))


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
values = []
for i in range(n):
	values.append(list(map(int, stdin.readline().split())))
d = {}
questions = []
k = int(stdin.readline())
for i in range(k):
	(l, r) = map(int, stdin.readline().split())
	questions.append((l, r))
for j in range(m):
	(l, r) = (0, 0)
	while r < n:
		if l == r:
			if r in d:
				d[r] = min(d[r], l)
			else:
				d[r] = l
			r += 1
		elif values[r][j] >= values[r - 1][j]:
			if r in d:
				d[r] = min(d[r], l)
			else:
				d[r] = l
			r += 1
		else:
			l = r
for (l, r) in questions:
	l -= 1
	r -= 1
	if r in d and d[r] <= l:
		stdout.write('Yes\n')
	else:
		stdout.write('No\n')


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().strip().split())
arr = [list(map(int, stdin.readline().strip().split())) for i in range(n)]
dp = [[1 for i in range(m)] for i in range(n)]
for i in range(1, n):
	for j in range(m):
		if arr[i][j] >= arr[i - 1][j]:
			dp[i][j] = dp[i - 1][j] + 1
dp = [max(i) for i in dp]
s = []
for q in range(int(stdin.readline())):
	(L, R) = map(int, stdin.readline().strip().split())
	if dp[R - 1] >= R - L + 1:
		s.append('Yes')
	else:
		s.append('No')
stdout.write('\n'.join(s))


import sys
input = sys.stdin.readline
mod = 1000000007

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	(n, m) = map(int, input().split())
	a = []
	fei = []
	maxi = [1 for i in range(n)]
	for i in range(n):
		a.append(list(map(int, input().split())))
		fei.append([1 for j in range(m)])
	for j in range(m):
		prev = 0
		for i in range(1, n):
			if a[i][j] >= a[i - 1][j]:
				fei[i][j] = fei[i - 1][j] + 1
				maxi[i] = max(maxi[i], fei[i][j])
	k = int(input())
	while k:
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		if maxi[r] >= r - l + 1:
			print('Yes')
		else:
			print('No')
		k -= 1
	return
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
arr = []
for i in range(n):
	arr.append(list(map(int, input().split())))
mp = []
for i in range(n):
	mp.append(i + 1)
for i in range(m):
	pre = -1
	st = 0
	for j in range(n):
		if arr[j][i] < pre:
			pre = arr[j][i]
			st = j
			mp[j] = min(mp[j], st)
		else:
			mp[j] = min(mp[j], st)
			pre = arr[j][i]
m = int(input())
for i in range(m):
	(a, b) = map(int, input().split())
	if mp[b - 1] <= a - 1:
		print('Yes')
	else:
		print('No')


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
(n, m) = ilele()
A = []
for i in range(n):
	B = alele()
	A.append(B)
dp = [[1 for j in range(m)] for i in range(n)]
for i in range(1, n):
	for j in range(m):
		if A[i][j] >= A[i - 1][j]:
			dp[i][j] = dp[i - 1][j] + 1
depth = [0]
for i in dp:
	depth.append(max(i))
for _ in range(int(input())):
	(l, r) = ilele()
	if l == r:
		Yy(1)
	else:
		Yy(depth[r] >= r - l + 1)


import os
import sys
from math import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return map(int, input().split())

def array():
	return [int(i) for i in input().split()]

def check(a):
	ansy = 0
	ansx = 0
	ans = []
	for i in range(1, len(a)):
		if a[i] >= a[i - 1]:
			ansy += 1
		else:
			ans.append((ansx, ansy))
			(ansx, ansy) = (i, i)
	if len(ans) == 0 or ans[-1] != (ansx, ansy):
		ans.append((ansx, ansy))
	return ans
(m, n) = value()
mat = []
for i in range(m):
	mat.append(array())
col = []
lst = []
for i in range(n):
	col.append([])
	for j in range(m):
		col[-1].append(mat[j][i])
	lst.append(check(col[-1]))
ans = {}
for i in lst:
	for j in i:
		try:
			ans[j[0]] = max(ans[j[0]], j[1])
		except:
			ans[j[0]] = j[1]
temp = list(ans.keys())
for i in temp:
	for j in range(i, ans[i] + 1):
		try:
			ans[j] = max(ans[i], ans[j])
		except:
			ans[j] = ans[i]
k = int(input())
for i in range(k):
	(l, r) = value()
	l -= 1
	r -= 1
	f = 0
	if r <= ans[l]:
		print('Yes')
	else:
		print('No')


(n, m) = map(int, input().split())
Table = []
for r in range(n):
	row = list(map(int, input().split()))
	Table.append(row)
k = int(input())
Tasklist = []
for task in range(k):
	(l, r) = map(int, input().split())
	Tasklist.append([l, r])
locate = [0] * (n + 1)
locate[n] = n
for c in range(m):
	maxx = n
	for r in range(n - 2, -1, -1):
		if Table[r][c] <= Table[r + 1][c]:
			if locate[r + 1] < maxx:
				locate[r + 1] = maxx
		else:
			maxx = r + 1
			if locate[r + 1] < maxx:
				locate[r + 1] = maxx
for task in range(k):
	Task = Tasklist[task]
	l = Task[0]
	r = Task[1]
	if locate[l] >= r:
		print('Yes')
	else:
		print('No')