永远真诚！永远热烈！！永远热泪盈眶！！！

这道题的话 我看写的人是T很多 这道题是这场的防AK 当时验题的时候 写的暴力是排序部分O(m log m)；查询部分最坏

情况每次查询要与全部区间比对，复杂度O(q * m) 也就是说 这道题的复杂度是O(m log m + q * m) 那 q*m 1e5 * 1e5

直接暴力肯定是超时的

这道题应该去考虑二分

因为每次操作都是将一个 0 改成 1，符合条件的区间肯定是越来越多的，所以显然具有单调性，然后就可以二分答案了

考虑到二分答案的话 这道题其实难度就很低了 因为这道题的check是很好写的

外面一个二分 logq +内层 (n+m+q) 然后再去乘测试样例t 这个时间复杂度就很低了

然后我们去看一下这道题是怎么写的 就是给一个全为0的数组 给了区间 可以进行 修改操作 问最少的操作次数 使得给的区间有一个变成美丽数组

美丽数组的要求是1的数量大于0的数量 那我们刚才已经说了每次操作是有单调性的 所以考虑去二分这个操作次数 也就是q

题意其实很简单 细节部分 看我的代码注释

/*
  * @Author: duck
  * @Date: 2025-11-19 18:54:08
  */
 #include <bits/stdc++.h>
 using namespace std;
 #define int long long
 #define ull unsigned long long
 #define endl '\n'
 #define EPS 1e-8
 #define fi first
 #define se second
 #define lowbit(x) x & (-x)
 const int inf = 0x3f3f3f3f3f3f3f3f; // 正好等于2的60次方
 typedef pair<int, int> pii;
 vector<pii> vec;
 vector<int> qq;
 int n, m;
 int q;
 ​
 int check(int mid)
 {
     //防止越界 因为学长开的动态数组vector开的小 你们静态 开的大 就无所谓 
     if (mid == q + 1)
     {
         return 0;
     }
 ​
     //既然要求1的数量比0多 那我们考虑直接全部初始化为-1
     //这样的话 我们修改完mid个 求前缀和 遍历所有区间 如果这个区间是正的
     //肯定是1的数量多余0的 
     vector<int> arr(n + 1, -1);
     arr[0] = 0;
     for (int i = 1; i <= mid; i++)
     {
         arr[qq[i]] = 1;
     }
 ​
     vector<int> sum(n + 1);
 ​
     for (int i = 1; i <= n; i++)
     {
         sum[i] = sum[i - 1] + arr[i];
     }
 ​
 ​
     int flag = 0;
 ​
     for (int i = 1; i <= m; i++)
     {
         if (sum[vec[i].se] - sum[vec[i].fi - 1] > 0)
         {
             flag = 1;
             break;
         }
     }
 ​
     if (flag == 1)
     {
         return 1;
     }
     else
     {
         return 0;
     }
 }
 void solve()
 {
 ​
     cin >> n >> m;
 ​
     vec.resize(m + 1);
 ​
     for (int i = 1; i <= m; i++)
     {
         int l, r;
         cin >> vec[i].fi >> vec[i].se;
     }
 ​
     cin >> q;
     qq.resize(q + 1);
 ​
     for (int i = 1; i <= q; i++)
     {
         cin >> qq[i];
     }
 ​
     //二分板子 写自己熟悉的就行 
     int l = 1, r = q + 1;
 ​
     while (l < r)
     {
         int mid = (l + r) >> 1;
         if (check(mid))
         {
             r = mid;
         }
         else
         {
             l = mid + 1;
         }
     }
 ​
     //最大为q 超过q了 说明是找不到的那种 输出-1
     if (l == q + 1)
     {
         cout << -1 << endl;
         return;
     }
 ​
     cout << l << endl;
 }
 signed main()
 {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int t = 1;
     cin >> t;
     while (t--)
     {
         solve();
     }
     return 0;
 }