+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت + منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر ----- خانم دکتر، خانم نسبتاً ولخرجی است و به خرید کردن علاقه بسیار زیادی دارد. او در کشوری با $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$ در امان است را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳۰ | $ n \le 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 ``` (۲۴امین دوره المپیاد کامپیوتر - آزمون یکم - ۱۳۹۳/۰۵/۲۳)