C - 1-SAT

得分：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。

6
a
!a
b
!c
d
!d

a

字符串 a 能够与 $S_1$ 匹配，同时在它的开头添加 ! 时也能够与 $S_2$ 匹配，所以它是一个不满足条件的字符串。 除此之外，字符串 d 也是一个不满足条件的字符串。

10
red
red
red
!orange
yellow
!blue
cyan
!green
brown
!gray

satisfiable