Показ мод
Ви плануєте провести показ мод, щоб продемонструвати три нові стилі одягу. Шоу проходитиме на сцені у вигляді сітки розміром 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 рядків можна в будь-якому порядку.
Якщо існує декілька допустимих відповідей, виведіть будь-яку з них.