题目描述

给定一棵 $n$ 个节点的树，每个节点 $i$ 有参数 $k_i,b_i,l_i,r_i$。

共 $Q$ 次询问：给出 $u,v,x$， 求 $\max\{k_ix+b_i \ |\ i \in \mathrm{path}(u,v)\ \mathrm{and}\ x\in[l_i,r_i] \}$（如果是空集则输出 $0$）。

注：本题加强自「集训队互测2016」Unknown

输入格式

一行两个整数 $n,Q$。

接下来 $n$ 行每行四个整数 $k_i,b_i,l_i,r_i$。

接下来 $n-1$ 行每行两个整数 $u,v$。

接下来 $Q$ 行每个三个整数 $u,v,x$。

输出格式

输出共 $Q$ 行。

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

0
5
6
9
20

数据范围与提示

$n,Q \le 10^5,\ 1\le u,v \le n,\ 0 \le k_i,l_i,r_i,x \le 10^6,\ 0 \le b_i \le 10^{12}, l_i \le r_i$