• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

اخیرا جاعلی پیدا شده است که فیش جعلی پرداخت مالیات درست می‌کند. با این روش مردم یک فیش جعلی، که نشان می‌دهد آن‌ها مالیاتشان را پرداخته‌اند، از این جاعل می‌گیرند و به اداره‌ی مالیات نشان‌ می‌دهند و دیگر مالیات نمی‌دهند. این پدیده‌ی شوم باعث کسادی بازار مرد مالیاتچی و بیکاری او شده است. متاسفانه مرد مالیاتچی که نمی‌تواند جلوی این اتفاق را بگیرد می‌خواهد بداند که حداقل چقدر وقتش خالی شده‌ است تا بتواند شغل دوم مناسبی پیدا کند. از این رو میخواهد تعداد فیش‌های اصل را بداند.

یک فیش مالیاتی رشته‌ای به طول $n$ است که تنها از ۰ و ۱ درست شده است.

حال فیشی تقلبی است که حداقل یکی از رشته‌های زیر، حداقل یک بار، در آن آمده باشد:

$110, 101, 111, 011$

برای فهم بیشتر به نمونه‌ها و توضیحشان مراجعه کنید.

دقت کنید که هر فیشی که تقلبی نباشد اصل است.

ورودی🔗

در تنها سطر ورودی $n$ آمده است که نمایانگر اندازه‌ی رشته‌ی فیش‌ها می‌باشد. $1 \le n \le 100 \ 000$

خروجی🔗

در تنها سطر خروجی باقیمانده‌ی تعداد فیش‌های اصل بر $10^9 + 7$ را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4

خروجی نمونه ۱🔗

6

توضیح نمونه‌ی اول

فیش‌های زیر تقلبی اند: $0011, 0101, 0110, 0111, 1010, 1011, 1100, 1101, 1110, 1111$ فیش‌های زیر اصل هستند: $0000, 0001, 0010, 0100, 1000, 1001$

پس از کل ۱۶ حالت فیش‌ها، ۱۰ تا تقلبی و ۶ تا اصل هستند که چون سوال تعداد اصل‌ها را خواسته‌ است جواب برابر ۶ می‌شود.

ورودی نمونه ۲🔗

3

خروجی نمونه ۲🔗

4

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

در اداره مالیات $n$ مالیات‌چی وجود دارد.

مالیات‌چی $i$ ام می‌تواند از $a_i$ نفر خاص در شهر مالیات بگیرد.

متاسفانه به علت کمبود بودجه اداره مالیات، ما برای سال بعد فقط می‌توانیم $m$ تا از مالیات‌چی‌ها را نگه داریم، حالا از شما می‌خواهیم به رییس اداره مالیات بگویید در صورتی که به بهترین شکل این $m$ نفر را انتخاب کند حداکثر از چند نفر می‌تواند مالیات بگیرد.

همچنین می‌دانیم بعضی از اشخاصی که بعضی از مالیات‌چی‌ها می‌توانند از آن‌ها مالیات بگیرند مشترک هستند.

مثلا مالیات چی اول و دوم هر کدام می‌توانند به ترتیب از ۷ و ۸ نفر در شهر مالیات بگیرند اما ۳ نفر از این افراد مشترک است، پس چنانچه بخواهیم دو نفر مالیات‌چی نگه داریم و این دو نفر را انتخاب کنیم ما از ۱۲ نفر می‌توانیم مالیات بگیریم نه از ۱۵ نفر.

برای فهم بهتر سوال بخش ورودی را بخوانید.

ورودی🔗

در یک خط $n$ به شما داده می‌شود که تعداد مالیات‌چی‌هاست و سپس $m$ که تعداد مالیات‌چی‌هایی است که برای سال بعد می‌توانیم داشته باشیم.

سپس در خط بعد $n$ عدد که $a_i$ هاست به شما داده می‌شود.

در خط سوم $q$ به شما داده می‌شود و در $q$ خط بعدی در هر خط ابتدا یک عدد $t_i$ می‌آید و سپس $t_i$ تا عدد که اندیس مالیات‌چی‌هاست و یک عدد $k_i$ که یعنی آن $t_i$ تا مالیات‌چی در $k_i$ تا از مردم شهر با هم مشترک هستند.

