B'To do this, he took the string t and a set of n strings s_1 , s_2 , s_3 , ..., s_n . Philip has m queries, in the i th of them, Philip wants to take a substring of the string t from l_i th to r_i th character, and count the number of its substrings that match some string from the set. More formally, Philip wants to count the number of pairs of positions a , b , such that l_i <= a <= b <= r_i , and the substring of the string t from a th to b th character coincides with some string s_j from the set. A substring of the string t from a th to b th character is a string obtained from t by removing the a - 1 character from the beginning and |t| - b characters from the end, where |t| denotes the length of the string t . Philip has already solved this problem, but can you? The first line contains two positive integers n and m ( 1 <= n, m <= 500 ,000 ) -- the number of rows in the set and the number of queries. The second line contains a single string t consisting of lowercase letters of the English alphabet ( 1 <= |t| <= 5 cdot 10^6 ). The following n lines describe the strings from the set. In the i th of them, a single string s_i is given, consisting of lowercase letters of the English alphabet. Denote by S the total length of all strings from the set. It is guaranteed that S <= 10^6 , as well as that all strings of s_i are different. In the following lines, queries are entered. The i th of them contains two positive integers l_i and r_i ( 1 <= l_i <= r_i <= |t| ) -- the left and right border of the substring t from the i -th query. In a single line, print m integers, i th of them should be equal to the answers to the i th query. In the first example, the first query requires the entire string to '...