Twin Beacon Line Reconstruction

A harbor uses two parallel beacon lines, the Upper Line and the Lower Line, strung along n numbered positions. At every position, the beacon on each line is either lit (1) or unlit (0). A dispatcher recorded three facts about last night's run: the total number of beacons lit on the Upper Line, the total number lit on the Lower Line, and, for every single position, the combined number of lit beacons at that position summed across both lines (which can only be 0, 1, or 2). Your job is to reconstruct one beacon pattern for both lines that is consistent with all of these recorded facts, or to report that no such pattern could have produced them.

Input format

Line 1: three integers n upper lower — the number of positions, the required total lit count on the Upper Line, and the required total lit count on the Lower Line. Line 2: n integers colSum[1] colSum[2] ... colSum[n], the combined lit count at each position (each is 0, 1, or 2).

Output format

If no valid pair of lines can satisfy all three recorded facts, print a single line containing -1. Otherwise print exactly two lines, each with n space-separated integers (each 0 or 1): the Upper Line's pattern, then the Lower Line's pattern. Any pattern satisfying every constraint is accepted.

Constraints

• 1 <= n <= 100000
• 0 <= upper, lower <= n
• colSum[i] is 0, 1, or 2 for every i

3 2 1
1 1 1

1 1 0
0 0 1

2 0 0
1 2

-1