XXVI Olimpíada Brasileira de Informática
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 Nx 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 ≤ N, Q ≤ 105
- 1 ≤ X ≤ N
- 0 ≤ R ≤ 50
Informações sobre a pontuação
- Em um conjunto de casos de teste equivalente a 30 pontos, N ≤ 103.
- Em um conjunto de casos de teste equivalente a 20 pontos, apenas as operações 2 e 3 serão usadas.
Exemplos
Entrada
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 |
Saída
0 4 5 |
Entrada
2 4 1 1 1 2 2 2 3 1 3 2 |
Saída
2 2 |
Entrada
3 6 1 1 2 1 2 3 1 3 4 4 3 1 3 0 4 3 |
Saída
4 3 |
