P7924 "EVOI-RD2" Traveler.

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.

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.

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

**[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