뭐야 내 수열 돌려줘요

시간 제한1초메모리 제한1024 MB

요약
길이 N인 수열의 prefix sum N개와 suffix sum N개를 순서 없이 섞은 2N개의 값을 받아, 원래 수열 A를 아무거나 하나 복원한다.
난이도

보통10점 중 7점

유형
수학, 그리디, 정렬, 구현
정답자
아직 제출이 없습니다

문제

쿠는 길이가 NN인 수열 A_1,A_2,⋯ ,A_NA\_1, A\_2, \cdots, A\_N을 가지고 있다. 쿠는 이 수열을 너무 아끼는 나머지, 수열 AA의 Prefix sum인 PP와 Suffix sum인 SS도 만들어 혹시 모를 사고에 대비했다.

어느 날, 건덕이가 쿠의 수열 AA를 훔쳐 갔고, 심지어 PP의 원소와 SS의 원소를 모두 한 데 섞어버리고 말았다!

쿠는 수열 AA의 NN개의 원소를 하나도 기억하지 못했기 때문에, 남아있는 수열 PP와 SS를 순서 없이 나열한 2N2N개의 원소를 통해 가능한 수열을 복원해 보려고 한다. 불쌍한 쿠를 위해 가능한 수열을 아무거나 하나 복원해 보자!

입력

첫째 줄에 수열 AA의 길이를 의미하는 정수 NN이 주어진다. (1≤N≤100,000)(1 \le N \le 100\\, 000)

둘째 줄에 수열 PP와 SS를 순서 없이 나열한 2N2N개의 원소를 의미하는 정수가 순서 없이 공백으로 구분되어 주어진다. (−109≤P_i,,S_i≤109)(-10^9 \le P\_i,\\, S\_i \le 10^9)

모든 P_iP\_i와 S_iS\_i는 수열 AA에서 올바르게 생성되었음이 보장된다.

출력

가능한 수열 AA의 원소를 순서대로 공백으로 구분하여 출력한다. 수열 AA의 모든 원소는 −109≤A_i≤109-10^9 \le A\_i \le 10^9를 만족하는 정수여야 한다. 조건을 만족하는 수열이 여러 가지라면 아무거나 하나 출력한다.

힌트

길이가 NN인 수열 AA의 Prefix sum은 다음과 같이 정의합니다. 1≤i≤N1 \le i \le N인 모든 ii에 대하여, P_i=A_1+⋯+A_iP\_i = A\_1 + \cdots + A\_i.

길이가 NN인 수열 AA의 Suffix sum은 다음과 같이 정의합니다. 1≤i≤N1 \le i \le N인 모든 ii에 대하여, S_i=A_i+⋯+A_NS\_i = A\_i + \cdots + A\_N.

예제1

  1. 예제 1

    입력
    6
    12 8 7 14 24 11 13 16 24 12 17 10
    
    예상 출력
    7 4 1 -4 6 10