Є \(N\) гравців, які стоять у колі, перенумеруємо їх \(1, 2, ..., N\) у порядку проти годинникової стрілки. Коли гравець \(i\) (\(1 \leq i \leq N\)) отримує м'яч у момент \(t\), то через \(S_i\) одиниці часу він передасть цей м'яч \(i+1\) гравцеві в момент часу \(t+S_i\).

Тут гравець \(N+1\) – це грацець під номером 1. Крім того, Степан передасть м'яч гравцеві \(i\) в момент \(T_i\).

Для кожного \(i\) (\(1 \leq i \leq N\)) знайдіть час, коли гравець \(i\) вперше отримує м'яча.

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(1 \le N \le 2 \times 10^5\))

Наступний  рядок містить \(N\) цілих чисел \(S_i\) (\(1 \le S_i \le 10^9\))

Наступний  рядок містить \(N\) цілих чисел \(T_i\) (\(1 \le T_i \le 10^9\))

Формат вихідних даних

У вихідний потік виведіть \(N\) рядків: \(i\)-й рядок містить шуканий час, коли гравець \(i\) вперше отримує м'яча.

Приклад вхідних даних

3
4 1 5
3 10 100

Приклад вихідних даних

3
7
8

Приклад вхідних даних

4
100 100 100 100
1 1 1 1

Приклад вихідних даних

1
1
1
1

Приклад вхідних даних

4
1 2 3 4
1 2 4 7

Приклад вихідних даних

1
2
4
7