using System;

using System.Collections;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Text.RegularExpressions;

public static class H171

{   

    //public static readonly string MESSAGE = "GIANTS BEAT DODGERS 10 TO 9 AND PLAY TOMORROW AT 1300";

    public static readonly string MESSAGE = "SPACE THE FINAL FRONTIER THESE ARE THE VOYAGES OF THE BIT STREAM DAILY PROGRAMMER TO SEEK OUT NEW COMPRESSION";

    public static void Main()

    {

        byte[] encoded = Encode(MESSAGE);

        string decoded = Decode(encoded);

        Console.WriteLine("Read message of {0} characters.", MESSAGE.Length);

        Console.WriteLine("Compressed message into {0} bytes ({1:P}).", encoded.Length, Convert.ToDouble(encoded.Length) / MESSAGE.Length);

        for(int i = 0; i < encoded.Length; ++i)

        {

            Console.Write("{0,-4}", encoded[i].ToString("X").PadLeft(2, '0'));

            if (i % 8 == 7) Console.WriteLine();

        }

        Console.WriteLine();

        Console.WriteLine("Decoded message: \"{0}\".", decoded);

        if (decoded == MESSAGE)

            Console.WriteLine("Message matches!");

        else

            Console.WriteLine("Message does not match!");

    }

    public static byte[] Encode(string message)

    {

        if (message.All(IsFiveBitEncodable))

            return EncodeFiveBit(message);

        else

            return EncodeSixBit(message);

    }

    public static string Decode(byte[] message)

    {

        if ((message[0] & 0x01) == 0)

            return DecodeFiveBit(message);

        else

            return DecodeSixBit(message);

    }

    public static byte[] EncodeFiveBit(string message)

    {

        BitArray bits = new BitArray(message.Length * 5 + 1);

        bits[0] = false;

        for(int i = 0; i < message.Length; ++i)

        {

            int bitIndex = i * 5 + 1;

            char c = message[i];

            byte encoded = Encode(c);

            foreach(bool bit in encoded.AsBits(5))

                bits[bitIndex++] = bit;

        }

        int byteCount = bits.Count / 8 + (((bits.Count % 8) == 0) ? 0 : 1);

        byte[] bytes = new byte[byteCount];

        bits.CopyTo(bytes, 0);

        return bytes;

    }

    public static string DecodeFiveBit(byte[] message)

    {

        BitArray bits = new BitArray(message);

        string decoded = "";

        for(int i = 0; (i * 5 + 6) < bits.Count; ++i)

        {

            int baseIndex = i * 5 + 1;

            byte encoded = bits.Cast<bool>().Skip(baseIndex).Take(5).AsByte();

            if (encoded != 0)

            {

                char c = Decode(encoded);

                decoded += c;

            }

        }

        return decoded;

    }

    public static byte[] EncodeSixBit(string message)

    {

        BitArray bits = new BitArray(message.Length * 6 + 1);

        bits[0] = true;

        for(int i = 0; i < message.Length; ++i)

        {

            int bitIndex = i * 6 + 1;

            char c = message[i];

            byte encoded = Encode(c);

            foreach(bool bit in encoded.AsBits(6))

                bits[bitIndex++] = bit;

        }

        int byteCount = bits.Count / 8 + (((bits.Count % 8) == 0) ? 0 : 1);

        byte[] bytes = new byte[byteCount];

        bits.CopyTo(bytes, 0);

        return bytes;

    }

    public static string DecodeSixBit(byte[] message)

    {

        BitArray bits = new BitArray(message);

        string decoded = "";

        for(int i = 0; (i * 6 + 7) < bits.Count; ++i)

        {

            int baseIndex = i * 6 + 1;

            byte encoded = bits.Cast<bool>().Skip(baseIndex).Take(6).AsByte();

            if (encoded != 0)

            {

                char c = Decode(encoded);

                decoded += c;

            }

        }

        return decoded;

    }

    public static bool IsFiveBitEncodable(char c)

    {

        return (c == ' ' ||

            (c >= Convert.ToInt32('A') && c <= Convert.ToInt32('Z')));

    }

    public static byte Encode(char c)

    {

        if (c == ' ')

            return 1;

        else if (c >= Convert.ToInt32('A') && c <= Convert.ToInt32('Z'))

            return Convert.ToByte((c - Convert.ToInt32('A')) + 2);

        else if (c >= Convert.ToInt32('0') && c <= Convert.ToInt32('9'))

            return Convert.ToByte((c - Convert.ToInt32('0')) + 28);

        else

            throw new ArgumentOutOfRangeException("c", c, "Character not in valid encoding set of [A-Z0-9 ].");

    }

    public static char Decode(byte encoded)

    {

        if (encoded == 1)

            return ' ';

        else if (encoded >= 2 && encoded < 28)

            return Convert.ToChar(encoded - 2 + Convert.ToInt32('A'));

        else if (encoded >= 28 && encoded < 38)

            return Convert.ToChar(encoded - 28 + Convert.ToInt32('0'));

        else

            throw new ArgumentOutOfRangeException("encoded", encoded, "Encoding is not valid.");

    }

    public static IEnumerable<bool> AsBits(this byte b, int bitCount)

    {

        int mask = 1 << (bitCount - 1);

        while(mask > 0)

        {

            yield return (b & mask) != 0;

            mask >>= 1;

        }

    }

    public static byte AsByte(this IEnumerable<bool> bits)

    {

        byte b = 0;

        foreach(bool bit in bits)

            b = Convert.ToByte((b << 1) | (bit ? 1 : 0));

        return b;

    }

}