Problem: Displaying Paintings

Want to try solving this problem? You can submit your code online if you log in or register.

Displaying Paintings

Input File: paintin.txt
Output File: paintout.txt
Time Limit: 1.25 seconds

You are working part time in the art gallery. On of your jobs is to place paintings on a wall in the gallery. The gallery is rather short on space, and needs to pack the paintings tightly on a single wall in the gallery. Each painting and the wall itself has dimensions which are an integer number of millimeters.

There are some rules about where paintings can be placed:

Paintings must be placed with their sides parallel to the sides of the wall, and in the correct orientation.
Paintings cannot overlap - the patrons need to see the whole painting to appreciate it.
Paintings must be hung in the order they arrive.
Paintings must be placed as far to the left of the wall as possible when they are hung.
Paintings must be hung as low as possible, without breaking rule 4.

The x-coordinate of a painting is the distance (in millimeters) of the left edge of the painting from the left edge of the wall. The y-coordinate is the distance (in millimeters) of the bottom of the painting from the bottom of the wall.

Thus rule 4 says that paintings must be given the least x-coordinate possible when they arrive, and rule 5 says that paintings must be given the least y-coordinate possible which doesn't increase the x-coordinate.

Input

The first line of input shall contain two integers W and H, separated by a single space. These give the width and height (respectively) of the wall on which the paintings are to be hung, measured in millimeters.

Each following line of input shall contain two integers w_i and h_i, separated by a single space. These give the width and height (respectively) of the next painting to be hung, measured in millimeters.

The input shall be terminated by a line consisting of two 0s (zeroes) separated by a single space.

You are guaranteed that:

1 <= W <= 30,000
1 <= H <= 30,000
For each painting i, 1 <= w_i <= W.
For each painting i, 1 <= h_i <= H.
All paintings can be hung on the wall by following the rules.

Output

For each painting in the input (each line after the first), your program shall output a single line consisting of two integers x_i and y_i, separated by a single space. These give the x-coordinate and y-coordinate of the corresponding painting when placed according to the rules.

Sample Input

Sample Output

Scoring

For each test case, let n be the number of paintings to be placed. If your program correctly places r of the paintings for this case, it shall be awarded r/n of the available marks for the test case.