Problem D
Raðgreining 2

Mynd fengin af Wikipedia, public domain

Aðferðin sem rannsóknarstofan þín notar til að raðgreina getur aðeins fundið smá bút af DNA röðinni í einu. Sem dæmi, ef DNA röð veirunnar er af lengd $6$, þá væri hægt að nota aðferðina til að greina DNA bútinn sem byrjar á staf $1$ og endar á staf $4$ í DNA röð veirunnar, og svo greina DNA bútinn sem byrjar á staf $3$ og endar á staf $6$ í DNA röð veirunnar. Ef fyrri greiningin skilaði DNA bútinum GCAT og seinni greiningin DNA bútinum ATTC, þá væri hægt að leiða það út að DNA röð veirunnar er í raun GCATTC.

Á þennan hátt er búið að raðgreina mismunandi búta af DNA röð veirunnar sem byrja á mismunandi stöðum, og það eina sem á eftir að gera er að taka bútana saman og finna hver DNA röð veirunnar er í heild sinni. En vúbs! Þú missir alla DNA bútana sem var búið að greina á gólfið, og núna veistu ekki hvernig hver bútur snýr. Til dæmis gæti seinni búturinn að ofan verið orðinn CTTA.

Gefnir þeir bútar sem búið er að greina, annaðhvort rétta eða öfuga, og hvar hver bútur byrjar í DNA röð veirunnar, skrifaðu forrit sem setur þá saman og finnur eina mögulega DNA röð sem gæti komið til greina.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$ og $m$ ($1 \leq n, m \leq 500$), lengdin á DNA röð veirunnar og fjöldi búta sem búið er að raðgreina.

Svo fylgja $m$ línur, ein fyrir hvern bút sem búið er að raðgreina. Hver af þessum línum byrjar á heiltölu $s$ ($1 \leq s \leq n$), staðsetningin í DNA röð veirunnar þar sem þessi bútur byrjar, og svo fylgir búturinn sjálfur, sem er strengur af lengd $k$ ($1\leq k \leq n-s+1$) sem inniheldur stafina G, T, A og C.

Úttak

Skrifið út eina línu sem inniheldur stafina í einni mögulegri DNA röð veirunnar. Ef margar mögulegar DNA raðir koma til greina, þá má skrifa út einhverja þeirra. Ef engin DNA röð kemur til greina, þá á bara að skrifa út eina línu sem inniheldur Villa.

Stigagjöf

9 3
1 GCAT
3 CTTA
7 AAC

GCATTCAAC

10 2
3 AAAA
8 GGG

GTAAAAAGGG

10 2
3 AAAA
6 GGG

Villa