310503: CF1843E. Tracking Segments

E. Tracking Segmentstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

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

Output

3
-1
3
3
3
1

Note

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.

题目大意：给定一个由n个0组成的数组a，以及m个不一定是不同的线段。每个线段由两个数字l_i和r_i（1≤l_i≤r_i≤n）定义，表示数组a的一个子数组a_{l_i}, a_{l_i+1}, …, a_{r_i}。如果一个线段上的1的数量严格大于0的数量，则称这个线段为“beautiful”。你有q个变化，每个变化都会给定一个数x（1≤x≤n），表示你必须将元素a_x赋值为1。你需要找到第一个变化后，至少有一个给定的线段变为“beautiful”，或者报告在处理完所有q个变化后，没有一个线段是“beautiful”。

输入数据格式：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含两个整数n和m（1≤m≤n≤10^5）——数组a的大小和线段的数量。
- 接下来有m行，每行包含两个整数l_i和r_i（1≤l_i≤r_i≤n）——线段的边界。
- 下一行包含一个整数q（1≤q≤n）——变化的数量。
- 接下来的q行，每行包含一个整数x（1≤x≤n）——需要设置为1的数组元素的索引。保证查询中的索引是不同的。
- 保证所有测试用例的n之和不超过10^5。

输出数据格式：
- 对于每个测试用例，输出一个整数——在至少有一个线段变为“beautiful”之后的最小变化数，或者如果没有任何线段变为“beautiful”，则输出-1。

示例输入输出已在原文中给出。题目大意：给定一个由n个0组成的数组a，以及m个不一定是不同的线段。每个线段由两个数字l_i和r_i（1≤l_i≤r_i≤n）定义，表示数组a的一个子数组a_{l_i}, a_{l_i+1}, …, a_{r_i}。如果一个线段上的1的数量严格大于0的数量，则称这个线段为“beautiful”。你有q个变化，每个变化都会给定一个数x（1≤x≤n），表示你必须将元素a_x赋值为1。你需要找到第一个变化后，至少有一个给定的线段变为“beautiful”，或者报告在处理完所有q个变化后，没有一个线段是“beautiful”。 输入数据格式： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含两个整数n和m（1≤m≤n≤10^5）——数组a的大小和线段的数量。 - 接下来有m行，每行包含两个整数l_i和r_i（1≤l_i≤r_i≤n）——线段的边界。 - 下一行包含一个整数q（1≤q≤n）——变化的数量。 - 接下来的q行，每行包含一个整数x（1≤x≤n）——需要设置为1的数组元素的索引。保证查询中的索引是不同的。 - 保证所有测试用例的n之和不超过10^5。 输出数据格式： - 对于每个测试用例，输出一个整数——在至少有一个线段变为“beautiful”之后的最小变化数，或者如果没有任何线段变为“beautiful”，则输出-1。 示例输入输出已在原文中给出。