在莱茵博物馆中,有两种展品需要特别的保护:珍稀展品和普通展品。为了增强安全措施,博物馆决定部署一种新的安全监测系统。这套系统通过分析每个展品上特殊的电子标签数据,来判定其是否属于珍稀展品。
每个展品的电子标签包含一个长度为 M 的序列,由字符 A, C, G, T 构成,代表不同类型的安全编码。现有 N 个珍稀展品和 N 个普通展品的编码数据被记录下来。
安全系统的工作人员发现,通过分析特定的几个编码位置,可以准确区分展品是否珍稀。具体来说,如果某三个不同位置的编码组合只在珍稀展品中出现,而从未在普通展品中出现,那么这组位置就能用来判定展品的珍贵程度。
更具体的说。假设所有安全编码的位置是 1 \sim M,如果有三个不同的位置 1 \le i \lt j \lt k \le M。取出所有珍稀展品编码中,这三个位置的字符,组成 N 个三位的字符串,我们称之为集合 S_1。再取出所有普通展品编码中,这三个位置的字符,组成另外 N 个三位的字符串,我们称之为集合 S_2。如果 S_1 集合中的字符串没有任何一个在 S_2 集合中出现,那么就可以认为这组位置 i,j,k 可以用来判定展品的珍稀程度。
你的任务是帮助博物馆找出所有能够区分珍稀和普通展品的三个编码位置的组合数量。
第 1 行读入两个整数 N 和 M。N 是珍稀展品和普通展品的数量,M 是电子标签的长度。
接下来 N 行,每行一个长度为 M 的字符串,描述一个珍稀展品的电子标签。
再接下来 N 行,每行一个长度为 M 的字符串,描述一个普通展品的电子标签。
输出一个整数,表示能够准确区分展品类型的三个位置的组合数量。
2 4 ACGT AAGC AGGT AAGT
2
3 8 AATTCCAT CATTGCAA AGTCCCAA ACGCCCAG ACTCGCAT ACTTCCAT
21
如果 i,j,k 取:1,2,3。
那么,珍稀产品的编码对应位置取出的字符串为:ACG,AAG,普通产品的编码对应位置取出的字符串为:AGG,AAG,其中 AAG 在两种编码中都有,因此这三个位置不能作为区分展品类型的位置组合。
分析可知 i,j,k 分别取:1,2,4 和 2,3,4 时,都可以作为区分展品类型的位置组合。
对于 30\% 的数据,满足 1 \le N \le 10,1 \le M \le 10。
对于 100\% 的数据,满足 1 \le N \le 100,1 \le M \le 100。