题目描述

在一个与合成燃料开发相关的分子工程问题抽象中，给定四条长度相等的分子链，需要组成一个超分子。在简化的二维模型中，超分子由这四条分子链以交错矩形排列方式构成，其交错特征表现为链对之间共享共同分子。

举例说明，假设有以下四条长度为$12$的分子链：

O I M D I H E I A F N L
C H J D B J M H P J K D
L C B J O J G I E K B O
K A I N L H L O L B E J

它们可以排列成以下两种交错结构：

第一种结构（面积$30$）：

        O           L
        I           C
        M           B
C H J D B J M H P J K D
        I           O
        H           J
        E           G
        I           I
        A           E
        F           K
K A I N L H L O L B E J
        L           O

第二种结构（面积$4$）：

            O     C
            I     H
            M     J
            D     D
L C B J O J G I E K B O
            H     J
            E     M
        K A I N L H L O L B E J
            A     P
            F     J
            N     K
            L     D

问题约束条件

1. 四条链可以放置在超分子的任意四个水平或垂直槽位中
2. 水平放置的链必须保持原始从左到右的方向，不能翻转
3. 垂直放置的链必须保持原始从上到下的方向，不能翻转
4. 超分子中心封闭矩形的面积必须尽可能大，且面积不能为$0$
5. 每条链超出中心交错矩形的首尾部分长度至少为$1$个元素

输入格式

每个数据集包含四条长度为$12$的分子链，每条链由连续大写字母表示（仅使用字母$A$到$P$）。第一个链的首字母为"$Q$"时表示输入结束。

输出格式

对每个数据集，输出一个整数表示合法排列能形成的最大封闭矩形面积。若无合法排列则输出$0$。

输入样例

CDBADCBBEFEF
DACCBADAFEAB
EFBDCAADBDCD
ABCDABCDABCD
DACCBADAFEAB
EFBDCAADBDCD
ABCDABCDABCD
CDBADCBBEFEF
ABABABABABAB
CDCDCDCDCDCD
EEEEEEEEEEEE
FFFFFFFFFFFF
ABAAAAAAAABA
CBCCCCCCCCBC
DBDDDDDDDDBD
EBEEEEEEEEBE
ABBBBBBBBBBA
ACCCCCCCCCCA
ADDDDDDDDDDA
AEEEEEEEEEEA
BBBABBBABBBB
CCACCCACCCCC
DDDDADDADDDD
EEAEEAEEEEEE
Q

输出样例

48
48
0
64
0
6

题目来源

$1995$年北美中东部地区竞赛