No tempo livre, Bessie gosta de experimentar com física. Descobriu duas novas partículas subatômicas, mootrinos e antimootrinos. Como os pares matéria-antimatéria comuns, elas se aniquilam e desaparecem ao se encontrar. Sua peculiaridade é inverter a direção, mantendo a rapidez, sempre que Bessie olha para elas.

No último experimento, coloca um número par $N$ ($2 \leq N \leq 2 \cdot 10^5$) de partículas numa linha. À esquerda há um mootrino, e depois os dois tipos alternam. A partícula $i$ está em $p_i$ ($0 \leq p_1 < \cdots < p_N \leq 10^{18}$). Os mootrinos vão inicialmente à direita, os antimootrinos à esquerda; a partícula $i$ tem rapidez constante $s_i$ unidades por segundo ($1 \leq s_i \leq 10^9$).

Bessie observa nos seguintes momentos:

• Primeiro, $1$ segundo após o início.
• Depois, $2$ segundos após a primeira observação.
• Depois, $3$ segundos após a segunda observação.
• ...
• Depois, $n + 1$ segundos após a observação $n$.

Em cada observação anota quais partículas desapareceram.

O experimento pode demorar extremamente, então ela quer primeiro simulá-lo. Dada a configuração, determine quando, isto é, em qual número de observação, verá cada partícula desaparecer. Pode-se mostrar que todas desaparecerão no fim.

Entrada

Cada entrada contém $T$ ($1\le T\le 10$) casos independentes.

Cada caso tem três linhas: a primeira contém $N$, a segunda $p_1,\dots,p_N$ e a terceira $s_1\dots,s_N$.

A soma de todos os $N$ não ultrapassa $2\cdot 10^5$.

Saída

Para cada caso, imprima os números das observações de desaparecimento de cada partícula, separados por espaços.

Exemplos

Entrada 1

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

Saída 1

9 9
11 11
1 1
3 3

Nota

Para o primeiro caso, as primeiras $8$ observações são:

• O mootrino, inicialmente à direita, aparece em $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$.
• O antimootrino, inicialmente à esquerda, aparece em $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$.

Exatamente na observação $9$, as partículas se encontram em $6$ e se aniquilam.

No segundo caso, o antimootrino começa $1$ unidade mais à direita, então se encontram em $6.5$ meio segundo antes da observação $11$.

Importam apenas os números das observações, não os tempos ou posições.

Entrada 2

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

Saída 2

1 1 3 3
7 2 2 7

Nota

Para o primeiro caso:

• As duas partículas mais à esquerda se encontram em $2$ exatamente na observação $1$.
• As duas mais à direita se encontram em $6.5$ meio segundo antes da observação $3$.

Subtarefas

• A entrada três satisfaz $N = 2$.
• A entrada quatro satisfaz $N \leq 2000$ e $p_i \leq 10^4$ para todas as vacas.
• As entradas cinco a sete satisfazem $N \leq 2000$.
• As entradas oito a doze não têm restrições adicionais.

Autores do problema: Aryansh Shrivastava, Benjamin Qi