Codeforces Round 216 (Div. 2) |
---|
Закончено |
Валера очень любит отрезки. Недавно он придумал одну интересную задачу.
На координатной прямой есть n отрезков, i-й отрезок начинается в позиции li и заканчивается в позиции ri (будем обозначать его [li, ri]). Требуется обработать m запросов, каждый из которых состоит из числа cnti и набора cnti координат точек, расположенных на координатной прямой. Ответом на запрос является количество таких отрезков, что каждый из них содержит хотя бы одну точку из набора. Отрезок [l, r] содержит точку q, если l ≤ q ≤ r.
Решение этой задачи Валере показалось слишком сложным. Поэтому он обратился за помощью к вам. Помогите Валере.
В первой строке задано два целых числа n, m (1 ≤ n, m ≤ 3·105) — количество отрезков на координатной прямой и количество запросов.
В следующих n строках задано описание отрезков. Строка номер i содержит два целых положительных числа li, ri (1 ≤ li ≤ ri ≤ 106) — границы i-го отрезка.
В следующих m строках содержится описание запросов по одному на строке. Каждая строка начинается с целого числа cnti (1 ≤ cnti ≤ 3·105) — количество точек в i-м запросе. Далее в строке идут cnti различных целых положительных чисел p1, p2, ..., pcnti (1 ≤ p1 < p2 < ... < pcnti ≤ 106) — координаты точек в i-м запросе.
Гарантируется, что суммарное количество точек во всех запросах не превосходит 3·105.
Выведите m целых неотрицательных чисел, где i-e число — ответ на i-й запрос.
3 3
1 3
4 5
6 7
3 1 4 7
2 4 5
1 8
3
1
0
Название |
---|