Показ мод#8694

Показ мод

1 секунда

128 мегабайтів

Легка

Ви плануєте провести показ мод, щоб продемонструвати три нові стилі одягу. Шоу проходитиме на сцені у вигляді сітки розміром $n$ на $n$ клітинок.

Кожна клітинка сітки може бути або порожньою (позначеною символом .), або містити одну модель. Моделі бувають трьох типів, залежно від стилю одягу: +, x і супер-модний o. Клітинка з моделлю + або x додає до шоу $1$ бал за стиль, а клітинка з моделлю o додає $2$ бали. Порожні клітинки не додають балів.

Для досягнення максимального художнього ефекту існують певні правила розміщення моделей:

Якщо дві моделі знаходяться в одному рядку або колонці, хоча б одна з них повинна бути +.
Якщо дві моделі знаходяться на одній діагоналі, хоча б одна з них повинна бути x.

Формально, модель у рядку $i_{0}$ i_0 і колонці $j_{0}$ j_0 та модель у рядку $i_{1}$ i_1 і колонці $j_{1}$ j_1 знаходяться в одному рядку, якщо $i_{0} = i_{1}$ i_0 = i_1, в одній колонці, якщо $j_{0} = j_{1}$ j_0 = j_1, і на одній діагоналі, якщо $i_{0} + j_{0} = i_{1} + j_{1}$ i_0 + j_0 = i_1 + 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 \leq t \leq 100$ 1 \le t \le 100). Далі йдуть $t$ тестів. Кожен тест починається з рядка, що містить два цілі числа $n$ ( $1 \leq n \leq 100$ 1 \le n \le 100) і $m$ ( $0 \leq m \leq n^{2}$ 0 \le m \le n^2). Далі йдуть $m$ рядків; $i$ -ий рядок містить символ +, x або o (тип моделі) і два цілі числа $r_{i}$ r_i і $c_{i}$ c_i (позицію моделі). Рядки сітки пронумеровані з $1$ до $n$ зверху вниз. Колонки сітки пронумеровані з $1$ до $n$ зліва направо.

Вихідні дані

Для кожного тесту спочатку виведіть один рядок, що містить Case #x: y z, де $x$ - номер тесту (починаючи з $1$ ), $y$ - кількість балів за стиль, зароблених вашим розташуванням, $z$ - загальна кількість моделей, які ви додали і/або замінили. Потім для кожної моделі, яку ви додали або замінили, виведіть рівно один рядок у тому ж форматі, в якому вони задані на вході, де символ - це тип моделі, яку ви додали або замінили. Виводити $z$ рядків можна в будь-якому порядку.

Якщо існує декілька допустимих відповідей, виведіть будь-яку з них.

Приклади

Приклад 1