Problem M. Match Schedule ≡

Statement

There are n teams participating in a football tournament. Each team plays against every other team exactly once. The goal is to arrange the matches such that, for each team, the number of home matches differs from the number of away matches by no more than 1.

You are required to output the schedule in the form of an n × n table. The i-th row should describe the matches of the i-th team, where:

• If the j-th element in the row is 'H', it means the match between teams i and j will take place at the home stadium of team i.
• If the j-th element in the row is 'A', it means the match will take place at the home stadium of team j.
• The diagonal elements (where i = j) should be marked with 'X' as no team plays against itself.

Input format

The first line of input contains a single integer n, representing the number of teams.

Output format

Output n lines, each containing n characters ('H', 'A', or 'X'), describing the desired match schedule. The match schedule must be consistent, meaning there are no contradictions.

Constraints

1 ≤ n ≤ 100

Sample tests

5

XAAHH
HXAAH
HHXAA
AHHXA
AAHHX

2

XA
HX