P17453 AC 自动机 / AC Automaton

给定确定性有限状态自动机（DFA），状态集 $Q=\{1,2,\dots,n\}$，起始状态 $q=1$，接受状态集 $F$ 大小为 $m$，字母表 $\Sigma=\{\texttt{A},\texttt{C}\}$。计算能够被自动机接受且长度不短于 $k$ 的字符串中字典序最小者。由于答案可能很长，因此如果答案的长度超过 $n$，你只需要输出答案的最后 $n$ 个字符。若满足前述要求的字符串不存在，输出 `WA`。 字符串被自动机接受，当且仅当存在一条从初始状态开始、到接受状态结束的 walk，使得走过的转移边的字母恰好形成了该字符串。walk 可以经过重复点、重复边。

**本题有多组测试数据。** 第一行包含一个整数 $T$ ($1\le T\le 5\times 10^5$)，表示测试数据组数。 对每组测试： - 第一行包含用空格分隔的三个整数，依次表示：状态数 $n$ ($2\le n\le 10^6$)，接受状态数 $m$ ($1\le m\le n-1$)，长度下限 $k$ ($1\le k\le 10^9$)。 - 第二行包含用空格分隔的 $m$ 个整数，表示接受状态集。保证这些数均在 $[2,n]$ 之间，且不重复。 - 接下来 $n$ 行，每行包含用空格分隔的 $2$ 个整数，其中第 $i$ 行的两个整数分别表示状态 $i$ 沿 `A`/`C` 转移后的状态。 保证 $\sum n\le 10^6$。

输出 $T$ 行，每行输出一个字符串，其中第 $i$ 行表示第 $i$ 组测试的答案。

样例第一组测试中，DFA 识别的语言为 $\{\texttt{A}\texttt{C}^{2t+1}\texttt{A}\mid t\ge 0\}$。