Anna 和 Bruno 参加了学校的汉字考试。Anna 和 Bruno 知道 $N$ 个汉字（编号从 $0$ 到 $N-1$）以及 $M$ 个单词（编号从 $0$ 到 $M-1$）。每个单词由他们已知的汉字组成，单词 $i$ 的第一个汉字是 $A_i$，最后一个汉字是 $B_i$。对于所有单词，满足 $A_i \neq B_i$。此外，所有单词的 $(A_i, B_i)$ 均不相同，即若 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$。每个单词都有一个书写所需时间 $C_i$。

考试中会提出 $Q$ 个如下问题： 问题 $j$：请回答一个以汉字 $S_j$ 开头并以汉字 $T_j$ 结尾的“汉字接龙”。

对于所有问题，满足 $S_j \neq T_j$。此外，所有问题的 $(S_j, T_j)$ 均不相同，即若 $i \neq j$，则 $(S_i, T_i) \neq (S_j, T_j)$。

如图 1 所示，“汉字接龙”是指一个单词序列，其中前一个单词的最后一个汉字与后一个单词的第一个汉字相同。以汉字 $S_j$ 开头并以汉字 $T_j$ 结尾的汉字接龙，是指第一个单词的第一个汉字为 $S_j$，且最后一个单词的最后一个汉字为 $T_j$ 的汉字接龙。

图 1: 以汉字 $S_j = \text{“报”}$ 开头，以汉字 $T_j = \text{“情”}$ 结尾的汉字接龙示例

虽然可能存在多种汉字接龙，但由于考试时间有限，必须回答其中总耗时最短的一个（若有多个最短的，回答其中任意一个即可）。汉字接龙的总耗时是其中包含的所有单词的耗时之和。

考试前夕，Bruno 忘记了 $K$ 个单词 $U_0, U_1, \dots, U_{K-1}$ 的耗时 $C_{U_0}, C_{U_1}, \dots, C_{U_{K-1}}$。这 $K$ 个单词恰好具有相同的第一个汉字。Anna 从 Bruno 那里得知了此事，但由于距离考试开始时间紧迫，她决定在考试期间将信息传达给 Bruno。在考试期间，Anna 可以通过敲击桌子的声音向 Bruno 发送 $0$ 或 $1$。Anna 希望发送 $0$ 或 $1$ 的次数尽可能少。Bruno 能否在考试中取得满分？

任务

给定汉字个数 $N$、单词个数 $M$ 及每个单词的首尾汉字、问题个数 $Q$ 及每个问题的信息、Bruno 忘记耗时的单词个数 $K$ 及其编号，这些信息分别提供给 Anna 和 Bruno。此外，Anna 被告知了全部 $M$ 个单词的耗时，而 Bruno 被告知了除那 $K$ 个单词之外的 $M-K$ 个单词的耗时。请编写程序，使 Anna 能向 Bruno 发送信息，并使 Bruno 在考试中取得满分。

实现细节

你必须使用同一种编程语言提交两个文件。

第一个文件名为 Anna.c 或 Anna.cpp。该文件实现 Anna 的策略，必须包含以下函数：

• void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[])

该函数仅在开始时被调用一次。 参数 $N$ 是汉字个数。 参数 $M$ 是单词个数。 参数 $A$ 是长度为 $M$ 的数组，$A[i]$ 是单词 $i$ 的第一个汉字的编号 $A_i$。 参数 $B$ 是长度为 $M$ 的数组，$B[i]$ 是单词 $i$ 的最后一个汉字的编号 $B_i$。 参数 $C$ 是长度为 $M$ 的数组，$C[i]$ 是书写单词 $i$ 的耗时 $C_i$。 参数 $Q$ 是问题个数。 参数 $S$ 是长度为 $Q$ 的数组，$S[j]$ 是问题 $j$ 的答案的第一个汉字编号 $S_j$。 参数 $T$ 是长度为 $Q$ 的数组，$T[j]$ 是问题 $j$ 的答案的最后一个汉字编号 $T_j$。 参数 $K$ 是 Bruno 忘记耗时的单词个数。 参数 $U$ 是长度为 $K$ 的数组，包含 Bruno 忘记耗时的单词编号 $U_0, U_1, \dots, U_{K-1}$。

在程序中，你可以调用以下函数向 Bruno 发送 $0$ 或 $1$： void Tap(int x) 参数 $x$ 是要发送给 Bruno 的 $0$ 或 $1$。 $x$ 必须为 $0$ 或 $1$。如果不满足，判为“不正解 [1]”。 如果 Tap 的调用次数超过 $1000$ 次，判为“不正解 [2]”。 * 如果 Tap 的调用被判定为不正解，程序将立即终止。

第二个文件名为 Bruno.c 或 Bruno.cpp。该文件实现 Bruno 的策略，必须包含以下函数：

• void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[])

