Memorize Words Segment

Reimu has \(n\) words she wants to memorize. She also has an article containing \(m\) words. She wants to find a contiguous segment of the article that covers the maximum number of distinct words from her memorize list (each word counted at most once even if it appears multiple times). In case there are multiple segments that achieve the same maximum distinct count, she desires the shortest segment (i.e. with the minimum number of words). If there is still a tie, choose the one with the smallest starting index.

Input Format (\(\text{format}\)): The first line contains two integers \(n\) and \(m\). The second line contains \(n\) words (separated by spaces) which are the words Reimu wants to memorize. The third line contains \(m\) words separated by spaces representing the article.

Problem Goal (\(\text{value}\)): Find the optimal continuous segment of the article that contains the maximum number of distinct words from the memorize list. Output the starting and ending indices (1-indexed) of this segment. If none of the memorize words appear in the article, output 1 1.

inputFormat

Input (\(\text{format}\)):

n m
word1 word2 ... word_n
article_word1 article_word2 ... article_word_m

Example:

3 7
apple banana orange
grape apple grape banana grape orange grape

outputFormat

Output (\(\text{format}\)):

L R

Where L and R are the 1-indexed starting and ending indices of the chosen subarray of the article.

sample

3 7
apple banana orange
grape apple grape banana grape orange grape

2 6