1-SAT

题目描述

给定 $N$ 个字符串 $S_1, S_2, \dots, S_N$。 每个字符串都是在由小写英文字母组成的非空字符串开头，附加 $0$ 个或 $1$ 个 ! 得到的。

字符串 $T$ 被称为「不满足的字符串」（unsatisfiable），当且仅当：在 $T$ 的开头附加 $0$ 个 ! 时、以及附加 $1$ 个 ! 时，两种情况下都分别能与 $S_1, S_2, \dots, S_N$ 中的某一个一致。

请判断是否存在不满足的字符串；若存在，请输出其中一个。

输入格式

输入按以下格式从标准输入给出：

$N$
$S_1$
$\vdots$
$S_N$

输出格式

如果存在不满足的字符串，输出其中 $1$ 个。

如果不存在，输出 satisfiable。

样例

6
a
!a
b
!c
d
!d

a

字符串 a 在开头附加 $0$ 个 ! 时与 $S_1$ 一致，附加 $1$ 个 ! 时与 $S_2$ 一致，因此是不满足的字符串。

除了 a 之外，输出 d 也是正确答案。

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

satisfiable

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le |S_i| \le 10$
• $S_i$ 是在由小写英文字母组成的非空字符串开头附加 $0$ 个或 $1$ 个 ! 得到的字符串。

提示

答案不唯一，输出任意合法解即可。