← Home 
write a go solution for Description:
Let LCP(s,t) be the length of the longest common prefix of strings s and t. Also let s[x...y] be the substring of s from index x to index y (inclusive). For example, if s= "abcde", then s[1...3]= "abc", s[2...5]= "bcde".

You are given a string s of length n and q queries. Each query is a pair of integer sets a_1,a_2,...,a_k and b_1,b_2,...,b_l. Calculate sumlimits_i=1^i=ksumlimits_j=1^j=lLCP(s[a_i...n],s[b_j...n]) for each query.

Input Format:
The first line contains two integers n and q (1<=n,q<=2*10^5) — the length of string s and the number of queries, respectively.

The second line contains a string s consisting of lowercase Latin letters (|s|=n).

Next 3q lines contains descriptions of queries — three lines per query. The first line of each query contains two integers k_i and l_i (1<=k_i,l_i<=n) — sizes of sets a and b respectively.

The second line of each query contains k_i integers a_1,a_2,...a_k_i (1<=a_1<a_2<...<a_k_i<=n) — set a.

The third line of each query contains l_i integers b_1,b_2,...b_l_i (1<=b_1<b_2<...<b_l_i<=n) — set b.

It is guaranteed that sumlimits_i=1^i=qk_i<=2*10^5 and sumlimits_i=1^i=ql_i<=2*10^5.

Output Format:
Print q integers — answers for the queries in the same order queries are given in the input.

Note:
Description of queries:

1. In the first query s[1...7]=abacaba and s[2...7]=bacaba are considered. The answer for the query is LCP(abacaba,abacaba)+LCP(abacaba,bacaba)+LCP(bacaba,abacaba)+LCP(bacaba,bacaba)=7+0+0+6=13.
2. In the second query s[1...7]=abacaba, s[2...7]=bacaba, s[3...7]=acaba and s[7...7]=a are considered. The answer for the query is LCP(abacaba,a)+LCP(bacaba,a)+LCP(acaba,a)=1+0+1=2.
3. In the third query s[1...7]=abacaba are compared with all suffixes. The answer is the sum of non-zero values: LCP(abacaba,abacaba)+LCP(abacaba,acaba)+LCP(abacaba,aba)+LCP(abacaba,a)=7+1+3+1=12.
4. In the fourth query s[1...7]=abacaba and s[5...7]=aba are considered. The answer for the query is LCP(abacaba,abacaba)+LCP(abacaba,aba)+LCP(aba,abacaba)+LCP(aba,aba)=7+3+3+3=16.. Output only the code with no comments, explanation, or additional text.