In ihrer Freizeit beschäftigt sich Bessie mit experimenteller Physik. Kürzlich entdeckte sie neue subatomare Teilchen, mootrinos und antimootrinos. Wie gewöhnliche Materie-Antimaterie-Paare vernichten sie sich beim Zusammentreffen und verschwinden. Besonders ist jedoch, dass sie ihre Bewegungsrichtung bei gleicher Geschwindigkeit umkehren, sobald Bessie sie ansieht.

Für ihren neuesten Versuch legt sie eine gerade Anzahl $N$ ($2 \leq N \leq 2 \cdot 10^5$) Teilchen auf eine Linie. Links beginnt ein mootrino, danach wechseln die Typen ab. Teilchen $i$ liegt bei $p_i$ ($0 \leq p_1 < \cdots < p_N \leq 10^{18}$). Mootrinos bewegen sich zunächst rechts, antimootrinos links; Teilchen $i$ hat konstante Geschwindigkeit $s_i$ Einheiten pro Sekunde ($1 \leq s_i \leq 10^9$).

Bessie beobachtet zu folgenden Zeitpunkten:

• Zuerst $1$ Sekunde nach Versuchsbeginn.
• Dann $2$ Sekunden nach der ersten Beobachtung.
• Dann $3$ Sekunden nach der zweiten Beobachtung.
• ...
• Dann $n + 1$ Sekunden nach der $n$-ten Beobachtung.

Bei jeder Beobachtung notiert sie, welche Teilchen verschwunden sind.

Der Versuch kann extrem lange dauern, daher möchte sie das Ergebnis zunächst simulieren. Bestimme anhand des Aufbaus, wann, also bei welcher Beobachtungsnummer, sie das Verschwinden jedes Teilchens feststellt. Es lässt sich zeigen, dass schließlich alle verschwinden.

Eingabe

Jede Eingabe enthält $T$ ($1\le T\le 10$) unabhängige Testfälle.

Jeder Testfall besteht aus drei Zeilen: zuerst $N$, dann $p_1,\dots,p_N$, dann $s_1\dots,s_N$.

Die Summe aller $N$ ist höchstens $2\cdot 10^5$.

Ausgabe

Gib für jeden Testfall die Beobachtungsnummer des Verschwindens jedes Teilchens durch Leerzeichen getrennt aus.

Beispiele

Eingabe 1

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

Ausgabe 1

9 9
11 11
1 1
3 3

Hinweis

Im ersten Testfall sehen die ersten $8$ Beobachtungen so aus:

• Das mootrino, anfangs rechts unterwegs, liegt an $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$.
• Das antimootrino, anfangs links unterwegs, liegt an $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$.

Genau bei Beobachtung $9$ treffen sie sich an $6$ und vernichten sich.

Im zweiten Testfall beginnt das antimootrino $1$ Einheit weiter rechts; sie treffen sich an $6.5$ eine halbe Sekunde vor Beobachtung $11$.

Nur Beobachtungsnummern interessieren uns, keine Zeiten oder Positionen.

Eingabe 2

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

Ausgabe 2

1 1 3 3
7 2 2 7

Hinweis

Für den ersten Testfall:

• Die beiden linken Teilchen treffen sich an $2$ genau bei Beobachtung $1$.
• Die beiden rechten Teilchen treffen sich an $6.5$ eine halbe Sekunde vor Beobachtung $3$.

Teilaufgaben

• Eingabe drei erfüllt $N = 2$.
• Eingabe vier erfüllt $N \leq 2000$ und $p_i \leq 10^4$ für alle Kühe.
• Eingaben fünf bis sieben erfüllen $N \leq 2000$.
• Eingaben acht bis zwölf haben keine zusätzlichen Beschränkungen.

Aufgabenautoren: Aryansh Shrivastava, Benjamin Qi