En su tiempo libre, Bessie disfruta la física experimental. Ha descubierto dos nuevas partículas subatómicas, mootrinos y antimootrinos. Como los pares materia-antimateria ordinarios, se aniquilan y desaparecen al encontrarse. Lo especial es que invierten su dirección, manteniendo la rapidez, cada vez que Bessie las mira.

En su último experimento coloca un número par $N$ ($2 \leq N \leq 2 \cdot 10^5$) de partículas en una recta. A la izquierda hay un mootrino y luego alternan los dos tipos. La partícula $i$ está en $p_i$ ($0 \leq p_1 < \cdots < p_N \leq 10^{18}$). Los mootrinos van inicialmente a la derecha, los antimootrinos a la izquierda; la partícula $i$ tiene rapidez constante $s_i$ unidades por segundo ($1 \leq s_i \leq 10^9$).

Bessie observa en estos momentos:

• Primero, $1$ segundo después del comienzo.
• Luego, $2$ segundos después de la primera observación.
• Luego, $3$ segundos después de la segunda observación.
• ...
• Luego, $n + 1$ segundos después de la observación $n$.

En cada observación registra qué partículas han desaparecido.

El experimento podría tardar muchísimo, así que quiere simular primero el resultado. Dada la configuración, determina cuándo, es decir, en qué número de observación, verá desaparecer cada partícula. Se puede demostrar que todas acabarán desapareciendo.

Entrada

Cada entrada contiene $T$ ($1\le T\le 10$) casos independientes.

Cada caso consta de tres líneas: la primera contiene $N$, la segunda $p_1,\dots,p_N$ y la tercera $s_1\dots,s_N$.

La suma de todos los $N$ no supera $2\cdot 10^5$.

Salida

Para cada caso, imprime los números de observación de la desaparición de cada partícula, separados por espacios.

Ejemplos

Entrada 1

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

Salida 1

9 9
11 11
1 1
3 3

Nota

Para el primer caso, las primeras $8$ observaciones son:

• El mootrino, inicialmente a la derecha, aparece en $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$.
• El antimootrino, inicialmente a la izquierda, aparece en $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$.

Justo en la observación $9$, se encuentran en $6$ y se aniquilan.

En el segundo caso, el antimootrino empieza $1$ unidad más a la derecha, por lo que se encuentran en $6.5$ medio segundo antes de la observación $11$.

Solo importan los números de observación, no los tiempos ni las posiciones.

Entrada 2

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

Salida 2

1 1 3 3
7 2 2 7

Nota

Para el primer caso:

• Las dos partículas más a la izquierda se encuentran en $2$ justo en la observación $1$.
• Las dos más a la derecha se encuentran en $6.5$ medio segundo antes de la observación $3$.

Subtareas

• La entrada tres cumple $N = 2$.
• La entrada cuatro cumple $N \leq 2000$ y $p_i \leq 10^4$ para todas las vacas.
• Las entradas cinco a siete cumplen $N \leq 2000$.
• Las entradas ocho a doce no tienen restricciones adicionales.

Autores del problema: Aryansh Shrivastava, Benjamin Qi