Beauty of Tourist Paths

Traveler A loves to journey. One day he arrives at a city consisting of \(n\) attractions (vertices) and \(m\) roads (edges) connecting them. Each attraction \(i\) has a beauty value \(a_i\).

A tourist path is defined as an edge‐simple path (i.e. a path in which edges are not repeated, though vertices may be visited multiple times) between two attractions.

There are \(q\) tourist seasons. In each season, Traveler A is given two attractions \(x\) and \(y\) and he walks through all tourist paths from \(x\) to \(y\). After all seasons, he records the sum of the beauty values of all attractions that he has visited on at least one path (each attraction is counted at most once even if visited multiple times).

You are to help him compute this overall beauty sum.

Note: Two attractions are considered connected if there exists at least one tourist path (i.e. an edge‐simple path) connecting them. In each query, only those attractions that appear on some simple \(x\)-\(y\) path are taken into account. The final answer is the sum of \(a_i\) over the union of attractions from all queries.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le 10^5)\) — the number of attractions and roads.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\) representing the beauty of each attraction.

Each of the next \(m\) lines contains two integers \(u\) and \(v\), indicating there is an undirected road connecting attractions \(u\) and \(v\).

The next line contains an integer \(q\) \((1 \le q \le 10^5)\) representing the number of tourist seasons.

Each of the next \(q\) lines contains two integers \(x\) and \(y\) denoting a query.

It is guaranteed that the graph can be arbitrary (may contain cycles). Attractions are numbered from 1 to \(n\). The queries are independent.

outputFormat

Output a single integer — the sum of the beauty values of all attractions that appear on some tourist path for at least one query. If for a query \(x\) and \(y\) are not connected by any tourist path, ignore that query.

sample

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

10