Gene

Problem Description

In high-school biology, a restriction site is a specific base sequence on a gene, and a restriction endonuclease can recognize this sequence and cut the gene into two pieces at the corresponding cutting position.

There is a restriction enzyme named $\texttt{EcoRI}$ whose recognition sequence is GAATTC, and whose cutting position is between G and A.

You are given a gene sequence of length $n$ (a string consisting only of A/T/G/C). Please determine how many parts $\texttt{EcoRI}$ can cut this sequence into under ideal conditions, and output the index of the base to the left of each cutting position.

The indices of the gene sequence are defined from left to right as $1, 2, 3, \dots, n$.

Input Format

The first line contains a positive integer $n$, the length of the gene sequence.

The second line contains a string of length $n$ representing the gene sequence, guaranteed to contain only the four characters A/T/G/C.

Output Format

The first line outputs a positive integer $x$, meaning $\texttt{EcoRI}$ can cut the given sequence into $x$ parts under ideal conditions.

The second line outputs the $x - 1$ positive integers in ascending order, the indices of the base to the left of each cutting position.

Sample Input

15
GATCGGAATTCTTCA

Sample Output

2
6

Sample Explanation

Clearly, for this sample it is easy to find the recognition sequence and cutting site of $\texttt{EcoRI}$: $\texttt{GATCG}\color{red}{\texttt{G{\downarrow}AATTC}}\texttt{TTCA}$.

Therefore, the original gene sequence can be cut into $2$ parts, and the index of the base G to the left of the cutting position is $6$.

Constraints

$6 \le n \le 10^7$

This is essentially a template KMP problem — it could not be more of a template. (If you cannot understand the problem statement, you may read the sample explanation.)