该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

“抛开一些性格或者外表上的因素，首先我会喜欢上一个浪漫又富有激情的人。”

“具体呢？”

温凉扬起头，一边想，一边肆意说道：

“浪漫要怎么具体呢？就好像我不太受得了你先前的那种说法，我是个很疯的人，我太喜欢张扬的爱意了。在这个所有人都知道要掩饰，要试探，要权衡利弊的时代，我就偏不 —— 我就要热烈，要坦荡，要以真心换真心，要想一百次不如做一次。我不喜欢那种幸福就摆在你面前，你却把那些阴影当成山川瀑布挡住视线，说自己无法幸福的人，就像..... 小甲你一样。”

看着女孩这般花漾飞扬，眼底满是对青春爱情的幻想，小甲不知不觉由衷笑了一下，他感叹道：

“那，能成为你爱的人，真的是一件幸福与压力兼具的事。”

说到这里，他又忍不住提醒：

“可就如你在车上说的，你会把爱情与人生绑定在一起，这虽然听上去很美好，但也太过执着了一些，不是吗？如果不去刻意为之的引导些什么，这世上很难碰见另一个跟你契合的灵魂。而且大多情况下，相爱的两人都需要换位思考、推己及人，要经历必然的相互迁就与自我克制，这是必然。”

温凉耸耸肩：“我知道你表达的意思，但我其实不赞同这个‘必然’的说法。”

“怎么说？”

“因为我相信这个世界上，肯定有这么一个人是为我而来的。他跟所有人都不一样，如果他出现了却停在原地，那就换我奔他而去就好 —— 就这么简单，不用想那么多的。”

“所以.... 你不是一个安稳的人？”

“当然不是，我是一个喜欢挑战的人。”

男人的眼神柔和下来，里面盛满了对眼前女孩的欣赏，像落了层细碎的光耀。

“但你有没有想过，人的内在是在不断变化的？随着人生阶段改变，我们渴望的东西也会变。也许二十岁的你，跟三十岁的你看待问题的角度不同；也许到了四十岁，你对待这个世界的方式，都会发生翻天覆地的改变。”

温凉眉头微扬，声音清亮得像撞碎了阳光：

“但人的灵魂是不变的呀！”

如果听一万遍反方向的钟，可以回到开始第一天，你愿意吗？

我愿意

题面描述

温凉听完了一万遍反方向的钟，来到了时光洪流之中，她看着眼前错综复杂的时间线，每个时间线都有对应着的题目，只有答对题目才可以回到这个时间线开始的那天，温凉选择了九月！可温凉期待，开心，徘徊，紧张的心情，根本无法冷静思考，聪明的你可以帮帮温凉吗？，让她去改变未来！

给定一个长度为 $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

输入 #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

输出 #1

3
-1
3
3
3
1

说明/提示

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

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