给定一个二分图。左部包含 $n$ 个顶点，编号从 $1$ 到 $n$，右部也包含 $n$ 个顶点，编号从 $1$ 到 $n$。共有 $m$ 条边，每条边连接左部的一个顶点和右部的一个顶点。

你将被询问 $q$ 个独立的查询。在每个查询中，给定三个整数：$(a, b, k)$。

对于一个固定的查询 $(a, b, k)$，考虑在给定图上的以下过程。初始时，每个顶点（包括左部和右部）的权重均为 $0$。你可以执行以下操作任意次：

• 选择左部顶点的一个任意子集 $S$（可能为空），并选择一个正实数 $p > 0$。
• 令 $N(S)$ 为与 $S$ 中至少一个顶点相邻的右部顶点的集合。
• 将 $S$ 中每个顶点的权重增加 $a \cdot p$。
• 将 $N(S)$ 中每个顶点的权重增加 $b \cdot p$。

令 $p_1, p_2, \dots, p_\ell$ 为你在所有操作中使用的 $p$ 的值。这些值必须满足：

$$ \sum_{i=1}^\ell p_i \le 1. $$

你的目标是选择这些操作（子集 $S$ 和值 $p$），使得所有顶点（包括左部和右部）的权重总和最多为 $k$。在此约束下，你应该最大化左部所有顶点的权重总和。

对于每个查询 $(a, b, k)$，每次都从所有顶点权重为 $0$ 开始，计算可以获得的左部顶点权重总和的最大可能值。

输入格式

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

第一行包含三个整数：$n$、$m$ 和 $q$ ($1 \le n \le 2000$，$0 \le m \le 10^4$，$1 \le q \le 2 \cdot 10^5$)。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示左部顶点 $u$ 和右部顶点 $v$ 之间的一条边。

接下来的 $q$ 行，每行包含三个整数：$a$、$b$ 和 $k$ ($0 \le a, b \le 10^6$，$0 \le k \le 10^9$)，描述一个查询。

图中没有重边。$n$ 的总和不超过 $2000$。$m$ 的总和不超过 $10^4$。$q$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个查询，输出一个实数：该查询可以获得的左部顶点权重总和的最大可能值。假设你的答案为 $a$，评审系统的答案为 $b$。如果 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$，则你的答案将被视为正确。

样例

输入样例 1

2
5 8 3
1 2
1 3
2 4
2 5
3 1
3 3
4 2
5 4
1 3 5
2 1 2
5 2 3
2 3 3
1 2
1 1
2 1
1 0 2
0 2 2
3 1 4

输出样例 1

1.250000000000000
1.333333333333333
2.142857142857144
2.000000000000000
0.000000000000000
3.000000000000000