Aoi 和 Bitaro 是 JOI 国国家情报局的间谍。他们这次的任务是对 IOI 国进行秘密调查。Bitaro 潜入 IOI 国，而 Aoi 从 JOI 国向 Bitaro 发送指令。

在潜入之前，Aoi 和 Bitaro 获得了 IOI 国的地图。IOI 国有 $N$ 个城市，编号为 $0$ 到 $N-1$。此外，IOI 国有 $M$ 条道路，编号为 $0$ 到 $M-1$。道路 $i$ ($0 \le i \le M-1$) 双向连接城市 $A_i$ 和城市 $B_i$，长度为 $C_i$。可以通过经过一些道路在任意两个城市之间往来。Bitaro 通过这些道路在 IOI 国的城市间移动。

此外，还有 $Q$ 个调查计划。第 $j$ 个计划 ($0 \le j \le Q-1$) 涉及调查 IOI 国的城市 $T_j$。

以上所有信息最初都提供给了 Aoi 和 Bitaro。随后，Bitaro 开始潜入 IOI 国。

Bitaro 成功躲避了众多追捕者，击败了刺客，最终成功潜入 IOI 国的城市 $0$。然而，由于潜入行动极其困难，Bitaro 丢失了关于 IOI 国的一些信息。具体来说，Bitaro 丢失了 $K$ 条道路的长度信息，即道路 $X_0, X_1, \dots, X_{K-1}$。换句话说，Bitaro 不再知道 $C_{X_0}, C_{X_1}, \dots, C_{X_{K-1}}$ 的值。请注意，虽然 Bitaro 丢失了这些信息，但 Aoi 仍然保留着它们。

Bitaro 立即向 Aoi 报告了他丢失了哪些道路的长度信息。

为了完成任务，Bitaro 想要知道从城市 $0$ 到 $Q$ 个调查计划中每个目标城市的最短路径。

Aoi 将向 Bitaro 发送一个由字符 '0' 或 '1' 组成的字符串来协助他。由于存在被拦截的风险，Aoi 希望最小化发送给 Bitaro 的内容。

编写一个程序来实现 Aoi 发送字符串给 Bitaro 的策略（给定关于 IOI 国的信息、调查计划以及 Bitaro 丢失信息的道路）。同时，编写一个程序来实现 Bitaro 在拥有他所掌握的信息和 Aoi 发送的字符串的情况下寻找最短路径的策略。

实现细节

你需要提交 2 个文件。

第一个文件是 Aoi.cpp。该文件旨在实现 Aoi 的策略，并应实现以下函数。程序应使用预处理指令 #include 包含 Aoi.h。

• std::string aoi(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X)

该函数对每个测试用例仅调用一次。

• 参数 $N$ 是 IOI 国的城市数量。
• 参数 $M$ 是 IOI 国的道路数量。
• 参数 $Q$ 是调查计划的数量。
• 参数 $K$ 是 Bitaro 丢失长度信息的道路数量。
• 参数 $A, B, C$ 是长度为 $M$ 的数组。它们表示道路 $i$ ($0 \le i \le M-1$) 双向连接城市 $A[i]$ 和城市 $B[i]$，长度为 $C[i]$。
• 参数 $T$ 是长度为 $Q$ 的数组。它表示第 $j$ 个计划 ($0 \le j \le Q-1$) 涉及调查城市 $T[j]$。
• 参数 $X$ 是长度为 $K$ 的数组。它表示 Bitaro 丢失了道路 $X[0], X[1], \dots, X[K-1]$ 的长度信息。
• 返回值是 Aoi 发送给 Bitaro 的字符串 $s$。
• 字符串 $s$ 的每个字符必须是 '0' 或 '1'。如果不满足此条件，你的程序将被判为 Wrong Answer [1]。
• 字符串 $s$ 的长度最多为 $12\,000$。如果不满足此条件，你的程序将被判为 Wrong Answer [2]。

第二个文件是 Bitaro.cpp。该文件旨在实现 Bitaro 的策略，并应实现以下函数。程序应使用预处理指令 #include 包含 Bitaro.h。

• void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X, std::string s)

该函数在 aoi 函数被调用后仅调用一次。

• 参数 $N, M, Q, K, A, B, C, T, X$ 的含义与上述相同。
• 参数 $s$ 是一个由 '0' 或 '1' 组成的字符串，代表 Aoi 发送给 Bitaro 的字符串。

在 Bitaro.cpp 中，你的程序可以调用以下函数：

• void answer(const std::vector<int> &e)

在对该函数的第 $(j+1)$ 次调用 ($0 \le j \le Q-1$) 中，你必须回答从城市 $0$ 到城市 $T_j$（第 $j$ 个调查计划的目标）的最短路径。

