+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اهورا به عرفان $n$ رشته هدیه داده است که $i$امین آن‌ها $s_i$ است. آرمین از عرفان $q$ سوال می‌پرسد. در پرسش $i$ام تعداد جفت $y$ و $x$هایی را می‌خواهد که شرایط زیر را داشته باشند: 1. $1 \leq x \lt y \leq p_i$ 2. $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$

حل سؤال در بانک سؤالات