Jousting Tournament

Time limit2sMemory limit512 MB

Summary

Print the fixed elimination schedule that pits competitors 1..n one by one, alternating winners between placeholders a and b.

Level: Easy2 of 10
Topics: Implementation, Simulation
Solved: No attempts yet

Problem

Jousting is a sport in which two knights on horseback try to knock each other off. There are so many participants now that the schedule has to be produced automatically. Print a schedule that determines the best jouster in the whole tournament.

There are n competitors numbered 1, 2, ..., n. The skill level of a competitor stays the same for the whole tournament, and the jouster with the higher skill level wins the match. All skill levels are different, so no match ends in a tie.

A schedule is an ordered sequence of triples. The first two items of a triple are the two competitors and the last item is the placeholder that stores the winner. A placeholder is a lowercase letter from a to z, and a competitor is written as a number or as a placeholder. For example,

1 2 a

means that jouster 1 meets jouster 2 and the winner is stored in a. From that match on, a can be used as a competitor. A schedule for a tournament with 4 jousters and 3 matches can be written like this.

1 2 a
3 4 b
a b c

The winner of that tournament is the jouster stored in c.

A placeholder may be used as a competitor only after an earlier match has stored a winner in it. The same placeholder cannot be a competitor and the winner of the same match. You may reuse a placeholder, but storing a new winner in it erases the jouster it held before.

A jouster may compete in any number of matches, and both competitors of a match may be the same jouster.

Input

The input is a single line containing one integer $n$ , the number of competitors. ( $2 \le n \le 1\,000$ )

Output

Print the schedule, one match per line, with the three items of a match separated by single spaces. Only the integers $1, 2, \ldots, n$ and lowercase placeholders may appear, the schedule may contain at most $10\,000$ matches, and the winner of the tournament must be stored in placeholder a when the tournament ends.

Many schedules satisfy those rules, so only the schedule built by the following construction is accepted.

Print 1 2 a on the first line.
For $k = 3, 4, \ldots, n$ in increasing order, print a match between the placeholder that currently holds the winner so far and jouster $k$ , and store the winner in the other placeholder of the pair a and b. The second line is therefore a 3 b, the third is b 4 a, the fourth is a 5 b, and the two letters keep alternating.
If the last match printed stored its winner in b, print one more line b b a.

Examples4

Example 1
Input
```
2
```
Expected output
```
1 2 a
```
Example 2
Input
```
4
```
Expected output
```
1 2 a
a 3 b
b 4 a
```
Example 3
Input
```
6
```
Expected output
```
1 2 a
a 3 b
b 4 a
a 5 b
b 6 a
```

Example 4

Input

Expected output

1 2 a
a 3 b
b 4 a
a 5 b
b 6 a
a 7 b
b b a