Електричні потреби
Ви плануєте збудувати новий завод у своєму місті. Оскільки ваші потреби в електроенергії значні, важливо розташувати завод поблизу електростанції. Ви хочете створити пріоритетний список можливих місць для будівництва.
Область, де потрібно розмістити завод, можна уявити у вигляді прямокутної сітки з 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. Останній рядок для кожного тестового випадку повинен містити один символ '-' (дефіс).