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

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

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.

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.