Given a tree with $n$ vertices such that each vertex has an associated cost $p_i$. There are $m$ queries: if vertex $a$ must or must not be chosen and vertex $b$ must or must not be chosen, what is the minimum cost of a vertex cover (i.e. minimum cost to choose a subset of vertices such that for all edges at least one endpoint is in the subset). If vertex covers do not exist under the constraint given in a query, output -1.

Input Specification

The first line contains two integers $n,m$ and one string $\mathtt{\text{type}}$. $n$ represents the number of vertices, $m$ represents the number of queries, and $\mathtt{\text{type}}$ represents additional constraints satisfied by the test case.

The second line contains $n$ integers $p_i$ denoting the cost associated with vertex $i$.

In the following $n-1$ lines, each line contains two integers $u,v$ denoting there exists an edge $(u,v)$ in the tree.

In the following $m$ lines, each line contains 4 integers $a,x,b,y$ $(a\ne b)$. If $x=0$, then vertex $a$ cannot be included in the vertex cover, while if $x=1$ vertex $a$ must be in the vertex cover. Similarly, if $y=0$, vertex $b$ cannot be included in the vertex cover, while if $y=1$, vertex $b$ must be in the vertex cover.

Output Specification

The output consists of $m$ lines. Each line contains an integer: the $j$-th line denotes the minimum cost of a vertex cover satisfying the constraints outlined in the $j$-th query. If it is impossible to have a vertex cover satisfying the constraint, output -1.

Sample 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

Sample Output 1

12
7
-1

For the first query, the subset of vertices shall be $\{4,5\}$.

For the second query, the subset of vertices shall be $\{1,2,3\}$.

The constraints in the last query cannot be satisfied since both endpoints of edge $(1,5)$ cannot be in the vertex cover.

Additional Samples

Additional samples can be found here.

Constraints

For all test cases, $n,m\le {10}^5$, $1\le p_i\le {10}^5$.

Test Case	Type	$n=$	$m=$
1-2	A3	$10$	$10$
3-4	C3
5-6	A3	$100$	$100$
7	C3
8-9	A3	$2000$	$2000$
10-11	C3
12-13	A1	${10}^5$	${10}^5$
14-16	A2
17	A3
18-19	B1
20-21	C1
22	C2
23-25	C3

Interpretation of $\mathtt{\text{type}}$:

• A - vertex $i$ and $i+1$ are connected directly by an edge.

• B - if the tree's root is vertex $1$, then the depth is at most $100$.

• C - no additional constraints on the tree.

• 1 - for all queries, $a=1$, $x=1$ (i.e. vertex $1$ must be included). There are no constraints on $b$ and $y$.

• 2 - in a query, vertex $a$ and $b$ are guaranteed to be adjacent.

• 3 - no additional constraints on the queries.