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×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≤n≤100.
- 1≤m≤n×(n−1)2.
- 1≤u,v≤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:
4412h24a23w34k
Output:
P∀AAP∀APPAPPPP