Contest Duration: - (local time) (100 minutes) Back to Home
C - 1-SAT /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 個の文字列 S_1, S_2, \dots, S_N が与えられます。 各文字列は、英小文字からなる空でない文字列の先頭に !0 文字か 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

6
a
!a
b
!c
d
!d


### 出力例 1

a


a の他に、d を出力しても正解になります。

### 入力例 2

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


### 出力例 2

satisfiable


Score : 300 points

### Problem Statement

Given are N strings S_1, S_2, \dots, S_N. Each of these is a non-empty string consisting of lowercase English letters, with zero or one ! added at the beginning.
We say a string T to be unsatisfied when it matches one of S_1, S_2, \dots, S_N regardless of whether we add an ! at the beginning of T.
Determine whether there exists an unsatisfied string. If so, present one such string.

### Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le |S_i| \le 10
• S_i is a non-empty string consisting of lowercase English letters, with zero or one ! added at the beginning.

### Input

Input is given from Standard Input in the following format:

N
S_1
\vdots
S_N


### Output

If there exists an unsatisfied string, print one such string.
If there is no unsatisfied string, print satisfiable.

### Sample Input 1

6
a
!a
b
!c
d
!d


### Sample Output 1

a


a matches S_1 as is, and it matches S_2 when we add an !, so it is unsatisfied. Besides that, d will also be accepted.

### Sample Input 2

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


### Sample Output 2

satisfiable