Egy ország városait kétirányú utak kötik össze, melyek használatáért díjat kell fizetni. Bármelyik városból bármelyik városba el lehet jutni az utakon. Két város között legfeljebb egy közvetlen út van. Néhány városban szupermarket is található. Az országba $Q$ család érkezik, akik különböző vagyoni helyzetűek. Minden család szeretne olyan városba költözni, ahol nincs szupermarket. Ha egy család vagyoni helyzete $K$, akkor csak olyan városban lakhat, ahonnan el tud menni bevásárolni egy szupermarketbe összesen legfeljebb $K$ útdíjat fizetve (az oda- és visszautat számolva). Adjuk meg minden családra, hogy hány olyan város van az országban, ahol nincs szupermarket, mégsem tud odaköltözni a család, mert túl költséges lenne egy szupermarketbe való eljutás a vagyoni helyzetükhöz képest.
Bemenet: Az első sor tartalmazza a városok $N$ számát, az utak $M$ számát, a szupermarketet tartalmazó városok $D$ számát és a családok $Q$ számát. A következő $M$ sor mindegyike három számot tartalmaz: az első kettő azon városok indexe, amik között az adott út van, a harmadik szám pedig az út használatának díja. A következő sorban $D$ szám van: azon városok indexei, amikben van szupermarket. A következő sorban $Q$ szám van: az $i$-edik szám az $i$-edik család vagyoni helyzetét leíró $K$ érték. A városokat 0-tól $N-1$-ig indexeljük.
Kimenet: Egy sorba írjunk ki $Q$ darab számot: a sor $i$-edik száma adja meg, hogy az $i$-edik család hány olyan városba nem tud költözni a vagyoni helyzete miatt, ahol nincs szupermarket.