题目描述

给定一个长度为 $n$ 的 01 串，请把它划分为尽量少的连续段，满足：

• 每段内 1 的个数都是奇数；
• 每段的长度不超过 $m$。

但你需要对 所有 $m\in[1,n]$ 分别求出最少段数（或判断无解）。

输入格式

本题多组数据：

• 第一行是数据组数 $T$。
• 对于每组数据：输入一个 01 串（其长度为 $n$）。

输出格式

对每组数据输出一行 $n$ 个整数，用空格隔开：

• 第 $i$ 个数表示 $m=i$ 时的最少段数；
• 若无解输出 -1。

输出量较大，请使用快速输出方式。

4
01101
0000
11111
1101001

-1 3 3 3 1
-1 -1 -1 -1
5 5 3 3 1
-1 4 4 2 2 2 2

样例解释

设 $[l,r]$ 表示把 $a_l,a_{l+1},\dots,a_r$ 划为一段。

对第一组测试数据：

• $m=1$ 时不存在合法划分；
• $m=2,3,4$ 时可划分为 $[1,2],[3,3],[4,5]$；
• $m=5$ 时可划分为 $[1,5]$。

对第四组测试数据：

• $m=2$ 时可划分为 $[1,1],[2,3],[4,5],[6,7]$；
• $m=4$ 时可划分为 $[1,4],[5,7]$； 且可以证明不存在更优解。

数据范围与提示

对所有数据：

• $1\le T\le 10^4$
• $1\le n\le 10^6$
• 单个测试点中 $n$ 的总和不超过 $2\times 10^6$

测试点分布（按题面整理）：