最遥远的路

Problem Description

小 A 有一张 $n$ 个点 $m$ 条边的有向图，每条边形如 $u_i, v_i, w_i, d_i$，其中 $u_i, v_i$ 分别表示边的起点与终点，$w_i$ 是边的权值，而 $d_i$ 是边的长度。并不保证所有边的权值两两不同。 小 A 想在图中找到一条路径，可以经过重复的点，使得路径上每条边的权值均在 $[l, r]$ 中，且边权严格递增。他还希望路径上所有边的长度总和尽可能地大。 现在有 $q$ 组询问，每次给出 $[l, r]$，请帮小 A 求出符合条件的路径长度最大是多少。

Input

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。 对于每组测试数据，

• 第一行三个正整数 $n, m, q$，分别表示顶点个数、边数与询问个数。
• 接下来 $m$ 行，每行四个正整数 $u_i, v_i, w_i, d_i$（保证 $u_i \neq v_i$），描述一条边。
• 接下来 $q$ 行，每行两个正整数 $l, r$（保证 $l \leq r$），表示一次询问。

Output

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

Sample Input

2
5 5 5
1 3 4 4
5 2 3 3
2 3 2 1
3 4 1 2
2 4 5 3
1 5
3 5
4 4
2 4
1 3
3 10 5
2 3 11 13
2 3 7 8
1 3 13 19
2 3 16 18
3 2 20 19
3 2 5 6
2 1 10 11
3 1 18 14
3 1 6 1
3 2 1 17
3 20
5 7
6 19
15 20
1 9

Sample Output

6
6
4
4
3
55
14
44
37
25

Hint

对于所有数据，$1 \leq T \leq 5$，$2 \leq n \leq 50$，$1 \leq m \leq 5 \times 10 ^ 4$，$1 \leq q \leq 5 \times 10 ^ 5$，$1 \leq u_i, \ v_i \leq n$，$1 \leq l, \ r, \ w_i, \ d_i \leq 10 ^ 9$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（8）