Problem Description

Do you know the company Just Odd Inventions? Their business is to create "just odd inventions." Here, we will refer to them as JOI Inc.

JOI Inc has developed a new product, "Just Long Neckties." There are $N + 1$ types of neckties, each labeled from $1$ to $N + 1$. The length of the $i$-th ($1 \leq i \leq N + 1$) type of necktie is $A_i$.

JOI Inc decided to gather their employees for a trial wearing session. $N$ employees will participate, and the $j$-th ($1 \leq j \leq N$) employee initially wears a necktie of length $B_j$.

The trial wearing session is planned to proceed as follows:

1. First, choose one type of necktie that will not be used in the session.
2. Then, each employee selects one type of necktie to try on from the remaining types. Note that no two employees can choose the same type of necktie.
3. Finally, each employee removes their current necktie and tries on the selected necktie.

An employee who was wearing a necktie of length $b$ and tries on a necktie of length $a$ will experience a strangeness of size $\max\{a - b, 0\}$. (Here, $\max\{a - b, 0\}$ represents the larger of $a - b$ and $0$.) The maximum strangeness felt by any employee during the session is defined as the strangeness of the session.

When the $k$-th type of necktie is not used in the session, let $C_k$ be the minimum possible strangeness of the session.

Given the lengths of each type of necktie and the initial lengths of neckties worn by each employee, create a program to compute the values of $C_1, C_2, \ldots, C_{N + 1}$.

Input Format

The input is provided from the standard input in the following format. All values are integers.

$N$ $A_1$ $\cdots$ $A_{N + 1}$ $B_1$ $\cdots$ $B_N$

Output Format

Output the values of $C_1, C_2, \ldots, C_{N + 1}$ in one line, separated by spaces.

Sample Input and Output

Sample Input #1

3
4 3 7 6
2 6 4

Sample Output #1

2 2 1 1

Sample Input #2

5
4 7 9 10 11 12
3 5 7 9 11

Sample Output #2

4 4 3 2 2 2

Notes/Hints

Constraints

• $1 \leq N \leq 200,000$.
• $1 \leq A_i \leq 1,000,000,000$ ($1 \leq i \leq N + 1$).
• $1 \leq B_j \leq 1,000,000,000$ ($1 \leq j \leq N$).

Subtasks

1. ($1$ point) $N \leq 10$.
2. ($8$ points) $N \leq 2,000$.
3. ($91$ points) No additional constraints.

Sample Explanation 1

For example, the session could proceed as follows:
- Decide not to use the 4th type of necktie.
- Employee 1 chooses the 1st type, employee 2 chooses the 2nd type, and employee 3 chooses the 3rd type of necktie.
- Each employee tries on their selected necktie.

In this case, the strangeness felt by each employee would be $2, 0, 3$ respectively, so the strangeness of the session is $3$.

By changing the choices of the employees, the strangeness of the session can be reduced to $1$. For example:
- Decide not to use the 4th type of necktie.
- Employee 1 chooses the 2nd type, employee 2 chooses the 3rd type, and employee 3 chooses the 1st type of necktie.
- Each employee tries on their selected necktie.

In this case, the strangeness felt by each employee would be $1, 1, 0$ respectively, so the strangeness of the session is $1$.

This is the minimum strangeness for not using the 4th type of necktie, so $C_4 = 1$.

见题面 Input 部分

见题面 Output 部分