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 ~\texttt{type}~. ~n~ represents the number of vertices, ~m~ represents the number of queries, and ~\texttt{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 \neq 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	~2\,000~	~2\,000~
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 ~\texttt{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.