Bajholm 运输公司拥有 $n$ 个仓库，每个岛屿上各有一个。这些岛屿通过桥梁连接，使得任意两个岛屿之间有且仅有一条路径（可能经过其他岛屿）。此外，每座桥梁都有一个最大载重限制。

Bajteusz 是公司的一名司机，负责在仓库之间运送货物。每次行程总是沿着最短路径进行。Bajteusz 对建筑很感兴趣，他认为 Bajholm 的某些桥梁是“建筑瑰宝”，因此他非常乐意经过这些桥梁。他将经过至少一座此类桥梁的行程称为“迷人行程”。

运输公司运送的货物种类繁多，因此 Bajteusz 的车辆载重经常变化。他想知道这如何影响他可以执行的潜在行程（即两个岛屿之间的路径）的数量。请编写一个程序，对于给定的车辆载重，计算有多少对仓库，使得连接它们的路径是“迷人”的，且车辆载重不超过路径上所有桥梁的载重限制。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 100\,000, 1 \le q \le 200\,000$)，分别表示 Bajholm 的岛屿数量和需要处理的查询数量。岛屿编号为 $1$ 到 $n$。

接下来的 $n - 1$ 行描述了 Bajholm 的桥梁：第 $i$ 行包含四个整数 $u_i, v_i, m_i$ 和 $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$)，表示第 $i$ 座桥连接岛屿 $u_i$ 和 $v_i$，最大载重为 $m_i$，且 $a_i = 1$ 表示 Bajteusz 认为该桥是建筑瑰宝。

接下来的 $q$ 行包含查询描述：第 $j$ 行包含一个整数 $w_j$ ($1 \le w_j \le 10^9$)，表示第 $j$ 次查询的车辆载重。

输出格式

输出 $q$ 行：第 $j$ 行应包含一个整数，即对于载重为 $w_j$ 的车辆，Bajteusz 可以行驶的迷人行程数量。

样例

输入格式 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

输出格式 1

7
5
0
2
2

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。