Задача G. Сад пермского периода ≡
| Автор: | Жюри ROI-2011 | Ограничение времени: | 3 сек | |
| Входной файл: | garden.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | garden.out | |||
| Максимальный балл: | 100 |
Условие
Оранжерея “Сад пермского периода” представляет собой прямоугольный участок для выращивания растений пермского периода. Оранжерея была разбита дорожками на квадраты. В центре каждого квадрата посажено одно растение. Размер квадрата зависит от корневой системы растения.
За год дорожки заросли травой, что затруднило уход за оранжереей. Чтобы при садовых работах не повредить корневую систему какого-либо растения, по имеющемуся расположению растений необходимо восстановить размеры соответствующих им квадратов.
Введем декартову прямоугольную систему координат, начало которой совмещено с левым нижним углом оранжереи. Ось Ox направлена вдоль нижней границы участка, ось Oy – вдоль левой. Изначально дорожки были проложены параллельно осям координат. Единичный отрезок удалось выбрать так, что координаты углов каждого из квадратов оказались целыми.
Требуется написать программу, которая по размеру оранжереи и координатам растений определит размеры соответствующих им квадратов.
Формат входного файла
В первой строке входного файла записаны три натуральных числа: W – ширина оранжереи, H – длина оранжереи и N – количество посаженых растений. В каждой из следующих N строк расположены по два числа: xi, yi – координаты i-го растения (0 < xi < W, 0 < yi < H). Гарантируется, что соответствующие растениям квадраты имеют целую длину стороны и покрывают всю оранжерею.Формат выходного файла
В выходной файл необходимо вывести N целых чисел – размеры квадратов, соответствующих растениям. Числа требуется вывести в порядке описания растений во входном файле.Ограничения
W, H ≤ 1012;
N ≤ 2 × 105;
Примеры тестов
| № | Входной файл (garden.in) |
Выходной файл (garden.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|