Under construction

Still being built. Things may change

4SUM

Interview

Time limit2sMemory limit512 MB

Summary
Pick one number from each of four sets of up to 500 integers so the four numbers sum to zero.
Level

Medium4 of 10

Topics
Hash map
Solved
No attempts yet

Problem

You are given four sets of integers. Choose one integer from each set so that the four chosen numbers add up to 00. You can assume that exactly one such choice exists.

Input

The first line contains four integers aa, bb, cc, and dd, separated by spaces. They give the sizes of the four sets, and each one satisfies 1≤a,b,c,d≤5001 \le a, b, c, d \le 500.

The next a+b+c+da + b + c + d lines each contain one element of a set. Every element is an integer no smaller than −60000-60000 and no larger than 6000060000. The elements of the first set come first, then the elements of the second set, then the third set, then the fourth set.

Output

Print the four integers whose sum is 00 on one line, separated by spaces. Order them the way their sets appear in the input.

Examples1

  1. Example 1

    Input
    3 2 4 2
    5
    17
    -8
    -13
    19
    6
    -9
    10
    0
    -14
    7
    
    Expected output
    17 -13 10 -14