+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۳۲ مگابایت + منبع: *CEOI 2018* **به محدودیت حافظه این سوال دقت کنید.** ---------- زورو که نتوانست پدرش را راضی کند که در درسش پیشرفت داشته است، راه و چاره دیگری برای پول در آوردن پیدا کرد. او قصد دارد یک دنباله به طول $n$ از اعداد طبیعی را بر روی تکه کاغذی بنویسد و به دوست ریاضی دانش بفروشد! از آنجایی که پارسا می‌داند هیچ آدم عاقلی یک دنباله از اعداد را نمی‌خرد، سعی بر چرندبافی درباره ی این دنباله می‌کند. او ادعا می‌کند که اگر تمام زیردنباله‌های متوالی به طول $l$ دنباله اولیه را در نظر بگیریم، تعداد زیادی از آنها $k$*-متشابه* هستند. به دو دنباله هم طول $k$*-متشابه* می‌گوییم اگر تعداد اندیس‌های متناظرشان که یکسان نیستند حداکثر $k$ باشد. حال که زورو دنباله $a$ و عدد $l$ را انتخاب کرده است، می‌خواهد به ازای هر کدام از $n-l+1$ زیردنباله ی متوالی به طول $l$ بداند که با چند دنباله ی دیگر $k$-متشابه است. از آنجایی که او هنوز مقدار $k$ را مشخض نکرده است، $q$ بار از شما می‌خواهد که به ازای یک $k$ خاص پاسخ سوال او را بدهید. # ورودی در خط اول ورودی به ترتیب دو عدد $n$ و $l$ آمده است. در خط دوم ورودی $n$ عدد با فاصله آمده‌اند که نشان دهنده دنباله زورو اند. در خط سوم ورودی $q$، تعداد پرسش‌های زورو آمده است. در هر یک از $q$ خط بعدی یک عدد $k_i$ آمده که پرسش زورو را مشخص می‌کند. $$1 \le l \le n \le 10\ 000$$$$1 \le a_i \le 10^9$$ $$1 \le q \le 100$$ $$0 \le k_i \le l$$ # خروجی در هر یک از $q$ خط خروجی ، $n-l+1$ عدد چاپ کنید که عدد $i$ام سطر $j$ام نشان دهنده تعداد زیردنباله‌های متوالی است که با زیردنباله $i$ام $k_j$-متشابه هستند. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۲۵ | $$n \le 300$$| | ۲ | ۲۰ | $$n \le 2000$$| | ۳ | ۲۰ | $$q = 1, k_1 = 0$$| | ۴ | ۱۵ | $$q = 1$$ | | ۵ | ۲۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 6 2 1 2 1 3 2 1 2 1 2 ``` ## خروجی نمونه ۱ ``` 2 1 1 1 1 4 4 4 4 4 ```