D. Пасьянс
ограничение по времени на тест
1.5 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть колода карт в 54 листа (52 стандартных карты и 2 различных джокера). Это все, что у него есть на данный момент. Чтобы не умереть со скуки, Вася раскладывает из них пасьянс.

Вася раскладывает nm карт в виде прямоугольника n × m. Если среди них есть джокеры, то Вася должен заменить их на некоторые из 54 - nm оставшихся (т. е. не лежащих на столе) карт так, чтобы джокеров не осталось. Вася может выбирать карты для замены произвольным образом. Помните, что каждая карта присутствует в колоде в единственном экземпляре. Вася старается сделать замену таким образом, чтобы пасьянс сошелся.

Вася считает, что пасьянс сошелся, если после замены джокеров существует два не пересекающихся квадрата 3 × 3, внутри каждого из которых все карты имеют либо одинаковую масть, либо попарно различные достоинства.

Определите по начальной позиции — может ли пасьянс сойтись или нет. И если да — укажите способ, которым это можно сделать.

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

В первой строке находятся целые числа n и m (3 ≤ n, m ≤ 17, n × m ≤ 52). В следующих n строках находятся по m слов в каждой. Каждое слово состоит из двух букв. Джокеры обозначаются «J1» и «J2» соответственно. Для всех остальных карт первая буква обозначает достоинство, а вторая — масть. Возможные достоинства: «2», «3», «4», «5», «6», «7», «8», «9», «T», «J», «Q», «K» и «A». Возможные масти: «C», «D», «H» и «S». Все карты различны.

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

Если пасьянс может сойтись — в первой строке выведите «Solution exists.» без кавычек. Во второй строке выведите каким образом нужно заменить джокеры. Возможны три варианта:

  • «There are no jokers.» — если джокеров во входных данных нет.
  • «Replace Jx with y.» — если джокер один. x — его номер, а y — карта, на которую его следует заменить.
  • «Replace J1 with x and J2 with y.» — если оба джокера присутствуют во входных данных. x и y здесь — различные карты, на которые нужно заменить первого и второго джокеров соответственно.

В третьей строке выведите координаты левого верхнего угла первого квадрата 3 × 3 в формате «Put the first square to (r, c).», где r и c — строка и столбец соответственно. Аналогичным образом в четвертой строке выведите координаты второго квадрата 3 × 3 в формате «Put the second square to (r, c).».

Если решений несколько — выведите любое.

Если решений нет — в единственной строке выведите «No solution.» без кавычек.

Смотрите примеры для более точного понимания формата вывода.

Примеры
Входные данные
4 6
2S 3S 4S 7S 8S AS
5H 6H 7H 5S TC AC
8H 9H TH 7C 8C 9C
2D 2C 3C 4C 5C 6C
Выходные данные
No solution.
Входные данные
4 6
2S 3S 4S 7S 8S AS
5H 6H 7H J1 TC AC
8H 9H TH 7C 8C 9C
2D 2C 3C 4C 5C 6C
Выходные данные
Solution exists.
Replace J1 with 2H.
Put the first square to (1, 1).
Put the second square to (2, 4).
Входные данные
4 6
2S 3S 4S 7S 8S AS
5H 6H 7H QC TC AC
8H 9H TH 7C 8C 9C
2D 2C 3C 4C 5C 6C
Выходные данные
Solution exists.
There are no jokers.
Put the first square to (1, 1).
Put the second square to (2, 4).
Примечание

Претесты покрывают все возможные форматы вывода.