你是塞维利亚的园丁,是歌剧中的一个小角色。歌剧的背景是一个矩形的庭院,包含 $R$ 行 $C$ 列的单元格。你被要求在庭院中安装一个树篱迷宫:每个单元格必须包含一个对角线方向的树篱。对于任何单元格,有两种可能的树篱:从左下到右上(用 / 表示)和从左上到右下(用 \ 表示)。每当两个树篱接触时,它们就形成了一堵连续的墙。
庭院周围是一圈宽度为一个单元格的环,四个角缺失。这些外圈单元格中的每一个都是一位朝臣的住所。这些外圈单元格中的朝臣按顺时针方向编号,从顶行最左侧的单元格开始编号为 $1$,到左列最顶端的单元格结束,编号为 $2 \times (R + C)$。例如,对于 $R = 2, C = 2$,外圈的编号如下所示。(注意此时尚未添加任何树篱。)
1 2 8 3 7 4 6 5
在这部不同寻常的歌剧中,爱情是相互且排他的:每位朝臣恰好爱着另一位朝臣,而对方也只爱着他们。每位朝臣都希望能够穿过树篱迷宫到达他或她的爱人身边,而不遇到任何其他朝臣。也就是说,任何一对相爱的朝臣必须通过迷宫中的一条路径连接起来,且该路径与其他所有路径都被树篱墙隔开。迷宫中存在不属于任何朝臣路径的部分是可以的,只要所有爱人对都能连接起来即可。
给定一份谁爱谁的名单,你能否构建出满足条件的树篱迷宫,或者确定这是 IMPOSSIBLE(不可能的)?
输入格式
输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含一行,包含两个整数 $R$ 和 $C$,随后是一行包含从 $1$ 到 $2 \times (R + C)$ 的所有整数的排列。每个整数代表一位朝臣的编号;列表中的第一位和第二位朝臣相爱且必须连接,第三位和第四位朝臣相爱且必须连接,依此类推。
输出格式
对于每个测试用例,输出一行 Case #x:,其中 $x$ 是测试用例编号(从 $1$ 开始)。然后,如果无法满足条件,再输出一行 IMPOSSIBLE。否则,输出 $R$ 行,每行包含 $C$ 个字符,表示满足条件的树篱迷宫,其中每个字符为 / 或 \。你不能将迷宫中的任何单元格留空。如果存在多种可能的迷宫,你可以输出其中任意一个。
数据范围
$1 \le T \le 500$ $1 \le R \times C \le 100$
样例
样例输入 1
4 1 1 1 4 3 2 1 3 1 8 2 7 3 4 5 6 2 2 8 1 4 5 2 3 7 6 1 1 1 3 2 4
样例输出 1
Case #1: / Case #2: //\ Case #3: // \/ Case #4: IMPOSSIBLE
说明
在样例 3 中,以下朝臣对是爱人:$(8, 1), (4, 5), (2, 3), (7, 6)$。以下是样例输出的示意图:
对于样例 3,请注意这也是一个有效的迷宫:
/\ \/
在样例 4 中,庭院仅由一个单元格组成,因此围绕它的朝臣(从顶部开始顺时针读取)分别是 $1, 2, 3$ 和 $4$。在这个单元格中只有两种可能的选择:/ 或 \。第一种选择会形成从 $1$ 到 $4$ 以及从 $2$ 到 $3$ 的路径。第二种选择会形成从 $1$ 到 $2$ 以及从 $3$ 到 $4$ 的路径。然而,这两种选择都无法帮助我们陷入爱河的朝臣,因为在这种情况下,$1$ 爱 $3$,$2$ 爱 $4$。所以这种情况是 IMPOSSIBLE,歌剧将充满悲伤的咏叹调!