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

اهورا به عرفان $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$