Find max equal-frequency block count for each prefix

Given a string S of length n (e.g., uppercase letters), for every prefix P = S[0..i] (for i = 0..n-1), compute the maximum integer k such that:

• The prefix length |P| is divisible by k .
• P can be partitioned into k contiguous blocks of equal length L = |P|/k .
• For every character c , the number of occurrences of c is the same in every block .

Equivalently, all k blocks must have identical character-frequency vectors (so each block is an anagram of the others).

Task: Output an array ans[1..n] where ans[i] is the maximum k for the prefix of length i.

Input

• A string S

Output

• n integers, where the i -th integer is the answer for prefix S[0..i-1] .

Example

S = "ABBA"

• Prefix "A" → k=1
• Prefix "AB" → cannot split into 2 equal-frequency blocks ( "A" vs "B" ), so k=1
• Prefix "ABB" → k=1
• Prefix "ABBA" → split into "AB" | "BA" , both have {A:1,B:1} , so k=2

Output: 1 1 1 2.