سوال ۳

خانم دکتر، خانم نسبتن ولخرجی است و به خرید کردن علاقه بسیار زیادی دارد. او در کشوری با $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 \neq v_i$)
• در $i$امین خط از $t$ خط بعد یک عدد $a_i$ آمده‌است که نشان دهنده شهر محل زندگی طلب‌کار $i$ام است.
• $1 \leq n \leq 5 * 10^4, 0 \leq m \leq 8 * 10^4$
• $0 \leq t \leq n$
• $1 \leq k \leq 100$
• $1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 100$
• $1 \leq a_i \leq n$

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

• زیر مسئله اول (۳۰ نمره): $1 \leq n \leq 400$
• زیر مسئله دوم (۷۰ نمره - بدون فیدبک):‌ بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال قبل