D. Карточная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два игрока играют в карточную онлайн-игру. Игра играется с использованием колоды из 32 карт. У каждой карты есть масть и ранг. Существует четыре масти: трефы, бубны, червы и пики. Мы закодируем их символами 'C', 'D', 'H', и 'S' соответственно. И существует 8 рангов, в порядке возрастания: '2', '3', '4', '5', '6', '7', '8', '9'.

Каждая карта обозначается двумя буквами: ее рангом и мастью. Например, восьмёрка червей обозначается как 8H.

В начале игры выбирается одна масть как козырная масть.

На каждом ходу игроки делают ходы следующим образом: первый игрок кладет одну из своих карт на стол, и второй игрок должен побить эту карту одной из своих карт. После этого обе карты перемещаются на сброс.

Карта может побить другую карту, если обе карты имеют одинаковую масть, и у первой карты ранг выше, чем у второй. Например, 8S может побить 4S. Кроме того, козырная карта может побить любую некозырную карту, независимо от ранга карт, например, если козырная масть — трефы ('C'), то 3C может побить 9D. Обратите внимание, что козырные карты могут быть побиты только козырными картами более высокого ранга.

В игре было сыграно $$$n$$$ раундов, поэтому в сбросе теперь находится $$$2n$$$ карт. Вы хотите восстановить раунды, сыгранные в игре, но карты в сбросе перемешаны. Найдите любую возможную последовательность из $$$n$$$ раундов, которая могла быть сыграна в игре.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Затем следуют $$$t$$$ наборов входных данных.

Первая строка набора входных данных содержит целое число $$$n$$$ ($$$1\le n\le 16$$$).

Вторая строка набора входных данных содержит один символ, козырная масть. Она является одной из «CDHS».

Третья строка набора входных данных содержит описание $$$2n$$$ карт. Каждая карта описывается двухсимвольной строкой, первый символ — ранг карты, который является одним из «23456789», и второй — масть карты, которая является одной из «CDHS». Все карты различны.

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

Для каждого теста выведите ответ на него:

  • Выведите $$$n$$$ строк. В каждой строке выведите описание двух карт, в том же формате, что и во входном файле: первая карта, сыгранная первым игроком, и вторая карта — карта, использованная вторым игроком, чтобы ее побить.
  • Если нет решения, выведите одну строку «IMPOSSIBLE».

Если существует несколько ответов, выведите любой из них.

Пример
Входные данные
8
3
S
3C 9S 4C 6D 3S 7S
2
C
3S 5D 9S 6H
1
H
6C 5D
1
S
7S 3S
1
H
9S 9H
1
S
9S 9H
1
C
9D 8H
2
C
9C 9S 6H 8C
Выходные данные
3C 4C
6D 9S
3S 7S
IMPOSSIBLE
IMPOSSIBLE
3S 7S
9S 9H
9H 9S
IMPOSSIBLE
6H 9C
9S 8C