Pendant son temps libre, Bessie aime expérimenter en physique. Elle a découvert deux nouvelles particules subatomiques, les mootrinos et antimootrinos. Comme les paires matière-antimatière ordinaires, elles s'annihilent et disparaissent en se rencontrant. Leur particularité est d'inverser leur direction, en gardant la même vitesse, chaque fois que Bessie les regarde.

Pour son dernier essai, elle place un nombre pair $N$ ($2 \leq N \leq 2 \cdot 10^5$) de particules sur une droite. À gauche se trouve un mootrino, puis les deux types alternent. La particule $i$ est en $p_i$ ($0 \leq p_1 < \cdots < p_N \leq 10^{18}$). Les mootrinos vont initialement à droite, les antimootrinos à gauche ; la particule $i$ a une vitesse constante de $s_i$ unités par seconde ($1 \leq s_i \leq 10^9$).

Bessie observe aux instants suivants :

• D'abord $1$ seconde après le début.
• Puis $2$ secondes après la première observation.
• Puis $3$ secondes après la deuxième observation.
• ...
• Puis $n + 1$ secondes après la $n$-ème observation.

À chaque observation, elle note quelles particules ont disparu.

L'expérience peut durer extrêmement longtemps, alors Bessie veut d'abord la simuler. À partir de sa configuration, déterminez quand, c'est-à-dire à quel numéro d'observation, elle constatera la disparition de chaque particule. On peut montrer qu'elles finiront toutes par disparaître.

Entrée

Chaque entrée contient $T$ ($1\le T\le 10$) tests indépendants.

Chaque test comporte trois lignes : la première contient $N$, la deuxième $p_1,\dots,p_N$, la troisième $s_1\dots,s_N$.

La somme de tous les $N$ ne dépasse pas $2\cdot 10^5$.

Sortie

Pour chaque test, affichez les numéros d'observation des disparitions de chaque particule, séparés par des espaces.

Exemples

Entrée 1

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

Sortie 1

9 9
11 11
1 1
3 3

Remarque

Pour le premier test, voici les $8$ premières observations :

• Le mootrino, initialement à droite, apparaît aux positions $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$.
• L'antimootrino, initialement à gauche, apparaît aux positions $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$.

Exactement à l'observation $9$, les particules se rencontrent en $6$ et s'annihilent.

Dans le deuxième test, l'antimootrino part $1$ unité plus à droite, donc elles se rencontrent en $6.5$ une demi-seconde avant l'observation $11$.

Seuls les numéros d'observation comptent, pas les instants ni les positions.

Entrée 2

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

Sortie 2

1 1 3 3
7 2 2 7

Remarque

Pour le premier test :

• Les deux particules les plus à gauche se rencontrent en $2$ exactement à l'observation $1$.
• Les deux particules les plus à droite se rencontrent en $6.5$ une demi-seconde avant l'observation $3$.

Sous-tâches

• L'entrée trois vérifie $N = 2$.
• L'entrée quatre vérifie $N \leq 2000$ et $p_i \leq 10^4$ pour toutes les vaches.
• Les entrées cinq à sept vérifient $N \leq 2000$.
• Les entrées huit à douze n'ont aucune contrainte supplémentaire.

Auteurs du problème : Aryansh Shrivastava, Benjamin Qi