Даны \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач