说明

乐乐计划寒假到$A$城旅游，在出发前他已经准备好了$A$城的地图。地图上有n个景点，m条双向通行的道路，每条边边权均为1，每条边连接两个景点$x_i$和$y_i$。

每个景点内都有一所供游人休息的旅馆，第i个景点的旅馆的舒适度为$c_i(0 \leq c_i \leq 100)$。

他希望在逛完第$i$个景点后，能够找到该景点及周围（也就是距离≤1）的最舒适的旅馆稍作休息，以恢复体力。

现在给出$q$个询问，每个询问给出一个景点编号x，表示要询问该景点及周围的最舒适的旅馆。

对于每个询问，需要给出舒适度最高的旅馆所对应的景点编号，以及该旅馆的舒适度是多少。

输入格式

第一行两个正整数$n(1 \leq n \leq 10^5)$和$m(1 \leq m \leq 10^6)$，分别表示景点数量、边的数量。

下面m行，每行两个数字$x_i,y_i$表示一条边连接的两个点

第m+2行n个数字，第$i$个数字代表第$i$个景点的旅馆的舒适度$c_i(0\le c_i\le 1000)$

第m+3行一个正整数$q(1 \leq q \leq 10^5)$，代表询问数量

下面q行，每行描述一个询问。每个询问包含一个数字x，表示询问的景点编号。

输出格式

共q行，每行对应一个询问的回答。

每个回答中第一个数字为舒适度最高的旅馆所对应的景点编号，第二个数字为该旅馆的舒适度，两个数字中间以空格隔开。

如果有多个景点的旅馆舒适度相同，输出景点编号最小的那个。

样例

7 6
1 2 
2 3
3 4
3 7
2 5
3 6
4 3 4 6 1 6 2
2
2
3

1 4
4 6

提示

可能有自环或重边，不保证图连通