마상 창시합 대진표

마상 창시합은 말을 탄 기사 두 명이 서로를 말에서 떨어뜨리려고 겨루는 경기다. 참가자가 많아지면서 대진표를 손으로 짜기 어려워졌고, 이제는 자동으로 만들어야 한다. 대회 전체에서 가장 강한 기사를 가려내는 대진표를 출력하라.

참가자는 n명이고 1, 2, ..., n번으로 번호가 붙어 있다. 각 참가자의 실력 수치는 대회 내내 변하지 않으며, 경기에서는 실력 수치가 더 높은 쪽이 이긴다. 모든 참가자의 실력 수치는 서로 다르므로 무승부는 없다.

대진표는 순서가 있는 삼중항의 나열이다. 삼중항의 앞 두 항목은 맞붙는 두 참가자이고, 마지막 항목은 승자를 담는 자리표다. 자리표는 알파벳 소문자 a부터 z까지이고, 참가자 자리에는 번호나 자리표를 쓴다. 예를 들어

1 2 a

는 1번과 2번이 맞붙고 그 승자가 a에 저장된다는 뜻이다. 이 경기 이후로는 a를 참가자로 쓸 수 있다. 기사 4명이 3경기를 치르는 대진표는 다음과 같이 쓸 수 있다.

1 2 a
3 4 b
a b c

이 대회의 우승자는 c에 저장된 기사다.

자리표는 앞선 경기에서 승자를 저장한 뒤에야 참가자로 쓸 수 있다. 한 경기에서 같은 자리표를 참가자와 승자로 동시에 쓸 수는 없다. 자리표를 다시 써도 되지만, 새 승자를 저장하면 그 전에 담고 있던 기사 정보는 사라진다.

한 기사가 치르는 경기 수에는 제한이 없고, 한 경기의 두 참가자가 같은 기사여도 된다.

첫째 줄에 참가자 수 $n$이 주어진다. ($2 \le n \le 1\,000$)

대진표를 한 줄에 한 경기씩 출력한다. 한 경기의 세 항목은 공백 하나로 구분한다. 등장할 수 있는 것은 정수 $1, 2, \ldots, n$과 소문자 자리표뿐이고, 경기 수는 $10\,000$개를 넘을 수 없으며, 대회가 끝난 시점에 우승자는 자리표 a에 저장되어 있어야 한다.

조건을 만족하는 대진표는 여러 가지이므로, 다음 규칙으로 만든 대진표 하나만 정답으로 인정한다.

1. 첫 줄에 1 2 a를 출력한다.
2. $k = 3, 4, \ldots, n$ 순서로, 지금까지의 승자를 담고 있는 자리표와 $k$번 기사의 경기를 출력하고, 승자는 a와 b 중 나머지 자리표에 저장한다. 따라서 둘째 줄은 a 3 b, 셋째 줄은 b 4 a, 넷째 줄은 a 5 b가 되며 두 글자가 번갈아 나온다.
3. 마지막으로 출력한 경기의 승자가 b에 저장되었다면, b b a 한 줄을 더 출력한다.