You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

洪水（$\texttt{flood}$）

【题目描述】

小 D 的家乡有 $n$ 个城市，所有城市通过 $n-1$ 条道路相连，保证任意两个城市之间都可以通过道路互相到达。

现在发生了 $m$ 场洪水，第 $i$ 场洪水发生在 $p_i$，水位为 $h_i$。

为了防止洪水泛滥，市长决定给每条边上修一个水坝，第 $i$ 条边上的水坝高度为 $w_i$。

对于一条边 $(u_i,v_i)$，若 $u_i$ 上产生一场水位为 $h$ 的洪水且 $h>w_i$，那么 $v_i$ 上也会产生一场水位为 $h$ 的洪水。

小 D 想知道是否存在一个城市没有被洪水淹没过。

但这个问题太简单了，小 D 一眼就做出了这道题，于是他把这个问题加强了一下，现在他想知道：

如果第 $i$ 条边的水坝高度从 $[l_i,r_i]$ 中等概率随机选取一个整数作为 $w_i$，那么存在一个城市没有被洪水淹没的概率是多少？

【输入格式】

从 $\texttt{flood.in}$ 中读入数据。

第一行两个整数 $n$ 和 $m$。

接下来 $n-1$ 行，每行表示一条边，每行四个整数 $u_i,v_i,l_i,r_i$，表示边的两个端点和权值的范围。

接下来 $m$ 行，每行两个整数 $p_i,h_i$，表示一场洪水。

【输出格式】

输出到 $\texttt{flood.out}$ 中。

一行一个整数表示答案。

【样例 1 输入】

5 2
1 2 1 10
2 3 2 9
1 4 3 12
2 5 4 6
1 7
5 5

【样例 1 输出】

888437475

【样例 2】

见下发文件中的 $\texttt{flood2.in}$ 与 $\texttt{flood2.ans}$。

该样例满足 $\text{Subtask 2}$ 的限制。

【样例 3】

见下发文件中的 $\texttt{flood3.in}$​ 与 $\texttt{flood3.ans}$​。

该样例满足 $\text{Subtask 3}$ 的限制。

【样例 4】

见下发文件中的 $\texttt{flood4.in}$ 与 $\texttt{flood4.ans}$。

该样例满足 $\text{Subtask 4}$ 的限制。

【数据范围】

对所有测试数据有：$1\le n,m\le 3000,1\le h_i\le10^9,1\le l_i\le r_i\le 10^9$。