using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{
    using System;

    public class Cipher
    {

        private static readonly String key = "hill";
        private static readonly int[][] mat = new int[][]
        {
            new int[] {key[0] - 'a' , key[1] - 'a' },
            new int[] {key[2] - 'a' , key[3] - 'a' }
        };

        private const int MOD = 26;

        public String Encrypt(String str)
        {
            str += '?';
            int len = str.Length;
            var sb = new StringBuilder();
            for (int i = 0; i < len && str[i] != '?'; i += 2)
            {
                //jamal?
                int[] cur = new int[] { str[i] - 'a', str[i + 1] - 'a' };
                char[] arr = mult(cur, mat);
                sb.Append(arr[0]).Append(arr[1]);
            }
            return sb.ToString();

        }

        private char[] mult(int[] cur, int[][] matrix)
        {
            char[] toReturn = new char[2];
            for (int i = 0; i < 2; ++i)
            {
                int res = 0;
                for (int j = 0; j < 2; ++j)
                {
                    res += matrix[i][j] * cur[j];
                    res %= MOD;//26
                }
                toReturn[i] = (char)(res + 'a');
            }
            return toReturn;
        }
        public String Decrypt(String enc)
        {
            int d = det();
            int dinv = FindDinv(d);
            if (dinv == -1) throw new Exception("no multiplicative inverse");
            int[][] adj = adjugate();

            for(int i = 0; i < adj.Length; ++i)
            {
                for(int j = 0; j < adj[i].Length; ++j)
                {
                    adj[i][j] = ((dinv * adj[i][j]) + MOD * 100) % MOD;
                }
            }

            var sb = new StringBuilder();

            for (int i = 0; i < enc.Length; i += 2)
            {
                int[] cur = new int[] { enc[i] - 'a', enc[i + 1] - 'a' };
                char[] arr = mult(cur, adj);
                sb.Append(arr[0]).Append(arr[1]);
            }

            return sb.ToString();
        }

        private int[][] adjugate()
        {
            return new int[][]
            {
                new int[]{ (mat[1][1] +2600) % MOD, (-mat[0][1] + 2600) % MOD},
                new int[]{ (-mat[1][0] + 2600) % MOD, (mat[0][0] + 2600) % MOD}
            };
        }

        private int FindDinv(int d)
        {
            for (int dinv = 1; dinv < MOD; ++dinv)
            {
                bool valid = (d * dinv) % MOD == 1;
                if (valid)
                    return dinv;
            }
            return -1;
        }

        private int det()
        {
            int det = mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0];
            while (det < 0) det += MOD;
            return det % MOD;
        }
        public static void Main()
        {
            Cipher cipher = new Cipher();
            String msg = "shortexample";
            String enc = cipher.Encrypt(msg);
            String dec = cipher.Decrypt(enc);
            String toShow = $"Encrypted:{enc}\nDecrypted:{dec}";
            Console.WriteLine(toShow);
            Console.ReadKey();
        }

    }

}