**Link**: contest

**Author**: viv001@

**Tester**: gerald@

Denote the two cubes to be A[][][] and B[][][].

For every fixed (x,y), let **MaxLineLenXY[x][y][z]** be the maximum length of a line with x and y coordinates fixed at (x,y) and ending at z such that the letters on both the lines in the cubes are identical. This can be easily computed as:

**MaxLineLenXY[x][y][z]=(A[x][y][z]==B[x][y][z] ? 1+MaxLineLenXY[x][y][z-1] : 0) … (1)**

Similarly, let MaxLineLenYZ[x][y][z] and MaxLineLenXZ[x][y][z] be the corresponding lines with fixed (y,z) and (x,z) coordinates.

For every fixed x, let **MaxSquareLenX[x][y][z]** be the maximum length of a square parallel to the x plane (with x-coordinate=x) ending at (y,z) that is common to both A and B. This can be computed as:

**MaxSquareLenX[x][y][z]=(A[x][y][z]==B[x][y][z] ? 1+min(MaxSquareLenX[x][y-1][z-1], MaxLineLenXY[x][y][z-1], MaxLineLenXZ[x][y-1][z]) : 0) … (2)**

Similarly, we may compute MaxSquareLenY[x][y][z] and MaxSquareLenZ[x][y][z]

Finally, let MaxCubeLen[x][y][z] be the maximum side of a cube that ends at (x,y,z). This can be computed as:

**MaxCubeLen[x][y][z]=(A[x][y][z]==B[x][y][z] ? 1 + min(max_cube_len[x-1][y-1][z-1], MaxSquareLenX[x][y-1][z-1], MaxSquareLenY[x-1][y][z-1], MaxSquareLenZ[x-1][y-1][z], MaxLineLenXY[x][y][z-1], MaxLineLenXZ[x][y-1][z], MaxLineLenYZ[x-1][y][z]) : 0). … (3)**

Then you simply compute the maximum value of MaxCubeLen[x][y][z] and count the number of triplets (x,y,z) that attain this maximum.