casute

Casute

Nargy si Fumeanu au plecat la munte. Ei au o harta a muntelui, in care sunt identificate $N$ casute montane (numerotate cu numere distincte intre {$1$} si {$N$}), situate la diferite inaltimi (casuta $i$ se afla la inaltimea {$H{~i~}$}). Aceste casute sunt legate prin $M$ poteci. O poteca leaga doua casute distincte si poate fi parcursa doar intr-un singur sens: de la casuta situata la o inaltime mai mica catre casuta situata la o inaltime mai mare.
La un moment dat, cei doi s-au despartit si fiecare a ajuns in dreptul unei casute, dar din fericire fiecare avea la el o copie a hartii. Cei doi si-au telefonat si au stabilit un loc de intalnire, astfel: se vor intalni la casuta situata la inaltimea minima dintre acele casute la care pot ajunge amandoi (tineti minte ca nu pot decat urca).

Pentru a evita astfel de situatii in viitor, cei doi si-au propus sa determine locul in care s-ar fi intalnit indiferent de casutele in care s-ar fi aflat cei doi. Ei vor trece aceste rezultate pe o foaie de hartie,  pentru fiecare pereche $i$ $j$ ({$1&le;i<j&le;N$}), perechile fiind considerate in ordine lexicografica. in cazul in care pentru o anumita pereche nu exista o astfel de casuta de intalnire, se va scrie pe foaie numarul {$0$}.

Pentru a evita astfel de situatii in viitor, cei doi si-au propus sa determine locul in care s-ar fi intalnit indiferent de casutele in care s-ar fi aflat cei doi. Ei vor trece aceste rezultate pe o foaie de hartie, pentru fiecare pereche $i$ $j$ ({$1 &le; i < j &le; N$}), perechile fiind considerate in ordine lexicografica. In cazul in care pentru o anumita pereche nu exista o astfel de casuta de intalnire, se va scrie pe foaie numarul {$0$}.

h2. Date de intrare

* {$1 ≤ N ≤ 3.000$}
* {$1 ≤ M ≤ 30.000$}

* inaltimile celor $N$ casute sunt numere intregi distincte din intervalul [{$1,10^­9^$}]

* inaltimile celor $N$ casute sunt numere intregi distincte din intervalul [{$1,10^9^$}]

* Se considera ca o pereche de numere ({$a b$}) este mai mica din punct de vedere lexicografic decat o alta pereche de numere ({$c d$}), daca $a<c$ sau $a=c$ si $b<d$
h2. Exemplu

{$3345345555{~(6)~} = 36654767{~(10)~} = 24052 (mod 666013)$}
== include(page="template/taskfooter" task_id="casute") ==

1965