# 1.
"""

"""
import heapq
def compress(s, step):
    compressed = ""
    index = 0
    count = 0
    before_bundle = None
    while (index + step) <= len(s):
        next_bundle = s[index:(index + step)]

        if before_bundle is None:
            before_bundle = next_bundle
            count += 1
            index += step
            continue

        if before_bundle == next_bundle:
            count += 1
            index += step
            continue

        if count > 1:
            compressed += str(count)
            compressed += before_bundle
        else:
            index -= step
            compressed += s[index]
            index += 1

        before_bundle = None
        count = 0

    if count > 1:
        compressed += str(count)
        compressed += before_bundle
    else:
        index = index - step

    compressed += s[index:]

    return compressed


def solution(s):
    lengths = []
    max_step = int(len(s) // 2)

    for step in range(1, max_step+1):
        result = compress(s, step)
        heapq.heappush(lengths, len(result))
    return heapq.heappop(lengths)


if __name__ == "__main__":
    print(solution("aabbaccc"))
    print(solution("abcabcdede"))
    print(solution("xababcdcdababcdcd"))
    print(solution("ababababababababababababababab")
# 2
"""

"""
def get_balance_str(s):
    balance_str = []
    open_count = 0
    index = 0
    start_index = 0

    while index < len(s):
        if s[index] == '(':
            open_count += 1
        else:
            open_count -= 1

        if open_count == 0:
            balance_str.append(s[start_index:index + 1])
            start_index = index + 1
            balance_str.append(s[start_index:len(s)])
            break
        index += 1
    return balance_str


def is_correct_str(balance):
    open_count = 0
    index = 0
    while index < len(balance):
        if balance[index] == '(':
            open_count += 1
        else:
            open_count -= 1
            if open_count < 0:
                return False
        index += 1

    if open_count == 0:
        return True
    else:
        return False


def reverse_bracket(s):
    result = ""
    for c in s:
        if c == '(':
            result += ')'
        else:
            result += '('
    return result


def make(balance):
    result = ""

    if not balance:
        return result

    while True:
        u, v = get_balance_str(balance)
        if is_correct_str(u):
            result += u
            if v:
                balance = v
            else:
                break
        else:
            temp = "("
            temp += make(v)
            temp += ")"
            temp += reverse_bracket(u[1:-1])
            result += temp
            break

    return result


def solution(p):
    return make(p)

# 3
"""

"""
def is_find_hole(lock, except_x, except_y):
    start_x, end_x = except_x
    start_y, end_y = except_y
    for x, row in lock:
        for y, _ in row:
            if start_x <= x <= end_x and start_y <= y <= end_y:
                continue
            if lock[x][y] == 0:
                return True
    return False


def rotate_right_key(key):
    M = len(key) - 1
    result = [[0 for _ in row] for row in key]

    for row, tiles in enumerate(key):
        for column, tile in enumerate(tiles):
            result[column][M - row] = tile

    return result


def is_docked(key, lock):
    for x, row in enumerate(key):
        for y, _ in enumerate(row):
            if lock[x][y] == -1:
                continue
            if key[x][y] == lock[x][y]:
                return False
    return True


def solution(key, lock):
    N = len(lock)
    M = len(key)
    keys = []
    for _ in range(4):
        keys.append(key)
        key = rotate_right_key(key)

    # extend lock
    EXTEND_SIZE = N + M * 2 - 2
    extended_lock = [[-1 for _ in range(EXTEND_SIZE)] for _ in range(EXTEND_SIZE)]

    for x in range(EXTEND_SIZE):
        for y in range(EXTEND_SIZE):
            if (M - 1) <= x <= (EXTEND_SIZE - M) and (M - 1) <= y <= (EXTEND_SIZE - M):
                extended_lock[x][y] = lock[x - (M - 1)][y - (M - 1)]

    # resolve
    for i in range(EXTEND_SIZE - (M - 1)):
        for j in range(EXTEND_SIZE - (M - 1)):
            if is_find_hole(extended_lock, (j, j + M - 1), (i, i + M - 1)):
                continue
            tile = [[extended_lock[x][y] for y in range(j, j + M)] for x in range(i, i + M)]
            for key in keys:
                if is_docked(key, tile):
                    return True

    return False

 # 4, 5, 6, 7 는 시간 부족으로 쳐다도 못봤습니다.