Equal Total Scores

Interview

Time limit1sMemory limit128 MB

Summary
Find one card from each person to swap so their total scores match, choosing the pair with the smallest sum, or print -1.
Level

Easy3 of 10

Topics
Brute force, Implementation, Array, Math
Solved
No attempts yet

Problem

Taro and Hanako each hold several cards, and every card has a score printed on it. They want to make the total score of the cards in their hands equal by exchanging exactly one of Taro's cards for exactly one of Hanako's cards. Decide which card should be swapped for which.

They must exchange a pair of cards even when their total scores are already equal.

Input

The input consists of several datasets. Each dataset has the following format:

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

The first line contains two integers nn and mm separated by a space, where nn is the number of cards Taro has and mm is the number of cards Hanako has. The next n+mn+m lines give one score per line: the first nn scores (s1s_1 to sns_n) are Taro's cards, and the remaining mm scores (sn+1s_{n+1} to sn+ms_{n+m}) are Hanako's.

Both nn and mm are positive integers no greater than 100100, and each score is a non-negative integer no greater than 100100.

The end of the input is a line containing two zeros separated by a single space; do not process it.

Output

For each dataset, print one line with two integers separated by a single space: the score of the card Taro gives to Hanako, followed by the score of the card Hanako gives to Taro. If several exchanges make the totals equal, print the pair whose sum is the smallest.

If no exchange can make the totals equal, print a single line containing only −1-1. The output must not contain any extra characters.

Examples1

  1. Example 1

    Input
    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
    
    Expected output
    1 3
    3 5
    -1
    2 2
    -1