Problem D
Orm

Igår vann lilla Olle det kända spelet Orm för första gången. I Orm finns det ett $3 \times N$ stort rutnät. Spelaren kontrollerar en orm som består av ett antal segment. Till en början består ormen av ett enda segment, vilket vi kallar för dess huvud. Varje sekund kan huvudet röra sig upp, ner, höger eller vänster. Om huvudet krockar med ett annat segment så förlorar du spelet. Efter att huvudet rör sig, så förlorar ormen segmentet längst bort från huvudet (det äldsta segmentet som tillhör ormen). Med andra ord kan man föreställa sig att ormens kropp förflyttat sig en ruta. Under spelets gång kommer det att dyka upp äpplen på vissa rutor. Om ormens huvud åker på ett äpple så försvinner äpplet, men segmentet längst bort från huvudet försvinner inte. Med andra ord ökar ormens längd med $1$.

Om ormen fyller upp hela rutnätet har man vunnit spelet, eftersom man inte längre kan öka ormens längd. När Olle vill skryta för sina vänner att han äntligen vunnit Orm, så tror de honom inte. För att övertyga sina kompisar tänker Olle rita upp hur hans orm såg ut när han vann. Tyvärr kommer han inte ihåg exakt hur den såg ut. Han kommer dock ihåg hur långt vissa rutor befann sig från svansen (segmentet längst bort från huvudet). Givet en del av dessa avstånd, kan du hitta hur Olles orm såg ut?

Figure 1: Bilden hur ormen ser ut i exempelfall 1. För detta rutnätet är det den enda giltiga ormen.

Indata

Den första raden innehåller heltalet $N$ ($1 \leq N \leq 1000$), antalet kolumner i rutnätet.

Därefter följer tre rader som vardera beskriver en rad av rutnätet. Den $i$:te raden innehåller heltalen $c_1, c_2, \dots , c_ N$ ($0 \leq c_ j \leq c_ N$), avståndet mellan svansen och ormens kroppssegment på rad $i$ och kolumn $j$. Om $c_ j$ är $0$ betyder det att Olle glömde vad $c_ j$ är. Alla $c_ j$ som inte är $0$ är parvis unika. Det är även garanterat att det finns minst en giltig lösning.

Utdata

Skriv ut $3$ rader med $N$ heltal vardera, som beskriver en giltig vinnande orm. Varje heltal mellan $1$ och $N \cdot 3$ måste förekomma exakt en gång. För varje $i$ mellan $1$ och $N \cdot 3 - 1$ måste segmentet med tal $i$ ligga ovanför, nedanför, till vänster eller höger relativt segmentet med tal $i+1$. Om det finns flera giltiga ormar kan du skriva ut vilken giltig orm som helst.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

5
3 2 0 10 11
4 0 8 15 12
0 0 0 14 0

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

6
0 0 0 0 0 0
4 3 16 15 14 11
5 6 7 8 9 10

1 2 17 18 13 12
4 3 16 15 14 11
5 6 7 8 9 10