Сервис плей-офф восстанавливает турнирную сетку соревнования по олимпийской системе.

В турнире участвуют ровно n = 2^k команд, где 1 <= k <= 17. Команды пронумерованы от 1 до n и изначально расположены в фиксированном порядке.

В первом раунде играют пары (1, 2), (3, 4), (5, 6), ..., (n - 1, n). Победитель каждого матча проходит в следующий раунд, сохраняя относительный порядок среди остальных победителей. Поэтому во втором раунде встречаются победитель пары (1, 2) с победителем пары (3, 4), затем победитель пары (5, 6) с победителем пары (7, 8) и так далее. Турнир продолжается, пока не останется один победитель.

Сервис получил полное описание всех матчей по раундам: для каждого матча известны оба участника и победитель. Требуется восстановить представление сетки в формате, удобном для отображения: для каждого матча нужно вывести пару winner loser.

Входные данные

Первая строка содержит одно целое число k (1 <= k <= 17) — показатель степени двойки. Число команд равно n = 2^k.

Далее следуют k блоков, описывающих раунды от первого к последнему.

Каждый блок имеет следующий формат:

• сначала задано число m — количество матчей в текущем раунде;
• затем идут m строк, каждая из которых содержит три целых числа a, b, w.

Это означает, что в очередном матче данного раунда встречались команды a и b, а победителем стала команда w, где w совпадает либо с a, либо с b.

Гарантируется, что входные данные корректны и согласованы с олимпийской системой: в первом раунде пары идут именно в порядке (1, 2), (3, 4), ..., (n - 1, n), а в каждом следующем раунде участники перечислены в том же относительном порядке, что и победители предыдущего раунда.

Выходные данные

Выведите k блоков.

Для каждого раунда i сначала выведите строку Round i:.

Затем для каждого матча этого раунда выведите строку из двух целых чисел в формате winner loser, где winner — победитель матча, а loser — проигравший.

Матчи внутри каждого раунда должны выводиться в том же порядке, в каком они заданы во входных данных.

После всех раундов выведите дополнительную строку формата Champion: w, где w — победитель турнира.

Ограничения

• 1 <= k <= 17
• n = 2^k
• все команды пронумерованы от 1 до n
• ввод осуществляется через стандартный ввод
• вывод осуществляется через стандартный вывод

Примеры

Пример 1

Входные данные

1
1
1 2 1

Выходные данные

Round 1:
1 2
Champion: 1

Пример 2

Входные данные

2
2
1 2 1
3 4 4
1
1 4 4

Выходные данные

Round 1:
1 2
4 3
Round 2:
4 1
Champion: 4