题目描述

法鲁姆（Farloom）是一个遍布丝线小径的王国。每条小径都是连接两个村庄的一根绷紧的直丝线。狡猾的反派“头骨暴君”打算沿竖直方向挥击这张由小径组成的网。

把王国看成一张图：顶点是村庄，第 $i$ 个村庄在平面上的坐标为 $(x_i,y_i)$；边是连接村庄的丝线小径。表示道路的线段可以在村庄之外相交，但不能在这些交点处从一条道路转到另一条道路。

王国居民猜测了 $q$ 个暴君可能攻击的位置。如果暴君沿横坐标为 $X$ 的竖直直线攻击，将删除：

• 所有满足 $x_i=X$ 的村庄；
• 所有连接村庄 $i,j$ 且满足 $\min(x_i,x_j)\le X\le\max(x_i,x_j)$ 的道路。

请帮助居民，对每个可能的攻击位置，求攻击后王国中剩余的连通分量数。所有询问相互独立：回答当前询问时，不需要考虑之前的攻击。

图的连通分量是一个顶点集合，集合中的任意顶点都可以沿边到达集合内的其他任意顶点，但不能沿边到达集合之外的顶点。

输入格式

每个测试包含多组数据。第一行包含整数 $t$，表示数据组数，满足 $1\le t\le5000$。接下来依次描述每组数据。

每组数据的第一行包含三个整数 $n,m,q$，分别表示村庄数、道路数和可能的攻击位置数，满足 $1\le n\le10^5$，$0\le m\le\min(10^5,\frac{n(n-1)}2)$，$1\le q\le10^5$。

第二行包含 $n$ 个整数 $x_i$，表示各村庄的横坐标。第三行包含 $n$ 个整数 $y_i$，表示各村庄的纵坐标。坐标范围为 $-10^9\le x_i,y_i\le10^9$。

接下来 $m$ 行，每行包含两个整数 $u_i,v_i$，表示道路连接的两个村庄编号，满足 $1\le u_i,v_i\le n$，且 $u_i\ne v_i$。

最后一行包含 $q$ 个整数，表示各个可能攻击位置的横坐标，每个数的绝对值都不超过 $10^9$。

保证同一组数据中，没有两个村庄的坐标相同。保证所有数据组的 $n$ 之和、$m$ 之和、$q$ 之和分别都不超过 $10^5$。

输出格式

对每组数据，输出一行 $q$ 个整数，分别表示各询问的答案。

注意，各询问相互独立。

2
9 9 6
0 0 0 1 1 2 2 2 3
0 2 -2 1 -1 0 2 -2 0
1 4
1 5
2 4
3 5
4 6
4 7
5 6
5 8
6 9
-1 0 1 2 3 10
5 3 4
-1 0 1 3 3
0 0 0 1 -1
1 2
2 3
4 5
0 1 2 3

1 1 6 2 1 1
3 2 2 1

提示

样例中的图如下所示：

:::align{center} :::