UPD 1: Add the application to automatic draw the rectangle.

Overview

This problem is a varient of the classic problem, "Packing rectangles with the smallest area rectangle.". This is also an optimization with you may not find the most optimal solution but the more rectangles you can place, the more score you get.

In this problem, given the size of the main rectangle and the size of others rectangles, find the maximum number of rectangle could be place in the main rectangle without overlapping the other rectangle ( note: these rectangles must be inside the main rectangle — but it can be touch in the borders of the main rectangle).

Input

The first line contains three integers n, m and k (1 ≤ n, m ≤ 100, 1 ≤ k ≤ 1000) — the height, the width of the fixed rectangle and the number of rectangles to be placed.

The next k lines have two integers x_i and y_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m) — the height and the width of the rectangle, remember that we can't rotate these rectangles.

Output

The first line of the ouput print k.

The next k line print two number x_j and y_j is the top — left point where the rectangle j placed. In case we don't place this rectangle, print "0 0" (without quotes).

Sample input

8 7 10
4 5
4 2
2 3
1 1
1 1
1 2
1 5
5 1
6 1
2 1

Sample output

10
1 1
5 1
5 3
1 6
7 3
7 4
8 3
1 7
2 6
6 7

Illustration

Picture for sample test case

Illustration application

Using the application

To use the application, you run your code to make a new ".exe" file (it must be in same folder with the input test). After that, upload the test input by clicking the button "Load input file...". Finally, click the button "Run external solution ..." and chose your ".exe" file.

P/s: Hope you to help with problem in case we want to maximize the area be covered. I just think of the brute force solution and some of the trival greedy approachs.