Challenge 24

Time limit1sMemory limit128 MB

Summary

From four distinct positive integers, enumerate every value reachable using each number once with +, -, *, and even-only division, then report the longest run of consecutive integers, choosing the largest start on ties.

Level: Medium6 of 10
Topics: Brute force, Recursion, Implementation, Math
Solved: No attempts yet

Problem

Challenge 24 is a calculation game popular with elementary-school students. At the start of the game, each player receives four cards, each showing a positive integer $i_1$ , $i_2$ , $i_3$ , $i_4$ . Using the four arithmetic operations (+, -, *, /) to combine the numbers appropriately, the first player to reach 24 wins. Each number must be used exactly once, and division may be used only when it comes out even (6/2 is allowed, but 6/4 is not). For example, given 7, 2, 5, 1, you can make 24 with (7-2)*5-1 or (7+1)*(5-2).

Now consider a game with the same rules but a slightly different goal. Given four numbers, first find every value that can be produced from them. Then find the longest run of consecutive integers among those values. For example, with 7, 2, 5, 1 the longest run is from -18 to 26.

You may not use + or - to turn a number negative; that is, every operator is used only as a binary operator.

Input

The input consists of several test cases. Each test case is a single line of four numbers. The four numbers are all positive integers, none exceeds 100, and they are all distinct. The input ends with a line of four zeros (0 0 0 0).

Output

For each test case, print the case number together with the longest run, in the format Case k: a to b, where $k$ is the case number starting from 1 and $a$ and $b$ are the first and last values of the longest run of consecutive integers. If there is more than one longest run, print the one whose starting value is largest.

Examples2

Example 1

Input

7 2 5 1
8 15 38 3
0 0 0 0

Expected output

Case 1: -18 to 26
Case 2: 150 to 153

Example 2
Input
```
1 2 3 4
0 0 0 0
```
Expected output
```
Case 1: -23 to 28
```