Magicianul Marcel, al ținuturilor „mai aproape de dincoace, dar mai încolo de dincolo”, a venit în audiență la palatul regelui pentru a-și presta uimitorul spectacol de magie... matematică.
Acesta a ascuns un șir de $N$ numere naturale în jobenul său magic, iar regele trebuie să ghicească șirul ales. Marcel îi dă voie să pună întrebări, anume regele poate întreba care este suma unei subsecvențe continue din șir. Formal, regele poate afla suma $S = a_l + a_{l+1} + \ldots + a_{r−1} + a_r$ pentru orice $1 \leq l < r \leq N$.
Dar Marcel este exigent și îi cere regelui să folosească cel mult $N$ astfel de întrebări.

Cerință

Ajutați-l pe rege să determine șirul ascuns de magicianul Marcel, scriindu-i un program.

Protocol de interacțiune

Programul concurentului trebuie să implementeze funcția cu următorul antet:

std::vector<int> solve(int N);

Funcția primește ca parametru numărul de elemente al șirului și trebuie să returneze un vector de dimensiune exact $N + 1$, cele $N$ elemente fiind indexate de la 1.
Programul va include header-ul magie.h care va conține definiția următoarei funcții:

int query(int left, int right);

Funcția va primi ca parametrii capătul din stânga, respectiv din dreapta al subsecvenței pentru care se dorește aflarea sumei. Dacă intervalul este invalid (left sau right sunt indici în afara șirului sau nu se respectă condiția de strictețe), programul își va opri execuția, iar verdictul va fi de răspuns greșit.

Restricții și precizări

• $3 \leq N \leq 10 \ 000$
• $1 \leq a_i \leq 10 \ 000 \ \forall \ i, \ 1 \leq i \leq N$
• Interactorul nu este adaptiv. Șirul de numere este fixat de la începerea execuției programului.
• În timpul concursului, interacțiunea a fost realizată prin stdin/stdout.
• Punctajele pentru grupe au fost modificate față de cele din concurs.

Exemplu de interacțiune

Avem $N = 6$

• Se apelează query(1,5) și se returnează 20.
• Se apelează query(5,6) și se returnează 30.
• Programul returnează vectorul $\{1, \ 3, \ 4, \ 2, \ 10, \ 20\}$.