在本题中，我们考虑 DNA 分子中的核苷酸序列，即由字符 ‘A’、‘C’、‘G’ 和 ‘T’ 组成的字符串。对于每个自然数 $k$，共有 $4^k$ 种不同的 $k$ 字母核苷酸序列。对于固定的自然数 $k$，如果给定的核苷酸序列 $s$ 包含所有 $k$ 字母核苷酸序列作为其子序列（不一定连续），则称该序列 $s$ 为 $k$-丰富（$k$-rich）的。

给定一个长度为 $n$ 的核苷酸序列 $s$。对于范围 $[1, n]$ 内的每个自然数 $k$，输出将 $s$ 修改为 $k$-丰富序列所需更改的最少字符数。注意，对于每个 $k$，结果是独立计算的。

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 的核苷酸序列 $s$，仅由字符 ‘A’、‘C’、‘G’ 和 ‘T’ 组成。

输出应包含 $n$ 个整数；第 $k$ 个整数表示将 $s$ 修改为 $k$-丰富核苷酸序列所需更改的最少字符数。如果对于给定的 $k$，无法通过修改 $s$ 中的字符达到要求，则第 $k$ 个数应为 $-1$。

样例

输入格式 1

8
AAGTAGAA

输出格式 1

1 3 -1 -1 -1 -1 -1 -1

说明

对于 $k = 1$，我们可以通过一次修改将 $s$ 变为例如 AAGTCGAA。所得核苷酸序列包含所有单字母单词作为子序列（换句话说，四种字母各出现至少一次），因此它是 1-丰富的。

对于 $k = 2$，我们可以通过三次修改将 $s$ 变为例如 2-丰富核苷酸序列 CAGTTGAC。注意，我们不能将 $s$ 修改为例如序列 CCGTTGAA，因为它不包含双字母单词 AC 作为子序列。

对于 $k > 2$，无法使序列 $s$ 成为 $k$-丰富的。