Problem J. Square-convexity: volume

Author:A. Shchurov   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

We call a three dimensional figure square-convex if every line segment which is parallel to the coordinate axes with both ends belonging to the figure, lies completely in this figure.

You are given an image of a square-convex figure in three projections. You are to calculate the volume of the figure. If the projections do not uniquely determine the shape of the figure, output the maximum possible volume for these projections.

Input format

The input contains three projections of the figure, depicted by ASCII graphics: top view, front and right.

Each projection consists of characters "." (ASCII 46) — designation of voids in the description of a projection, and "#" (ASCII 35) — faces of a square-convex body. Each symbol represents a block with the edge length 1. It is guaranteed that in the description of the projection there are neither rows nor columns consisting entirely of voids. A description of each projection ends with a "-" (ASCII 45) in a separate line.

Output format

The output should contain a single integer: figure volume.

Constraints

The width and height of each projection does not exceed 100 characters; the figure volume is not equal to zero.

Sample tests

No. Standard input Standard output
1
#
#
#
-
#
#
-
.#.
###
-
4
2
##
##
-
##
##
-
##
##
-
8

0.116s 0.013s 13