分数: 300 点
问题陈述
给出的是 N 字符串 S_1, S_2, \dots, S_N。
其中每一个都是由小写英文字母组成的非空字符串,其中包含零个或一个 ! 添加在开头。
我们说一个字符串 T 当它匹配其中之一时不满意 S_1, S_2, \dots, S_N 无论我们是否添加 ! 开头 T.
判断是否存在不满足的字符串。如果是,请提供一个这样的字符串。
约束
- 1 \le N \le 2 \times 10^5
- 1 \le |S_i| \le 10
- S_i 是由小写英文字母组成的非空字符串,其中包含零个或一个
!添加在开头。
输入
输入由标准输入按以下格式给出:
N S_1 \vdots S_N
输出
如果存在不满足的字符串,则打印一个这样的字符串。
如果没有不满足的字符串,则打印 satisfiable.
示例输入 1
6 a !a b !c d !d
示例输出 1
a
a 匹配 S_1 照原样,并且它匹配 S_2 当我们添加 !,所以不满意。
除此之外, d 也将被接受。
示例输入 2
10 red red red !orange yellow !blue cyan !green brown !gray
示例输出 2
satisfiable