В свободное время Bessie увлекается экспериментальной физикой. Недавно она открыла пару новых субатомных частиц, mootrinos и antimootrinos. Как обычные пары вещества и антивещества, они аннигилируют и исчезают при встрече. Их особенность в том, что каждый взгляд Bessie меняет направление их движения, сохраняя скорость.

В новом опыте Bessie разместила чётное число $N$ ($2 \leq N \leq 2 \cdot 10^5$) частиц на прямой. Слева стоит mootrino, далее два вида чередуются, и частица $i$ находится в $p_i$ ($0 \leq p_1 < \cdots < p_N \leq 10^{18}$). Mootrinos изначально движутся вправо, antimootrinos — влево, а частица $i$ имеет постоянную скорость $s_i$ единиц в секунду ($1 \leq s_i \leq 10^9$).

Bessie наблюдает в следующие моменты:

• Сначала через $1$ секунду после начала опыта.
• Затем через $2$ секунды после первого наблюдения.
• Затем через $3$ секунды после второго наблюдения.
• ...
• Затем через $n + 1$ секунд после $n$-го наблюдения.

При каждом наблюдении Bessie записывает, какие частицы исчезли.

Опыт может длиться чрезвычайно долго, поэтому Bessie хочет сначала смоделировать результат. По заданной установке определите, когда, то есть при каком номере наблюдения, она заметит исчезновение каждой частицы. Можно показать, что все частицы в итоге исчезнут.

Входные данные

Каждый вход содержит $T$ ($1\le T\le 10$) независимых тестов.

Каждый тест состоит из трёх строк: первая содержит $N$, вторая $p_1,\dots,p_N$, третья $s_1\dots,s_N$.

Сумма всех $N$ не превышает $2\cdot 10^5$.

Выходные данные

Для каждого теста выведите через пробел номера наблюдений исчезновения всех частиц.

Примеры

Входные данные 1

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

Выходные данные 1

9 9
11 11
1 1
3 3

Примечание

В первом тесте первые $8$ наблюдений выглядят так:

• Mootrino, изначально движущийся вправо, находится в позициях $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$.
• Antimootrino, изначально движущийся влево, находится в позициях $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$.

Ровно при наблюдении $9$ две частицы встречаются в позиции $6$ и аннигилируют.

Во втором тесте antimootrino начинает на $1$ единицу правее, поэтому встреча в $6.5$ происходит за полсекунды до наблюдения $11$.

Нужны только номера наблюдений, а не времена или позиции.

Входные данные 2

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

Выходные данные 2

1 1 3 3
7 2 2 7

Примечание

Для первого теста:

• Две крайние левые частицы встречаются в $2$ ровно при наблюдении $1$.
• Две крайние правые частицы встречаются в $6.5$ за полсекунды до наблюдения $3$.

Подзадачи

• Вход три удовлетворяет $N = 2$.
• Вход четыре удовлетворяет $N \leq 2000$ и $p_i \leq 10^4$ для всех коров.
• Входы с пятого по седьмой удовлетворяют $N \leq 2000$.
• Во входах с восьмого по двенадцатый дополнительных ограничений нет.

Авторы задачи: Aryansh Shrivastava, Benjamin Qi