Maximizing Non-overlapping Flower Patches

In this problem, you are given a rectangular garden with a width (W) and a length (L). Additionally, there are (N) different flower patch types, each with its own rectangular dimensions. Each patch can be placed in the garden in either of two orientations: with its given width along the garden's width (horizontal placement) or by rotating it 90° (vertical placement). Your task is to calculate, for each patch type, the maximum number of patches that can be placed in the garden without overlapping any other patch, given the two possible orientations.

For each patch type with dimensions (w_i) and (l_i), the number of patches that can fit in the garden when placed horizontally is given by: [ \left\lfloor \frac{W}{w_i} \right\rfloor \times \left\lfloor \frac{L}{l_i} \right\rfloor ]

Similarly, if the patch is rotated (vertical placement), the number is: [ \left\lfloor \frac{W}{l_i} \right\rfloor \times \left\lfloor \frac{L}{w_i} \right\rfloor ]

For each patch type, you should choose the maximum of the two possible numbers of patches that can be placed. Input details are provided below.

inputFormat

The input is read from standard input and consists of multiple numbers separated by spaces and/or newlines. The first two integers represent the width (W) and the length (L) of the garden. This is followed by an integer (N) which denotes the number of flower patch types. The next (N) lines each contain two integers (w_i) and (l_i), representing the dimensions of the (i)-th flower patch.

outputFormat

Print a single line on standard output consisting of (N) integers separated by a space. Each integer represents the maximum number of patches that can be placed in the garden for the corresponding flower patch type.## sample

5 4 1
2 1

10