Give you a graph G of n points, numbered 1-n. We define the Geosetic set of two points as Geodetic(x,y), representing the set of points on all the shortest path from point x to point y.

Each point has a weight wi, we define the sum of the points in Geodetic (x, y) corresponding to wi as U(x,y)

We guarantee that there is no self-loop and there is at most one edge between two points.

For example

Geodetic(2,5)={2,3,4,5}

Geodetic(1,5)={1,3,5}

 

U(2,5)=6+2+7+4=19

U(1,5)=1+2+4=7

输入描述:

The first line contains two integers n and
m (3<=n<=200,1<=m<=n*(n-1)/2)—the number of points and the number
of edges. The second line contains n integers, w1, w2, w3,…,wn(1<=wi<=1e6).
The next m lines, two integers x and y per line, indicate that there is an
undirected edge between x and y with a length of 1. The next line is a integer
q(1<=q<=1e5)-the number of questions, the next q lines, two integers x
and y per line, indicate a question.

输出描述:

q lines, one integer per line.

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

19
7
13