I had OA today, I got 3 questions to solve. I solved other two but couldn't solve this.

Pls share the solution.

Problem Statement

There is a door at Amazon Office which can be used only by one person at a time i. e either a person can enter from the door or exit but no two people can do it simultaneously. If two person going in the opposite direction arrived at the door at the same time then these 3 cases should be considered:-

If the door was not used before or it was not used in the previous second then the person who wants to exit goes first.

If the door has been used in the previous second for entering, then the person who wants to enter goes first.

If the door has been used in the previous second for exiting, then the person who wants to exist goes first.

If two people arrive at the same time and going in the same direction then the person whose name in the given list comes first will go first.

Note:- To cross the door, it will take exactly one second for each person.

Input

The first line of input contains a single integer N containing the number of people The second line of input contains N space- separated integers depicting the arrival time of the ith person. The last line of input containing N space- separated integers which are either 0 or 1. 0 indicates that the person wants to enter and 1 indicates he wants to exit.

Constraints:-

1 <= N <= 50000

0 <= Arrival[i] <= Arrival [i+1] <= 1000000000

Output

Print N space- separated integers denoting the time at which the ith person will cross the door.

Example

Sample Input:-

4

0 0 1 5

0 1 1 0

Sample Output:-

2 0 1 5

Explanation:-

At t = 0:- the first and the second person wants to enter and exit. As per case 1 2nd person will goes first.

At t=1:- the first and the 3rd person wants to enter and exit. As per case 3 the 3rd person goes first.

At t= 2:- only 1st is the only person standing so he goes.

At t = 3 and 4 no one wants to cross

At t = 5 the 4th person is the only one who wants to cross.

Sample Input:-

5

0 1 1 3 3

0 1 0 0 1

Sample Output:-

0 2 1 4 3