W wolnym czasie Bessie zajmuje się fizyką doświadczalną. Odkryła dwa nowe rodzaje cząstek subatomowych, mootrinos i antimootrinos. Jak zwykłe pary materii i antymaterii, anihilują i znikają przy spotkaniu. Wyróżnia je to, że zmieniają kierunek ruchu, zachowując szybkość, ilekroć Bessie na nie spojrzy.

W najnowszym eksperymencie umieszcza parzystą liczbę $N$ ($2 \leq N \leq 2 \cdot 10^5$) cząstek na prostej. Z lewej zaczyna mootrino, potem typy się przeplatają. Cząstka $i$ leży w $p_i$ ($0 \leq p_1 < \cdots < p_N \leq 10^{18}$). Mootrinos początkowo idą w prawo, antimootrinos w lewo; cząstka $i$ ma stałą szybkość $s_i$ jednostek na sekundę ($1 \leq s_i \leq 10^9$).

Bessie obserwuje w następujących chwilach:

• Najpierw $1$ sekundę po rozpoczęciu eksperymentu.
• Potem $2$ sekundy po pierwszej obserwacji.
• Potem $3$ sekundy po drugiej obserwacji.
• ...
• Potem $n + 1$ sekund po obserwacji $n$.

Podczas każdej obserwacji zapisuje, które cząstki zniknęły.

Eksperyment może trwać bardzo długo, więc chce najpierw zasymulować wynik. Dla podanego układu określ kiedy, czyli przy jakim numerze obserwacji, zauważy zniknięcie każdej cząstki. Można wykazać, że wszystkie ostatecznie znikną.

Wejście

Każde wejście zawiera $T$ ($1\le T\le 10$) niezależnych testów.

Każdy test składa się z trzech wierszy: pierwszy zawiera $N$, drugi $p_1,\dots,p_N$, trzeci $s_1\dots,s_N$.

Suma wszystkich $N$ nie przekracza $2\cdot 10^5$.

Wyjście

Dla każdego testu wypisz numery obserwacji zniknięcia każdej cząstki, oddzielone spacjami.

Przykład

Wejście 1

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

Wyjście 1

9 9
11 11
1 1
3 3

Uwagi

W pierwszym teście pierwszych $8$ obserwacji wygląda tak:

• Mootrino, początkowo poruszające się w prawo, pojawia się w pozycjach $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$.
• Antimootrino, początkowo poruszające się w lewo, pojawia się w pozycjach $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$.

Dokładnie podczas obserwacji $9$ spotykają się w $6$ i anihilują.

W drugim teście antimootrino zaczyna o $1$ jednostkę bardziej w prawo, więc spotykają się w $6.5$ pół sekundy przed obserwacją $11$.

Liczą się tylko numery obserwacji, nie czasy ani pozycje.

Wejście 2

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

Wyjście 2

1 1 3 3
7 2 2 7

Uwagi

Dla pierwszego testu:

• Dwie najbardziej lewe cząstki spotykają się w $2$ dokładnie podczas obserwacji $1$.
• Dwie najbardziej prawe spotykają się w $6.5$ pół sekundy przed obserwacją $3$.

Podzadania

• Wejście trzecie spełnia $N = 2$.
• Wejście czwarte spełnia $N \leq 2000$ i $p_i \leq 10^4$ dla wszystkich krów.
• Wejścia od piątego do siódmego spełniają $N \leq 2000$.
• Wejścia od ósmego do dwunastego nie mają dodatkowych ograniczeń.

Autorzy zadania: Aryansh Shrivastava, Benjamin Qi