T539574 ”Minceraft“的合成系统
题目背景
> You should try our sister game, Minceraft!
*2025/11/19：本题原本有两个测试点的标准答案有误，现已修改*
小 B 是一个十分熟悉 Java 语言的 Minceraft Modder，他喜欢研究风靡全球的沙盒游戏 Minceraft 中的各种机制。而现在他把目光投向了 Minceraft 中的合成系统。
*合成（Crafting）是一种在 Minceraft 中获得多种方块、工具和其他资源的方法。合成时，玩家必须先把物品从物品栏移入合成方格中。2×2的简易合成方格可以直接在物品栏中找到，而3×3的合成方格需要使用工作台或合成器来打开。 ——Minceraft Wiki*
题目描述
合成系统是沙盒游戏 Minceraft 中的一个重要组成部分。在 Minceraft 中，可用的合成配方分为两种。为了使用合成配方进行合成，我们需要用到**合成方格（Crafting Grid）**，合成方格是一个使用可能的合成配方子集进行一些基础合成的方式，在 Minceraft 中，合成方格既可以是正方形，也可以是长与宽不相等的长方形。
以下是对两种合成配方的介绍：
- 对于一些物品的合成，其原材料的排放位置无关紧要。这些配方称为**无序配方（Shapeless Recipes）**。其原材料可以**随意放置在合成方格中任何地方**。
- 但是，许多重要的配方要求原材料**以一定规律排列**，这些配方称为**有序配方（Shaped Recipes）**。不过，在原材料之间的相对位置保持不变的情况下，**原材料排列的整体可以在合成方格内随意移动**。例如，一个3×1的配方，其原材料可以排在3×3合成方格的最顶行、中间行或最底行，但却不能在2×2合成方格中合成，因为这种方格不能提供三个横排的位置。注意这种“有序配方”的位置虽然可以平移，但是**不可以上下或左右镜像翻转，也不可以以任意角度旋转**。
下面是一个无序配方的例子：
在这个无序配方中，我们用末影水晶与烈焰粉合成了一个末影之眼。使用这个无序配方进行合成时，合成方格上末影水晶与烈焰粉的位置可以任意改变。
下面是一个有序配方的例子：
在这个有序配方中，我们用三根木棍和三条线合成了一把弓。注意使用这个有序配方进行合成时，合成方格上三根木棍和三条线的位置是不能改变的。同时，在图中的三个空方格上不能摆放任何物品。
另外，在任意一个配方中，**每个原材料可以对应着不止一个物品**。比如在合成火把的有序配方中，可以使用木棍和煤炭进行合成，就像下面这样：
也可以使用木棍和木炭进行合成，就像下面这样：
同时，**所有 Minceraft 中的合成配方都只会合成出1个物品，而且合成结果有可能也被包含在合成配方中**（~~虽然第二点肯定是“亏本”的，但在 Minceraft 中你不需要在意那么多~~），这两点与 Minecraft 是不完全一样的。在上面的例子中，我们只会得到1个火把，而在 Minecraft 中使用类似的配方可以得到4个火把。
现在我们有 $C$ 个可用的合成配方和 $T$ 个合成方格，我们需要对于每个合成方格，输出该合成方格对应的合成结果。如果没有可用的合成配方，则输出 `air` ，如果在一个合成方格中同时满足多个合成配方的原材料要求，则按照字典序输出所有合成结果。
小 B 只会 Java 语言，但 Java 程序的速度实在是太慢了。于是他请求你使用 C++ 语言来帮助他快速解决上面的问题。
输入格式
第一行包含一个整数 $C$ ,表示共有 $C$ 个可用的合成配方。
接下来若干行，分别描述所有的合成配方。在描述每个配方前，会有一个整数 $p$ 来表示这是哪一种配方。如果 $p = 1$ ，那么下面将会描述一个**有序配方**，如果 $p = 2$，那么下面将会描述一个**无序配方**。
对于第 $i$ $( 1 \le i \le C) $ 个配方，如果它是有序配方，将会以如下的形式进行描述：
*第一行共有3个整数 $x_i, y_i, z_i$ 和一个字符串 $w_i$ ，表示该有序配方共有 $x_i$ 行 $y_i$ 列，共包含 $z_i$ **种**不同的原材料，且合成结果为名称为 $w_i$ 的物品。*
*接下来有 $x_i$ 行描述整个配方，每行共有 $y_i$ 个字符。这 $x_i$ 行中每种不同的字符分别代表着一种原材料。*
*然后有 $z_i$ 行，第 $j$ $( 1 \le j \le z )$ 行共有一个字符 $k_j$ ，一个整数 $s_j$ 和 $s_j$ 个字符串，表示第 $j$ 种原材料。其中 $k_j$ 代表着上面配方中相应字符的位置表示这种原材料（数据保证 $k_1$ 到 $k_z$ 不重不漏地表示了配方中出现过的所有字符）， $s_j$ 表示这种原材料对应的物品数，后面 $s_j$ 个字符串表示所有可行的物品的名称。*
***有序配方中每种原材料可能有不止1个**，比如弓的配方中有3根木棍，“木棍”这种原材料有3个。*
而如果第 $i$ $( 1 \le i \le C )$ 个配方是无序配方，将会以如下的形式进行描述：
*第一行共有1个整数 $z_i$ 和一个字符串 $w_i$ ，表示该无序配方共包含 $z_i$ **个**不同的原材料，且合成结果为名称为 $w_i$ 的物品。*
*然后有 $z_i$ 行，第 $j$ $( 1 \le j \le z )$ 行共有一个整数 $s_j$ 和 $s_j$ 个字符串，表示第 $j$ 个原材料。其中 $s_j$ 表示这个原材料对应的物品数，后面 $s_j$ 个字符串表示所有可行的物品的名称。*
注意**有序配方中原材料可能是空气**（空气的物品名称一定为 `air` ，起到占位符的作用），而**无序配方中原材料不可能是空气**，并且**多个不同的配方可能拥有相同的合成结果**。
举个例子，以下7行描述了弓的有序配方：
```text
3 3 3 bow
.#I
#.I
.#I
. 1 air
# 1 stick
I 1 string
```
以下5行描述了火把的有序配方：
```
2 1 2 torch
O
I
O 2 coal charcoal
I 1 stick
```
而以下3行描述了末影之眼的无序配方：
```
2 ender_eye
1 ender_pearl
1 blaze_powder
```
所有合成配方都描述完后的下面一行，会有一个整数 $T$ ，表示共有 $T$ 个合成方格。
接下来若干行，分别描述所有的合成方格。第 $i$ 个合成方格共用 $n_i $ 行，每行 $m_i$ 个字符串来描述。第 $j$ $( 1 \le i \le n_i)$ 行第 $k$ $( 1 \le k \le m_i)$ 个字符串表示合成方格上第 $j$ 行第 $k$ 列的物品的名称，如果该位置上没有物品，则字符串为 `air` 。
输出格式
共 $T$ 行，第 $i$ 行代表第 $i$ 个合成方格的合成结果。
说明/提示
### 样例解释
对于第1个合成方格， `bcd` 符合物品 `zzzz` 的合成配方中的第一个原材料，而 `abc` 符合第二个原材料，因此可以合成出 `zzzz`，而该合成方格不符合其余任何合成配方。
对于第2~4个合成方格，分别符合且仅符合 `bow` ， `torch` 和 `eye` 的合成配方。
对于第5个合成方格，里面的物品看似符合 `torch` 的合成配方，但实际上下面多了一根木棍，所以什么都合成不出来，因此输出 `air`。
### 数据范围
对于全部数据， $1 \le C, T \le 100$ ， $1 \le n_i, m_i, x_i, y_i \le 10$ ， $1 \le z_i \le 10 $， $1 \le s_j \le 10 $， $p \in \{1, 2\}$ ， $k_i$ 为 `#` 、 `.` 或26个大写字母。
| 测试点 | 特殊性质 |
| :----------: | :----------: |
| $1 \sim 2$ | A、C、D |
| $3$ | B、C、D |
| $4 \sim 5$ | A、C |
| $6$ | B、C |
| $7 \sim 8$ | A、D |
| $9$ | B、D |
| $10 \sim 12$ | A |
| $13 \sim 14$ | B |
| $15 \sim 16$ | C |
| $17 \sim 20$ | 无 |
特殊性质 A：没有无序配方；
特殊性质 B：没有有序配方；
特殊性质 C：每个原材料只对应一个物品，即 $s_j = 1$；
特殊性质 D：总共只有一个可用的配方，即 $C = 1$。
保证数据中出现的所有字符串由小写字母组成且长度都小于等于10，且所有合成配方的合成结果都不为 `air`。