Даны \(n\) отрезков в формате \([l; r]\) на числовой прямой.
Также даны \(m\) запросов в формате \([x; y]\). Какое минимальное число отрезков надо взять так, чтобы каждая точка (не обязательно целочисленная) от \(x\) до \(y\) была покрыта хотя бы одним из них?
Если нельзя выбрать отрезки так, чтобы каждая точка от \(x\) до \(y\) была покрыта, тогда выведите -1 на этот запрос.
Выходные данные
Выведите \(m\) целых чисел. \(i\)-е число должно быть ответом на \(i\)-й запрос: либо минимальное число отрезков необходимое, чтобы каждая точка (не обязательно целочисленная) от \(x_i\) до \(y_i\) была покрыта хотя бы одним из них, либо -1, если нельзя выбрать отрезки так, чтобы каждая точка от \(x_i\) до \(y_i\) была покрыта.
Примечание
В первом примере три запроса:
- запрос \([1; 3]\) может быть покрыт отрезком \([1; 3]\);
- запрос \([1; 4]\) может быть покрыт отрезками \([1; 3]\) и \([2; 4]\). Нельзя покрыть \([1; 4]\) одним отрезком;
- запрос \([3; 4]\) может быть покрыт отрезком \([2; 4]\); Не важно, что покрыты какие-то точки вне данного запроса.
Во втором примере четыре запроса:
- запрос \([1; 2]\) может быть покрыт отрезком \([1; 3]\). Обратите внимание, что можно выбрать любой из отрезков \([1; 3]\);
- запрос \([1; 3]\) может быть покрыт отрезком \([1; 3]\);
- запрос \([1; 4]\) не может быть покрыт никаким набором отрезков;
- запрос \([1; 5]\) не может быть покрыт никаким набором отрезков. Обратите внимание, что отрезки \([1; 3]\) и \([4; 5]\) вместе не покрывают \([1; 5]\), потому что даже нецелые точки должны быть покрыты. Здесь \(3.5\) не покрыта, например.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
1 3
2 4
1 3
1 4
3 4
|
1
2
1
|
|
2
|
3 4
1 3
1 3
4 5
1 2
1 3
1 4
1 5
|
1
1
-1
-1
|