** دقت کنید که اشتراک‌هایی که به شما داده می‌شوند از هم جدا و کاملا مستقل هستند؛ یعنی مثلا اگر مالیاتچی‌های ۱ و ۲ و ۳ در ۵ نفر و مالیاتچی‌های ۱ و ۲ در ۴ نفر با هم اشتراک داشته باشند، طبیعتا این ۴ نفر کاملا مستقل از آن ۵ نفر بوده و هیچ اشتراکی ندارند. **

$1 \le m \le n \le 20$ $1 \le q \le 10$ $2 \le t_i \le n$ $1 \le a_i \le 100$

برای فهم بهتر توضیح نمونه ۱ را بخوانید.

خروجی🔗

در یک خط بیشینه‌ی تعداد نفراتی که می‌شود سال بعد از آن‌ها مالیات گرفت را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

5 3
15 20 25 30 24
5
2 1 2 7
3 1 2 3 3
2 2 3 2
2 3 4 5
2 4 5 6 

خروجی نمونه ۱🔗

68

بهترین حالت این است که مالیات‌چی دوم و چهارم و پنجم را انتخاب کنیم، که از آنجایی که مالیات چی ۴ و ۵ در ۶ نفر باهم مشترک هستند جواب آخر برابرست با ۶ - ۲۰ + ۳۰ + ۲۴.

ورودی نمونه ۲🔗

3 3
3 3 3
1
3 1 2 3 2

خروجی نمونه ۲🔗

5

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

متاسفانه باخبر شدیم که آقای مالیاتچی، به کشور فلان فرار مالیاتی کرده است!

حیف که دیر فهمیدیم وگرنه زودتر فرد مناسبی را جایگزین او می‌کردیم. از این رو این سوال شسته و رفته خدمت شما:

به یک رشته خوب می‌گوییم اگر حرفی در آن وجود داشته باشد که حداقل به اندازه‌ی نصف طول آن رشته آمده باشد. برای مثال رشته‌ی $ab$ خوب است در حالی که رشته‌ی $abc$ خوب نیست. حال به شما یک رشته می‌دهیم و شما باید تعداد زیررشته‌های خوب آن را خروجی دهید.

ورودی🔗

در تنها سطر ورودی یک رشته که تنها از حروف کوچک انگلیسی درست شده است آمده است. طول این رشته بین ۱ تا $10^5$ می‌باشد.

خروجی🔗

در تنها سطر خروجی تعداد زیررشته‌های خوب رشته‌ی ورودی را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

aaa

خروجی نمونه ۱🔗

6

ورودی نمونه ۲🔗

z

خروجی نمونه ۲🔗

1

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

تولد، تولد، تولد مرد مالیات‌چی‌ست. مرد مالیاتچی در حال تدارک مراسم است و می‌خواهد ببیند که چند نفر را می‌تواند دعوت کند.

طبق رسم سنتی مالیاتچیان، در آخر هر مراسم تولدی باید یک صندلی‌بازی نیز انجام شود. البته صندلی‌بازی مالیاتچیان مقداری با صندلی‌بازی عادی متفاوت است. آنان به این صورت بازی می‌کنند:

ابتدا تعداد $n$ صندلی (به تعداد مالیاتچیان دعوت شده) در یک ردیف کنار هم قرار داده شده و از ۱ تا $n$ شماره‌گذاری می‌شود. سپس عدد $z$ که نمایانگر میزان جذابیت بازی می‌باشد انتخاب می‌شود و هر کدام از $n$ مالیاتچی عددی یکتا بین $z + 1$ و $n + z$ برمیگزینند به طوری که هر مالیاتچی دقیقا یک عدد داشته باشد. حال هر مالیاتچی می‌تواند روی هر کدام از صندلی‌هایی که باقیمانده شماره‌ی خودش بر شماره‌ی صندلی برابر صفر می‌باشد بنشیند. هدف بازی این است که تمامی مالیاتچیان به طور همزمان برروی صندلی بنشینند و هیچ صندلی‌ای خالی نماند. دقت کنید که روی هر صندلی حداکثر یک نفر می‌تواند بنشیند.

متاسفانه اگر همه‌ی مالیاتچیان نتوانند همزمان روی صندلی بنشینند، مراسم به هم می‌ریزد. از این رو مرد مالیاتچی می‌خواهد به تعداد درستی آدم دعوت کند. او تعداد سناریو در ذهنش دارد و می‌خواهد به ازای هر کدام بداند که آیا در آن سناریو مراسم به درستی و خوبی برگزار خواهد شد یا خیر.

