• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۳۲ مگابایت
• منبع: 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