配点 : $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 と出力せよ。

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