مشترک


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

اهورا به عرفان nn رشته هدیه داده است که iiامین آن‌ها sis_i است. آرمین از عرفان qq سوال می‌پرسد. در پرسش iiام تعداد جفت yy و xxهایی را می‌خواهد که شرایط زیر را داشته باشند:

  1. 1x<ypi1 \leq x \lt y \leq p_i
  2. lilcp(sx,sy)ril_i \leq lcp(s_x, s_y) \leq r_i

فرض کنید ۲ رشته aa و bb داریم lcp(a,b)lcp(a, b) برابر است با طول بلند ترین پیشوند مشترک آن‌ها.

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

ورودی🔗

در سطر اول عدد nn می‌آید و در nn سطر بعدی sis_i (رشته‌ها متشکل از حروف کوچک انگلیسی هستند) می‌آید. در سطر بعد qq می‌آید و در qq سطر بعد به ترتیب pip_i، lil_i و rir_i می‌آید. 1n5000001 \leq n \leq 500\,000 1q10000001 \leq q \leq 1000\,000 si500000\sum |s_i| \leq 500\,000 2pin2 \leq p_i \leq n 0liri10000000 \leq l_i \leq r_i \leq 1000\,000

خروجی🔗

در ازای پرسش ii تعداد زوج‌های نامرتب (x,y)(x, y) که در شرایط گفته شده صدق می‌کنند را خروجی دهید.

مثال🔗

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

3
abb
acd
abd
3
3 1 2
3 0 1
2 2 3
Plain text

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

3
2
0
Plain text
  • lcp(s1,s2)=1lcp(s_1, s_2) = 1
  • lcp(s2,s3)=1lcp(s_2, s_3) = 1
  • lcp(s1,s3)=2lcp(s_1, s_3) = 2

پرسش اول. در ۳ رشته‌ی اول هر ۳ جفت رشته‌ای که داریم lcplcp آن‌ها بین ۱ و ۲ است.

پرسش دوم‌. در ۳ رشته‌ی اول 0lcp(s1,s2)=lcp(s2,s3)10 \leq lcp(s_1, s_2) = lcp(s_2, s_3) \leq 1

پرسش سوم. در ۲ رشته‌ی اول lcp(s1,s2)<2lcp(s_1, s_2) \lt 2