Courses

Aritmética

Exponenciação rápida

Module: Exponenciação rápida

Problem

5 /5

Mudança de uma-duas-três-quatro-cinco vacas

Problem

N vacas (1 ≤ N ≤ 10⁵) O fazendeiro John está em uma fila. A i-ésima vaca à esquerda tem rótulo i (1 ≤ i ≤ N).
FD deu às vacas M pares de inteiros s (L₁,R₁)…(L_M,R_{M), onde 1 ≤ M≤ 100. Então ele disse às vacas para repetir exatamente K (1 ≤ K ≤ 10⁹) vezes o processo de M etapas:

Para cada i de 1 a M:

A sequência das vacas nas posições Li…Ri à esquerda inverte sua ordem.

Imprima os rótulos de todas as vacas da esquerda para a direita para cada i, (1 ≤ i ≤ N) após a conclusão do processo.

Entrada

A primeira linha contém os números N, M, K. Para cada 1 ≤ i≤ M string i+1 contém L_i e R_i, dois inteiros no intervalo 1…N, onde L_i<R_i.

Impressão

Na i-ésima linha da saída, imprima o i-ésimo elemento do array depois de executar todas as instruções K vezes.
Exemplos

#
Entrada
Saída
Explicação

1

7 2 2
25
3 7

1
2
4
3
5
7
6

Inicialmente, a ordem das vacas da esquerda para a direita é [1,2,3,4,5,6,7]

Após a primeira etapa do processo, a ordem será [1,5,4,3,2,6,7]

Após a segunda etapa do processo, o pedido passará a ser [1,5,7,6,2,3,4].

Repetindo as duas etapas mais uma vez, obtemos o resultado mostrado na saída.}

#	Entrada	Saída	Explicação
1	7 2 2 25 3 7	1 2 4 3 5 7 6	Inicialmente, a ordem das vacas da esquerda para a direita é [1,2,3,4,5,6,7] Após a primeira etapa do processo, a ordem será [1,5,4,3,2,6,7] Após a segunda etapa do processo, o pedido passará a ser [1,5,7,6,2,3,4]. Repetindo as duas etapas mais uma vez, obtemos o resultado mostrado na saída.