Problem C: Toroidal Chess Queens' Problem 

Problem

The toroidal M×N chess board is obtained from the usual M×N one in the same way as one obtains a torus from rectangle: by gluing together the upper side with the lower one and the left side with the right one. The arrow directions after the gluing should coincide. The figure below represents the toroidal chess desk 4×3:

So, shifting to the left from the very left column you get to the very right one. Shifting to the right from the very right column, you find yourself on the first one. In the same way, moving up from the top row, you arrive on the bottom one and moving down from the bottom row, you get to the top one.

Toroidal chess figures move in the same way, as the plain ones. In particular, the queen attacks any figure which is situated in the same row, column or diagonal.

The problem is to place K queens on the toroidal chess board so that no one will attack another.

Input

The input will consist of several lines. Each line contains three integers M, N and K, separated by space. Here M denotes number of board columns, N - number of board rows, K - number of queens to be placed. (1<=M,N,K<=14)

The input is terminated by <EOF>.

Output

For each input line the output should consist of solution representation. The position of every queen is placed in the separate line as a pair of two integers separated by space. The first integer denotes the column number (from 1 to M), the second - the row number (from 1 to N). If there is no solution for given M, N, K, you should output two zeroes in one line. If there are several solutions, you should output only one of them.

Sample Input

3 2 3
6 3 2

Sample Output

0 0
1 1
4 3






Alexander Denisjuk, 2002