Most Common Browsing Path

You are given a list of webpages visited sequentially by a user. Your task is to determine the most common contiguous browsing path of a given length k. A browsing path is defined as a sequence of k consecutive page visits. In the event of a tie (i.e. when two or more paths occur with the same maximum frequency), output the lexicographically smallest path (when compared as a sequence of strings separated by a single space).

Input Format: The first line contains two integers n and k, where n is the total number of pages visited and k is the length of the browsing path to consider. The second line contains n space-separated strings representing the visited page URLs.

Output Format: A single line containing k space-separated strings that form the most common browsing path.

Note: When comparing paths, use the lexicographical order defined by the standard order on strings.

The solution involves using a sliding window of size k over the list of URLs, counting the frequency of each contiguous subsequence, and then selecting the path with the highest frequency. This can be formally described by the formula:

[ \text{Let } P_i = (a_{i}, a_{i+1}, \dots, a_{i+k-1}) \quad \text{for } 1 \le i \le n-k+1. ]

Then, find a path \( P_x \) such that:

[ \text{count}(P_x) = \max_{1 \le i \le n-k+1} \text{count}(P_i), ]

and if there are multiple such paths, choose the smallest one in lexicographic order.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains two integers n and k, separated by a space.
2. The second line contains n space-separated strings representing the URLs of the pages visited.

outputFormat

Output a single line to standard output (stdout) containing the most common browsing path as k space-separated strings. If multiple paths have the same frequency, output the lexicographically smallest one.

## sample

10 3
home products about home products contact home products about checkout

home products about