Problem 443: Pisi

ACPC (The Association of Cats' Politically Correctness) a afirmat că toate pisicile sunt la fel de drăgălașe, afirmație care mai mult ca sigur este falsă, ținând cont că există și pisici fără blană.

Revoltați de această afirmație, organizatorii unei expoziții de pisici s-au hotărât să organizeze și un concurs în cadrul expoziției. Astfel, ei vor evalua toate cele N pisici expuse, pentru a stabili odată pentru totdeauna cele mai drăgălașe dintre ele.

Fiecare pisică a fost evaluată după trei criterii:

Pufoșenie sau scorul genetic: cât de pufoasă este blana pisicii;
Fotogenicitate sau instinctul artistic: cât de fotogenică este pisicuța;
Dragoste sau norocul în viață: cât de iubită este pisica de către stăpânul ei.

Organizatorii expoziției au conceput astfel câte un clasament separat pentru fiecare dintre cele trei categorii, stabilind ordinea celor N pisici în funcție de fiecare criteriu. Cu toate acestea, acum ei doresc să creeze un clasament cumulat, care să stabilească o ordine clară și necontestabilă a drăgălășeniei acestora.

Cum în multe dintre cazuri s-a dovedit că acest lucru nu este ușor de stabilit, aceștia au convenit că o pisică i (1 ≤ i ≤ N) este considerată "absolut mai drăgălașă" decât o pisică j dacă pisica i apare înaintea pisicii j în minim două dintre cele trei clasamente individuale.

Întrucât nu au foarte multă experiență cu concursurile, organizatorii te roagă să îi ajuți să determine dacă există un clasament cumulat valid și, dacă acesta există, să-l găsești. Un clasament este considerat valid dacă, pentru oricare două pisici i și j (1 ≤ i, j ≤ N), pisica i apare înaintea pisicii j în clasament dacă și numai dacă pisica i este "absolut mai drăgălașă" decât pisica j.

Detalii de implementare

Veți implementa funcția cu următorul antet:

std::vector<int> rank_cats(std::vector<int> p, std::vector<int> f, std::vector<int> d)

Atenție! Funcția rank_cats va fi apelată cel puțin o dată și de cel mult 10 ori. Cei trei vectori p, f și d vor avea aceeași lungime și vor reprezenta clasamentele tuturor celor N = |p| pisici, conform fiecăruia dintre cele trei criterii menționate. De exemplu, $p_i (0 ≤ i < N)$ va reprezenta numărul de ordine al pisicii de pe locul i + 1 după pufoșenie. Se garantează că fiecare dintre cei trei vectori reprezintă permutări ale numerelor de la 1 la N.

Pentru ca soluția returnată să fie validă, trebuie ca lungimea vectorului returnat să fie egală cu N și ca acesta să reprezinte un clasament cumulat valid, conform cu explicațiile din enunț. Dacă nu există niciun clasament valid, funcția trebuie să returneze vectorul vid (de lungime zero).

Punctare

Subtask 1 (8 puncte)

1 ≤ N ≤ 10

Subtask 2 (8 puncte)

1 ≤ N ≤ 17

Subtask 3 (23 puncte)

1 ≤ N ≤ 2 000

Subtask 4 (61 puncte)

1 ≤ N ≤ 100 000

Model de grader

Graderul va citi de la consolă datele de intrare în următorul format:

linia 1: $N$ , reprezentând numărul de pisici
linia 2: $p_0 \ p_1 \ ... \ p_{N-1}$ (separate prin câte un spațiu)
linia 3: $f_0 \ f_1 \ ... \ f_{N-1}$ (separate prin câte un spațiu)
linia 4: $d_0 \ d_1 \ ... \ d_{N-1}$ (separate prin câte un spațiu)

Graderul va afișa la consolă răspunsul vostru în următorul format:

linia 1: $r_0 \ r_1 \ ... \ r_{N-1}$ (separate prin câte un spațiu), reprezentând clasamentul cumulat.

Dacă răspunsul vostru este vectorul vid, graderul va afișa o singură linie, cu mesajul NO SOLUTION.

Exemple

stdin

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

stdout

3 1 4 6 5 2

stdin

stdout

NO SOLUTION

Explicație

Cele trei pisici expuse corespunzătoare celui de-al doilea exemplu sunt ilustrate mai jos:

Concurentul cu numărul 1 este mai pufos și mai iubit decât concurentul 2, dar este mai puțin pufos și mai puțin fotogenic decât concurentul 3. În schimb, concurentul 2 este mai fotogenic și mai iubit decât concurentul 3.

În concluzie, nu putem determina un clasament cumulat al celor trei concurenți.

Pisi