题目描述

小明和小红在做一个数字游戏。 小明写出一个二进制数， 小红必须交换其中的两个数字来得出一个新的二进制数（必须进行交换操作且只能交换两个数字）。 小明想知道所有得到的新二进制数中第二大的数是几。 小红知道怎么计算最大的数， 但是她不知道怎么计算第二大的数， 你能帮帮她么？

输入格式

共一行。 为小明给出的一个二进制数， 不包含前导零。 保证所有输入的二进制数通过交换一定能产生至少两个比原数更大的数字。

输出格式

共一行。 为小红执行交换操作后第二大的二进制数。

样例

1110011

1111001

样例解释

交换后最大的二进制数为 1111010， 交换的是第四位的 0 和第 7 位的 1。 第二大的二进制数为 1111001， 交换的是第四位的 0 和第 6 位的 1。

输入解释

如数字:11110000， 不论如何交换， 交换后一定会变小， 这种输入情况不会存在； 再比如数字： 101000， 交换后只会产生一个比他大的数字 110000， 无法通过交换得到第二个比原数字更大的数， 这种输入情况也不会存在。

数据范围

• 对于 30%的数据， 保证输入的二进制数长度$\le$10。
• 对于 60%的数据， 保证输入的二进制数长度$\le$1000。
• 对于 100%的数据， 保证输入的二进制数长度$\le$1000000。

来源

BCSP-X 2024 小学组 T2