Дистанционный практикум по программированию

Задана прямоугольная область размером H пикселей в высоту и W в ширину. Её необходимо полностью заполнить в 1 ряд с помощью К изображений. Каждое изображение имеет свой размер H_i x W_i (высота и ширина) в пикселях. Размер любой картинки можно изменить так, чтобы пропорции сохранялись.

Пусть H_i и W_i - высота и ширина исходного изображения, H'_i и W'_i - размеры растянутого или сжатого изображения. Будем считать, что пропорции сохранены, если H'_i/W'_i отличается не более чем на 10% от H_i/W_i.

Изображения нельзя поворачивать. Все изображения должны быть задействованы, а прямоугольную область необходимо заполнить полностью, не выползая за её пределы. Ваша задача определить для каждой фотографии её новую ширину W'_i, так чтобы пропорции были сохранены, а область была заполнена полностью. Если ответов несколько, выведите любой.

Исходные данные

В первой строке входного файла содержатся 3 целых числа: H (1<=H<=10⁴), W (1<=W<=10⁹) и K (1<=K<=10⁵) - высота, ширина области и количество изображений.

В следующих К строках содержится по 2 целых числа, разделённых пробелом: H_i (1<=H_i<=10⁴) и W_i (1<=W_i<=10⁴) - высота и ширина i-й фотографии.

Результат

Выведите в выходной файл К целых чисел - ширину каждой фотографии в порядке, данном во вводе. Если ответов несколько, выведите любой. Если решения не существует, выведите одно число 0.

Пример

9 21 2
10 10
9 10

10 11

9 10 1
9 12

0