小 $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$ 求出符合条件的路径长度最大是多少。

输入格式

第一行三个正整数 $n,m,q$，分别表示顶点个数、边数与询问个数。

接下来 $m$ 行，每行四个正整数 $u_i,v_i,w_i,d_i$（保证 $u_i\neq v_i$），描述一条边。

接下来 $q$ 行，每行两个正整数 $l,r$（保证 $l\leq r$），表示一次询问。

输出格式

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

样例1

输入

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

输出

6
6
4
4
3

样例2

输入

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

输出

55
14
44
37
25

提示

对于所有数据，$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$。