想象一下，你需要求一个带权无向图中若干对顶点之间的最短路径长度。
听起来太简单了，不是吗？我们也这么觉得。
因此，在本题中，你的程序在每个测试点上将被运行两次。在第一次运行期间，你可以读取边权。在第二次运行期间，你将只获得没有边权的图，并且你需要求出若干对顶点之间的最短路径长度。
“没有边权我怎么知道最短路径？”你可能会问。这是一个非常合理的问题，所以我们会让它变得简单一些：
- 如果在第一次运行期间给你 $m$ 个边权，你最多可以输出 $12m$ 个比特（作为一个二进制字符串），它们将被原封不动地传递给你程序的第二次运行。
- 最短路径长度不需要精确，但与实际值 $X$ 的误差不能超过其 $0.1\%$。换句话说，你的答案 $Y$ 必须满足条件 $0.999X \le Y \le 1.001X$。
输入格式
你的程序在每个测试点上将被运行两次。
第一行包含一个整数 $T$ ($1 \le |T| \le 10^5$)。其绝对值表示测试用例的数量。如果 $T < 0$，则是第一次运行；否则，是第二次运行。接着是 $|T|$ 个测试用例，格式如下。
如果是第一次运行：
下一行包含一个整数 $m$ ($1 \le m \le 10^5$)，表示图中的边数。
下一行包含 $m$ 个整数 $w_1, w_2, \dots, w_m$ ($1 \le w_i \le 10^6$)，表示边的权重。
如果是第二次运行：
下一行包含四个整数 $n, m, q, b$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le q \le 10^5$, $0 \le b \le 12m$)，分别表示顶点数、图中的边数、最短路径长度查询的数量，以及你在第一次运行期间发送的比特数。
下一行包含一个长度为 $b$ 的二进制字符串：即你在第一次运行期间打印的比特。
接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \ne b_i$)：表示下一条边的端点。该边的权重等于第一次运行中的 $w_i$（但在第二次运行中不会给出）。
接下来的 $q$ 行中，每行包含两个整数 $s, f$ ($1 \le s, f \le n$)，表示要求你求出从顶点 $s$ 到顶点 $f$ 的最短路径长度。
保证两次运行中给出的 $m$ 值相同，没有任意一对顶点被直接连接超过一次，且在单个文件中所有测试用例的 $n$ 之和以及 $m \cdot q$ 之和均不超过 $3 \cdot 10^5$。
输出格式
对于每个测试用例：
如果是第一次运行：
输出一个整数 $b$ ($0 \le b \le 12m$)：你打算传递给第二次运行的比特数。
如果 $b > 0$，在下一行输出一个长度为 $b$ 的二进制字符串：即比特本身。它们将被原封不动地传递给第二次运行。
如果是第二次运行：
对于 $q$ 个查询中的每一个，输出两个请求顶点之间的最短路径长度，如果不存在这样的路径，则输出 $-1$。你的答案不需要是整数，可以是小数，小数点后最多保留 15 位数字。如果你的答案与正确答案 $X$ 的绝对误差不超过 $X \cdot 10^{-3}$，则将被接受。
样例
输入样例 1
-2 3 4 5 6 1 1
输出样例 1
36 000000000100000000000101000000000110 12 000000000001
输入样例 2
2 4 3 5 36 000000000100000000000101000000000110 1 2 2 3 3 1 1 1 1 2 3 1 2 3 2 4 2 1 1 12 000000000001 1 2 1 2
输出样例 2
0.00000 4.00000 6.00000 5.00000 -1.00000 1.00000
说明
在原样例中，程序的两次运行输入和输出数据是用虚线和额外的空行隔开的。实际的输入和输出数据中既没有虚线也没有空行。
对于样例中的两个测试用例，在第一次运行期间，解决方案决定使用所有可用的比特，并将所有权重写为 12 位二进制数。然后，在第二次运行期间，解决方案计算出了所有边的权重，并打印了所有请求的最短路径长度，包括顶点 2 和 4 之间不存在路径的情况。
请注意，当你在测试系统中查看样例时，输入数据可能不完全对应于任何一次运行的实际输入数据，因为这些数据是根据测试的内部格式生成的。