import math
from typing import List


__all__ = ['expand', 'encrypt', 'decrypt']


# I’ve used List[int], but it amuses me to contemplate Tuple[(int,) * 30] too.

def rotate_left(lhs: int, rhs: int, bits: int) -> int:
    return (lhs << rhs) | (lhs >> (bits - rhs))


def rotate_right(lhs: int, rhs: int, bits: int) -> int:
    return (lhs << (bits - rhs)) | (lhs >> rhs)


def expand(key: int) -> List[int]:
    mask = 2**64 - 1
    y = key & mask
    k = [y]
    x = (key >> 64) & mask

    for i in range(0, 29):
        x = ((rotate_right(x, 9, 64) + y) ^ i) & mask
        y = (rotate_left(y, 2, 64) & mask) ^ x
        k.append(y)

    return k


def encrypt(k: List[int], n: int, plain_text: int) -> int:
    mask = 2**n - 1
    x = plain_text & mask
    y = (plain_text >> n) & mask

    for ki in k:
        x = ((rotate_right(x, 9, n) + y) ^ ki) & mask
        y = (rotate_left(y, 2, n) ^ x) & mask

    return (y << n) | x


def decrypt(k: List[int], n: int, cipher_text: int) -> int:
    mask = 2**n - 1
    x = cipher_text & mask
    y = (cipher_text >> n) & mask

    for ki in k[::-1]:
        y = rotate_right(x ^ y, 2, n) & mask;
        x = rotate_left(((x ^ ki) - y) & mask, 9, n) & mask;

    return (y << n) | x