DNA Pattern Search

You are given a DNA sequence of length \(n\) consisting of uppercase English letters, and a pattern string, also consisting of uppercase letters. Your task is to find all starting positions in the DNA sequence where the exact pattern occurs.

If the pattern does not occur in the DNA sequence at all, output \(-1\). Otherwise, output the zero-based indices of all occurrences separated by a single space.

Note: The DNA sequence and the pattern are given as strings without any spaces. The value of \(n\) satisfies \(1 \leq n \leq 10^5\). You may assume that the length of the pattern is at most \(n\).

inputFormat

The input consists of three lines:

1. The first line contains an integer \(n\), representing the length of the DNA sequence.
2. The second line contains a DNA sequence of length \(n\), consisting only of uppercase letters.
3. The third line contains the pattern string to be searched in the DNA sequence.

outputFormat

If the pattern is found, output a single line containing the starting indices of each occurrence separated by a single space. If the pattern is not found in the sequence, output \(-1\).

10
ACGTACGTAG
ACG

0 4