def find(parents, cur, income, answer):
    alloc = income//10
    if parents[cur] == cur or alloc == 0:
        answer[cur] += income-alloc
        return
    answer[cur] += income-alloc
    find(parents, parents[cur], alloc, answer)
    return

def solution(enroll, referral, seller, amount):
    N = len(enroll)
    answer = [0] * N
    name2id = {name:i for i,name in enumerate(enroll)}
    parents = [i if referral[i]=='-' else name2id[referral[i]] for i in range(N)]
    for i in range(len(seller)):
        find(parents, name2id[seller[i]], amount[i]*100, answer)
    return answer

import numpy as np

def quad_comp(n, arr, answer):
    values = np.unique(arr)
    if len(values) == 1:
        answer[values[0]] += 1
        return
    div = n//2
    quad_comp(div, arr[:div, :div], answer)
    quad_comp(div, arr[:div, div:], answer)
    quad_comp(div, arr[div:, :div], answer)
    quad_comp(div, arr[div:, div:], answer)

def solution(arr):
    arr = np.array(arr)
    answer = [0,0]
    quad_comp(len(arr), arr, answer)
    return answer

def solution(n, left, right):
    return [max(divmod(i,n))+1 for i in range(left,right+1)]

alpha = {10:'A',11:'B',12:'C',13:'D',14:'E',15:'F'}

def n_base(num, base):
    result = str()
    while num > 0:
        num, mod = divmod(num, base)
        result += str(mod) if mod < 10 else alpha[mod]
    return result[::-1]

def solution(n, t, m, p):
    arr = '01'
    total = t*m
    p = p%m

    i = 2
    while len(arr) < total:
        arr += n_base(i, n)
        i += 1

    answer = [t for i,t in enumerate(arr[:total]) if (i+1)%m==p]
    return ''.join(answer)

def solution(n, times):
    answer = 0
    start, end = 1, max(times)*n

    while start <= end:
        mid = (start+end)//2
        passed = 0
        for time in times:
            passed += mid // time
            if passed >= n:
                break
        if passed >= n:
            answer = mid
            end = mid-1
        elif passed < n:
            start = mid+1

    return answer

from itertools import product

def solution(N, number):
    S = [set() for _ in range(9)]

    if N == number:
        return 1
    else:
        S[1].add(N)

    for i in range(2,9):
        S[i].add(int(str(N)*i))
        for j in range(1,i):
            for x,y in product(S[j],S[i-j]):
                S[i].update({x+y,x-y,x*y})
                if y != 0:
                    S[i].add(x//y)
        if number in S[i]:
            return i
    return -1

import re

def solution(files):
    answer = []

    for file in files:
        head, number, tail = re.findall('([^0-9]+)([0-9]+)(.*)', file)[0]
        answer.append((head.lower(), int(number), tail, file))
    answer.sort(key=lambda x: [x[0],x[1]])

    return [file for _,_,_,file in answer]

def solution(msg):
    answer = []
    chars = [chr(x) for x in range(64,91)]

    cache = str()
    for c in msg:
        cache += c
        if cache not in chars:
            answer.append(chars.index(cache[:-1]))
            chars.append(cache)
            cache = c
    answer.append(chars.index(cache))

    return answer

import datetime as dt
import re
import math

def solution(m, musicinfos):
    answer = list()

    lower_repl = lambda match: match.group(1)[0].lower()
    sharp_repl = lambda s: re.sub('([A-G]#)', lower_repl, s)
    m = sharp_repl(m)
    strptime = lambda x: dt.timedelta(hours=int(x[0]),minutes=int(x[1]))

    for info in musicinfos:
        start, end, title, chord = info.split(',')
        plays = (strptime(end.split(':'))-strptime(start.split(':'))).seconds//60
        chord = sharp_repl(chord)
        chord = (chord * math.ceil(plays/len(chord)))[:plays]
        if m in chord:
            answer.append((plays,title))

    return sorted(answer, key=lambda x: x[0], reverse=True)[0][1] if len(answer) else '(None)'

from collections import deque

def solution(cacheSize, cities):
    answer = 0
    cache = deque(maxlen=cacheSize)

    for city in cities:
        city = city.lower()
        if city in cache:
            answer += 1
            cache.remove(city)
            cache.append(city)
        else:
            answer += 5
            cache.append(city)
    return answer