====== سوال ۳ ====== خانم دکتر، خانم نسبتن ولخرجی است و به خرید کردن علاقه بسیار زیادی دارد. او در کشوری با $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$ * زیر مسئله دوم (۷۰ نمره - بدون فیدبک):‌ بدون محدودیت اضافی ===== محدودیت‌ها ===== * محدودیت زمان: ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ | 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 | * [[سوال ۲|سوال قبل]]