Medium Sum Set Problem
/

## Fast Fourier transform, Linear Algebra, Mathematics

Problem
Editorial
Analytics

In this problem, we define "set" is a collection of distinct numbers. For two sets $A$ and $B$, we define their sum set is a set $S(A, B) = \{a + b | a\in A, b \in B\}$. In other word, set $S(A, B)$ contains all elements which can be represented as sum of an element in $A$ and an element in $B$. Given two sets $A, C$, your task is to find set $B$ of positive integers with maximum size such that $S(A, B) = C$. It is guaranteed that there is unique such set.

Input Format

The first line contains $N$ denoting the number of elements in set $A$, the following line contains $N$ space-separated integers $a_i$ denoting the elements of set $A$.

The third line contains $M$ denoting the number of elements in set $C$, the following line contains $M$ space-separated integers $c_i$ denoting the elements of set $C$.

Output Format

Print all elements of $B$ in increasing order in a single line, separated by space.

Constraints

• $1 \le N, M \le 5\times10^5$
• $1 \le a_i, c_i \le 5\times10^5$
SAMPLE INPUT
2
1 2
3
3 4 5


SAMPLE OUTPUT
2 3

Explanation

If $e$ is an element of set $B$, then $e + 2$ is an element of set $C$, so we must have $e \le 3$. Clearly, $e$ cannot be $1$ because $1 + 1 = 2$ is not an element of set $C$. Therefore, $B = \{2, 3\}$.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...