F. Дуфф бол галзуу

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дуфф найзуудынхаа дэргэд галзуу юм шиг байдаг. Энэ нь заримдаа Малек Дуффын найзуудаас ямар нэгэн шалтгаангүйгээр чихэр авахад хүргэдэг.

Түүнд $n$ найз бий. Түүний $i$-р найзын нэр нь $s_{i}$ (найзуудын нэр давтагдаж болно). Дуфф Малекаас найзуудаасаа $q$ удаа чихэр авахыг хүснэ. Дуфф ууртай байна гэвч тэр тодорхой дүрмийн дагуу аашилдаг. Тэр Малекаас найз $k$-аасаа чихэр аваад өг гэж хэлэхийг хүслээ гэж бодъё. Тэгвэл Дуфф $l$ болон $r$ гэсэн хоёр тоо сонгох ба Малекд яг ширхэг чихэр найзаасаа ав гэж хэлэх ба $occur(t, s)$ нь $s$ тэмдэгт мөр дунд $t$ тэмдэгт мөр хэдэн удаа тохиолдох тоог заана.

Малек Дуффаас ирсэн хүсэлт бүрийн хувьд хэдэн чихэр авахыг тооцоолох боломжгүй. Иймд тэр таныг туслахыг гуйж байна. Түүнд хүсэлт бүрийн хувьд хэдэн чихэр авахыг нь хэлж өгнө үү.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ болон $q$ ($1 ≤ n, q ≤ 10^{5}$) байна.

Дараагийн $n$ мөр нэрүүдийг агуулна. Эдгээр мөрүүдийн $i$-р мөр бүр Англи цагаан толгойн жижиг үсгээс бүтэх $s_{i}$-г агуулна().

Дараагийн $q$ мөр хүсэлтүүдийг агуулна. Мөр бүрт гурван бүхэл тоон утга $l, r$ болон $k$ (Малек Дуффын $k$-р найзаас ширхэг чихэр авах ёстой) байна.

Гаралт

Нэг мөрөнд нэг хүсэлтийн хариуг хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 5
a
ab
abab
ababab
b
1 5 4
3 5 4
1 5 2
1 5 3
1 4 1
Гаралт
12
6
3
7
1
Сэтгэгдлүүдийг ачааллаж байна...