I. 悄悄搬家具

Hasty Haul

时间限制：3 秒 · 内存限制：1024 MiB

原题：NWERC 2025 H · 查看官方英文原文（英文 PDF 也已作为本题附件提供）

题目描述

两个队伍想在一个 $h$ 行 $w$ 列的房间中恶作剧。房间里恰有 $k$ 件家具，每件家具占据一个格子，其余格子为空。每个队伍到达时，只来得及把一件家具从当前格子搬到一个空格子。

两个队伍必须事先约定同一个策略：当看到相同的房间布局时，都必须做出相同的移动。他们不知道彼此到达的先后，之后也不能再通信。两次到达之间不会有其他人移动家具。

他们希望，无论初始布局是什么，后到的队伍都能恰好撤销先到队伍的操作，使所有家具恢复原位。你的任务是实现这样的统一策略；如果对于给定的 $h$ 、 $w$ 、 $k$ ，不存在能覆盖所有布局的策略，则输出 risky。

本题为多轮运行题（multi-pass）。评测器会多次启动你的程序，次数可能多于两次。后续运行中的输入及测试数量可能取决于此前的输出。对同一个布局的决策必须在同一次运行和不同次运行之间保持一致，不能依赖随机选择或仅在单次运行中保存的状态。官方本地测试工具随题目附件提供。

每次程序启动时，第一行包含测试数量 $t$ （ $1 \leq t \leq 10000$ ）。

每组测试首先给出 $h$ 、 $w$ 、 $k$ （ $1 \leq h, w \leq 8$ ， $1 \leq k < h\cdot w$ ）。随后 $h$ 行，每行 $w$ 个字符：. 表示空格子，# 表示家具。

保证每个布局中恰好有 $k$ 件家具，且至少存在一个空格子。

对每组测试，如果不存在适用于给定 $h$ 、 $w$ 、 $k$ 的所有布局的合法统一策略，输出 risky。

否则输出两行：第一行输出 $r_{1}$ 、 $c_{1}$ ，第二行输出 $r_{2}$ 、 $c_{2}$ ，表示将 $(r_{1}, c_{1})$ 的家具移到空格子 $(r_{2}, c_{2})$ 。行、列编号均从 $1$ 开始。

对于你输出移动后的布局，再按完全相同的策略执行一次，必须使布局恢复到本次输入时的状态。

3
1 4 2
.#.#
4 4 8
..#.
###.
..##
.#.#
1 3 1
.#.

1 4
1 1
4 4
4 1
risky

2
1 4 2
##..
4 4 8
..#.
###.
..##
##..

样例含多轮输入。中文题面下方的第一轮样例来自官方题包；第二轮的完整示例及本地测试说明请同时查看附带的官方英文原文和测试工具。

原题版权归原作者及相应赛事评委会所有，采用 CC BY-SA 4.0 许可。中文译文为本练习赛整理，按相同许可发布。题号及中文标题作了调整，输入约束、样例和判题要求依照官方原题；图示及完整英文叙述请参阅英文原文附件。