Problem Description

Little A is a traveler who loves traveling. One day, he came to a city. This city consists of $n$ scenic spots and $m$ roads connecting these spots. Each scenic spot has an aesthetic value $a_i$.

A tourist route is defined as a not-necessarily simple path between two scenic spots: vertices may be visited multiple times, but edges may not be repeated.

Next, there are $q$ travel seasons. In each travel season, Little A will specify two vertices $x$ and $y$, and then he will walk through all tourist routes from $x$ to $y$.

After all travel seasons end, Little A will calculate the sum of the aesthetic values of all scenic spots he has passed through (if a scenic spot is visited multiple times, its aesthetic value is counted only once). He wants you to output this total aesthetic value sum.

Input Format

The first line contains two positive integers $n, m$.

The second line contains $n$ positive integers $a_i$, representing the weight of vertex $i$.

The next $m$ lines each contain two positive integers, representing the endpoints of an undirected edge.

Then an integer $q$, meaning there are $q$ travel seasons.

The next $q$ lines each contain two integers $x, y$, representing the specified start and end points.

Output Format

One line containing one integer, representing the final total aesthetic value sum.

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

10

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

15

Hint

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (30 pts): $3 \leq n \leq 500, m \leq 2 \times 10^5, q \leq 200$.
• Subtask 2 (30 pts): $3 \leq n \leq 3 \times 10^5, m \leq 2 \times 10^6, q \leq 10^6$.
• Subtask 3 (40 pts): $3 \leq n \leq 5 \times 10^5, m \leq 2 \times 10^6, q \leq 10^6$.

For $100\%$ of the testdata, it is guaranteed that $3 \leq n \leq 5 \times 10^5$, $m \leq 2 \times 10^6$, $q \leq 10^6$, $1 \leq a_i \leq 100$, and the graph is connected, with no multiple edges and no self-loops.

Explanation of the statement:

The figure above is unrelated to the sample.

As shown, the distribution of scenic spots in the city forms an undirected graph.
Suppose vertex $6$ is the scenic spot $x$, and vertex $5$ is the scenic spot $y$.
Obviously, the path $6 \rightarrow 2 \rightarrow 4 \rightarrow 5$ and the path $6 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5$ are both valid. These two paths both satisfy the condition of being simple paths, and both are walked within one travel season.
Although the edge $6 \rightarrow 2$ is traversed twice, it is still valid, because it is not traversed twice within a single path.

In short, in one travel season, he will walk an uncertain number of paths. Each path must be a simple path, but between different simple paths, repeated edges are allowed.

Translated by ChatGPT 5