Сіз матрёшка қуыршақтарын сататын дүкен ашуды жоспарлап отырсыз. Сіз зауыттан $1$-ден $N$-ге дейін нөмірленген $N$ матрёшка қуыршағына тапсырыс бердіңіз. $i$-ші ($1 \le i \le N$) матрёшка қуыршағын табанының диаметрі $R_i$ см және биіктігі $H_i$ см болатын іші қуыс тік дөңгелек цилиндр деп санауға болады.

Матрёшка қуыршақтарын бірінің ішіне бірін салып сақтауға болады. Әрбір матрёшка қуыршағының ішіне ең көп дегенде бір басқа матрёшка қуыршағын салуға болады, ол үшін ішіне салынатын қуыршақтың табанының диаметрі де, биіктігі де сыртқы қуыршақтың сәйкес өлшемдерінен қатаң түрде кіші болуы керек. Басқа қуыршақтың ішіне салынған қуыршақтың өзі де ішіне тағы бір қуыршақты қамтуы мүмкін.

Бір күні сіз зауыттан хабарлама алдыңыз. Олар барлық $N$ қуыршақты бірден дайындай алмайтындықтан, сізге табанының диаметрі кемінде $A$ см және биіктігі ең көп дегенде $B$ см болатын барлық қуыршақтарды жіберетін болды.

$A$ мен $B$ мәндері кенеттен өзгеруі мүмкін. Сондықтан сіз $Q$ жұптың $(A_j, B_j)$ ($1 \le j \le Q$) әрқайсысы үшін келген қуыршақтарды сақтау үшін бірінің ішіне бірін салғанда, басқа ешбір қуыршақтың ішіне салынбаған матрёшка қуыршақтарының ең аз санын алдын ала есептеп қоюды ұйғардыңыз.

Кіріс деректер

Стандартты кірістен келесі деректерді оқыңыз:

• Бірінші жолда бос орын арқылы бөлінген екі бүтін сан $N$ және $Q$ берілген. Бұл тапсырыс берілген $N$ матрёшка қуыршағы және $(A, B)$ мәндерінің $Q$ жұбы бар екенін білдіреді.
• Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бос орын арқылы бөлінген екі бүтін сан $R_i$ және $H_i$ берілген. Бұл $i$-ші қуыршақтың табанының диаметрі $R_i$ см және биіктігі $H_i$ см екенін білдіреді.
• Келесі $Q$ жолдың $j$-ші жолында ($1 \le j \le Q$) бос орын арқылы бөлінген екі бүтін сан $A_j$ және $B_j$ берілген.

Шығыс деректер

Шығыс $Q$ жолдан тұруы керек. $j$-ші жолда ($1 \le j \le Q$) $(A_j, B_j)$ жұбы үшін келген қуыршақтарды сақтау үшін бірінің ішіне бірін салғанда, басқа ешбір қуыршақтың ішіне салынбаған матрёшка қуыршақтарының ең аз саны шығарылуы тиіс.

Шектеулер

Барлық кіріс деректер келесі шарттарды қанағаттандырады:

• $1 \le N \le 200\,000$.
• $1 \le Q \le 200\,000$.
• $1 \le R_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le H_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le A_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).

Ішкі есептер

Ішкі есеп 1 [11 ұпай]

• $N \le 10$.
• $Q = 1$.

Ішкі есеп 2 [15 ұпай]

• $N \le 100$.
• $Q = 1$.

Ішкі есеп 3 [25 ұпай]

• $N \le 2\,000$.
• $Q \le 2\,000$.

Ішкі есеп 4 [49 ұпай]

• Қосымша шектеулер жоқ.

Мысалдар

Кіріс деректер 1

7 3
9 5
3 7
10 6
5 10
2 6
10 10
4 1
10 5
3 5
3 9

Шығыс деректер 1

0
1
2

Ескертпе

• $(A, B) = (10, 5)$ болғанда, табанының диаметрі кемінде $10$ см және биіктігі ең көп дегенде $5$ см болатын қуыршақтар жоқ, сондықтан $0$ шығарылады.
• $(A, B) = (3, 5)$ болғанда, табанының диаметрі кемінде $3$ см және биіктігі ең көп дегенде $5$ см болатын 1-ші және 7-ші қуыршақтар келеді. 7-ші қуыршақты 1-ші қуыршақтың ішіне салып сақтауға болады. Басқа ешбір қуыршақтың ішіне салынбаған қуыршақтардың ең аз саны — $1$.
• $(A, B) = (3, 9)$ болғанда, табанының диаметрі кемінде $3$ см және биіктігі ең көп дегенде $9$ см болатын 1-ші, 2-ші, 3-ші және 7-ші қуыршақтар келеді. Бұл жағдайда 7-ші қуыршақты 1-ші қуыршақтың ішіне, ал 1-ші қуыршақты 3-ші қуыршақтың ішіне салып сақтауға болады. Басқа ешбір қуыршақтың ішіне салынбаған қуыршақтардың ең аз саны — $2$.

Кіріс деректер 2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

Шығыс деректер 2

3
1
3
5
0
2
1
3