Электрические нужды
Вы собираетесь построить новый завод в вашем городе. Поскольку у вас высокие потребности в электроэнергии, важно, чтобы завод находился рядом с электростанцией. Вы хотите составить приоритетный список возможных местоположений.
Область, где должен быть построен завод, представлена в виде прямоугольной сетки размером N на M ячеек. Некоторые из этих ячеек содержат электростанции. Новый завод занимает ровно одну ячейку и может быть размещен в любой пустой ячейке (то есть в ячейке, которая не содержит электростанцию).
Рядки нумеруются от 1 до N, а столбцы — от 1 до M. Таким образом, местоположение ячейки можно описать двумя целыми числами. Ячейка (i, j) находится в рядке i и столбце j. Расстояние между ячейкой (i_0, j_0) и ячейкой (i_1, j_1) определяется как max(|i_0 − i_1|, |j_0 − j_1|), где |x| обозначает абсолютное значение x. Электрический приоритет местоположения — это его минимальное расстояние до ближайшей электростанции.
Вы пронумеруете все возможные местоположения последовательными целыми числами, начиная с 1, в порядке возрастания электрического приоритета. Если несколько местоположений имеют одинаковый электрический приоритет, они будут пронумерованы в порядке возрастания номеров рядков. Если и номера рядков совпадают, то они будут пронумерованы в порядке возрастания номеров столбцов.
На следующем рисунке представлена сетка 4×7. Черные ячейки содержат электростанции. Темно-серые ячейки имеют электрический приоритет 1, светло-серые — 2, а белые — 3. Число внутри каждой ячейки — это номер, присвоенный местоположению.
Вам будет дано несколько запросов о построенном приоритетном списке. В каждом запросе будет указано число, представляющее позицию в приоритетном списке, и вам нужно определить, какому местоположению соответствует эта позиция.
Входные данные
Каждый тестовый случай задается несколькими строками. Первая строка содержит три целых числа N, M и P, обозначающих количество рядков и столбцов сетки (1 ≤ N, M ≤ 10^9) и количество существующих электростанций (1 ≤ P ≤ 20). Каждая из следующих P строк содержит два целых числа R и C, обозначающих номера рядка и столбца местоположения электростанции (1 ≤ R ≤ N и 1 ≤ C ≤ M). Все местоположения электростанций в пределах одного тестового случая различны. Следующая строка содержит одно целое число Q, обозначающее количество запросов (1 ≤ Q ≤ 50). Затем следует строка с Q целыми числами p_1, ..., p_Q, представляющими позиции в приоритетном списке (1 ≤ p_i ≤ N×M−P).
Последний тестовый случай завершается строкой, содержащей три нуля.
Выходные данные
Для каждого тестового случая выведите Q+1 строк. Строка i из первых Q строк должна содержать два целых числа, обозначающих номера рядка и столбца местоположения, которому был присвоен номер p_i. Последняя строка для каждого тестового случая должна содержать один символ '-' (дефис).