Description

你即将举办一场时装秀，展示三种新款服装。秀场的舞台是最时尚的形状：一个 $N \times 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 型，只要不违反上述规则。

你的任务是找到一种合法的放置和/或升级方式，使得获得的风格分最大。

Input Format

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试数据。每组测试数据的第一行包含两个整数 $N$ 和 $M$。接下来 $M$ 行，每行包含一个字符（+、x 或 o）和两个整数 $R_i$、$C_i$，表示该模特的类型和位置。网格的行从上到下编号为 $1$ 到 $N$，列从左到右编号为 $1$ 到 $N$。

Output Format

对于每个测试用例，首先输出一行 Case #x: y z，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你安排下获得的风格分，$z$ 是你添加和/或替换的模特总数。然后，对于每一个你添加或替换的模特，输出一行，格式与输入部分相同，字符为你添加或替换的模特类型。这 $z$ 行顺序不限。

如果有多种合法方案，你可以输出其中任意一种。

3
2 0
1 1
o 1 1
3 4
+ 2 3
+ 2 1
x 3 1
+ 2 2

Case #1: 4 3
o 2 2
+ 2 1
x 1 1
Case #2: 2 0
Case #3: 6 2
o 2 3
x 1 2

Hint

样例说明

样例输出展示了样例数据的一组解。其他解也是可能的。注意最后一个样例不会出现在 Small 数据集中。

在样例 1 中，网格为 $2 \times 2$，初始为空。输出对应如下网格（用 . 表示空格）：

x.
+o

在样例 2 中，唯一的格子已经被 o 型模特占据，无法再添加或替换模特。

在样例 3 中，初始网格如下：

...
+++
x..

输出对应如下网格：

.x.
++o
x..

数据范围

• $1 \leq T \leq 100$。
• $1 \leq N \leq 100$。
• $1 \leq C_i \leq N$，对所有 $i$。
• $0 \leq M \leq N^2$。
• 不会有两个预放置的模特在同一格子。
• 保证所有预放置的模特均符合规则。

小数据（10 分，测试集 1 - 可见）

• $R_i = 1$，对所有 $i$。（所有预放置的模特都在第一行。你可以在该行添加/替换模特，也可以在其他行添加模特。）

大数据（25 分，测试集 2 - 隐藏）

• $1 \leq R_i \leq N$，对所有 $i$。

由 ChatGPT 4.1 翻译