站外题求助

【题目描述】

小明在玩一个游戏：他有若干个不同的命题，每一个命题都是一个仅含小写字母的字符串。他还有若干个陈述，每一个陈述都指出某一个命题的正确与否。现在，他想知道这些陈述是否产生了矛盾，你可以帮帮他吗？

具体的，每一个陈述形如 $S$ 或者 $!S$，其中 $S$ 是一个仅含小写字母的字符串。$S$ 代表命题 $S$ 正确，而 $!S$ 代表命题 $S$ 错误。

【输入格式】

第一行，一个数 $n$ 表示陈述的个数。

接下来 $n$ 行，每行一个仅含小写字母的字符串，代表一个命题。

【输出格式】

如果陈述没有矛盾，则输出 satisfiable。

否则输出产生矛盾，且指出其正确的陈述最早出现的命题。

【样例输入】

7
c
!d
a
!a
b
!c
d

【样例输出】

c

【数据规模】

$S$ 的长度不超过 $10$。

对于 $40\%$ 的数据，$n \le 50$。

对于 $100\%$ 的数据，$n \le 2 \times 10^5$。