题目背景

在本题中，你需要将两个文件合并成一个文件提交。

不要引入任何头文件，并在文件头加入如下的内容：

#include <vector>
void answer(const std::vector<int> &);

题目描述

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 希望尽量减少发送的内容。

给定关于 IOI 国 的信息、调查计划以及 Bitaro 所遗失信息的道路，请编写程序实现 Aoi 的发送策略；同时，编写程序实现 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$ 的长度最多为 $12000$。若不满足此条件，你的程序将被判定为 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$ 是 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]$。
• 参数 $s$ 是一个每个字符均为 ‘0’ 或 ‘1’ 的字符串，表示 Aoi 发送给 Bitaro 的字符串。

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

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

• 在第 $(j+1)$ 次调用（$0 \le j \le Q-1$）该函数时，你需要回答从城市 $0$ 到第 $j$ 个调查计划目标城市 $T_j$ 的最短路径。
• 参数 e 是一个数组，表示从城市 $0$ 到城市 $T_j$ 的最短路径所经过的道路序列。
• 设数组 e 的长度为 $n$。元素 e[0], e[1], \ldots, e[n-1] 是该最短路径上按行进顺序经过的道路的编号。
• 若存在多条最短路径，任选其一作为答案即可。
• 参数 e 的每个元素必须在 $0$ 到 $M-1$ 之间。若不满足此条件，你的程序将被判定为 Wrong Answer [3]。
• 参数 e 所指示的道路序列必须构成一条从城市 $0$ 到城市 $T_j$ 的路径。更正式地，它必须满足以下条件。
  • 存在一列数字 $u_0, u_1, \ldots, 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。

注意，实际评测器不同于样例评测器。样例评测器作为单进程执行，从标准输入读取数据，并向标准输出与标准错误输出写出结果。

输入格式

样例评测器从标准输入读取如下数据。

$N$ $M$
$A_0$ $B_0$ $C_0$
$A_1$ $B_1$ $C_1$
$A_{M-1}$ $B_{M-1}$ $C_{M-1}$
$Q$
$T_0$ $T_1$ $\cdots$ $T_{Q-1}$
$K$
$X_0$ $X_1$ $\cdots$ $X_{K-1}$

输出格式

样例评测器向标准输出与标准错误输出输出如下信息（引号仅为说明）。

• 若你的程序被判为 Wrong Answer [1], [2], [3], [4], 或 [6]，样例评测器会在标准错误输出写出其类型，如 “Wrong Answer [1]”。标准输出不会输出任何内容。
• 否则，aoi 函数返回的字符串 $s$ 的长度会以 “Accepted: 2024” 的格式输出到标准错误输出。此外，在第 $(j+1)$ 次（$0 \le j \le Q-1$）对 answer 的调用中，路径长度会输出到标准输出的第 $(j+1)$ 行。样例评测程序 不会检查 该路径是否最短。

若你的程序同时满足多种 Wrong Answer 的条件，样例评测器仅报告其中一种。

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

提示

示例通信

下面给出一个样例评测器的输入及相应的函数调用。

样例输入 1	调用	返回值
$$\texttt{3 3}\ \texttt{1 2 1} \ \texttt{0 2 2} \ \texttt{0 1 3} \ \texttt{2} \ \texttt{2 1} \ \texttt{2} \ \texttt{0 1}$$	aoi(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [1, 2, 3], [2, 1], [0, 1])
^		"101001"
	bitaro(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [-1, -1, 3], [2, 1], [0, 1], "101001")
	answer([1])
	answer([1, 0])

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

从比赛网站下载的文件 sample-01-in.txt 与输入样例 $1$ 相对应。压缩包中的 sample-01-in.txt 与 sample-02-in.txt 可作为样例评测器的输入。

约束

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

• $2 \le N \le 10000$。
• $1 \le M \le 20000$。
• $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) \ne (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 \ne T_k$（$0 \le j < k \le Q-1$）。
• $0 \le X_k \le M-1$（$0 \le k \le K-1$）。
• $X_k \ne X_l$（$0 \le k < l \le K-1$）。
• 通过若干条道路可以在任意两座城市之间往来。
• 所有输入值均为整数。

评分

若你的程序在任意测试用例中被判定为 Wrong Answer [1] - [6]（见实现细节）或出现任意类型的运行时错误（TLE、MLE、异常结束等），你的得分为 $0$ 分。

否则，评分依据为在本题所有测试用例中，函数 aoi 返回的字符串 $s$ 的最大长度 $L$。

• 若 $1561 \le L \le 12000$，得分为 $\left\lfloor \dfrac{100\,000}{L-560} \right\rfloor$。
• 若 $0 \le L \le 1560$，得分为 $100$ 分。

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