Ночью на сибирской трассе одновременно сошло \(n\) снежных заносов. Каждый занос перекрывает участок дороги между километровыми отметками \(a_i\) и \(b_i\) включительно. Сообщения о заносах поступали диспетчеру по рации в произвольном порядке, поэтому \(a_i\) может оказаться как меньше, так и больше \(b_i\): занос покрывает все километровые отметки от \(\min(a_i, b_i)\) до \(\max(a_i, b_i)\) включительно.
К утру с трассы поступили \(m\) запросов от водителей. Каждый водитель называет километровую отметку \(p_j\), на которой он сейчас находится, и просит сообщить, сколько заносов перекрывают этот километр. Помогите диспетчеру быстро ответить на все запросы.
Формат входных данных
В первой строке записаны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 50\,000\)) — количество заносов и количество запросов.
В следующих \(n\) строках записаны по два целых числа \(a_i\) и \(b_i\) (\(-10^9 \le a_i, b_i \le 10^9\)) — концы участка \(i\)-го заноса в произвольном порядке.
В последней строке через пробел записаны \(m\) целых чисел \(p_1, p_2, \ldots, p_m\) (\(-10^9 \le p_j \le 10^9\)) — километровые отметки, о которых спрашивают водители.
Формат выходных данных
Выведите \(m\) целых чисел через пробел: для каждой отметки \(p_j\) — количество заносов, перекрывающих этот километр.
Примечание
Точка считается принадлежащей участку с концами \(a\) и \(b\), если выполняется неравенство \(\min(a, b) \le p \le \max(a, b)\). Совпадение с границей засчитывается.
| № | Входные данные | Выходные данные |
|
1
|
3 2
0 5
-3 2
7 10
1 6
|
2 0
|
|
2
|
1 3
10 -10
-100 100 0
|
0 0 1
|