题目描述

比特山是比特镇的飙车圣地。在比特山上一共有 $n$ 个广场，编号依次为 $1$ 到 $n$，这些广场之间通过 $n−1$ 条双向车道直接或间接地连接在一起，形成了一棵树的结构。

因为每条车道的修建时间以及建筑材料都不尽相同，所以可以用两个数字 $l_i,r_i$ 量化地表示一条车道的承受区间，只有当汽车以不小于 $l_i$ 且不大于 $r_i$ 的速度经过这条车道时，才不会对路面造成伤害。

Byteasar 最近新买了一辆跑车，他想在比特山飙一次车。Byteasar 计划选择两个不同的点 $S,T$，然后在它们树上的最短路径上行驶，且不对上面任意一条车道造成伤害。

Byteasar 不喜欢改变速度，所以他会告诉你他的车速。为了挑选出最合适的车速，Byteasar 一共会向你询问 $m$ 次。请帮助他找到一条合法的道路，使得路径上经过的车道数尽可能多。

输入格式

第一行包含两个正整数 $n,m$，表示广场的总数和询问的总数。

接下来 $n−1$ 行，每行四个正整数 $u_i,v_i,l_i,r_i$，表示一条连接 $u_i$ 和 $v_i$ 的双向车道，且承受区间为 $[l_i,r_i]$。

接下来 $m$ 行，每行一个正整数 $q_i$，分别表示每个询问的车速。

输出格式

输出 $m$ 行，每行一个整数，其中第$i$行输出车速为 $q_i$ 时的最长路径的长度，如果找不到合法的路径则输出 $0$。

样例

5 3
3 2 2 4
1 5 2 5
4 5 2 2
1 2 3 5
1
2
3

0
2
3

• 当车速为 $1$ 时，不存在合法的路径。
• 当车速为 $2$ 时，可以选择 $1-5-4$ 这条路径，长度为 $2$。
• 当车速为 $3$ 时，可以选择 $3-2-1-5$ 这条路径，长度为 $3$。

数据范围

对于 $100\%$ 的数据，$1\le u_i, v_i,q_i \le n$，$\ 1\le l_i\le r_i\le n$。