Alyona and Spreadsheet
time limit per test 1 second memory limit per test 256 megabytes
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 ai,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 ai,j≤ai+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 ai,j≤ai+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!

传送门:CF777C

Input

The first line of the input contains two positive integers n and m (1≤n·m≤100000) — 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 ai, j (1 ≤ ai, j ≤ 109). The next line of the input contains an integer k (1≤k≤100000) — the number of task that teacher gave to Alyona. The i-th of the next k lines contains two integers li and ri (1≤li≤ri≤n).

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
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

Sample Output

1
2
3
4
5
6
Yes
No
Yes
Yes
Yes
No

题解

先扫一遍记录index[i][j]表示第i行第j个在它那一列前面有多少个连续的,包括自己 然后有10W条查询,必须要达到O(1) 所以再建一个数组保存每一行中列最大连续的数目
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
int n=sc.nextInt();
int m=sc.nextInt();
int [][]maze=new int[n+1][m+1];
int [][]index=new int[n+1][m+1];
int []row=new int[n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
maze[i][j]=sc.nextInt();
}
}
int k=sc.nextInt();
for(int j=1;j<=m;j++){
index[1][j]=1;
for(int i=2;i<=n;i++){
if(maze[i][j]>=maze[i-1][j]){
index[i][j]=index[i-1][j]+1;
}
else{
index[i][j]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
row[i]=Math.max(row[i], index[i][j]); 多出一个数组保存每行最大往下连续的个数,使查询保持O(1)
}
}
for(int o=1;o<=k;o++){
int l=sc.nextInt();
int r=sc.nextInt();
int flag=0;
if(row[r]>=r-l+1) flag=1;
if(flag==1) pw.println("Yes");
else pw.println("No");
}
pw.flush();
}
}

}
class FastScanner {
BufferedReader br;
StringTokenizer st;

public FastScanner() {
try {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer("");
} catch (Exception e) {
e.printStackTrace();
}
}

public boolean hasNext() {
while (!st.hasMoreTokens()) {
String line = nextLine();
if (line == null) {
return false;
}
st = new StringTokenizer(line);
}
return true;
}

public String next() {
if (st.hasMoreTokens())
return st.nextToken();
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
e.printStackTrace();
}
return st.nextToken();
}

public int nextInt() {
return Integer.parseInt(next());
}

public long nextLong() {
return Long.parseLong(next());
}

public double nextDouble() {
return Double.parseDouble(next());
}

public String nextLine() {
String line = "";
try {
line = br.readLine();
} catch (Exception e) {
e.printStackTrace();
}
return line;
}

public Integer[] nextIntegerArray(int n) {
Integer[] a = new Integer[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}

public int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}

public char[] nextCharArray() {
return nextLine().toCharArray();
}
}