Minimizing Maximum Discomfort

JOI Corporation has invented a new type of tie. There are \(N+1\) ties numbered from 1 to \(N+1\), and the length of the \(i\)-th tie is \(A_i\). The company is hosting a party with \(N\) employees. Initially, the \(j\)-th employee is wearing a tie of length \(B_j\).

The party proceeds as follows:

1. The boss, JOI-kun, removes one tie from the collection.
2. Each of the \(N\) employees selects one tie among the remaining ties with the condition that no two employees choose the same tie.
3. Finally, every employee takes off the tie they initially wore and puts on the tie they selected.

If an employee originally wore a tie of length \(b\) and later puts on a tie of length \(a\), then the employee experiences a discomfort of \(\max\{a-b,0\}\). The overall discomfort of the party is defined as the maximum discomfort among all employees.

For each tie \(k\) (\(1 \le k \le N+1\)) that JOI-kun may remove, let \(C_k\) be the minimum possible overall discomfort that can be achieved by an optimal assignment of the remaining ties to the employees. Your task is to compute \(C_1, C_2, \dots, C_{N+1}\) corresponding to each possible tie removal.

Note: When computing the discomfort for a specific removal, the employees are allowed to choose their ties in any order (subject to the uniqueness condition) to minimize the maximum \(\max\{a-b,0\}\) value.

It can be shown that an optimal strategy is to sort the lengths of the remaining ties and the employees' original tie lengths, then pair them in order. More precisely, let \(T\) be the sorted list of tie lengths (after removing one tie) and \(E\) be the sorted list of the employees' original tie lengths. Then, the discomfort for an employee in position \(j\) (with \(0 \le j \le N-1\)) is \(\max\{T_{j} - E_{j}, 0\}\) and the overall discomfort is \(\max_{0 \le j \le N-1} \max\{T_{j} - E_{j}, 0\}\>.

inputFormat

The first line contains a single integer \(N\) (the number of employees).
The second line contains \(N+1\) integers \(A_1, A_2, \dots, A_{N+1}\), where \(A_i\) represents the length of the \(i\)-th tie.
The third line contains \(N\) integers \(B_1, B_2, \dots, B_N\), where \(B_j\) represents the initial tie length of the \(j\)-th employee.

All numbers are separated by a single space.

outputFormat

Output \(N+1\) integers \(C_1, C_2, \dots, C_{N+1}\) in one line, separated by spaces, where \(C_k\) is the minimum possible overall discomfort when the \(k\)-th tie (in the original input order) is removed by JOI-kun.

sample

2
5 2 4
3 3

1 2 2