Dominoes#542

Dominoes

1 second

256 megabytes

A horizontal row of dominoes is on the table. When implementing your solution in C++, add the directive #define lll long long and use lll for 64-bit integers. When implementing your solution in Python, add the line lll = int at the beginning of the program and convert every value you read to a number with the call lll(...). Its left end shows $l$ , and its right end shows $r$ .

Andrii has two dominoes: $(a, b)$ and $(c, d)$ . Taras has one domino: $(e, f)$ . Each pair gives the numbers on the two halves of the corresponding domino.

A domino can be attached to an end of the row if the touching halves show equal numbers. A domino may be reversed before it is attached. Dominoes already in the row cannot be moved or reversed.

First, Andrii must attach both his dominoes: one on the left and the other on the right. He chooses which domino to attach on each side and its orientation. Each domino must be used exactly once.

Then Taras tries to attach his domino to either end of the row. He may also reverse it.

Find an arrangement of Andrii's dominoes that leaves Taras unable to move, or report that no such arrangement exists.

Example for $l = 1$ l = 1, $r = 2$ r = 2, $(a, b) = (1, 3)$ (a, b) = (1, 3), $(c, d) = (2, 4)$ (c, d) = (2, 4), and $(e, f) = (1, 2)$ (e, f) = (1, 2)

Input

The first line contains two integers $l$ and $r$ ( $0 \leq l, r \leq 6$ 0 \le l, r \le 6) — the numbers at the left and right ends of the existing row, respectively.

The second line contains two integers $a$ and $b$ ( $0 \leq a, b \leq 6$ 0 \le a, b \le 6) — the numbers on Andrii's first domino.

The third line contains two integers $c$ and $d$ ( $0 \leq c, d \leq 6$ 0 \le c, d \le 6) — the numbers on Andrii's second domino.

The fourth line contains two integers $e$ and $f$ ( $0 \leq e, f \leq 6$ 0 \le e, f \le 6) — the numbers on Taras's domino.

Different dominoes may have identical pairs of numbers. Andrii's two dominoes are separate pieces even if they show the same numbers; both pieces must be used.

Output

If no suitable arrangement exists, print $- 1$ .

Otherwise, on the first line, print two numbers $x$ and $y$ — the numbers on the domino Andrii attaches on the left. On the second line, print two numbers $z$ and $t$ — the numbers on the domino he attaches on the right. On both lines, write the numbers in left-to-right order. Thus, $y = l$ y=l, $z = r$ z=r, and the new ends of the row are $x$ and $t$ .

Use both of Andrii's dominoes, each exactly once, with reversal allowed. Afterwards, Taras must have no legal move. If several arrangements are possible, print any of them.

Examples

Example 1

Example 2

Example 3

Note

The first example is shown in the picture above. Andrii attaches $(1, 3)$ on the left in the order $3, 1$ , and $(2, 4)$ on the right in the order $2, 4$ . The new ends of the row are $3$ and $4$ . Taras has $(1, 2)$ , so he cannot make a move.

In the second example, $(1, 3)$ can only be attached on the left. Therefore, $(2, 1)$ must be attached on the right. The new ends are $3$ and $1$ . Taras can attach his domino $(1, 4)$ to the end showing $1$ , so no suitable arrangement exists.

Example for $l = 1$ l = 1, $r = 2$ r = 2, $(a, b) = (1, 3)$ (a, b) = (1, 3), $(c, d) = (2, 1)$ (c, d) = (2, 1), and $(e, f) = (1, 4)$ (e, f) = (1, 4)

In the third example, Andrii attaches $(0, 6)$ on the left in the order $6, 0$ , and $(0, 5)$ on the right in the order $0, 5$ . The new ends are $6$ and $5$ . Neither matches the numbers $0$ and $4$ on Taras's domino, so he cannot make a move.

Editorial