题目描述

给定一个长度为 $n$ 的数组 $a$，初始时全部为 $0$。同时给定 $m$ 个（不一定不同的）区间。每个区间由两个数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）定义，表示数组 $a$ 的子数组 $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$。

我们称区间 $l_i, r_i$ 是“美丽的”，如果该区间内 $1$ 的数量严格大于 $0$ 的数量。例如，如果 $a = [1, 0, 1, 0, 1]$，则区间 $[1, 5]$ 是美丽的（$1$ 的数量为 $3$，$0$ 的数量为 $2$），但区间 $[3, 4]$ 不是美丽的（$1$ 的数量为 $1$，$0$ 的数量为 $1$）。

你还有 $q$ 次修改操作。每次修改给出一个 $1 \le x \le n$，表示将 $a_x$ 赋值为 $1$。

你需要找出在第几次修改后，至少有一个给定的区间变成美丽的；如果所有 $q$ 次修改后仍没有任何区间变成美丽的，则输出 $-1$。

输入格式

第一行包含一个整数 $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$。

说明/提示

在第一个样例中，前两次修改后没有任何美丽区间，但第三次修改后，区间 $[1; 5]$ 内有 $3$ 个 $1$ 和 $2$ 个 $0$，因此答案为 $3$。

在第二个样例中，所有修改后都没有美丽区间。

由 ChatGPT 4.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