题目描述
给定n个字符串$s_i$
给出若干次询问, 每次询问第$a$个字符串在第$x$个位置和第$b$个字符串在第$y$个位置上的最长公共前缀长度
保证给出字符串的总长度在$10^6$以内,且字符串中仅含大小写字母
输入格式:
第一行两个整数$n,q$ 接下来n行, 每行一个字符串表示$s_i$ 接下来q行, 每行4个整数a,x,b,y如上所述
输出格式:
一行, 一个数表示最少需要的步骤数
样例输入:
3 3 aaaaa abcdaa bcd 1 1 2 5 2 1 3 1 2 2 3 1
样例输出:
2 0 3
样例解释:
第一次询问aaaaa与aa的最长公共前缀显然是aa
第二次询问abcdaa与bcd的最长公共前缀显然是空串
第三次询问bcdaa与bcd的最长公共前缀显然是bcd
数据范围
保证 $ \sum |s_i| <= 10^6, 1<=n<=5*10^5, q <= 2*10^5 $
子任务1:(200分)
无其他限制