• 参数 $e$ 是一个表示从城市 $0$ 到城市 $T_j$ 的最短路径的数组。
• 设 $n$ 为数组 $e$ 的长度。元素 $e[0], e[1], \dots, e[n-1]$ 是最短路径中道路的索引，按遍历顺序排列。
• 如果存在多条可能的最短路径，可以选择其中任意一条作为答案。
• 参数 $e$ 的每个元素必须在 $0$ 到 $M-1$ 之间。如果不满足此条件，你的程序将被判为 Wrong Answer [3]。
• 参数 $e$ 指示的道路序列必须构成一条从城市 $0$ 到城市 $T_j$ 的路径。更正式地说，它必须满足以下条件： 存在一个数字序列 $u_0, u_1, \dots, u_n$，使得：
  • $u_0 = 0$。
  • $u_n = T_j$。
  • 道路 $e[k]$ ($0 \le k \le n-1$) 连接城市 $u_k$ 和城市 $u_{k+1}$。 如果不满足这些条件，你的程序将被判为 Wrong Answer [4]。
• 如果参数 $e$ 指示的道路序列不是从城市 $0$ 到城市 $T_j$ 的所有路径中的最短路径，你的程序将被判为 Wrong Answer [5]。此处，路径长度定义为所用道路长度之和。
• answer 函数必须被调用恰好 $Q$ 次。如果在 bitaro 函数执行结束时对 answer 函数的调用次数不等于 $Q$，你的程序将被判为 Wrong Answer [6]。

重要提示

• 你的程序可以实现其他内部函数或使用全局变量。提交的文件将与评测程序一起编译，并成为单个可执行文件。所有全局变量和内部函数都应在匿名命名空间中声明，以避免与其他文件冲突。评测时，它将作为 Aoi 和 Bitaro 两个进程执行。Aoi 进程和 Bitaro 进程不能共享全局变量。
• 你的程序不得使用标准输入和标准输出。你的程序不得通过任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。

编译与测试运行

你可以从竞赛网页下载包含示例评测程序的压缩包来测试你的程序。压缩包中还包含你的程序的示例源文件。

示例评测程序是 grader.cpp。为了测试你的程序，将 grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h 放在同一目录下，并运行以下命令来编译你的程序。或者，你可以运行压缩包中包含的 compile.sh。

g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp

编译成功后，将生成可执行文件 grader。

请注意，实际的评测程序与示例评测程序不同。示例评测程序将作为一个单一进程执行，它将从标准输入读取输入数据，并将结果写入标准输出和标准错误输出。

输入格式 1

N M
A0 B0 C0
A1 B1 C1
...
AM-1 BM-1 CM-1
Q
T0 T1 ... TQ-1
K
X0 X1 ... XK-1

输出格式 1

(输出结果)

说明

如果你的程序被判为 Wrong Answer [1], [2], [3], [4] 或 [6]，示例评测程序会在标准错误输出中写入其类型，例如 “Wrong Answer [1]”。标准输出不会有任何输出。

如果不是上述情况，aoi 函数返回的字符串 $s$ 的长度将以 “Accepted: 2024” 的格式输出到标准错误输出。此外，在对 answer 函数的第 $(j+1)$ 次调用 ($0 \le j \le Q-1$) 中，路径的长度将输出到标准输出的第 $(j+1)$ 行。示例评测程序不会检查路径是否为最短路径。

如果你的程序满足多种 Wrong Answer 的条件，示例评测程序仅报告其中一种。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 10\,000$。
• $1 \le M \le 20\,000$。
• $1 \le Q \le 16$。
• $1 \le K \le 300$。
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le M-1$)。
• $(A_i, B_i) \neq (A_j, B_j)$ ($0 \le i < j \le M-1$)。
• $1 \le C_i \le 10^{12}$ ($0 \le i \le M-1$)。
• $1 \le T_j \le N-1$ ($0 \le j \le Q-1$)。
• $T_j \neq T_k$ ($0 \le j < k \le Q-1$)。
• $0 \le X_k \le M-1$ ($0 \le k \le K-1$)。
• $X_k \neq X_l$ ($0 \le k < l \le K-1$)。
• 可以通过经过一些道路从任意城市到达任何其他城市。
• 所有输入值均为整数。

评分

如果你的程序在任何测试用例中被判为任何类型的 Wrong Answer [1] - [6] 或任何类型的运行时错误（TLE、MLE、异常终止等），你的得分为 0 分。

否则，评分基于所有测试用例中 aoi 函数返回的字符串 $s$ 的最大长度（记为 $L$）。

• 如果 $1561 \le L \le 12\,000$，得分为 $\lfloor \frac{100\,000}{L - 560} \rfloor$ 分。
• 如果 $0 \le L \le 1560$，得分为 100 分。

此处，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

样例

输入格式 1

3 3
1 2 1
0 2 2
0 1 3
2
2 1
2
0 1

输出格式 1

2
1

说明

从城市 $0$ 到城市 $1$ 的最短路径可以通过按顺序经过道路 $1$ 和 $0$ 来实现，或者直接通过道路 $2$ 实现。因此，对于本样例中对 answer 函数的第二次调用，调用 answer([2]) 也是可以接受的。