Problem C
Deterministic Finite Automata - Union

You are given two deterministic finite automata that accept the languages $\mathcal{L}_1$ and $\mathcal{L}_2$. You should output the union, a deterministic finite automaton that accepts the language $\mathcal{L} = \mathcal{L}_1 \cup \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$.

Let the number of states in the two automata be $n_1$ and $n_2$. The input will satisfy $n_1 \cdot n_2 \cdot c \leq 300\, 000$.

Output

Output any deterministic finite automaton representing the union 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$.

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

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

1 4 1 0
acgt

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

1 4 1 1
acgt
1
1 1 1 1