Calculate Vertex Sums on Shortest Paths

You are given an undirected graph with \( n \) vertices and \( m \) edges. Each vertex \( i \) has an associated value \( v_i \). The graph may be disconnected; however, queries will only be asked for vertices that are connected (or are the same vertex).

Your task is to answer \( q \) queries. Each query provides two vertices \( s \) and \( t \), and you must compute the sum of vertex values along the shortest path from \( s \) to \( t \). The shortest path is the one with the minimum number of edges. If \( s = t \), the answer is simply \( v_s \).

Note: The sum along the path is defined as the sum of the values of all vertices encountered on the path including both endpoints.

Example:

Input:
5 4
1 2 3 4 5
1 2
2 3
3 4
4 5
3
1 5
2 4
3 5
Output:
15
9
12

</p>

The first line contains two integers \( n \) and \( m \). The second line contains \( n \) integers representing the vertex values. Each of the next \( m \) lines contains two integers representing an edge between two vertices. The next line contains an integer \( q \) (the number of queries), followed by \( q \) lines each containing two integers for the start and end vertices.

inputFormat

The input is given via standard input (stdin) with the following format:

 n m
 v1 v2 ... vn
 u1 v1
 u2 v2
 ...
 um vm
 q
 s1 t1
 s2 t2
 ...
 sq tq

Where:

• \( n \) is the number of vertices.
• \( m \) is the number of edges.
• \( v_i \) is the value of vertex \( i \).
• Each of the next \( m \) lines contains two integers \( u \) and \( v \) representing an undirected edge.
• \( q \) is the number of queries.
• Each query consists of two integers \( s \) and \( t \) indicating the start and end vertices.

outputFormat

For each query, print a single integer on a new line representing the sum of the vertex values along the shortest path from \( s \) to \( t \).

## sample

5 4
1 2 3 4 5
1 2
2 3
3 4
4 5
3
1 5
2 4
3 5

15
9
12

</p>