Зборовни префикси

Префикс на даден збор е секој дел од тој збор што се добива со отстранување на одреден број знаци од неговиот крај, но без целосно да се избрише зборот. На пример, за зборот "zhuchko", можни префикси се "z", "zh", "zhu", "zhuc", "zhuch", "zhuchk" и "zhuchkо", но празниот стринг не се смета за префикс.

Нека ви е дадена низа S од N зборови, сите составени од мали латинични букви - од a до z. Ќе добиете Q прашанки поврзани со претходно дадените N зборови.

Секоја прашанка е претставена со 2 различни цели броеви X и Y (1 ≤ X, Y ≤ N), кои го означуваат следното прашање: Колку зборови составени од малите латинични букви (од a до z) постојат, такви што тие се префикс на зборот SX или на зборот SY, но не се префикс на ниту еден од останатите N - 2 зборови во низата S.

Ваша задача е да одговорите точно на секоја од прашанките.



Влез

Во првиот ред се дадени два цели броја N и Q (1 ≤ N ≤ 200 000 и 1 ≤ Q ≤ 200 000) - бројот на зборови во низата S и бројот на прашанки. Притоа, вкупниот број на букви во сите зборови ќе биде до 200 000.

Во секој од следните N редови е даден по еден збор Si - низа (стринг) од мали латинични букви од a до z.

Во следните Q редови дадени се по два различни цели броеви Xi, Yi (1 ≤ Xi, Yi ≤ N), кои ја опишуваат i-тата прашанка.



Излез

Отпечатете Q редови, секој со по еден цел број - одговорот на соодветната прашанка.



Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 256 megabytes



Примери


влез
6 2
mouse
mou
mother
misunderstanding
mister
mission
1 2
5 6
излез
3
7


Објаснување за првиот пример:
За (X = 1, Y = 2) → "mouse" и "mou"
Можни зборови кои се префикси или на “mouse” или на “mou” се зборовите “m”, “mo”, “mou”, “mous” и “mouse”. Но зборовите “m” и “mo” се исто така префикси на зборот “mother”, па затоа нив не ги броиме во одговорот.
Одговор: 3
За (X = 5, Y = 6) → "mister" и "mission"
Можни зборови кои се префикси или на “mister” или на “mission” се зборовите “m”, “mi”, “mis”, “mist”, “miste”, “mister”, “miss”, “missi”, “missio” и “mission”. Но зборовите “m”, “mi” и “mis” се исто така префикси на зборот “misunderstanding”, па затоа нив не ги броиме во одговорoт.
Одговор: 7


 Submit your code