Valera has got a rectangle table consisting of *n* rows and *m* columns. Valera numbered the table rows starting from one, from top to bottom and the columns – starting from one, from left to right. We will represent cell that is on the intersection of row *x* and column *y* by a pair of integers (*x*, *y*).

Valera wants to place exactly *k* tubes on his rectangle table. A tube is such sequence of table cells (*x*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">1</sub>), (*x*<sub class="lower-index">2</sub>, *y*<sub class="lower-index">2</sub>), ..., (*x*<sub class="lower-index">*r*</sub>, *y*<sub class="lower-index">*r*</sub>), that: 
 -  *r* ≥ 2; -  for any integer *i* (1 ≤ *i* ≤ *r* - 1) the following equation |*x*<sub class="lower-index">*i*</sub> - *x*<sub class="lower-index">*i* + 1</sub>| + |*y*<sub class="lower-index">*i*</sub> - *y*<sub class="lower-index">*i* + 1</sub>| = 1 holds; -  each table cell, which belongs to the tube, must occur exactly once in the sequence. 
Valera thinks that the tubes are arranged in a fancy manner if the following conditions are fulfilled: 
 -  no pair of tubes has common cells; -  each cell of the table belongs to some tube. 
Help Valera to arrange *k* tubes on his rectangle table in a fancy manner.
The first line contains three space-separated integers *n*, *m*, *k* (2 ≤ *n*, *m* ≤ 300; 2 ≤ 2*k* ≤ *n*·*m*) — the number of rows, the number of columns and the number of tubes, correspondingly.
import time, random

VAZIO = 0

NUMERO_CANOS = 15
NUMERO_LINHAS = 10
NUMERO_COLUNAS = 10

class Nodo(object):
    def __init__(self, estado, prof, custoEstimado):
        self.estado = estado
        self.prof = prof
        self.custoEstimado = custoEstimado
        self.tamCanos = [0]*NUMERO_CANOS
    def __eq__(self, other):
        return self.estado == other.estado
    def __cmp__(self, other):
        return cmp(self.custoEstimado, other.custoEstimado)
    def __lt__(self, other):
        return self.custoEstimado < other.custoEstimado
    def __hash__(self):
        return hash(self.estado)


def buscaBSM2(estadoInicial):
    nodoInicial = Nodo(estadoInicial, 0, 0)
    nodoInicial.custoEstimado = estimaCusto(nodoInicial.estado, nodoInicial.tamCanos)

    nodoAtual = nodoInicial

    nodosExplorados = 0
    
    while(1):
        nodosExplorados += 1
        
        sucessores = pegaSucessores(nodoAtual)
        ultimo = False
        
        if(len(sucessores) > 0):
            proximoNodo = min(sucessores)
        else:
            ultimo = True
            
        if(proximoNodo.custoEstimado >= nodoAtual.custoEstimado or ultimo):
            if(ehMeta(nodoAtual)):
                return nodoAtual, nodosExplorados
            else:
                nodoAtual = geraAleatorio()
        else:
            nodoAtual = proximoNodo

    return 0;

def ehMeta(nodo):
    if(nodo.prof >= NUMERO_LINHAS*NUMERO_COLUNAS):
        todosAdicionados = True
        for tam in nodo.tamCanos:
            if(tam < 2):
                todosAdicionados = False
                break
        if(todosAdicionados):
            return True

    return False

def geraAleatorio():
    estado = tuple([VAZIO])*NUMERO_LINHAS*NUMERO_COLUNAS
    posicoesLivres = list(range(0, NUMERO_LINHAS*NUMERO_COLUNAS))

    for n_cano in range(0, NUMERO_CANOS):
        i = random.randint(0, len(posicoesLivres)-1)
        pos = posicoesLivres[i]
        posicoesLivres.remove(pos)
    
        linha = pos//NUMERO_COLUNAS
        coluna = pos%NUMERO_COLUNAS

        estado = novoEstado((n_cano, 1), linha, coluna, estado)

    novoNodo = Nodo(estado, NUMERO_CANOS, 0)
    novoNodo.tamCanos = [1]*NUMERO_CANOS
    novoNodo.custoEstimado = estimaCusto(estado, novoNodo.tamCanos)

    return novoNodo

def estimaCusto(estado, tamCanos):
    canosColocados = sum(tamCanos)
    numeroCanos = len(tamCanos)
    
    espacosVazios = NUMERO_LINHAS*NUMERO_COLUNAS - canosColocados

    custoEstimado = espacosVazios
    
    for tam in tamCanos:
        if(tam < 2):
            custoEstimado += 1

    if(espacosVazios < (numeroCanos - canosColocados)*2):
        custoEstimado += NUMERO_LINHAS*NUMERO_COLUNAS*2
    
    return custoEstimado
        
def pegaSucessores(nodo):
    sucessores = []

    estado = nodo.estado
    tamCanos = nodo.tamCanos

    for n_cano in range(0, NUMERO_CANOS):
        if(tamCanos[n_cano] == 0):
            for i in range(0, len(estado)):
                if(estado[i] == VAZIO):
                    lista = list(estado)
                    lista[i] = (n_cano, 1)
                    
                    copiaTam = tamCanos.copy()
                    copiaTam[n_cano] += 1
                        
                    novoNodo = Nodo(tuple(lista), nodo.prof + 1, estimaCusto(estado, copiaTam))
                    novoNodo.tamCanos = copiaTam
                    
                    sucessores.append(novoNodo)
        else:
            pontaCano = (n_cano, tamCanos[n_cano])
            linha, coluna = pegPos(pontaCano,estado)
            
            ##baixo
            if(linha > 0):
                l = linha - 1
                c = coluna
                if(estado[l*NUMERO_COLUNAS + c] == VAZIO):
                    novaPonta = (n_cano, tamCanos[n_cano] + 1)
                    
                    copiaTam = tamCanos.copy()
                    copiaTam[n_cano] += 1
                        
                    novoNodo = Nodo(novoEstado(novaPonta, l, c, estado), nodo.prof + 1, estimaCusto(estado, copiaTam))
                    novoNodo.tamCanos = copiaTam
                    
                    sucessores.append(novoNodo)

            ##cima
            if(linha < (NUMERO_LINHAS-1)):
                l = linha + 1
                c = coluna
                if(estado[l*NUMERO_COLUNAS + c] == VAZIO):
                    novaPonta = (n_cano, tamCanos[n_cano] + 1)

                    copiaTam = tamCanos.copy()
                    copiaTam[n_cano] += 1
                        
                    novoNodo = Nodo(novoEstado(novaPonta, l, c, estado), nodo.prof + 1, estimaCusto(estado, copiaTam))
                    novoNodo.tamCanos = copiaTam
                    
                    sucessores.append(novoNodo)

            ##esquerda
            if(coluna > 0):
                l = linha
                c = coluna - 1
                if(estado[l*NUMERO_COLUNAS + c] == VAZIO):
                    novaPonta = (n_cano, tamCanos[n_cano] + 1)

                    copiaTam = tamCanos.copy()
                    copiaTam[n_cano] += 1
                        
                    novoNodo = Nodo(novoEstado(novaPonta, l, c, estado), nodo.prof + 1, estimaCusto(estado, copiaTam))
                    novoNodo.tamCanos = copiaTam
                    
                    sucessores.append(novoNodo)

            ##direita
            if(coluna < (NUMERO_COLUNAS-1)):
                l = linha
                c = coluna + 1
                if(estado[l*NUMERO_COLUNAS + c] == VAZIO):
                    novaPonta = (n_cano, tamCanos[n_cano] + 1)

                    copiaTam = tamCanos.copy()
                    copiaTam[n_cano] += 1
                        
                    novoNodo = Nodo(novoEstado(novaPonta, l, c, estado), nodo.prof + 1, estimaCusto(estado, copiaTam))
                    novoNodo.tamCanos = copiaTam
                    
                    sucessores.append(novoNodo)
        

    return sucessores

def pegPos(item, estado):
    try:
        posArray = estado.index(item)
        linha = posArray//NUMERO_COLUNAS
        coluna = posArray%NUMERO_COLUNAS
        return(linha, coluna)
    except:
        return (-1,-1)

def novoEstado(item, linha, coluna, estado):
    lista = list(estado)
    lista[linha*NUMERO_COLUNAS + coluna] = item
    return tuple(lista)
  
def naoRepete(estado, pai):
    if(pai.prof == 0 and estado != pai.estado):
        return True
    
    if(estado == pai.estado):
        return False
    
    if(naoRepete(estado, pai.pai)):
        return True
        
def posicoesCanos(nodo):
    listaPosicoes = []
    
    for i in range(0, len(nodo.tamCanos)):
        posicoes = []
        
        for n in range(1, nodo.tamCanos[i] + 1):
            pos = pegPos((i, n), nodo.estado)
            posicoes.append((pos[0]+1, pos[1]+1))
            
        listaPosicoes.append(posicoes)

    return listaPosicoes

            
## Main
entrada = input()
entrada = entrada.split(" ")

NUMERO_LINHAS = int(entrada[0])
NUMERO_COLUNAS = int(entrada[1])
NUMERO_CANOS = int(entrada[2])

estadoInicial = tuple([VAZIO])*NUMERO_LINHAS*NUMERO_COLUNAS
tempo = time.time()
nodoObtido, nodosExplorados = buscaBSM2(estadoInicial)

try:

    for i in range(0, len(nodoObtido.tamCanos)):
        imprimir = str(nodoObtido.tamCanos[i])
        
        for n in range(1, nodoObtido.tamCanos[i] + 1):
            pos = pegPos((i, n), nodoObtido.estado)
            imprimir += " " + str(pos[0]+1) + " " + str(pos[1]+1)

        print(imprimir)
except:
    print("### problema ###")
