Problem H
PrintQuoter3D

With the commoditization of 3D printing, Mat Hedicine decided to try his hand at starting his own 3D printing business. He knows there is a lot of competition in this space and he needs a way to distinguish himself. Knowing that few people are good at CAD, he thought, what if customers could simply send a few pictures of an object that they would like printed?

The real problem Mat had was that he didn’t have a good way to estimate the cost of a print job, and his misestimations were starting to cost him a lot money (not to mention customers). Can you help Mat out by writing a program to estimate a 3D print job’s cost from a set of images?

When a customer wants an object printed, they send Mat three black-and-white images: a front view, right view, and top view, as shown below. As we all know, the cost of a job is proportional to the amount of filament required. Mat wants to avoid underestimating the cost, so he would like you to calculate the highest possible material volume the customer’s object can have, given its three orthogonal views. (The actual volume may be less, e.g. if the object were hollow, but there’s no way for Mat to tell from the pictures alone.) Sometimes the customer makes a mistake and sends Mat bad images, so your program should also be able to tell Mat if the three views are inconsistent in that they do not depict a 3D object. Note that images may depict objects with several pieces (i.e. disconnected components), but that’s not a problem because Mat would be happy to print all of the pieces.

Input

The first line of input contains three space-separated integers, $W$, $H$, and $D$, indicating the pixel width, height, and depth of the images, respectively ($1 \le W, H, D \le 100$). On the following $2H+D$ lines are the three customer images, the front, right, and top views of the object, in that order, encoded with ‘.’ representing an empty pixel and ‘#’ representing a filled pixel, as follows:

• The front view image contains $H$ lines of data, each with $W$ characters. The first line corresponds to the top of the object and the first character to its left.

• The right view image contains $H$ lines of data, each with $D$ characters. The first line corresponds to the top of the object and the first character to its front.

• The top view image contains $D$ lines of data, each with $W$ characters. The first line corresponds to the back of the object and the first character to its left.

Output

Output the maximum volume the customer’s object may have (in units of cubic pixel size), as an integer on a single line. If the three provided views are inconsistent, write the word “invalid” on a single line instead.

4 2 3
####
.#..
.##
###
.###
##..
.#..

8

2 2 2
#.
.#
#.
.#
#.
.#

invalid