Показ мод
Вы собираетесь провести показ мод, чтобы показать три новых стиля одежды. Шоу будет проходить на сцене самой модной из всех форм: на сетке из n на n клеток.
Каждая клетка в сетке может быть или пустой (которую будем представлять символом .), или содержать одну модель моды. Модели бывают трех типов, в зависимости от стиля одежды, которую они носят: +, x и супер-модный o. Ячейка с моделью + или x добавляет к шоу 1 очко за стиль. Ячейка с моделью o добавляет 2 очка за стиль. Пустые ячейки очков не добавляют.
Для достижения максимального художественного эффекта существуют правила размещения моделей относительно друг друга.
Если две модели находятся в одном ряду или в одной колонке, то хотя бы одна из них должна быть +.
Если две модели находятся на одной диагонали, то хотя бы одна из них должна быть x.
Формально, модель расположенная в строке i[0] и колонке j[0] и модель расположенная в строке i[1] и колонке j[1], находятся в одной строке если i[0] = i[1], находятся в одной колонке если j[0] = j[1], находятся на одной диагонали если i[0] + j[0] = i[1] + j[1] или i[0] - j[0] = i[1] - j[1].
Например, следующая расстановка не корректна:
...
x+o
.+.
Средний ряд содержит пару моделей (x и o), ни одна из которых не равна +. Диагональ начинающаяся в + в нижней строке и идущая к o в среднем ряду содержит две модели, ни одна из которых не равна x.
Однако следующая расстановка является допустимой. Ни строка, ни столбец, ни диагональ не противоречат правилам.
+.x
+x+
o..
Ваш художественный консультант уже поместил m моделей в определенные ячейки, следуя этим правилам. Вы можете разместить любое количество (включая ноль) дополнительных моделей любого типа, который вам нравится. Вы не можете удалять существующие модели, но можете модернизировать столько существующих моделей + и x до моделей o, сколько пожелаете, если вышеупомянутые правила не нарушены.
Ваша задача - найти легальный способ размещения и / или обновления моделей, который получит максимально возможное количество очков стиля.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Далее следуют t тестов. Каждый тест начинается строкой из двух целых чисел n (1 ≤ n ≤ 100) и m (0 ≤ m ≤ n^2). Далее следуют m строк; i-ая строка содержит символ +, x или o (тип модели) и два целых числа r[i] и c[i] (позицию модели). Строки сетки пронумерованы с 1 до n сверху вниз. Колонки сетки пронумерованы с 1 до n слева направо.
Выходные данные
Для каждого теста сначала выведите одну строку, содержащую Case #x: y z, где x - номер теста (начиная с 1), y - количество очков стиля, заработанные Вашим расположением, z - общее количество моделей, которые Вы добавили и / или заменили. Затем для каждой модели, которую вы добавили или заменили, выведите ровно одну строку в том же формате в каком они заданы на входе, где символ - это тип модели, которую Вы добавили или заменили. Выводить z строк можно в любом порядке.
Если существует несколько допустимых ответов, выведите любой из них.