一群研究人员在银河系中发现了一颗未知的行星。
他们正在研究这颗行星上曾经存在的古老文明。已知该行星上有 $n$ 座城市，以及 $m$ 条连接这些城市的双向道路。每条道路仅在特定的时间段内存在：第 $i$ 条道路连接城市 $a_i$ 和 $b_i$，且仅在第 $c_i$ 年到第 $d_i$ 年（包含起始和结束年份）期间存在。在同一年份，两个城市之间可能存在多条道路。
研究人员提出了 $q$ 个问题。每个问题要求计算在第 $l_i$ 年到第 $r_i$ 年（包含起始和结束年份）的区间内，有多少个年份 $k$ 满足：在第 $k$ 年存在的道路网络中，可以从城市 $x_i$ 走到城市 $y_i$。请帮助研究人员回答这些问题。
输入格式
输入文件的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 77777, 1 \le m \le 77777$)，分别表示城市数量和双向道路数量。
接下来的 $m$ 行，每行包含四个整数 $a_i, b_i, c_i$ 和 $d_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le c_i \le d_i \le 10^9$)，表示第 $i$ 条道路连接的城市以及该道路存在的年份区间。
下一行包含一个整数 $q$ ($1 \le q \le 77777$)，表示问题数量。
接下来的 $q$ 行，每行包含四个整数 $x_i, y_i, l_i$ 和 $r_i$ ($1 \le x_i, y_i \le n, x_i \neq y_i, 1 \le l_i \le r_i \le 10^9$)，表示第 $i$ 个问题的城市对及年份区间。
输出格式
输出共 $q$ 行，每行输出一个整数。第 $i$ 行的数字表示在第 $l_i$ 年到第 $r_i$ 年之间，有多少个年份 $k$ 满足在第 $k$ 年可以从城市 $x_i$ 到达城市 $y_i$。
子任务
本题包含 7 个子任务。
| 子任务 | 附加限制 | 分值 | 依赖子任务 |
|---|---|---|---|
| 0 | 样例 | 0 | — |
| 1 | $n, m, q \le 100, d_i \le 100, r_i \le 100$ | 5 | 0 |
| 2 | $n, m, q \le 3000, d_i \le 3000, r_i \le 3000$ | 7 | 1 |
| 3 | $m = n - 1, a_i = i, b_i = i + 1$ | 12 | — |
| 4 | $d_i = 10^9$ | 16 | — |
| 5 | $l_i = r_i$ | 12 | — |
| 6 | $n, m, q \le 40000$ | 27 | 2 |
| 7 | — | 21 | 3, 4, 5, 6 |
样例
输入 1
4 4 1 2 2 5 2 3 1 4 3 4 2 3 4 2 4 4 3 1 3 1 5 4 2 2 4 1 4 3 6
输出 1
3 3 2
说明
考虑样例。在第二年，存在道路 $1-2$、$2-3$ 和 $3-4$。因此，在这一年可以从任意城市到达其他任意城市。
城市 $1$ 和 $3$ 之间没有直接道路，但在第二、三、四年可以通过路径 $1-2-3$ 互相到达。
城市 $4$ 和 $2$ 之间在第二、三年可以通过路径 $4-3-2$ 到达，而在第四年它们之间存在直接道路。