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

У вас есть массив $$$a$$$, состоящий из $$$n$$$ нулей. Также, вам дан набор из $$$m$$$ необязательно различных отрезков. Каждый отрезок задается двумя числами $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) и представляет собой подмассив $$$a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$$$ массива $$$a$$$.

Назовём отрезок $$$l_i, r_i$$$ красивым, если количество единиц на этом отрезке строго больше, чем количество нулей. Например, если $$$a = [1, 0, 1, 0, 1]$$$, тогда отрезок $$$[1, 5]$$$ является красивым (количество единиц равно $$$3$$$, количество нулей равно $$$2$$$), но отрезок $$$[3, 4]$$$ не является красивым (количество единиц равно $$$1$$$, количество нулей равно $$$1$$$).

У вас также есть $$$q$$$ изменений. Каждое изменение задано числом $$$1 \le x \le n$$$, это означает, что вы должны присвоить элементу $$$a_x$$$ значение $$$1$$$.

Вы должны найти первое изменение, после которого хотя бы один из $$$m$$$ заданных отрезков становится красивым, или сообщить, что ни один из них не является красивым после применения всех $$$q$$$ изменений.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 10^5$$$) — размер массива $$$a$$$ и количество отрезков соответственно.

Далее следует $$$m$$$ строк, состоящих из двух чисел $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — границы отрезков.

В следующей строке дано целое число $$$q$$$ ($$$1 \le q \le n$$$) — количество измений.

В следующих $$$q$$$ строках содержится по одному целому числу $$$x$$$ ($$$1 \le x \le n$$$) — индекс элемента массива, который нужно приравнять к $$$1$$$. Гарантируется, что все индексы в запросах различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — наименьший номер изменения, после которого хотя бы один из отрезков окажется красивым, или $$$-1$$$, если ни один отрезок не станет красивым.

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

В первом примере, после первых двух изменений не будет красивых отрезков, а после третьего изменения на отрезке $$$[1; 5]$$$ будет 3 единицы и 2 нуля, получается ответ 3.

Во втором примере у нас не будет красивых отрезков.