Problem B
Enumerating Pairs

An important concept in set theory is the idea of enumerating (listing) the elements of an infinite set. When a set is countable, then the items in that set are enumerable by some program.

Natural Numbers

For example, the set of natural numbers (all positive integers) is infinite, and countable, and therefore enumerable. We could imagine an loop that enumerates the natural numbers like this:

i = 1
while True:
    print(i)
    i = i + 1

This loop would never finish running, but it has a nice property: given any natural number $x$ (which could be very large), the loop would eventually output $x$ (if it were allowed to run long enough).

Pairs of Natural Numbers

For this problem, we’ll move beyond the natural numbers to enumerate another infinite (but countable) set: pairs of natural numbers. Your program should print these pairs, similar to the way the above loop prints the natural numbers. Let’s try adapting the loop above for pairs:

i = 1
while True:
    j = 1
    while True:
        print(i, j)
        j = j + 1
    i = i + 1

This initially appears to work like the earlier loop, but it has a significant flaw. Can you see what it is? (Here’s a hint: can you think of a pair of numbers that it would not be able to print?)

While your program should not run forever (like the loops above do), you should design it so that if it were allowed to run long enough, it would be able to eventually output any specified pair $(x, y)$, which again, could have very large values. This is the same as the property mentioned above for the natural numbers.

How Your Program is Evaluated

To make the problem a little more interesting, your program will be given three values $A$, $B$, and $C$. The values $A$ and $B$ form lower bounds on the pair values; every pair $(x, y)$ that your program produces should have the properties $A \le x$ and $B \le y$.

Further, we need to define one more property. We say that a pair $(x, y)$ is supported if any of the following are true:

• $x = A$ and $y = B$, or

• $x = A$ and $(x, y - 1)$ is supported, or

• $y = B$ and $(x - 1, y)$ is supported, or

• $(x - 1, y)$ is supported and $(x, y - 1)$ is supported.

Given $A$, $B$, and $C$, your program’s output is considered correct if it outputs only pairs that are all unique and includes the supported pair $(A+C,B+C)$. For example, if $A=1$ and $B=7$ and $C=2$, then your program should output unique pairs that includes the supported pair $(3,9)$.

With some reasoning, we can show that if the program is able to produce supported pairs in this way, then if we allow it to run long enough (using a large enough $C$), it would eventually print any arbitrary pair.

Input

The input is a single line with three integers: $A$, $B$, and $C$, separated by single spaces. These values correspond to the variables defined above.

Output

Output unique supported pairs of natural numbers. The numbers in the output should be separated by whitespace. The order of the pairs is not important.

Scoring

Your program will be tested on a set of test groups, each of which is worth a number of points. Each test group contains several test cases, and to receive the points for a test group your program must solve all of the test cases in that group. The score of your program is the sum of the points received on all of the test groups.

1 7 2

1 10
1 7
1 11
2 9
1 9
3 9
3 8
2 10
1 8
2 8
5 7
4 7
3 7
4 8
2 7