Description

给定一个无向连通图，边带权，可能存在重边自环。有 $q$ 次查询，每次给定 $x,y,z$，求所有以 $x$ 为起点，$y$ 为终点的路径（不要求为简单路径）中，边权和 $\bmod\ z$ 的最小值是多少。

交互方式

本题为交互题，只支持 C++ 语言提交，并且不支持 C++14 (GCC 9)。

你需要编写以下三个函数：

void Ready(int T, int subtask_id)

该函数在每个测试点中仅会调用一次，两个参数表示该测试点的数据组数和子任务编号。样例的子任务编号为 $-1$。

void Set(int n, int m, int q, vector <int> u, vector <int> v, vector <int> w)

在调用 Ready 之后，该函数会（在每个测试点中）被调用 $T$ 次，其中 $n,m$ 分别表示图的边数和点数。$u,v,w$ 的大小均为 $m$，$u[i],v[i],w[i]$ 表示图的一条边。

int Go(int x, int y, int z)

每次调用 Set 之后，该函数会（在每组数据中）被调用 $q$ 次，每次调用表示一次查询。返回值应为本次查询的答案。

你可以直接以下发文件中的 template.cpp 为基础编写。

Input Format

以下格式只对本地测试有效，但变量名的含义与实际评测相同。在实际评测中，请不要试图从标准输入（stdin）读取任何内容。

本题有多组数据。

第一行两个非负整数 $T$ 和 $\text{subtask\_id}$，分别表示数据组数和 Subtask 编号。

特别地，样例满足 $\text{subtask\_id}=-1$。

对于每组数据：

• 第一行是空行。
• 第二行三个非负整数 $n,m,q$。
• 接下来 $m$ 行，每行三个非负整数 $u,v,w$，表示一条边。
• 接下来 $q$ 行，每行三个正整数 $x,y,z$，表示一次查询。

Output Format

以下格式只对本地测试有效，但变量名的含义与实际评测相同。在实际评测中，请不要试图向标准输出（stdout）打印任何内容。

对于每组数据：

• 第一行是空行。
• 下面 $q$ 行，每行一个非负整数，表示答案。

2 -1
2 1 1
1 2 1
1 2 2
3 3 1
1 2 1
2 3 1
1 3 1
1 3 2

1
0

Hint

【样例解释】

对于第 $1$ 组数据的唯一一组询问，所有路径均形如 $1\to 2\to 1\to \dots \to 1\to 2$，可以证明所有路径的权值均为 $1$。

对于第 $2$ 组数据的唯一一组询问，路径 $1\to 2\to 3$ 权值为 $2\bmod 2=0$，路径 $1\to 3$ 的答案为 $1\bmod 2=1$，所以答案为 $0$。

【数据范围】

对于 $100\%$ 的数据，$0\le T\le 1.5 \times 10^4$，$-1 \le \text{subtask\_id} \le 9$，$0\le n,m,q\le 10^6$，$1\le u,v,x,y\le n$，$0\le w\le 10^9$，$1\le z\le 10^9$，保证图连通。

请下载附件中的 judge_result.jpeg 以了解交互库所占用资源的规模。如果你不想下载附件的话，我们在这里用一句话概括一下：保证交互库的运行时间不超过 0.15 秒，占用的内存不超过 60 MB。

本题开启子任务捆绑测试。

• Subtask 0 - Subtask 4（10 pts）：$n,m,q,w,z\le 10$，$T \le 1.5 \times 10^4$。
  • Subtask 0（2 pts）：$n=0$。
  • Subtask 1（2 pts）：$n=1$。
  • Subtask 2（1 pts）：$n=2$，$m \le 3$。
  • Subtask 3（4 pts）：$n \le 4$，$m \le 6$，$w \le 8$。
  • Subtask 4（1 pts）：在 Subtask 0 - Subtask 4 下无特殊限制。
• Subtask 5 - Subtask 9（90 pts）：$n,m,q\le 10^6$，$w,z \le 10^9$，$T=1$。
  • Subtask 5（20 pts）：$n,m,q,w,z\le 100$。
  • Subtask 6（20 pts）：$n,m,q,w,z\le 10^3$。
  • Subtask 7（10 pts）：$w,z\le 5$。
  • Subtask 8（10 pts）：$w=1$。
  • Subtask 9（30 pts）：在 Subtask 5 - Subtask 9 下无特殊限制。

Idea：ppip，Solution：喵仔牛奶，Code：ppip，Data：035966_L3