Broadcast Trigger Span Fusion

A newsroom monitoring tool watches a live transcript for a fixed list of alert trigger phrases. Whenever a trigger phrase appears anywhere in the transcript as a contiguous run of characters, every character it covers must be visually emphasized so producers cannot miss it — a phrase may occur more than once, and occurrences of the same or different phrases may overlap or sit right next to each other. Whenever two emphasized character ranges touch or overlap, they must be fused into one unbroken emphasized range rather than shown as two separate adjacent ones. Given the transcript and the list of trigger phrases, print the transcript with each maximal emphasized range wrapped between the markers << (placed immediately before its first character) and >> (placed immediately after its last character); every character that no trigger phrase ever covers is left exactly as it is.

Input format

• Line 1: the transcript s, a string of lowercase English letters and digits only.
• Line 2: a single integer m — the number of trigger phrases.
• Next m lines: one trigger phrase each, a string of lowercase English letters and digits only (phrases may repeat in the list).

Output format

Print a single line: the transcript s with << and >> inserted around every maximal fused emphasized range, with every other character left untouched and in its original order.

Constraints

• 1 <= length of s <= 500
• 1 <= m <= 50
• 1 <= length of each trigger phrase <= 50
• Matching is case-sensitive substring matching; every occurrence of every phrase counts, including overlapping occurrences of the same or different phrases.

abcxyz123xyz
2
abc
xyz

<<abcxyz>>123<<xyz>>

aaabbb
2
aa
ab

<<aaab>>bb