V - Virus

Jedno pekné ráno sa Alica zobudila a zistila, že v I mestách vznikla infekcia, ktorá už zamorila celé mestá a šíri sa ďalej po cestách. Medzi dvoma mestami existuje maximálne jedna cesta. Alica si ako dobrá biochemička uvedomila, že dokáže nájsť protilátku, no bude to trvať čas T. Keďže ju môže infekcia nakaziť tiež, potrebuje utiecť. Samozrejme môže utekať len cez neinfikované mestá a keď sa jej podarí nájsť protilátku, musí sa ešte dostať do nejakého neinfikovaného mesta (alebo tam byť v čase T), aby mohla vyrobiť dosť protilátok.
Pomôžte Alici zistiť či dokáže vytvoriť protilátku včas, alebo celé ľudstvo na Zemi zahynie.

Ku každej spojnici dvoch miest máme navyše dané časy, ktoré potrebuje Alica (C2) a nákaza (C1) na prechod.

Úloha

Pre danú situáciu zistite, či Alica stihne nájsť protilátku.

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 Alica 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 Alica 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 Alica zachráni svet vypíšte „1“ inak vypíšte „0“.

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:

0
0
1
1