Problem Statement

There are $N$ jobs numbered $1$ through $N$, and you want to complete them over $N$ days. You perform exactly one job per day.

Job $i$ can be performed on any day from day $L_i$ through day $R_i$. Here, the following conditions are guaranteed to hold for $L_i$ and $R_i$:

• $1 \leq L_i \leq i \leq R_i \leq N$
• $1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N$
• $1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N$

Particularly, from the first condition, it follows that it is possible to complete all $N$ jobs over $N$ days.

Furthermore, each job has a type of L or R. Initially, all jobs are of type R.

The cost of performing a job is defined as follows:

• Suppose job $i$ is performed on day $x_i$. If job $i$ is of type L, the cost is defined as $x_i-L_i$; if it is of type R, the cost is defined as $R_i-x_i$.

From now on, there will be $N$ queries that change the type of a job to L. In the $i$-th query, the type of job $P_i$ is changed to L.

For each $k=0,1,\ldots,N$, solve the following problem:

• Consider the state after processing the first $k$ queries. Find the minimum possible total cost of all $N$ jobs.

Constraints

• $1 \leq N \leq 10^6$
• $1 \leq L_i \leq i \leq R_i \leq N$
• $1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N$
• $1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N$
• $(P_1,P_2,\ldots,P_N)$ is a permutation of $(1,2,\ldots,N)$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
P_1 P_2 \ldots P_N

Output

For each $k=0,1,2,\ldots,N$, output the answer in this order, separated by spaces.