7. Marťan a snehová búrka

Ako všetci dobre vieme, Marťania náš často navštevujú vo svojich lietajúcich tanieroch. Marťan Denys práve dostal vodičský preukaz. Rozhodol sa ho naplno využiť a priletieť na Slovensko po legendárnu kofolu a horalky (tie na Marse nedostať). To však precenil svoje letecké schopnosti, pretože zabudol na ďalšiu vec, ktorú na Marse nemajú¹ – atmosféru. A Denys si to nevedomky namieril rovno do snehovej búrky.

Neostávalo mu nič iné, ako zavolať do KSP² a oznámiť svoje núdzové pristátie na jednej z ich pristávacích dráh. Tisícky KSPákov na ňu okamžite vybehli v snahe byť prvými, ktorí Denysa privítajú. To však nie je úplne jednoduché – Denysa snehová búrka kotrmáca hore-dolu, a tak síce dokáže technikou Kontrolovaného Samovoľného Pádu zaručiť, že “pristane” na dráhe, nevie však, kde na nej sa nakoniec ocitne.

Každý vedec si teda vybral nejaké miesto na dráhe, na ktoré sa postavil a úzkostlivo čaká, kde Denys nakoniec skončí. Hneď ako pristane, každý z nich sa plnou rýchlosťou rozbehne jeho smerom.

KSP programátorom sa podarilo pomocou simulácie vypočítať niekoľko pravdepodobných miest na dráhe, na ktorých by Denys mohol skončiť. KSPákov teraz pre každé z týchto miest nesmierne zaujíma, kto by sa k Denysovi dostal ako prvý, keby Denys pristál na tomto mieste. KSP potrebuje vašu pomoc!

Úloha

Pristávacia dráha je veľmi dlhá, rovná cesta. Pozíciu každého KSPáka či možného Denysovho pristátia si preto vieme jednoducho vyjadriť vzdialenosťou od jej začiatku v metroch.

Každý KSPák sa postavil na nejaký meter \(x_i\) na pristávacej dráhe a keď Denys pristane, rozbehne sa k nemu rýchlosťou \(v_i\) metrov za sekundu. Pre každú polohu pristátia v zozname zistite, ktorí KSPáci by Denysa privítali ako prví, keby pristál na nej.

Formát vstupu

V prvom riadku vstupu sú dve celé čísla \(n, q\) (\(1 \leq n,q \leq 300\,000\)): počet KSPákov a počet možných miest, na ktorých Denys možno nakoniec pristane. KSPáci sú očíslovaní od \(1\) po \(n\).

Nasleduje \(n\) riadkov, \(i\)-ty z nich obsahuje dve celé čísla \(x_i, v_i\) – začiatočnú polohu a rýchlosť KSPáka číslo \(i\). Dvojice \(x_i, v_i\) sú navzájom rôzne. Platí \(0 \leq x_i < 10^9\) a \(0 < v_i \leq 10^9\).

Nakoniec, v poslednom riadku vstupu je \(q\) medzerou oddelených celých čísel \(y_1, y_2, \dots, y_q\) (\(0 \leq y_j < 10^9\)) – zoznam možných pristávacích miest. Sú navzájom rôzne a žiadne z nich sa nerovná začiatočnej polohe niektorého KSPáka.

Formát výstupu

Vypíšte \(q\) riadkov. V \(j\)-tom z nich vypíšte počet KSPákov, ktorí by Denysa privítali ako prví, keby pristál na \(y_j\)-tom metri pristávacej dráhy – teda počet takých \(i\), pre ktoré \(1 \leq i \leq n\) a zlomok \(\frac{|x_i - y_j|}{v_i}\) je najmenší cez všetky \(i\). Následne do toho istého riadku vypíšte čísla všetkých takýchto KSPákov, zoradené vzostupne.

Hodnotenie

Pre jednotlivé testovacie sady platia nasledovné obmedzenia:

Navyše, v sadách \(3,4,5\) platí \(x_i < y_j\) pre všetky zmysluplné \(i, j\) – teda všetci KSPáci stoja naľavo od všetkých možných pristávacích miest.

Príklady

Input:

4 7
10 5
30 1
20 4
100 1
5 31 22 15 85 60 61

Output:

1 1
1 2
1 3
1 1
2 1 4
2 1 3
1 1

Input:

3 4
10 5
30 1
20 4
31 85 60 61

Output:

1 2
1 1
2 1 3
1 1

Toto je príklad vstupu v sadách 3,4,5