二进制字符串是一个非空的由 '0' 和 '1' 组成的序列，例如 010110, 1, 11101 等。两个二进制字符串 $S$ 和 $T$ 的编辑距离，记作 $edit(S, T)$，是将 $S$ 修改为 $T$ 所需的最少单字符编辑（插入、删除或替换）次数。例如，0011 和 1100 的编辑距离为 4，即 0011 → 011 → 11 → 110 → 1100。1100101 和 1110100 的编辑距离为 2，即 1100101 → 1110101 → 1110100。

Ayu 有一个二进制字符串 $S$。她想找到一个与 $S$ 等长的二进制字符串，使其与 $S$ 的编辑距离最大。形式化地说，她想找到一个二进制字符串 $T_{max}$，满足 $|S| = |T_{max}|$ 且对于所有满足 $|S| = |T|$ 的二进制字符串 $T$，都有 $edit(S, T_{max}) \geq edit(S, T)$。

她需要你的帮助！然而，为了降低任务难度，你只需要返回任意一个与 $S$ 等长的二进制字符串 $T$，使得 $S$ 和 $T$ 的编辑距离大于 $S$ 长度的一半。形式化地说，你必须返回一个二进制字符串 $T$，满足 $|S| = |T|$ 且 $edit(S, T) > \frac{|S|}{2}$。

当然，如果你愿意，仍然可以返回 $T_{max}$，因为可以证明对于任何二进制字符串 $S$，都有 $edit(S, T_{max}) > \frac{|S|}{2}$。这也证明了对于任何二进制字符串 $S$ 都存在解。如果存在多个有效解，你可以输出其中任意一个。

输入格式

输入包含一个二进制字符串 $S$ ($1 \leq |S| \leq 2000$)。

输出格式

在一行中输出一个与 $S$ 等长的二进制字符串 $T$，满足 $edit(S, T) > \frac{|S|}{2}$。

样例

样例输入 1

0011

样例输出 1

1100

说明 1

如上例所示，0011 和 1100 的编辑距离为 4。由于 $4 > \frac{4}{2}$，因此 1100 是该样例的一个有效输出。

样例输入 2

1100101

样例输出 2

0011010