As we all know, Max is the best video game player among her friends. Her friends were so jealous of hers, that they created an actual game just to prove that she's not the best at games. The game is played on a directed acyclic graph (a DAG) with _n_ vertices and _m_ edges. There's a character written on each edge, a lowercase English letter.
<center></center>Max and Lucas are playing the game. Max goes first, then Lucas, then Max again and so on. Each player has a marble, initially located at some vertex. Each player in his/her turn should move his/her marble along some edge (a player can move the marble from vertex _v_ to vertex _u_ if there's an outgoing edge from _v_ to _u_). If the player moves his/her marble from vertex _v_ to vertex _u_, the "character" of that round is the character written on the edge from _v_ to _u_. There's one additional rule; the ASCII code of character of round _i_ should be **greater than or equal** to the ASCII code of character of round _i_ - 1 (for _i_ > 1). The rounds are numbered for both players together, i. e. Max goes in odd numbers, Lucas goes in even numbers. The player that can't make a move loses the game. The marbles may be at the same vertex at the same time.
Since the game could take a while and Lucas and Max have to focus on finding Dart, they don't have time to play. So they asked you, if they both play optimally, who wins the game?
You have to determine the winner of the game for all initial positions of the marbles.
## Input
The first line of input contains two integers _n_ and _m_ (2 ≤ _n_ ≤ 100, ).
The next _m_ lines contain the edges. Each line contains two integers _v_, _u_ and a lowercase English letter _c_, meaning there's an edge from _v_ to _u_ written _c_ on it (1 ≤ _v_, _u_ ≤ _n_, _v_ ≠ _u_). There's at most one edge between any pair of vertices. It is guaranteed that the graph is acyclic.
## Output
Print _n_ lines, a string of length _n_ in each one. The _j_\-th character in _i_\-th line should be 'A' if Max will win the game in case her marble is initially at vertex _i_ and Lucas's marble is initially at vertex _j_, and 'B' otherwise.
[samples]
## Note
Here's the graph in the first sample test case:
<center></center>Here's the graph in the second sample test case:
<center></center>
**Definitions**
Let $ G = (V, E) $ be a directed acyclic graph (DAG) with $ |V| = n $, $ |E| = m $.
Each edge $ (v, u) \in E $ is labeled with a character $ c \in \Sigma $, where $ \Sigma $ is the set of lowercase English letters.
Let $ \text{ord}(c) $ denote the ASCII value of character $ c $.
Let $ (i, j) \in V \times V $ denote the initial positions of Max’s and Lucas’s marbles, respectively.
Players alternate turns: Max moves on odd-numbered rounds, Lucas on even-numbered rounds.
Let $ r \geq 1 $ denote the global round number (1-indexed).
Let $ c_r \in \Sigma $ denote the character used in round $ r $.
Constraint: $ \text{ord}(c_r) \geq \text{ord}(c_{r-1}) $ for all $ r \geq 2 $.
A player loses if they cannot make a valid move on their turn.
**Constraints**
1. $ 2 \leq n \leq 100 $, $ m \leq \frac{n(n-1)}{2} $
2. $ G $ is acyclic.
3. For each edge $ (v, u, c) \in E $, $ 1 \leq v, u \leq n $, $ v \neq u $, $ c \in \Sigma $.
4. At most one edge between any pair of vertices.
**Objective**
For each initial state $ (i, j) \in V \times V $, determine the winner under optimal play:
- Output an $ n \times n $ matrix $ W $, where $ W[i][j] = $
- `'A'` if Max wins when starting at $ (i, j) $,
- `'B'` otherwise.
The game state is fully described by $ (v, u, \ell) $, where:
- $ v \in V $: Max’s current vertex,
- $ u \in V $: Lucas’s current vertex,
- $ \ell \in \Sigma \cup \{ \bot \} $: last used character (or $ \bot $ for no prior move).
Define $ \text{win}(v, u, \ell) \in \{ \text{True}, \text{False} \} $:
- True if the *current player* can force a win from state $ (v, u, \ell) $.
- The current player is Max if the number of prior moves is even (i.e., round is odd), Lucas otherwise.
But since turn order is determined by move count, and the state must encode whose turn it is, we instead define:
Let $ \text{dp}[v][u][c] $ be a boolean value indicating whether the *current player* wins from state where:
- Max is at vertex $ v $,
- Lucas is at vertex $ u $,
- Last character used is $ c \in \Sigma \cup \{ \bot \} $,
- The turn is determined implicitly by the number of moves made (which is not stored, so we must encode turn in state).
But since the parity of moves determines the current player, and the state space is small ($ n \leq 100 $, $ |\Sigma| = 26 $), we define:
**State:** $ (v, u, \ell, p) $, where:
- $ v, u \in V $: positions of Max and Lucas,
- $ \ell \in \Sigma \cup \{ \bot \} $: last character played ($ \bot $ for no move yet),
- $ p \in \{0, 1\} $: player to move (0 = Max, 1 = Lucas).
**Transition:**
From state $ (v, u, \ell, p) $, the current player $ p $ moves their own marble:
- If $ p = 0 $: choose edge $ (v, v', c) \in E $ such that $ \text{ord}(c) \geq \text{ord}(\ell) $ (if $ \ell \neq \bot $), or any $ c $ if $ \ell = \bot $.
- If $ p = 1 $: choose edge $ (u, u', c) \in E $ with same constraint.
New state:
- If $ p = 0 $: $ (v', u, c, 1) $
- If $ p = 1 $: $ (v, u', c, 0) $
**Base case:**
If no valid move exists, current player loses → return False.
**Objective:**
For all $ i, j \in V $:
Compute $ \text{dp}[i][j][\bot][0] $ → if True, output `'A'`; else `'B'`.
**Output:**
An $ n \times n $ matrix where entry $ (i, j) $ is `'A'` if $ \text{dp}[i][j][\bot][0] = \text{True} $, else `'B'`.