Problem H
Deterministic Finite Automata - Kleene Star

You are given a deterministic finite automaton that accepts the language $\mathcal{L}$. You should output the Kleene star, a deterministic finite automaton that accepts the language $\mathcal{L}^{\ast }$.

Input

The input contains the description of a deterministic finite automaton.

The first line contains four 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 $1 \leq n \leq 20$, $1 \leq s \leq n$, and $0 \leq f \leq n$.

Output

Output any deterministic finite automaton representing the Kleene star of the input automata. Your output is subject to the same format and restrictions as the input, except it may be larger, allowing $n \cdot c \leq 300\, 000$.

You may assume that there exists a non-deterministic finite automata accepting $\mathcal{L}^{\ast }$ which can be converted to a deterministic finite automata adhering to these limits using the power set construction without any additional reductions.

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

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

1 4 1 1
acgt
1
1 1 1 1

1 4 1 1
acgt
1
1 1 1 1