O!--字符串中的最小、最大 ?

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

这是个什么问题呢?DP,贪心,数据结构,图论,数论还是计算几何?管他呢,反正胖巨巨都会,虽然胖巨巨走得早。
 
给出n个字符串Si,由于寒假比较无聊,胖胖开始计算这n个Si中有多少个满足min(ord(R),ord(L)) < ord(Si)<= max(ord(L),ord(R))。
ord(T) = (T0- 'a'+1)*26^(Len-0) + (T1- 'a'+1)*26^(Len-1) + (T2- 'a'+1)*26^(Len-2) +......+ (Ti- 'a'+1)*26^(Len-i) +......(0 <= i < Len,Len表示字符串T的长度)。
说明:min(x,y),max(x,y)分别表示选取x,y中较小值和较大值。

Input

多组输入,对于每组输入:
第一行输入两个整数n,m(1 <= n <= 300000,m <= 10000)。
接下来n行,每行包含一个字符串Si。
接下来m行每行包含两个字符串L,R,用一个空格隔开。
L,R,Si仅包含'a','b','c',L,R,Si的长度len∈[1,10]。

Output

对于每组输入,输出m行,每行包含一个整数代表答案。

Sample Input

3 3
ab
abab
ababab
ab abab
ab ababab
a ababab

Sample Output

1
2
3

Hint

 

Source

zmx