给定一个包含 $n$ 个顶点和 $m$ 条边的有向无环图。顶点编号为 $1, 2, \dots, n$，边编号为 $1, 2, \dots, m$。

你需要处理 $q$ 次询问。在第 $i$ 次询问中，给定四个整数 $u_i, v_i, l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le m$)。你需要回答仅使用编号在 $k$ ($l_i \le k \le r_i$) 范围内的边时，顶点 $u_i$ 是否能到达顶点 $v_i$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。对于每个测试用例：

第一行包含三个整数 $n, m$ 和 $q$ ($2 \le n \le 50\,000, 1 \le m \le 100\,000, 1 \le q \le 50\,000$)，分别表示顶点数、边数和询问数。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i < v_i \le n$)，表示一条从顶点 $u_i$ 到顶点 $v_i$ 的有向边。

接下来的 $q$ 行，第 $i$ 行包含四个整数 $u_i, v_i, l_i$ 和 $r_i$ ($1 \le u_i < v_i \le n, 1 \le l_i \le r_i \le m$)，描述第 $i$ 次询问。

输出格式

对于每次询问，输出一行。如果仅使用编号在 $k$ ($l_i \le k \le r_i$) 范围内的边时，顶点 $u_i$ 能到达顶点 $v_i$，则输出 “YES”。否则，输出 “NO”。

样例

输入 1

1
5 6 5
1 2
1 3
3 4
2 4
2 5
3 5
3 5 1 5
3 5 1 6
1 4 1 6
1 4 2 3
1 4 4 5

输出 1

NO
YES
YES
YES
NO