這是一個多輪（multi-pass）問題。

在 Kivotos 的數位檔案庫中，Plana 發現了一系列被稱為「雙時態日誌」（Bitemporal Logs）的神祕記錄。每個日誌由 $n$ 個標記為 $1$ 到 $n$ 的條目組成，形成一棵有根樹。然而，根據時間流向是回溯式（Logic A）還是前瞻式（Logic B），其結構限制有所不同：

• Logic A：樹的根為條目 $1$；每個其他條目 $i$ 都有一個父節點 $p_i$，滿足 $p_i < i$。
• Logic B：樹的根為條目 $n$；每個其他條目 $i$ 都有一個父節點 $q_i$，滿足 $q_i > i$。

為了分析結構屬性，Plana 定義了兩種類型的條目：

• 終端（Terminal）：不作為任何其他條目之父節點的條目。
• 樞紐（Hub）：至少作為一個其他條目之父節點的條目。

Plana 觀察到一種稱為「邏輯共振」（Logical Resonance）的完美對稱性。此屬性在 Logic A 日誌與 Logic B 日誌之間成立，若且唯若：

對於每個 $i$，條目 $i$ 在 Logic A 中是終端 $\iff$ 條目 $i$ 在 Logic B 中是樞紐。

Plana 已從數學上證明，在此限制下，有效的 Logic A 日誌與 Logic B 日誌的數量是相同的。現在，她委託你設計一個「通用轉換協議」（Universal Translation Protocol）——一個雙射（bijection）——將一種日誌格式轉換為另一種。

評測正確性

你的程式在每次測試中會被執行兩次。在第一輪中，你的程式需要將每個 Logic A 日誌轉換為滿足邏輯共振條件的 Logic B 日誌。在第二輪中，給定由你的第一輪產生的 Logic B 日誌，你的程式需要精確還原出原始的 Logic A 日誌。

第二輪的輸入由與你第一輪輸出相同的 Logic B 日誌組成，順序可能不同。對於第二輪中的每個輸入 Logic B 日誌，你需要輸出其對應的 Logic A 日誌。如果對於每個這樣的 Logic B 日誌，你的輸出與產生它的原始 Logic 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$，代表 Logic 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$，代表 Logic 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$，代表轉換後的 Logic B 日誌。必須滿足 $q_n = 0$，且對於 $1 \le i \le n - 1$，$i < q_i \le n$。邏輯共振屬性必須成立：條目 $i$ 在 Logic A 中是終端，若且唯若條目 $i$ 在 Logic B 中是樞紐。

否則，若 $r = 2$，對於每個測試案例，輸出 $n$ 個以空格分隔的整數 $p_1, p_2, \dots, p_n$，代表還原後的 Logic 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 的一種可能有效雙射如下所示：