Permuturns

Alin and Blin are playing a game called Palatro. They share a deck of $N$ cards labeled $1$ through $N$. Alin writes the number $A_i$ on card $i$, and Blin writes the number $B_i$ on card $i$. Each player must write every number from $1$ to $N$ on exactly one card (thus $A$ and $B$ are permutations).

Clin is the referee of the game. He decides the order in which the two players must reveal their cards, giving $N$ requests of the form:
"Show the card with index $C_1$", then "Show the card with index $C_2$", and so on. Here $(C_1, C_2, \dots, C_N)$ represents a permutation of the numbers from $1$ to $N$.
At the beginning, Clin considers the first card shown ($C_1$) to be the winning card. Each time a new card $C_i$ is revealed, Clin checks the numbers written on it: if both Alin’s number and Blin’s number are greater than those on the current winning card, then card $C_i$ becomes the new winning card.

More formally, Clin uses the following algorithm to determine the winning card:

winner = C[1]
for i=2...N:
    if A[C[i]] > A[winner] and B[C[i]] > B[winner]:
        winner = C[i]

Task

For each $i$ from $1$ to $N$, determine in how many distinct ways Clin can give the requests such that the winning card is card $i$. Since the answer may be very large, output it modulo $10^9 + 7$.

Input data

The first line contains the integer $N$.
The second line contains $N$ integers, the elements of permutation $A$.
The third line contains $N$ integers, the elements of permutation $B$.

Output data

Print $N$ integers, separated by spaces, the answer for each $i$.

Restrictions

• $1 \leq N \leq 200 \ 000$.

Example

stdin

3
2 1 3
3 2 1

stdout

4 0 2

Explanation

$C = [1, 2, 3] \Rightarrow$ At the end of the algorithm, $winner = 1$
$C = [1, 3, 2] \Rightarrow$ At the end of the algorithm, $winner = 1$
$C = [2, 1, 3] \Rightarrow$ At the end of the algorithm, $winner = 1$
$C = [2, 3, 1] \Rightarrow$ At the end of the algorithm, $winner = 1$
$C = [3, 1, 2] \Rightarrow$ At the end of the algorithm, $winner = 3$
$C = [3, 2, 1] \Rightarrow$ At the end of the algorithm, $winner = 3$