Crazy Timer

Igor is well-known for creating weird but ingenious inventions. His latest invention is a programmable timer. This contains between 2 and 5 wheels, depending on the model. The wheels can be set into rotation and are each designed to complete a full rotation before stopping. The wheels each take an integer number of seconds to complete a revolution and all wheels in the timer have different revolution times. The 2-, 3-, 4- and 5-wheel models are designed to measure short, medium, long and very long time intervals respectively. The design ensures that all possible programmable time intervals will be an integral number of seconds.

The front of the timer has a button (to start running the program) and a peg board. There is a set of pegs, each labelled with a program instruction. If we take the 4-wheel model as an example, there are 10 different programming instructions. These are shown below.

W1 Start
W1 Double
W2 Start
W2 Double
W3 Start
W3 Double
W4 Start
W4 Double
START Timer
STOP Timer

The four wheels are labelled W1 to W4. There are two program instructions for each wheel. W1 Start causes wheel 1 to be set into rotation. W1 Double doubles the rotation speed of wheel 1. If the wheel is currently stationary it will rotate at twice its normal speed when (and if) it is subsequently set into motion. If the wheel is currently part way through a rotation, it will complete the rotation at twice the normal speed. START Timer results in an audible signal to indicate the start of the timing function and a red light comes on to show that the timer is currently measuring a time interval. There are also ports in the timer to which external devices can be connected. The START Timer command will send power to these devices. The Stop Timer command issues an audible signal to indicate the end of the timed interval, the red light goes out and power is disconnected from any external devices.

The program instructions are carried out when specific events take place. The 4-wheel model has 5 events. The first of these is BEGIN. This event takes place when the button is pressed to start the program execution. There is one event associated with each wheel. These are labelled END W1 to END W4. The event END W1 occurs at the instant when wheel 1 completes a full revolution. The peg board on the timer has 6 rows, each of which can hold 10 pegs. The first row is simply a storage position for the 10 pegs. There is one peg for each program instruction and there are no duplicates. The remaining 5 rows are labelled with the 5 events. The following table shows an example of the peg layout for a typical program. The wheel rotation times (in seconds) for this example are: 144, 1904, 7056 and 10112.

BEGIN   W3 Start    W4 Start
END W1  STOP Timer
END W2  W1 Start
END W3  W4 Double   START Timer
END W4  W2 Double   W2 Start

The illustration does not show two of the possible program commands. These are not required in this program so will remain in the storage area, which is not shown. The illustration shows the layout on the front of the timer after the program has been pegged in. Note that it is not a chronological sequence. The program will make more sense if we determine the chronological sequence of events which takes place when the program is run. The following table does this. The first column shows the event, the second column shows the time in seconds (after the start) when this event takes place and the third column shows the program instructions which are executed at this time.

BEGIN      0        W3 Start    W4 Start
END W3  7056        W4 Double   START Timer
END W4  8584        W2 Double   W2 Start
END W2  9536        W1 Start
END W1  9680        STOP Timer

It is now easy to interpret the sequence of events. When the program starts (at time 0) wheels 3 and 4 are set into motion. At time 7056 wheel 3 completes a revolution. At this instant wheel 4 has its rotation speed doubled and the measured time interval is started. Wheel 4 completes its rotation at time 8584. At this instant wheel 2 is set into motion at twice the normal speed. Wheel 2 completes its rotation at time 9536. Wheel 1 is then set into rotation and completes a revolution at time 9680. At this instant the measured time interval is stopped. The measured time was started at 7056 seconds and stopped at 9680 seconds. So the length of the measured time interval is 2624 seconds.

Note that there is only one peg for each different program instruction, so each of these can be used at most once. If pegs are added or removed during program operation the program is immediately terminated and the device is reset. If at any time during program execution there is a period of several seconds when no wheel is in motion, the device also resets. If two or more events occur at exactly the same time then all corresponding program instructions for these events are carried out simultaneously. If the STOP Timer command is encountered before or at the same time as the START Timer command, both instructions will be ignored and there will be no measured time interval.

The previous example made use of all 4 wheels. This is not necessary. The following simple example uses this timer to provide a measured time interval of 1904 seconds (the rotation time of wheel 2).

BEGIN   W2 Start    START Timer
END W1  
END W2  STOP Timer
END W3  
END W4  

In this problem you will be given the wheel rotation times for each of the 2-, 3-, 4- and 5-wheel models. In each case you are asked to find all of the distinct measured times which can be created by the device. In order to ensure that you have found all of them and that you have disregarded any duplicates, you are asked to calculate the sum of all of the possible measured times.

For example, if we take a 2-wheel model with rotation times of 4 and 12 seconds, it is possible to create 10 distinct measured time intervals. You should be able to verify that these are: 2, 4, 5, 6, 7, 8, 10, 12, 14, 16. The sum of these times is 84.

Note that the 5-wheel model clearly needs two extra instruction pegs for the 5th wheel as well as additional spaces and one more row in the peg board.

Input/Output description: The input data will consist of 4 separate lines, one for each of the 2-, 3-, 4- and 5-wheel models, in that order. Each line will contain the revolution times of the wheels. These will be given in ascending order of size and separated by single spaces. In each case you need to find all of the distinct measured time intervals which can be created. Your answer is the sum of these. Combine all four answers into a single string, separated by spaces.

Example:

input:
4 12
88 216 344
144 1904 7056 10112
37088 203680 219392 255584 287232

answer:
84 19863 7216526 8165273037