총점 같게 만들기

면접 대비

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

요약
두 사람이 카드를 한 장씩 교환해 총점을 같게 만드는 쌍을 찾고, 합이 가장 작은 쌍을 출력하거나 없으면 -1을 출력한다.
난이도

쉬움10점 중 3점

유형
완전 탐색, 구현, 배열, 수학
정답자
아직 제출이 없습니다

문제

타로와 하나코는 각각 여러 장의 카드를 들고 있으며, 카드마다 점수가 하나씩 적혀 있습니다. 두 사람은 타로의 카드 한 장과 하나코의 카드 한 장을 서로 맞바꿔서 각자 손에 든 카드 점수의 합을 같게 만들려고 합니다. 어떤 카드를 어떤 카드와 바꿔야 하는지 구하세요.

두 사람의 총점이 이미 같더라도 반드시 카드 한 쌍을 교환해야 합니다.

입력

입력은 여러 개의 데이터 집합으로 이루어집니다. 각 데이터 집합의 형식은 다음과 같습니다.

n m
s1
s2
...
sn
sn+1
sn+2
...
sn+m

첫 번째 줄에는 공백으로 구분된 두 정수 nn과 mm이 주어지며, nn은 타로가 가진 카드 수, mm은 하나코가 가진 카드 수입니다. 이어지는 n+mn+m개의 줄에는 한 줄에 하나씩 점수가 주어집니다. 처음 nn개의 점수(s1s_1부터 sns_n까지)는 타로의 카드이고, 나머지 mm개의 점수(sn+1s_{n+1}부터 sn+ms_{n+m}까지)는 하나코의 카드입니다.

nn과 mm은 모두 100100 이하의 양의 정수이고, 각 점수는 100100 이하의 음이 아닌 정수입니다.

입력의 끝은 공백으로 구분된 두 개의 00이 적힌 줄로 표시되며, 이 줄은 처리하지 않습니다.

출력

각 데이터 집합에 대해, 공백으로 구분된 두 정수를 한 줄에 출력합니다. 첫 번째 수는 타로가 하나코에게 주는 카드의 점수, 두 번째 수는 하나코가 타로에게 주는 카드의 점수입니다. 총점을 같게 만드는 교환 방법이 여러 가지라면, 두 점수의 합이 가장 작은 쌍을 출력합니다.

어떤 교환으로도 총점을 같게 만들 수 없으면, −1-1 하나만 적힌 줄을 출력합니다. 출력에는 형식에 맞지 않는 불필요한 문자가 없어야 합니다.

예제1

  1. 예제 1

    입력
    2 2
    1
    5
    3
    7
    6 5
    3
    9
    5
    2
    3
    3
    12
    2
    7
    3
    5
    4 5
    10
    0
    3
    8
    1
    9
    6
    0
    6
    7 4
    1
    1
    2
    1
    2
    1
    4
    2
    3
    4
    3
    2 3
    1
    1
    2
    2
    2
    0 0
    
    예상 출력
    1 3
    3 5
    -1
    2 2
    -1