Description

Given a positive integer $n$ and two integer sequences $a = (a_1, \ldots, a_n)$ and $b = (b_1, \ldots, b_n)$ of length $n$, where $b_i$ is guaranteed to be non-negative, but $a_i$ may be negative.

Define the notation $[n]$ to represent the set $\{ i \mid 1 \le i \le n \}$.

For each $k \in [n]$, you need to select a subset $S$ of $[n]$ with size $k$. Under this constraint, find the maximum value of

$$\Bigl( \max_{i \in S} a_i \Bigr) - \Bigl( \operatorname*{mex}_{i \in S} b_i \Bigr).$$

Note: $\displaystyle \operatorname*{mex}_{i \in S} b_i$ denotes the minimum non-negative integer that does not appear in $\{ b_i \mid i \in S \}$.

Input Format

The input contains multiple test cases.

The first line contains an integer $T$, indicating the number of test cases. For each test case:

• The first line contains a positive integer $n$.
• The second line contains $n$ integers $a_1, \ldots, a_n$.
• The third line contains $n$ non-negative integers $b_1, \ldots, b_n$.

Output Format

For each test case, output $n$ lines. The $i$-th line should contain one integer, which is the answer when $k = i$.

1
3
1 2 3
0 0 1

3
1
1

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

9
9
9
9
9
9
9
9
8
9
9
9
9
9
9
4
4
4
4
2

2
6
0 0 0 0 0 0
6 5 2 7 1 6
6
6 5 0 7 9 2
0 0 0 0 0 0

0
0
0
0
0
0
8
8
8
8
8
8

Hint

【Sample Explanation #1】

When $k=1$, let $S = \{3\}$, then the answer is $3 - 0 = 3$.

When $k=2$, let $S = \{2, 3\}$, then the answer is $3 - 2 = 1$.

When $k=3$, let $S = \{1, 2, 3\}$, then the answer is $3 - 2 = 1$.

【Data Range】

This problem uses bundled testing.

Subtask ID	$\sum n \le$	Special Properties	Score
$1$	$10$	C	$11$
$2$	$200$		$17$
$3$	$2000$		$23$
$4$	$10^6$	AC	$19$
$5$		BC	$7$
$6$	$10^5$	C	$22$
$7$	$10^6$	None	$1$

• Special Property A: $a_i = 0$.
• Special Property B: $b_i = 0$.
• Special Property C: $T = 1$.

For all test cases, $1 \le T, n, \sum n \le 10^6$, $-10^{9} \le a_i \le 10^{9}$, $0 \le b_i \le 10^{9}$.

Translated by DeepSeek V3.1