L. AC Automaton
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a deterministic finite automaton (DFA) with a state set $$$Q=\{1,2,\dots,n\}$$$, a start state $$$q=1$$$, an accept state set $$$F$$$ of size $$$m$$$, and an alphabet $$$\Sigma=\{\texttt{A},\texttt{C}\}$$$. Find the lexicographically smallest string accepted by the automaton with a length of at least $$$k$$$. Since the answer might be very long, if the length of the answer exceeds $$$n$$$, you only need to output the last $$$n$$$ characters of the answer. If no string satisfies the aforementioned requirements, output WA.

A string is accepted by the automaton if and only if there exists a walk starting from the initial state and ending at an accept state, such that the letters on the traversed transition edges exactly form the string. The walk can pass through repeated vertices and edges.

Input

There are multiple test cases.

The first line contains a single integer $$$T$$$ $$$(1\le T\le 5\times 10^5)$$$, denoting the number of test cases.

For each test case:

  • The first line contains three space-separated integers: the number of states $$$n$$$ $$$(2\le n\le 10^6)$$$, the number of accept states $$$m$$$ $$$(1\le m\le n-1)$$$, and the lower bound of the length $$$k$$$ $$$(1\le k\le 10^9)$$$.
  • The next line contains $$$m$$$ space-separated distinct integers, denoting the set of accept states. It is guaranteed that these numbers are in the range $$$[2,n]$$$.
  • Then $$$n$$$ lines follow, each containing $$$2$$$ space-separated integers. The two integers on the $$$i$$$-th line denote the states transitioned to from state $$$i$$$ along A and C, respectively.

It is guaranteed that $$$\sum n\le 10^6$$$.

Output

Output $$$T$$$ lines, each containing a string, where the $$$i$$$-th line represents the answer for the $$$i$$$-th test case.

Example
Input
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
Output
CCCCA
WA
Note

In the first test case of the sample, the language recognized by the DFA is $$$\{\texttt{A}\texttt{C}^{2t+1}\texttt{A}\mid t\ge 0\}$$$.