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

Input

5
1 4 1 2 5
3 1 2 1 1

Output

5 1 3 1 1

Explanation

The reasoning for the sample output is provided below: