题目描述

After being stationed on Hoth, you’ve decided that this is the worst decision you have ever made. The planet is cold, there is nothing to do, and to make matters worse, the Empire keeps sending probe droids down to see if anyone is hiding on the planet. At least you can do something about the probe droids!

The field near your base is covered with these droids in a uniform fashion. Your base has a turret in the southwest (bottom-left) corner of the field, at location $(1, 1)$. Each remaining lattice point (points with integer coordinates) on the grid of $n \times m$ points contains a droid.

An example $3 \times 5$ grid:

:::align{center} :::

Note that row 1 is at the bottom, row $n$ is at the top, column 1 on the left and column $m$ on the right.

Your base is at coordinate $(1, 1)$, while the droids are at all positive coordinates in the range $(1\dots n, 1\dots m)$, excluding $(1, 1)$ of course. Your base has a turret on it facing east, towards higher-number columns in row 1. You’ve programmed the turret to operate in the following way: If a droid is its line of sight, then destroy the droid. Otherwise, rotate counter-clockwise until the turret can see a droid. Keep going until all droids are destroyed.

Your task is to figure out the $i^{\text{th}}$ droid destroyed when the turret executes your algorithm.

输入格式

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with three integers $n$, $m$ ($1 \leq n, m \leq 10^6$, $m$ and $n$ cannot both be 1) and $q$ ($1 \leq q \leq 100$), where the grid has $n$ rows and $m$ columns, and there will be $q$ queries to answer. Each of the next $q$ lines will have a single integer $i$ ($1 \leq i < n \times m$), which is a query for the $i^{\text{th}}$ droid destroyed.

输出格式

Output $q$ lines, corresponding to the $q$ queries in order. For each query, output two integers $r$ and $c$, separated by a single space, which represent the row ($r$) and column ($c$) of the $i^{\text{th}}$ droid destroyed.

3 5 3
1
14
8

1 2
3 1
3 5