Problem B
Deterministic Finite Automata - Complement

You are given a deterministic finite automaton that accepts the language $\mathcal{L}$ You should output the complement, a deterministic finite automaton that accepts the language $\overline{\mathcal{L}}$.

Input

The first line of inputs contains two positive integers $n$, $c$, $s$, and $f$, where $n$ is the number of states, $c$ is the size of the alphabet, $s$ is the initial state, and $f$ is the number of final states. The second line consists of a string $\Sigma = \Sigma _1\Sigma _2\dots \Sigma _c$ of $c$ distinct symbols, each of which is a lowercase english character. The third line consists of $f$ distinct positive integers, the set of final states. Then $n$ lines follow, each with $c$ positive integers, describing the symbol table. The $j$-th integer on the $i$-th of those lines represents the state transitioned to from state $i$ upon reading $\Sigma _j$.

Each state is an integer between $1$ and $n$. It is guaranteed that $n \cdot c \leq 100\, 022$, $1 \leq s \leq n$, and $0 \leq f \leq n$.

Output

Output any deterministic finite automaton representing the complement of the input automaton. Your output is subject to the same format and restrictions as the input.

3 2 1 1
ab
1
1 2
1 3
3 3

4 2 1 3
ab
2 3 4
1 2
1 3
3 4
4 3

1 4 1 0
acgt

1 1 1 1

1 4 1 1
acgt
1
1 1 1 1