Você está ajudando em um grande evento de Computação e precisa imprimir os recibos de inscrição. O organizador do evento irá entregar para você um arquivo .pdf gigante cujas as páginas correspondem aos recibos de todos os participantes, um por página em ordem de inscrição. Assim, no início do evento, a ordem dos participantes na fila pode ser representada por uma sequência ordenada:

1 2 3 4 5 6 7 8 9 10

O problema é que, enquanto o arquivo original está em ordem de inscrição, os participantes são impacientes e acabam bagunçando a ordem da fila. Para otimizar o tempo, antes de imprimir o documento, você deseja rearranjar as páginas para que ele seja impresso na ordem de retirada.

Os participantes bagunçam a fila de duas maneiras:

1. Quando um grupo de amigos, que estão um atrás do outro, resolve conversar, eles podem voltar à fila na ordem inversa. Assim, se os amigos de 2 até 5 resolverem conversar, após eles voltarem, a fila ficará da seguinte maneira:

   1 5 4 3 2 6 7 8 9 10
   

2. Pode ser também que uma pessoa resolva esperar por outra. Assim, depois que a participante 1 decidir esperar por seu amigo 2, a fila ficará da seguinte maneira:

   5 4 3 2 1 6 7 8 9 10
   

O seu objetivo é escrever um programa rearranjar.c que descobre a ordem em que as páginas do .pdf devem ser impressas.

Entrada

A primeira linha contém um inteiro $n$ indicando o número de participantes ($0 \le n \le 10000$). A seguinte linha contém um inteiro $m$ representando o número de movimentos na fila de participantes ($0 \le m \le 500$). Cada uma das $m$ linhas seguintes tem uma das duas formas:

• 1 a b representando que o grupo de amigos, começando pelo de número de inscrição a até o de número b resolvem conversar e voltam em ordem inversa;

• 2 a b representando que o participante de número a resolveu esperar pelo participante de número b.

Exemplo de entrada

10
2
1 2 5
2 1 2

Saída

A saída deve ser uma linha de $n$ inteiros representando a ordem em que as páginas do documento devem ser impressas.

Exemplo de saída

5 4 3 2 1 6 7 8 9 10

Critérios

É obrigatório representar a sequência de páginas como um vetor estático e organizar o programa em funções de forma que cada operação da fila seja implementada por uma função distinta. Também pode ser útil criar uma função que descobre o índice de um número no vetor.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push.

Esta tarefa não será corrigida por um monitor, mas vocês são incentivados a mostrar o código a um monitor e tirar dúvidas sobre a tarefa nos horários de atendimento.

Turma AB: O peso desta tarefa é 1.

← Anterior Voltar Próximo →