Kaguya is a lazy girl: she couldn't be bothered to come up with a backstory for this problem, so you just need to know that it is related to Kaguya.

There are $n$ villages and $n-1$ roads, where the $i$-th road connects village $i$ and village $i+1$. Every year during the holidays, people from each village go out for a trip; specifically, people from village $i$ want to go to village $p_i$. It is guaranteed that $p$ is a permutation of length $n$. Note that some people may not want to leave their village, so it is possible that $p_i = i$.

The transportation system between these villages is peculiar: if the person currently at village $i$ wants to travel to village $i+1$, the person currently at village $i+1$ must also move to village $i$. In simple terms, every move consists of swapping the positions of people currently in adjacent villages.

There are checkpoints on some roads. If a swap involves a road with a checkpoint, a toll of $1$ must be paid; otherwise, no toll is required. All villagers are sufficiently intelligent and prioritize the collective interest: they will always choose a method that minimizes the total cost to fulfill their travel plans.

In year $0$, there are no checkpoints on any roads. Over the next $n-1$ years, the government plans to build a checkpoint on one road each year (so that after $n-1$ years, all roads have checkpoints). The plan for building checkpoints is a permutation $q$ of length $n-1$, where $q_i$ denotes that a checkpoint is built on the $i$-th road in year $i$.

Given the permutations $p$ and $q$, you need to output the total cost the villagers must pay to complete their travel plans for each year $i \in [1, n-1]$. Assume that in each year, the checkpoint is built before the travel takes place, and you only need to consider the cost of the villagers' travel for that year; after the trip, the villagers instantly teleport back to their original villages.

Input

The first line contains an integer $n$ ($n \geq 2$), representing the number of villages.

The second line contains a permutation of length $n$, and the third line contains a permutation of length $n-1$, representing the travel plan and the checkpoint construction plan, respectively.

Output

Output $n-1$ integers on a single line, where the $i$-th integer represents the minimum cost in year $i$.

Examples

Input 1

3
3 2 1
1 2

Output 1

2 3

Input 2

10
10 5 2 6 7 8 3 1 9 4
7 6 5 2 9 8 3 4 1

Output 2

13 18 19 23 24 24 24 24 25

Subtasks

Subtask 1 (13 points): $n \leq 8$.

Subtask 2 (29 points): $n \leq 400$.

Subtask 3 (17 points): $n \leq 5000$.

Subtask 4 (41 points): $n \leq 3 \times 10^5$.