Zajko Hopsajko má problém. Potrebuje kvôli Veľkej noci rôzne behať medzi inými zajacmi a vybavovať tu tamto, tam zas hento \dots lenže vonku nakydalo snehu tak, že to na Veľkú noc až pekné nie je. A Hopsajka potom oziabajú labky a drkocú mu zuby. A ak ste už niekedy videli zajačie zuby, tak viete, že to nie je žiadna sranda, keď drkocú.
Našťastie sú aspoň niektoré zajačie nory prepojené podzemnými chodbami. Vtedy sa Hopsajko snehu úplne vyhne. Niekedy však nemá na výber a musí aspoň časť cesty prejsť vonkajškom. Hopsajko by rád vonku strávil čo najmenej času.
Navyše ani vonku si nemôže behať len tak. Snehové záveje sú na neho priveľké, zapadol by a zahynul. Môže nanajvýš tak využiť niektoré z už vyšľapaných cestičiek.
Na vstupe dostanete popis podzemných chodbičiek medzi norami a popis cestičiek v snehu. Následne dostanete niekoľko otázok. Každá otázka sa pýta na niektoré dve nory. Vašou úlohou je:
V prvom riadku vstupu sú tri kladné celé čísla: počet nôr $n$, počet spojení $m$ a počet otázok $q$. Platí $1\leq n\leq 4000, 1\leq m\leq 40000$ a $1\leq q\leq 30$. Nory sú očíslované od 0 po $n-1$, vrátane.
Nasleduje $m$ riadkov, každý z nich popisuje jedno spojenie. Každé spojenie je
popísané tromi číslami $x$, $y$, $d$ a jedným písmenom $T$. Čísla $x$, $y$ sú čísla
dvoch rôznych nôr, ktoré dotyčné spojenie spája. Číslo $d$ je čas, ktorý Hopsajkovi
trvá toto spojenie (ľubovoľným smerom) použiť. Písmeno $T$ je P ak je to
spojenie chodba vedúca Pod zemou a N ak je to v snehu prešľapaná cestička
Nad zemou. Platí, že $d$ je celé a $0\leq d\leq 10^6$.
Každý z posledných $q$ riadkov obsahuje jednu otázku: dve čísla nôr $u$, $v$.
Pre každú otázku vypíšte jeden riadok. Ak sa Hopsajko vôbec nevie dostať
z nory $u$ do nory $v$, vypíšte -1 -1, v opačnom prípade
vypíšte medzerou oddelené $x$ a $y$ definované vyššie.
2 1 1
0 1 30 P
0 1
0 30
2 1 1
0 1 30 N
0 1
30 30
4 2 3
0 1 30 N
2 1 30 P
0 1
0 2
0 3
30 30
30 60
-1 -1