Chú voi con và các bit (Little Elephant and Bits)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho biểu diễn nhị phân của một số nguyên dương, không có số $0$ ở đầu và có ít nhất hai chữ số. Phải xóa đúng một bit, giữ nguyên thứ tự các bit còn lại. Hãy tạo số nhị phân lớn nhất có thể.

Input

Một dòng chứa chuỗi nhị phân $s$, với $2 \le |s| \le 10^5$.

Output

In chuỗi nhị phân lớn nhất thu được sau khi xóa đúng một bit.

Subtask

Các giới hạn chung:

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

• $s$ chỉ gồm 0, 1 và ký tự đầu là 1.

• Subtask 1 (20 điểm): $|s| \le 20$

• Subtask 2 (30 điểm): $|s| \le 5000$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

110010

Output

11010

Giải thích

Xóa chữ số 0 đầu tiên tại vị trí thứ ba cho kết quả 11010. Xóa một bit 1 sớm hơn sẽ làm tiền tố nhỏ đi.