Krazy Golf

MAPS Team is keeping up with the kids, and wants to revitalise Golf, a historically slow and methodical sport, with the hyper-popular gaming trend of a battle royale!

The golf course is a standard $n$-hole course, however the scoring has been changed, because it makes way more sense for a higher score to mean a better golfer!

Each hole nets the player a certain amount of points, which accumulates throughout the course. However, at the end of every hole, there is a gate. If you do not have at least $g_i$ points, then you are eliminated from the competition!

One of the competitors, Lauren, has given you their scorecard - how many points they would likely score in each of the $n$ holes. She'd like to know how many holes she will get to play before being eliminated.

However, you don't always need to run the full $n$-hole course for the competition - you're allowed to start at any of the holes, as long as you complete each consecutive hole until hole $n$, or you are eliminated.

You'd like to know, for every possible starting hole - how many holes Lauren would be able to play before being eliminated.

Input

Input will begin with a single integer $n$ ($1 \leq n \leq 3\times 10^5$) - the number of holes in the course.

2 lines will follow, each containing $n$ integers.

The first line specifies the gate values $g_i$ ($0 \leq g_i \leq 10^9$) - If, after completing hole $i$, you do not have $g_i$ points, you are eliminated from the competition!

The second specifies the point values $p_i$ ($0 \leq p_i \leq 10^9$) - How many points Lauren can expect to receive from hole $i$.

Output

Output $n$ integers - representing how many holes Lauren would be able to play if starting at hole 1, 2, 3, $\ldots$ $n$.

Example 1

5
1 4 1 2 5
3 1 2 1 1

5 1 3 1 1

Explanation

The reasoning for the sample output is provided below: