The Bajholm Transport Company rents $n$ warehouses, one on each of the islands of Bajholm. These islands are connected by bridges in such a way that there is exactly one path between every pair of islands (possibly passing through other islands). Additionally, each bridge has a limit on the maximum weight of a vehicle that can cross it.

Bajteusz is one of the drivers at the company and transports goods between warehouses. Every trip is always made along the shortest possible route. Bajteusz is interested in architecture and considers some of the Bajholm bridges to be architectural gems, so he is very keen to cross them. Trips that pass through at least one such bridge are called charming.

The transport company carries a wide variety of goods, so the weight of Bajteusz's vehicle changes frequently. He wonders how this affects the number of potential trips (understood as a journey between two islands) that he could make. Help him and write a program that, for a given vehicle weight, determines the number of pairs of warehouses for which the connecting shortest path is charming and the vehicle's weight does not exceed the limit on any of the bridges that must be crossed.

Input

The first line of input contains two integers $n$ and $q$ ($2 \le n \le 100\,000$, $1 \le q \le 200\,000$) denoting the number of islands in Bajholm and the number of queries to consider. The islands are numbered with integers from $1$ to $n$.

The next $n - 1$ lines contain the description of the bridges of Bajholm: the $i$-th of these lines contains four integers $u_i, v_i, m_i$ and $a_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le m_i \le 10^9, 0 \le a_i \le 1$), meaning that the $i$-th bridge connects islands $u_i$ and $v_i$, the maximum weight of a vehicle that can cross this bridge is $m_i$, and $a_i = 1$ means that Bajteusz considers the bridge an architectural gem.

The next $q$ lines contain the descriptions of the queries: the $j$-th of these lines contains an integer $w_j$ ($1 \le w_j \le 10^9$), denoting the vehicle weight for the $j$-th query.

Output

Output $q$ lines: the $j$-th line should contain a single integer, which is the answer to the $j$-th query from the input, i.e., the number of charming routes that Bajteusz could travel with a vehicle of weight $w_j$.

Examples

Input 1

6 5
1 2 2 0
2 3 6 1
2 5 8 1
5 4 9 0
5 6 4 0
3
5
10
7
8

Output 1

7
5
0
2
2

Evaluation tests

1ocen: $n = 10, q = 10$; island $i$ and $i+1$ are connected by a bridge with a weight limit of $i$ for $1 \le i \le 9$, bridges with an even weight limit are architectural gems; queries are for weights $1, 2, 3, \dots, 10$.

2ocen: $n = 100\,000, q = 1$; all bridges are architectural gems and lead from island 1 to island $i$ for $2 \le i \le n$.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.