在传奇的《黑客帝国》三部曲中扮演尼奥后,基努·里维斯开始怀疑自己:也许我们真的生活在虚拟现实中?为了确定这是否属实,他需要解决以下问题。
如果一个仅由 0 和 1 组成的字符串包含不同数量的 0 和 1,我们称该字符串为好字符串。例如,1、101、0000 是好的,而 01、1001 和 111000 则不好。
我们得到一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅由零和一组成。我们需要将 $$$s$$$ 切割成尽可能少的子串 $$$s_1, s_2, \ldots, s_k$$$ ,这样它们都是好的。更正式地说,我们必须找到最小的好字符串序列 $$$s_1, s_2, \ldots, s_k$$$,使得它们的串联(连接)等于 $$$s$$$,即 $$$s_1 + s_2 + \dots + s_k = s$$$。
例如,将 110010 切割成 110 和 010 或切割成 11 和 0010 是有效的,因为 110、010、11、0010 都是好的,并且我们不能将 110010 切割成更少数量的子串,因为 110010 本身不好。同时,将 110010 切割成 1100 和 10 是无效的,因为这两个字符串都不好。此外,将 110010 切割成 1, 1, 0010 是无效的,因为它不是最小的,即使所有 $$$3$$$ 字符串都很好。
你能帮助基努吗?我们可以证明解总是存在的。如果有多个最佳答案,请打印其中一个。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1\le n \le 100$$$) — 字符串 $$$s$$$ 的长度。
第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,仅由零和一组成。
输出
在第一行中,输出单个整数 $$$k$$$ ($$$1\le k$$$) — 您已将 $$$s$$$ 切成的最小字符串数。
在第二行中,输出 $$$k$$$ 字符串 $$$s_1, s_2, \ldots, s_k$$$ 以空格分隔。每个字符串的长度必须为正。它们的串联必须等于 $$$s$$$ 并且它们都必须是好的。
如果有多个答案,请打印其中一个。
示例
输入 #1
1 1
输出 #1
1 1
输入 #2
2 10
输出 #2
2 1 0
输入 #3
6 100011
输出 #3
2 100 011
注意
在第一个示例中,字符串 1 根本没有被剪切。因为好,所以条件满足。
在第二个示例中,1 和 0 都很好。由于 10 不太好,所以答案确实很小。
在第三个示例中,100 和 011 都很好。由于 100011 不好,所以答案确实很小。