← 返回题目列表

AtCoder · abc187_c

C. 一元可满足性

中文机器翻译题面 查看原题

分数: 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