The Toxic iShongololo

"iShongololo" is the Zulu name for a millipede. They are long, shiny, black arthropods with many legs.

The iShongololo eats through an edible "fruit" which for the sake of this problem can be considered a rectangular solid with integer dimensions of L (length), W (width) and H (height).

Task:

You are required to write a program that maximizes the number of blocks eaten by the iShongololo without violating the constraints given. The program must output the actions that the iShongololo makes as it eats its way through the fruit.

The iShongololo starts outside the fruit. The first block the iShongololo must eat is 1, 1, 1 and it must then move to this block. It stops when no more blocks can be legally eaten and it can no longer move.

Constraints:

  1. The iShongololo occupies exactly one empty block.
  2. The iShongololo can only eat one complete block at a time.
  3. The iShongololo cannot move to a position where it has previously moved to (that is, move backwards or cross its path).
  4. The iShongololo cannot move to a solid (uneaten) block, or outside the fruit.
  5. The iShongololo may only move to or eat blocks with whom it shares a face. It may only eat blocks which have no other faces exposed to empty eaten blocks.

Input:

As input your program will receive three numbers (integers) which are the length (L), width (W) and height (H) of the solid.

The three integers L, W, H, are each on a separate line. The three integers will be between 1 and 32 (inclusive).

Sample input:

TOXIC.DAT

Explanation:

2
3
2
Length of solid is 2.
Width of solid is 3.
Height of solid is 2.

Output:

The output consists of lines that begin with "E" (eat) or "M" (move) followed by 3 integers that represent the block eaten or moved to on the axes corresponding to L, W, H.

For example the following is a valid solution for the input example.

Sample output (this may not be optimal):

TOXIC.OUT

Explanation:

E 1 1 1
M 1 1 1
E 2 1 1
E 1 1 2
E 1 2 1
M 1 2 1
E 1 3 1
M 1 3 1
E 2 3 1
E 1 3 2
M 1 3 2
Eat the block 1 1 1
Move to the block 1 1 1
Eat the block 2 1 1
Eat the block 1 1 2
Eat the block 1 2 1
Move to the block 1 2 1
Eat the block 1 3 1
Move to the block 1 3 1
Eat the block 2 3 1
Eat the block 1 3 2
Move to the block 1 3 2

Scoring: