/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の文字列 S_1, S_2, \dots, S_N が与えられます。
各文字列は、英小文字からなる空でない文字列の先頭に ! を 0 文字か 1 文字付加したものです。
文字列 T は、T の先頭に ! を 0 文字付加しても 1 文字付加しても S_1, S_2, \dots, S_N のいずれかに一致するとき、不満な文字列であるといいます。
不満な文字列があるかどうか判定し、あれば 1 つ示してください。
制約
- 1 \le N \le 2 \times 10^5
- 1 \le |S_i| \le 10
- S_i は英小文字からなる空でない文字列の先頭に
!を 0 文字か 1 文字付加したものである。
入力
入力は以下の形式で標準入力から与えられる。
N S_1 \vdots S_N
出力
不満な文字列が存在する場合、不満な文字列を 1 つ出力せよ。
不満な文字列が存在しない場合、satisfiable と出力せよ。
入力例 1
6 a !a b !c d !d
出力例 1
a
文字列 a は、先頭に ! を 0 文字付加する場合は S_1 と、1 文字付加する場合は S_2 と一致するため不満な文字列です。
a の他に、d を出力しても正解になります。
入力例 2
10 red red red !orange yellow !blue cyan !green brown !gray
出力例 2
satisfiable
Score : 300 points
Problem Statement
Given are N strings S_1, S_2, \dots, S_N.
Each of these is a non-empty string consisting of lowercase English letters, with zero or one ! added at the beginning.
We say a string T to be unsatisfied when it matches one of S_1, S_2, \dots, S_N regardless of whether we add an ! at the beginning of T.
Determine whether there exists an unsatisfied string. If so, present one such string.
Constraints
- 1 \le N \le 2 \times 10^5
- 1 \le |S_i| \le 10
- S_i is a non-empty string consisting of lowercase English letters, with zero or one
!added at the beginning.
Input
Input is given from Standard Input in the following format:
N S_1 \vdots S_N
Output
If there exists an unsatisfied string, print one such string.
If there is no unsatisfied string, print satisfiable.
Sample Input 1
6 a !a b !c d !d
Sample Output 1
a
a matches S_1 as is, and it matches S_2 when we add an !, so it is unsatisfied.
Besides that, d will also be accepted.
Sample Input 2
10 red red red !orange yellow !blue cyan !green brown !gray
Sample Output 2
satisfiable