Jogo da Memória

Todo domingo, Zuleide monta a barraca dela na Feira da Torre de TV, entre a tenda dos pastéis e a das redes de dormir. Ela vende um jogo da memória feito à mão, com cartas que trazem os monumentos de Brasília desenhados a nanquim: dois Congressos, duas Catedrais, duas pontes JK, e assim por diante. Como ninguém compra o que não experimenta, Zuleide inventou um desafio para atrair freguês: quem limpar o tabuleiro dela leva o jogo de graça.

O desafio funciona assim. Zuleide embaralha as cartas e as espalha viradas para baixo num tabuleiro de $N$ linhas e $M$ colunas. Cada carta traz um desenho, e cada desenho aparece em exatamente duas cartas do tabuleiro. Para conversar com os fregueses de fora, que não sabem distinguir o Itamaraty do Palácio da Justiça, ela numerou os desenhos de $1$ a $\frac{N \cdot M}{2}$. A cada jogada, o freguês aponta duas cartas ainda viradas para baixo e Zuleide as vira. Se os desenhos forem iguais, o par foi encontrado e as duas cartas ficam viradas para cima até o fim do jogo. Se forem diferentes, Zuleide diz qual desenho estava em cada uma e vira as duas de volta para baixo.

A pegadinha é o limite: o freguês só leva o jogo se encontrar todos os pares usando, no máximo, tantas jogadas quantas são as cartas do tabuleiro, ou seja, $N \cdot M$ jogadas. Zuleide garante que sempre dá para vencer. Só que quase ninguém consegue, e quem perde acaba comprando o jogo mesmo assim, o que é exatamente o plano dela.

Você está na fila com o dinheiro contado e decidiu que vai levar o jogo de graça. Escreva um programa que jogue contra Zuleide e limpe o tabuleiro dentro do limite.

Este é um problema interativo: em vez de ler uma entrada fixa, o seu programa conversa com o juiz, que faz o papel de Zuleide. O seu programa aponta as cartas e recebe de volta o que ela viu ao virá-las.

Interação

No início, o juiz envia uma linha com dois inteiros $N$ e $M$ ($1 \leq N, M \leq 10^4$), as dimensões do tabuleiro. É garantido que $N \cdot M$ é par e que $2 \leq N \cdot M \leq 10^4$. As linhas são numeradas de $1$ a $N$, de cima para baixo, e as colunas de $1$ a $M$, da esquerda para a direita. Cada carta traz um inteiro entre $1$ e $\frac{N \cdot M}{2}$, e cada um desses inteiros aparece em exatamente duas cartas.

A cada jogada, o seu programa imprime uma linha r1 c1 r2 c2, com $1 \leq r_1, r_2 \leq N$ e $1 \leq c_1, c_2 \leq M$, indicando as duas cartas que quer virar: a da linha $r_1$ e coluna $c_1$ e a da linha $r_2$ e coluna $c_2$. As duas posições devem ser distintas e nenhuma delas pode ser de uma carta já emparelhada. O juiz responde uma linha:

• IGUAL, se as duas cartas traziam o mesmo inteiro. O par foi encontrado e as duas cartas ficam viradas para cima até o fim do jogo.
• DIFERENTE v1 v2, se traziam inteiros diferentes: $v_1$ é o inteiro da carta em $(r_1, c_1)$ e $v_2$ é o da carta em $(r_2, c_2)$. As duas voltam a ficar viradas para baixo.

Quando a resposta IGUAL completar o último par, o jogo acaba e o seu programa deve encerrar.

Seu programa pode fazer no máximo $N \cdot M$ jogadas. Estourar esse limite, indicar uma posição fora do tabuleiro, repetir a mesma posição nas duas cartas de uma jogada ou virar uma carta já emparelhada dá Wrong Answer.

É garantido que o tabuleiro está fixado antes da primeira jogada, ou seja, o juiz não muda as cartas de lugar em função do que você jogou, e que existe uma estratégia que limpa qualquer tabuleiro dentro do limite.

Dê flush na saída depois de cada linha impressa. A conversa com o juiz passa por um pipe, e uma linha presa no buffer de saída nunca chega do outro lado: o seu programa fica esperando por uma resposta que não vem e o veredito acaba sendo um Time Limit Exceeded injusto. Use fflush(stdout) em C, std::endl ou << std::flush em C++, print(..., flush=True) em Python, io::stdout().flush() em Rust e System.out.flush() em Java e Kotlin, cujas JVMs têm buffer próprio. Em Bash, o echo já entrega a linha. Leia sempre a resposta antes de fazer a jogada seguinte, e leia uma linha por vez: ler a entrada até o fim trava o programa, porque o juiz só fala depois de cada jogada sua.

Entrada

A única coisa que o seu programa recebe antes de jogar é a linha com $N$ e $M$. Tudo o que ele lê depois são as respostas IGUAL e DIFERENTE v1 v2, uma por linha, cada uma logo depois de uma jogada que ele mesmo imprimiu.

Saída

O seu programa imprime as jogadas no formato r1 c1 r2 c2, uma por linha, e encerra assim que a resposta IGUAL completar o último par.

Exemplo

Nos diálogos abaixo, as linhas sem recuo são o que o seu programa imprime e as linhas recuadas são o que o juiz responde.

Num tabuleiro $2 \times 2$ cujas cartas, escondidas, são

1 2
2 1

uma partida vencedora é:

        2 2
1 1 1 2
        DIFERENTE 1 2
2 1 2 2
        DIFERENTE 2 1
1 1 2 2
        IGUAL
1 2 2 1
        IGUAL

A figura a seguir reflete essa partida. Nas duas primeiras jogadas as cartas viradas eram diferentes e voltaram para baixo; nas duas últimas, os pares foram encontrados. Foram $4$ jogadas, exatamente o limite $N \cdot M = 4$.

Num tabuleiro $1 \times 2$ só há um par, e uma jogada resolve:

        1 2
1 1 1 2
        IGUAL