小Petya非常喜欢和小玛莎一起玩。最近他收到了妈妈送给他的一款名为《零一》的游戏作为礼物。佩蒂亚立即邀请玛莎和他一起玩这个游戏。
在游戏开始之前,几张牌从左到右排成一行。每张卡片包含一个数字:0 或 1。玩家轮流移动,玛莎先移动。在每次移动过程中,玩家应该从桌子上移除一张牌并移动所有其他牌,以缩小被移除的牌留下的间隙。例如,如果在某人移动之前,桌子上的牌组成了序列 01010101,那么在取出第四张牌后(牌从 1 开始编号),序列将如下所示:0100101。
当桌上只剩下两张牌时游戏结束。这些卡上的数字决定了二进制表示法中的数字:最高有效位位于左侧。玛莎的目标是最小化数量,佩蒂亚的目标是最大化数量。
比赛开始前发生了一起不愉快的事故。孩子们把果汁洒在一些卡片上,卡片上的数字变得模糊了。每一张被损坏的卡片上都可能写有 0 或 1。考虑数字初始排列的所有可能变体(在果汁溢出之前)。对于每个变体,假设 Petya 和 Masha 都处于最佳状态,让我们找出游戏结束时还剩下哪两张牌。写在这两张卡片上的一对有序数字称为结果。您的任务是找到初始数字排列的所有变体的结果集。
输入
第一行包含一个字符序列,每个字符可以是“0”、“1”或“?”。这个顺序决定了牌在桌子上从左到右的初始排列。字符“?”意味着给定的牌在比赛前就被破坏了。序列的长度范围为 2 到 105(包含 2 和 105)。
输出
打印所有可能的初始数字排列的结果集。将每个可能的结果打印在一行上。每个结果应由两个字符表示:游戏结束时留下的卡片上写的数字。结果应按字典顺序升序排序(参见第一个示例)。
示例
输入 #1
????
输出 #1
00 01 10 11
输入 #2
1010
输出 #2
10
输入 #3
1?1
输出 #3
01 11
注意
在第一个示例中,所有 16 种数字排列变体都是可能的。对于变体 0000,结果是 00。对于变体 1111,结果是 11。对于变体 0011,结果是 01。对于变体 1100,结果是 10。无论所有其他变体的结果如何,我们正在寻找的集合都将包含所有 4 个可能的结果。
在第三个示例中,只有 2 个数字排列变体是可能的:111 和 101。对于变体 111,结果是 11。对于变体 101,结果是 01,因为在第一回合,玛莎可以移除左侧的第一张牌,之后游戏将结束。