Zero-One

题意翻译

## 题目描述 在游戏开始之前，几张牌从左到右排成一行放在一张桌子上。每张牌包含`0`或`1`。玩家轮流移动（Masha 先移动）。在每一次移动中，玩家会移除一张牌。例如，在某人移动之前，表上的卡片形成了一个序列`01010101`，那么在第 $4$ 张卡片被移动之后（卡片从 $1$ 开始编号），序列将变成`0100101`。 当只剩 $2$ 张牌时，游戏结束。这些卡上的数字决定了二进制中的数字。Masha 的目标是最小化这个数字；Petya 的目标是最大化这个数字。 现在，有些卡片上的数字变得模糊了，记作`?`。假设 Petya 和 Masha 都玩得很好，请你找出游戏结束时剩下的 $2$ 张牌所有可能的情况。 ## 输入格式 只有 $1$ 行，包含一系列字符，每个字符可以是`0`，`1`或`?`。字符的顺序决定了牌摆放的初始顺序。 $2 \leq$ 字符长度 $\leq 10^5$。 ## 输出格式 输出所有可能的结果，每行 $1$ 个。按字典序升序排列。 ## 说明/提示 样例组 #1 解释：有 $16$ 种可能的排列。如果一开始牌面为`0000`，结果是`00`；如果一开始牌面为`1111`，结果是`11`；如果一开始牌面为`0011`，结果是`01`；如果一开始牌面为`1100`，结果是`10`。总共只有 $4$ 种不同的结果。 样例组 #3 解释：只有 $2$ 种可能的数字排列：`111`和`101`。如果一开始牌面为`111`，结果是`11`；如果一开始牌面为`101`，结果是`01`。Masha 可以在第一次操作时取出最左边的牌，然后游戏结束。

题目描述

Little Petya very much likes playing with little Masha. Recently he has received a game called "Zero-One" as a gift from his mother. Petya immediately offered Masha to play the game with him. Before the very beginning of the game several cards are lain out on a table in one line from the left to the right. Each card contains a digit: 0 or 1. Players move in turns and Masha moves first. During each move a player should remove a card from the table and shift all other cards so as to close the gap left by the removed card. For example, if before somebody's move the cards on the table formed a sequence 01010101, then after the fourth card is removed (the cards are numbered starting from 1), the sequence will look like that: 0100101. The game ends when exactly two cards are left on the table. The digits on these cards determine the number in binary notation: the most significant bit is located to the left. Masha's aim is to minimize the number and Petya's aim is to maximize it. An unpleasant accident occurred before the game started. The kids spilled juice on some of the cards and the digits on the cards got blurred. Each one of the spoiled cards could have either 0 or 1 written on it. Consider all possible variants of initial arrangement of the digits (before the juice spilling). For each variant, let's find which two cards are left by the end of the game, assuming that both Petya and Masha play optimally. An ordered pair of digits written on those two cards is called an outcome. Your task is to find the set of outcomes for all variants of initial digits arrangement.

输入输出格式

输入格式

The first line contains a sequence of characters each of which can either be a "0", a "1" or a "?". This sequence determines the initial arrangement of cards on the table from the left to the right. The characters "?" mean that the given card was spoiled before the game. The sequence's length ranges from $ 2 $ to $ 10^{5} $ , inclusive.

输出格式

Print the set of outcomes for all possible initial digits arrangements. Print each possible outcome on a single line. Each outcome should be represented by two characters: the digits written on the cards that were left by the end of the game. The outcomes should be sorted lexicographically in ascending order (see the first sample).

输入输出样例

输入样例 #1

????

输出样例 #1

00
01
10
11

输入样例 #2

1010

输出样例 #2

10

输入样例 #3

1?1

输出样例 #3

01
11

说明

In the first sample all 16 variants of numbers arrangement are possible. For the variant 0000 the outcome is 00. For the variant 1111 the outcome is 11. For the variant 0011 the outcome is 01. For the variant 1100 the outcome is 10. Regardless of outcomes for all other variants the set which we are looking for will contain all 4 possible outcomes. In the third sample only 2 variants of numbers arrangement are possible: 111 and 101. For the variant 111 the outcome is 11. For the variant 101 the outcome is 01, because on the first turn Masha can remove the first card from the left after which the game will end.