Smokogąsienice

Limit pamięci = 128 MB

W Bajtocji zapanowała plaga smokogąsienic, które są podobne do zwykłych gąsienic, ale są wielkie jak smoki. Do przepędzenia ich król Bajtazar wezwał rycerzy, którzy są tradycyjnym środkiem do walki ze smokami.

Rycerze wyruszają z zamku Bajtazara w punkcie (0,0). Gąsienice znajdują się na północ (dodatni kierunek osi Y) od zamku, południa (Y <= 0) broni Mur Bajtocki.

Rycerze szarżują na koniu (bądź bez niego) i irytują napotkane na swojej trasie gąsienice dokuczliwym dźganiem mieczem - po czym kontynuują podróż tym samym torem w poszukiwaniu kolejnych przeciwników. Konstrukcja zbroi oraz fakt, że rycerz w hełmie widzi tylko do przodu, powodują, że rycerze nie zmieniają kierunku ruchu - czyli poruszają się po półprostych o początku w zamku Bajtazara. Ustawiają się wybranym kierunku dzięki obrotowej platformie.

Po pokonaniu zagrożenia, Bajtazar zwołał rycerzy, aby ich nagrodzić (ciekawe jak wrócili, skoro nie mogą zawracać). Nagroda zależy od waleczności. Odważni rycerze ruszyli w kierunku gąsienic, a tchórze wybrali kierunki pozwalające uniknąć walki.

Bajtazar wie, gdzie były gąsienice (a te są bardzo powolne i nie zmieniały położenia) oraz kierunki, w których wyruszyli rycerze. Na podstawie tych danych znajdź liczbę gąsienic, z którymi walczył każdy z rycerzy.

Wejście

Dane są liczby gąsienic G i rycerzy R (1 <= L , S <= 500 000).
W kolejnych G liniach opisane są gąsienice:
"X_1i Y_1i X_2i Y_2i" oznacza gąsienicę o końcach w (X_1i,Y_1i) (X_2i,Y_2i). Gąsienica jest odcinkiem.
W R liniach opisane są kierunki rycerzy:
"X_i Y_i" oznacza, że rycerz poruszał się od zamku (0,0) w kierunku punktu (X_i,Y_i).
(-10^6 <= X <= 10^6) (1 <= Y <= 10^9)

Wyjście

Dla każdego rycerza należy podać liczbę smokogąsienic, z którymi walczył (czyli tych, które mają conajmniej jeden punkt wspólny z torem ruchu rycerza).
Wyniki należy podać w takiej kolejności, w jakiej rycerze byli opisywani na wejściu.

Przykład

IN:
IN:
4 2

3 1 3 4
-1 3 2 3
-4 6 7 6
-2 1 -4 4

1 1
-2 3

OUT:
2 1
[Zgłoś rozwiązanie]   [Moje zgłoszenia]