Теперь Беси занялась физикой.
Она открыла пару субатомных частиц, которые назвала
mootrinos и
antimootrinos.
Как стандартные
пары материя-антиматерия,
mootrinos и antimootrinos аннигилируют друг друга и исчезают, когда
они встречаются.
Ещё эти частицы отличаются тем, что они переключают направление движения
(сохраняя скорость), когда Беси посмотрит на них.
В последнем эксперименте Беси разместила чётное число \(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\)).
Беси ведёт наблюдение в следующие моменты времени:
- Сначала через \(1\) секунду после начала эксперимента.
- Затем через \(2\) секунды после первого наблюдения.
- Затем через \(3\) секунды после второго наблюдения.
- ...
- Затем через \(n + 1\) секунду после \(n\)-го наблюдения.
После каждого наблюдения Беси помечает, какие частицы исчезли.
Этот эксперимент может потребовать слишком много времени для
завершения, поэтому Беси для начала хочет просимулировать результаты.
Помогите Беси определить, когда (т.e., номер наблюдения)
когда она обнаружит, что исчезли все частицы.
Можно доказать, что все частицы в конце концов исчезнут.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Каждый ввод состоит из
\(T\) (
\(1\le T\le 10\)) независимых подтестов.
Каждый подтест состоит из трёх строк.
Первая строка содержит \(N\), вторая строка содержит \(p_1,\dots,p_N\),
третья строка содержит \(s_1\dots,s_N\).
Гарантируется, что сумма всех \(N\) не превысит \(2\cdot 10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите номер наблюдения, на котором исчезнут все частицы,
разделяя одиночными пробелами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5
|
9 9
11 11
1 1
3 3
|