Նարեն և աղյուսակը
Ինֆորմատիկայի դասերին փոքրիկ աղջիկ Նարեն շատ հայտնի մի ծրագրի միջոցով սովորում է աղյուսակներ խմբագրել։
Նա այժմ ունի
n տողերից և m սյուներից կազմված աղյուսակ։ Աղյուսակում i-րդ տողի j-րդ տեղում գտնվող տարրը նշանակենք a[i][j]-ով։ Կասենք, որ աղյուսակը տեսակավորված է չնվազման կարգով ըստ j-րդ սյան, եթե a[i][j] ≤ a[i+1][j] 1-ից n-1 բոլոր i-երի համար։Ուսուցչուհին Նարեին
k առաջադրանք է տվել։ Յուրաքանչյուր առաջադրանքի համար Նարեն ստացել է երկու l և r թվեր, և պետք է պատասխանի հետևյալ հարցին․ եթե աղյյուսակից բոլոր տողերը հեռացնենք և թողնենք միայն l-ից r, ներառյալ, տողերը, ապա այն տեսակավորված կլինի՞ չնվազման կարգով ըստ որևէ սյան։ Այլ խոսքերով ասած, գոյություն ունի՞, արդյոք, այնպիսի j, որ a[i][j] ≤ a[i+1][j] l-ից r-1 բոլոր i-երի համար։Օգնեք Նարեին, որ կարողանա կատարել բոլոր առաջադրանքները։
Մուտքային տվյալներ
Առաջին տողում տրված են n և m
(1 ≤ n*m ≤ 100000) դրական ամբողջ թվերը` աղյուսակում տողերի և սյուների քանակները, համապատասխանաբար։Հաջորդ n տողերից յուրաքանչյուրում տրված է m թիվ
(1 ≤ a[i][j] ≤) : Հաջորդ տողում տրված է առաջադրանքների k քանակը (1 ≤ k ≤ 100 000), որ Նարեն պիտի կատարի։ Հաջորդ k տողերից յուրանչուրում տրված են երկու l և r թվերի 1-ից n սահմաններից։Ելքային տվյալներ
Ելքում պետք է արտածել k տող։ i-րդ տողում
(1 ≤ i ≤ k) պետք է արտածել Yes բառը, եթե համապատասխան առաջարդանքի պատասխանը «այո» է, հակառակ դեպքում պետք է արտածել No բառը։Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր). Օրինակը
- Ենթախնդիր 1 (10 միավոր). 1 ≤ n, k ≤ 100 և m = 1
- Ենթախնդիր 2 (40 միավոր). 1 ≤ n, m, k ≤ 100
- Ենթախնդիր 3 (50 միավոր). Լրացուցիչ սահմանափակումներ չկան։
Օրինակ
Մուտք | Ելք |
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 | Yes
No
Yes
Yes
Yes
No |
Բացատրություն
Օրինակում աղյուսակը ըստ որևէ սույնի տեսակավորված չէ, բայց, օրինակ 1-3 տողերը տեսակավորված են ըստ առաջին սյան, իսկ 4-5 տողերն ըստ 3 սյան։
Աղբյուրը՝ Հանրապետական 2022
Constraints
Time limit: 0.2 seconds
Memory limit: 512 MB
Output limit: 1 MB