P16132 [ICPC 2018 NAIPC] Probe Droids

被派驻到霍斯星球后，你认定这是你这辈子做过最糟糕的决定。这颗星球寒冷刺骨、百无聊赖，更糟的是，帝国还不断地派遣探测机器人降落到星球上，搜寻是否有藏匿人员。至少，你还能对探测机器人做点什么！ 基地附近的原野上均匀地分布着这些机器人。你的基地位于原野的西南角（左下角），坐标为 $(1, 1)$。$n \times m$ 网格上的其余整数坐标点都各有一个机器人。 一个 $3 \times 5$ 网格的例子： :::align{center}  ::: 注意，第 1 行在最下方，第 $n$ 行在最上方，第 1 列在左侧，第 $m$ 列在右侧。 你的基地位于坐标 $(1, 1)$，而机器人的位置是 $(1 \dots n, 1 \dots m)$ 范围内的所有正坐标点（当然，不包括 $(1, 1)$ 本身）。基地上有一座炮塔，朝向东（即第 1 行中列号增大的方向）。你为炮塔设定的运行方式如下：如果炮塔的视线方向上有机器人，则摧毁该机器人；否则，逆时针旋转炮塔，直到它能看到某个机器人。重复此过程，直到所有机器人被摧毁。 你的任务是确定在炮塔执行上述算法时，第 $i$ 个被摧毁的机器人是哪一个。

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个测试用例的第一行包含三个整数 $n$、$m$（$1 \leq n, m \leq 10^6$，且 $m$ 和 $n$ 不能同时为 $1$）和 $q$（$1 \leq q \leq 100$），其中网格有 $n$ 行 $m$ 列，并有 $q$ 个询问需要回答。接下来的 $q$ 行，每行包含一个整数 $i$（$1 \leq i < n \times m$），表示询问第 $i$ 个被摧毁的机器人。

输出 $q$ 行，按顺序对应每个询问。对于每个询问，输出两个整数 $r$ 和 $c$，之间用一个空格分隔，分别表示第 $i$ 个被摧毁的机器人的行坐标和列坐标。

翻译由 DeepSeek V3.2 完成