• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت
• منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر

خانم دکتر، خانم نسبتاً ولخرجی است و به خرید کردن علاقه بسیار زیادی دارد. او در کشوری با $n$ شهر زندگی می کند که شهرهایش با $m$ جاده دو طرفه به هم متصل هستند. هر جاده نیز طول مشخصی دارد.

اخیراً خانم دکتر به علت خرید های زیادش بدهی بالا آورده و $t$ چک دست طلب‌کارهایش دارد. طلب کار $i$ام در شهر $a_i$ زندگی‌ می‌کند و چک این طلب‌کار در روز $i$ام برگشت می خورد. هر طلب کار بعد از برگشت خوردن چکش می خواهد خانم دکتر را پیدا کند و او را به زندان بیندازد. ولی از آن جایی که طلب‌کارها آدم های تنبلی هستند، در صورتی به دنبال خانم دکتر می روند که فاصله شهرشان تا شهر خانم دکتر کمتر از $k$ باشد.

حال آقای مهندس، همسر مهربان خانم دکتر، در هر یک از $t$ روز می خواهد بداند که خانم دکتر را به چند شهر می‌تواند فراری دهد که از دست طلب‌کارها در امان باشد. به او کمک کنید!

ورودی

در خط اول ورودی چهار عدد $n$ و $m$ و $t$ و $k$ آمده‌است که به ترتیب تعداد شهرها، تعداد جاده‌ها، تعداد طلب‌کارها و حداکثر مسافتی که طلب‌کارها حاضرند طی کنند را نشان می‌دهد.

در $m$ خط بعد در هر خط ۳ عدد $u_i$ و $v_i$ و $w_i$ آمده است که وجود یک جاده دو طرفه به طول $w_i$ از شهر $u_i$ به شهر $v_i$ را نشان می دهد. (بین هر دو شهر حداکثر یک جاده وجود دارد و $u_i \ne v_i$)

در $i$ امین خط از $t$ خط بعد یک عدد $a_i$ آمده‌است که نشان دهنده شهر محل زندگی طلب‌کار $i$ام است.

$$1 \le n \le 50\ 000$$ $$0 \le m \le 80\ 000$$

$$0 \le t \le n$$

$$1 \le k \le 100$$

$$1 \le u_i, v_i \le n$$ $$1 \le w_i \le 100$$

$$1 \le a_i \le n$$

خروجی

در $t$ خط خروجی در خط $i$ام تعداد شهر هایی که خانم دکتر در روز $i$ در امان است را چاپ کنید.

زیرمسئله‌ها

مثال

ورودی نمونه ۱

7 6 3 3
3 4 1
3 5 1
4 7 1
5 1 1
3 6 1
6 2 2
4
3
6

خروجی نمونه ۱

2
1
0

ورودی نمونه ۲

1 0 1 1
1

خروجی نمونه ۲

0

(۲۴امین دوره المپیاد کامپیوتر - آزمون یکم - ۱۳۹۳/۰۵/۲۳)