Problem G
Deterministic Finite Automata - Concatenation

You are given two deterministic finite automata that accept the languages $\mathcal{L}_1$ and $\mathcal{L}_2$. You should output the concatenation, a deterministic finite automaton that accepts the language $\mathcal{L} = \mathcal{L}_1\mathcal{L}_2$.

Input

The input contains the description of two deterministic finite automata that use the same alphabet. Each is described as follows.

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 s \leq n$, and $0 \leq f \leq n$.

Additionally it is guaranteed the total number of states in the input is at most $21$.

Output

Output any deterministic finite automaton representing the concatenation 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}$ which can be converted to a deterministic finite automata adhering to these limits using the power set construction without any additional reductions.

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

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

1 4 1 0
acgt

1 1 1 1
1 4 1 1
acgt
1
1 1 1 1

1 4 1 0
acgt

1 1 1 1