该函数在 Anna 函数调用后被调用一次。 参数 $N, M, A, B, Q, S, T, K, U$ 与 Anna 中的相同。 参数 $C$ 是长度为 $N$ 的数组，$C[i]$ 是书写单词 $i$ 的耗时 $C_i$。如果 $i$ 是 $U_0, U_1, \dots, U_{K-1}$ 中的任意一个，则为 $-1$。 参数 $L$ 是从 Anna 发送过来的 $0$ 或 $1$ 的总个数。 参数 $X$ 是长度为 $L$ 的数组，表示从 Anna 发送过来的 $0$ 或 $1$ 的序列 $X[0], X[1], \dots, X[L-1]$。

在程序中，你可以调用以下函数： void Answer(int w) 参数 $w$ 必须是 $0$ 到 $M-1$ 之间的整数或 $-1$。如果不满足，判为“不正解 [3]”。 如果在调用了 $Q$ 次 $w = -1$ 的情况后再次调用此函数，判为“不正解 [4]”。 如果 Answer 的调用被判定为不正解，程序将立即终止。

程序必须使用此函数对每个问题进行回答，共重复 $Q$ 次。对于第 $j+1$ 次操作 ($0 \le j \le Q-1$)，执行以下步骤： 1. 针对问题 $j$ 的答案单词序列，从第一个单词到最后一个单词，依次将单词编号作为参数调用 Answer(w)。 2. 随后，调用 Answer(-1)。

在 Bruno 函数调用后，将进行答案判定： 如果 $w = -1$ 的调用次数少于 $Q$，判为“不正解 [5]”。 如果某个问题的答案序列长度为 $0$，判为“不正解 [6]”。 如果某个问题的答案中，前一个单词的最后一个汉字与后一个单词的第一个汉字不同，判为“不正解 [7]”。 如果某个问题 $j$ 的答案中，第一个单词的第一个汉字不是 $S_j$，或最后一个单词的最后一个汉字不是 $T_j$，判为“不正解 [8]”。 * 如果某个问题的答案总耗时不是最短的，判为“不正解 [9]”。

数据范围

所有输入数据满足以下条件： $2 \le N \le 300$ $1 \le M \le N \times (N - 1)$ $0 \le A_i < N$ ($0 \le i < M$) $0 \le B_i < N$ ($0 \le i < M$) $A_i \neq B_i$ ($0 \le i < M$) $(A_i, B_i) \neq (A_j, B_j)$ ($0 \le i < j < M$) $1 \le C_i \le 10^{16}$ ($< 2^{54}$) ($0 \le i < M$) $1 \le Q \le 60$ $0 \le S_j < N$ ($0 \le j < Q$) $0 \le T_j < N$ ($0 \le j < Q$) $S_j \neq T_j$ ($0 \le j < Q$) $(S_i, T_i) \neq (S_j, T_j)$ ($0 \le i < j < Q$) 存在以汉字 $S_j$ 开头并以汉字 $T_j$ 结尾的汉字接龙 ($0 \le j < Q$) $1 \le K \le 5$ $0 \le U_k < M$ ($0 \le k < K$) $U_i \neq U_j$ ($0 \le i < j < K$) * Bruno 忘记耗时的单词的第一个汉字相同，即 $A_{U_0} = A_{U_1} = \dots = A_{U_{K-1}}$。

子任务

子任务 1 [10 分]

• 满足 $Q \le 10$。
• 对于每个问题，存在一个使用不超过 $10$ 个单词的答案。
• Anna 最多只能调用 $1000$ 次 Tap。

子任务 2 [22 分]

• Anna 最多只能调用 $180$ 次 Tap。

子任务 3 [8 分]

• Anna 最多只能调用 $160$ 次 Tap。

子任务 4 [40 分]

• Anna 最多只能调用 $90$ 次 Tap。

子任务 5 [20 分]

• 设该子任务所有测试用例中 Tap 调用次数的最大值为 $L$。该子任务得分为：
  • 当 $L \le 64$ 时，得 $20$ 分。
  • 当 $64 < L < 90$ 时，得 $\lfloor (\frac{90 - L}{90 - 64})^2 \times 20 \rfloor$ 分（其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数）。
  • 当 $L \ge 90$ 时，得 $0$ 分。

样例

输入格式 1

4 5 3 2
2 1 10
0 2 20
3 1 30
0 1 40
3 0 50
3 0 50
3 1 30
0 1 30
1
3

输出格式 1

Anna 侧:
Tap(0)
Tap(0)
Tap(1)
Tap(0)

Bruno 侧:
Answer(4)
Answer(-1)
Answer(2)
Answer(-1)
Answer(1)
Answer(0)
Answer(-1)

说明

此例中 Anna 和 Bruno 接收到的参数如下表所示：

注意 $C$ 数组中 $C[1]$ 和 $C[3]$ 的值。