Ambush Planning in Byteburg

In the town of Byteburg, there are \( n \) houses along a river numbered from 1 to \( n \). Two notorious criminals, Bitie and Bytie, live in houses of the same color, but their exact color is unknown. They always set out on a raid: Bitie leaves his house and walks downstream (towards larger numbers) while Bytie walks upstream (towards smaller numbers). As they traverse the houses before meeting, each robber will break into exactly one house for each of a set of tip colors provided in an anonymous tip. In other words, if the tip colors are \( T = \{t_1,t_2,\dots,t_k\} \), then on the raid Bitie will rob one house of each color in \( T \) from the houses between his starting house and the meeting house, and similarly Bytie will rob one house of each color in \( T \) from the houses between the meeting house and his starting house. Note that the robbed houses must lie strictly between the starting house and the meeting house.

Your task is to help detective Bythony determine all possible meeting places for the bandits. A meeting place is a house with index \( m \) (with \( 1 < m < n \)) for which there exists a pair of houses \( i \) and \( j \) (with \( i < m < j \)) such that:

• The houses \( i \) and \( j \) (the bandits’ houses) are of the same color.
• The segment of houses from \( i+1 \) to \( m-1 \) contains at least one occurrence of every color in \( T \) (so Bitie can rob them).
• The segment from \( m+1 \) to \( j-1 \) contains at least one occurrence of every color in \( T \) (so Bytie can rob them).

If there is at least one color \( X \) for which such a pair exists, then the house \( m \) is a valid meeting place. Output all valid meeting house indices in increasing order; if none exist output -1.

Input Note: The house colors and tip colors are represented by single characters. Use prefix sums or other techniques to efficiently check for the existence of the tip colors within the given segments.

inputFormat

The input consists of three lines:

• The first line contains two integers \( n \) and \( k \) where \( n \) is the number of houses and \( k \) is the number of tip colors.
• The second line contains \( n \) space-separated characters representing the colors of the houses in order.
• The third line contains \( k \) space-separated characters representing the tip colors \( T \) (the colors of the houses that will be robbed during the raid).

outputFormat

Output a single line containing the indices of all possible meeting houses in increasing order separated by a single space. If there is no valid meeting place, output -1.

sample

7 2
G R B Y R B G
R B

4