ED23S1

A análise genômica teve avanços significativos nessa última década, culminando com o completo mapeamento do genoma humano.

Um processo que os geneticistas gostariam de dominar no laboratório é a de crossing-over. Trata-se de um fenômeno, que ocorre durante a meiose, é que consiste na quebra de cromossomos em alguns pontos e, na sequência, há uma troca de pedaços correspondentes entre eles. Vale destacar ainda que as trocas provocam o surgimento de outras sequências de genes ao longo dos cromossomos, como mostram as figuras a seguir.

Um grupo de geneticistas está muito interessado em simular o crossing-over, para tentar prever todas as caraterísticas possíveis. Nessa simulação um gene é uma sequência de bases do DNA (Adenina, Citosina, Guanina, Timina).

A ideia desses cientistas é controlar o crossing-over, localizando uma sequência de bases genéticas e substituindo por outra sequência, todas as vezes que um par dessas sequencias ocorrerem nos genes.

Você foi contratado para realizar essa simulação. Há muitas formas de armazenar os dados gerados por esse mapeamento, mas uma das formas mais eficientes de manipular as bases é tratar cada gene como uma lista encadeada de bases de DNA na ordem que parecem no gene.

Para sua simulação, os cientistas informam dois genes (ou pedaços de genes) e quais sequencias devem ser trocadas entre esses genes.  e você deve mostrar as duas novas sequências geradas. Para essa simulação, os pares de sequências devem ser trocados todas as vezes que forem encontrados e as trocas ocorrem na ordem em que são informadas.

ENTRADA

A primeira linha contém a sequência do primeiro gene, nessa simulação, um gene pode ter até 10³ bases.

A segunda linha contém a sequência do segundo gene.

A terceira linha contém o número de pares de sequencias para troca. 

Os próximos pares de linhas contêm as sequencias que devem ser trocadas entre si nos dois genes.

SAÍDA

A primeira linha contém a nova sequência do primeiro gene.

A segunda linha contém a nova sequência do segundo gene.

 Exemplos