Šeštadieninė informatikos olimpiadininkų mokykla

Netrukus atsidarys visiškai nauja moderni sumuštinių reikmenų parduotuvė, prekiaujanti būtiniausiais sumuštinių reikmenimis – duona ir sviestu. Kadangi jau atidarymo dieną tikimasi didžiulio klientų antplūdžio, kad per naktį prie jos durų nesirikiuotų pirkėjų eilės, buvo nuspręsta padaryti registraciją į eilę internetu.

Parduotuvėje įdarbintos dvi pardavėjos – viena parduoda duoną, kita sviestą. Buvo paskaičiuota, jog per pirmąją darbo dieną abi jos sugebėtų aptarnauti po klientų, taigi tiek į duonos, tiek į sviesto eilę galėjo užsiregistruoti po klientų. Greitai visos vietų buvo užpildytos, bet tada parduotuvės savininkas suprato, jog vis tiek gali kilti problemų, jei vienu metu ateis eilė tam pačiam žmogui abiejose eilėse – tada kažkas turės laukti, o jau pirmąją dieną dirbti viršvalandžius pardavėjai nėra geras ženklas. Jo anaiptol nenuramino ir tai, jog išanalizavus užsiregistravusiųjų sąrašą paaiškėjo, kad kiekvienas žmogus užsiregistravęs duonos eilėje, yra užsiregistravęs ir sviesto eilėje, taigi iš viso parduotuvėje apsilankys lygiai skirtingų klientų.

Kad pardavėjoms nereikėtų dirbti viršvalandžių, parduotuvės savininkas nusprendė pakoreguoti sviesto eilę taip, kad nė vienas žmogus abiejose eilėse nebūtų toje pačioje vietoje. Tačiau jei tokio pokyčio metu kuris nors žmogus atsiduria tolesnėje eilės vietoje, negu buvo iki šiol, jis tampa nepatenkintas – jei jis buvo vietoje ir buvo perkeltas į vietą (), jo nepasitenkinimo lygis bus . Nepatenkinti klientai taip pat nėra gerai, todėl parduotuvės savininkas prašo, kad parašytum programą, kuri sviesto eilę perrikiuotų taip, kad ne tik nė vienas žmogus nebūtų toje pačioje vietoje abiejose eilėse, bet ir didžiausią nepasitenkinimo lygį turinčio žmogaus nepasitenkinimo lygis būtų minimalus.

Pradiniai duomenys

Pirmoje eilutėje – vienintelis skaičius (). Pirkėjai sunumeruoti nuo 1 iki .
Antroje eilutėje – skaičių – -ojoje duonos eilės pozicijoje yra pirkėjas Nr. (, , kai ).
Trečioje eilutėje – skaičių – -ojoje sviesto eilės pozicijoje yra pirkėjas Nr. (, , kai ).

Rezultatai

Jeigu yra toks būdas perrikiuoti sviesto eilę, kad pardavėjoms nereikėtų dirbti viršvalandžių, pirmoje eilutėje išveskite minimalų didžiausio nepasitenkinimo lygio dydį, o antroje eilutėje – skaičių, atspindinčių tinkamą sviesto eilę tokiu pačiu formatu, kaip pradiniuose duomenyse. Jei yra keli variantai, išveskite bet kurį.

Jeigu pardavėjos bet kokiu atveju privalės dirbti viršvalandžius, išveskite vieną skaičių -1.

Pavyzdžiai

2
2 1
1 2

0
1 2

3
1 2 3
3 2 1

1
2 3 1