NoGameNoLife

După ce au cucerit toate cele $16$ rase, Sora și cu Shiro în sfârșit au ajuns sa îl provoace pe zeul Tet la duel. Tet a generat aleator un graf neorientat cu costuri pe muchii. La sfârșit, acesta le-a pus celor doua personaje $Q$ întrebări de forma: care este drumul de lungime minima de la nodul $x$ la nodul $y$? Pentru că știe ca este o problema grea, el se mulțumește cu drumuri cât mai scurte, nu neapărat cele mai scurte.

Date de intrare

Pe prima linie a fișierului de intrare nolife.in se va afla un număr natural $N$ (numărul de noduri) și un numar natural $M$ (numărul de muchii). Pe următoarele $M$ linii vor fi trei numere $x$, $y$ și $z$, reprezentând faptul că există muchie între nodurile $x$ şi $y$ de lungime $z$. Pe următoarea linie se va afla un singur numar natural $Q$. Pe urmatoarele $Q$ linii vor fi câte două numere, $x$ și $y$ – nodurile între care vrea să găsim un drum cât mai scurt.

Date de ieșire

În fișierul de ieșire nolife.out se va afișa răspunsul pentru fiecare întrebare, câte unul pe linie. Un răspuns trebuie să descrie un drum între nodurile $x$ și $y$ în felul următor: Primul număr de pe linie este numărul de noduri prin care trece drumul, urmat de nodurile în ordinea de parcurgere de la $x$ la $y$. În cazul în care vreți să nu răspundeți la o întrebare, afișați doar $0$ pentru aceasta.

Restricții si precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq M \leq 300 \ 000$;
• $1 \leq Q \leq 20 \ 000$;
• Pentru că e demiurg programator, Tet indexează indicii nodurilor de la $0$ la $N-1$;
• Se garantează că există drum între toate nodurile din întrebări;
• Cel mai bun concurent o să o câștige pe Jibril.

Punctare

Tet știe că viața e o competiție, așa că vă va puncta în felul următor: Pentru fiecare test veți primi un scor brut, care reprezintă suma scorurilor pentru fiecare întrebare. Pentru fiecare întrebare primiți $1$ punct dacă aflați un drum de lungime optimă, altfel veți primi un număr de puncte calculat după formula: $\large \displaystyle \frac{0.9}{2^{\left(\frac{\text{lungime\_gasita}}{\text{lungime\_optima}}-1\right)\times 4}}$
Știm că sună complicat, dar doar vrea să zică că primiți maxim $0.9$ puncte pentru orice scor neoptim, iar la fiecare abatere de $25$ de la optim vi se înjumătățește punctajul. În timpul probei veți primi acest scor brut, însă pentru punctajul final vom normaliza scorurile brute ale tuturor concurentilor și sursa oficială. Adică veți obține pentru fiecare test scorul vostru brut împărțit la cel mai bun scor pe acel test dintre toate sursele (inclusiv sursa oficială).

Exemplu

nolife.in

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

nolife.out

2 1 2 
4 2 1 4 0 
2 1 4 
2 3 4

Explicație

Această soluție primește punctaj complet pe test, deoarece toate drumurile sunt optime.