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 and Q . Next line contains N space separated words, W . Next Q lines contain a string S each. Sum of lengths of all the words () is less than or equal to . Sum of lengths of all the query strings () is less than or equal to .
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:
is a substring in and . So lexicographical smallest and largest word that contains the as substring are and respectively.
is a substring in all the words. So lexicographical smallest and largest word that contains the as substring are and respectively.
a is a substring in all the words. So lexicographical smallest and largest word that contains the a as substring are and respectively.
d is a not substring in any of the given words. So the answer is 1.