Trong quá trình truyền dữ liệu, vì một số yếu tố môi trường có thể dễ dàng làm ảnh hưởng đến dữ liệu trong suốt quá trình lưu thông. Sự phổ biến của mạng Internet và WiFi làm lượng dữ liệu truyền tải hàng ngày tăng kỷ lục. Và theo tỷ lệ tương ứng, lượng dữ liệu bị truyền sai cũng tăng vọt. Mục tiêu chính của bài toán này là xác định và (nếu có thể) sửa lỗi trong các tin nhắn được gửi qua mạng WiFi.

Kỹ thuật được sử dụng trong bài toán để xác định lỗi là kiểm tra chẵn lẻ; Có thể được mô tả như sau: Cho một bản tin sẽ được gửi đi qua đường truyền. Do đặc điểm đường truyền, bản tin sẽ được truyền dưới dạng một chuỗi các bit 0, 1 nối tiếp. Trước khi gửi S, thêm một bit B được thêm vào cuối của chuỗi ký tự nhị phân của S sao cho bản tin nhận được sẽ có tổng số bit 1 là chẵn. Nếu S có số chẵn các bit 1, bit thêm B sẽ có giá trị 0. Ngược lại, nếu S có một số lẻ Của các bit có giá trị 1, B sẽ có giá trị 1. Bằng cách này, sau khi chèn bit B, thông điệp S' sẽ có một số chẵn của các bit có giá trị 1.

Khi người nhận nhận được tin nhắn S', số bit 1 của tin nhắn sẽ được đếm. Nếu số lượng là chẵn, nó có nghĩa là tin nhắn đã được chuyển thành công. Nếu không, nó có nghĩa là thông điệp đã bị sửa đổi và không chính xác.

Nhiệm vụ của bạn là viết một thuật toán làm cho việc chèn thêm bit B vào trong tin nhắn S, đảm bảo rằng sau khi chèn tin S có một số bit chẵn có giá trị 1.

Đầu vào

Mỗi trường hợp kiểm tra bao gồm một dòng chứa thông điệp S, có ít nhất 1 và nhiều nhất là 10000 bit.

Đầu ra

In một dòng chứa thông điệp S với bit thêm B.

VÍ DỤ 1

INPUT 1

10

OUTPUT 1

101

VÍ DỤ 2

INPUT 2

000110

OUTPUT 2

0001100

VÍ DỤ 3

INPUT 3

0

OUTPUT 3

00