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