閒暇時，Bessie 喜歡涉獵實驗物理。她最近發現了一對新的亞原子粒子，名為 mootrinos 和 antimootrinos。與普通的物質—反物質對一樣，它們相遇時會相互湮滅並消失。然而，它們的獨特之處在於，每當 Bessie 看著它們時，它們都會改變運動方向，同時保持速率不變。

在最新的實驗中，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$ 秒後。

每次觀測時，Bessie 記錄哪些粒子已經消失。

實驗可能需要極長時間才能結束，因此 Bessie 想先模擬結果。給定實驗設定，請幫助她確定何時（即第幾次觀測）會發現每個粒子消失！可以證明所有粒子最終都會消失。

輸入格式

每份輸入包含 $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