Fişierul intrare/ieşire:	tractor.in, tractor.out	Sursă	Stelele Informaticii 2006, clasele 11-12
Autor	Adrian Diaconu, Mircea Bogdan Pasoi	Adăugată de	Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test	0.8 sec	Limită de memorie	36096 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Tractor

Zaharel si-a cumparat tractor si s-a inscris la un concurs de tractorit. La acest concurs sunt inscrisi N = 2^K participanti in total, iar concursul se desfasoara dupa sistemul eliminatoriu:

• La inceput cei N participanti (numerotati convenabil de la 1 la N) sunt asezati de catre organizatorii intr-o ordine oarecare.
• In prima runda, participantul de pe pozitia 1 se intrece cu cel de pe pozitia 2, cel de pe pozitia 3 cu cel de pe pozitia 4, cel de pe pozitia 5 cu cel de pe pozitia 6 etc. Castigatorii avanseaza in runda urmatoare, pierzatorii sunt elimitati din concurs.
• In a doua runda, castigatorul dintre participantii de pe pozitiile 1 si 2 se intrece cu castigatorul dintre participantii de pe pozitiile 3 si 4, etc., castigatorul dintre participantii de pe pozitiile N - 3 si N - 2 se intrece cu castigatorul dintre participantii de pe pozitiile N - 1 si N.
• Concursul continua in acelasi mod, la fiecare runda eliminandu-se jumatate din participanti, pana cand mai ramane unul singur. Participantul care ramane singur va fi considerat castigatorul concursului.

La fiecare intrecere in tractorit in care participantul cu numarul i il bate pe participantul cu numarul j se aduna la premiu valoarea A_{i, j}. Premiul este luat de ultimul participant cara ramane in concurs.

Fiecare din cei N jucatori isi imagineaza cel mai favorabil scenariu (care depinde de asezarea data de organizatori si de castigatorii fiecarei intreceri) in care el castiga turneul iar premiul strans este maxim posibil.

Cerinta

Determinati pentru fiecare din cei N jucatori care este premiul maxim pe care il poate obtine, considerand ca el castiga turneul.

Date de intrare

In fisierul tractor.in se afla pe prima linie un numar natural T reprezentand numarul de teste. Urmeaza apoi descrierea celor T teste. Pe prima linie a unui test se va afla numarul N de participanti, iar pe urmatoarele N linii cate N numere naturale separate prin spatii reprezentand matricea A pentru testul respectiv.

Date de iesire

Fisierul de iesire tractor.out va contine cate N linii pentru fiecare test reprezentand premiile maxime care se pot obtine pentru fiecare jucator, in ordinea numerotarii de la 1 la N.

Restrictii

• 1 ≤ T ≤ 4
• 1 ≤ N ≤ 16 (N este o putere a lui 2)
• 0 ≤ A_{i, j} ≤ 1 000 000, A_{i, i} = 0

Exemplu

Explicatie

Vom considera exemplul cu N = 4 in care jucatorul cu numarul 1 vrea sa stie premiul maxim pe care il poate obtine. Daca asezarea initiala este 1 4 2 3 iar intrecerile se desfasoara astfel:

    [1]
   /   \
  1     2
 / \   / \
1   4 2   3

Premiul care se obtine este A_{1, 4} + A_{2, 3} + A_{1, 2} = 16, iar acesta este maxim considerand toate cele 24 posibiltati pentru asezarea initiala si toate posibilitatile de desfasurare a meciurilor.

Cum se trimit solutii?