Електричні потреби#3749
Ви плануєте збудувати новий завод у своєму місті. Оскільки ваші потреби в електроенергії значні, важливо розташувати завод поблизу електростанції. Ви хочете створити пріоритетний список можливих місць для будівництва.
Область, де потрібно розмістити завод, можна уявити у вигляді прямокутної сітки з рядків і стовпців. Деякі з цих клітинок містять електростанцію. Новий завод займатиме рівно одну клітинку і може бути розміщений у будь-якій порожній клітинці (тобто в клітинці, яка не містить електростанцію).
Нумеруючи рядки від до і стовпці від до , розташування клітинки можна описати двома цілими числами. Клітинка знаходиться в рядку і стовпці . Відстань між клітинкою (i_0, j_0) і клітинкою (i_1, j_1) визначається як \max(|i_0 - i_1|, |j_0 - j_1|), де означає абсолютне значення . Електричний пріоритет місця - це його мінімальна відстань до електростанції.
Ви пронумеруєте всі можливі місця послідовними цілими числами, починаючи з , у порядку зростання електричного пріоритету. Серед місць з однаковим електричним пріоритетом ви пронумеруєте їх у порядку зростання номерів рядків. Серед місць з однаковим електричним пріоритетом і номером рядка ви розташуєте їх у порядку зростання номерів стовпців.
На наступному малюнку показано сітку 4 \times 7. Чорні клітинки - це клітинки з електростанціями. Темно-сірі клітинки мають електричний пріоритет , світло-сірі - електричний пріоритет , а білі - електричний пріоритет . Число всередині кожної клітинки - це номер, присвоєний вами місцю.
Ви отримаєте кілька запитів щодо побудованого пріоритетного списку. У кожному запиті вам буде надано число, що представляє позицію в пріоритетному списку, і ви повинні визначити, якому місцю було присвоєно цю позицію.
Кожен тестовий випадок задається кількома рядками. Перший рядок містить три цілі числа , і , що представляють кількість рядків і стовпців сітки (1 \le N, M \le 10^9) і кількість існуючих електростанцій (1 \le P \le 20). Кожен з наступних рядків містить два цілі числа і , що представляють номери рядка і стовпця розташування електростанції (1 \le R \le N і 1 \le C \le M). У межах кожного тестового випадку всі місця розташування електростанцій різні. Наступний рядок містить одне ціле число , що представляє кількість запитів (1 \le Q \le 50). Потім слідує рядок з цілими числами p_1, \ldots, p_Q, що представляють позиції в пріоритетному списку (1 \le p_i \le N \times M - P).
Останній тестовий випадок супроводжується рядком, що містить три нулі.
Для кожного тестового випадку виведіть Q+1 рядків. Рядок з перших рядків повинен містити два цілі числа, що представляють номери рядка і стовпця місця, якому було присвоєно номер p_i. Останній рядок для кожного тестового випадку повинен містити один символ '-' (дефіс).
Приклад 1