Given a tree with vertices such that each vertex has an associated cost . There are queries: if vertex must or must not be chosen and vertex 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 and one string . represents the number of vertices, represents the number of queries, and represents additional constraints satisfied by the test case.

The second line contains integers denoting the cost associated with vertex .

In the following lines, each line contains two integers denoting there exists an edge in the tree.

In the following lines, each line contains 4 integers . If , then vertex cannot be included in the vertex cover, while if vertex must be in the vertex cover. Similarly, if , vertex cannot be included in the vertex cover, while if , vertex must be in the vertex cover.

#### Output Specification

The output consists of lines. Each line contains an integer: the -th line denotes the minimum cost of a vertex cover satisfying the constraints outlined in the -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 .

For the second query, the subset of vertices shall be .

The constraints in the last query cannot be satisfied since both endpoints of edge cannot be in the vertex cover.

#### Additional Samples

Additional samples can be found here.

#### Constraints

For all test cases, , .

Test Case | Type | ||
---|---|---|---|

1-2 | A3 | ||

3-4 | C3 | ||

5-6 | A3 | ||

7 | C3 | ||

8-9 | A3 | ||

10-11 | C3 | ||

12-13 | A1 | ||

14-16 | A2 | ||

17 | A3 | ||

18-19 | B1 | ||

20-21 | C1 | ||

22 | C2 | ||

23-25 | C3 |

Interpretation of :

A - vertex and are connected directly by an edge.

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

C - no additional constraints on the tree.

1 - for all queries, , (i.e. vertex must be included). There are no constraints on and .

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

3 - no additional constraints on the queries.

## Comments