Broadcast Codeword Span Finder

A monitoring station recorded one long transmission as a single lowercase string. Engineers keep a fixed list of known codewords they are watching for. Whenever a contiguous block of the transmission exactly equals one of the codewords, that block counts as a detected span, identified by its inclusive 0-indexed start and end position within the transmission. The same codeword can be detected many times at different positions, spans from different codewords may overlap or nest inside one another, and the codeword list may itself contain repeats — but each distinct (start, end) span must be reported only once even if several codewords (or duplicate entries) all match that exact span. Report every detected span, sorted first by ascending start position and, among spans sharing a start, by ascending end position.

Input format

Line 1: the transmission string text (1 <= length <= 200), lowercase English letters only. Line 2: an integer n (1 <= n <= 50), the number of codewords. Next n lines: one codeword each, lowercase English letters only, each of length between 1 and 50.

Output format

First line: an integer k, the number of distinct detected spans. Next k lines: two space-separated integers start end for each span, in the required sorted order. If no span is detected, print 0 and nothing else.

Constraints

• 1 <= text.length <= 200
• 1 <= n <= 50
• 1 <= codeword.length <= 50
• All characters are lowercase English letters ('a'-'z').

themissionlogbegins
4
mission
log
begins
miss

4
3 6
3 9
10 12
13 18

aaa
3
a
aa
aaa

6
0 0
0 1
0 2
1 1
1 2
2 2