Country Z has $n$ cities and $n-1$ bidirectional roads. Each road connects two cities, and any two cities can reach each other through a series of roads.

The Minister of Defense of Country Z, Xiao Z, wants to station troops in the cities. Stationing troops must satisfy the following conditions: A city may or may not have troops stationed in it. For any two cities directly connected by a road, at least one of them must have troops stationed in it. * Stationing troops in a city incurs a cost. The cost of stationing troops in city $i$ is $p_i$.

Xiao Z has planned a troop stationing scheme that minimizes the total cost. However, the King has given Xiao Z $m$ requirements, each specifying whether troops should be stationed in two specific cities. Xiao Z needs to provide an answer for each requirement. Specifically, if the $j$-th requirement given by the King can satisfy the aforementioned stationing conditions (without considering other requirements besides the $j$-th one), you need to provide the minimum cost to station troops under that requirement. If the $j$-th requirement cannot be satisfied, output -1 ($1 \le j \le m$). Now, please help Xiao Z.

Input

The first line contains two integers $n, m$ and a string $type$. $n$ and $m$ represent the number of cities and the number of requirements, respectively. $type$ is a string consisting of an uppercase letter A, B, or C and a digit 1, 2, or 3. It can help you obtain partial points. You may not need to use this parameter. The meaning of this parameter is described in detail in the [Constraints] section.

The second line contains $n$ integers $p_i$, representing the cost of stationing troops in city $i$.

The next $n-1$ lines each contain two integers $u, v$, representing a bidirectional road between $u$ and $v$.

The next $m$ lines each contain four integers $a, x, b, y$ ($a \neq b$), representing the $j$-th requirement: station $x$ troops in city $a$ and $y$ troops in city $b$. Here, $x$ and $y$ can only take values 0 or 1: if $x$ is 0, it means no troops are stationed in city $a$; if $x$ is 1, it means troops must be stationed in city $a$. Similarly for $y$ and city $b$.

Adjacent integers in each line of the input are separated by a single space.

Output

Output $m$ lines. Each line contains one integer, representing the minimum cost to satisfy the King's $j$-th requirement. If the King's $j$-th requirement cannot be satisfied, output -1.

Examples

Input 1

5 3 C3
2 4 1 3 9
1 5
5 2
5 3
3 4
1 0 3 0
2 1 3 1
1 0 5 0

Output 1

12
7
-1

Note

For the first requirement, the cost is minimized by stationing troops in cities 4 and 5. For the second requirement, the cost is minimized by stationing troops in cities 1, 2, and 3. The third requirement cannot be satisfied because not stationing troops in both city 1 and city 5 implies that two cities directly connected by a road have no troops stationed in them.

Constraints

For 100% of the data, $n, m \le 300000, 1 \le p_i \le 100000$.

Meaning of the types: A: City $i$ and city $i+1$ are directly connected. B: The distance between any city and city 1 does not exceed 100 (distance is defined as the number of edges on the shortest path). That is, if the tree is rooted at city 1, the depth does not exceed 100. C: No special constraints on the shape of the tree. 1: The query guarantees $a=1, x=1$, i.e., troops must be stationed in city 1. No restrictions on $b, y$. 2: The query guarantees $a, b$ are adjacent (directly connected by a road). 3: No special constraints on the query.