Problem Description

Pitaro has two sets of $N$ cards each. The first set of cards is named $A$ and has numbers $a_1$ to $a_N$ written on them in order from the top. The second set of cards is named $B$ and has numbers $b_1$ to $b_N$ written on them in order from the top.

Pitaro can rearrange the cards in set $B$ any way he likes, at any time, as many times as he wants.

Pitaro plays a game $N$ times as follows:

• In the $i$th game $(1 \leq i \leq N)$, the sequence of numbers written on the first $i$ cards of set $A$ is denoted as $C_i$.
• Pitaro rearranges the cards in set $B$ to maximize the number of times the sequence $C_i$ appears consecutively in the sequence of numbers written on the cards of set $B$.
• However, the appearances of $C_i$ must not overlap. For example, the sequence {1 2 1 2 1 2 1 2} can be considered as {(1 2 1 2) (1 2 1 2)}, which means the sequence {1 2 1 2} appears 2 times. Counting it as {(1 2 1 2) 1 2 1 2}, {1 2 (1 2 1 2) 1 2}, or {1 2 1 2 (1 2 1 2)} is not allowed.
• The number of times the sequence $C_i$ appears consecutively in the sequence of numbers written on the cards of set $B$ is the score for that game.

Write a program to determine the score Pitaro can achieve in each game.

Input Format

The input is given from the standard input in the following format:

$N$ $a_1$ $a_2$ $\cdots$ $a_N$ $b_1$ $b_2$ $\cdots$ $b_N$

Output Format

Output $N$ lines to the standard output. The $i$th line $(1 \leq i \leq N)$ should contain the score Pitaro can achieve in the $i$th game.

Sample Input and Output

Sample Input #1

5
1 2 3 4 5
1 2 2 1 3

Sample Output #1

2
2
1
0
0

Sample Input #2

5
1 1 1 1 1
1 1 1 1 1

Sample Output #2

5
2
1
1
1

Notes/Hints

Constraints

• All inputs are integers.
• $2 \leq N \leq 100,000$.
• $1 \leq a_i, b_i \leq 100,000$ $(1 \leq i \leq N)$.

Subtasks

1. ($16$ points) $N \leq 8$.
2. ($10$ points) $a_i = 1$ $(1 \leq i \leq N)$.
3. ($24$ points) $N \leq 1,000$.
4. ($50$ points) No additional constraints.

Sample Explanation 1

For example, by rearranging to {1 2 3 2 1}, $C_1$ can appear 2 times, by rearranging to {3 1 2 1 2}, $C_2$ can appear 2 times, and by rearranging to {2 1 2 3 1}, $C_3$ can appear 1 time. This input/output example satisfies subtasks $1, 3, 4$.

Sample Explanation 2

The only sequence that can be obtained from set $B$ is {1 1 1 1 1}. This input/output example satisfies subtasks $1, 2, 3, 4$.

见题面 Input 部分

见题面 Output 部分