+ محدودیت زمان: ۱.۵ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
اهورا به عرفان $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$