你是一家软件公司的经理。公司今天有 $n$ 名程序员和 $m$ 个项目。项目 $i$ 只能由程序员 $a_i$ 和 $b_i$ 完成。程序员 $a_i$ 完成该项目需要 $t_i$ 字节秒，而程序员 $b_i$（若 $a_i \neq b_i$）完成该项目所需的时间是 $a_i$ 的两倍。这两名程序员可以分担工作：程序员 $a_i$ 可以选择一个实数 $x_i$ ($0 \le x_i \le t_i$)，并在项目 $i$ 上花费 $x_i$ 字节秒。在这种情况下，程序员 $b_i$ 需要在项目 $i$ 上花费 $2 \cdot (t_i - x_i)$ 字节秒。如果 $a_i = b_i$，则程序员 $a_i$ 必须独自完成整个项目，花费 $t_i$ 字节秒。

程序员 $a_i$ 和 $b_i$ 可以独立地在项目 $i$ 上工作。例如，他们可以同时工作，也可以在完全不同的时间段分配他们的工作时间。

每名程序员同一时间只能处理一个项目。一名程序员的总工作时间是他处理所有项目所花费时间之和。我们假设切换项目所需的时间可以忽略不计。

所有程序员今天同时开始工作。其中一些人会告诉你他们很赶时间，希望尽早下班。作为一名优秀的经理，你希望满足这些期望。然而，你目前还不确定具体哪些程序员赶时间。因此，你需要考虑 $q$ 个独立的场景。每个场景由一个非空的赶时间程序员子集描述。对于每个场景，请确定最小的实数 $T$，使得你可以安排程序员的工作，从而完成所有项目，且每名赶时间的程序员工作时间不超过 $T$ 字节秒。

可以证明结果均为有理数。请以既约分数形式输出所有答案。

输入格式

第一行包含三个整数 $n, m$ 和 $q$ ($1 \le n \le 13; 1 \le m \le 200; 1 \le q \le 10\,000$)，分别表示程序员人数、项目数量和需要考虑的场景数量。

接下来 $m$ 行，每行包含三个整数 $a_i, b_i$ 和 $t_i$ ($1 \le a_i, b_i \le n; 1 \le t_i \le 1\,000\,000$)，表示负责给定项目的程序员以及程序员 $a_i$ 完成该项目所需的时间。

接下来 $q$ 行描述各个场景；第 $i$ 个场景占一行，包含一个长度为 $n$ 的二进制字符串 $s_i$；如果第 $j$ 个字符为 '1'，则表示第 $j$ 名程序员赶时间，否则为 '0'。每个二进制字符串 $s_i$ 至少包含一个字符 '1'。

输出格式

输出应包含 $q$ 行；第 $i$ 行应包含一个以既约分数形式 $x/y$（满足 $\gcd(x, y) = 1$ 且 $y > 0$）表示的有理数 $T$，即第 $i$ 个场景中赶时间的程序员工作时间限制的最小值。

样例

输入 1

5 7 7
2 1 2
2 2 1
3 2 3
3 4 5
4 3 2
1 5 7
1 5 7
10000
01000
00110
11100
11111
01111
01111

输出 1

0/1
1/1
4/1
18/7
28/3
19/4
19/4

说明

在第一个场景中，程序员 1 可以立即下班，因为其他程序员可以处理剩下的项目。

在第二个场景中，程序员 2 必须完成第二个项目，这需要花费他 1 字节秒。

在第三个场景中，程序员 4 将在第五个项目上花费 2 字节秒，在第四个项目上花费 2 字节秒。程序员 3 应在第四个项目上花费 4 字节秒。

在第四个场景中，程序员 1 和 3 将分别在项目一和项目三上花费 $18/7$ 字节秒。程序员 2 需要分别花费 $5/7, 1$ 和 $6/7$ 字节秒来完成前三个项目，完成工作的时间同样为 $(5+7+6)/7 = 18/7$。

在第五个场景中，程序员 1 和 5 每人需要在最后两个项目上至少花费 $28/3$ 字节秒。存在一种策略，使得每名程序员在最多 $28/3$ 字节秒后完成工作。