Given N words and Q queries. Each query will have a string. You have to print two integers. Index of lexicographical smallest and largest string that contains the query string as substring. If there are multiple lexicographical smallest string, print the smallest index. If there are multiple lexicographical largest string, print the largest index. If there is no word that contains the query string as substring, print 1.
Note: Consider 0-indexing.
Input Format:
First line will contains two integers, N \((1 \le N \le 2 * 10^4)\) and Q \((1 \le Q \le 10^5)\). Next line contains N space separated words, W \((1 \le |W| \le 10^5)\). Next Q lines contain a string S \((1 \le |S| \le 10^5)\) each. Sum of lengths of all the words (\(sum(|W|)\)) is less than or equal to \(10^6\). Sum of lengths of all the query strings (\(sum(|S|)\)) is less than or equal to \(2 * 10^7\).
Output Format:
Print the index of lexicographical smallest and largest string that contains the string S as substring.
Lexicographical order of the given words are:
-
\(aab\)
-
\(abababc\)
-
\(abc\)
\(bc\) is a substring in \(abababc\) and \(abc\). So lexicographical smallest and largest word that contains the \(bc\) as substring are \(abababc\) and \(abc\) respectively.
\(ab\) is a substring in all the words. So lexicographical smallest and largest word that contains the \(ab\) as substring are \(aab\) and \(abc\) respectively.
a is a substring in all the words. So lexicographical smallest and largest word that contains the a as substring are \(aab\) and \(abc\) respectively.
d is a not substring in any of the given words. So the answer is 1.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor