L - Liek

Jedno pekné ráno sa Adolf zobudil a zistil, že v niekoľkých mestách prepukla nová infekcia, ktorá už zamorila celé mestá a šíri sa ďalej po cestách. Biochemik Adolf si uvedomil, že dokáže nájsť liek, no bude to trvať nejaký čas. Keďže ho môže infekcia nakaziť tiež, potrebuje utiecť. Samozrejme môže utekať len cez neinfikované mestá a keď sa mu podarí nájsť liek, musí sa ešte dostať do nejakého neinfikovaného mesta (alebo tam byť v čase nájdenia lieku), aby mohol liek aj vyrobiť .
Pomôžte Adolfovi zistiť či dokáže vytvoriť liek včas, alebo celé ľudstvo na Zemi zahynie.

Medzi dvoma mestami existuje maximálne jedna cesta. Ku každej spojnici dvoch miest máte dané časy, ktoré potrebuje Adolf aj nákaza na prechod.

Úloha

Pre danú situáciu zistite, či Adolf stihne nájsť a vyrobiť liek.

Vstup

V prvom riadku vstupu je celé číslo N – počet testovacích vstupov.
Nasleduje N sekcií, každá z nich začína riadkom s 5 celými číslami X,T,I,M,C oddelených medzerami:
- X je mesto, v ktorom sa Adolf nachádza
- T je čas na vytvorenie protilátky
- I je počet infikovaných miest
- M je počet miest
- C je počet ciest
V ďalšom riadku nasleduje I medzerami oddelených čísel, zoznam nakazených miest (mestá sú číslované od nuly).
Nasleduje C riadkov s popisom ciest, každý obsahuje 4 čísla A,B,C1,C2:
- A,B sú dve rôzne mestá, ktoré cesta spája
- C1 je čas, ktorý trvá nákaze prejsť
- C2 je čas, ktorý potrebuje Adolf na prechod cestou

1 ≤ N ≤ 10
1 ≤ T < 2³¹
1 ≤ C ≤ 500 000
0 ≤ A, B, X < M ≤ 1 000
1 ≤ I < M
0 ≤ C1, C2 < 2³¹

Výstup

Pre každý vstup vypíšte jeden riadok výstupu. Ak Adolf zachráni svet vypíšte znak „+“, inak vypíšte „-“.

Príklad

Vstup:

4
0 8 1 5 6
3
0 1 6 4
0 4 4 5
1 2 11 18
1 4 6 8
2 3 2 4
3 4 1 3
0 2 1 2 1
0
0 1 5 18
4 7 2 7 10
1 3
0 1 2 6
0 3 3 7
1 2 8 10
1 3 1 3
2 3 5 12
2 4 1 8
2 6 3 12
3 4 6 9
4 5 2 5
5 6 3 7
4 2 2 5 4
0 3
0 1 3 7
1 2 4 3
1 4 1 2
2 3 4 9

Výstup:

-
-
+
+