XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: troca.x, onde x deve ser c, cpp, java, js ou py

Troca

Um cientista especializado em bioinformática está estudando formas de simular alguns fenômenos, que ocorrem dentro das células, relacionados ao funcionamento de proteínas. Parece muito complicado, não? Só que o problema computacional básico que ele precisa resolver eficientemente é fácil de entender. Existe uma sequência de N cartas, indexadas de 1 a N, e cada carta contém dois números impressos, um de cada lado. As cartas são colocadas na mesa, na sequência, com um dos lados virado para cima. Dados dois inteiros i e j, com i ≤ j, a operação troca(i,j) consiste em virar todas as cartas da posição i até a posição j, inclusive. Por exemplo, considere a sequência de cartas abaixo.

virado para cima 31 2 45 3 8 1 32 10 4 27 12 7 7 9 63 47
virado para baixo 1 12 6 4 97 2 87 10 3 9 55 56 11 90 3 8

A operação de troca(5,11) resultaria na seguinte sequência de cartas:

virado para cima 31 2 45 3 97 2 87 10 3 9 55 7 7 9 63 47
virado para baixo 1 12 6 4 8 1 32 10 4 27 12 56 11 90 3 8

O problema do cientista é que a sequência de cartas pode ser muito grande e podem ser feitas muitas operações de troca. Ele precisa saber a sequência dos números que estarão virados para cima ao final de todas as operações. Você pode ajudá-lo?

Entrada

A primeira linha da entrada contém dois inteiros N e T, indicando respectivamente a quantidade de cartas e a quantidade de operações de troca. A segunda linha contém N inteiros, indicando os números virados para cima inicialmente. A terceira linha contém N números, indicando os virados para baixo inicialmente. As T linhas seguintes contém, cada uma, dois inteiros I e J, indicando os limites de uma operação de troca.

Saída

Imprima uma linha contendo N inteiros representando os números que estarão virados para cima após todas as operações.

Restrições

  • 1 ≤ N ≤ 105
  • 1 ≤ T ≤ 105
  • 1 ≤ I ≤ J ≤ N
  • O valor dos elementos dos vetores está entre 0 e 109, inclusive.

Informações sobre a pontuação

  • Para um conjunto de casos de teste valendo 10 pontos, I=J para todas as operações;
  • Para um conjunto de casos de teste valendo 20 pontos, N ≤ 104 e T ≤ 104.

Exemplos

Entrada
16 1
31 2 45 3 8 1 32 10 4 27 12 7 7 9 63 47
1 12 6 4 97 2 87 10 3 9 55 56 11 90 3 8
5 11
Saída
31 2 45 3 97 2 87 10 3 9 55 7 7 9 63 47
	

 

Entrada
10 5
7 88 23 44 1 67 73 2 9 11
4 55 1 1 3 74 82 9 8 37
1 3
5 10
2 6
5 9
1 7
Saída
7 55 1 44 1 67 82 2 9 37
	

 

Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação