SPOJ Brasil

Todo ano, para garantir a saúde e o bem-estar de seus súditos, o Rei da Nlogônia exige que todos os seus cidadãos façam um exame anual de saúde. Este ano, o médico da família real observou que o Bispo da Nlogônia estava obeso, e ordenou que ele fizesse caminhadas diárias no pátio do castelo.

O bispo planejou um caminho muito interessante ao longo do pátio, que é uma grade com L linhas de largura por C colunas de comprimento. Ele começa o passeio no canto superior esquerdo do pátio e se desloca diagonalmente entre os quadrados do pátio, virando 90 graus para a esquerda ou para a direita toda vez que ele encontra a borda do pátio. O passeio termina quando o bispo chega em algum outro canto do pátio. Por exemplo, a figura abaixo ilustra o passeio do bispo e os números atribúidos aos quadrados (a) em um pátio de dimensões 3 × 5 e (b) em um pátio de dimensões 4 × 5.

Para se distrair durante a sua caminhada, o bispo numera os quadrados visitados em ordem crescente, começando de 1. Isso significa que alguns quadrados são numerados uma vez, alguns são numerados duas vezes e outros não são numerados.

O rei, ao observar o passeio do bispo no pátio, ponderou se era possível determinar os números que o bispo atribui a um determinado quadrado sem precisar esperar que o bispo termine o seu passeio.

Tarefa

Escreva um programa que, dadas as dimensões do pátio, determina os números que o bispo atribuiu a uma série de quadrados de interesse do rei.

Entrada

A entrada contém um unico conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).

A primeira linha da entrada contém três inteiros L, C, e Q, separados por um espaço em branco, indicando a largura do pátio (2 ≤ L ≤ 10⁹), o comprimento do pátio (2 ≤ C ≤ 10⁹) e o número de consultas que devem ser respondidas (1≤ Q ≤ 10⁵).

Cada uma das Q linhas seguintes contém dois inteiros X e Y , separados por um espaço em branco, indicando a linha e a coluna do quadrado a ser consultado (1 ≤ X ≤ L, 1 ≤ Y ≤ C).

Saída

Seu programa deve imprimir, na saída padrão, Q linhas. Para cada consulta, imprima uma linha contendo um inteiro K, indicando o número de vezes em que o bispo visitou aquele quadrado, seguido do(s) número(s) que o bispo atribuiu aquele quadrado, caso houver, em ordem crescente, separados por espaços.

Exemplo

Entrada:
3 5 3
1 1
3 3
1 4

Saída:
1 1
1 3
0

Entrada:
2 2 4
1 1
2 1
1 2
2 2

Saída:
1 1
0
0
1 2

Entrada:
4 3 3
1 1
2 2
1 3

Saída:
1 1
2 2 6
1 7