CF1510J.Japanese Game

Joseph 非常喜欢日本文化。去年他学习了日本的传统服饰和视觉艺术，现在他正在研究一种叫做 Nonogram 的日本游戏的奥秘。

在该游戏的一维版本中，有一排 $n$ 个空格子，其中一些需要用笔填充。对于每个解法，都有一个称为“轮廓”的描述——一个正整数序列，表示连续被填充的格子的长度。例如，轮廓 $[4, 3, 1]$ 表示有三个连续的被填充区块，长度分别为 $4$、$3$ 和 $1$，并且相邻的区块之间至少有一个空格。

这是 $n = 12$，$p = [4, 3, 1]$ 的一种合法解。

这是错误的解：前四个被填充的格子没有连在一起。

这是错误的解：最后一个被填充的格子前面应该至少有一个空格。

Joseph 发现，对于某些 $n$ 和轮廓 $p$，存在很多种填充格子的方式可以满足轮廓。现在他正在解一个包含 $n$ 个格子的 Nonogram，并且有一个轮廓 $p$。他已经创建了 $p$ 的“掩码”——即所有在每一种解法中都必须被填充的格子。

这是 $n = 12$，$p = [4, 3, 1]$ 的掩码：上图中所有被填充的格子在每一种解法中都必须被填充。

休息过后，Joseph 把原始的轮廓 $p$ 给弄丢了。他现在只有 $n$ 和掩码 $m$。请你帮 Joseph 找到任意一个掩码为 $m$ 的轮廓 $p'$，或者说明不存在这样的轮廓，Joseph 搞错了。

输入仅一行，一个字符串 $m$，表示原始轮廓 $p$ 的掩码。$m$ 的长度为 $n$（$1 \le n \le 100\,000$）。字符串 $m$ 只包含符号 # 和 _，分别表示被填充和空的格子。

如果不存在与掩码 $m$ 匹配的轮廓，输出 $-1$。

否则，第一行输出一个整数 $k$，表示轮廓 $p'$ 中整数的个数。

第二行输出 $k$ 个整数，表示轮廓 $p'$。

• 如果没有任何格子被填充（即 $m$ 全为 _），输出 $0$。
• 如果掩码 $m$ 不能由任何合法的轮廓生成，输出 $-1$。
• 否则，输出任意一个合法的轮廓即可。

数据范围：

$|m| = n$。

$1 \le n \le 10^5$。

由 ChatGPT 4.1 翻译