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: interview

Starter code:

Solutions:
n, m = list(map(int, input().split()))
M = [list(map(int, input().split())) for r in range(n)]

depth = [[1] * m for r in range(n)]

for c in range(m):
    for r in range(1, n):
        if M[r][c] >= M[r - 1][c]:
            depth[r][c] = depth[r - 1][c] + 1

max_depth = [max(col) for col in depth]

ans = ""
k = int(input())
for i in range(k):
    l, r = list(map(int, input().split()))
    if max_depth[r - 1] >= r - l + 1:
        ans += "Yes\n"
    else:
        ans += "No\n"

print(ans)


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')

def __starting_point():
    solve()
__starting_point()

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

    #print(rr)
    k = II()
    ans = []
    for _ in range(k):
        l,r = LI()
        if rr[l-1] >= r-1:
            ans.append('Yes')
        else:
            ans.append('No')
            
    print('\n'.join(ans))

main()

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

    #print(rr)
    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())

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)


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(n-2,-1,-1):
		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[c-1]>=d-c+1:
		ans += "Yes\n"
	else:
		ans += "No\n"
print(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)]#a 2d array of size [n][m]
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#if in increasing order increase value by 1
               
best=[max(i) for i in v]#to store largest value in row
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):#compare that largest value
          ans+="Yes\n"
     else :
          ans+="No\n"

print(ans)



#---------------EL FUTURO ES INCIERTO--------------#
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
	#end for
#end for

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"
#end for

print (res)


#!/usr/bin/env python3
def ri():
    return list(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
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

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")


import sys
n,m = list(map(int,sys.stdin.readline().rstrip().split()))
matrix = []
for _ in range(n):
	row = list(map(int,sys.stdin.readline().rstrip().split()))
	matrix.append(row)

# initialize table
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 = [0] * n
# for i in range(n):
# 	lst = [A[i][j] for j in range(m)]
# 	rows[i] = max(lst)
rows = [max(row) for row in A]

ans = ""
k = int(sys.stdin.readline().rstrip())
for _ in range(k):
	l,r = list(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(n)]

val = [ [1]*m for i in range(n)]
for i in range(m):
	for j in range(n-2,-1,-1):
		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[c-1]>=d-c+1:
		ans += "Yes\n"
	else:
		ans += "No\n"
print(ans)




# Made By Mostafa_Khaled


import sys
from math import log2,floor,ceil,sqrt
# import bisect
# from collections import deque

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
input = stdin.readline
n, m = list(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')