Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Минимальное покрытие отрезков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны $$$n$$$ отрезков в формате $$$[l; r]$$$ на числовой прямой.

Также даны $$$m$$$ запросов в формате $$$[x; y]$$$. Какое минимальное число отрезков надо взять так, чтобы каждая точка (не обязательно целочисленная) от $$$x$$$ до $$$y$$$ была покрыта хотя бы одним из них?

Если нельзя выбрать отрезки так, чтобы каждая точка от $$$x$$$ до $$$y$$$ была покрыта, тогда выведите -1 на этот запрос.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — количество отрезков и количество запросов, соответственно.

В каждой из следующих $$$n$$$ строк записаны по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \le l_i < r_i \le 5 \cdot 10^5$$$) — данные отрезки.

В каждой из следующих $$$m$$$ строк записаны по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \le x_i < y_i \le 5 \cdot 10^5$$$) — запросы.

Выходные данные

Выведите $$$m$$$ целых чисел. $$$i$$$-е число должно быть ответом на $$$i$$$-й запрос: либо минимальное число отрезков необходимое, чтобы каждая точка (не обязательно целочисленная) от $$$x_i$$$ до $$$y_i$$$ была покрыта хотя бы одним из них, либо -1, если нельзя выбрать отрезки так, чтобы каждая точка от $$$x_i$$$ до $$$y_i$$$ была покрыта.

Примеры
Входные данные
2 3
1 3
2 4
1 3
1 4
3 4
Выходные данные
1
2
1
Входные данные
3 4
1 3
1 3
4 5
1 2
1 3
1 4
1 5
Выходные данные
1
1
-1
-1
Примечание

В первом примере три запроса:

  1. запрос $$$[1; 3]$$$ может быть покрыт отрезком $$$[1; 3]$$$;
  2. запрос $$$[1; 4]$$$ может быть покрыт отрезками $$$[1; 3]$$$ и $$$[2; 4]$$$. Нельзя покрыть $$$[1; 4]$$$ одним отрезком;
  3. запрос $$$[3; 4]$$$ может быть покрыт отрезком $$$[2; 4]$$$; Не важно, что покрыты какие-то точки вне данного запроса.

Во втором примере четыре запроса:

  1. запрос $$$[1; 2]$$$ может быть покрыт отрезком $$$[1; 3]$$$. Обратите внимание, что можно выбрать любой из отрезков $$$[1; 3]$$$;
  2. запрос $$$[1; 3]$$$ может быть покрыт отрезком $$$[1; 3]$$$;
  3. запрос $$$[1; 4]$$$ не может быть покрыт никаким набором отрезков;
  4. запрос $$$[1; 5]$$$ не может быть покрыт никаким набором отрезков. Обратите внимание, что отрезки $$$[1; 3]$$$ и $$$[4; 5]$$$ вместе не покрывают $$$[1; 5]$$$, потому что даже нецелые точки должны быть покрыты. Здесь $$$3.5$$$ не покрыта, например.