Gold Bars

Interview

Time limit2sMemory limit512 MB

Summary

Given three bar weights with an even total, decide whether the bars already split evenly, or which single bar to cut in two so the pieces divide equally.

Level: Easy3 of 10
Topics: Math, Implementation, Brute force, Array
Solved: No attempts yet

Problem

The highway robbers John and Bob robbed a caravan and got three gold bars as their loot. Deciding to split the loot fairly, John and Bob weighed the bars and found that they weigh $x_1$ , $x_2$ , and $x_3$ pounds, respectively.

Now John and Bob want to divide the bars so that each of them gets the same amount of gold. They would rather not saw the bars, but there is no way around it. After discussing the situation, they decided that if they can, they will split the loot as it is, and if they cannot, they will saw one bar into two pieces. They cannot saw two or all three bars.

Help John and Bob choose which bar to saw into two pieces and into which pieces to saw it, so that afterward they can divide the loot equally.

Input

The first line of the input contains three integers: $x_1$ , $x_2$ , and $x_3$ ( $1 \le x_i \le 10^8$ , the sum of the bars' weights is even).

Output

If it is impossible to saw one bar in such a way that the gold can then be divided equally, output $-1$ .

If John and Bob can already divide the gold equally, output $0$ .

Otherwise, on the first line output $1$ if the first bar should be sawed, $2$ if the second bar should be sawed, or $3$ if the third bar should be sawed. On the second line output two positive integers: the weights of the pieces into which the bar should be sawed. The two pieces must sum to the original weight of the bar. Since the total weight of the gold is even, the bar always needs to be sawed into pieces of integer weight. If there are several possible solutions, output any of them.

Examples1

Example 1
Input
```
2 3 3
```
Expected output
```
2
2 1
```