これはマルチパス問題です。

Kivotosのデジタルアーカイブにおいて、Planaは「Bitemporal Logs（双時間ログ）」として知られる謎の記録のコレクションを発見しました。各ログは $1$ から $n$ までの番号が付けられた $n$ 個の要素から構成され、根付き木を形成しています。ただし、時間の流れが遡及的（Logic A）か、前向き（Logic B）かによって、構造的な制約が異なります。

• Logic A: 木は要素 $1$ を根とします。他のすべての要素 $i$ は、$p_i < i$ を満たす親 $p_i$ を持ちます。
• Logic B: 木は要素 $n$ を根とします。他のすべての要素 $i$ は、$q_i > i$ を満たす親 $q_i$ を持ちます。

構造的特性を分析するために、Planaは2種類の要素を定義しました。

• Terminal（末端）: 他のどの要素の親でもない要素。
• Hub（ハブ）: 少なくとも1つの他の要素の親である要素。

Planaは「Logical Resonance（論理共鳴）」と呼ばれる完全な対称性を観察しました。この特性は、Logic AのログとLogic Bのログの間で、以下の場合にのみ成立します。

すべての $i$ について、要素 $i$ がLogic AにおいてTerminalである $\iff$ 要素 $i$ がLogic BにおいてHubである。

Planaはこの制約下において、有効なLogic AのログとLogic Bのログの数が同一であることを数学的に証明しました。今、彼女はあなたに、一方のログ形式を他方に変換するための全単射である「Universal Translation Protocol（普遍的変換プロトコル）」の設計を依頼しました。

注記: あなたの解法は、いずれの実行においてもインタラクティブな手順として評価されます。

評価の仕組み

あなたの解法は各テストケースで2回実行されます。1回目の実行では、Logic Aのログを、Logical Resonance条件を満たすLogic Bのログに変換する必要があります。2回目の実行では、1回目の実行で生成されたLogic Bのログが与えられ、元のLogic Aのログを正確に復元する必要があります。

2回目の実行の入力は、1回目の実行で出力したLogic Bのログと同じもの（順序は異なる可能性があります）で構成されます。各入力されたLogic Bのログに対して、それに対応するLogic Aのログを出力する必要があります。すべてのそのようなLogic Bのログに対して、あなたの出力が1回目の実行でそれを生成したLogic Aのログと完全に一致する場合、あなたの解法は正解とみなされます。

開発およびテストを支援するためのテストツールが提供されています。

入力

入力の最初の行には、実行番号 $r$ ($r \in \{1, 2\}$) とテストケース数 $T$ ($1 \le T \le 10^5$) が含まれます。

各テストケースについて、最初の行には整数 $n$ ($2 \le n \le 10^3$) が含まれます。

$r = 1$ の場合、2行目にはLogic Aのログを表す $n$ 個の整数 $p_1, p_2, \dots, p_n$ が含まれます。$p_1 = 0$ であり、かつ $2 \le i \le n$ に対して $1 \le p_i < i$ が要素 $i$ の親であることが保証されています。ここで、$0$ は親を持たない要素（すなわち根）を表します。

それ以外の場合（$r = 2$ の場合）、2行目にはLogic Bのログを表す $n$ 個の整数 $q_1, q_2, \dots, q_n$ が含まれます。$q_n = 0$ であり、かつ $1 \le i \le n - 1$ に対して $i < q_i \le n$ が要素 $i$ の親であることが保証されています。

すべてのテストケースにおける $n^2$ の総和は $10^7$ を超えないことが保証されています。

出力

$r = 1$ の場合、各テストケースについて、変換されたLogic Bのログを表す $n$ 個の整数 $q_1, q_2, \dots, q_n$ をスペース区切りで出力してください。$q_n = 0$ であり、かつ $1 \le i \le n - 1$ に対して $i < q_i \le n$ を満たす必要があります。また、Logical Resonanceの特性（要素 $i$ がLogic AでTerminalであることと、要素 $i$ がLogic BでHubであることが同値であること）が成立しなければなりません。

それ以外の場合（$r = 2$ の場合）、各テストケースについて、復元されたLogic Aのログを表す $n$ 個の整数 $p_1, p_2, \dots, p_n$ をスペース区切りで出力してください。

入出力例

入力例 1 (Pass 1)

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

出力例 1 (Pass 1)

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

入力例 2 (Pass 2)

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

出力例 2 (Pass 2)

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

注記

サンプル1の解説：考えられる有効な全単射を以下に示します。