Problem AF
Pýramídasala

Mynd fengin af flickr.com

Fyrirtækið Pýramídar ehf. selur hundruði pýramída hvert ár. Viðskiptamódelið þeirra er frábrugðið því sem þekkist almennt hjá fyrirtækjum. Pýramídas, eigandi fyrirtækisins, réði starfsmenn sem selja fyrir fyrirtækið. Starfsmenn Pýramídasar ráða svo sína eigin starfsmenn, þeirra starfsmenn ráða sína eigin starfsmenn, og svo framvegis. Starfsmenn eru því með einn yfirmann (nema Pýramídas) en geta haft marga undirmenn. Ef að starfsmaður er með undirmann þá mun hann alltaf hafa að minnsta kosti tvo undirmenn. Í öðrum orðum, þá mun starfsmaður aldrei hafa nákvæmlega einn undirmann. Athugið að undirmönnum er raðað eftir því hvenær þeir voru ráðnir; undirmaðurinn sem var ráðinn fyrst kemur fremst, sá næsti á eftir honum, og svo framvegis.

Pýramídas á alla pýramídana í upphafi og selur þá áfram til starfsmanna sinna. Þeir selja svo pýramídana áfram til starfsmanna sinna og heldur það áfram þar til pýramídarnir eru komnir í hendur þeirra sem hafa enga starfsmenn undir sér. Þeir starfsmenn selja pýramídana til þeirra sem eru ekki starfsmenn fyrirtækisins en hafa samt áhuga á pýramídum. Starfsmenn þurfa svo að skila $10\mathrm{\%}$ af gróða sínum til yfirmanns síns.

Nýlega hafa borist kvartanir um lögmæti starfseminnar. Þú hefur verið ráðinn til að rannsaka. Fyrsta skref rannsóknarinnar er að skilja uppbyggingu fyrirtækisins. Því miður vill enginn starfsmaður veita þér neinar upplýsingar um hverjir starfa fyrir hvern eða hver sé yfirmaður hvers.

Þú hefur starfsmannaskrá sem segir þér starfsmannanúmer hvers og eins starfsmanns. Þú hefur einnig komist yfir þrjár runur af starfsmannanúmerum sem eiga að lýsa uppbyggingu fyrirtækisins. Vinur þinn Bjarki er sérfræðingur í dulkóðun og hefur komist að því að eftirfarandi þrjár mismunandi aðferðir voru notaðar til að búa til runurnar þrjár:

1. Fyrst skrifar starfsmaður númerið sitt og skipar undirmönnum sínum að fylgja aðgerðum sínum. Undirmenn skipa sínum undirmönnum áfram.

2. Fyrst skipar hann fyrsta undirmanni sínum að fylgja aðgerðum sínum. Næst skrifar hann númerið sitt. Þá skipar hann öðrum undirmanni að fylgja aðgerðum sínum. Svo skrifar hann númerið sitt. Þá er röðin komin að þriðja undirmanni. Alltaf skrifar hann númer sitt á milli aðgerða undirmanna sinna þar til síðasti undirmaðurinn hefur klárað. Ef starfsmaður hefur engan undirmann þá skrifar hann númer sitt einu sinni.

3. Fyrst skipar starfsmaður undirmönnum sínum að fylgja aðgerðum sínum og svo skrifar hann númerið sitt. Undirmenn skipa sínum undirmönnum áfram.

Útfrá þessum þremur runum geturðu sagt hver uppbygging fyrirtækisins er? Hver vinnur fyrir hvern og í hvaða röð voru undirmennirnir ráðnir?

Inntak

Inntak er fjórar línur. Fyrsta línan í inntakinu samanstendur af tveimur heiltölum $1\le N\le {10}^5$, fjöldi starfsmanna, og $M$, fjöldi talna í runu 2. Önnur lína samanstendur af $N$ heiltölum, runu 1. Þriðja lína samanstendur af $M$ heiltölum, runu 2. Fjórða lína samanstendur af $N$ heiltölum, runu 3.

Starfsmannanúmer eru alltaf heiltölur á bilinu $1$ upp í $N$, en þeim er ekki úthlutað á neinn sérstakan hátt.

Úttak

Skrifið út $N$ línur. Lína $i$ skal innihalda starfsmannanúmer allra undirmanna starfsmannsins með númerið $i$. Undirmennirnir þurfa að vera skrifaðir í réttri röð. Þið getið gert ráð fyrir að það sé alltaf til nákvæmlega ein lausn.

Stigagjöf

Útskýring á sýnidæmum

Fyrsta sýnidæmið fellur undir hóp $1$ og má sjá uppbyggingu fyrirtækisins á myndinni að neðan.

Figure 1: Sýnidæmi 1

Annað sýnidæmið fellur undir hóp $2$ og má sjá uppbyggingu fyrirtækisins á myndinni að neðan.

Figure 2: Sýnidæmi 2

Þriðja sýnidæmið fellur undir hóp $3$ og má sjá uppbyggingu fyrirtækisins á myndinni að neðan.

Figure 3: Sýnidæmi 3

5 5
2 1 4 3 5
1 2 3 4 5
1 3 5 4 2

1:
2: 1 4
3:
4: 3 5
5:

7 7
5 7 3 1 2 4 6
3 7 2 1 4 5 6
3 2 4 1 7 6 5

1: 2 4
2:
3:
4:
5: 7 6
6:
7: 3 1

12 15
6 8 5 7 1 12 3 11 10 4 9 2
5 8 7 6 12 1 3 6 10 11 4 11 9 11 2
5 7 8 12 3 1 10 4 9 2 11 6

1: 12 3
2:
3:
4:
5:
6: 8 1 11
7:
8: 5 7
9:
10:
11: 10 4 9 2
12: