Frequência

Byteland é uma cidade bastante conhecida por propor variados desafios aos seus habitantes. Recentemente, o prefeito de Byteland, Joãozinho, decidiu propor um desafio que ele gosta de chamar de Tabuleiro da Frequência.

A brincadeira ocorre da seguinte forma. Inicialmente, um tabuleiro com dimensões $N\times N$ é dado contendo apenas 0’s. Depois disso, $Q$ operações são propostas, podendo ser de 4 tipos:

• 1 $X$ $R$: Atribuir o valor R a todos os números da linha $X$;
• 2 $X$ $R$: Atribuir o valor R a todos os números da coluna $X$;
• 3 $X$: Imprimir o valor mais frequente na linha $X$;
• 4 $X$: Imprimir o valor mais frequente da coluna $X$.

Joãozinho é muito bom com computadores, mas também é bastante preguiçoso. Sabendo que você é um dos melhores programadores do mundo, ele decidiu pedir sua ajuda para resolver este problema.

Entrada

A primeira linha da entrada é composta por dois inteiros $N$ e $Q$, representando, respectivamente, o tamanho do tabuleiro e a quantidade de operações. As próximas $Q$ linhas da entrada vão conter as $Q$ operações. O primeiro inteiro de cada linha vai indicar o tipo da operação. Caso seja 1 ou 2, será seguido por mais dois inteiros $X$ e $R$. Caso seja 3 ou 4, será seguido por apenas mais um inteiro $X$.

Saída

Para cada operação do tipo 3 ou 4, seu programa deve produzir uma linha, contendo o valor da resposta correspondente. Se uma linha ou coluna tiver dois ou mais valores que se repetem o mesmo número de vezes, você deve imprimir o maior deles. Por exemplo, se uma linha tem os valores [5,7,7,2,5,2,1,3], tanto o 2, 5 e 7 se repetem duas vezes, então a resposta será 7, pois é o maior deles.

Restrições

• $1 \leq N, Q \leq 10^5$
• $1 \leq X \leq N$
• $0 \leq R \leq 50$

Informações sobre a pontuação

• Em um conjunto de casos de teste equivalente a $30$ pontos, $N \leq 10^3$.
• Em um conjunto de casos de teste equivalente a $20$ pontos, apenas as operações 2 e 3 serão usadas.

Exemplos

Exemplo de entrada 1

5 9
3 1
1 1 2
1 3 4
1 4 4
4 2
2 2 5
2 3 5
2 4 5
3 3

Exemplo de saída 1

0
4
5

Exemplo de entrada 2

2 4
1 1 1
2 2 2
3 1
3 2

Exemplo de saída 2

2
2

Exemplo de entrada 3

3 6
1 1 2
1 2 3
1 3 4
4 3
1 3 0
4 3

Exemplo de saída 3

4
3