ورودی🔗

در سطر اول ورودی $t$ می‌آید که نمایانگر تعداد سناریو‌های در ذهن مرد مالیاتچی می‌باشد.

سپس در $t$ سطر، در هر سطر، دو عدد طبیعی $n$ و $z$ با فاصله از می‌آید که به ترتیب نمایانگر تعداد صندلی‌ها و میزان جذابیت بازی می‌باشد. $1 \le t \le 100$ $1 \le n, z \le 10^9$

خروجی🔗

به ازای هر سناریو اگر این سناریو اجرایی است و مراسم به درستی برگزار خواهد شد Yes وگرنه No خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

2
1 3
4 2

خروجی نمونه ۱🔗

Yes
Yes

در سناریوی اول یک صندلی با شماره‌ ۱ و یک مالیاتچی با شماره‌ ۴ وجود دارد که این مالیاتچی می‌تواند بر روی صندلی بنشیند چرا که ۴ بر ۱ بخش‌پذیر است.

در سناریو دوم چهار صندلی با شماره‌ ۱، ۲، ۳ و ۴ وجود دارد و شماره‌ افراد نیز ۳، ۴، ۵، ۶ می‌باشد که به این صورت تمامی افراد روی صندلی می‌نشینند:

مالیاتچی شماره‌ ۳ برروی صندلی شماره ۳، مالیاتچی شماره ۴ برروی صندلی شماره ۴، مالیاتچی شماره ۵ برروی صندلی شماره‌ ۱ و مالیاتچی شماره‌‌ ۶ برروی صندلی ۲.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

به علت اعتراض فراوان مردم به مالیات، اداره‌ی مالیات نحوه محاسبه‌ی مالیات را عوض کرده است تا مثلا بگوید که به اعتراضات رسیدگی کرده است.

در این محاسبه‌ی جدید مالیات، افراد با توجه به درآمد و سطح سوادشان مالیات می‌دهند. مثلا مالیات شخصی با سطح سوادی $k$ و درآمد $x$ به این صورت حساب می‌شود:

تابع $f(x, k)$ را به این صورت تعریف میکنیم که اگر $x$ زوج باشد $f(x, k) = x / 2$ و اگر $x$ فرد باشد $f(x, k) = x + k$.

حال دنباله‌ی زیر را در نظر بگیرید:

$x, f(x, k), f(f(x, k), k), f(f(f(x, k), k), k), ...$

مقدار مالیات شخصی با درآمد $x$ و سطح سواد $k$ برابر اولین عضو دنباله‌ی بالا است که مقدار آن کمتر یا مساوی $k$ می‌باشد. اندیس این عضو از دنباله را $g(x, k)$ فرض میکنیم.(دنباله از ۰ شماره‌گذاری می‌شود) اگر مرد مالیاتچی از چنین شخصی مالیات بگیرد به اندازه‌ی $g(x, k)$ می‌تواند کارمزد برای خودش بگیرد.

به همان علت که اداره‌ی مالیات همچین تابعی را برای محاسبه‌ی مالیات برگزیده است، میزان سواد افراد در شهر مرد مالیاتچی عددی فرد می‌باشد.

مرد مالیاتچی می‌خواهد از یک محله ثروتمند پول بگیرد. تمامی افراد این محله دارای سطح سواد $d$ می‌باشند. میزان درآمد افراد این محله بین $l$ تا $r$ می‌باشد (دقیقا به ازای هر عدد در این بازه یک نفر است که این درآمد را دارد).

حال به مرد مالیاتچی بگویید که در مجموع او چقدر می‌تواند پول به عنوان کارمزد بسلفد!

ورودی🔗

در تنها سطر ورودی سه عدد $l$، $r$ و $d$ آمده است.

عدد $d$ فرد می‌باشد.

$1 \le d \le 100 \ 000$ $1 \le l \le r \le 10^{16}$

خروجی🔗

در تنها سطر خروجی میزان درآمد مرد مالیاتچی را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

6 6 1

خروجی نمونه ۱🔗

4

دنباله‌ی $f(6, 1)$ به این صورت است:

$6, 3, 4, 2, 1, 2, 1, 2, 1, 2, ...$

ورودی نمونه ۲🔗

1 5 3

خروجی نمونه ۲🔗

4