D3. Игра в Девятку III
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этой версии задачи нужно найти $$$26$$$ раскладов с различными значениями важности первого хода.

Алиса и Боб решили сыграть в карточную игру «Девятка». Пожалуйста, внимательно прочитайте условие задачи, поскольку правила могут отличаться от известных вам.

Для игры нужна стандартная колода из $$$36$$$ карт — по девять карт (от шестёрки до туза) каждой из четырёх мастей (трефы, бубны, пики и черви). Карты по достоинству от младшей к старшей идут следующим образом: шестёрка, семёрка, восьмёрка, девятка, десятка, валет, дама, король, туз.

Перед игрой колода перемешивается, и каждому игроку раздаётся по $$$18$$$ карт. Карты нужно выкладывать из руки на стол по определённым правилам. Выигрывает игрок, который первым выложит все карты из своей руки.

Игроки ходят по очереди. Ход игрока имеет один из следующих видов:

  • выложить на стол из своей руки девятку любой масти;
  • выложить на стол шестёрку, семёрку или восьмёрку любой масти, если на столе уже лежит карта той же масти достоинством на единицу выше;
  • выложить на стол десятку, валета, даму, короля или туза любой масти, если на столе уже лежит карта той же масти достоинством на единицу ниже.

Например, девятку пик можно выложить на стол в любой момент, для выкладывания семёрки треф необходимо наличие на столе восьмёрки треф, а для выкладывания туза червей необходимо наличие на столе короля червей.

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

Помимо того, что каждый игрок стремится избавиться от карт в своей руке, Алиса и Боб также хотят, чтобы в конце игры в руке у их соперника карт осталось как можно больше, а в их руке — как можно меньше. Напомним, что игра заканчивается, как только один из игроков выкладывает на стол последнюю карту из своей руки.

Результатом игры назовём совокупность из информации о том, кто из двух игроков выиграет при оптимальной игре, а также о том, сколько карт останется в руке у проигравшего.

Пусть Алиса и Боб уже взяли в руки свои $$$18$$$ карт каждый, но ещё не решили, кто из них будет ходить первым. Величиной важности первого хода для данного расклада назовём абсолютную разность между результатами игры в случае, если первой будет ходить Алиса, и в случае, если первым будет ходить Боб.

Например, если в обоих случаях выиграет Боб, но в одном случае у Алисы останется $$$6$$$ карт в руке в конце игры, а во втором — всего $$$2$$$, то величина важности первого хода равна $$$4$$$. Если же в одном случае выиграет Алиса и у Боба останется $$$5$$$ карт в руке, а во втором случае выиграет Боб и у Алисы останется $$$3$$$ карты в руке, то величина важности первого хода равна $$$8$$$.

Ребята хотят узнать, насколько разной бывает величина важности первого хода для разных раскладов. По заданному числу $$$k \le 26$$$ помогите им найти такие $$$k$$$ раскладов, что величины важности первого хода для всех них — различные целые числа.

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

В единственной строке задано целое число $$$k$$$ ($$$2 \le k \le 26$$$) — число необходимых раскладов.

В задаче три теста. В первом тесте $$$k = 2$$$, во втором тесте $$$k = 13$$$, в третьем тесте $$$k = 26$$$.

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

Выведите $$$k$$$ пар строк. Каждая пара строк должна соответствовать некоторому раскладу. Величины важности первого хода для всех выведенных раскладов должны быть различными целыми числами.

В первой строке каждой пары выведите $$$18$$$ строк длины $$$2$$$ через пробел, описывающих карты Алисы в любом порядке. Первый символ строки должен обозначать достоинство карты — символ из набора 6, 7, 8, 9, T, J, Q, K, A, обозначающий шестёрку, семёрку, восьмёрку, девятку, десятку, валета, даму, короля и туза соответственно. Второй символ строки должен обозначать масть карты — символ из набора C, D, S, H, обозначающий трефы, бубны, пики и черви соответственно.

Во второй строке выведите $$$18$$$ строк длины $$$2$$$ через пробел, описывающих карты Боба в том же формате.

Каждая из $$$36$$$ возможных карт должна находиться в руке одного из двух игроков в единственном экземпляре.

Пример
Входные данные
2
Выходные данные
KS QD 8D QC 8S 8C JD 9H AC TH 9S 9D QH 7H 8H TS 7S 9C
6D JS 7D KH QS TC AD AS KC 6C 7C TD AH KD 6S JC JH 6H

JC JS 8S TD JD KH 7D 9C KC TH QD 8D 7H TC KD 9H 8C 6D
7S AC QH AD 8H TS 6H JH 6C AH 7C 6S 9D QC AS QS KS 9S
Примечание

В первом выведенном раскладе все девятки находятся в руке у Алисы. Даже если Боб будет ходить первым, ему всё равно придётся пропустить первый же свой ход. Следовательно, первый ход при таком раскладе имеет важность $$$0$$$.

Во втором выведенном раскладе вне зависимости от того, чьим будет первый ход, выиграет Алиса. Однако если Алиса будет ходить первой, то у Боба в конце игры в руке останется одна карта, а если же она будет ходить второй, то у Боба останется пять карт. Соответственно, величина важности первого хода при таком раскладе равна $$$4$$$.