- محدودیت زمان: ۱.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
اهورا به عرفان n رشته هدیه داده است که iامین آنها si است. آرمین از عرفان q سوال میپرسد. در پرسش iام تعداد جفت y و xهایی را میخواهد که شرایط زیر را داشته باشند:
- 1≤x<y≤pi
- li≤lcp(sx,sy)≤ri
فرض کنید ۲ رشته a و b داریم lcp(a,b) برابر است با طول بلند ترین پیشوند مشترک آنها.
عرفان که همچنان خسته است باز هم از شما میخواهد تا جواب سوالات آرمین را بدهید.
ورودی🔗
در سطر اول عدد n میآید و در n سطر بعدی si (رشتهها متشکل از حروف کوچک انگلیسی هستند) میآید. در سطر بعد q میآید و در q سطر بعد به ترتیب pi، li و ri میآید.
1≤n≤500000
1≤q≤1000000
∑∣si∣≤500000
2≤pi≤n
0≤li≤ri≤1000000
خروجی🔗
در ازای پرسش i تعداد زوجهای نامرتب (x,y) که در شرایط گفته شده صدق میکنند را خروجی دهید.
مثال🔗
ورودی نمونه ۱🔗
خروجی نمونه ۱🔗
- lcp(s1,s2)=1
- lcp(s2,s3)=1
- lcp(s1,s3)=2
پرسش اول. در ۳ رشتهی اول هر ۳ جفت رشتهای که داریم lcp آنها بین ۱ و ۲ است.
پرسش دوم. در ۳ رشتهی اول 0≤lcp(s1,s2)=lcp(s2,s3)≤1
پرسش سوم. در ۲ رشتهی اول lcp(s1,s2)<2