- محدودیت زمان: ۱.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
اهورا به عرفان \(n\) رشته هدیه داده است که \(i\)امین آنها \(s_i\) است. آرمین از عرفان \(q\) سوال میپرسد. در پرسش \(i\)ام تعداد جفت \(y\) و \(x\)هایی را میخواهد که شرایط زیر را داشته باشند:
- \(1 \leq x \lt y \leq p_i\)
- \(l_i \leq lcp(s_x, s_y) \leq r_i\)
فرض کنید ۲ رشته \(a\) و \(b\) داریم \(lcp(a, b)\) برابر است با طول بلند ترین پیشوند مشترک آنها.
عرفان که همچنان خسته است باز هم از شما میخواهد تا جواب سوالات آرمین را بدهید.
ورودی
در سطر اول عدد \(n\) میآید و در \(n\) سطر بعدی \(s_i\) (رشتهها متشکل از حروف کوچک انگلیسی هستند) میآید. در سطر بعد \(q\) میآید و در \(q\) سطر بعد به ترتیب \(p_i\)، \(l_i\) و \(r_i\) میآید. \[1 \leq n \leq 500\,000\] \[1 \leq q \leq 1000\,000\] \[\sum |s_i| \leq 500\,000\] \[2 \leq p_i \leq n\] \[0 \leq l_i \leq r_i \leq 1000\,000\]
خروجی
در ازای پرسش \(i\) تعداد زوجهای نامرتب \((x, y)\) که در شرایط گفته شده صدق میکنند را خروجی دهید.
مثال
ورودی نمونه ۱
3
abb
acd
abd
3
3 1 2
3 0 1
2 2 3
خروجی نمونه ۱
3
2
0
- \(lcp(s_1, s_2) = 1\)
- \(lcp(s_2, s_3) = 1\)
- \(lcp(s_1, s_3) = 2\)
پرسش اول. در ۳ رشتهی اول هر ۳ جفت رشتهای که داریم \(lcp\) آنها بین ۱ و ۲ است.
پرسش دوم. در ۳ رشتهی اول \(0 \leq lcp(s_1, s_2) = lcp(s_2, s_3) \leq 1\)
پرسش سوم. در ۲ رشتهی اول \(lcp(s_1, s_2) \lt 2\)