BASE32 Decoding

Interview

Time limit1sMemory limit256 MB

Summary

Print the original string S from its given Base32 encoding with padding.

Level: Easy3 of 10
Topics: Bit manipulation, String, Implementation
Solved: No attempts yet

Problem

BASE32 is an encoding that represents a byte array with 32 characters. It cuts the original data into 5 bit pieces and maps each piece to one of 32 characters, the 26 uppercase letters A to Z and the 6 digits 2 to 7. When the length of the original data is not a multiple of 5 bytes, the last piece is padded with zero bits, and = characters are appended so that the length of the encoded result is a multiple of 8.

Given the BASE32 encoding of a string S, write a program that prints S.

Input

The first line contains the result of encoding the string S with BASE32. S consists only of uppercase letters, lowercase letters and digits, and its length is at most 50.

Output

Print the string S on the first line.

Examples2

Example 1
Input
```
KBZG6Z3SMFWW22LOM4ZTE===
```
Expected output
```
Programming32
```
Example 2
Input
```
IE======
```
Expected output
```
A
```