9685: ABC187 —— C - 1-SAT
[Creator : ]
Description
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.
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.
Input
Input is given from Standard Input in the following format:
```
$N$
$S_1$
$\vdots$
$S_N$
```
```
$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`.
If there is no unsatisfied string, print `satisfiable`.
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.
- $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.
Sample 1 Input
6
a
!a
b
!c
d
!d
Sample 1 Output
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 2 Input
10
red
red
red
!orange
yellow
!blue
cyan
!green
brown
!gray
Sample 2 Output
satisfiable