You are given 2 strings text and pattern, consisting of lowercase english letters.
Let str be any substring of pattern having some length len greater than 0. Then the starting index of each occurence, if any, of str in text is contained in the set S(len).
You have to answer multiple queries. For each query, you need to determine the Kth samllest element among all the elements in S(L), S(L+1),......, S(R-1), S(R) (duplicates, if any, are retained). If the answer is not possible, then print -1.
Note:
Input Format:
The first line contains the string text. (1 ≤ |text| ≤ 10^5)
The second line contains the string pattern. (1 ≤ |pattern| ≤ 10^3)
The third line contains an integer denoting the number of queries, Q. (1 ≤ Q ≤ 10^5)
Then follow Q lines.
Each of the Q lines contains 3 integers L, R and K. (1 ≤ L ≤ R ≤ |pattern|, 1 ≤ K ≤ 10^8)
Output Format:
For each query, output the Kth smallest element is S(L),S(L+1),....,S(R-1),S(R).
If the answer is not possible, then output -1.
S(1) = {0,1,2,3,4,5}
S(2) = {0,1,2,3}
S(3) = {0,1,2}
S(4) = {0,1}
S(5) = {0}
Query 1: S(1),S(2) = {0,0,1,1,2,2,3,3,4,5}
The 7th smallest element is 3.
Query 2: S(2),S(3),S(4),S(5) = {0,0,0,0,1,1,1,2,2,3}
There are only 10 elements. So the output is -1.
Query 3: S(2),S(3),S(4),S(5) = {0,0,0,0,1,1,1,2,2,3}
The 9th smallest element is 2.