خانم دکتر، خانم نسبتن ولخرجی است و به خرید کردن علاقه بسیار زیادی دارد. او در کشوری با n شهر زندگی می کند که شهرهایش با m جاده دو طرفه به هم متصل هستند. هر جاده نیز طول مشخصی دارد.
اخیرن خانم دکتر به علت خرید های زیادش بدهی بالا آورده و t چک دست طلبکارهایش دارد. طلب کار iام در شهر ai زندگی میکند و چک این طلبکار در روز iام برگشت می خورد. هر طلب کار بعد از برگشت خوردن چکش می خواهد خانم دکتر را پیدا کند و او را به زندان بیندازد. ولی از آن جایی که طلبکارها آدم های تنبلی هستند، در صورتی به دنبال خانم دکتر میروند که فاصله شهرشان تا شهر خانم دکتر کمتر از k باشد.
حال آقای مهندس، همسر مهربان خانم دکتر، در هر یک از t روز می خواهد بداند که خانم دکتر را به چند شهر میتواند فراری دهد که از دست طلبکارها در امان باشد. به او کمک کنید!
در 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 |