A Plus B

Borcsa에게는 각각 $N$개의 음이 아닌 정수를 포함하는 두 배열이 있다.

첫 번째 배열의 수는 $A[0], A[1], \ldots, A[N-1]$이고, 두 번째 배열의 수는 $B[0], B[1], \ldots, B[N-1]$이다. 두 배열의 수는 모두 오름차순으로 정렬되어 있다. 즉,

• $A[0] \le A[1] \le \cdots \le A[N-1]$이고,
• $B[0] \le B[1] \le \cdots \le B[N-1]$이다.

Borcsa는 산술 덧셈을 매우 좋아해서, $0$부터 $N-1$까지의 각 $i$와 $0$부터 $N-1$까지의 각 $j$에 대해 합 $A[i]+B[j]$를 계산했다.

Borcsa가 계산한 $N^2$개의 모든 합을 오름차순으로 정렬하여 배열 $C$에 저장하자. 여러분의 과제는 $C$의 처음 $N$개 값을 찾는 것이다.

구현 세부사항

다음 프로시저를 구현해야 한다.

int[] smallest_sums(int N, int[] A, int[] B)

• $N$: 각 배열의 원소 수.
• $A, B$: 오름차순으로 정렬된 음이 아닌 정수들을 포함하는 길이 $N$의 배열.
• 이 프로시저는 $A$의 원소 하나와 $B$의 원소 하나를 더해서 얻을 수 있는 합 중 가장 작은 $N$개를 포함하는 길이 $N$의 배열을 반환해야 한다. 배열에는 합들이 오름차순으로 들어 있어야 한다.
• 이 프로시저는 각 테스트 케이스마다 정확히 한 번 호출된다.

예제

예제 1

다음 호출을 살펴보자.

smallest_sums(2, [0, 2], [1, 4])

이 경우 $N=2$이다. Borcsa가 계산한 합은 $N^2=4$개이다.

• $0+1=1$
• $0+4=4$
• $2+1=3$
• $2+4=6$

배열 $C$에는 이 합들이 오름차순으로 정렬되어 들어 있으므로 $C=[1,3,4,6]$이다. $C$에서 가장 작은 $N=2$개의 원소는 $1$과 $3$이다. 따라서 프로시저는 배열 $[1,3]$을 반환해야 한다.

예제 2

다음 호출을 살펴보자.

smallest_sums(3, [0, 2, 2], [3, 5, 6])

$9$개의 쌍별 합은 오름차순으로 $3,5,5,5,6,7,7,8,8$이다. 프로시저는 가장 작은 $3$개의 합, 즉 배열 $[3,5,5]$를 반환해야 한다.

제약 조건

• $1 \le N \le 100\,000$
• $0 \le A[i] \le 10^9$ ($0 \le i < N$인 각 $i$에 대해)
• $0 \le B[j] \le 10^9$ ($0 \le j < N$인 각 $j$에 대해)
• $A$와 $B$는 오름차순으로 정렬되어 있다.

서브태스크

1. (10점) $N=1$
2. (20점) $N \le 100$
3. (30점) $N \le 2\,500$
4. (40점) 추가 제약 조건이 없다.

샘플 그레이더는 다음 형식으로 입력을 읽는다.

• 1번째 줄: $N$
• 2번째 줄: $A[0]\ A[1]\ \ldots\ A[N-1]$
• 3번째 줄: $B[0]\ B[1]\ \ldots\ B[N-1]$

smallest_sums가 반환한 배열의 원소를 어떤 음이 아닌 $n$에 대해 $c[0],c[1],\ldots,c[n-1]$이라고 하자.

샘플 그레이더의 출력 형식은 다음과 같다.

• 1번째 줄: $c[0]\ c[1]\ \ldots\ c[n-1]$