题目背景

『板栗好闪，拜谢板栗』

众所周知，板栗树是神奇的。

题目描述

板栗老师家有一棵 \(n\) 个节点的板栗树，第 \(i\) 个点在 \(t_i\) 时刻会有 \(a_i\) 个板栗成熟。

她有 \(q\) 个问题需要求助于你，第 \(i\) 个问题由 \(4\) 个数 \(l,r,x,y\)，表示她想问你 \([l,r]\) 时间内板栗树上 \(x,y\) 之间的路径上（包括 \(x,y\)）有多少板栗成熟。

输入格式

第一行两个整数 \(n,q\)，表示一共有 \(n\) 个节点和 \(q\) 个询问。

接下来 \(n-1\) 行，第 \(i\) 行包含 \(2\) 个正整数 \(u_i,v_i\)，表示 \(u_i,v_i\) 之间有一条边。

接下来 \(n\) 行，每行 \(2\) 个整数 \(t_i,a_i\)，表示第 \(i\) 个点 \(t_i\) 时刻有 \(a_i\) 个板栗成熟。

接下来 \(q\) 行，每行 \(4\) 个整数 \(l_i,r_i,x_i,y_i\)，表示一组询问。

输出格式

对于每个询问，输出一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

22
17

提示

对于 \(20\%\) 数据，满足 \(n,q,t_i\le 200\)。

对于 \(50\%\) 数据，满足 \(n,q,t_i\le 2000\)。

对于额外的 \(20\%\) 数据，满足 \(t_i\le 10^2\)。

对于 \(100\%\) 数据，满足 \(n,q\le 10^5,1\le l_i\le r_i\le \max\limits_{j=1}^n t_j,1\le t_i,a_i \le 10^5\)。