Defense Planning in Z Country

Z Country has \( n \) cities connected by \( n-1 \) bidirectional roads forming a tree, i.e. any two cities are connected by a unique simple path. The defense minister, Little Z, wants to deploy troops in some cities. Deploying a troop in city \( i \) costs \( p_i \). A valid deployment must satisfy that for every road connecting two directly adjacent cities, at least one of the two cities has a troop.

After Little Z finds a minimum-cost deployment without extra restrictions, the king issues \( m \) queries. Each query fixes the troop status in two specified cities. A query is given as four integers \( a, x, b, y \) meaning that city \( a \) must have a troop if \( x=1 \) (and must not have one if \( x=0 \)), and similarly city \( b \) is forced to state \( y \). For each query, considering only the extra restrictions in that query (and ignoring those of other queries), you are to determine the minimum deployment cost that satisfies both the original coverage conditions and the fixed statuses. If no valid deployment exists under the query conditions, output \( -1 \).

The standard dynamic programming formulation on trees is as follows. For a node \( u \), let \[ \text{dp}[u][0] = \sum_{v \in \text{child}(u)} \text{dp}[v][1] \quad\text{and}\quad \text{dp}[u][1] = p_u + \sum_{v \in \text{child}(u)} \min\big(\text{dp}[v][0],\,\text{dp}[v][1]\big). \]

When a city is forced, the corresponding state (either 0 or 1) is the only valid option (the other state cost is taken as \( +\infty \)). You may choose any city as the root (for example, city 1) because the graph is a tree.

inputFormat

The first line contains two integers \( n \) and \( m \), representing the number of cities and the number of queries.

The second line contains \( n \) space‐separated integers \( p_1, p_2, \ldots, p_n \), where \( p_i \) is the cost to deploy a troop in city \( i \).

Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \), indicating that there is a road connecting city \( u \) and city \( v \).

Then \( m \) lines follow. Each of these lines contains four integers: \( a, x, b, y \). Here, \( a \) and \( b \) are cities, and \( x, y \) are either 0 or 1. If \( x=1 \) (resp. \( y=1 \)), then city \( a \) (resp. city \( b \)) must have a troop; if \( x=0 \) (resp. \( y=0 \)) then city \( a \) (resp. city \( b \)) must not have a troop.

outputFormat

For each query, output one line containing a single integer: the minimum cost to deploy troops satisfying the coverage conditions and the extra forced constraints, or \( -1 \) if it is impossible.

sample

3 3
1 2 3
1 2
2 3
1 1 3 0
1 0 2 0
2 1 3 1

3
-1
5