Unique Valid Subsequences in Gene Sequence

Given a gene sequence of length \(n\) and a list of \(m\) candidate subsequences, your task is to determine which candidate subsequences appear in the gene sequence as valid subsequences. A string \(s\) is considered a subsequence of a string \(t\) if \(s\) can be obtained by deleting zero or more characters from \(t\) without changing the order of the remaining characters.

Your program should output all unique valid subsequences found in the gene sequence, sorted in lexicographical order. Note that duplicate candidate subsequences should be considered only once.

inputFormat

The input is read from standard input and has the following format:

1. The first line contains an integer \(n\), the length of the gene sequence.
2. The second line contains the gene sequence, a string of length \(n\).
3. The third line contains an integer \(m\), the number of candidate subsequences.
4. The fourth line contains \(m\) space-separated strings, representing the candidate subsequences.

outputFormat

Print all unique candidate subsequences that are valid subsequences of the gene sequence, sorted in lexicographical order. The subsequences should be printed on a single line, separated by a single space. If no valid subsequence is found, print an empty line.

4
abac
3
ab ac bc

ab ac bc