Cho một chuỗi biểu diễn một số ở hệ nhị phân (cơ số 2) hoặc thập lục phân (cơ số 16). Nhiệm vụ của bạn là chuyển đổi số đó sang hệ đếm còn lại.

• Nếu đầu vào là chuỗi nhị phân (chỉ gồm các ký tự '0' và '1'), hãy in ra biểu diễn của nó ở hệ 16, sử dụng chữ in hoa.
• Nếu đầu vào là chuỗi thập lục phân (gồm các ký tự '0' đến '9' và 'A' đến 'F'), hãy in ra biểu diễn của nó ở hệ nhị phân, không có số 0 ở đầu (trừ khi kết quả là 0).

Input

• Gồm một dòng duy nhất là chuỗi biểu diễn số, có độ dài không quá ~10^5~ ký tự.
• Chuỗi này hoặc chỉ gồm các ký tự '0' và '1', hoặc chỉ gồm các ký tự '0' đến '9' và 'A' đến 'F' (chữ in hoa).
• Đảm bảo đầu vào không pha trộn giữa hai hệ và không chứa số 0 thừa ở đầu nếu không cần thiết.

Output

• In ra một dòng duy nhất là chuỗi kết quả sau khi chuyển đổi hệ cơ số.

Ví dụ

Input 1

111100001111

Output 1

F0F

Input 2

1A3

Output 2

110100011

Input 3

0

Output 3

0

Chấm điểm

• Subtask 1 (60 điểm): Chuỗi đầu vào có độ dài không quá 1000 ký tự.

• Subtask 2 (40 điểm): Chuỗi đầu vào có độ dài tối đa ~10^5~ ký tự.