题目描述

给定一个长度不超过 1000 的二进制格雷码字符串，编写一个程序将其转换为相应的二进制码字符串并输出。

格雷码是一种二进制编码方式，其中任意两个连续的数只有一位不同。二进制格雷码和普通二进制码之间的转换遵循以下规则：

• 二进制码的最高位与格雷码的最高位相同。
• 从最高位开始，二进制码的每一位可以通过格雷码的当前位与二进制码的上一位进行异或运算得到。

输入格式

一个字符串 G，表示格雷码的二进制形式。字符串的长度不超过 1000，且仅包含字符 '0' 和 '1'。

输出格式

一个字符串，表示输入格雷码对应的二进制码。

样例输入

100

样例输出

Ob111

说明

样例中，输入的格雷码是 100。其对应的二进制码是0b111。(0b表示二进制数)

提示

格雷码的转换可以通过以下步骤实现：

1. 将格雷码字符串 G 反转。
2. 将反转后的格雷码的最高位作为二进制码的最高位。
3. 从反转后的格雷码的次高位开始，每一位通过与上一位的二进制码进行异或运算得到当前位的二进制码。
4. 最终将计算出的二进制码再反转，得到所需的结果。