← 返回题目列表

Codeforces · 412/C

C. 模式

中文机器翻译题面 查看原题

开发人员经常面临正则表达式模式。模式通常定义为由字符和元字符组成的字符串,用于设置搜索规则。这些模式最常用于检查特定字符串是否满足特定规则。

在此任务中,模式将是由小英文字母和问号(“?”)组成的字符串。模式中的问号是一个元字符,表示英语字母表中的任意小写字母。如果我们可以通过用适当的字符替换问号来将字符串转换为模式,我们将假设字符串与模式匹配。例如,字符串 aba 匹配模式:???, ??a, a?a, aba。

为 R1 公司工作的程序员喜欢用谜语互相猜谜(以及他们自己)。其中之一如下:给你n个相同长度的模式,你需要找到一个包含尽可能少的问号的模式,并与每个给定的模式相交。如果存在同时匹配第一个和第二个模式的字符串,则两个模式相交。你能解开这个谜语吗?

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 模式数。接下来的 n 行包含模式。

保证图案只能由小英文字母和符号“?”组成。所有模式都是非空的并且具有相同的长度。所有模式的总长度不超过105个字符。

输出

在一行中打印问题的答案 - 具有最少数量的符号“?”的模式,该模式与每个给定的符号相交。如果有多个答案,请打印其中任何一个。

示例

输入 #1

2
?ab
??b

输出 #1

xab

输入 #2

2
a
b

输出 #2

?

输入 #3

1
?a?b

输出 #3

cacb

注意

考虑第一个例子。图案 xab 与每个给定图案相交。图案 ???也与每个给定的模式相交,但它包含更多的问题符号,因此它不是最佳答案。显然,xab 是最佳答案,因为它不包含任何问号。还有很多其他的最优答案,例如:aab、bab、cab、dab等等。