CF1843E.Tracking Segments

You are given an array $a$ consisting of $n$ zeros. You are also given a set of $m$ not necessarily different segments. Each segment is defined by two numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) and represents a subarray $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ of the array $a$.

Let's call the segment $l_i, r_i$ beautiful if the number of ones on this segment is strictly greater than the number of zeros. For example, if $a = [1, 0, 1, 0, 1]$, then the segment $[1, 5]$ is beautiful (the number of ones is $3$, the number of zeros is $2$), but the segment $[3, 4]$ is not is beautiful (the number of ones is $1$, the number of zeros is $1$).

You also have $q$ changes. For each change you are given the number $1 \le x \le n$, which means that you must assign an element $a_x$ the value $1$.

You have to find the first change after which at least one of $m$ given segments becomes beautiful, or report that none of them is beautiful after processing all $q$ changes.

你有一个由 $n$ 个零组成的数组 $a$。同时，你被给定一个包含 $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$。

你需要找出第一次修改操作，使得在该次操作之后，所给的 $m$ 个区间中至少有一个变为优美的；如果处理完全部 $q$ 次修改后仍没有任何区间变为优美，则报告不存在这样的操作。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le m \le n \le 10^5$) — the size of the array $a$ and the number of segments, respectively.

Then there are $m$ lines consisting of two numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) —the boundaries of the segments.

The next line contains an integer $q$ ($1 \le q \le n$) — the number of changes.

The following $q$ lines each contain a single integer $x$ ($1 \le x \le n$) — the index of the array element that needs to be set to $1$. It is guaranteed that indexes in queries are distinct.

It is guaranteed that the sum of $n$ for all test cases does not exceed $10^5$.

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

For each test case, output one integer — the minimum change number after which at least one of the segments will be beautiful, or $-1$ if none of the segments will be beautiful.

对于每个测试用例，输出一个整数——使得至少有一个线段变为“优美”的最小修改次数；若没有任何线段能变为“优美”，则输出 $-1$。

In the first case, after first 2 changes we won't have any beautiful segments, but after the third one on a segment $[1; 5]$ there will be 3 ones and only 2 zeros, so the answer is 3.

In the second case, there won't be any beautiful segments.

在第一种情况下，前两次修改后将不存在任何优美线段；但在第三次修改后，在线段 $[1; 5]$ 上将有 3 个 1 和仅 2 个 0，因此答案为 3。

在第二种情况下，将不存在任何优美线段。