Nel tempo libero Bessie si diletta con la fisica sperimentale. Ha scoperto due nuove particelle subatomiche, mootrinos e antimootrinos. Come le normali coppie materia-antimateria, si annichilano e scompaiono quando si incontrano. La particolarità è che invertono la direzione, mantenendo la velocità in modulo, ogni volta che Bessie le guarda.

Per l'ultimo esperimento colloca un numero pari $N$ ($2 \leq N \leq 2 \cdot 10^5$) di particelle su una linea. A sinistra c'è un mootrino, poi i tipi si alternano. La particella $i$ è in $p_i$ ($0 \leq p_1 < \cdots < p_N \leq 10^{18}$). I mootrinos vanno inizialmente a destra, gli antimootrinos a sinistra; la particella $i$ ha velocità costante $s_i$ unità al secondo ($1 \leq s_i \leq 10^9$).

Bessie osserva nei seguenti momenti:

• Prima, $1$ secondo dopo l'inizio.
• Poi, $2$ secondi dopo la prima osservazione.
• Poi, $3$ secondi dopo la seconda osservazione.
• ...
• Poi, $n + 1$ secondi dopo l'osservazione $n$.

A ogni osservazione registra quali particelle sono scomparse.

L'esperimento può durare moltissimo, quindi vuole prima simularne il risultato. Dato l'allestimento, determina quando, cioè a quale numero di osservazione, noterà la scomparsa di ogni particella. Si può dimostrare che tutte finiranno per scomparire.

Input

Ogni input contiene $T$ ($1\le T\le 10$) casi indipendenti.

Ogni caso ha tre righe: la prima contiene $N$, la seconda $p_1,\dots,p_N$, la terza $s_1\dots,s_N$.

La somma di tutti gli $N$ non supera $2\cdot 10^5$.

Output

Per ogni caso, stampa i numeri di osservazione delle scomparse di ogni particella, separati da spazi.

Esempi

Input 1

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

Output 1

9 9
11 11
1 1
3 3

Spiegazione

Nel primo caso, le prime $8$ osservazioni sono:

• Il mootrino, inizialmente a destra, appare nelle posizioni $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$.
• L'antimootrino, inizialmente a sinistra, appare nelle posizioni $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$.

Esattamente all'osservazione $9$ si incontrano in $6$ e si annichilano.

Nel secondo caso, l'antimootrino parte $1$ unità più a destra, quindi si incontrano in $6.5$ mezzo secondo prima dell'osservazione $11$.

Contano solo i numeri delle osservazioni, non tempi o posizioni.

Input 2

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

Output 2

1 1 3 3
7 2 2 7

Spiegazione

Per il primo caso:

• Le due particelle più a sinistra si incontrano in $2$ esattamente all'osservazione $1$.
• Le due più a destra si incontrano in $6.5$ mezzo secondo prima dell'osservazione $3$.

Sottoproblemi

• L'input tre soddisfa $N = 2$.
• L'input quattro soddisfa $N \leq 2000$ e $p_i \leq 10^4$ per tutte le mucche.
• Gli input da cinque a sette soddisfano $N \leq 2000$.
• Gli input da otto a dodici non hanno vincoli aggiuntivi.

Autori del problema: Aryansh Shrivastava, Benjamin Qi