Alice challenged Patchouli a game to determine her knowledge about her dolls. Specifically, she created a matrix, which is a directed acyclic graph with $n$ vertices and $m$ edges. Each edge is weighed a lower-case English letter. Initially, Alice gave herself and Patchouli each a doll, onto which the letter `a` was labeled, and placed each of them on a vertex of the matrix.
Each turn's event is as the following:
- Each person can move their doll from vertex $u$ to vertex $v$ if and only if there exists an edge from $u$ and $v$ with a weight (letter) being **no less than** the current label alphabetically, and that very letter will be assigned to both dolls.
- The first person unable to do this loses the game.
Afraid that her game wouldn't be challenging enough for Patchouli (as she's one of **those who know**), Alice gave Patchouli the riddle: If both of them played optimally and Alice goes first, then for each scenario, assuming Alice's doll started at $i$, and Patchouli's doll at $j$, who would win the game?
Let's help Patchouli find the answer!
### Input:
The first lines contains $2$ integers $n$ and $m$ - The number of vertices and edges of the matrix.
The next $m$ lines, each consists of $2$ integers $u$ and $v$, and a letter $w$ - Indicating that there exists an edge from $u$ to $v$, to which $w$ was assigned.
### Output:
Print a $n \times n$ matrix of characters, `A` at row $i$, column $j$, if Alice would win the game if her doll was placed on vertex $i$, Patchouli's on vertex $j$, and `P` otherwise.
### Constraints
- $1 \le n \le 100$.
- $1 \le m \le \frac{ n \times (n - 1)}2$.
- $1 \leq u, v \leq n$.
It is guaranteed that the matrix is a directed acyclic graph, and that there should exist no pair of vertices connected by more than $1$ edge.
### Example
Input:
```
4 4
1 2 h
2 4 a
2 3 w
3 4 k
```
Output:
```
PAAA
APAA
APPA
PPPP
```
