这是一个多轮交互问题。

在 Kivotos 的数字档案中，Plana 发现了一系列被称为“双时态日志”（Bitemporal Logs）的神秘记录。每个日志包含 $n$ 个条目，标记为 $1$ 到 $n$，构成一棵有根树。然而，根据时间流向是回顾性（逻辑 A）还是前瞻性（逻辑 B），其结构约束有所不同：

• 逻辑 A (Logic A)：树以条目 $1$ 为根；每个其他条目 $i$ 都有一个父节点 $p_i$，满足 $p_i < i$。
• 逻辑 B (Logic B)：树以条目 $n$ 为根；每个其他条目 $i$ 都有一个父节点 $q_i$，满足 $q_i > i$。

为了分析结构属性，Plana 定义了两种类型的条目：

• 终端 (Terminal)：不作为任何其他条目父节点的条目。
• 枢纽 (Hub)：至少作为其他一个条目父节点的条目。

Plana 观察到一种称为“逻辑共振”（Logical Resonance）的完美对称性。当且仅当满足以下条件时，逻辑 A 日志和逻辑 B 日志之间存在此属性：

对于每个 $i$，条目 $i$ 是逻辑 A 中的终端 $\iff$ 条目 $i$ 是逻辑 B 中的枢纽。

Plana 已经从数学上证明，在此约束下，有效的逻辑 A 日志和逻辑 B 日志的数量是相同的。现在，她委托你设计一个通用转换协议——一个双射——将一种日志格式转换为另一种。

说明：你的解决方案在每次运行中都将被评估为交互式过程。

评估正确性

你的解决方案在每次测试中会被执行两次。在第一轮中，你的解决方案需要将每个逻辑 A 日志转换为满足逻辑共振条件的逻辑 B 日志。在第二轮中，给定第一轮生成的逻辑 B 日志，你的解决方案需要精确恢复原始的逻辑 A 日志。

第二轮的输入由与你第一轮输出相同的逻辑 B 日志组成，顺序可能不同。对于第二轮中的每个输入逻辑 B 日志，你需要输出其对应的逻辑 A 日志。如果对于每个这样的逻辑 B 日志，你的输出与生成它的原始逻辑 A 日志完全相同，则你的解决方案被视为正确。

提供了一个测试工具来帮助你开发和测试你的解决方案。

输入格式

第一行包含两个整数 $r$ ($r \in \{1, 2\}$) 和 $T$ ($1 \le T \le 10^5$)，分别表示运行轮次和测试用例数量。

对于每个测试用例，第一行包含一个整数 $n$ ($2 \le n \le 10^3$)。

如果 $r = 1$，第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示逻辑 A 日志。保证 $p_1 = 0$，且对于 $2 \le i \le n$，$1 \le p_i < i$ 是条目 $i$ 所连接的条目。此处我们使用 $0$ 表示条目没有父节点（即根节点）。

否则，如果 $r = 2$，第二行包含 $n$ 个整数 $q_1, q_2, \dots, q_n$，表示逻辑 B 日志。保证 $q_n = 0$，且对于 $1 \le i \le n - 1$，$i < q_i \le n$ 是条目 $i$ 所连接的条目。

保证所有测试用例的 $n^2$ 之和不超过 $10^7$。

输出格式

如果 $r = 1$，对于每个测试用例，输出 $n$ 个以空格分隔的整数 $q_1, q_2, \dots, q_n$，表示转换后的逻辑 B 日志。必须满足 $q_n = 0$，且对于 $1 \le i \le n - 1$，$i < q_i \le n$。必须满足逻辑共振属性：条目 $i$ 是逻辑 A 中的终端，当且仅当条目 $i$ 是逻辑 B 中的枢纽。

否则，如果 $r = 2$，对于每个测试用例，输出 $n$ 个以空格分隔的整数 $p_1, p_2, \dots, p_n$，表示恢复后的逻辑 A 日志。

样例

样例输入 1 (第一轮)

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

样例输出 1 (第一轮)

3 3 4 0
3 4 4 0
2 3 4 0

样例输入 1 (第二轮)

2 3
4
2 3 4 0
4
3 3 4 0
4
3 4 4 0

样例输出 1 (第二轮)

0 1 1 1
0 1 1 2
0 1 2 1

说明

样例 1 的解释：展示了一种可能的有效双射。

逻辑 A 与逻辑 B 的对应关系