You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定确定性有限状态自动机（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$ 组测试的答案。

样例

2
5 1 6
4
2 5
5 3
4 2
5 5
5 5
3 1 2
2
2 3
3 3
3 3

CCCCA
WA

提示

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