In AMPPZ 2025, $80$ teams from $27$ institutions are competing. The abbreviations of these institutions are UW, UJ, UWR, MAP, PW, AGH, PG, NLU, PUT, PO, PWR, SGGW, UMCS, UR, ZUT, DTP, GOO, HUA, KUL, PL, PM, PS, UAM, UG, UMK, UO, WAT. Here is the complete table showing the number of teams from each institution*:

*The list of teams may change slightly between the preparation of this task and the contest.

The contest hall is an $8 \times 10$ grid consisting of $8$ rows with $10$ workstations each. To prevent unauthorized communication, the organizers must find an arrangement in which teams from the same institution do not sit next to each other – neither sharing an edge nor a corner.

The audience has its favorite – a team from the institution whose abbreviation is given in the input. The film crew has already set up their cameras in the top-left corner of the contest hall, so one team from the institution given in the input must be seated there.

Find any arrangement of teams that satisfies the given conditions.

Input

The only line contains a word consisting of $2$ to $4$ uppercase letters – the abbreviation of the favorite institution (one of the $27$ listed above).

Output

Print the found arrangement of teams – $8$ lines, each with $10$ words (abbreviations) separated by spaces. The first word in the first line must match the favorite institution provided in the input. If multiple solutions exist, print any of them.

Note

In the example test, the audience's favorite is Uniwersytet Wrocławski†. The provided output contains correct abbreviations and counts, and UWR indeed appears in the top-left corner. However, this is not a valid output, because in many places teams from the same institution are adjacent to each other. Below, three example collisions are highlighted in bold.

†Perhaps because one of UWR's teams won the previous edition of AMPPZ.