Countries and Cities

There are \(N\) cities in total, spread across \(K\) countries. The first country has \(a_1\) cities, the second has \(a_2\), ..., the \(K\)-th has \(a_K\) cities, and they are numbered consecutively. Namely:
– cities of country 1 are numbered \(1\) through \(a_1\);
– cities of country 2 are numbered \(a_1+1\) through \(a_1+a_2\);
– …
– cities of country \(K\) are numbered \(a_1+a_2+\dots+a_{K-1}+1\) through \(N\).

Roads have been built between the cities. For every \(1 \le i < N\), there is a road between cities \(i\) and \(i+1\). Additionally, \(M\) extra roads each connect two cities within the same country.

You are given \(Q\) queries, each containing two cities \(X\) and \(Y\) located in different countries. Your task is to find the number of shortest paths from city \(X\) to city \(Y\). Since the answer can be large, print it modulo \(10^9+7\).

Input

The first line contains three integers – \(K, N, M\) (\(1 \le K, N, M \le 3 \cdot 10^5;\ K \le N\)).

The second line contains \(a_1, a_2, \dots, a_K\) (\(a_i \ge 1\); \(a_1+a_2+\dots+a_K = N\)).

Each of the next \(M\) lines contains two integers \(u\) and \(v\), meaning there is an extra road between cities \(u\) and \(v\) (\(1 \le u, v \le N\); \(|u-v| \ge 2\)). It is guaranteed that the cities connected by extra roads lie in the same country.

The next line contains a single integer \(Q\) (\(1 \le Q \le 3 \cdot 10^5\)).

Each of the next \(Q\) lines contains cities \(X\) and \(Y\) (\(1 \le X, Y \le N\)). It is guaranteed that they lie in different countries.

Output

For each query, print the answer on a new line – the number of shortest paths modulo \(10^9+7\).

Example

3 13 5
4 5 4
1 3
4 2
8 6
10 13
5 7
3
7 12
4 5
1 13

2
1
4

Note

The picture shows 3 countries and 13 cities. Cities 1, 2, 3 belong to country A; cities 4–9 belong to country B; and cities 10–13 belong to country C. There are also extra roads between cities 1–3, 2–4, 5–7, 6–8, and 10–13.