你即将举办一场时装秀，以展示三种新的服装风格。秀场位于一个形状最时髦的区域：一个 $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 模型。

你的任务是找到一种合法的放置和/或升级模型的方法，以获得尽可能多的风格点。

输入格式

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

输出格式

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

如果有多个有效的答案，你可以输出其中任何一个。

样例

样例输入 1

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

样例输出 1

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

说明

样例输出展示了针对样例测试用例的一组答案。其他答案也可能是可能的。注意，最后一个样例测试用例不会出现在小型数据集中。

在样例 #1 中，网格是 2-by-2 的，初始为空。输出对应于以下网格。（在这些解释中，我们使用 . 表示空白单元格。）

x.
+o

在样例 #2 中，唯一的单元格已经被一个 o 模型占据，无法添加新模型或替换该 o 模型。

在样例 #3 中，放置任何模型之前，网格如下所示：

...
+++
x..

输出对应于此网格：

.x.
++o
x..