On the day before this contest, two CCPC teams are playing a game after dress rehearsal.
As we know, a CCPC team consists of $3$ contestants, so there are $6$ players in the game. The game is played on a directed graph. The graph has $n$ vertices and $m$ arcs. These vertices are labeled by $1, 2, \\dots, n$.
Initially, there is a token placed in one of the graph vertices. Players take turns moving the token along one of the arcs that starts in the vertex the token is currently in. When there is no such arc, then this player's team loses the game.
Let's mark two teams as $A$ and $B$, then the order of $6$ players can be displayed as a string $o r d$ with length $6$. Player from team $o r d_1$ moves first, then $o r d_2, o r d_3, \\dots, o r d_6, o r d_1 \\dots$
Each player will follow a strategy that leads his team to win, and if there is no possible to win, he will try to make the game run infinitely. But some contestants announce they are "actors" before the game, each of them will follow a strategy that leads his team to lose, and if there is no possible to lose, he will try to make the game run infinitely.
All the players know what the order is and who are actors. They also know preferences of other players. They will play optimally, but they are not allowed to discuss before or during the game.
For each initial position of the token, your task is to determine what kind of result the game is going to have.
The first line of the input contains an integer $T (1 <= T <= 100)$, denoting the number of test cases.
In each test case, there is two integers $n (1 <= n <= 100000, 1 <= m <= 200000)$ in the first line, denoting the number of vertices and arcs.
For the next $m$ lines, each line contains two integers $u_i, v_i (1 <= u_i, v_i <= n)$, denoting an arc from vertex $u_i$ to vertex $v_i$. Note that $u_i$ can be the same with $v_i$, but no arc will appear more than once.
The next line contains a string $o r d$ of length 6, denoting the order. There are exactly $3$ of which are "_A_" and the others are "_B_".
The next line contains six integers $a_1, a_2, \\dots, a_6 (0 <= a_i <= 1)$, where $a_i$ denotes whether the player corresponding to $o r d_i$ is an actor. Specifically, $a_i = 1$ means he is an actor while $a_i = 0$ means not.
It is guaranteed that $sum n <= 2 times 10^6$ and $sum m <= 3 times 10^6$.
For each test case, print a single line containing $n$ characters, where the $i$-th character should denote the result of the game if the token is in vertex $i$ initially. The result of the game is denoted by "_A_" if the team $A$ wins the game, "_B_" if the team $B$ wins the game, and "_D_" if the game runs infinitely.
## Input
The first line of the input contains an integer $T (1 <= T <= 100)$, denoting the number of test cases.In each test case, there is two integers $n (1 <= n <= 100000, 1 <= m <= 200000)$ in the first line, denoting the number of vertices and arcs.For the next $m$ lines, each line contains two integers $u_i, v_i (1 <= u_i, v_i <= n)$, denoting an arc from vertex $u_i$ to vertex $v_i$. Note that $u_i$ can be the same with $v_i$, but no arc will appear more than once.The next line contains a string $o r d$ of length 6, denoting the order. There are exactly $3$ of which are "_A_" and the others are "_B_".The next line contains six integers $a_1, a_2, \\dots, a_6 (0 <= a_i <= 1)$, where $a_i$ denotes whether the player corresponding to $o r d_i$ is an actor. Specifically, $a_i = 1$ means he is an actor while $a_i = 0$ means not.It is guaranteed that $sum n <= 2 times 10^6$ and $sum m <= 3 times 10^6$.
## Output
For each test case, print a single line containing $n$ characters, where the $i$-th character should denote the result of the game if the token is in vertex $i$ initially. The result of the game is denoted by "_A_" if the team $A$ wins the game, "_B_" if the team $B$ wins the game, and "_D_" if the game runs infinitely.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the number of cities.
- Let $ r = (r_1, r_2, \dots, r_n) \in \mathbb{Z}^n $ be the risk vector, where $ r_i $ is the risk in city $ i $.
- Let $ D = [d_{i,j}] \in \mathbb{Z}^{n \times n} $ be the symmetric distance matrix, with $ d_{i,i} = 0 $ and $ d_{i,j} = d_{j,i} \geq 1 $ for $ i \neq j $.
- Let $ q \in \mathbb{Z} $ be the number of queries.
Each query is a triple $ (u, v, w) \in \{1, \dots, n\}^2 \times \mathbb{Z} $, with $ w $ being the risk threshold.
**Constraints**
1. $ 1 \leq T \leq 50 $
2. $ 1 \leq n \leq 200 $, $ 1 \leq q \leq 2 \times 10^4 $
3. $ 1 \leq r_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $
4. $ 1 \leq d_{i,j} \leq 10^5 $ for $ i \neq j $, $ d_{i,i} = 0 $, $ d_{i,j} = d_{j,i} $
5. For each query: $ 1 \leq u, v \leq n $, $ 1 \leq w \leq 10^5 $
**Objective**
For each query $ (u, v, w) $, compute the shortest path length from city $ u $ to city $ v $, such that every intermediate city $ k $ on the path satisfies $ r_k \leq w $.
That is, define the subgraph $ G_w = (V_w, E_w) $ where:
- $ V_w = \{ i \in \{1, \dots, n\} \mid r_i \leq w \} $,
- $ E_w = \{ (i,j) \mid i,j \in V_w \text{ and } d_{i,j} < \infty \} $,
then compute:
$$
\text{dist}_w(u, v) = \min \left\{ \sum_{(i,j) \in P} d_{i,j} \,\middle|\, P \text{ is a path from } u \text{ to } v \text{ in } G_w \right\}
$$
If no such path exists, output $ \infty $ (though input guarantees connectivity under constraints).