NC53175. 销售基因链
描述
译自 JOI Open 2016 T2 「RNA 鎖の販売 / Selling RNA Strands」
基因库中有N个字符串，这些字符串仅由A,G,U,C组成（保证每个字符串都包含四种字母）。
由M组查询，每组查询包含两个字符串P,Q，试求：基因库中有多少个字符串同时存在前缀P和后缀Q。
举个例子，GAC存在前缀G,GA,GAC，存在后缀C,AC,GAC，那么我们可以说：GAC同时存在前缀GA和后缀AC。
由M组查询，每组查询包含两个字符串P,Q，试求：基因库中有多少个字符串同时存在前缀P和后缀Q。
举个例子，GAC存在前缀G,GA,GAC，存在后缀C,AC,GAC，那么我们可以说：GAC同时存在前缀GA和后缀AC。
输入描述
第一行有两个整数N,M。
在接下来的N行中，每行一个字符串，表示基因库中的一个字符串。
在接下来的M行中，每行有两个用空格分隔的字符串，表示一组查询。
输出描述
输出共M行，每行一个整数，表示符合查询条件的字符串的数量。
示例1
输入:
2 3 AUGC AGC G C AU C A C
输出:
0 1 2
说明:
第一组查询：找不到。第二组查询：AUGC满足条件。
第三组查询：AUGC和AGC满足条件。
示例2
输入:
3 3 AA AA AGA AA AA AG GA AG GA
输出:
2 1 1
说明:
注意基因库中的字符串可以重复。示例3
输入:
8 7 GCGCUACCCCAACACAAGGCAAGAUAUA G GGAC GCGG U GCGCUACCCCAACACAAGGCAAGAUGGUC GCCG GCGCUGA GCGCUACCC A GCGCUACCCC AC GCG C GCGC A G G G C G GGA
输出:
1 0 1 2 3 2 0