###正答
N = int(input())
S = set(input() for i in range(N))
for s in S:
if "!" + s in S:
print(s)
exit()
print("satisfiable")
###ポイント
x in listは計算量オーダーO(N)だが
x in setは計算量オーダーO(1)となることを利用すると簡単に溶ける。
理由はset型のデータは各値をハッシュ関数という関数に入れて出てきた値を結び付けているかららしい。
以下の記事がわかりやすかったのでリンクを貼っておく
####ハッシュテーブル(Hash Table)を簡単に理解しよう
上の記事を参考にしてx in setが内部でどのような動きをしているかわかりやすく例を挙げる。
set={23,7,11,4,10}の要素に9が含まれるかどうか考える。
ここでhash(x)=x%5なるハッシュ関数を考えると
hash(23)=3,hash(7)=2,hash(11)=1,hash(4)=4,hash(10)=0となるので
メモリの0番地に10を,１番地に11を,2番地に7を,3番地に23を,4番地に4を格納する。
ここでhash(9)=4なので4番地のメモリに入ってる数を確かめる。
結果、入っていた数は4であり、9ではないのでsetに9は含まれないことがわかる。
以上の例でリストだと1番地から4番地までの全てで値を確認しなければならなかったのがsetを使うことで4番地だけ確認するだけで済んだことがわかる。
###一言
今回のコンテストでこの問題につまづいて40分程度溶かしてしまった。
こんな問題知識がなければ解けるはずもないのでとっとと切りあげればよかった。
閃き系の問題なら時間かけることで解けるかもしれないが、知識問題だとどうしても無理だ。
かといって今解いてる問題が知識問題なのか閃き問題なのかはわからないので次からは30分悩んでもできなかったら飛ばして次の問題に行くことにしよう。