ecotraseu

Ecotraseu

În "centrul vechi al oraşului Copenhaga":http://www.denstoredanske.dk/@api/deki/files/27202/=48693232.jpg nu circulă maşini. De aceea, companiile de turism parchează autobuzele de hop-on hop-off în apropierea intersecţiilor de la margine. Oraşul este modelat astfel încât între oricare două intersecţii există un drum simplu unic. Intersecţiile de la extremitatea unei singure străzi sunt staţiile de autobuz, iar cele care leagă mai multe străzi - obiective turistice.

Fiecare stradă din Copenhaga are asociat un _avantaj_. De exemplu, pe străzile cu avantaj negativ sunt strategic poziţionaţi tinerii de la organizaţiile nonprofit în căutare de donaţii, iar pe străzile cu avantaj pozitiv - magazinele cu bere _aproape_ gratis. Suma avantajelor străzilor care formează un drum este avantajul acelui drum. Un drum simplu de avantaj $0$, cu staţii de autobuz în extremităţi distincte, se numeşte _ecotraseu_.

Fiecare stradă din Copenhaga are asociat un _avantaj_. De exemplu, pe străzile cu avantaj negativ sunt strategic poziţionaţi tinerii de la organizaţiile nonprofit în căutare de donaţii, iar pe străzile cu avantaj pozitiv - magazinele cu bere _aproape_ gratis. Suma avantajelor străzilor care formează un drum este avantajul acelui drum. Un drum simplu de avantaj $0$, cu staţii de autobuz distincte în extremităţi, se numeşte _ecotraseu_.

Companiile de turism ştiu că în oraş există un ecotraseu, dar ar vrea să gasească şi extremităţile unuia pentru a parca autobuzele în ele.

h2. Restricţii

* $1$ $<=$ $x$, $y$ $<=$ $N$ $<=$ $100.000$
* $|a|$ $<=$ $10.000$

* $1$ $<=$ $x$, $y$ $<=$ $N$ $<=$ $10^5^$
* $|a|$ $<=$ $10^4^$

* $1$ $<=$ $T$ $<=$ $20$

* Cel mult $10$ teste au $1$ $<=$ $N$ $<=$ $10.000$
* Cel mult $10$ teste au $10.000$ $<=$ $N$ $<=$ $100.000$

* Cel mult $10$ teste au $1$ $<=$ $N$ $<=$ $10^4^$
* Cel mult $10$ teste au $10^4^$ $<=$ $N$ $<=$ $10^5^$

h2. Exemplu

10452