Kangury [A]

Limit pamięci: 32 MB

Bajtazar jedzie do Australii fotografować kangury. Zaczął już przygotowania do wyjazdu i zorientował się, że może mieć problem z zabraniem całego swojego sprzętu fotograficznego. Bajtazar posiada kolekcję obiektywów o różnorodnych parametrach. Każdy obiektyw najlepiej nadaje się do fotografowania obiektów jedynie w pewnym zakresie odległości od aparatu; kangury znajdujące się w odległości spoza tego zakresu albo nie zmieszczą się w kadrze, albo będą zbyt małe.

Bajtazar zna również dokładny plan podróży: jego wyprawa przebiegać będzie przez szereg punktów obserwacyjnych. Przewodnicy Bajtazara powiedzieli mu już, jak wygląda każdy z punktów i w jakim przedziale odległości powinien się on spodziewać kangurów.

Teraz Bajtazar zastanawia się, które obiektywy zabrać ze sobą. Ponieważ bardzo nie lubi on zmieniać obiektywu w aparacie, dla każdego obiektywu chciałby obliczyć, jaki jest najdłuższy ciąg kolejnych punktów obserwacyjnych, w których ten obiektyw będzie przydatny. Obiektyw jest przydatny w danym punkcie, jeśli istnieje pewna odległość, w której można spodziewać się kangurów i która mieści się w przedziale optymalnych odległości dla tego obiektywu. Napisz program, który rozwiąże problem Bajtazara.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (, ) oznaczające liczbę punktów obserwacyjnych oraz liczbę obiektywów w kolekcji Bajtazara. Kolejne wierszy zawiera po dwie liczby całkowite , (), które oznaczają, że w -tym punkcie obserwacyjnym kangury mogą pojawić się w odległości od do stóp bajtockich, włącznie.

Dalej następuje wierszy, z których każdy zawiera dwie liczby całkowite , (). Oznaczają one, że -ty obiektyw najlepiej sprawdza się przy fotografowaniu kangurów w odległości od do stóp bajtockich, włącznie.

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy, z których -ty powinien zawierać liczbę punktów widokowych w najdłuższym spójnym fragmencie wyprawy, w którym Bajtazar może fotografować kangury za pomocą obiektywu numer . Obiektywy numerujemy zgodnie z kolejnością z wejścia.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

2
3
0

Autorzy zadania: Jakub Łącki, Jakub Radoszewski.