余暇に Bessie は実験物理を楽しんでいます。最近、mootrinos と antimootrinos という新しい亜原子粒子の対を発見しました。普通の物質と反物質の対のように、出会うと対消滅します。ただし、Bessie が見るたびに、速さは変えずに運動方向を反転するという特徴があります。

最新の実験では、偶数 $N$ 個（$2 \leq N \leq 2 \cdot 10^5$）の粒子を直線上に置きました。左端は mootrino で、二種類が交互に並び、$i$ 番目は位置 $p_i$（$0 \leq p_1 < \cdots < p_N \leq 10^{18}$）にあります。mootrinos は最初右へ、antimootrinos は最初左へ進み、$i$ 番目の一定の速さは毎秒 $s_i$ 単位（$1 \leq s_i \leq 10^9$）です。

Bessie は次の時刻に観測します。

• 最初は実験開始から $1$ 秒後。
• 次は最初の観測から $2$ 秒後。
• 次は二回目の観測から $3$ 秒後。
• ...
• 次は $n$ 回目の観測から $n + 1$ 秒後。

各観測で、どの粒子が消えたかを記録します。

実験には非常に長い時間がかかるかもしれないので、先に結果をシミュレーションしたいと考えています。実験の設定から、各粒子の消失を発見する時点、すなわち観測の番号を求めてください。すべての粒子が最終的に消えることを示せます。

入力

各入力は $T$ 個（$1\le T\le 10$）の独立したテストケースを含みます。

各テストケースは三行です。最初は $N$、二行目は $p_1,\dots,p_N$、三行目は $s_1\dots,s_N$ を含みます。

すべての $N$ の合計は $2\cdot 10^5$ 以下と保証されます。

出力

各テストケースについて、各粒子の消失を観測する番号を空白区切りで出力してください。

入出力例

入力 1

4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5

出力 1

9 9
11 11
1 1
3 3

注記

最初のテストでは、最初の $8$ 回の観測は次のようになります。

• mootrino（最初は右へ移動）の位置は $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$ です。
• antimootrino（最初は左へ移動）の位置は $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$ です。

その後、ちょうど $9$ 回目の観測で、二粒子は位置 $6$ で出会い対消滅します。

二番目のテストでは antimootrino がさらに $1$ 単位右から始まるので、$11$ 回目の観測の半秒前に位置 $6.5$ で出会います。

必要なのは観測番号だけで、時刻や位置ではないことに注意してください。

入力 2

2
4
1 3 5 8
1 1 1 1
4
1 4 5 8
1 1 1 1

出力 2

1 1 3 3
7 2 2 7

注記

最初のテストについて：

• 左端の二粒子は、ちょうど $1$ 回目の観測で位置 $2$ で出会います。
• 右端の二粒子は、$3$ 回目の観測の半秒前に位置 $6.5$ で出会います。

小課題

• 入力三は $N = 2$ を満たします。
• 入力四は $N \leq 2000$ を満たし、すべての牛について $p_i \leq 10^4$ です。
• 入力五から七は $N \leq 2000$ を満たします。
• 入力八から十二には追加の制約はありません。

問題作成者：Aryansh Shrivastava、Benjamin Qi