302162: CF412C. Pattern
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Pattern
题意翻译
给你$n$个长度相等的字符串,由小写字母和问号(问号视为任意一个小写字母)组成。你需要输出一个与之长度相等的字符串,使得当这个字符串的第$i$位为某个字母时,$n$个字符串的第$i$位均为这个字母。 如果某一位不符合规定,你需要输出?,(当然如果某一位符合规定也可以输出?)但是问号数目要尽量小。题目描述
Developers often face with regular expression patterns. A pattern is usually defined as a string consisting of characters and metacharacters that sets the rules for your search. These patterns are most often used to check whether a particular string meets the certain rules. In this task, a pattern will be a string consisting of small English letters and question marks ('?'). The question mark in the pattern is a metacharacter that denotes an arbitrary small letter of the English alphabet. We will assume that a string matches the pattern if we can transform the string into the pattern by replacing the question marks by the appropriate characters. For example, string aba matches patterns: ???, ??a, a?a, aba. Programmers that work for the R1 company love puzzling each other (and themselves) with riddles. One of them is as follows: you are given $ n $ patterns of the same length, you need to find a pattern that contains as few question marks as possible, and intersects with each of the given patterns. Two patterns intersect if there is a string that matches both the first and the second pattern. Can you solve this riddle?输入输出格式
输入格式
The first line contains a single integer $ n $ $ (1<=n<=10^{5}) $ — the number of patterns. Next $ n $ lines contain the patterns. It is guaranteed that the patterns can only consist of small English letters and symbols '?'. All patterns are non-empty and have the same length. The total length of all the patterns does not exceed $ 10^{5} $ characters.
输出格式
In a single line print the answer to the problem — the pattern with the minimal number of signs '?', which intersects with each of the given ones. If there are several answers, print any of them.
输入输出样例
输入样例 #1
2
?ab
??b
输出样例 #1
xab
输入样例 #2
2
a
b
输出样例 #2
?
输入样例 #3
1
?a?b
输出样例 #3
cacb