题目描述

一片山区中分布着 $n$ 个物资站，物资站之间由道路相连，并且任意两个物资站之间都恰好只有一条简单路线。将物资站 $1$ 设为总仓库，以它为根后，这些道路构成一棵有根树。

第 $i$ 个物资站的某种货物单价为正整数 $a_i$。

对于树上的两个物资站 $u,v$，从 $u$ 前往 $v$ 时依次经过的物资站记为 $p_1,p_2,\ldots,p_k$，其中 $p_1=u$、$p_k=v$，且相邻两个物资站之间有道路直接相连。由于道路构成一棵树，这条路线唯一确定。

现在有 $q$ 次行程询问。每次给出两个物资站 $u,v$，一名商队会严格按照从 $u$ 到 $v$ 的顺序经过路线上的各站。商队可以在第 $i$ 个经过的物资站买入货物，并在第 $j$ 个经过的物资站卖出，其中 $1\le i\le j\le k$。允许在同一站买入并卖出，此时收益为 $0$。

若选择的位置为 $i,j$，则本次交易收益为 $a_{p_j}-a_{p_i}$。请对每次询问求出能够获得的最大收益。

保证每次询问中的 $v$ 一定是 $u$ 的祖先。

输入格式

第一行两个正整数 $n,q$，分别表示物资站数量和询问次数。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示物资站 $u$ 与物资站 $v$ 之间有一条道路。

接下来一行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示各物资站的货物单价。

接下来 $q$ 行，每行两个正整数 $u,v$，表示一次从物资站 $u$ 前往其祖先物资站 $v$ 的行程询问。

输出格式

输出共 $q$ 行，每一行输出一个整数，表示对应询问的答案。

样例

样例 1 输入

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

样例 1 输出

    3
    2

【样例 1 解释】

对于第一次询问，商队依次经过物资站 $4,3,2,1$，对应单价为 $2,4,5,1$。在物资站 $4$ 以价格 $2$ 买入，并在物资站 $2$ 以价格 $5$ 卖出，可获得最大收益 $5-2=3$。

对于第二次询问，商队依次经过物资站 $5,4,3$，对应单价为 $3,2,4$。在物资站 $4$ 以价格 $2$ 买入，并在物资站 $3$ 以价格 $4$ 卖出，可获得最大收益 $4-2=2$。

数据范围与提示

保证对于所有的测试点满足以下限制：$1\leq n\leq 2\times 10^5,1\leq q\leq 5\times 10^5,1\leq a_i\leq 10^9$。

特殊性质 A：$a_i\leq 2$。

特殊性质 B：第 $i$ 条边连接节点 $i$ 和 $i+1$。