E. Concatenation with intersectiontime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputVasya had three strings a, b and s, which consist of lowercase English letters. The lengths of strings a and b are equal to n, the length of the string s is equal to m. Vasya decided to choose a substring of the string a, then choose a substring of the string b and concatenate them. Formally, he chooses a segment [l_1, r_1] (1 \leq l_1 \leq r_1 \leq n) and a segment [l_2, r_2] (1 \leq l_2 \leq r_2 \leq n), and after concatenation he obtains a string a[l_1, r_1] + b[l_2, r_2] = a_{l_1} a_{l_1 + 1} \ldots a_{r_1} b_{l_2} b_{l_2 + 1} \ldots b_{r_2}.Now, Vasya is interested in counting number of ways to choose those segments adhering to the following conditions:  segments [l_1, r_1] and [l_2, r_2] have non-empty intersection, i.e. there exists at least one integer x, such that l_1 \leq x \leq r_1 and l_2 \leq x \leq r_2;  the string a[l_1, r_1] + b[l_2, r_2] is equal to the string s. InputThe first line contains integers n and m (1 \leq n \leq 500\,000, 2 \leq m \leq 2 \cdot n) — the length of strings a and b and the length of the string s.The next three lines contain strings a, b and s, respectively. The length of the strings a and b is n, while the length of the string s is m.All strings consist of lowercase English letters.OutputPrint one integer — the number of ways to choose a pair of segments, which satisfy Vasya's conditions.ExamplesInput6 5aabbaabaaaabaaaaaOutput4Input5 4azazazazazazazOutput11Input9 12abcabcabcxyzxyzxyzabcabcayzxyzOutput2NoteLet's list all the pairs of segments that Vasya could choose in the first example:  [2, 2] and [2, 5];  [1, 2] and [2, 4];  [5, 5] and [2, 5];  [5, 6] and [3, 5]; 
Input6 5aabbaabaaaabaaaaa
Output4
['data structures', 'hashing', 'strings', 'two pointers', '*2700']