Little Elephant and Bits

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Given the binary representation of a positive integer with no leading zero and at least two digits, delete exactly one bit while preserving the order of all remaining bits. Produce the largest possible binary number.

Input

One line contains a binary string $s$, with $2 \le |s| \le 10^5$.

Output

Print the largest binary string obtainable after deleting exactly one bit.

Subtasks

General constraints:

• $2 \le |s| \le 10^5$.

• $s$ contains only 0, 1, and starts with 1.

• Subtask 1 (20 points): $|s| \le 20$

• Subtask 2 (30 points): $|s| \le 5000$

• Subtask 3 (50 points): No additional constraints.

Examples

Input

110010

Output

11010

Explanation

Deleting the first 0, at the third position, gives 11010. Deleting an earlier 1 would make the prefix smaller.