呢題係一道多階段（multi-pass）問題。

喺奇普托斯（Kivotos）嘅數碼檔案館入面，普拉娜（Plana）發現咗一批神秘嘅記錄，稱為「雙時態日誌（Bitemporal Logs）」。每份日誌由 $n$ 個標記為 $1$ 到 $n$ 嘅條目組成，構成一棵有根樹。不過，根據時間流係回溯性（邏輯 A）定係前瞻性（邏輯 B），結構上嘅限制會有所唔同：

• 邏輯 A：棵樹以條目 $1$ 為根；其餘每個條目 $i$ 都有一個父節點 $p_i$，滿足 $p_i < i$。
• 邏輯 B：棵樹以條目 $n$ 為根；其餘每個條目 $i$ 都有一個父節點 $q_i$，滿足 $q_i > i$。

為咗分析結構特性，普拉娜定義咗兩種類型嘅條目：

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

普拉娜觀察到一種叫做邏輯共鳴（Logical Resonance）嘅完美對稱性。一份邏輯 A 日誌同一份邏輯 B 日誌之間滿足呢個性質，當且僅當：

$$\text{For every } i\text{, entry } i \text{ is a Terminal in Logic A} \iff \text{entry } i \text{ is a Hub in Logic B.}$$

普拉娜已經喺數學上證明咗，喺呢個限制之下，合法嘅邏輯 A 日誌同邏輯 B 日誌嘅數量係完全相同嘅。而家，佢交畀你一項任務：設計一個通用翻譯協議——即係一個雙射（bijection）——將一種日誌格式轉換成另一種。

正確性評測

你嘅程序喺每個測試點上面會被執行兩次。喺第一次運行入面，你嘅程序需要將每份邏輯 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

輸入

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

輸出

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

範例 1，階段 2

輸入

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

輸出

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

範例 1 說明

下圖展示咗一種合法嘅雙射方案。