Вы играете в популярную видеоигру Escape the BThouse. Как вы могли догадаться, цель игры — выбраться из дома.

Дом состоит из $n$ комнат, расположенных в ряд и пронумерованных от $1$ до $n$, и $n+1$ двери между ними. Первая дверь — это выход, расположенный в комнате $1$, аналогично, $(n+1)$-я дверь — это выход из комнаты $n$. Все остальные двери $2 \le i \le n$ соединяют комнаты $(i-1, i)$. Ваша цель — выйти из дома через первую или $(n+1)$-ю дверь.

Для открытия $i$-й двери требуется не менее $b_i$ очков опыта. Опыт можно получить, выполняя задания в комнатах, при этом задание в комнате $i$ дает $a_i$ очков опыта. Формально, для выполнения задания достаточно просто войти в комнату. Также в игре встроена механика монетизации: в любой момент времени вы можете приобрести произвольное количество опыта по цене $1$ единица опыта за $1$ игровую монету.

Вам нужно выбрать стартовую комнату, в которой ваш персонаж появится с $0$ очков опыта. Для каждой комнаты вычислите минимальное количество монет, необходимое для того, чтобы выбраться из дома, начав игру в этой комнате.

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

Первая строка содержит одно целое число $n$ ($1 \le n \le 10^6$).

Вторая строка содержит $n$ целых чисел $a_1, \dots, a_n$, разделенных пробелами ($0 \le a_i \le 10^9$).

Третья строка содержит $n+1$ целое число $b_1, \dots, b_{n+1}$, разделенных пробелами ($0 \le b_i \le 10^9$).

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

Выведите $n$ целых чисел $ans_1, \dots, ans_n$, разделенных пробелами, где $ans_i$ — минимальное количество монет, необходимое для завершения игры, начав в комнате $i$.

Подзадачи

Эта задача содержит 8 подзадач, соответствующих следующим требованиям:

1. $n \le 500$. Оценивается в 12 баллов.
2. $n \le 5000$. Оценивается в 8 баллов.
3. $n \le 2 \cdot 10^5$, $a_i = 0$. Оценивается в 10 баллов.
4. $n \le 2 \cdot 10^5$, $b_1 \le b_2 \le \dots \le b_{n+1}$. Оценивается в 10 баллов.
5. $n \le 2 \cdot 10^5$, $b_i \le 100$. Оценивается в 19 баллов.
6. $n \le 2 \cdot 10^5$. Оценивается в 21 балл.
7. Исходные ограничения задачи. Оценивается в 20 баллов.

Примеры

Пример 1

3
2 1 3
9 8 5 7

6 4 3

Пример 2

3
1 3 3
10 2 5 6

1 1 2

Примечание

Рассмотрим первый пример. Оптимальная стратегия для первой комнаты следующая:

1. Получить 2 единицы опыта в 1-й комнате.
2. Купить 6 единиц опыта за 6 монет.
3. Перейти во 2-ю комнату через 2-ю дверь.
4. Получить 1 единицу опыта во 2-й комнате.
5. Перейти в 1-ю комнату через 2-ю дверь.
6. Выйти через 1-ю дверь.

Всего требуется 6 монет.

Для второй комнаты:

1. Получить 1 единицу опыта во 2-й комнате.
2. Купить 4 единицы опыта за 4 монеты.
3. Перейти в 3-ю комнату через 3-ю дверь.
4. Получить 3 единицы опыта в 3-й комнате.
5. Выйти через 4-ю дверь.

Всего требуется 4 монеты.

Для третьей комнаты:

1. Получить 3 единицы опыта в 3-й комнате.
2. Купить 2 единицы опыта за 2 монеты.
3. Перейти во 2-ю комнату через 3-ю дверь.
4. Получить 1 единицу опыта во 2-й комнате.
5. Перейти в 3-ю комнату через 3-ю дверь.
6. Купить 1 единицу опыта за 1 монету.
7. Выйти через 4-ю дверь.

Всего требуется 3 монеты.