题目描述

环网曾经是人类文明史上的奇迹，银河系中的无数星球被时空之门联系在一起，从此时间和空间不再是阻碍。一旦两个星球之间建立了时空联系，那么通过时空之门可以在一瞬间从一个星球到达另外一个星球。人类文明因此以前所未有的速度扩张到银河系的每个角落。

在被称为末日浩劫的上古事件中，人工智能消失了，而时空之门从此再也没有响应人类的呼唤。人类文明的 $n$ 个星球中，如今只剩下 $k$ 个尚有人类居住，而他们只能进行简单的实时通讯，再也不能互相访问。

更可怕的事情发生了，某个尚有人类居住的星球 r 上爆发了电子瘟疫。这种瘟疫大肆破坏人类的电子植入设备，几乎毁灭了 r 星。r 星被毁灭之前传送过来的信息证实该电子瘟疫和上古人工智能的相似性将会允许它们通过部分上古时空之门。由于时空之门已经有几个世纪没人维护了，所以电子瘟疫利用时空之门进行的传送甚至不是双向的。

为了阻止电子瘟疫，人类决定使用他们剩余的总和为 $w$ 的空间能量对环网中的某个星球进行空间打击（可以是 r 星）。空间打击可以让一个星球彻底消失。然而由于星球的参数不同，打击每个星球需要的空间能是不一样的。人类指挥官很想知道，人类能否打击某个星球使得电子瘟疫不能到达剩下的 $k-1$ 个人类居住星，如果能的话，最小需要多少空间能。注意到如果电子瘟疫本来就不能到达剩下的 $k-1$ 个人类居住星，那么就不需要打击了。

由于多重宇宙的存在，在不同宇宙中，$k$ 个人类居住点是不同的，为此，我们将对你进行多组询问。

输入格式

第一行三个整数 $n,m,r$，表示环网的星球数量、电子瘟疫尚能利用的时空连接数量以及 r 星的编号。

第二行到第 $m+1$ 行，每行两个整数 $u_i,v_i$。表示电子瘟疫可以从 $u_i$ 星利用时空之门传送到 $v_i$ 星，这个传送不是双向的。保证每个有序对 $u_i,v_i$ 只会出现最多一次，而且不存在 $u_i=v_i$。

第 $m+2$ 行有 $n$ 个整数 $e_{1\cdots n}$，表示打击每个星球需要的空间能。

第 $m+3$ 行有一个整数 $q$，表示有 $q$ 组询问。

对于每组询问，第一行有两个整数 $t(t=k-1),w$。表示除了 r 星以外尚有 $t$ 个星球有人居住，$w$ 表示人类空间能总和，接下来一行有 $t$ 个数字，是这 $t$ 个星球的编号。

输出格式

对于每组询问，如果人类无法阻止瘟疫到达某个人类居住星球，请输出 1，否则输出最小需要的空间能。

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

8
1
3

数据规模与约定

对于 $100\%$ 的数据，$2\leq n\leq 2\times 10^5$，$0\leq m\leq 5\times 10^5$，$0\leq w,e_i\leq 10^9$，$1\leq q\leq 5\times 10^5$，$1\leq t<n$，$1\leq \sum t\leq 5\times 10^5$。