Garden of the Permian

Greenhouse "Garden of the Permian period" is a rectangular area for growing plants of the Permian period. The greenhouse was divided into squares tracks. In the center of each square planted one plant. The size depends on the square root of the plant.

During the year the track overgrown with grass, making it difficult to care for the greenhouse. To work in the garden not to damage the root system of a plant at the existing location of the plant to restore the size of the corresponding squares.

We introduce a rectangular Cartesian coordinate system whose origin is combined with the left lower corner greenhouse. Ox axis is directed along the lower border of the plot, the axis Oy - along the left. Initially, the tracks were laid parallel to the coordinate axes. The unit interval was chosen so that the coordinates of the corners of each square were intact.

Required to write a program that the size of the greenhouse and the plants will determine the size of the coordinates of the corresponding squares.

Input

The first line of the input file contains three positive integers: W – width of the greenhouse, H – the length of the greenhouse and N – the number of planted trees. In each of the following N lines are located at two numbers: x_i, y_i – the coordinates of the i^th plant (0 < x_i < W, 0 < y_i < H; W, H ≤ 10^12; N ≤ 2×10^5). It is guaranteed that the corresponding squares of the plants have an entire length of the side and cover the entire greenhouse.

Output

The output file must take N integers - the size of the squares of the plants. The numbers in the order you want to display the description of plants in the input file.

Examples

Note

Greenhouse in the second example corresponds to the following figure