def solution(animal, paths):
    children = [[] for _ in range(len(animal))]
    
    for parent, child in paths:
        children[parent].append(child)
    
    def dfs(current, sheep, wolf, next_steps):
        if animal[current] == 0:
            sheep += 1
        else:
            wolf += 1
        
        if wolf >= sheep:
            return sheep
        
        new_steps = next_steps + children[current]
        new_steps.remove(current)
        
        max_sheep = sheep
        
        for step in new_steps:
            max_sheep = max(max_sheep, dfs(step, sheep, wolf, new_steps))
        
        return max_sheep
    
    return dfs(0, 0, 0, [0])

from collections import deque

def solution(info, edges):
    n = len(info)
    tree = [[] for _ in range(n)]
    for parent, child in edges:
        tree[parent].append(child)

    queue = deque([(0, 0, 0, info[:])]) 
    answer = 1 

    while queue:
        node, sheep, wolf, infoCopy = queue.pop()
        value = infoCopy[node]
        infoCopy[node] = 2  

        if value == 1:
            wolf += 1
        elif value == 0:
            sheep += 1
            queue.append((0,sheep,wolf,infoCopy[:]))
        if wolf >= sheep:
            continue
        if answer < sheep: 
            answer = sheep
        for child in tree[node]:
            queue.append((child, sheep, wolf, infoCopy[:]))
    
    return answer

def solution(info, edges):
    result = set()
    
    visit = [False for _ in info]
    def dfs(sheeps, wolfs):
        if sheeps > wolfs:
            result.add(sheeps)
        else:
            return
        
        for s, e in edges:
            if visit[s] and not visit[e]:
                visit[e] = True
                if info[e] == 0:
                    dfs(sheeps + 1, wolfs)
                else:
                    dfs(sheeps, wolfs + 1)
                visit[e] = False
        
    visit[0] = True
    dfs(1, 0)
    return max(result)

from collections import deque

# 현재 위치에서 다음으로 이동할 수 있는 위치들을 반환하는 함수
def get_next_positions(board, loc):
    dRow, dCol = [0, 0, 1, -1], [1, -1, 0, 0]
    next_positions = []
    for d in range(4):
        nr, nc = loc[0] + dRow[d], loc[1] + dCol[d]
        if nr < 0 or nc < 0 or nr >= len(board) or nc >= len(board[0]):
            continue
        elif board[nr][nc] == 0:
            continue
        next_positions.append((nr, nc))
    return next_positions

# 재귀적으로 게임을 탐색하여 승리/패배 여부와 이동 횟수를 계산하는 함수
def search(board, aloc, bloc, turn):
    if turn % 2 == 0:  # A의 턴
        next_positions = get_next_positions(board, aloc)
    else:  # B의 턴
        next_positions = get_next_positions(board, bloc)

    # 현재 턴의 캐릭터가 더 이상 이동할 수 없으면 상대가 승리함
    if not next_positions:
        return turn % 2 != 0, turn  # (A가 승리하면 True, B가 승리하면 False), 현재까지의 이동 횟수 반환

    # A와 B가 같은 위치에 있으면 현재 턴의 캐릭터가 승리함
    if aloc == bloc:
        return turn % 2 == 0, turn + 1

    win, lose = [], []
    if turn % 2 == 0:  # A의 턴
        board[aloc[0]][aloc[1]] = 0  # A가 이동한 위치를 0으로 처리
        for nr, nc in next_positions:
            is_a_win, cnt = search(board, [nr, nc], bloc, turn + 1)
            if is_a_win:
                win.append(cnt)  # A가 이기는 경우
            else:
                lose.append(cnt)  # A가 지는 경우
        board[aloc[0]][aloc[1]] = 1  # 백트래킹을 위해 위치 복구
    else:  # B의 턴
        board[bloc[0]][bloc[1]] = 0  # B가 이동한 위치를 0으로 처리
        for nr, nc in next_positions:
            is_a_win, cnt = search(board, aloc, [nr, nc], turn + 1)
            if not is_a_win:
                win.append(cnt)  # B가 이기는 경우
            else:
                lose.append(cnt)  # B가 지는 경우
        board[bloc[0]][bloc[1]] = 1  # 백트래킹을 위해 위치 복구

    # 승리하는 경우가 있으면 가장 빨리 승리할 수 있는 경로를 선택
    if win:
        return turn % 2 == 0, min(win)  # 승리하는 사람과 그 중 가장 빠른 승리
    else:  # 패배할 수밖에 없다면 최대한 오래 버팀
        return turn % 2 != 0, max(lose)  # 패배하는 가장 긴 경로 반환

# 최종적으로 승리/패배 여부와 이동 횟수 반환
def solution(board, aloc, bloc):
    winner, answer = search(board, aloc, bloc, 0)
    return answer

def solution(input_string):
    lonely = set()
    prev = ''
    seen = set()

    for i in range(len(input_string)):
        if input_string[i] != prev and input_string[i] in seen:
            lonely.add(input_string[i])
        
        seen.add(input_string[i])

        prev = input_string[i]
    answer = ''.join(sorted(lonely))

    return answer if answer else "N"

def solution(input_string):
    answer = ''
    alphabetSet = set()
    aloneSet = set()
    before = input_string[0]
    
    for idx in range(1, len(input_string)):
        if before != input_string[idx]:
            if before in alphabetSet:
                aloneSet.add(before)
            else:
                alphabetSet.add(before)
            before = input_string[idx]
    if before in alphabetSet:
        aloneSet.add(before)
    else:
        alphabetSet.add(before)
    answer = "".join(sorted(list(aloneSet)))
    return answer if len(answer)>0 else "N"

from collections import defaultdict

def solution(input_string):
    instr = input_string
    acnt = defaultdict(int)
    
    p = 0
    ch = instr[p]
    cnt = 0
    while p < len(instr):
        if instr[p] == ch:
            cnt += 1
            p += 1
            continue
        
        acnt[ch] += 1
        ch = instr[p]
        p += 1
        cnt = 1
    acnt[ch] += 1
    
    result = []
    for ch in acnt:
        if acnt[ch] > 1:
            result.append(ch)
    result.sort()
    result = "".join(result)
    
    return 'N' if len(result) == 0 else result

from itertools import permutations

def solution(ability):
    max_sum = 0
    
    for perm in permutations(range(len(ability)), len(ability[0])):
        sum_value = 0
        for event, student in enumerate(perm):
            sum_value += ability[student][event]
        max_sum = max(max_sum, sum_value)
    
    return max_sum

from collections import deque
def solution(ability):
    answer = 0
    queue = deque([(0,0,[0]*len(ability))])
    eventLen = len(ability[0])
    peopleLen = len(ability)
    while queue:
        idx, cnt, people  = queue.pop()
        if eventLen  == idx:
            answer = max(answer,cnt)
            continue
        for i in range(peopleLen):
            if people[i] == 0 :
                queue.append((idx+1,cnt+ability[i][idx],people[:i]+[1]+people[i+1:]))
    return answer

result = 0

def solution(ability):
    n = len(ability)
    m = len(ability[0])
    use = [-1 for _ in range(n)]
    
    def find(depth, cur):
        global result
        if depth == m:
            result = max(result, cur)
            return
        
        for i, s in enumerate(ability):
            if use[i] >= 0:
                continue
            
            use[i] = depth
            find(depth + 1, cur + s[depth])
            use[i] = -1
    
    find(0, 0)
    return result

def solution(queries):
    answer = []
    def find(depth,number):
        path = []
        depthCnt = depth
        while depthCnt>1:
            depthCnt-=1
            path.append(number%4)
            number = number//4
        for num in reversed(path):
            if num == 0: return "RR"
            elif num ==3: return "rr"
        return "Rr"
    for query in queries:
        generation,number = query
        answer.append(find(generation,number-1))
    # re = []
    # for query in [[4,i] for i in range(1,65)]:
    #     generation,number = query
    #     re.append(find(generation,number-1))
    return answer

case = ('RR','Rr','Rr','rr')

def get_gene(pose):
    n, p = pose
    if n == 1:
        return 'Rr'
    
    mother_gene = get_gene((n - 1, (p - 1) // 4 + 1))
    
    result = ""
    if mother_gene == 'Rr':
        result = case[p % 4 - 1]
    else:
        result = mother_gene
    return result
 
def solution(queries):
    return [get_gene(q) for q in queries]

def solution(id_list, report, k):
    
    reportDic = {}
    for reGet in report:
        sender, getter = reGet.split()
        if getter not in reportDic:
            reportDic[getter] = set()
        reportDic[getter].add(sender)
    senderDic={}
    for name in id_list:
        senderDic[name]=0
    answer = []
    for reported in reportDic:
        senders = list(reportDic[reported])
        if len(senders)>=k:
            for sender in senders:
                senderDic[sender] +=1
    for sender in senderDic:
        answer.append(senderDic[sender])
    return answer

def solution(id_list, report, k):
    report = set(report)
    reports = {user: [] for user in id_list}

    for r in report:
        a, b = r.split()
        reports[b].append(a)

    banned = [user for user in id_list if len(reports[user]) >= k]
    mail_count = {user: 0 for user in id_list}

    for user in banned:
        for reporter in reports[user]:
            mail_count[reporter] += 1

    return [mail_count[user] for user in id_list]

def solution(id_list, report, k):
    report = tuple(map(lambda s: s.split(), report)) # ((from, to),)
    report_user = dict()
    report_table = dict()
    
    
    for (f, t) in report:
        if f not in report_table:
            report_table[f] = set()
                    
        if t not in report_user:
            report_user[t] = set()
        
        if t in report_table[f]:
            continue

        
        report_table[f].add(t)
        report_user[t].add(f)


    ban_users = tuple(map(lambda v: v[0], filter(lambda v: len(v[1]) >= k , report_user.items())))
    
    answer = list()
    for uid in id_list:
        if uid not in report_table.keys():
            answer.append(0)
            continue
            
        answer.append(len(tuple(filter(lambda t: t in ban_users, report_table[uid]))))
    
    return answer

from collections import defaultdict

def solution(id_list, report, k):
    user_report = defaultdict(set)
    report_cnt = defaultdict(int)
    
    for r_str in report:
        id, r_id = r_str.split(" ")
        if r_id not in user_report[id]:
            user_report[id].add(r_id)
            report_cnt[r_id] += 1
        
    result = defaultdict(int)
    for id in id_list:
        for r_id in user_report[id]:
            if report_cnt[r_id] >= k:
                result[id] += 1
    
    return [result[id] for id in id_list]

import re

def solution(n, k):
    answer = 0
    num = ""
    while n > 0:
        num = str(n % k) + num
        n = n // k
    numList = []
    for value in re.split(r"0+", num):
        if value != "1" and value != "": 
            numList.append(int(value))
    def isPrim(num):
        for i in range(2, int(num**0.5) + 1):
            if num%i == 0 :
                return False
        return True
    for num in numList:
        if isPrim(num):
            answer += 1
    return answer

import numpy as np

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    return True
def solution(n, k):
    converted = np.base_repr(n, base=k)
    numbers = converted.split('0')
    count = 0
    
    for num_str in numbers:
        if num_str == '':
            continue
        num = int(num_str)
        if is_prime(num):
            count += 1

    return count

def radix(n, k):    
    result = []
    while n > 0:
        n, m = divmod(n, k)
        result.append(m)
    
    return ''.join(map(str, result[::-1]))

eratos = None
def is_prime(n, max_stop):
    if n <= 1:
        return False
    
    global eratos
    if eratos is None:
        eratos = [False] * max_stop
        
        for i in range(2, max_stop):
            if eratos[i]:
                continue
            
            pos = i + i
            while pos < max_stop:
                eratos[pos] = True
                pos += i

    return eratos[n] is not True
            

def solution(n, k):
    n = radix(n, k)
    
    stop = int(10_000_000)
    
    cnt = 0
    for v in n.split('0'):
        if len(v) == 0:
            continue
        
        if is_prime(int(v), stop):
            cnt += 1 
            
    return cnt

import math

def solution(n, k):
    num = n
    c_num = ""
    while num > 0:
        if num < k:
            c_num += str(num)
            break
        c_num += str(num % k)
        num //= k
    
    nums = c_num[::-1].split("0")
    # max_num = int(str(k - 1) * len(max(nums)))
    # che = [True for i in range(max_num + 1)]
    # for i in range(2, int(math.sqrt(max_num)) + 1):
    #     if che[i]:
    #         for j in range(i + i, max_num + 1, i):
    #             che[j] = False
    
    result = 0
    for i in nums:
        if len(i) == 0:
            continue
        a = int(i)
        if a <= 1:
            continue
        
        flag = True
        for j in range(2, int(math.sqrt(a)) + 1):
            if a % j == 0:
                flag = False
                break
        if flag:
            result += 1
        
    return result

import math
def solution(fees, records):
    defaultTime, defaultCharge, unitTime, unitCharge= fees
    carRecordDic = {}
    carTimeDic = {}
    for record in records:
        time,number,behavior = record.split(" ")
        hour,minute = [int(char) for char in time.split(":")]
        if behavior == "OUT":
            inHour,inMinute= 0,0
            if len(carRecordDic.get(number,[]))>0:
                inHour,inMinute = carRecordDic[number].pop()
            time = (hour-inHour)*60+(minute-inMinute)
            carTimeDic[number] = carTimeDic.get(number,0)
            carTimeDic[number] = carTimeDic[number]+time
        else:
            carRecordDic[number] = carRecordDic.get(number,[])
            carRecordDic[number].append((hour,minute))
    for number in carRecordDic:
        if len(carRecordDic[number])>0:
            hour,minute = carRecordDic[number].pop()
            carTimeDic[number] =carTimeDic.get(number,0)
            carTimeDic[number]= carTimeDic[number]+(23-hour)*60+(59-minute)
    carNumbers = sorted(carTimeDic)
    answer = []
    for number in carNumbers:
        time = carTimeDic[number]-defaultTime
        time = math.ceil(time/unitTime if time>0 else 0)
        answer.append(time*unitCharge+defaultCharge)
    return answer

import collections

def hh_mm_to_m(s):
    hh, mm = map(int, s.split(':'))
    return mm + (hh * 60)

def calculate(f, time_delta):
    basic_min, basic_price, unit_min, unit_price = f
    
    # print(f, time_delta)
    
    result = basic_price
    time_delta -= basic_min
    
    
    if time_delta <= 0:
        return result
    
    n, r = divmod(time_delta, unit_min)
    
    return result + (n * unit_price) + (unit_price if r > 0 else 0)
    
    
    
def solution(fees, records):
    car_min = collections.defaultdict(int)
    car_nums = dict()
    car_price = collections.defaultdict(int)
    
    for r in records:
        time, num, action = r.split(' ')
        m = hh_mm_to_m(time)
        
        if action == 'IN':
            car_nums[num] = m
        
        elif action == 'OUT':
            time_delta = m - car_nums[num] 
            car_min[num] += time_delta
            del car_nums[num]
    
    # cleanup remain    
    for K, V in car_nums.items():
        time_delta = hh_mm_to_m('23:59') - V
        car_min[K] += time_delta
    
    # print(car_min)
    
    for K, V in car_min.items():
        car_price[K] = calculate(fees, V)
      

    return list(map(lambda k: car_price[k], sorted(car_price.keys())))

from collections import defaultdict
import math

def solution(fees, records):
    result = defaultdict(int)
    
    def calc_m(in_time, out_time):
        it = list(map(int, in_time.split(":")))
        ot = list(map(int, out_time.split(":")))
        
        it_hh, it_mm = it[0], it[1]
        ot_hh, ot_mm = ot[0], ot[1]
        
        m = ot_mm - it_mm
        h = ot_hh - it_hh
        
        m = (h * 60) + m
        
        return m
        
    time_table = dict()
    time_sum = defaultdict(int)
    
    for r in records:
        time, car_num, in_out = r.split(" ")
        
        if in_out == "IN":
            time_table[car_num] = time
        
        if in_out == "OUT":
            in_time = time_table[car_num]
            time_sum[car_num] += calc_m(in_time, time)
            del time_table[car_num]
    
    end = "23:59"
    for car_num in time_table.keys():
        in_time = time_table[car_num]
        time_sum[car_num] += calc_m(in_time, end)

    for car_num in time_sum:
        m = time_sum[car_num]
        
        fee = fees[1]
        if m - fees[0] > 0:
            fee += math.ceil((m - fees[0]) / fees[2]) * fees[3]
        
        result[car_num] = fee
    
    return [result[cn] for cn in sorted(result)]

def solution(n, info):
    ans = []
    def find(cur, depth, rest):
        if rest == 0:
            ans.append([c for c in cur])
            return
        
        if depth == 11:
            tmp = [c for c in cur]
            tmp[10] = rest
            ans.append(tmp)
            return
        
        
        if info[depth] < rest:
            cur[depth] = info[depth] + 1
            find(cur, depth + 1, rest - cur[depth])
            cur[depth] = 0
        
        find(cur, depth + 1, rest)
        
    find([0 for i in range(11)], 0, n)
    
    result = 0
    resulta = []
    for a in ans:
        sumb = 0
        suma = 0
        for i in range(11):
            if a[i] == 0 and info[i] == 0:
                continue
            
            s = 10 - i
            if a[i] > info[i]:
                suma += s
            else:
                sumb += s
                
        if suma > sumb:
            df = suma - sumb
            if df > result or (df == result and a[::-1] > resulta[::-1]):
                result = df
                resulta = a
                
    return [-1] if result == 0 else resulta

def solution(n, info):
    max_diff = 0
    answer_list = []

    def calculate(score, op, remain_arrow, ryan_info):
        nonlocal max_diff, answer_list
        idx = 10 - score

        if score > 10 or remain_arrow < 0:
            # Base case: All scores have been considered
            if remain_arrow < 0:
                return
            if remain_arrow > 0:
                ryan_info[10] += remain_arrow  # Assign remaining arrows to 0 score
            ryan_score = 0
            apeach_score = 0
            for i in range(11):
                if ryan_info[i] == 0 and op[i] == 0:
                    continue
                if ryan_info[i] > op[i]:
                    ryan_score += 10 - i
                else:
                    apeach_score += 10 - i
            diff = ryan_score - apeach_score
            if diff > 0:
                if diff > max_diff:
                    max_diff = diff
                    answer_list = [ryan_info.copy()]
                elif diff == max_diff:
                    answer_list.append(ryan_info.copy())
            if remain_arrow > 0:
                ryan_info[10] -= remain_arrow  # Backtrack
            return

        # Option 1: Ryan tries to win this score
        need_to_win = op[idx] + 1
        if remain_arrow >= need_to_win:
            ryan_info[idx] = need_to_win
            calculate(score + 1, op, remain_arrow - need_to_win, ryan_info)
            ryan_info[idx] = 0  # Backtrack

        # Option 2: Ryan does not win this score
        ryan_info[idx] = 0
        calculate(score + 1, op, remain_arrow, ryan_info)

    ryan_info = [0] * 11
    calculate(0, info, n, ryan_info)

    if not answer_list:
        return [-1]

    # Select the best answer according to the problem's criteria
    answer_list.sort(key=lambda x: x[::-1], reverse=True)
    return answer_list[0]

from collections import deque

def solution(n, info):
    answers = []
    apeachScore = 0
    for idx, score in enumerate(info):
        if score > 0:
            apeachScore += 10 - idx
    
    maxScore = 0 
    queue = deque([(0, n, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0, apeachScore)])
    
    while queue:
        idx, remain, rionInfo, rionScore, apeachScore = queue.popleft()
        if idx == 10 or remain == 0:

            if rionScore > apeachScore:
                scoreDiff = rionScore - apeachScore
                if scoreDiff > maxScore:
                    maxScore = scoreDiff
                    answers = [rionInfo[:10]+[rionInfo[10]+remain]]
                elif scoreDiff == maxScore:
                    answers.append(rionInfo[:10]+[rionInfo[10]+remain])
            continue
        queue.append((idx + 1, remain, rionInfo[:], rionScore, apeachScore))
        if remain > info[idx]:
            shoot = info[idx] + 1
            newRionInfo = rionInfo[:]
            newRionInfo[idx] = shoot
            newRionScore = rionScore + (10 - idx)
            newApeachScore = apeachScore
            if info[idx] > 0:
                newApeachScore -= (10 - idx)
            queue.append((idx + 1, remain - shoot, newRionInfo, newRionScore, newApeachScore))
    if not answers:
        return [-1]
    answer = [0] * 11
    for an in answers:
        for i in range(10, -1, -1):
            if an[i] > answer[i]:
                answer = an
                break
            elif an[i] < answer[i]:
                break
    
    return answer

from collections import deque

def solution(info, edges):
    n = len(info)
    tree = [[] for _ in range(n)]
    for parent, child in edges:
        tree[parent].append(child)

    queue = deque([(0, 0, 0, info[:])]) 
    answer = 1 

    while queue:
        node, sheep, wolf, infoCopy = queue.pop()
        value = infoCopy[node]
        infoCopy[node] = 2  

        if value == 1:
            wolf += 1
        elif value == 0:
            sheep += 1
            queue.append((0,sheep,wolf,infoCopy[:]))
        if wolf >= sheep:
            continue
        if answer < sheep: 
            answer = sheep
        for child in tree[node]:
            queue.append((child, sheep, wolf, infoCopy[:]))
    
    return answer

def solution(board, skill):
    h = len(board)
    w = len(board[0])
    result = [[0 for j in range(w + 1)] for i in range(h + 1)]
    
    for t, r1, c1, r2, c2, d in skill:
        if t == 1:
            d *= -1
        
        result[r1][c1] += d
        result[r1][c2 + 1] += -d
        result[r2 + 1][c1] += -d
        result[r2 + 1][c2 + 1] += d
    
    for i in range(h):
        for j in range(w - 1):
            result[i][j + 1] += result[i][j]
    
    for i in range(h - 1):
        for j in range(w):
            result[i + 1][j] += result[i][j]
    
    cnt = 0
    for i in range(h):
        for j in range(w):
            cnt += 1 if board[i][j] + result[i][j] > 0 else 0
    
    return cnt

def solution(board, skill):
    n = len(board)
    m = len(board[0])
    prefix_sum = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 누적합 배열에 스킬 반영
    for ty, r1, c1, r2, c2, degree in skill:
        if ty == 1:  # 공격일 때는 음수로
            degree = -degree
        
        # 변화량을 기록
        prefix_sum[r1][c1] += degree
        prefix_sum[r1][c2 + 1] -= degree
        prefix_sum[r2 + 1][c1] -= degree
        prefix_sum[r2 + 1][c2 + 1] += degree

    # 누적합 계산
    for i in range(n):
        for j in range(1, m):
            prefix_sum[i][j] += prefix_sum[i][j - 1]

    for j in range(m):
        for i in range(1, n):
            prefix_sum[i][j] += prefix_sum[i - 1][j]

    # 원본 보드에 누적합 반영
    answer = 0
    for i in range(n):
        for j in range(m):
            board[i][j] += prefix_sum[i][j]
            if board[i][j] > 0:
                answer += 1

    return answer

def solution(board, skill):
    n = len(board)
    m = len(board[0])
        
    for ty,r1,c1,r2,c2,degree in skill:
        if ty == 1:
            degree = -degree
        
        for i in range(r1, r2+1):
            for j in range(c1, c2+1):
                board[i][j] += degree
    
    answer = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] > 0:
                answer += 1
        
    return answer

def solution(board, skill):
    answer = len(board) * len(board[0])
    effect = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
    
    for behavior in skill:
        skillType, r1, c1, r2, c2, degree = behavior
        if skillType == 1:
            degree = -degree
        
        effect[r1][c1] += degree
        effect[r1][c2 + 1] -= degree
        effect[r2 + 1][c1] -= degree
        effect[r2 + 1][c2 + 1] += degree

    for i in range(len(board)):
        for j in range(1, len(board[0])):
            effect[i][j] += effect[i][j - 1]

    for j in range(len(board[0])):
        for i in range(1, len(board)):
            effect[i][j] += effect[i - 1][j]

    for i in range(len(board)):
        for j in range(len(board[0])):
            board[i][j] += effect[i][j]
            if board[i][j] <= 0:
                answer -= 1

    return answer

# 효율성: 시간초과

def solution(board, skill):
    for record in skill:
        t, r1, c1, r2, c2, degree = record
        
        pos0 = (r1, c1)
        pos1 = (r2, c2)
        
        for y in range(pos0[0], pos1[0] + 1):
            for x in range(pos0[1], pos1[1] + 1):
                if t == 1:
                    board[y][x] -= degree
                else:
                    board[y][x] += degree
        
        cnt = len(board) * len(board[0])
        for y in range(len(board)):
            for x in range(len(board[0])):
                if board[y][x] <= 0:
                    cnt -= 1
                
    return cnt

from collections import deque
def solution(begin, target, words):
    def check(word1,word2): #다른 알파벳이 2개 이상 있는지 확인하는 function
        cnt = 0
        for ch1,ch2 in zip(word1,word2):
            if ch1!=ch2: cnt+=1
        return cnt<2
    wordDic = {} #word를 저장하는 Tree
    wordLen = len(words)
    queue = deque([begin])
    #begin 부터 시작하여 다른 words들과 비교하였을때 다른 알파벳이 1개인 word를 자신의 자식 노드로 삼는다
    while queue:
        word = queue.popleft()
        wordDic[word] = []
        for word2 in words:
            if check(word,word2):
                wordDic[word].append(word2)
                words.remove(word2)
                queue.append(word2)
    answer = wordLen
    queue = deque([(begin,0)])
    #bfs
    while queue:
        word,cnt = queue.popleft()
        children = wordDic[word]
        #node의 word가 target과 같은 경우 anwer에 이전 answer값과 현재 cnt값중 가장 작은 값을 저장
        if word == target:answer = min(answer,cnt)
        if not children : continue
        for child in children : queue.append((child,cnt+1))
    #answer이 변하지 않았을 경우 return 0
    if answer == wordLen : return 0
    return answer

from collections import deque

def solution(begin, target, words):
    if target not in words:
        return 0
    
    queue = deque([(begin, 0)])
    visited = set([begin])

    while queue:
        current_word, steps = queue.popleft()

        if current_word == target:
            return steps

        for word in words:
            if word not in visited and sum([c1 != c2 for c1, c2 in zip(current_word, word)]) == 1:
                queue.append((word, steps + 1))
                visited.add(word)

    return 0

import re
import collections
def available(w, words):
    result = set()
    
    wlist = list(w)
    for idx, c in enumerate(wlist):
        wlist[idx] = '.'
        regex = re.compile('^' + ''.join(wlist) + '$')
        wlist[idx] = c
        
        for word in words:
            if regex.match(word) is None:
                continue
            if word == w:
                continue
            
            result.add(word)
                
    return list(result)
def solution(begin, target, words):
    word_vector = {}
    for w in words + [begin]:
        word_vector[w] = available(w, words)
        
    
    queue = collections.deque() # (current, used, depth)
    queue.append((begin, [begin], 0))
    
    while queue:
        current, used, depth = queue.popleft()
        
        
        if current == target:
            return depth
        
        for w in word_vector[current]:
            if w in used:
                continue
                
            queue.append((w, used + [w], depth + 1))
    
    return 0

from collections import defaultdict, deque

def solution(begin, target, words):
    pattern = defaultdict(set)
    for w in words:
        for i, ch in enumerate(w):
            p = w[:i] + "*" + w[i + 1:]
            pattern[p].add(w)
    
    queue = deque()
    queue.append([begin, 0])
    visit = defaultdict(bool)
    visit[begin] = True
    while len(queue) > 0:
        node = queue.popleft();
        word = node[0]
        cnt = node[1]
        if word == target:
            return cnt
        
        next = set()
        for i, ch in enumerate(word):
            p = word[:i] + "*" + word[i + 1:]
            next = next | pattern[p]
        
        for n in next:
            if visit[n]:
                continue
            visit[n] = True
            queue.append([n, cnt + 1])
            
    return 0

from collections import deque

def solution(maps):
    movement = [(0, 1), (1, 0), (-1, 0), (0, -1)]  
    xEnd = len(maps[0]) - 1 
    yEnd = len(maps) - 1
    queue = deque([(0, 0, 1)]) #(row값,column값,비용(cnt))
    visited = set([(0, 0)]) 
    #bfs
    while queue:
        i, j, cnt = queue.popleft()
        if i == yEnd and j == xEnd:
            return cnt
        for dx, dy in movement:
            ni, nj = i + dx, j + dy
            if 0 <= ni <= yEnd and 0 <= nj <= xEnd and maps[ni][nj] == 1 and (ni, nj) not in visited:
                visited.add((ni, nj))
                queue.append((ni, nj, cnt + 1))
    return -1

from collections import deque

def solution(maps):
    answer = 0
    dx , dy = [1,-1,0,0],[0,0,1,-1]
    def bfs(x,y):
        q = deque()
        q.append((x,y))
        
        while q:
            x,y = q.popleft()
            
            for i in range(4):
                nx = dx[i] + x
                ny = dy[i] + y
                
                if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]): continue
                if maps[nx][ny] == 0:
                    continue
                if maps[nx][ny] == 1:
                    maps[nx][ny] = maps[x][y] + 1
                    q.append((nx, ny))     
        return maps[len(maps)-1][len(maps[0])-1]
    answer = bfs(0,0)
    return -1 if answer == 1 else answer

import collections
def solution(maps):   
    width = len(maps[0])
    height = len(maps)
    available_move = ((-1, 0), (1, 0), (0, -1), (0, 1))
    
    ## dest = (0, 0)
    ## start = (n - 1, m - 1)
    visited = set() # do not visit if there's fast way (already visited)

    queue = collections.deque()
    queue.append((width - 1, height - 1, 1)) # (x, y, depth)
    while queue:
        x, y, depth = queue.popleft()
        
        if x == 0 and y == 0:
            return depth
        
        if (x, y) in visited:
            continue
            
        if maps[y][x] == 0:
            continue
        
        visited.add((x, y))
        
        for (next_x, next_y) in available_move:
            new_x, new_y = x + next_x, y + next_y
                        
            if new_x < 0 or new_x >= width or new_y < 0 or new_y >= height:
                continue
            
            queue.append((new_x, new_y, depth + 1))
        
    return -1

from collections import deque

def solution(maps):
    next_list = deque()
    visit = list(map(lambda arr: list(map(lambda num: False, arr)), maps))
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    next_list.append([0, 0, 1])
    visit[0][0] = True
    while(len(next_list) > 0):
        loc = next_list.popleft()
        x = loc[0]
        y = loc[1]
        
        if (x == len(maps) - 1 and y == len(maps[0]) - 1):
            return loc[2]
        
        for ix, iy in zip(dx, dy):
            next_x = x + ix
            next_y = y + iy
            
            if next_x < 0 or next_x >= len(maps) or next_y < 0 or next_y >= len(maps[0]):
                continue
            if not visit[next_x][next_y] and maps[next_x][next_y] == 1:
                visit[next_x][next_y] = True
                next_list.append([next_x, next_y, loc[2] + 1])
                
    return -1

from collections import deque

def solution(board):
    N = len(board)
    cost = [[[float('inf')] * 4 for _ in range(N)] for _ in range(N)]
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    queue = deque()
    
    for i in range(4):
        cost[0][0][i] = 0
    
    queue.append((0, 0, -1, 0))
    
    while queue:
        x, y, prev, current_cost = queue.popleft()
        
        for i in range(4):
            dx, dy = d[i]
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] == 0:
                new_cost = current_cost + 100
                
                if prev != -1 and prev != i:
                    new_cost += 500
                
                if new_cost < cost[nx][ny][i]:
                    cost[nx][ny][i] = new_cost
                    queue.append((nx, ny, i, new_cost))
    
    return min(cost[N-1][N-1])

from collections import deque

def solution(board):
    movement = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    xEnd = len(board[0]) - 1
    yEnd = len(board) - 1
    #가장 작은 비용을 저장하는 map
    makeBoard = [[float('inf') for _ in range(xEnd+1)] for _ in range(yEnd+1)]
    def bfs(boardDp, queue):
        #queue = [(row값,column값,비용,방향)]
        #방향은 movement의 index값으로 나타낸다 ex)방향이 0일 경우 (0,1)으로 움직임 = 오른쪽으로 움직임
        while queue:
            i, j, price, direction = queue.popleft()
            for idx, (dx, dy) in enumerate(movement):
                ni, nj = i + dx, j + dy
                if 0 <= ni <= yEnd and 0 <= nj <= xEnd and board[ni][nj] == 0:
                    #현재 방향과 가려는 방향이 같으면 100 아니라면 600(한번 움직이고 코너를 만들어야 함으로 100+500=600)
                    cost = 100 if direction == idx else 600
                    #최소 비용을 저장하는 map에 (발생한 비용+이때까지의 비용)과 원래 저장되어있던 비용중 가장 작은 비용을 저장한다
                    if boardDp[ni][nj] >= cost + price:
                        boardDp[ni][nj] = cost + price
                        queue.append((ni, nj, cost + price, idx))
        return boardDp[yEnd][xEnd]
    #출발지점(0,0)에서 갈 수 있는 방향은 오른쪽(0,1) 또는 아래(1,0)임으로 둘을 따로 계산하여 비교해준다
    return min(bfs(makeBoard, deque([(0, 0, 0, 0)])), bfs(makeBoard, deque([(0, 0, 0, 1)])))

from collections import deque
import sys

def solution(board):
    n = len(board)
    d = [[-1, 0, 1, 0], [0, 1, 0, -1]]
    
    def dfs(start):
        visit = [[sys.maxsize for i in range(n)] for j in range(n)]
        visit[0][0] = 0

        queue = deque()
        queue.append(start)
        while queue:
            x, y, cost, dir = queue.popleft()

            for i in range(4):
                nx = x + d[0][i]
                ny = y + d[1][i]

                if nx < 0 or nx >= n or ny < 0 or ny >= n:
                    continue
                if board[nx][ny] == 1:
                    continue

                n_cost = cost + (100 if dir == i else 600)
                if n_cost < visit[nx][ny]:
                    visit[nx][ny] = n_cost
                    queue.append([nx, ny, n_cost, i])
                    
        return visit[n - 1][n - 1]
    
    return min(dfs([0, 0, 0, 1]), dfs([0, 0, 0, 2]))

from collections import deque
import sys

def solution(board):
    n = len(board)
    d = [[-1, 0, 1, 0], [0, 1, 0, -1]]
    
    def dfs(start):
        visit = [[sys.maxsize for i in range(n)] for j in range(n)]
        visit[0][0] = 0

        queue = deque()
        queue.append(start)
        while queue:
            x, y, cost, dir = queue.popleft()

            for i in range(4):
                nx = x + d[0][i]
                ny = y + d[1][i]

                if nx < 0 or nx >= n or ny < 0 or ny >= n:
                    continue
                if board[nx][ny] == 1:
                    continue

                n_cost = cost + (100 if dir == i else 600)
                if n_cost < visit[nx][ny]:
                    visit[nx][ny] = n_cost
                    queue.append([nx, ny, n_cost, i])
                    
        return visit[n - 1][n - 1]
    
    return min(dfs([0, 0, 0, 1]), dfs([0, 0, 0, 2]))

import collections

def solution(board):
    # n x n, 0 -> available, 1 -> wall
    # start: (0, 0), end: (n - 1, n - 1)
    
    # one-way: 100, change direction cost: 500
    
    queue = collections.deque()
    def BFS(queue):
        SIZE = len(board)
        price_board = [[SIZE * SIZE * 100_000_000_000] * SIZE for _ in range(SIZE)]

        directions = {'L': (-1, 0), 'R': (1, 0), 'U': (0, -1), 'D': (0, 1)}

        # price_board[0][0] = 0

        while queue:
            x, y, cost, direction = queue.popleft()

            if x == SIZE - 1 and y == SIZE - 1:
                continue  # We've reached the end

            for d, (dx, dy) in directions.items():
                new_cost = 100
                if direction is not None and direction != d:
                    new_cost += 500

                new_x, new_y = x + dx, y + dy
                if new_x < 0 or new_x >= SIZE or new_y < 0 or new_y >= SIZE:
                    continue  # Out of bounds

                if board[new_y][new_x] == 1:
                    continue  # It's a wall

                if price_board[new_y][new_x] < cost + new_cost:
                    continue

                price_board[new_y][new_x] = cost + new_cost
                queue.append((new_x, new_y, cost + new_cost, d))

        return price_board[SIZE - 1][SIZE - 1]
    
    queue.append((0, 0, 0, 'R'))
    a = BFS(queue)
    queue.clear()
                 
    queue.append((0, 0, 0, 'D'))
    b = BFS(queue)
    queue.clear()
    return min(a, b)

def solution(name):
    answer = 0
    length = len(name)
    move = length - 1
    
    for idx in range(length):
        answer += min(ord(name[idx]) - ord('A'), ord('Z') - ord(name[idx]) + 1)
        
        next_idx = idx + 1
        while next_idx < length and name[next_idx] == 'A':
            next_idx += 1
        
        distance = idx + length - next_idx + min(idx, length - next_idx)
        move = min(move, distance)
    
    answer += move
    return answer

from collections import deque
def solution(name):
    answer = 0
    word = ""
    #name의 크기에 따라 초기 word = "AAA"(크기=3) 또는 "AAAA"(크기=4)
    for _ in range(len(name)): word+="A"
    queue = deque([(0,0,word)]) #(계산하려는 index값,비용(cnt),현재 word) 
    #BFS
    while queue:
        idx,cnt, word = queue.popleft()
        #up = 해당 index의 word 값을 원하는 name 값으로 변형시키기 위해 아래 또는 위래 움직이는 비용
        up = abs(ord(word[idx]) - ord(name[idx]))
        #down = up과 반대방향으로 움직였을때 발생하는 비용
        down = (26 - up)
        result = min(up, down)+cnt
        #해당 index의 word 값을 name 값으로 변경
        word = word[:idx]+name[idx]+word[idx+1:]
        #word와 name이 같을 겨우 return
        if word == name:
            return result
        #커서를 오른쪽으로 이동
        queue.append(((idx+1)%len(name),result+1,word))
        #커서를 왼쪽으로 이동
        queue.append(((idx-1)%len(name),result+1,word))
    return -1

def solution(name):
    arr = [min(abs(ord('A') - ord(i)), 26 - abs(ord('A') - ord(i))) for i in name]
    result = sum(arr)
    
    n = len(name)
    min_dst = n - 1
    for i, ch in enumerate(name):
        j = i + 1
        while j < n and name[j] == 'A':
            j += 1
        
        min_dst = min(min_dst, (i * 2) + (n - j), ((n - j) * 2) + i)
    
    return result + min_dst

def solution(number, k):
    idx = 0
    while idx < len(number)-1 and k!=0:
        #현재 자리의 숫자가 다음 자리의 숫자보다 작으면 그 숫자를 제거
        if number[idx]<number[idx+1]:
            number = number[:idx]+number[idx+1:]
            k-=1
            # 제거한 후, 이전 자리로 돌아가서 다시 비교
            idx= idx-1 if idx-1>=0 else 0
        else: idx+=1
    # 제거해야 할 숫자가 남아있다면, 뒤에서 k개를 제거
    # 굳이 가장 작은 숫자를 제거하지 않아도 정렬되어있음으로 뒷자리부터 제거하면된다
    if k!=0:
        number= number[:len(number)-k]
    return number

def solution(number, k):
    stack = []
    cntr = 0
    
    nums = list(number)
    
    for i in nums:
        while len(stack) > 0 and stack[-1] < i and cntr < k:
            stack.pop()
            cntr += 1
            
        stack.append(i)
        
    return ''.join(stack[0:len(number) - (k - cntr)])

def solution(number, k):
    stack = []
    for n in number:
        while stack and k > 0 and stack[-1] < n:
            stack.pop()
            k -= 1
        stack.append(n)

    return ''.join(stack[:len(number) - k])

def solution(number, k):
    i = 0
    while i < len(number) - 1 and k > 0:
        if number[i + 1] > number[i]:
            number = number[:i] + number[i + 1:]
            k -= 1
            
            if i == 0:
                i -= 1
            else:
                i -= 2    
        i += 1
        
    if k > 0:
        number = number[:len(number) - k]
    
    return number

def solution(people, limit):
    answer = 0
    people.sort()
    start = 0
    end = len(people) - 1
    while start <= end:
        #현재 가장 무거운 사람을 태운 뒤 현재 가장 가벼운 사람까지 태울 수 있다면 태워준다
        if people[start] + people[end] <= limit:
            start += 1 
        end -= 1 
        answer += 1
    
    return answer

import collections
import math

def solution(people, limit):
    people.sort()
    ptr_a = 0
    ptr_b = len(people) - 1
    
    cnt = 0
    while ptr_a < ptr_b:
        if people[ptr_b] + people[ptr_a] <= limit:
            cnt += 1 
            ptr_a += 1
            
            
        ptr_b -= 1
        
    return len(people) - cnt

from collections import deque

def solution(people, limit):
    answer = 0
    people = deque(sorted(people))
    
    while people:
        start = people.pop()
        if len(people) > 0 and start + people[0] <= limit:
            people.popleft()
        answer += 1
    return answer

from collections import defaultdict

def solution(people, limit):
    w = defaultdict(int)
    for p in people:
        w[p] += 1
    
    n = len(people)
    l, r = 1, 240
    
    cnt = 0
    while l <= r:
        if w[r] == 0:
            r -= 1
            continue
        
        w[r] -= 1
        cnt += 1
        m = limit - r
        while l <= m:
            if w[l] == 0:
                l += 1
                continue
            w[l] -= 1
            break
    return cnt

def solution(routes):
    routes.sort(key=lambda x: x[1])
    cameras = 0
    end_camera = -float('inf')
    
    for i in routes:
        if end_camera < i[0]:
            end_camera = i[1]
            cameras += 1
            
    return cameras

def solution(routes):
    answer = 0
    idx = 0
    #나가는 시점을 기준으로 sort
    routes.sort(key = lambda x:x[1])
    while idx <len(routes):
        answer+=1
        start, end = routes[idx]
        idx+=1
        #만약 현재 end에 카메라를 설치하였을때 end보다 진입 시점이 빠르면 카메라에 찍힌다
        while idx<len(routes) and routes[idx][0]<=end:
            idx+=1
    return answer

def solution(routes):
    routes.sort(key = lambda v: (v[1], v[0]))
    
    cnt = 1
    camera = routes[0][1]
    
    for start, end in routes:
        if start > camera:
            camera = end
            cnt += 1
            
    return cnt

def solution(routes):
    answer = 0
    routes.sort(key = lambda x: (x[1], x[0]))
    min_value = float('-inf')
    for route in routes:
        if route[0] > min_value:
            answer += 1
            min_value = route[1]
    return answer

def solution(routes):
    rs = sorted(routes, key = lambda r: (r[1], r[0]))
    
    cnt = 0
    p = -30_001
    for r in rs:
        if r[0] > p:
            cnt += 1
            p = r[1]
    
    return cnt

import collections

def solution(routes):
    rs = sorted(routes, key = lambda r: (r[1], r[0]))
    
    q = collections.deque()
    pivot = 0
    result = 0
    for r in rs:
        if len(q) == 0:
            q.append(r)
            pivot = r[1]
            continue
        
        if r[0] <= pivot:
            pivot = max(pivot, r[0])
        else:
            # print(q, r)
            result += 1
            q.clear()
            pivot = r[1]
        q.append(r)
    
    if q:
        if q[-1][0] <= pivot:
            result += 1
        else:
            result += 2
    
    return result

def solution(numbers, hand):
    leftNums = [1,4,7] #왼쪽 손가락으로 누를 수 있는 번호
    rightNums = [3,6,9] #오른쪽 손가락으로 누를 수 있는 번호
    leftCurrent = 10 # *번호는 10으로
    rightCurrent = 12 # #번호는 12으로
    answer = ""
    for num in numbers:
        if num  == 0 : num = 11# 0번호는 11으로
        #왼쪽손가락으로 해당 번호까지 가는데 비용 = (123,456,789를 각 1,2,3층으로 표현 하였을때 한층에 3개임으로 //3을 해준다) 층 수 + 해당 층 까지 갔을때 필요한 이동 수
        leftCnt = abs(num-leftCurrent)//3+abs(num-leftCurrent)%3
        rightCnt = abs(num-rightCurrent)//3+abs(num-rightCurrent)%3
        isLeft = True
        
        if num in leftNums: isLeft = True
        elif num in rightNums: isLeft = False
        else:
            #비용이 같을 경우 어느 손잡이인가에 따라
            if leftCnt == rightCnt:
                if hand=="left": isLeft = True
                else: isLeft = False
            elif leftCnt>rightCnt: isLeft = False
            else: isLeft = True
        #이동한 손 저장 밑 현재 위치 변화
        if isLeft:
            leftCurrent = num
            answer+="L"
        else:
            rightCurrent = num
            answer+="R"
    return answer

def distance(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
                                           
def solution(numbers, p_hand):
    left_pos = (3, 0)
    right_pos = (3, 2)
    
    result = []
    
    for n in numbers:
        pos = (n - 1) // 3
        hand = (n - 1) % 3 ## 0 => 왼손, 1 => 중간, 2 => 오른손
        if n == 0:
            pos = 3
            hand = 1
        
        if hand == 2:
            result.append('R')
            right_pos = (pos, hand)
        elif hand == 0:
            result.append('L')
            left_pos = (pos, hand)
        else:
            left_distance = distance((pos, hand), left_pos)
            right_distance = distance((pos, hand), right_pos)
            
            if left_distance == right_distance:
                result.append(p_hand[0].upper())
                if p_hand == 'right':
                    right_pos = (pos, hand)
                else:
                    left_pos = (pos, hand)
            elif left_distance < right_distance:
                result.append('L')
                left_pos = (pos, hand)
            else:
                result.append('R')
                right_pos = (pos, hand)
                
    return ''.join(result)

def calc_distance(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solution(numbers, hand):
    keypad = [['1', '2', '3'], ['4', '5', '6'], ['7', '8', '9'], ['*', '0', '#']]
    
    lp = [3, 0]
    rp = [3, 2]
    result = [" "] * len(numbers)
    
    for i, num in enumerate(numbers):
        str_num = str(num)
        for j in range(0, 3):
            if str_num == keypad[j][0]:
                lp[0] = j
                lp[1] = 0
                result[i] = "L"
                break
                
            if str_num == keypad[j][2]:
                rp[0] = j
                rp[1] = 2
                result[i] = "R"
                break
        
        for j in range(0, 4):
            if str_num == keypad[j][1]:
                num_point = [j, 1]
                a = calc_distance(num_point, lp)
                b = calc_distance(num_point, rp)
                if a > b:
                    rp[0] = j
                    rp[1] = 1
                    result[i] = "R"
                elif a < b:
                    lp[0] = j
                    lp[1] = 1
                    result[i] = "L"
                else:
                    if hand == "right":
                        rp[0] = j
                        rp[1] = 1
                        result[i] = "R"
                    else:
                        lp[0] = j
                        lp[1] = 1
                        result[i] = "L"
                break
                
    return "".join(result)

def solution(numbers, hand):
    answer = ''
    prev_left = 10
    prev_right = 12
    
    for number in numbers:
        if number == 0:
            number = 11
        
        if number in [1, 4, 7]:
            answer += 'L'
            prev_left = number
        elif number in [3, 6, 9]:
            answer += 'R'
            prev_right = number
        else:
            left_distance = abs((prev_left - 1) // 3 - (number - 1) // 3) + abs((prev_left - 1) % 3 - (number - 1) % 3)
            right_distance = abs((prev_right - 1) // 3 - (number - 1) // 3) + abs((prev_right - 1) % 3 - (number - 1) % 3)
            if left_distance < right_distance:
                answer += 'L'
                prev_left = number
            elif right_distance < left_distance:
                answer += 'R'
                prev_right = number
            else:
                if hand == 'right':
                    answer += 'R'
                    prev_right = number
                else:
                    answer += 'L'
                    prev_left = number
    return answer

def solution(numbers):
    answer = []
    for num in numbers:
        fNum = num+1
        # num과 num보다 큰 fnum xor연산을 비교 후 1(둘의 비트가 다를 때) 카운트
        checkCnt = bin(num^fNum).count("1")
        # 2개 이하일때 정답
        if checkCnt<=2: answer.append(fNum)
        else:
            addNum = ""
            # 어차피 이진수 00...01을 더한것이기 때문에 달라진 수 = 자리올림이 된 가장 큰(가장 왼쪽) 비트 1개 + 나머지 0이된 비트의 수 ex) 00101111+00000001 = 00110000
            #따라서 위 예제처럼 이전 수 와 비교하였을때 가장 왼쪽비트를 제외한 비트들이 1에서 0이 된 것 임으로 필요한 만큰 가장 작은(가장 오른쪽) 비트를 1로 바꾸어 나가면 된다
            for _ in range(checkCnt-2): addNum+="1"
            answer.append(int(addNum,2)+fNum)
    return answer

import math
def to_binary(n):
    result = []
    
    cnt = 3
    d = n
    while d > 0:
        d, m = divmod(d, 2)
        result.append(m)
        
    return list(reversed(result))

def to_decimal(b):
    result = 0
    
    for idx, b in enumerate(reversed(b)):
        result += (pow(2, idx) * int(b))

    return result    
    
def ans(n):
    #binary = to_binary(n)
    binary = ['0'] + list(bin(n)[2:])
    
    # 가장 맨 뒤에 있는 0을 찾고 => 1로 설정,
    # 그리고 뒤에 있는 1을 0으로 설정
    
    cur = len(binary) - 1
    while cur >= 0:
        if binary[cur] == '0':
            binary[cur] = '1'
        
            for idx, b in enumerate(binary[cur + 1:], cur + 1):
                if b == '1':
                    binary[idx] = '0'
                    break
                    
            return to_decimal(binary)
            
        cur -= 1
        
    
    
def solution(numbers):
    return list(map(ans, numbers))

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            long x = numbers[i];
            if (x % 2 == 0) {
                answer[i] = x + 1;
            } else {
                long temp = x;
                int c = 0;
                while (temp % 2 == 1) {
                    temp /= 2;
                    c++;
                }
                long increment = (long)Math.pow(2, c - 1);
                answer[i] = x + increment;
            }
        }
        return answer;
    }
}

from collections import defaultdict

def solution(numbers):    
    memo = defaultdict(int)
    memo[1] = 2
    result = [0 for i in range(len(numbers))]
    
    for i, num in enumerate(numbers):
        if memo[num] > 0:
            result[i] = memo[num]
            continue
        
        if num % 2 == 0:
            memo[num] = num + 1
            result[i] = memo[num]
            continue
        
        temp = '0' + bin(num)[2:]
        right_idx = temp.rfind('0')
        temp_list = list(temp)
        
        temp_list[right_idx] = '1'
        temp_list[right_idx+1] = '0'
        
        temp_str = "".join(temp_list)
        memo[num] = int("0b" + temp_str, 2)
        result[i] = memo[num]
        
    return result

from collections import deque

def solution(skill, skill_trees):
    #선행 스킬 순서가 있는 스킬 set
    skillSet = set(skill) 
    answer = 0
    for skillTree in skill_trees:
        skillDeque = deque(skill)
        isPass = True
        for getSkill in skillTree:
            #선행 스킬 순서가 있는 스킬일 경우
            if getSkill in skillSet:
                #선행 스킬중 먼저 배워야하는 스킬을 들고와 현재 스킬트리의 스킬과 일치하는지 확인(일치하지 않을 시 선행 스킬에 맞지 않음)
                if getSkill != skillDeque.popleft():
                    isPass = False
                    break
        if isPass:
            answer += 1
    return answer

import collections
def match(skill, tree):
    skill = collections.deque(skill)
    skill_list = set(skill)
    
    for s in tree:
        if s in skill_list:
            if skill[0] == s:
                skill_list.remove(s)
                skill.popleft()
                
            else:
                return False
            
    return True
    

def solution(skill, skill_trees):
    result = map(lambda t: match(skill, t), skill_trees)
    return collections.Counter(result)[True]

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for(int i = 0; i < skill_trees.length; i++) {
            String skillTree = skill_trees[i];
            String filtered = skillTree.replaceAll("[^" + skill + "]", "");
            if(skill.startsWith(filtered)) {
                answer++;
            }
        }
        return answer;
    }
}

def solution(skill, skill_trees):
    cnt = 0
    ss = set(skill)
    for st in skill_trees:
        i = 0
        flag = True
        for ch in st:
            if ch not in ss:
                continue
            if skill[i] != ch:
                flag = False
                break
            i += 1
                
        if flag:
            cnt += 1
    
    return cnt

import re

def solution(skill, skill_trees):
    cnt = 0
    r = re.compile(f"[{skill}]")
    for st in skill_trees:
        i = 0
        flag = True
        for ch in r.findall(st):
            if skill[i] != ch:
                flag = False
                break
            i += 1
        
        if flag:
            cnt += 1
    
    return cnt

import math

def solution(n, k):
    answer = []
    # 사람들(번호) 리스트
    numList = [i for i in range(1, n+1)]
    #남은 사람의 수
    remain = n
    #현재 자리에 사람이 정해졌을 때 가능한 나머지 자리에 배치 할 수 있는 경우의 수 = factorial(남은사람의 수)
    k -= 1
    #처음에 첫번째 자리가 정해졌을 때 가능한 경우의 수 factorial에서 나누어간다
    current = math.factorial(n-1)
    while remain > 0:
        #원하는 k번째 방법 // current = 현재 자리에 가능한 사람의 최대 사전 순
        index = k // current
        k %= current
        #정한 사람의 번호 제거
        answer.append(numList.pop(index))
        remain -= 1
        if remain>0:
            current //= remain
    return answer

import java.util.*;

class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        long[] fac = new long[n];
        List<Integer> numbers = new ArrayList<>();
        
        fac[0] = 1;
        for (int i = 1; i < n; i++) {
            fac[i] = fac[i-1] * i;
        }
        
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }
        
        k--;
        
        for(int i = 0; i < n; i++) {
            int idx = (int)(k / fac[n - i - 1]);
            answer[i] = numbers.get(idx);
            numbers.remove(idx);
            k %= fac[n - i - 1];
        }
        
        return answer;
    }
}

memo = {}
def factorial(n):
    global memo
    
    if n <= 1:
        return 1
    
    if n in memo:
        return memo[n]
    
    memo[n] = n * factorial(n - 1)
    return memo[n]    

def recursive(n, avail, k):
    if n == 0:
        return []
    
    msn = factorial(len(avail) - 1) # most significant number
    idx = k // msn
    
    current = avail.pop(idx)
    
    return [current] + recursive(n - 1, avail, k % msn)
    
def solution(n, k):
    available = [n for n in range(1, n + 1)]
    
    # k == 1-index, convert to 0-idx
    return recursive(n, available, k - 1)

def solution(n, k):
    f = 1
    for i in range(1, n + 1):
        f *= i
    
    nums = [i for i in range(1, n + 1)]
    ans = []
    while n > 1:
        f = f // n
        
        num = nums[(k - 1) // f]
        ans.append(num)
        nums.remove(num)
        
        n -= 1
        k %= f
        
    ans.append(nums[-1])
    return ans

def solution(numbers, target):
    answer = 0
    def calculate(index,current):
        nonlocal  answer
        if index == len(numbers):
            if current == target:
                answer +=1
            return
        calculate(index+1,current+numbers[index])
        calculate(index+1,current-numbers[index])
    calculate(0,0)
    return answer

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        ArrayList<Integer> q = new ArrayList<>();
        q.add(0);
        
        for (int number : numbers) {
            ArrayList<Integer> tmp = new ArrayList<>();
            
            for (int a : q) {
                tmp.add(a - number);
                tmp.add(a + number);
            }
            q = tmp;
        }
        
        for (int x : q) {
            if (x == target) {
                answer++;
            }
        }
        
        return answer;
    }
}

import sys
cnt = 0

sys.setrecursionlimit(50)
def recursive(current, numbers, target):
    global cnt
    if len(numbers) == 0:    
        if current == target:
            cnt += 1
            
        return
    
    cur_num = numbers[0]
    
    recursive(current + cur_num, numbers[1:], target)
    recursive(current - cur_num, numbers[1:], target)
    
def solution(numbers, target):
    global cnt
    recursive(0, numbers, target)
    
    return cnt

def bf(numbers, target, i, acc):
    if i == len(numbers):
        return 1 if acc == target else 0
    
    return bf(numbers, target, i + 1, acc + numbers[i]) + bf(numbers, target, i + 1, acc - numbers[i])

def solution(numbers, target):
    return bf(numbers, target, 0, 0)

from collections import deque
class Node:
    def __init__(self, name):
        self.name = name
        self.children = []
def solution(tickets):
    nodes = {}
    tickets.sort(key=lambda x: x[1]) #가능한 경로를 알파벳 순서로 정렬
    for ticket in tickets: #경로 tree 구현
        start, end = ticket
        nodes[start] = nodes.get(start, Node(start))
        nodes[end] = nodes.get(end, Node(end))
        nodes[start].children.append(nodes[end])
    #DFS (경로,이동한 횟수, 남은 티켓들)
    queue = deque([(["ICN"],0,tickets)])
    ticketLen = len(tickets)
    while queue:
        path,cnt,notVisited = queue.popleft()
        if cnt == ticketLen: return path
        #현재 공항에서 가능한 경로들
        for node in nodes[path[-1]].children:
            #이동한 경로
            move = [path[-1],node.name]
            #사용한 티켓이 아닌 경우
            if move in notVisited:
                newVisited = notVisited.copy()
                newVisited.remove(move)
                queue.append((path+[node.name],cnt+1,newVisited))
    return []

import java.util.*;

class Solution {
    public String[] solution(String[][] tickets) {
        Map<String,PriorityQueue<String>> maps = new HashMap<>();
        List<String> answer = new ArrayList<>();
        
        for (String[] ticket : tickets) {
            maps.computeIfAbsent(ticket[0], k -> new PriorityQueue<>()).add(ticket[1]);
        }
        
        dfs("ICN", maps, answer);
        Collections.reverse(answer);
        
        return answer.toArray(new String[0]);
    }
    
    private void dfs(String start, Map<String,PriorityQueue<String>> maps, List<String> answer) {
        PriorityQueue<String> target = maps.get(start);
        while(target != null && !target.isEmpty()) {
            String next = target.poll();
            dfs(next, maps, answer);
        }
        
        answer.add(start);
    }
}

import collections

def recursive(cur, airport, ticket_remain):
    if ticket_remain == 0:
        return [cur]
    
    airport[cur].sort()

    for idx, (next_ap, visited) in enumerate(airport[cur]):        
        if visited:
            continue
        
        airport[cur][idx][1] = True
        result = recursive(next_ap, airport, ticket_remain - 1)
        airport[cur][idx][1] = False
        
        if result is not None:
            return [cur] + result
        
        
    
    
def solution(tickets):
    airport = collections.defaultdict(list)
    
    for (src, dst) in tickets:
        airport[src].append([dst, False]) # [dst, visited]
        
    ticket_remain = len(tickets)
    return recursive('ICN', airport, ticket_remain)

def solution(tickets): 
    answer = []
    used = [False for _ in tickets]
    
    def dfs(path):
        if len(path) == len(tickets) + 1:
            answer.append(path)
            return
        
        for idx, ticket in enumerate(tickets):
            if ticket[0] == path[len(path) - 1] and not used[idx]:
                used[idx] = True
                dfs(path + [ticket[1]])
                used[idx] = False
        
    dfs(["ICN"])
    answer.sort()
    return answer[0]

import heapq

def solution(jobs):
    # 요청 순서대로 정렬
    jobs.sort()
    total, current, complete = 0, 0, 0
    waiting = []
    jobs_cnt = len(jobs)
    
    while complete < jobs_cnt:
        # 현재 시간에 있는 작업을 대기 시킴
        while jobs and jobs[0][0] <= current:
            begin, duration = jobs.pop(0) # 작업 시작 시간, 소요 시간
            heapq.heappush(waiting, (duration, begin)) # 소요 시간 기준 대기
            
        if waiting:
            # 대기 중인 요청 중 가장 짧은 요청 처리
            duration, begin = heapq.heappop(waiting)
            current += duration
            total += current - begin
            complete += 1
        else:
            # 대기 중인 요청이 없으면 다음 요청 작업 시작
            current = jobs[0][0] if jobs else current
            
    answer = total // jobs_cnt
    return answer

import heapq

INSERT = 1
LEN = 0

def solution(jobs):
    queue = []
    
    jobs.sort()
    queue.append((jobs[0][1], jobs[0][0]))
    
    current_ms = 0
    jobs_cur = 1
    
    job_waittime = 0
    
    while queue:
        item = heapq.heappop(queue)
        
        job_waittime += max(current_ms - item[INSERT], 0) + item[LEN]
        current_ms = max(current_ms + item[LEN], item[INSERT] + item[LEN])
        
        for available_job in jobs[jobs_cur:]:
            if available_job[0] > current_ms:
                break
            
            heapq.heappush(queue, (available_job[1], available_job[0]))
            jobs_cur += 1
        
        if not queue and jobs_cur < len(jobs):
            available_job = jobs[jobs_cur]
            queue.append((available_job[1], available_job[1]))
            jobs_cur += 1
    
        
    return job_waittime // len(jobs)

def solution(jobs):
    answer = 0
    jobs.sort()
    n = len(jobs)
    time = 0
    total_time = 0
    completed = [False] * n
    
    while not all(completed):
        min_task = float('inf')
        index = -1
        
        for i in range(n):
            if not completed[i] and jobs[i][0] <= time and jobs[i][1] <= min_task:
                min_task = jobs[i][1]
                index = i
        if index != -1:
            time += jobs[index][1]
            total_time += time - jobs[index][0]
            completed[index] = True
        else:
            time += 1
            
    return total_time // n

def solution(jobs):
    jobsLen = len(jobs)
    #끝나는 시점을 기준으로 sort
    #이렇게 정렬하게 되면 현재 시간을 기준으로 가장 짧은 작업부터 시작할 수 있게 된다
    jobs = sorted(jobs, key=lambda x: x[1])
    #총 걸린 시간
    answer = 0
    #현재 시간
    time = 0
    while jobs:
        notFound = True
        for idx, job in enumerate(jobs):
            #가장 짧은 작업을 가져오는데 이가 현재 시점에서 시작하는 작업인가를 확인
            #맞을 시 해당 작업을 answer및 time에 추가해준다
            if time >= job[0]:
                jobs = jobs[:idx] + jobs[idx+1:]
                answer += time + job[1] - job[0]
                time += job[1]
                notFound = False
                break
        #만약 어떠한 작업도 현재 시점에서는 실행할 수 없으면 가장 빠르게 실행할 수 있는 시점으로 이동한다(기다린다)
        if notFound and jobs:
            time = min(job[0] for job in jobs)
    return answer // jobsLen

import heapq

def solution(jobs):
    hq = []
    
    for j in jobs:
        heapq.heappush(hq, (j[0], j[1]))
    
    cur = 0
    pt = 0
    while len(hq) > 0:
        arr = []
        while len(hq) > 0 and hq[0][0] <= cur:
            arr.append(heapq.heappop(hq))
        
        if len(arr) == 0:
            tmp = heapq.heappop(hq)
            pt += tmp[1]
            cur = tmp[0] + tmp[1]
            continue
        
        arr.sort(key = lambda p: p[1])
        wt = (cur - arr[0][0]) + arr[0][1]
        pt += wt
        cur = cur + arr[0][1]
        
        for i in range(1, len(arr)):
            heapq.heappush(hq, (arr[i][0], arr[i][1]))

    return pt // len(jobs)

def solution(gems):
    ### pre setup ###
    items = dict()
    
    # filling gems
    for name in gems:
        if name not in items:
            items[name] = 0
    
    items_cnt = len(items)
    # end setup ##
    
    
    min_distance = len(gems)
    min_pos = (0, 0) #(start_pos, end_pos)
    
    ptr_start = 0
    ptr_end = 0
    current_el = dict()
    
    while ptr_end < len(gems):       
        # 부족한 상황에는 다 추가
        if len(current_el) < items_cnt:
            if gems[ptr_end] not in current_el:
                current_el[gems[ptr_end]] = 0
                
            current_el[gems[ptr_end]] += 1
        
        # 항목이 다 있는 상태. 부족해질 때 까지 앞으로 땡길것.
        while len(current_el) == items_cnt and ptr_start <= ptr_end:
            distance = ptr_end - ptr_start
            if distance < min_distance:
                min_pos = (ptr_start, ptr_end)
                min_distance = distance
                        
            current_el[gems[ptr_start]] -= 1            
            if current_el[gems[ptr_start]] == 0:
                del current_el[gems[ptr_start]]
                
            ptr_start += 1
        
        ptr_end += 1
        
    return list(map(lambda v: v + 1, min_pos))

def solution(gems):
    unique_gems = set(gems)
    num_unique_gems = len(unique_gems)
    num_gems = len(gems)

    start = end = 0
    gem_dict = {gems[0]: 1}
    answer = [0, num_gems - 1]

    while start < num_gems and end < num_gems:
        if len(gem_dict) == num_unique_gems:
            if end - start < answer[1] - answer[0]:
                answer = [start, end]
            gem_dict[gems[start]] -= 1
            if gem_dict[gems[start]] == 0:
                del gem_dict[gems[start]]
            start += 1
        else:
            end += 1
            if end < num_gems:
                gem_dict[gems[end]] = gem_dict.get(gems[end], 0) + 1

    return [answer[0] + 1, answer[1] + 1]

from collections import defaultdict

def solution(gems):
    n = len(set(gems))
    
    m = len(gems)
    i, j = 0, 0
    jewelry_box = defaultdict(int)
    jewelry_box[gems[0]] += 1
    result = [0, m - 1]
    
    
    while i <= j < m:
        if len(jewelry_box) == n:
            if result[1] - result[0] + 1 > j - i + 1:
                result[0], result[1] = i, j
            
            if jewelry_box[gems[i]] == 1:
                del jewelry_box[gems[i]]
            else:
                jewelry_box[gems[i]] -= 1
            i += 1
        else:
            j += 1
            if j == m:
                break
            jewelry_box[gems[j]] += 1
    
    result[0] += 1
    result[1] += 1
    
    return result

def solution(gems):
    #잼들의 종류를 모아놓은 set
    gemList = set()
    for gem in gems:
        gemList.add(gem)
    #잼들의 종류의 개수
    gemListLen = len(gemList)
    startPoint = 0
    #진열대에 있는 모든 잼들의 개수
    gemLen = len(gems)
    endPoint = gemLen
    #현재 살 수 있는 잼을 key로 개수를 value로 저장
    check = {}
    start = 0
    #end를 점점 키우면서 check에 값을 더해나가는데 start를 늘려 전체적인 길이를 줄일 수 있으면 줄인다
    for end in range(gemLen):
        #check에 gem 추가
        check[gems[end]] = check.get(gems[end],0)+1
        #만약 현재 모든 종류의 잼을 살 수 있는 상태라면 start의 크기를 늘릴 수 있을 만큼 늘려가면서 길이를 줄인다
        while len(check)==gemListLen:
            #길이가 더 작으면 저장
            if end-start < endPoint-startPoint:
                startPoint,endPoint = start+1,end+1
            #start부분의 잼 들고오기
            num = check.get(gems[start],1)
            #만약 잼이 1개밖에 없다면 해당 잼을 check에서 제거
            if num == 1 :
                del check[gems[start]]
            #잼이 1개 이상 있다면 그 개수를 1개 줄여준다
            else:
                check[gems[start]]-=1
            start+=1
    return [startPoint,endPoint]

def solution(n, costs):
    # 리스트 정렬(비용기준)
    costs.sort(key=lambda x: x[2])
    
    connection = set([costs[0][0]])
    
    total = 0
    
    while len(connection) < n:
        for x, y, cost in costs:
            if x in connection and y not in connection:
                connection.add(y)
                total += cost
                break
            elif y in connection and x not in connection:
                connection.add(x)
                total += cost
                break
    
    return total

import heapq
def solution(n, costs):
    # costs -> list[[land_start_idx, land_end_idx, cost(weight)]]
    order_by_cost_asc = sorted(list(map(lambda v: (v[2], v[0], v[1]), costs)))
    
    lands = set(map(lambda v: v[0], costs))
    lands.update(set(map(lambda v: v[1], costs)))
    
    lands_area = dict()
    lands_area_rep = dict()
    for idx in lands:
        lands_area[idx] = idx
        lands_area_rep[idx] = set([idx])
        
    ### end setup ####
    belong = set()
    cost_sum = 0
    for (cost, start_idx, end_idx) in order_by_cost_asc:
        if lands_area[start_idx] == lands_area[end_idx]:
            continue
        
        cost_sum += cost
        merged_from = lands_area[start_idx]
        merged_to = lands_area[end_idx]
        
        lands_area_rep[merged_to].update(lands_area_rep[merged_from])
        lands_area_rep[merged_from].update(lands_area_rep[merged_to])
        
        for old_idx in lands_area_rep[merged_from]:
            lands_area[old_idx] = merged_to

        if len(lands_area_rep[merged_to]) == len(lands):
            break
            
    return cost_sum

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        parent[x] = y

def solution(n, costs):
    costs.sort(key=lambda x: x[2])
    
    global parent
    parent = list(range(n))
    
    total_cost = 0
    cnt = 0
    
    for cost in costs:
        x, y, c = cost
        if find(x) != find(y):
            union(x, y)
            total_cost += c
            cnt += 1
            if cnt == n - 1:
                break
    
    return total_cost

# from collections import defaultdict

def sumMst(belong_to, first_mst_num, second_mst_num):
    for i, node_mst_num in enumerate(belong_to):
        if node_mst_num == first_mst_num:
            belong_to[i] = second_mst_num

def solution(n, costs):
    costs.sort(key = lambda e: (e[2], e[1], e[2]))
    
    belong_to = [-1 for i in range(n)]
    result = 0
    mst_num = 0
    for cost in costs:
        check = set(belong_to)
        if -1 not in check and len(check) == 1:
            break
            
        if belong_to[cost[0]] >= 0 and belong_to[cost[0]] == belong_to[cost[1]]:
            continue
            
        if belong_to[cost[0]] == -1 and belong_to[cost[1]] == -1:
            belong_to[cost[0]] = mst_num
            belong_to[cost[1]] = mst_num
            mst_num += 1
            result += cost[2]
            continue
        
        if belong_to[cost[0]] >= 0:
            if belong_to[cost[1]] == -1:
                belong_to[cost[1]] = belong_to[cost[0]]
            else:
                sumMst(belong_to, belong_to[cost[0]], belong_to[cost[1]])
            
            result += cost[2]
            continue
        if belong_to[cost[1]] >= 0:
            if belong_to[cost[0]] == -1:
                belong_to[cost[0]] = belong_to[cost[1]]
            else:
                sumMst(belong_to, belong_to[cost[1]], belong_to[cost[0]])
                
            result += cost[2]
            continue
    return result

def solution(n, costs):
    #비용의 순서로 정렬
    #비용이 작은 순으로 간선을 연결하여 최소비용이 되도록 만든ㄴ다
    costs = sorted(costs,key = lambda x : x[2])
    #index는 child 섬 value는 parent 섬
    #초기에는 자기 자신이 부모, 자식 노드
    parent = [i for i in range(n)]
    #두 노드의 부모 노드를 찾고 만약 같은 경우 같은 tree에 존재하는 것 임으로 pass
    #만약 부모 노드가 다르면 서로 다른 tree에 존재하는 것 임으로 이를 한 노드를 부모노드로 저장해주어 연결시킨다 
    def union(x,y):
        xFind = find(x)
        yFind = find(y)
        if xFind == yFind: return
        parent[xFind] = yFind
    #부모 노드를 찾는 함수
    def find(x):
        if parent[x] == x:
            return x
        return find(parent[x])
    answer = 0
    cnt = 0
    for i in range(len(costs)):
        #두 노드의 부모 노드가 다를 시(두 노드가 하나의 tree로 연결되어있지 않을 시)
        if find(costs[i][0])!=find(costs[i][1]):
            #두 노드 연결
            union(costs[i][0],costs[i][1])
            #총 비용에 현재 간선의 비용 추가
            answer+=costs[i][2]
            #방문한 노드의 수 +1
            cnt+=1
        #모든 노드를 방문했으면 바로 return
        if cnt == n :return
    return answer

# 55점

def solution(words, queries):
    words_by_length = {}
    for word in words:
        length = len(word)
        if length not in words_by_length:
            words_by_length[length] = []
        words_by_length[length].append(word)
    
    answer = []
    
    for query in queries:
        count = 0
        length = len(query)
        if length not in words_by_length:
            answer.append(0)
            continue
        
        if query[0] == '?':
            idx = query.rfind('?') + 1
            sub_query = query[idx:]
            for word in words_by_length[length]:
                if word.endswith(sub_query):
                    count += 1
        else:
            idx = query.find('?')
            sub_query = query[:idx]
            for word in words_by_length[length]:
                if word.startswith(sub_query):
                    count += 1
        
        answer.append(count)
    
    return answer

import collections
from typing import *
class Node:
    children = {}
    cnt = 0
    root = None
    
    def __init__(self, root = None):
        self.children = dict()
        self.root = root
        
    def push(self, c):
        if c not in self.children:
            self.children[c] = Node(self)
            
        return self.children[c]
    
    '''
    push가 완료되면 반드시 flush로 뒷정리를 해줘야 함.
    '''
    def flush(self):
        root_ptr = self
        while root_ptr != None:
            root_ptr.cnt += 1
            root_ptr = root_ptr.root
    
    def __str__(self):
        return str(self.children)
    
    def __repr__(self):
        return str(self.children)
    
    def match_cnt(self, str_slice):
        node_ptr = self
        
        for c in str_slice:
            if c == '?':
                return node_ptr.cnt
            
            if c not in node_ptr.children:
                return 0
            
            node_ptr = node_ptr.children[c] 
        
        return node_ptr.cnt

def solution(words, queries):
    trie_forward = collections.defaultdict(Node)
    trie_backward = collections.defaultdict(Node)
    
    for w in words:
        l = len(w)
        
        # fill forward
        node_ptr = trie_forward[l]
        for c in w:
            node_ptr = node_ptr.push(c)
        node_ptr.flush()
            
        node_ptr = trie_backward[l]
        for c in reversed(w):
            node_ptr = node_ptr.push(c)
        node_ptr.flush()
            
    ans = []
    for q in queries:
        l = len(q)
        res = 0
        if q[0] == '?':
            res = trie_backward[l].match_cnt(q[::-1])
        else:
            res = trie_forward[l].match_cnt(q)
                
        ans.append(res)
        
    return ans

# 100점중 55점 (시간초과). 대신 3분만에 구현완료. 시간 안될것 같으면 부분점수 라도 얻는게?
import re
def solution(words, queries):
    result = []
    for q in queries:
        r = re.compile('^' + q.replace('?', '.') + '$')
        
        cnt = 0
        for w in words:
            if r.match(w) is not None:
                cnt += 1
                
        result.append(cnt)
        
    return result

from bisect import bisect_left, bisect_right

MAX_WORD_LEN = 100_001

def solution(words, queries):
    asc = [[] for i in range(MAX_WORD_LEN)]
    rev_asc = [[] for i in range(MAX_WORD_LEN)]
    
    for w in words:
        n = len(w)
        asc[n].append(w)
        rev_asc[n].append(w[::-1])
    
    for i in range(1, MAX_WORD_LEN):
        asc[i].sort()
        rev_asc[i].sort()
    
    result = [0 for i in range(len(queries))]
    for i, q in enumerate(queries):
        left, right = 0, 0
        
        if q[0] == "?":
            q = q[::-1]
            left = bisect_left(rev_asc[len(q)], q.replace("?", "a"))
            right = bisect_right(rev_asc[len(q)], q.replace("?", "z"))
        else:
            left = bisect_left(asc[len(q)], q.replace("?", "a"))
            right = bisect_right(asc[len(q)], q.replace("?", "z"))
        
        result[i] = right - left
    
    return result

class Node:
    def __init__(self, data):
        #현재 가사
        self.data = data
        #다음 가사
        self.child = {}
        #가사의 끝인 경우 true
        self.isEnd = False

def solution(words, queries):
    #?가 앞에 나오는 경우와 뒤에 나오는 경우 각각 reverseRoot tree와 forwardRoot를 사용하여 검색한다
    #두 트리 모두 가사의 순서대로 tree를 만드는데 예를들어 frodo의 경우 f가 루트 r이 자식 노드 그 자식노드가 o가 된다
    #fowardRoot는 앞에서 부터 순서대로 tree를 만든것이고 reverseRoot는 반대이다
    #이를 나눈 이유는 ?가 나올때는 모든 자식 노드들을 보아야하는데 ?????o같은 경우 모든 노드들을 보아야하는데 reverseRoot를 가지고 뒤에서 부터 맞추어 나간다면 경우의 수를 확연히 줄일 수 있다 
    forwardRoot = Node(None)
    reverseRoot = Node(None)
    #가사를 글자 순서대로(또는 글자 순서 반대로) tree를 만들어 준다
    def addChild(text,node):
        for char in text:
            if char not in node.child:
                node.child[char] = Node(char)
            node = node.child[char]
        node.isEnd = True
    for word in words:
        addChild(word,forwardRoot)
        addChild(word[::-1],reverseRoot)
    #tree를 가지고 가사를 찾아주는 함수
    def find(text,root):
        nodes = [root]
        length = len(text)
        cnt = 0
        for idx, char in enumerate(text):
            newNodes = []
            for node in nodes:
                #?일 경우 모든 자식 노드들을 append
                if char == "?":
                    #가사의 마지막인 경우 매치된 총 수에 모든 자식의 노드의 수를 더해준다
                    if idx == length - 1:
                        for childNode in node.child.values():
                            if childNode.isEnd:
                                cnt += 1
                    else:
                        newNodes.extend(node.child.values())
                #자식 노드 중 순서에 맞고 알파벳이 일치할 경우 해당 자식을 추가해준다
                elif char in node.child:
                    childNode = node.child[char]
                    #가사의 마지막일 경우 매치된 총 수에 1을 더해준다
                    if idx == length - 1:
                        if childNode.isEnd:
                            cnt += 1
                    else:
                        newNodes.append(childNode)
            nodes = newNodes
            #만약 순서와 알파벳이 맞는 자식노드가 없으면 break
            if not nodes:
                break
        return cnt
    #중복된 검색이 있을 수 있음으로 dictionary에 저장
    answerDic = {}
    answer = []
    for query in queries:
        if query not in answerDic:
            #?부터 시작할 시 reverRoot를 반대일시 forwardRoot를 사용
            if query[0]=="?":
                answerDic[query] = find(query[::-1],reverseRoot)
            else:            
                answerDic[query] = find(query,forwardRoot)
        answer.append(answerDic[query])
    return answer

n = int(input())
answer = 0
before = 0
modNum = 1000_000_007
#현재 줄의 값의 합 = (현재 줄의 값 * (이전 줄의 값의 합+1)) % 1000000007
# ex)문제에서 cpu4에서는 6+6+3 = 3(2+2+1) = 현재줄의 값*(이전줄의 값+1)
for m in list(map(int, input().split())):
    before = (m*(before+1))%modNum
    answer = (answer+before)%modNum
print(answer %modNum)

n = int(input())
arr = list(map(int, input().split(" ")))
MOD = 1000000007

sum = arr[0] % MOD
pre = sum
for i in range(1, n - 1):
    pre = ((pre + 1) * arr[i]) % MOD
    sum = (sum + pre) % MOD
        
print(int(sum))

MOD = 10**9+7

n = int(input())
cpu = list(map(int, input().split()))

dp = [0] * n
dp[0] = cpu[0] % MOD

sum = dp[0]
for i in range(1, n-1):
    dp[i] = ((dp[i-1] + 1) * cpu[i]) % MOD
    sum = (sum + dp[i]) % MOD

print(sum)

import sys

# n = 500_000
# multiply = [i for i in range(1, 500_001)]

n = int(sys.stdin.readline())
multiply = tuple(map(int, sys.stdin.readline().split(' ')))

current = 0
last = 0
result = 0

for i in range(n - 2, -1, -1):
    current = (current * multiply[i] + multiply[i]) % 1_000_000_007
    result = (result + current) % 1_000_000_007

print(result)

# 30점 부분점수

import sys

# n = 500_000
# multiply = [i for i in range(1, 500_001)]

n = int(sys.stdin.readline())
multiply = tuple(map(int, sys.stdin.readline().split(' ')))

arr = [0] * n
arr[-1] = multiply[-1]
result = multiply[-1]
for i in range(n - 2, 0, -1):
    arr[i] = arr[i + 1] * multiply[i - 1] + multiply[i - 1]
    result = (result + arr[i]) % 1_000_000_007

print(result)

import sys
import collections

def solve(n):
    nums = collections.deque((1, 1, 1))
    current = 3

    if n <= 3:
        nums[n - 1]

    while current < n:
        nums.append(nums.popleft() + nums[0])
        current += 1

    return nums[-1]


T = int(sys.stdin.readline())
for _ in range(T):
    print(solve(int(sys.stdin.readline())))

t = int(input())
nArr = [int(input()) for _ in range(t)]
sieve = [0,1,1,1,2]
#6번째 이후 부터는 이전 번째 값 + 5번째 이번 값
for n in nArr:
    for i in range(len(sieve),n+1):
        sieve.append(sieve[i-1]+sieve[i-5])
    print(sieve[n])

import sys

n = int(sys.stdin.readline())

dp = [0 for i in range(100)]
dp[0], dp[1], dp[2] = 1, 1, 1

for i in range(3, 100):
    dp[i] = dp[i - 3] + dp[i - 2]

for i in range(n):
    x = int(sys.stdin.readline())
    sys.stdout.write(f"{dp[x - 1]}\n")

t = int(input())
dp = [0] * 101

dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 2
dp[5] = 2
dp[6] = 3
dp[7] = 4
dp[8] = 5
dp[9] = 7
dp[10] = 9

for i in range(11, 101):
    dp[i] = dp[i-1] + dp[i-5]

for _ in range(t):
    n = int(input())
    print(dp[n])

from collections import deque

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

max_len, before_max_len, max_num = 0, 0, 0

def bfs(start_x, start_y):
    global max_len, before_max_len, max_num
    visited = [[0] * m for _ in range(n)]
    q = deque([(start_x, start_y)])
    visited[start_x][start_y] = 1
    end_x, end_y = start_x, start_y
    
    while q:
        x, y = q.popleft()
        if grid[x][y] == 0: 
            continue
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] != 0 and not visited[nx][ny]:
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))
                end_x, end_y = nx, ny

    if visited[end_x][end_y] > max_len:
        max_len = visited[end_x][end_y]
        max_num = grid[start_x][start_y] + grid[end_x][end_y]
        before_max_len = visited[end_x][end_y]
    elif visited[end_x][end_y] == max_len:
        max_num = max(max_num, grid[start_x][start_y] + grid[end_x][end_y])

for i in range(n):
    for j in range(m):
        if grid[i][j] != 0:
            bfs(i, j)

print(max_num)

from collections import deque 

n, m = list(map(int, input().split(" ")))

arr = [[0 for j in range(m)] for i in range(n)]

for i in range(n):
    tmp = list(map(int, input().split(" ")))
    for j in range(m):
        arr[i][j] = tmp[j]

d = list(zip([0, 1, 0, -1], [1, 0, -1, 0]))
dm = 0
result = 0
queue = deque()
visit = [[False for b in range(m)] for a in range(n)]

for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            continue

        queue.clear()
        queue.append([i, j, 0])
        for a in range(n):
            for b in range(m):
                visit[a][b] = False
        visit[i][j] = True

        dis_max = 1
        room_num_max = 0

        while len(queue) > 0:
            next = queue.popleft()
            x = next[0]
            y = next[1]
            dis = next[2]

            if dis > dis_max:
                room_num_max = arr[x][y]
                dis_max = dis
            elif dis == dis_max:
                room_num_max = max(room_num_max, arr[x][y])

            for dx, dy in d:
                nx = x + dx
                ny = y + dy

                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if arr[nx][ny] == 0 or visit[nx][ny]:
                    continue
                
                visit[nx][ny] = True
                queue.append([nx, ny, dis + 1])
        
        if (dis_max == 0):
            continue
        
        if dis_max > dm:
            dm = dis_max
            result = arr[i][j] + room_num_max
        elif dis_max == dm:
            result = max(result, arr[i][j] + room_num_max)

print(0 if dm == 0 else result)

from collections import deque

n, m = map(int, input().split())
mapGrid = [list(map(int, input().split())) for _ in range(n)]
maxVal = 0
maxResults = []
def bfs(i, j):
    visited = set()
    queue = deque([(i, j, 0)])
    global maxVal,maxResults
    while queue:
        row, column, cnt = queue.popleft()
        # visit한 곳이거나 0이라서 갈 수 없는 곳이라면 continue
        if (row, column) in visited or mapGrid[row][column] == 0:
            continue
        visited.add((row, column))
        #현재까지 길이 중 가장 긴 길이라면 maxVal과 maxResults를 갱신
        if cnt > maxVal:
            maxVal = cnt
            maxResults = [(i,j,row, column)]
        #현재까지 길이가 maxVal과 같다면 maxResults에 추가
        elif cnt == maxVal:
            maxResults.append((i,j,row, column))
        if row > 0:
            queue.append((row - 1, column, cnt + 1))
        if row < n - 1:
            queue.append((row + 1, column, cnt + 1))
        if column > 0:
            queue.append((row, column - 1, cnt + 1))
        if column < m - 1:
            queue.append((row, column + 1, cnt + 1))
#브루트 포스로 모든 경우의 수를 탐색
for i in range(n):
    for j in range(m):
        bfs(i,j)
result = 0
for startI,startJ,endI,endJ in maxResults:
    result = max(result,mapGrid[endI][endJ] + mapGrid[startI][startJ])
print(result)

import sys
import collections
y_len, x_len = map(int, sys.stdin.readline().split(' '))

matrix = [tuple(map(int, sys.stdin.readline().split(' '))) for _ in range(y_len)]

def fartest(x, y):
    visited = [[0] * x_len for _ in range(y_len)]
    to_visit = collections.deque()

    if matrix[y][x] == 0:
        return -1, -1
    
    to_visit.append((x, y, 0))
    last = (-1, -1, -1)
    while to_visit:
        x_cur, y_cur, l = to_visit.popleft()
        if y_cur < 0 or y_cur >= y_len:
            continue
        if x_cur < 0 or x_cur >= x_len:
            continue
        if matrix[y_cur][x_cur] == 0:
            continue
        
        if visited[y_cur][x_cur] != 0:
            continue
        
        last = (x_cur, y_cur, l)
        visited[y_cur][x_cur] = 1

        to_visit.append((x_cur + 1, y_cur, l + 1))
        to_visit.append((x_cur - 1, y_cur, l + 1))
        to_visit.append((x_cur, y_cur + 1, l + 1))
        to_visit.append((x_cur, y_cur - 1, l + 1))

    return last[2], matrix[y][x] + matrix[last[1]][last[0]]



max_l, max_s = 0, 0

for cur_y in range(y_len):
    for cur_x in range(x_len):
        l, s = fartest(cur_x, cur_y)

        if l == -1:
            continue

        if max_l < l:
            max_l = l
            max_s = s
        
        elif max_l == l and max_s < s:
            max_s = s

print(max_s)

size = int(input())

for i in range(size):
    n = int(input())

    buttons = [0 for i in range(5)]
    sixties, tens, ones = n // 60, (n % 60) // 10, n % 10

    if ones > 5:
        tens += 1
        ones -= 10
    if tens > 3:
        sixties += 1
        tens -= 6
    if tens < 0 and ones == 5: # 30~60인데 일의 자리가 5인 경우는 빼는게 낫다.
        tens += 1
        ones -= 10

    buttons[0] = sixties
    buttons[1 if tens >= 0 else 2] = abs(tens)
    buttons[3 if ones >= 0 else 4] = abs(ones)

    print(*buttons)

t = int(input())
for _ in range(t):
    n = int(input())
    result = [0] * 5
    x = n

    if x > 60:
        result[0] += x // 60
        x %= 60

    if x > 35:
        result[0] += 1
        x = 60 - x
        if x % 10 > 5:
            result[2] += x // 10 + 1
            result[3] += 10 - (x % 10)
        else:
            result[2] += x // 10
            result[4] += x % 10
    else:
        if x % 10 > 5:
            result[1] += x // 10 + 1
            result[4] += 10 - (x % 10)
        else:
            result[1] += x // 10
            result[3] += x % 10
    print(" ".join(map(str, result)))

import sys
T = int(sys.stdin.readline())

def sum_state(a: dict[str, int]):
    return sum(a.values())

def min_state(a: dict[str, int], b: dict[str, int]):
    a_sum, b_sum = sum_state(a), sum_state(b)
    # print(a, b)
    if a_sum < b_sum:
        return a
    elif b_sum < a_sum:
        return b
    
    if a['ADDH'] < b['ADDH']:
        return a
    elif a['ADDH'] > b['ADDH']:
        return b

    if a['ADDT'] < b['ADDT']:
        return a
    elif a['ADDT'] > b['ADDT']:
        return b
    
    if a['MINT'] < b['MINT']:
        return a
    elif a['MINT'] > b['MINT']:
        return b
    
    if a['ADDO'] < b['ADDO']:
        return a
    elif a['ADDO'] > b['ADDO']:
        return b
    
    if a['MINO'] < b['MINO']:
        return a
    elif a['MINO'] > b['MINO']:
        return b
    
    # 아예 똑같은 경우
    return a

def solution(n: int):
    # cnt, result = 10_000_000, {'ADDH': 10_000_000, 'ADDT': 10_000_000, 'MINT': 10_000_000, 'ADDO': 10_000_000,  'MINO': 10_000_000}

    def solution_10(n: int, state: dict[str, int]):
        state_1 = dict(state)
        state_2 = dict(state)
        
        if abs(n) % 10 == 0:
            if n < 0:
                state_1['MINT'] = abs(n) // 10
                return state_1
            
            state_1['ADDT'] = n // 10
            return state_1


        if n < 0:
            state_1['MINT'] = abs(n) // 10
            state_2['MINT'] = (abs(n) // 10) + 1
            MINT_1 = (n % 10 - 10, state_1)
            MINT_2 = (n % 10, state_2)

            a = solution_1(*MINT_1)
            b = solution_1(*MINT_2)
            # print(a, b)
            return min_state(a, b)

        else:
            state_1['ADDT'] = n // 10
            state_2['ADDT'] = (n // 10) + 1
            ADDT_1 = (n % 10 , state_1)
            ADDT_2 = (n % 10 - 10, state_2)

            a = solution_1(*ADDT_1)
            b = solution_1(*ADDT_2)

            return min_state(a, b)


    def solution_1(n: int, state: dict[str, int]):
        state1 = dict(state)
        state2 = dict(state)
        if n < 0:
            state1['MINO'] = abs(n)
            return state1
        
        state2['ADDO'] = n
        return state2

    ADDH_1 = (n % 60, {'ADDH': n // 60, 'ADDT': 0, 'MINT': 0, 'ADDO': 0, 'MINO': 0})
    ADDH_2 = (n % 60 - 60, {'ADDH': n // 60 + 1, 'ADDT': 0, 'MINT': 0, 'ADDO': 0, 'MINO': 0})
    
    ADDH_1 = solution_10(*ADDH_1) # 108이라는 숫자가 왔을때, 60 -> +48로 갈수도
    ADDH_2 = solution_10(*ADDH_2) # 108이라는 숫자가 왔을때, 120 -> -12로 갈수도

    # print(ADDH_1, ADDH_2)
    return min_state(ADDH_1, ADDH_2)

for _ in range(T):
    result = solution(int(sys.stdin.readline()))
    print(result['ADDH'], result['ADDT'], result['MINT'], result['ADDO'], result['MINO'])

from collections import deque

t = int(input())
nArr = [int(input()) for _ in range(t)]
for n in nArr:
    #각 addt과 addo는 양수일때는 그대로 addt,addo 값이며 이가 음수 일때는 줄여야 한다고 판단하여 각 mint,mino값이 된다
    button = [0]*5
    addh = n//60
    addt = (n%60)//10
    addo = n%10
    #addo가 5이상일시 상위 시간(10분)을 돌려줘고 addo를 10분 줄이는 것이 이득
    if addo >5 :
        addt+=1
        addo-=10
    #addt가 3이상일시 상위 시간(1시간)을 돌려줘고 addt를 6분 줄이는 것이 이득
    if addt >3:
        addh+=1
        addt-=6
    #addt가 음수일때(mint가 1이상일때) 우선 순위고 addt가 더 높음으로 addo를 줄이고 addt를 늘리는 것이 더 이득이다
    if addt<0 and addo ==5:
        addt+=1
        addo-=10
    button[0] = addh
    button[2-(addt>=0)] = abs(addt)
    button[4-(addo>=0)] = abs(addo)
    print(*button)

from collections import deque

n, m = map(int, input().split(" "))

arr = [input() for i in range(n)]
visit = [[False for j in range(m)] for i in range(n)]
flag = False

for i in range(n):
    if flag:
        break
    for j in range(m):
        if visit[i][j]:
            continue

        ch = arr[i][j]
        y = j
        while y < m and arr[i][y] == ch:
            y += 1
        
        x = i
        while x < n and arr[x][j] == ch:
            x += 1
        
        size = (i - x) * (j - y)

        queue = deque()
        queue.append([i, j])
        visit[i][j] = True
        real_size = 1
        
        while len(queue) > 0:
            next = queue.popleft()
            x = next[0]
            y = next[1]

            for dx, dy in zip([0, 1], [1, 0]):
                nx = x + dx
                ny = y + dy
                
                if nx >= n or ny >= m:
                    continue
                if arr[nx][ny] != ch:
                    continue
                if visit[nx][ny]:
                    continue
                
                real_size += 1
                queue.append([nx, ny])
                visit[nx][ny] = True
        
        if size != real_size:
            print("BaboBabo")
            flag = True
            break
if flag == False:
    print("dd")

import sys
import collections
import copy

height, width = map(int, sys.stdin.readline().split(' '))

matrix = [list(sys.stdin.readline().strip()) for _ in range(height)]
visited = [[False] * width for _ in range(height)]

def is_square(x, y):
    global matrix, visited, height, width
    partial_width = 0
    partial_height = 0
    approx_width = 0
    approx_height = 0

    char = matrix[y][x]

    for cur_x in range(x, width):
        if matrix[y][cur_x] != char:
            break
        
        approx_width = cur_x
    
    for cur_y in range(y, height):
        if matrix[cur_y][x] != char:
            break

        approx_height = cur_y
     

    # visited_local = copy.deepcopy(visited)
    to_visit = collections.deque()
    to_visit.append((x, y))


    ## boundary check
    while to_visit:
        (cur_x, cur_y) = to_visit.popleft()
        # print(char, cur_x, cur_y)

        if cur_x < 0 or cur_x >= width:
            continue
        if cur_y < 0 or cur_y >= height:
            continue
        
        if matrix[cur_y][cur_x] != char:
            ## approx_width, height에 가기 전에 이미 다른게 막으면... 그건 중간에 뭐가 있는거니까 중지
            if (y <= cur_y <= approx_height) and (x <= cur_x <= approx_width):
                # print(y, cur_y, approx_height, x, cur_x, approx_width)
                # print('t')
                return False
            
            continue
        if visited[cur_y][cur_x] == True:
            continue

        if (y <= cur_y <= approx_height) == False or (x <= cur_x <= approx_width) == False:
            # print(y, cur_y, approx_height, x, cur_x, approx_width)
            return False
        
        visited[cur_y][cur_x] = True
        partial_width = max(partial_width, cur_x)
        partial_height = max(partial_height, cur_y)

        to_visit.append((cur_x + 1, cur_y))
        to_visit.append((cur_x - 1, cur_y))
        to_visit.append((cur_x, cur_y + 1))
        to_visit.append((cur_x, cur_y - 1))

    # 대각선만 검사해 보는거로 (전체 검사하니 시간초과)
    # for cur_y in range(y, partial_height + 1):
    #     if matrix[cur_y][x] != char:
    #         return False
    #     if matrix[cur_y][partial_width] != char:
    #         return False
        
    # for cur_x in range(x, partial_width + 1):
    #     if matrix[y][cur_x] != char:
    #         return False
    #     if matrix[partial_height][cur_x] != char:
    #         return False
            
    return True

for y in range(height):
    for x in range(width):
        if visited[y][x] == True:
            continue

        if is_square(x, y) == False:
            print('BaboBabo')
            exit()


print('dd')

from collections import deque
n, m = map(int, input().split())
grid = [list(input()) for _ in range(n)]
visited = set() 

def check(i, j):
    char = grid[i][j]
    checkVisited = set()
    queue = deque([(i, j)])
    maxI, maxJ = i, j
    minI, minJ = i, j

    while queue:
        currentI, currentJ = queue.popleft()
        #상하좌우 중 같은 글자를 가진 곳만 visit
        if (currentI, currentJ) in checkVisited or char != grid[currentI][currentJ]:
            continue
        checkVisited.add((currentI, currentJ))
        #방분한 곳의 좌우 끝값
        maxI = max(currentI, maxI)
        maxJ = max(currentJ, maxJ)
        minI = min(currentI, minI)
        minJ = min(currentJ, minJ)

        if currentI < n - 1:
            queue.append((currentI + 1, currentJ))
        if currentJ < m - 1:
            queue.append((currentI, currentJ + 1))
        if currentI > 0:
            queue.append((currentI - 1, currentJ))
        if currentJ > 0:
            queue.append((currentI, currentJ - 1))

    visited.update(checkVisited)
    #방문한 곳의 좌우 끝값을 이용해 방문하지 않은 곳이 있는지 확인
    for row in range(minI, maxI + 1):
        for column in range(minJ, maxJ + 1):
            if (row, column) not in checkVisited:
                return True
    return False

found = False
for i in range(n):
    for j in range(m):
        if (i, j) not in visited:
            if check(i, j):
                print("BaboBabo")
                found = True
                break
    if found:
        break

if not found:
    print("dd")

import sys
import collections
sys.setrecursionlimit(1000)

from typing import *
H, W, L = map(int, sys.stdin.readline().split(' '))
matrix = [tuple(sys.stdin.readline().rstrip()) for _ in range(H)]
FIND_WORD = sys.stdin.readline()
quick_path = [[dict() for _ in range(W)] for _ in range(H)]

def find_len(x, y):
    global quick_path, matrix

    # def optimized_recursive(x, y, l, debug_path: List[str]):
    def optimized_recursive(x, y, l, debug_path: List[str] = []):
        if (0 <= x < W) == False or (0 <= y < H) == False:
            return 0
        
        if l == L - 1 and matrix[y][x] == FIND_WORD[L - 1]:
            # reach to the end
            # print('===>', x, y)
            return 1
        

        if l in quick_path[y][x]:
            return quick_path[y][x][l]
        
        if matrix[y][x] != FIND_WORD[l]:
            quick_path[y][x][l] = 0
            return 0
        
        # print(debug_path, x, y)
        # debug_path.append((matrix[y][x], x, y))
        
        # way4 = optimized_recursive(x - 1, y, l + 1, debug_path) + optimized_recursive(x + 1, y, l + 1, debug_path) + optimized_recursive(x, y + 1, l + 1, debug_path) + optimized_recursive(x, y - 1, l + 1, debug_path)
        # cross = optimized_recursive(x - 1, y + 1, l + 1, debug_path) + optimized_recursive(x - 1, y - 1, l + 1, debug_path) + optimized_recursive(x + 1, y + 1, l + 1, debug_path) + optimized_recursive(x + 1, y - 1, l + 1, debug_path)

        way4 = optimized_recursive(x - 1, y, l + 1) + optimized_recursive(x + 1, y, l + 1) + optimized_recursive(x, y + 1, l + 1) + optimized_recursive(x, y - 1, l + 1)
        cross = optimized_recursive(x - 1, y + 1, l + 1) + optimized_recursive(x - 1, y - 1, l + 1) + optimized_recursive(x + 1, y + 1, l + 1) + optimized_recursive(x + 1, y - 1, l + 1)

        # debug_path.pop()
    
        quick_path[y][x][l] = way4 + cross
        return quick_path[y][x][l]

    # print(x, y)
    return optimized_recursive(x, y, 0)

cnt = 0
for y in range(H):
    for x in range(W):
       cnt += find_len(x, y) 

print(cnt)

h, w, l = map(int, input().split())
grid = [list(input()) for _ in range(h)]
word = input()

directions = [(-1, 0), (1, 0), (0, -1), (0, 1), 
              (-1, -1), (-1, 1), (1, -1), (1, 1)]
dp = [[0] * w for _ in range(h)]
answer = 0
#첫번째 글자는 1로 시작
for i in range(h):
    for j in range(w):
        if grid[i][j] == word[0]:
            dp[i][j] = 1
#이전 글자의 위치를 찾아서 그 위치의 값만큼 더해준다
#이전 글자의 위치는 8방향으로 갈 수 있는 위치이며 해당 위치에 이전 글자가 있는지 확인한다
#이전 글자가 있다면 해당 위치의 값을 가져와서 현재 위치의 값을 더해준다
#이렇게 하면 해당 위치에 현재 글자가 있는 경우의 수를 구할 수 있다
for idx in range(1, len(word)):
    #중복된 글자가 있을 경우 해당 값이 원하는 값보다 더 증가함으로
    #바로 이전의 기록만 저장해준다
    next_dp = [[0] * w for _ in range(h)]
    answer=0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == word[idx]:
                value = 0
                for di, dj in directions:
                    ni, nj = i + di, j + dj
                    #갈 수 있는 곳이며 해당 위치에 글자가 바로 이전의 글자라면 값을 가져온다
                    if 0 <= ni < h and 0 <= nj < w and grid[ni][nj] == word[idx - 1]:
                        value += dp[ni][nj]
                next_dp[i][j] = value
                answer+=value
    dp = next_dp
print(answer)

def solution(prices):
    length = len(prices)
    answer = [0]*length
    for i in range(length):
        for j in range(i+1,length):
            answer[i] +=1
            if prices[i]>prices[j]: break
        #떨어지는 시점 확인 (ex) i는 0일때 index가 3인 순간에 값이 이전 값 보다 작음으로 이때 까지 answer의 값을 증가시킨다)
        
    return answer

def solution(prices):
    answer = [0] * len(prices)
    
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            answer[i] += 1
            if prices[j] < prices[i]:
                break
                
    return answer

import heapq

def solution(prices):
    pricelist = list()
    
    result = [0] * len(prices)
    
    for idx, p in enumerate(prices):
        while len(pricelist) > 0 and pricelist[0][0] < -p:
            price, pos = heapq.heappop(pricelist)
            result[pos] = idx - pos
            
        heapq.heappush(pricelist, (-p, idx))
        
    # on remain
    while len(pricelist) > 0:
        price, pos = pricelist.pop()
        result[pos] = len(prices) - pos - 1
    
    return result

def solution(prices):
    length = len(prices)
    
    answer = [0] * length
    
    stack = []
    for i in range(length):
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    
    while stack:
        j = stack.pop()
        answer[j] = length - j - 1
    
    return answer

from collections import deque

def solution(prices):
    n = len(prices)
    dq = deque()
    result = []
    
    for i in range(n - 1, -1, -1):
        cnt = 0
        while True:
            if len(dq) == 0:
                result.append(n - i - 1)
                dq.append([prices[i], i])
                break
            
            top = dq[len(dq) - 1]
            if top[0] >= prices[i]:
                dq.pop()
            else:
                result.append(top[1] - i)
                dq.append([prices[i], i])
                break
        
    return result[::-1]

def solution(prices):
    s = list()
    answer = prices.copy()
    
    for x in range(len(prices)):
        while len(s) > 0:
            if s[-1][0] > prices[x]:
                item = s.pop()
                answer[item[1]] = (x - item[1])
            else:
                break
                
                
        s.append((prices[x], x))

    x = len(prices) - 1
    for (_, i) in s:
        answer[i] = x - i
    
    return answer

def solution(progresses, speeds):
    stack  = []
    for idx,progress in enumerate(progresses):
        num = 100-progress #남은 작업 크기
        if num%speeds[idx]!= 0: #해당 작업을 끝내기 위해 필요한 시간 저장
            stack.append(num//speeds[idx]+1)
        else: 
            stack.append(num//speeds[idx])
    cnt = 1
    current = stack[0]
    answer  = []
    for num in stack[1:]:
        if current>=num: cnt+=1 #이전 직업이 끝난 시점에 지금 작업도 같이 끝났을 있으면(이전 작업에 필요한 시간이 현재 직업에 필요한 시간보다 크거나 같으면) 끝난 작업 + 1
        else:
            answer.append(cnt) #현재 작업이 끝나기 위해 더 많은 시간이 필요하면(이전 작업에 필요한 시간이 현재 작업에 필요한 시간보다 작으면) 이때까지 끝난 작업을 answer에 append
            cnt =1 #끝낸 작업 초기화
            current = num
    answer.append(cnt)
    return answer

import math

def solution(progresses,speeds):
    days = [math.ceil((100 - p) / s) for p, s in zip(progresses, speeds)]
    result = []
    max_days = days[0]
    cnt = 0
    
    for day in days:
        if day > max_days:
            result.append(cnt)
            cnt = 1
            max_days = day
        else:
            cnt += 1
            
    result.append(cnt)
    return result

def solution(progresses, speeds):
    answer = []
    days = 0
    complete = 0
    while len(progresses) > 0:
        task = progresses[0]
        speed = speeds[0]
        if(task + days * speed) >= 100:
            progresses.pop(0)
            speeds.pop(0)
            complete += 1
        else:
            if complete > 0:
                answer.append(complete)
                complete = 0
            else:
                days += 1
    answer.append(complete)
    return answer

import math

def solution(progresses, speeds):
    days_going = 0
    
    result = []
    while progresses:
        remain_days = math.ceil((100 - progresses[0]) / speeds[0]) - days_going
        
        waiting_cnt = 0
        for idx, p in enumerate(progresses[1:], 1):
            if math.ceil((100 - progresses[idx]) / speeds[idx]) - days_going <= remain_days:
                waiting_cnt += 1
            else:
                break
                
        result.append(1 + waiting_cnt)
        del progresses[:1 + waiting_cnt]
        del speeds[:1 + waiting_cnt]
        
    return result

import math

def solution(progresses, speeds):
    result = []
    before = math.ceil((100 - progresses[0]) / speeds[0])
    cnt = 1
    
    for p, s in zip(progresses[1:], speeds[1:]):
        d = math.ceil((100 - p) / s)
        
        if before >= d:
            cnt += 1
        else:
            result.append(cnt)
            before = d
            cnt = 1
            
    result.append(cnt)
    
    return result

import math

def solution(progresses, speeds):
    answer = []
    calculated = []
    for x in range(len(progresses)):
        calculated.append(days(progresses[x], speeds[x]))
    
    i = 0
    limit = len(calculated)
    answer = [1, ]
    last = calculated[0]
    for d in calculated[1:]:
        if last < d:
            answer.append(0)
            last = d
            
        answer[-1] += 1      
        
        
    return answer

def days(p, s):
    return math.ceil((100 - p) / s)

from collections import deque

def solution(n, edge):
    graph = {}
    for vertext in edge: #그래프 만들기
        start = vertext[0]
        to = vertext[1]
        graph[start] = graph.get(start, set())
        graph[start].add(to)
        graph[to] = graph.get(to, set())
        graph[to].add(start) #두 노드끼리 서로 오고 갈 수 있음을 저장
    value = {i: 50000 for i in range(1, n+1)}
    queue = deque([(1, 0)])
    value[1] = 0 #value의 key값은 노드의 번호 값은 그 노드까지 가는데 필요한 최소 비용
    while queue: #BFS
        start, cnt= queue.popleft()
        for to in graph[start]:
            if cnt + 1 < value[to]: #BFS를 하는데 이때 VISITED를 사용하는게 아니라 해당 노드까지 가는데 걸린 비용이 더 짧을 경우(최단 거리일 경우) 만 queue에 추가해주고 value에 저장해 준다(이미 존재 할 경우 cnt+1로 초기화)
                queue.append((to, cnt + 1))
                value[to] = cnt + 1
    maxVal = 0
    answer = 0
    for num in value.values(): #해당 노드까지 가는데 필요한 최소 비용이 가장 크거나 같을 경우만 +1
        if num > maxVal: 
            maxVal = num
            answer=1
        elif num == maxVal:
            answer+=1
    return answer

import heapq

def solution(n, edge):
    # 그래프 초기화
    graph = [[]for _ in range(n + 1)]
    for u, v in edge:
        graph[u].append((v,1))
        graph[v].append((u,1))
        
    # 거리 배열 초기화
    distance = [float('inf')] * (n+1)
    distance[1] = 0
    heap = [(0,1)]
    
    # 다익스트라
    while heap:
        cur_dist, cur_node = heapq.heappop(heap)
        
        if cur_dist > distance[cur_node]:
            continue
            
        for adj, weight in graph[cur_node]:
            dist = cur_dist + weight
            if dist < distance[adj]:
                distance[adj] = dist
                heapq.heappush(heap, (dist, adj))
    
    # 결과
    max_dist = max(distance[1:])
    return distance.count(max_dist)

from collections import deque

def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    
    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    distances = [-1] * (n+1)
    distances[1] = 0
    q = deque([1])
    
    while q:
        current = q.popleft()
        
        for n in graph[current]:
            if distances[n] == -1:
                distances[n] = distances[current] + 1
                q.append(n)
    count = 0
    for distance in distances:
        if distance == max(distances):
            count += 1
    
    return count

from collections import Counter

def solution(n, vertex):
    distance = [50_001] * (n + 1)
    distance[1] = 1
    
    vd = dict()
    
    for ve in vertex:
        ve = sorted(ve)
        a, b = ve
        
        if a not in vd:
            vd[a] = list()
        if b not in vd:
            vd[b] = list()
        
        vd[a].append(b)    
        vd[b].append(a)    
    
    to_visit = list()
    
    for dst in vd[1]:
        to_visit.append((1, dst))
    
    
    while to_visit:
        (src, dst) = to_visit.pop(0)
        
        if distance[dst] <= distance[src] + 1:
            continue
        
        distance[dst] = distance[src] + 1
        
        if dst not in vd:
            continue
            
        for vde in vd[dst]:               
            to_visit.append((dst, vde))   
    
    cntr = Counter(distance[1:])
    k = max(cntr.keys())
    return cntr[k]

from collections import defaultdict, deque

def solution(n, edge):
    map = defaultdict(list)
    for e in edge:
        map[e[0]].append(e[1])
        map[e[1]].append(e[0])
    
    arr = [-1 for i in range(n + 1)]
    arr[1] = 0
    
    farthest = 0
    que = deque()
    que.append(1)
    while len(que) > 0:
        i = que.popleft()
        for node in map[i]:
            if arr[node] == -1:
                arr[node] = arr[i] + 1
                que.append(node)
                farthest = max(farthest, arr[node])
    
    return arr.count(farthest)

from collections import deque
def solution(n, results):
    winGraph = {} #이긴 경우를 저장해주는 그래프
    looseGraph ={}#진 경우를 저장해주는 그래프
    def bfs(start,graph): #BFS를 돌려 몇개의 노드를 방문하였는지 return시켜 준다
        queue = deque([start])
        visited = set()
        while queue:
            current = queue.popleft()
            if current not in visited:
                visited.add(current)
                for neighbor in graph.get(current,[]):
                    queue.append(neighbor)
        return len(visited)-1
                
    for vertext in results:
        node = vertext[0] #이긴 사람의 노드
        neighbor = vertext[1] #진 사람의 노드
        winGraph[node] = winGraph.get(node, set())
        winGraph[node].add(neighbor)
        looseGraph[neighbor] = looseGraph.get(neighbor, set())
        looseGraph[neighbor].add(node)
    answer = 0
    for node in range(1,n+1):
        #승패를 따로 저장해둠으로써 만약 방문 가능한 모든 노드를 방문하였을 때 모든 노드를 방문하였으면 현재 노드의 등수는 정해져있다고 볼 수 있다
        #예를 들어 2번 선수의 경우 bfs를 돌렸을 때 winGraph의 경우 1,3,4를 방문하였을 것이고 looseGraph의 경우 5번 경우를 방문하였기에 모든 노드를 방문하였다고 볼 수 있고
        #5번선수의 경우 winGraph에서는 어떤 노드도 방문할 수 없지만 looseGraph의 경우 2번 노드를 방문 후 1,3,4노드를 방문 즉 2,1,3,4번 노드를 방문하여 모든 노드를 방문하였다고 볼 수 있다
        wins = bfs(node,winGraph)
        looses = bfs(node,looseGraph)
        if n-1 == wins+looses:
            answer+=1
    return answer

def solution(n, results):
    win_graph = [[False] * (n + 1) for _ in range(n + 1)]
    
    for winner, loser in results:
        win_graph[winner][loser] = True
    
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if win_graph[i][k] and win_graph[k][j]:
                    win_graph[i][j] = True
    
    answer = 0
    
    for i in range(1, n + 1):
        count = 0
        for j in range(1, n + 1):
            if win_graph[i][j] or win_graph[j][i]:
                count += 1
        if count == n - 1:
            answer += 1
    
    return answer

def solution(n, results):
    arr = [[0 for j in range(n)] for i in range(n)]
    
    for r in results:
        arr[r[0] - 1][r[1] - 1] = 1
        arr[r[1] - 1][r[0] - 1] = -1
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if arr[i][j] == 0 and arr[i][k] == 1 and arr[k][j] == 1:
                    arr[i][j] = 1
                if arr[i][j] == 0 and arr[i][k] == -1 and arr[k][j] == -1:
                    arr[i][j] = -1
    
    cnt = 0
    for r in arr:
        if r.count(0) == 1:
            cnt += 1
            
    return cnt

import sys
sys.setrecursionlimit(10**6)
class Tree:
    def __init__(self, info):
        self.place = info[1:] #노드의 위치
        self.idx = info[0] #노드의 번호
        self.right = None
        self.left = None

def makeTree(subTree):
    if not subTree:
        return None
    parent = Tree(subTree[0]) #y값은 sort가 되어있음으로 level이 높은 순서임으로 0번째가 가장 level이 높다
    leftSub = []
    rightSub = []
    for node in subTree[1:]: #모든 자식 노드를 가져와 x값이 큰 것을 오른쪽 서브트리로 x값이 작은 것을 왼쪽 서브트리로 ㅁppend
        if node[1] < parent.place[0]:
            leftSub.append(node)
        else:
            rightSub.append(node)
    #분류한 자식 노드들을 가지고 다시 subTree를 만든다
    parent.left = makeTree(leftSub)
    parent.right = makeTree(rightSub)
    return parent #만든 subTree를 return

def solution(nodeinfo):
    nodeinfo = sorted([[idx + 1, *place] for idx, place in enumerate(nodeinfo)], key=lambda x: -x[2])
    #y값을 기준으로 sort를 하여 Tree의 level의 순서대로 나오도록 정렬해주고 idx+1를 저장하여 해당 노드의 번호를 저장해준다
    tree = makeTree(nodeinfo)
    
    preResult = []
    postResult = []
    
    def preOrder(node): #전위 순회
        if node:
            preResult.append(node.idx)
            preOrder(node.left)
            preOrder(node.right)
    
    def postOrder(node): #후위 순회
        if node:
            postOrder(node.left)
            postOrder(node.right)
            postResult.append(node.idx)
    
    preOrder(tree)
    postOrder(tree)
    
    return [preResult, postResult]

import sys
sys.setrecursionlimit(10000)

to_visit = list()
nodeinfo_cur = 1

class Tree:
    val = None
    
    left = None
    right = None
    
    cord = None
    x_start = None
    x_end = None
    
    def __init__(self, val, cord, x_start, x_end):
        self.val = val
        
        self.cord = cord
        self.x_start = x_start
        self.x_end = x_end
    
    def __str__(self):
        return "(" + str(self.left) + " " + str(self.val) + " " + str(self.right) + ")"
    
def divide(parent, nodeinfo):
    global to_visit
    global nodeinfo_cur
    
    
    if nodeinfo_cur >= len(nodeinfo):
        return
    

    x_start = parent.x_start
    x_end = parent.x_end
    x_mid = parent.cord[0]
    
    
    # print(nodeinfo[nodeinfo_cur][1][0], x_start, x_end)
    
    # 내 child의 tree가 아님. sibling의 어느 부분일듯
    if nodeinfo[nodeinfo_cur][1][0] < x_start or nodeinfo[nodeinfo_cur][1][0] > x_end:
        return
    
    # 일단 내 범위임
    if nodeinfo[nodeinfo_cur][1][0] < x_mid:
        parent.left = Tree(nodeinfo[nodeinfo_cur][0], nodeinfo[nodeinfo_cur][1], x_start, x_mid)
        nodeinfo_cur += 1
    
    # left만 있는 노드일 수도 있으므로, right 조건인지 체크 해야함
    if nodeinfo_cur < len(nodeinfo) and x_mid < nodeinfo[nodeinfo_cur][1][0] <= x_end:
        parent.right = Tree(nodeinfo[nodeinfo_cur][0], nodeinfo[nodeinfo_cur][1], x_mid, x_end)
        nodeinfo_cur += 1
    
    if parent.left is not None:
        to_visit.append(parent.left)
    if parent.right is not None:
        to_visit.append(parent.right)

def post_trav(node, result):
    if node.left is not None:
        post_trav(node.left, result)
    if node.right is not None:
        post_trav(node.right, result)
        
    result.append(node.val)
    
    
def pre_trav(node, result):
    result.append(node.val)
    
    if node.left is not None:
        pre_trav(node.left, result)
    if node.right is not None:
        pre_trav(node.right, result)
    
    
def solution(nodeinfo):
    nodeinfo = sorted(enumerate(nodeinfo, 1), key = lambda c: (-c[1][1], c[1][0]))
    max_x = 0
    for _, (x, y) in nodeinfo:
        if x > max_x:
            max_x = x
    
    global to_visit
    global nodeinfo_cur
    
    parent = Tree(nodeinfo[0][0], nodeinfo[0][1], 0, max_x)
    to_visit.append(parent)
    
    while to_visit:
        p = to_visit.pop(0)
        divide(p, nodeinfo)
    
        
    # print(parent)
    
    post_result = []
    post_trav(parent, post_result)
    
    pre_result = []
    pre_trav(parent, pre_result)
    
    # 전위탐색 1개, 후위탐색 1개
    return [pre_result, post_result]

def solution(n):
    fibo = [0,1]
    for i in range(2,n+1):
        fibo.append(fibo[i-1]+fibo[i-2])
    # 재귀로 계산하면 5를 계산하기 위해 4와 3를 호출하고 4를 계산하기 위해 다시 3와 2를 호출해야 함으로 비효율적
    return fibo[n]%1234567

def solution(n):
    dp = [0] * (n + 2)
    dp[1] = 1
    
    for idx in range(2, n + 1):
        dp[idx] = dp[idx - 2] + dp[idx - 1]
    
    return dp[n] % 1234567

import sys
sys.setrecursionlimit(200000)


fibo_cache = dict()

def fibo(n):
    global fibo_cache

    if n <= 1:
        fibo_cache[n] = n
        return n
        
    f_idx_1 = n - 1
    f_idx_2 = n - 2
    

    if f_idx_2 not in fibo_cache:
        f_result_2 = fibo(f_idx_2)
        fibo_cache[f_idx_2] = f_result_2
        
    if f_idx_1 not in fibo_cache:
        f_result_1 = fibo(f_idx_1)
        fibo_cache[f_idx_1] = f_result_1
        
    f_result_1 = fibo_cache[f_idx_1]
    f_result_2 = fibo_cache[f_idx_2]
    
    return f_result_2 + f_result_1

def solution(n):
    return fibo(n) % 1234567

def solution(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n] % 1234567

def solution(n):
    a = 0
    b = 1
    
    for i in range(1, n):
        tmp = a
        a = b
        b = (tmp + b) % 1234567
    
    return b

def solution(N, number):
    dict = {}
    def recursive(value,cnt):
        if cnt>8 or (cnt>0 and value==0): return
    #최솟값이 8보다 크거나 현재 계산된 값이 0이라면 의미가 없으므로 return 시킨다
        dict[value] = min(dict.get(value,cnt),cnt)
        #현재 값이 이전 계산에서 있었는지 확인하고 더 작으면 저장
        num = N
        for i in range(1,9):
            recursive(value+num,cnt+i) #값 +
            recursive(value-num,cnt+i) #값 -
            recursive(value*num,cnt+i) #값 *
            recursive(value/num,cnt+i) #값 /
            num = num*10+N #N이 9 일따 9,99,999을 사칙연산 이때 cnt의 값은 1,2,3 만큼 증가
    recursive(0,0)
    return dict.get(number,-1)

def solution(N, number):
    arr = []
    
    for count in range(1, 9):
        case = set()
        case.add(int(str(N)*count))
        for i in range(count - 1):
            for op1 in arr[i]:
                for op2 in arr[-i - 1]:
                    case.add(op1 + op2)
                    case.add(op1 * op2)
                    case.add(op1 - op2)
                    if op2 != 0:
                        case.add(op1 // op2)
        
        if number in case:
            return count
        arr.append(case)
    
    return -1

def solution(triangle):
    grid = [[0] * (i + 1) for i in range(len(triangle))]
    grid[0][0] = triangle[0][0]
    for idx in range(1, len(triangle)):
        for j in range(len(triangle[idx])): #피라미드의 위에서 부터 오른쪽으로 하나씩 그려 나간다
            if j == 0: #피라미드 층의 첫번째는 그림으로 보았을 때 상위 층의 왼쪽 값은 받을 수 없음으로 오른쪽 값만 더해 저장
                grid[idx][j] = grid[idx - 1][j] + triangle[idx][j]
            elif j == idx: #피라미드 층의 마지막은 그림으로 보았을 때 상위 층의 오른쪽 값은 받을 수 없음으로 왼쪽 값만 더해 저장
                grid[idx][j] = grid[idx - 1][j - 1] + triangle[idx][j]
            else: #피라미드 층의 중간에 있는 것들은 상위 층의 오른쪽 값이나 왼쪽값을 받을 수 있음으로 그 중 큰 값을 더해 저장
                grid[idx][j] = max(grid[idx - 1][j - 1], grid[idx - 1][j]) + triangle[idx][j]
    return max(grid[-1]) #피라미드 마지막 층 중 가장 값이 큰 것을 return

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                triangle[i][j] += triangle[i - 1][j]
            elif j == len(triangle[i]) - 1:
                triangle[i][j] += triangle[i - 1][j - 1]
            else:
                triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j])
    
    return max(triangle[-1])

def search(triangle, line_pos):
    max_tree = [[triangle[0][0]]]
    
    for line_idx, line in enumerate(triangle[1:], 1):
        this_line = []
        
        for col_idx, col in enumerate(line):
            maxium_parent = []
            # left
            if col_idx > 0:
                maxium_parent.append(max_tree[line_idx - 1][col_idx - 1])
                
            # right
            if col_idx < len(line) - 1:
                maxium_parent.append(max_tree[line_idx - 1][col_idx])
                
            this_line.append(max(maxium_parent) + col)
        
        max_tree.append(this_line)
    
    return max(max_tree[-1])

def solution(triangle):
    return search(triangle, 0)

def solution(triangle):
    if len(triangle) > 1:
        for i in range(len(triangle) - 2, -1, -1):
            for idx, num in enumerate(triangle[i]):
                triangle[i][idx] += max(triangle[i + 1][idx], triangle[i + 1][idx + 1]);
    
    return triangle[0][0]

def solution(m, n, puddles):
    map = [[0 for j in range(m)] for i in range(n)]
    
    for i in range(n):
        map[i][0] = 1
    
    for j in range(m):
        map[0][j] = 1
    
    for p in puddles:
        map[p[1] - 1][p[0] - 1] = -1
        
        if p[1] == 1:
             for i in range(p[0], m):
                    map[0][i] = -1
        
        if p[0] == 1:
             for i in range(p[1], n):
                    map[i][0] = -1
        
    print(map)
    for i in range(1, n):
        for j in range(1, m):
            if map[i][j] == -1:
                continue
            
            if map[i - 1][j] != -1:
                map[i][j] = (map[i][j] + map[i - 1][j]) % 1000000007
            
            if map[i][j - 1] != -1:
                map[i][j] = (map[i][j] + map[i][j - 1]) % 1000000007
    print(map)
    return map[n - 1][m - 1] % 1000000007

def solution(m, n, puddles):
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    dp[1][1] = 1
    
    for i, j in puddles:
        dp[j][i] = -1
        
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if dp[i][j] == -1:
                dp[i][j] = 0
                continue
                
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
            
    return dp[n][m] % 1000000007

def solution(m, n, puddles):
    grid = [[0] * m for _ in range(n)]  #해당 위치로 갈 수 있는 방법의 수를 저장
    for i in range(1,m): #처음에서 오른쪽으로만 움직였을 때(그림에서 가장 윗 층만 움직였을 때) 최단 거리로 갈 수 있는 방법이 하나밖에 없음으로 모두 1을 저장해주고 만약 puddles가 있다면 puddles 다음은 최단거리로 갈 수 있는 방법이 없음으로 0을 그대로 놔두어 준다
        if [i+1,1] in puddles:
            break
        grid[0][i] = 1
    for i in range(1,n): #처음에서 밑으로만 움직였을 때(그림에서 가장 왼쪽 만 움직였을 때) ~이하 위와 동문
        if [1,i+1] in puddles:
            break
        grid[i][0] = 1
    for i in range(1,n):
        for j in range(1,m):
            if [j+1,i+1] in puddles: #puddles에 도착하였을때 해당 경우는 무시
                continue
            grid[i][j] = grid[i-1][j]+grid[i][j-1] #현재 위치로 올 수 있는 방법이 현재 위치의 위와 왼쪽에 도착하였을 경우 가 있는데 해당 위치(현재 위치의 위 아래)로 올 수 있는 경우의 수를 더해 현재 위치로 도착 할 수 있는 경우의 수를 정한다
    return grid[-1][-1]%1000000007

def solution(x, y, puddles):
    heatmap = [[0] * (x + 1) for _ in range(y + 1)]
    
#     # fill bottom
#     for x_pos in range(x):
#         heatmap[y - 1][x_pos] = 1
    
#     # fill right
#     for y_pos in range(y):
#         heatmap[y_pos][x - 1] = 1
    heatmap[y - 1][x - 1] = 1
    
    blocked = ()
    if len(puddles[0]) > 0:
        blocked = tuple(map(lambda v: (v[0] - 1, v[1] - 1), puddles))
    
    for line in range(y - 1, -1, -1):
        for x_pos in range(x - 1, -1, -1):
            if (x_pos, line) in blocked:
                heatmap[line][x_pos] = 0
                continue
            elif (x_pos, line) == (x - 1, y - 1):
                continue
            
            heatmap[line][x_pos] = heatmap[line + 1][x_pos] + heatmap[line][x_pos + 1]
            
    return heatmap[0][0] % 1_000_000_007

def solution(money):
    n = len(money)
    dp1 = [0 for i in range(n)]
    dp1[0] = money[0]
    dp1[1] = max(money[0], money[1])

    for i in range(2, n - 1):
        dp1[i] = max(dp1[i - 1], money[i] + dp1[i - 2])

    dp2 = [0 for i in range(n)]
    dp2[0] = 0
    dp2[1] = money[1]

    for i in range(2, n):
        dp2[i] = max(dp2[i - 1], money[i]+dp2[i - 2])

    return max(max(dp1), max(dp2))

def solution(money):
    n = len(money)
    
    if n == 3:
        return max(money)
    
    dp1 = [0] * n
    dp1[0] = money[0]
    dp1[1] = max(money[0], money[1])
    
    for i in range(2, n-1):
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])
    
    dp2 = [0] * n
    dp2[0] = 0
    dp2[1] = money[1]
    
    for i in range(2, n):
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i])
    
    return max(dp1[n-2], dp2[n-1])

def solution(money):
    length = len(money)
    #처음에서 시작하였을 때와 두번째에서 시작하였을 때를 나누어야지 후에 마지막을 선택할지 안할지를 결정할 수 있다
    firStartGrid = [0 for _ in range(length)] #처음 위치에서 시작하였을 때
    firStartGrid[0] = money[0]
    firStartGrid[1] = money[0] #처음 위치가 시작 위치이기 때문에 2번째 값은 첫번째 값으로 대체
    for i in range(2,length-1): #처음 위치가 시작 위치이기 때문에 마지막은 고를 수 없다
        firStartGrid[i] = max(firStartGrid[i-2]+money[i],firStartGrid[i-1]) #현재 위치의 이전 이전 위치를 기준으로 보았을 때 이 위치(현재 위치의 이전 이전 위치)를 골라서 한칸을 띄운 위치의 집을 터는것이 이득인지 아니면 고르지 않음으로서 다음 위치의 집을 터는 것이 이득인지 확인 후 저장(집 2개를 터는 것 보다 한 개를 터는 것이 더 이득이여야지 현재 집을 털지 않고 넘어가는 것이 이득이다)
    secStartGrid = [0 for _ in range(length)] #두 번째 위치에서 시작하였을 때
    secStartGrid[1] = money[1] #두 번째 위치에서 시작하였기 때문에 2번째 값을 저장하고 1번째 값은 그대로 두어도 괜찮다
    for i in range(2,length): #두 번째 위치에서 시작하기 때문에 마지막을 고르거나 안고르거나 선택 할 수 이다
        secStartGrid[i] = max(secStartGrid[i-2]+money[i],secStartGrid[i-1]) #이하동문
    return max([*firStartGrid,*secStartGrid])

def solution(money):
    money_agg = [0] * len(money)
    money_agg[0] = money[0]
    money_agg[1] = money[1]
    money_agg[2] = money[2]
    
    money_agg_1 = money_agg[:]
    
    # len <= 3일때는 모든곳이 근접함. 그러므로, 하나만 뽑을 수 있음
    if len(money) <= 3:
        return max(money)
    
    # 이제부터는 최소 4개임.    
    # 제로 부터 시작 (맨 마지막거는 못감)
    money_agg[2] = money_agg[0] + money[2]
    # 원래는 range(2, ···) 였는데, 이러면 idx -3 때문에 문제가 생겨서... 그렇다고 if문을 매번 하기에는 성능 문제
    for idx in range(3, len(money)  - 1):
        money_agg[idx] = max(money_agg[idx - 2], money_agg[idx - 3]) + money[idx]
    
    # 1부터 시작 (맨 마지막거 갈 수 있음)
    # 마찬가지로, idx == 3 일때 idx-3 때문에 0를 참조할 수 있음. 1부터 시작해야 하는게 조건이므로, 0이 안되게 특수조건화
    money_agg_1[3] = money_agg_1[1] + money[3]
    for idx in range(4, len(money)):
        money_agg_1[idx] = max(money_agg_1[idx - 2], money_agg_1[idx - 3]) + money[idx]
    
    return max(max(money_agg[-3:]), max(money_agg_1[-3:]))

def solution(participant, completion):
    participants = {}
    for name in participant:
        participants[name] = participants.get(name,0)+1 #참가자이름:참가자이름을 가진 참여자의 수
    for completionName in completion:
        participants[completionName]-=1 #completion에 있는 참가자를 제외
    for name in participants:
        if participants[name]>0: return name #남은 참가자를 return

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

import collections

def solution(participant, completion):
    runner = collections.defaultdict(int)
    
    for p in participant:
        runner[p] += 1
    
    for c in completion:
        if runner[c] == 1:
            runner.pop(c, None)
            continue
        runner[c] -= 1
    
    return list(runner.keys())[0]

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
        
    answer = participant[-1]
    return answer

def solution(phone_book):
    phoneNumDic = {}
    for phoneNum in phone_book:
        text = ""
        for i in range(len(phoneNum)):
            text += phoneNum[i]
            phoneNumDic[text] = phoneNumDic.get(text,0)+1 #전화번호의 모든 접두어를 dictionary에 기억한다
    for phoneNum in phone_book:
        if phoneNumDic.get(phoneNum, 0) > 1: #해당 전화번호가 자신을 제외하고 다른 전화번호의 접두어가 가능할 경우 해당 전화번호 key의 value값이 2이상임으로 이때 false를 return시켜준다
            return False    
    return True

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return True

def solution(phone_book):
    phone_book.sort()
    for i in range(1, len(phone_book)-1, 1):
        if(phone_book[i].startswith(phone_book[i-1]) or phone_book[i+1].startswith(phone_book[i])):
            return False
    return True

def solution(phone_book):
    header = set()
    
    for p in phone_book:
        for i in range(1, len(p)):
            header.add(p[:i])
    
    for p in phone_book:
        if p in header:
            return False
    return True

def solution(phone_book):
    phone_book.sort()

    for p in range(len(phone_book) - 1):
        if phone_book[p] == phone_book[p+1][0:(len(phone_book[p]))]:
            return False
        
    
    answer = True
    return answer

def solution(clothes):
    dict = {}
    answer = 1
    for cloth in clothes:
        category = cloth[1]
        if category in dict:
            dict[category].append(cloth[0])
        else:
            dict[category] = [cloth[0]]

    for category in dict:
        answer *= (len(dict[category]) + 1)

    return answer - 1

def solution(clothes):
    answer = 0
    clothesDic = {}
    for cloth in clothes:
        clothesDic[cloth[1]] = clothesDic.get(cloth[1],0)+1 #종류: 해당 종류의 의상 개수 (같은 이름을 가진 의상이 존재하지 않음으로 무조건 개수가 1씩 늘어난다)
    answer = 1
    for cloth in clothesDic:
        answer*=clothesDic[cloth]+1 #경우의 수=(해당 종류의 의상 중 하나를 고를 경우의 수 + 해당 옷을 입지 않을 경우의수)*반복
    return answer-1 #옷을 하나도 입지 않을 경우의 수 제거

import collections

def solution(clothes):
    clothes_dict = collections.defaultdict(int)
    
    for c in clothes:
        clothes_dict[c[1]] += 1
    
    cnt = 1
    for c in clothes_dict:
        cnt *= clothes_dict[c] + 1
    
    return cnt - 1

def solution(clothes):
    w = dict()
    for (name, t) in clothes:
        if t not in w:
            w[t] = 1
        
        w[t] += 1
        
    s = 0
    w = list(w.values())
    
    answer = 1
    for x in w:
        answer *= x
    
    return answer - 1

def solution(record):
    answer = []
    dict = {}
    
    for r in record:
        r = r.split(" ")

        if r[0] == "Enter" or r[0] == "Change":
            dict[r[1]] = r[2]
    
    for r in record:
        r = r.split(" ")
        
        if r[0] == "Enter":
            answer.append(f"{dict[r[1]]}님이 들어왔습니다.")
        elif r[0] == "Leave":
            answer.append(f"{dict[r[1]]}님이 나갔습니다.")
    
    return answer

def solution(record):
    userDic = {}
    idRecord=[]
    for getRecord in record:
        getRecord = getRecord.split(" ")
        if len(getRecord)==3: userDic[getRecord[1]] = getRecord[2] #행동, 유저아이디, 닉네임 순으로 들어오는데 닉네임이 들어올 시 유저의 닉네임이 변경됨으로 이를 key를 유저아이디로 value를 닉네임으로 dictionary에 저장한다
        if getRecord[0]!="Change": idRecord.append((getRecord[1],getRecord[0])) #닉네임 변경은 result에 포함되지 않음으로 이를 제외한 행동들과 유저의 아이디를 기록해둔다
    answer = []
    for userId,act in idRecord:
        text =userDic[userId]+"님이 " #유저의 아이디를 닉네임으로 변경
        if act == "Enter":
            text+="들어왔습니다."
        else: text+="나갔습니다."
        answer.append(text)
    return answer

def solution(record):
    user = dict()
    
    for r in record:
        tmp = r.split(" ")
        if tmp[0] in ['Enter', 'Change']:
            user[tmp[1]] = tmp[2]
    
    result = []
    for r in record:
        tmp = r.split(" ")
        
        if tmp[0] == 'Enter':
            result.append(f"{user[tmp[1]]}님이 들어왔습니다.")
            continue
        if tmp[0] == 'Leave':
            result.append(f"{user[tmp[1]]}님이 나갔습니다.")
            continue
    
    return result

def solution(record):
    id_to_nick = {}
    
    for r in record:
        r = r.split(' ')
        if r[0] in ('Enter', 'Change'):
            id_to_nick[r[1]] = r[2]
    
    template = {
        'Enter': '{user}님이 들어왔습니다.',
        'Leave': '{user}님이 나갔습니다.',
        'Change': None
    }
    
    result = []
    for r in record:
        r = r.split(' ')
        if r[0] in ('Enter', 'Leave'):
            result.append(template[r[0]].replace('{user}', id_to_nick[r[1]]))
            
    return result

def solution(genres, plays):
    answer = []
    count_dict = {}
    song_dict = {}
    
    for i in range(len(genres)):
        if genres[i] not in count_dict:
            count_dict[genres[i]] = 0
        count_dict[genres[i]] += plays[i]
        
        if genres[i] not in song_dict:
            song_dict[genres[i]] = []
        song_dict[genres[i]].append((plays[i], i))

    sorted_genres = sorted(count_dict.keys(), key=lambda x: count_dict[x], reverse=True)
    
    for genre in sorted_genres:
        songs = sorted(song_dict[genre], key=lambda x: (-x[0], x[1]))
        answer.extend([song[1] for song in songs[:2]])
    
    return answer

def solution(genres, plays):
    genreDic = {}
    genreTotalDic = {}
    for idx, (genre, play) in enumerate(zip(genres, plays)):
        genreDic[genre] = genreDic.get(genre,[])
        genreDic[genre].append((play,idx)) #장르별로 고유번호와 재생횟수를 기록
        genreTotalDic[genre] = genreTotalDic.get(genre,0)+play #장르별 총 재생횟수를 기록
    genreTotalArr = genreTotalDic.items()#array로 변경
    answer = []
    for genre, _ in sorted(genreTotalArr, key=lambda x: -x[1]): #많이 재생된 순으로 장르를 정렬
        cnt = 0 #최대 2개씩만 기록되도록 제한
        for _,idx in sorted(genreDic[genre],key=lambda x: (-x[0], x[1])): #장르별 많이 재생된 순으로 같으면 고유번호가 낮은 순으로 정렬
            cnt+=1
            answer.append(idx)
            if cnt >=2: break
    return answer

from collections import defaultdict

def solution(genres, plays):
    genre_song_dict = defaultdict(list)
    genre_count_dict = defaultdict(int)
    
    for i, (genre, play) in enumerate(zip(genres, plays)):
        genre_song_dict[genre].append((i, play))
        genre_count_dict[genre] += play
            
    answer = []
    for genre in sorted(genre_count_dict, key=lambda genre: genre_count_dict[genre], reverse=True):
        for num in sorted(genre_song_dict[genre], key=lambda zipped_song: zipped_song[1], reverse=True)[:2]:
            answer.append(num[0])
            
    return answer

def solution(genres, plays):
    g = dict()
    p = dict()
    
    for i in range(len(genres)):
        k = genres[i]
        if genres[i] not in g:
            g[k] = 0
            p[k] = list()
        
        g[k] += plays[i]
        p[k].append((i, plays[i]))
    
    g = list(g.items())
    g.sort(key=sort_key, reverse=True)
    
    answer = []
    for x in g:
        for i in take2(p[x[0]]):
            answer.append(i[0])
    
    return answer

def sort_key(g):
    return g[1]

def take2(g):
    g.sort(key=sort_key, reverse=True)
    
    return g[:2]

def map_first(i):
    return i[0]

def solution(n, times):
    left= 1
    right = max(times)*n #걸리는 시간을 기준으로 binary search
    answer = 0
    while left <= right:
        checkN = 0
        middle = (left+right)//2
        for time in times: 
            checkN+=middle//time #선택한 시간(middle)일때 해당 심사관은 몇명을 상대할 수 있는가
            if checkN>=n: break #n이 넘어가버리면 시간을 더 짧게 할 수 있으므로 이후의 for문은 필요하지 않음
        if checkN>=n: #현재 선택한 시간일때 심사관이 더 많은 사람들을 심사할 수 있음
            answer = middle
            right = middle-1
        else: #현재 선택한 시간일때 심사관이 원하는 명 수(n)만큼 심사 할 수 없다
            left = middle+1
    return answer

def solution(n, times):
    times.sort()
    
    answer = 0  
    left, right = 1, times[-1] * n
    
    while left <= right:
        target_time = (left + right) // 2
        
        total_processed = 0
        for time in times:
            total_processed += (target_time // time)
            
            if total_processed >= n:
                break
        
        if total_processed < n:
            left = target_time + 1
        elif total_processed >= n:
            right = target_time -1
            
    return left

import heapq

def solution(n, times):
    heap = []
    
    for idx, time in enumerate(times):
        heapq.heappush(heap, (time, time, idx))
    
    for _ in range(n - 1):
        earliest, t, idx = heapq.heappop(heap)
        heapq.heappush(heap, (t + earliest, t, idx))
    
    return heapq.heappop(heap)[0]

from decimal import *
import math

def solution(n, times):
    process_per_min = sum(map(lambda t: 1 / Decimal(t), times))
    
    return math.ceil(n / process_per_min)

def solution(n, times):
    answer = 0
    left = 1
    right = max(times) * n
    
    while left <= right:
        mid = (left+ right) // 2
        cnt = 0
        for time in times:
            cnt += mid // time
            if cnt >= n:
                break
        if cnt >= n:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    return answer

def solution(n, times):
    if n == 1:
        return min(times)
    if len(times) == 1:
        return times[0] * n
    
    s = 0
    e = max(times) * n
    max_time = e
    
    while s <= e:
        m = (s + e) // 2
        cnt = sum([m // t for t in times])
        
        if cnt >= n and max_time > m:
            max_time = m
        
        if cnt < n:
            s = m + 1
        else:
            e = m - 1
    
    return max_time

import itertools

def solution(info, query):
    infoDic = {"": []}
    def inputInfoDic(array, score):
        for i in range(5):
            for combination in itertools.combinations(array, i): 
                text = ''.join(combination)
                if text in infoDic:
                    infoDic[text].append(score)
                else:
                    infoDic[text] = [score]
    for getInfo in info:
        getInfo = getInfo.rsplit(" ", 1) #지원자 정보(언어,직군,경력,소울푸드)
        score = int(getInfo[1]) #점수
        inputInfoDic(getInfo[0].split(" "), score) #지원자 정보를 가능한 모든 조합으로 뽑고 이를 join시켜 하나의 str로 만든 후 dictionary에 넣는다. 이렇게 하면 query에 빈 정보("-")가 들어와도 다른 정보들을 비교하여 찾을 수 있음
    for key in infoDic:
        infoDic[key].sort()
    
    def binarySearch(arr, num):
        start, end = 0, len(arr)
        while start < end:
            mid = (start + end) // 2
            if arr[mid] >= num:
                end = mid
            else:
                start = mid + 1
        return start
    
    answer = []
    for getQuery in query:
        getQuery = getQuery.rsplit(" ", 1) #지원자 query(언어,직군,경력,소울푸드)
        score = int(getQuery[1]) #지원자 score
        key = getQuery[0].replace("and", "").replace(" ", "").replace("-", "")
        #"-"을 제외한 query 정보들을 join
        matched = infoDic.get(key,[]) #해당 query에 맞는 정보를 가진 지원자들의 score 배열을 가져오는데 없을시 빈 배열을 가져옴
        startPoint = binarySearch(matched, score) #지원자들의 score 배열 중 원하는 점수 이상의 시작점을 찾음
        answer.append(len(matched) - startPoint)
    return answer

def map_convert(col):
    s = col.split(' ')
    return (s[0], s[1], s[2], s[3], -1 if s[4] == '-' else int(s[4]))
        
def find_range_int(rows, lower, col_idx):
    start, end = 0, len(rows)
    
    while start < end:
        mid = (start + end) // 2
        val = rows[mid][col_idx]
        
        if val < lower:
            start = mid + 1
        elif val >= lower:
            end = mid
    
    return start

def filter_only_match(rows, col_idx, match):
    if match == '-':
        return (0, len(rows))
    
    
    start, end = 0, len(rows)
    while start < end:
        mid = (start + end) // 2
        val = rows[mid][col_idx]
        
        if val < match:
            start = mid + 1
        elif val >= match:
            end = mid
    
    pos_start = start

    end = len(rows)
    while end > start:
        mid = (start + end) // 2
        val = rows[mid][col_idx]
        
        if val <= match:
            start = mid + 1
        elif val > match:
            end = mid
    
    pos_end = end
    
    return (pos_start, pos_end)

def solution(info, query):
    rows = sorted(map(map_convert, info), key = lambda v: v[4])

    result = []    
    for q in query:
        lang, _, position, _, exp, _, food, score = q.split(' ')
        cur_rows = rows[find_range_int(rows, int(score), 4):]

        
        q = (lang, position, exp, food)
        for col_idx in range(4):
            cur_rows = sorted(cur_rows, key = lambda v: v[col_idx])

            start, end = filter_only_match(cur_rows, col_idx, q[col_idx])
            cur_rows = cur_rows[start:end]

        result.append(len(cur_rows))

    return result

from itertools import combinations

def binary_search(scores, target):
    left, right = 0, len(scores)
    while left < right:
        mid = (left + right) // 2
        if scores[mid] >= target:
            right = mid
        else:
            left = mid + 1
    return left

def solution(info, query):
    info_dict = {}

    for i in info:
        i = i.split()
        conditions = i[:-1]
        score = int(i[-1])
        for n in range(5):
            for comb in combinations([0, 1, 2, 3], n):
                temp = conditions.copy()
                for c in comb:
                    temp[c] = '-'
                key = ''.join(temp)
                if key in info_dict:
                    info_dict[key].append(score)
                else:
                    info_dict[key] = [score]
    
    for key in info_dict:
        info_dict[key].sort()
    
    answer = []

    for q in query:
        q = q.replace("and ", "")
        q = q.split()
        key = ''.join(q[:-1])
        score = int(q[-1])
        
        if key in info_dict:
            scores = info_dict[key]
            idx = binary_search(scores, score)
            answer.append(len(scores) - idx)
        else:
            answer.append(0)
    
    return answer

from itertools import combinations
from collections import defaultdict
from bisect import bisect_left, bisect_right

def solution(info, query):
    table = sorted([data.split(" ") for data in info])
    score = [int(row.pop()) for row in table]
    combi = defaultdict(list)
    result = []
    
    for idx, row in enumerate(table):
        for i in range(5):
            for c in combinations(row, i):
                combi["".join(c)].append(score[idx])
    
    for i in combi.keys():
        combi[i].sort()
    
    for q in query:
        q = q.split(" and ")
        tmp = q.pop().split(" ")
        s = int(tmp[-1])
        q.append(tmp[0])
        q = ["" if i == "-" else i for i in q]
        q = "".join(q)
        
        idx = bisect_left(combi[q], s)
        result.append(len(combi[q]) - idx)
    
    return result

def solution(distance, rocks, remove_cnt_target):
    rocks = sorted(rocks)
    rocks.append(distance)
    
    start, end = 0, distance
    
    answer = 0
    
    while start <= end:
        target_distance = (start + end) // 2
        
        last_position = 0
        remove_cnt = 0
        for r in rocks:
            if r - last_position < target_distance:
                remove_cnt += 1
            else:
                last_position = r
                
            if remove_cnt_target < remove_cnt:
                break
        
        if remove_cnt_target < remove_cnt:
            end = target_distance - 1
        else:
            answer = target_distance 
            start = target_distance + 1
        # # 5개를 제거할 생각이었는데, 실제로는 4개를 제거함
        # if remove_cnt_target >= remove_cnt:
        #     # 일단 최대값을 저장함.
        #     answer = target_distance 
        #     # 최소값을 높일 필요가 있음. 
        #     start = target_distance + 1
        # else:
        #     end = target_distance - 1
            
    return answer

def solution(distance, rocks, n):
    rocks = sorted(rocks)
    rocks.append(distance) #처음 바위는 for문에서 0부터 시작하면 되니까 따로 append안시키고 마지막 바위의 위치만 append
    result = 0
    start,end = 0,distance 
    while start<=end:
        mid = (start+end)//2 #이 크기 만큼은 돌 사이 거리가 있어야 한다는 최소 거리
        before = 0
        count = 0
        for rock in rocks:
            if rock-before<mid: count+=1 #사이 거리가 부족하다면 해당 바위 제거 후 부순 바위+=1
            else: before = rock #사이 거리가 충분하다면 다음 바위 비교
            if count >n: break #부순 바위의 수가 제거할 바위의 수(n)보다 많아지만 이후 for문이 필요 없음
        if count>n: #부순 바위의 수가 제거할 바위의 수(n)보다 많을 때 최소 사이 거리를 줄임
            end= mid-1 
        else: #부순 바위의 수가 제거할 바위의 수(n)보다 적을 때 최소 사이 거리를 늘임
            result = mid
            start = mid+1
    return result

def solution(distance, rocks, n):
    answer = 0
    
    left = 1
    right = distance
    
    rocks.sort()
    rocks.append(distance)
    while left <= right:
        mid = (left + right) // 2
        cnt = 0
        prev_rock = 0
        
        for rock in rocks:
            if rock - prev_rock < mid:
                cnt += 1
                if cnt > n:
                    break
            else:
                prev_rock = rock
        if cnt > n:
            right = mid -1
        else:
            answer = mid
            left = mid + 1
    
    return answer

def solution(distance, rocks, n):
    answer = 0
    rocks.sort()
    
    s, e = 0, distance #바위가 아닌 거리를 기준으로 탐색함
    while s <= e:
        m = (s + e) // 2 #중간 거리 즉 이 m이 최소 거리가 되려면 몇 개의 바위를 제거해야 하는지 구해야함
        pre = 0
        cnt = 0
        
        for rock in rocks:
            if cnt > n: #이미 n개 초과의 바위를 없애야 하는 경우
                break
                
            #앞의 바위와의 거리를 비교함
            if rock - pre < m: #거리가 작은 경우
                cnt += 1
            else: #큰 경우에는 앞의 돌을 현재 돌로 기억한다.
                pre = rock #거리가 작은 돌은 삭제 해야하기 때문
                
        if distance - pre < m: #마지막 돌과 목적지까지 거리 계산
            cnt += 1
        
        # 삭제해야 할 돌의 개수를 확인해 비교하고 s, e를 제어하여 다음 탐색 위치로 이동
        if cnt > n:
            e = m - 1
        else:
            answer = m
            s = m + 1
    return answer

def solution(stones, k):
    ppl = 0
    start, end = 0, max(stones)
    
    
    while start <= end:
        current_ppl = (start + end) // 2
        less_then_ppl = 0
        
        for s in stones:
            if s < current_ppl:
                less_then_ppl += 1
                
                if less_then_ppl >= k:
                    break
            else:
                less_then_ppl = 0
                
        if less_then_ppl >= k:
            end = current_ppl - 1
        else:
            ppl = current_ppl
            start = current_ppl + 1
            
    return ppl

def solution(stones, k):
    start,end = 0,max(stones) #기준을 사람 수로 잡음 사람 수가 디딤돌이 적힌 수의 최댓값일때 모든 바위를 넘어가야하기 때문에 end값이 됨
    answer = 0
    while start<=end:
        mid = (start+end)//2 #사람의 수
        jump=0 #뛰어야하는 크기
        canJump = True
        for stone in stones:
            if stone<mid: jump+=1 #해당 stone이 사람의 수(사람이 건넌 수)보다 적으면 그 바위는 뛰어가야 하는 바위임으로 jump+=1
            else: jump = 0 #아니라면 0으로 초기화
            if jump>=k: #뛰어야하는 크기의 제한(k)보다 많이 뛰어야하면 뒤의 for문이 필요 없음
                canJump = False
                break
        if canJump: #제한(k)에 걸리지 않고 모든 바위를 넘어갔을 경우
            answer = mid
            start = mid+1 #사람의 수를 늘림
        else: end = mid-1 #제한(k)에 걸렸을 경우 사람의 수를 줄임
    return answer

def solution(stones, k):
    left = 1
    right = max(stones)
    
    while left <= right:
        mid = (left + right) // 2
        count = 0
        max_count = 0
        
        for stone in stones:
            if stone - mid <= 0:
                count += 1
                if count >= k:
                    break
            else:
                count = 0
        
        if count >= k:
            right = mid - 1
        else:
            left = mid + 1
    
    return left

def isGoOver(stones, man, k):
    cnt = 0
    for stone in stones:
        if stone < man:
            cnt += 1
        else:
            cnt = 0
        if cnt >= k:
            return False
    return True

def solution(stones, k):
    s, e = 1, max(stones)
    m = 0
    result = 0
    
    while s <= e:
        m = (s + e) // 2
        
        if isGoOver(stones, m, k):
            result = max(result, m)
            s = m + 1
        else:
            e = m - 1
    
    return result

def solution(numbers):
    answer = set()
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            answer.add(numbers[i] + numbers[j])
    return sorted(answer)

import itertools
def solution(numbers):
    numberSet = set()
    for num1,num2 in itertools.permutations(numbers,2): #조합
        numberSet.add(num1+num2)
    return list(sorted(numberSet))#정렬

import itertools

def solution(numbers):
    answer = []
    comb = itertools.combinations(numbers, 2)
    
    for i in comb:
        answer.append(sum(i))
    
    ans_sum = list(set(answer))
    return sorted(ans_sum)

import itertools

def solution(numbers):
    return sorted(list(set(nums[0] + nums[1] for nums in itertools.combinations(numbers, 2))))

import itertools

def solution(numbers):
    return sorted(list(set(nums[0] + nums[1] for nums in itertools.permutations(numbers, 2))))

import itertools 

def solution(numbers):
    answer = []
    c = list(itertools.combinations(numbers,2))
    for i in c:
        a,b = i
        answer.append(a+b)
    set_answer = set(answer)
    arr = list(set_answer)
    arr.sort()
    return arr

import itertools

def solution(numbers):
    return sorted(list(set(n1 + n2 for n1, n2 in itertools.combinations(numbers, 2))))

import itertools

def solution(numbers):
    return sorted(list(set(n1 + n2 for n1, n2 in itertools.permutations(numbers, 2))))

def solution(citations):
    max_value = max(citations)
    chk = [0] * max_value

    res = 0
    for i in range(1, max_value):
        for c in citations:
            if c >= i:
                chk[i] += 1
        if chk[i] >= i and i > res:
            res = i

    return res

def solution(citations):
    citations = sorted(citations,reverse=True) #정렬
    arrLen = len(citations)
    for i in range(arrLen):
        if citations[i]<=i: #h편이상(citations[i]편 이상)이 h편(i) 이상
            return i  #citations[i]가 return되지 않는 이유는 [0,3,5,5,5,5]일때 3이상이여도 되지만 4이상이여도 성립하기 때문에i값을 return 시켜야 더 큰 값이 return 된다
    return arrLen

def solution(citations):
    citations.sort(reverse=True)
    for idx , citation in enumerate(citations):
        if idx >= citation:
            return idx
    return len(citations)

def solution(citations):
    citations.sort()
    
    max_h = 0
    for h in range(1, len(citations) + 1):
        if (citations[len(citations) - h] >= h) and (citations[len(citations) - h - 1] <= h or len(citations) == h):
            max_h = h            
    
    return max_h

def solution(citations):
    answer = [0 for i in range(10001)]
    size = len(answer)
    h_index = 0
    
    for i, num in enumerate(citations):
        for j in range(0, num + 1):
            answer[j] += 1
    
    # print(answer)
    for i, num in enumerate(answer):
        # print(num, ">=", i, len(citations) - num, "<=", i)
        if num >= i and len(citations) - num <= i:
            h_index = i
    
    return h_index

def solution(strings, n):
    answer = []
    
    for i in range(len(strings)):
        strings[i] = strings[i][n] + strings[i]
    strings.sort()
    
    for i in range(len(strings)):
        answer.append(strings[i][1:])
    
    return answer

def solution(strings, n):
    return sorted(strings,key=lambda x :(x[n],x))

def solution(strings, n):
    strings.sort(key= lambda x : x[n]+x)
    
    return strings

def solution(strings, n):
    return sorted(strings, key = lambda key: (key[n], key))

def extract_key(s, n):
    return s[n] + '_' + s

def solution(strings, n):
    return sorted(strings, key = lambda v: extract_key(v, n))

def solution(numbers):
    numbers_str = list(map(str, numbers))
    
    numbers_str.sort(key=lambda x: x*3, reverse=True)
    answer = ''.join(numbers_str)
    
    if answer[0] == '0':
        return '0'
    
    return answer

def solution(numbers):
    numberList = list(map(str, sorted(numbers, key=lambda x: (str(x)*4)[:4], reverse=True))) #최대 크기가 1000임으로 길이가 6이 될때까지 늘려 원소들을 비교한다 ex) 1과 1000을 비교하기 위해
    result = "".join(numberList)
    return str(int(result)) #result 0000이었을 때를 위해

def solution(numbers):
    answer = ''
    numbers= list(map(str,numbers))
    numbers.sort(key=lambda x : x*3,reverse=True)
    for i in numbers:
        answer = answer + i
    
    return str(int(answer))

import itertools

def solution(numbers):
    return str(max(map(lambda s: int(''.join(s)), itertools.permutations(map(str, numbers)))))

from functools import cmp_to_key

def my_compare(a, b):
    if a == 0:
        return 1
    
    str_a = str(a)
    str_b = str(b)
    return int(str_b+str_a) - int(str_a+str_b)

def solution(numbers):    
    result = sorted(numbers, key=cmp_to_key(my_compare))
    str_result = "".join(map(str, result))
    
    return "0" if int(str_result) == 0 else str_result

def solution(answers):
    result = []
    first,second,third = 0,0,0 #점수들
    firAn = [1,2,3,4,5] 
    secAn = [2,1,2,3,2,4,2,5]
    thrAn = [3,3,1,1,2,2,4,4,5,5]
    for i,answer in enumerate(answers):
        first += 1 if firAn[i%5] == answer else 0
        second += 1 if secAn[i%8] == answer else 0
        third += 1 if thrAn[i%10] == answer else 0
    maxScore = max([first,second,third])
    for i,score in enumerate([first,second,third]):
        if score == maxScore:
            result.append(i+1)
    return result

def solution(answers):
    a = [1,2,3,4,5]
    b = [2,1,2,3,2,4,2,5]
    c = [3,3,1,1,2,2,4,4,5,5]
    person = [0] * 3
    answer = []
    for i in range(len(answers)):
        if(answers[i] == a[i%5]):
            person[0] += 1
        
        if(answers[i] == b[i%8]):
            person[1] += 1
        
        if (answers[i] == c[i%10]):
            person[2] += 1
        winner = max(person)
    for i in range(len(person)):
        if person[i] == winner:
            answer.append(i+1)
    return answer

def solution(answers):
    answer = []
    
    fuck_math = [[1, 2, 3, 4, 5], [2, 1, 2, 3, 2, 4, 2, 5], [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]]
    cnt = [0, 0, 0]
    
    for i, ans in enumerate(answers):
        for j, jjick in enumerate(fuck_math):
            if jjick[i % len(jjick)] == ans:
                cnt[j] += 1
    
    max_cnt = max(cnt)
    
    for i, c in enumerate(cnt):
        if c == max_cnt:
            answer.append(i + 1)
    
    return answer

def solution(answers):
    answer = (
        (1, 2, 3, 4, 5),
        (2, 1, 2, 3, 2, 4, 2, 5),
        (3, 3, 1, 1, 2, 2, 4, 4, 5, 5)
    )
    
    correct_score = []
    for a in answer:
        correct_cnt = 0
        
        pos = 0
        for pa in answers:
            if pa == a[pos]:
                correct_cnt += 1
                
            pos = (pos + 1) % len(a)
        
        correct_score.append(correct_cnt)
        
    max_score = max(correct_score)
    result = []
    for idx, score in enumerate(correct_score):
        if score == max_score:
            result.append(idx + 1)
            
    return result

def solution(answers):
    ans = []
    first_person = [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5]
    second_person = [2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5]
    third_person = [3,3,1,1,2,2,4,4,5,5,3,3,1,1,2,2,4,4,5,5,3,3,1,1,2,2,4,4,5,5,3,3,1,1,2,2,4,4,5,5]
    first_answer,second_answer, third_answer = 0,0,0  
    for i in range(len(answers)):
        if i >39:
            idx= i%40
        else:
            idx = i
        if answers[i] == first_person[idx]:
            first_answer +=1
        if answers[i] == second_person[idx]:
            second_answer +=1
        if answers[i] == third_person[idx]:
            third_answer +=1
        
    max_num = max(first_answer,second_answer,third_answer)
    if first_answer == max_num:
        ans.append(1)
    if second_answer == max_num:
        ans.append(2)
    if third_answer == max_num:
        ans.append(3)
    ans.sort()
    return ans

def solution(brown, yellow):
    for row in range(1, yellow + 1):
        if yellow % row == 0:
            col = yellow // row #yellow의 column과 row을 구한 뒤
            if 2 * (row + col) + 4 == brown: #brown을 둘렀을때 크기가 같으면
                return [col + 2, row + 2]

import math


def solution(brown, yellow):
    size = brown + yellow
    
    # sqrt를 통해서는 범위제한만 가능. (아직 이게 width임을 보장할 수는 없음)
    max_width = math.ceil(math.sqrt(size))
    for width in range(max_width, 0, -1):
        height = size / width
                
        if not height.is_integer():
            continue
        
        width = int(width)
        height = int(height)
               
        if (width - 2) * (height - 2) == yellow:
            return [max(width, height), min(width, height)]

def solution(brown, yellow):
    # 답을 저장할 리스트
    answer = []

    # 노란 타일의 세로와 가로를 저장할 변수
    yellow_width = 0
    yellow_height = 0

    for height in range(1, int(yellow**0.5) + 1):
        if yellow % height == 0:
            yellow_width = yellow // height
            yellow_height = height
            if (yellow_width + yellow_height) * 2 + 4 == brown:
                answer.append(yellow_width + 2)
                answer.append(yellow_height + 2)
                return sorted(answer, reverse=True)

    return answer

def solution(brown, yellow):
    answer = []
    def count(a,b):
        hap =0
        board = [[0] *b for i in range(a)]
        for i in range(a):
            for j in range(b):
                if i==0 or j==0:
                    board[i][j] = 1
                if i == (a-1) or j==(b-1):
                    board[i][j] =1
        for i in board:
            hap += sum(i)  
        if hap == brown:
            return True
        else:
            return False
    
    for i in range(3, (brown+yellow)//2+1):
        if (brown + yellow) %i==0:
            b = (brown+yellow) // i
            a,b = i,b
            if a>=b:
                ans = count(a,b)
                if ans == True:
                    break
    answer.append(a)
    answer.append(b)
            
            
        
    return answer

import math

def solution(brown, yellow):
    answer = [0, 0]
    
    area = brown + yellow
    for i in range(3, int(math.sqrt(2005000)) + 1):
        j = area // i
        if area % i == 0 and j >= 3:
            width = i if i > j else j
            height = i if i < j else j
            
            brown_cnt = (width * 2) + ((height - 2) * 2)
            if brown_cnt == brown:
                answer[0] = width
                answer[1] = height
                break
    
    return answer

def solution(numbers):
    result = 0
    for num in joinPieces(numbers):
        result += 1 if checkSum(int(num)) else 0 #귀찮아서 체를 안썼는데 쓰는것이 빠를듯
    return result
def checkSum(num): #소수인지 확인
    if num == 1 or num == 0:
        return False
    for i in range(2,int(num**0.5)+1):
        if num%i==0: #나누어지는 수가 있으면 소수가 아님
            return False 
    return True
def joinPieces(numbers): #순열 구하는 함수
    result = []
    def perm(idx, n, piece):
        if idx == n:
            result.append(int("".join(piece[:n])))
        else:
            for i in range(idx, len(piece)): #idx+1부터 시작하면 안바꾸었을때를 포함하지 못함
                piece[idx], piece[i] = piece[i], piece[idx] #순서 변경
                perm(idx + 1, n, piece)
                piece[idx], piece[i] = piece[i], piece[idx]  #순서 원위치
    for i in range(1, len(numbers) + 1): #i = 부분집합의 크기
        perm(0, i, list(numbers)) 
    return set(result)

import itertools
import math

def primes_count(numbers):
    alive = []
    for i in range(2, int(math.sqrt(max(numbers))) + 1):
        to_remove = []
        
        for n in numbers:
            if n == i:
                alive.append(n)
                
            if n % i == 0:
                to_remove.append(n)
            
        for n in to_remove:
            numbers.remove(n)
            
    return len(alive) + len(numbers)
    
def solution(numbers):
    combination_set = set()
    for l in range(1, len(numbers) + 1):
        for i in itertools.permutations(numbers, l):
            num = int(''.join(i))
            if num <= 1:
                continue
                
            combination_set.add(num)
    return primes_count(combination_set)

import itertools
import math

def eratos(num):
    max_table_search = math.ceil(math.sqrt(num))
    table = [False for _ in range(num + 1)]
    
    for i in range(2, max_table_search):
        ptr = i
        if table[ptr]:
            continue
        
        ptr += i
        while ptr < len(table):
            table[ptr] = True
            
            ptr += i

    table[0] = True
    table[1] = True
    return table

def solution(numbers):
    possible_num = sorted(tuple(numbers), reverse=True)
    max_available = int(''.join(possible_num))
    
    eratos_table = eratos(max_available)
    
    lookup_num = set()
    for l in range(1, len(possible_num) + 1):
        lookup_num.update(map(lambda s: int(''.join(s)), itertools.permutations(possible_num, r = l)))
    
    return len(tuple(filter(lambda n: eratos_table[n] == False, lookup_num)))

import math
from itertools import permutations
def prima(num):
    if num <2:
        return False
    for x in range(2, int(math.sqrt(num))+1):
        if num % x ==0:
            return False
    return True

def solution(numbers):
    answer = 0
    arr = []
    for st in numbers:
        arr.append(st)
        
    products_arr = []
    
    for i in range(1, len(numbers)+1):
        for j  in permutations(arr , i):
            products_arr.append(int("".join(j)))
    
    
    for i in list(set(products_arr)):
        if prima(i) == True:
            print(i)
            answer +=1
    return answer

import math;

result = set()

def recur(numbers, size, cur_num, use_list):
    if len(cur_num) == size:
        tmp = int(cur_num)
        
        if tmp < 2:
            return
        if tmp == 2:
            result.add(2)
            return
        for i in range(2, int(math.sqrt(tmp))+1):
            if tmp%i==0:
                return
        result.add(tmp)
        return
    
    for i in range(0, len(numbers)):
        if i not in use_list:
            use_list.add(i)
            recur(numbers, size, cur_num+numbers[i], use_list)
            use_list.remove(i)

def solution(numbers):    
    for i in range(1, len(numbers)+1):
        recur(numbers, i, "", set())
    
    return len(result)

import re

def solution(user_ids, banned_input):
    banned_ids = [banned_id.replace('*', '.') + '$' for banned_id in banned_input]
    #*을 .으로 바꿔준후 $을 더해 정규 표현식으로 표현해 준다
    error_ids = [[] for _ in range(len(banned_ids))]
    for i, banned_id in enumerate(banned_ids):
        for user_id in user_ids:
            if re.fullmatch(banned_id, user_id):
                error_ids[i].append(user_id) #[불량사용자 배열의 번호][제재 아이디]
    
    answer = set() #[1,2,3] [2,3,1]과 같은 중복도 잡아줌
    
    def recursive(idx, checkArr):
        if idx == len(error_ids):
            answer.add(frozenset(checkArr)) #제재 아이디가 중복되지 않는 배열 add
            #frozenset을 해야지 수정불가능한 객체가 되어서 set에 넣을 수 있다 
            return
        for user_id in error_ids[idx]: #불량사용자 별 제재 아이디를 하나씩
            if user_id not in checkArr: #불량사용자 별이기 때문에 중복이 있을 수 있음
                recursive(idx + 1, checkArr + [user_id])
    
    recursive(0, [])
    
    return len(answer)

import itertools

def checkBan(user_id, banned_id):
    for i in range(len(banned_id)):
   
        for j in range(len(user_id[i])):
            if len(banned_id[i]) != len(user_id[i]):
                return False
            if banned_id[i][j] == '*':
                continue
            if banned_id[i][j] != user_id[i][j]:
                return False
    return True
            
def solution(user_id, banned_id):
    answer = []
    
    for permu in itertools.permutations(user_id, len(banned_id)):
        if checkBan(permu, banned_id):
            user = list(set(permu))
            user.sort()
            if user not in answer:
                answer.append(user)

    return len(answer)

import re

def pick_recursive(current, available, picked):
    if len(available) == 0:
        current_pick = '-'.join(sorted(current))
        if current_pick not in picked:
            picked.add(current_pick)
            
        return picked
    
    for user in available[0]:
        if user in current:
            continue
        
        current.add(user)
        pick_recursive(current, available[1:], picked)
        current.remove(user)
    
    return picked

def solution(user_id, banned_id):
    banned_id_re = tuple(map(lambda pattern: re.compile('^' + pattern.replace("*", '.') + '$'), banned_id))
    banned_id_list = []
    
    for pattern in banned_id_re:
        banned_id_re_list = []
        for uid in user_id:
            if pattern.match(uid):
                banned_id_re_list.append(uid)
                
        banned_id_list.append(banned_id_re_list)
    
    picked = set()
    current = set()
    
    return len(pick_recursive(current, banned_id_list, picked))

combinations = set()

def find(ban_user, depth, combination):
    if depth == len(ban_user):
        combinations.add("".join(sorted([str(i) for i in combination])))
        return
    
    for id in ban_user[depth]:
        if id in combination:
            continue
        combination.append(id)
        find(ban_user, depth + 1, combination)
        combination.remove(id)

def match(id, pattern):
    if len(id) != len(pattern):
        return False
    
    for i in range(len(id)):
        if pattern[i] == "*":
            continue
        if id[i] != pattern[i]:
            return False
    return True

def solution(user_id, banned_id):
    ban_user = [[] for i in banned_id]
    
    for i, id in enumerate(user_id):
        for j, pattern in enumerate(banned_id):
            if match(id, pattern):
                ban_user[j].append(i)
    
    find(ban_user, 0, [])
        
    return len(combinations)

operator = ["*", "-", "+"]

def solution(expression):
    arr = split(expression)
    maxVal = 0
    for i in range(3):
        fir = operator[i % 3] #operator 순서
        sec = operator[(i + 1) % 3]
        thr = operator[(i + 2) % 3]
        maxVal = max(maxVal, abs(changeOrder(arr[:], fir, sec, thr)),abs(changeOrder(arr[:], fir, thr, sec))) #두 번째 세 번째 순서를 바꾼 값을 비교
    return maxVal

def changeOrder(arr, fir, sec, thr):
    def findOper(arr, oper): #받은 operator을 찾아 그 앞 뒤 배열의 숫자를 operator에 맞게 계산해서 압축
        idx = 1
        while idx < len(arr):
            if arr[idx] == oper: #operator을 발견
                result = cal(oper, arr[idx - 1], arr[idx + 1]) #앞 뒤 숫자로 계산
                arr = arr[:idx - 1] + [result] + arr[idx + 2:] #3개의 배열을 없애고 계산한 값을 끼워 넣음
                #idx +=1을 안해야지 순서가 맞음
            else:
                idx += 1
        return arr

    arr = findOper(arr, fir)
    arr = findOper(arr, sec)
    arr = findOper(arr, thr)
    return arr[0]

def cal(oper, a, b): #oper:str을 받아 계산해주는 함수
    if oper == "+":
        return a + b
    elif oper == "-":
        return a - b
    elif oper == "*":
        return a * b

def split(sentence): #expression을 배열로 바꾸어주는 함수
    arr = []
    start = 0 #start와 end 포인터 두개로 가늠
    for end in range(len(sentence)):
        if sentence[end] in operator: #+,-,*을 만났을때 앞과 해당 operator을 배열로 넣음 
            arr.append(int(sentence[start:end]))
            arr.append(sentence[end])
            start = end + 1
    arr.append(int(sentence[start:])) #마지막 숫자 append
    return arr

import re
import itertools

oper = ('+', '-', '*')

def calculate(exp, op_priority):
    cc = {
        '+': lambda n1, n2: n1 + n2,
        '-': lambda n1, n2: n1 - n2,
        '*': lambda n1, n2: n1 * n2
    }
    
    remain = exp[:]
    for op in op_priority:
        ptr = 0
        while ptr < len(remain):
            if remain[ptr] != op:
                ptr += 1
                continue
            
            run = cc[op]
            remain[ptr] = run(int(remain[ptr - 1]), int(remain[ptr + 1]))

            remain.pop(ptr + 1)
            remain.pop(ptr - 1)
            
    return remain[0]
            

def solution(expression):
    token = re.findall('\d+|\+|-|\*', expression)
    
    op_priority = itertools.permutations(oper)
    return max(map(lambda op: abs(calculate(token, op)), op_priority))

import itertools
def solution(expression):
    answer = 0
    
    for permu in itertools.permutations(['*','-','+'],3):
        numbers = []
        signs = []
        num = ''
        for char in expression:
            if char.isdigit():
                num += char
            else:
                numbers.append(int(num))
                signs.append(char)
                num = ''
        numbers.append(int(num))
        result = 0
        for sign in permu:
            while sign in signs:
                idx = signs.index(sign)
                if sign == '*':
                    value = numbers[idx] * numbers[idx+1]
                if sign == '-':
                    value = numbers[idx] - numbers[idx+1]
                if sign == '+':
                    value = numbers[idx] + numbers[idx+1]
                numbers[idx] = value
                
                del signs[idx]
                del numbers[idx+1]
        answer = max(answer, abs(numbers[0]))
      
    return answer

import itertools
import re

def solution(exp):
    answer = 0
    
    splited_exp = re.split("(\*|\-|\+)", exp)
    
    for ordered_opers in itertools.permutations(["*", "-", "+"], 3):
        tmp_exp = splited_exp
        for op in ordered_opers:
            while op in tmp_exp:
                for i, x in enumerate(tmp_exp):
                    if x == op:
                        num = eval(tmp_exp[i - 1] + x + tmp_exp[i + 1])
                        tmp_exp = tmp_exp[:i - 1] + [str(num)] + tmp_exp[i + 2:]
                        break
        answer = max(abs(int(tmp_exp[0])), answer)
    
    return answer

def solution(num):
    return recursive(num,0)

def recursive(num,cnt):
    if num ==1 : return cnt
    if cnt == 500: return -1
    if num %2 ==0 :
        return recursive(num//2, cnt+1)
    else:
        return recursive(num*3+1, cnt+1)

def solution(num):
    answer = 0
    while (num != 1):
        if answer > 500:
            answer = -1
            break
        else:
            if (num %2 ==0):
                num = num // 2
            else:
                num = num *3 +1
            answer +=1
        
    return answer

def solution(num):
    def collatz(num, count):
        if num == 1:
            return count
        if count == 500:
            return -1
        if num % 2 == 0:
            return collatz(num // 2, count + 1)
        else:
            return collatz(num * 3 + 1, count + 1)
    return collatz(num, 0)

def collatz(num, depth):
    if num == 1:
        return depth
    if depth == 500:
        return -1
    
    if num % 2 == 0:
        num//=2
    else:
        num = num * 3 + 1
    
    return collatz(num, depth + 1)

def solution(num):
    return collatz(num, 0)

def solution(num):
    for i in range(500):
        if num == 1:
            return i
        if num % 2 == 0:
            num//=2
        else:
            num = num * 3 + 1
    
    return -1

def solution(num):
    for cnt in range(500):
        if num == 1:
            return cnt
        
        if num & 1 == 0:
            num //= 2
        else:
            num = num * 3 + 1
    
    return -1

def hanoi(n,start , to,by,answer):
    if n==0:
        return
    else:
        hanoi(n-1 , start, by, to,answer)
        answer.append([start, to])
        hanoi(n-1,by, to, start,answer)

def solution(n):
    answer = [[]]
    hanoi(n,1,3,2,answer)
    return answer[1:]

def solution(n):
    return recursive(n, 1, 3, 2, [])

def recursive(n, start, end, middle, answer):
    if n == 1:
        answer.append([start, end])
    else:
        recursive(n-1, start, middle, end, answer) #n-1개의 원반을 중간으로 이동
        answer.append([start, end]) #n-1개를 옮겼으니 마지막에 남은건 가장 무거운 원반
        #따라서 이를 마지막으로 이동
        recursive(n-1, middle, end, start, answer) #중간으로 옮겼던 n-1개의 원반을
        #다시 마지막으로 이동
    return answer

# 일단 알고리즘을 어캐해야할지 감도 안와서... 전체 흐름을 적어봄
# 1) [1 -> 3]
# 2) <1 -> 2, [1 -> 3], 2 -> 3>
# 3) (1 -> 3, <1 -> 2>, 3 -> 2), [1 -> 3], (2 -> 1, <2 -> 3>, 1 -> 3)
move_log = []

def hanoi(depth, src, dst):
    # 맨 위의것이 될 때 까지 함수 호출 들어감.
    if depth == 0:
        return
    
    stopover = 6 - src - dst
    
    hanoi(depth - 1, src, stopover)
    move_log.append([src, dst])
    hanoi(depth - 1, stopover, dst)   
    return

def solution(n):
    global move_log
    # 어쨋든 맨 아래의 것을 (n-1) 1 -> 3으로 옮김 (wrap)
    hanoi(n, 1, 3)
    
    return move_log

def hanoi(n, start, mid, end, answer):
    if n == 1:
        answer.append([start, end])
        return
    hanoi(n-1, start, end, mid, answer)
    answer.append([start, end])
    hanoi(n-1, mid, start, end, answer)

def solution(n):
    answer = []
    hanoi(n, 1, 2, 3, answer)
    return answer

def hanoi(n, a, b, c, result):
    if n == 0:
        return result
    
    hanoi(n-1, a, c, b, result)
    result.append([a, c])
    hanoi(n-1, b, a, c, result)

def solution(n):
    answer = []
    hanoi(n, 1, 2, 3, answer)
    return answer

count = 0

def solution(word):
    global count
    for alphabet in ['A','E','I','O','U']:
        if dfs(word,alphabet):
            return count

def dfs(findWord,word):
    global count
    count +=1
    if findWord == word :
        return True
    if len(word) == 5:
        return False
    for alphabet in ['A','E','I','O','U']:
        if dfs(findWord,word+alphabet):
            return True

def solution(word):
    answer = 0
    for i, n in enumerate(word):
        answer+= (5**(5-i)-1) / 4 * "AEIOU".index(n) +1
    return answer

#첫번째 글자가 정해졌을때 나올 수 있는 경우의 수가 5**4+5**3+5**2+5**1+1 이고
#첫번째와 두번째 글자가 정해졌을때 경우의 수가 5**3+5**2+5**1+1이기 때문에 이에 +1한 값이
#해당 글자의 순서이다 이를 점화식으로 나타내면 시그마 i=0 부터 j까지 5의 i제곱 이므로
#등비수열의 합에 의해 1*(5**(5-i)) / (5-1) 이 된다

from itertools import product
def solution(word):
    answer = 0
    words = ['A','E','I','O','U']
    ans = []
    for i in range(1, 6):
        for j in product(words,repeat = i):
            ans.append("".join(j))

    ans.sort()
    
    return ans.index(word)+1

alphabet = ['A', 'E', 'I', 'O', 'U']

count = 0
def find(word, current):
    global count
    
    count += 1
    if current == word:
        return True
    
    if len(current) >= 5:
        return False
    
    for alpha in alphabet:
        current.append(alpha) 
        if find(word, current):
            return True
        
        current.pop()
            

def solution(word):
    global count
    word = list(word)
    
    current = []
    for alpha in alphabet:
        current.append(alpha) 
        if find(word, current):
            return count
        
        current.pop()

alpha = ["A", "E", "I", "O", "U"]

def aeiou(word, result):
    if len(word) >= 5:
        return
    
    for ch in alpha:
        tmp = word + ch
        result.append(tmp)
        aeiou(tmp, result)
    

def solution(word):
    answer = []
    aeiou("", answer)
    return answer.index(word) + 1

def solution(k, room_number):
    answer = []
    rooms = {}
    for room in room_number:
        numbers = rooms.get(room, 0) 
        # rooms 에 room이 있다면 value 반환 아니면 0 반환 
        if numbers:
            temp = [room]
            while True:
                index = numbers
                numbers = rooms.get(numbers,0)
                if not numbers:
                    answer.append(index)
                    rooms[index] = index+1
                    for i in temp:
                        rooms[i] = index + 1
                    break
                temp.append(numbers)
        
        else:
            answer.append(room)
            rooms[room] = room+1
    
        
    return answer

def solution(k, room_number):
    rooms = dict()
    for customer in room_number:
        visits=[]
        while customer in rooms:
            visits.append(customer)
            customer = rooms[customer]
        for visit in visits:
            rooms[visit] = customer +1
        rooms[customer] = customer +1
    return list(rooms)

import sys
sys.setrecursionlimit(2000)
#파이썬은 기본 재귀 함수 제한이 1000 이를 2000으로 수정하는 코드
def solution(k, room_number):
    rooms = {}

    def find(customer):
        if customer not in rooms:
            rooms[customer] = customer + 1
            return customer
        rooms[customer] = find(rooms[customer])
        return rooms[customer]

    return [find(customer) for customer in room_number]

def solution(k, room_number):
    hashmap = {}
    result = []
    
    for room in room_number:
        follow = room
        
        visited = [follow, ]
        while follow in hashmap:
            follow = hashmap[follow]
            visited.append(follow)
            
        result.append(follow)
        
        for v in visited:
            hashmap[v] = follow + 1
    
    return result

import sys
sys.setrecursionlimit(10000)

def find_room(num, room_table):
    if num not in room_table:
        room_table[num] = num + 1
        return num + 1
    
    next_room = find_room(room_table[num], room_table)
    room_table[num] = next_room
    return next_room

def solution(k, room_number):
    room_table = {}
    
    for num in room_number:
        find_room(num, room_table)
        
    return list(room_table.keys())

import sys
sys.setrecursionlimit(10000)

def find_room(num, room_table, result):
    if num not in room_table:
        room_table[num] = num + 1
        result.append(num)
        return num + 1
    
    next_room = find_room(room_table[num], room_table, result)
    room_table[num] = next_room
    return next_room

def solution(k, room_number):
    room_table = {}
    result = []
    for num in room_number:
        find_room(num, room_table, result)
    
    return result

def solution(s, n):
    s = list(s)
    for i in range(len(s)):
        if s[i].isupper():
            s[i] = chr((ord(s[i]) - ord('A') + n) % 26 + ord('A'))
        elif s[i].islower():
            s[i]=chr((ord(s[i])-ord('a')+ n)%26+ord('a'))
    return "".join(s)

def solution(s, n):
    answer = ''
    for i in range(len(s)):
        if s[i] == ' ':
            answer += ' '
            continue
        first = ord('A') if s[i].isupper() else ord('a') 
        answer += chr((ord(s[i]) - first + n) % 26 + first) #해당아스키 값 - 알파벳의 시작 아스키 값 + n을 26으로 나눈 나머지를 다시 알파벳의 시작 아스키 값에 더해준다
    return answer

def solution(s, n):
    answer = ""
    for c in s:
        if 'A' <= c <= 'Z':
            answer += chr((ord(c) - ord('A') + n) % 26 + ord('A'))   
        elif 'a' <= c <= 'z':
            answer += chr((ord(c) - ord('a') + n) % 26 + ord('a'))
        else:
            answer += c
    return answer

def solution(s, n):
    result = ""
    for i in range(len(s)):
        ch = s[i]
        if ch == " ":
            result+=" "
            continue
        
        tmp = ord(ch) + n
        if "A" <= ch <= "Z":
            if tmp > 90:
                tmp-=26
        if "a" <= ch <= "z":
            if tmp > 122:
                tmp-=26
        result+=chr(tmp)
        
    return result

def solution(s, n):
    answer = ''
    dicts = {'a':0, 'b':1, 'c':2, 'd':3, 'e':4, 'f':5, 'g':6,'h':7,'i':8,'j':9,'k':10,'l':11,'m':12,'n':13, 'o':14,'p':15,'q':16,'r':17,'s':18,'t':19,'u':20,'v':21, 'w':22,'x':23,'y':24,'z':25}
    convert_dict = {v:k for k,v in dicts.items()}
    for i in range(len(s)):
        if s[i] == ' ':
            answer +=' '
        elif s[i] not in dicts :
            alphbet=s[i].lower()
            num = dicts[alphbet] +n 
            ans = convert_dict[num%26]
            answer+= ans.upper()
        else:
            num = dicts[s[i]] +n
            ans = convert_dict[num%26]
            answer+= ans
    return answer

def solution(s, n):
    result = []
    
    a = ord('a')
    z = ord('z')
    A = ord('A')
    Z = ord('Z')
    alphabet = z - a
    
    for c in s:
        ch = ord(c)
        
        # 대문자
        if (ch >= A and ch <= Z):
            ch = (ch - A + n) % (alphabet + 1) + A
            result.append(chr(ch))
        elif (ch >= a and ch <= z):
            ch = (ch - a + n) % (alphabet + 1) + a
            result.append(chr(ch))
        else:
            result.append(c)
            
    return ''.join(result)

def solution(s):
    answer = ''
    for word in s.split(' '):
        for i in range(len(word)):
            if i % 2 == 0:
                answer += word[i].upper()
            else:
                answer += word[i].lower()
        answer += ' '
    return answer[0:-1]

def solution(s):
    answer = ''
    index = 0
    for i in range(len(s)):
        alphabet = s[i]
        if alphabet == " ": #공백 초기화
            answer+= alphabet
            index = 0
            continue
        if index%2 == 0:# 짝일경우
            answer += alphabet.upper()
        else: #나머지
            answer += alphabet.lower()
        index += 1
    return answer

def solution(s):
    answer = ""
    idx = 0
    for c in s:
        if c == ' ':
            idx = 0 
        elif idx % 2 == 0:
            c = c.upper()
            idx += 1
        else:
            c = c.lower()
            idx += 1
        answer += c
    return answer

def solution(s):
    ans = ''
    idx = 0
    for i in s:
        idx +=1
        if i ==' ':
            ans +=' '
            idx =0
            continue
        elif idx % 2==1:
            ans += i.upper()
        else:
            ans += i.lower()
 
    return ans

def solution(s):
    answer = ''
    
    arr = s.split(" ")
    for word in arr:
        for i in range(0, len(word)):
            tmp = word[i]
            if i%2==0:
                tmp = tmp.upper()
            else:
                tmp = tmp.lower()
            answer+=tmp
        answer+=" "
    
    return answer[:-1]

def solution(s):   
    result = []
    for s in s.split(' '):
        word = []
        
        for idx, c in enumerate(s):            
            if idx % 2 == 0:
                word.append(c.upper())
            else:
                word.append(c.lower())
        
        result.append(''.join(word))
        print(result)
    
    return ' '.join(result)

def solution(s):
    answer = []
    s = s[2:-2]
    s = s.split('},{')
    s.sort(key = len)
    for i in s:
        li = i.split(',')
        for ele in li:
            if int(ele) not in answer:
                answer.append(int(ele))
    return answer

def solution(s):
    s = "".join(list(s)[1 : len(s) - 1])
    
    start = []
    end = []
    for i in range(len(s)):
        if s[i] == '{':
            start.append(i + 1)
        if s[i] == '}':
            end.append(i)
    
    cases = []
    for i in range(len(start)):
        s_set = s[start[i] : end[i]]
        cases.append(list(map(int, s_set.split(','))))
    cases.sort(key=len)
    
    answer = []
    answer_set = set()
    for c in cases:
        for e in c:
            if e in answer_set:
                continue
            answer_set.add(e)
            answer.append(e)
    
    return answer

def solution(s):
    answer = []
    
    ss = sorted(s[2:-2].split("},{"), key = len)
    set_answer = set()
    
    for arr in ss:
        i_arr = list(map(int, arr.split(",")))
        for num in i_arr:
            if num in set_answer:
                continue
            answer.append(num)
            set_answer.add(num)
    
    return answer

def solution(s):
    tuples = []
    answer = []
    for tuple in s[2:-2].split("},{"): #튜플로 변환
        tuple = list(map(lambda x: int(x),tuple.split(","))) 
        tuples.append(tuple)
    tuples = sorted(tuples,key= lambda tuple: len(tuple)) # list 길이에 따른 정렬
    for tuple in tuples: #같은것만
        for i in range(len(tuple)):
            num = tuple[i]
            if num not in answer:
                answer.append(num)
    return answer

import re
def solution(s):
    r = re.compile("{([\d, ]+)}")
    find = r.findall(s)
    
    result = []
    find = sorted(find, key=len)
    shown = {}
    for f in find:
        splited = map(int, f.split(','))
        
        for num in splited:
            if num in shown:
                continue
            
            result.append(num)
            shown[num] = None
            
    return result

def solution(s): 
    stack = []
    for i in s:
        if len(stack) == 0:
                stack.append(i)
        elif stack[-1] == i:
            stack.pop()
        else: 
            stack.append(i)
    if len(stack) == 0:
        return 1
    else: 
        return 0

from collections import deque;

def solution(s):
    stack = deque()
    
    for ch in s:
        if len(stack) == 0:
            stack.append(ch)
        elif stack[-1] == ch:
            stack.pop()
        else:
            stack.append(ch)
    
    return 1 if len(stack) == 0 else 0

def solution(s):
    stack = []
    for char in s:
        if stack and stack[-1] == char: #짝수로 붙어있기 때문에 stack에 넣고 빼기
            stack.pop()
        else:
            stack.append(char)
    return 1 if not stack else 0

def solution(s):
    answer = -1
    stack = []
    
    for c in s:
        if(len(stack) == 0):
            stack.append(c)
            continue
        if(stack[-1] == c): stack.pop()
        else: stack.append(c)
        
    return 1 if len(stack) == 0 else 0

def solution(s):
    answer = -1
    stack =[]
    for i in s:
        if len(stack) ==0:
            stack.append(i)
        elif stack[-1] == i:
            stack.pop()
        else:
            stack.append(i)
    if len(stack) ==0:
        answer = 1
    else:
        answer =0
        
    return answer

def solution(s):
    tmp = []
    
    for c in s:
        tmp.append(c)
        
        while len(tmp) >= 2 and tmp[-1] == tmp[-2]:
            tmp.pop()
            tmp.pop()
    
    return 1 if len(tmp) == 0 else 0

def solution(s):
    answer = len(s)
    
    for size in range(1, len(s)//2 + 1):
        
        tmp = ""
        cur = s[:size]
        cnt = 1
        
        for i in range(size, len(s) + size, size): # 마지막 스트링까지 더해주기 위해 범위 설정
            if cur == s[i:i+size]:
                cnt+=1
                continue
            
            if cnt == 1:
                tmp += cur
            else:
                tmp += str(cnt) + cur
            cur = s[i:i+size]
            cnt = 1
        
        answer = min(answer, len(tmp))
    
    return answer

def solution(s):
    if len(s) == 1:
        return 1
    
    answer = len(s)
    
    for s_len in range(1, len(s) // 2 + 1):
        comp_str = ""
        prev_str = s[:s_len]
        count = 1
        
        for j in range(s_len, len(s), s_len):
            next_str = s[j:j + s_len]
            if prev_str == next_str:
                count += 1
            else:
                comp_str += prev_str if count == 1 else str(count) + prev_str
                prev_str = next_str
                count = 1
        
        comp_str += prev_str if count == 1 else str(count) + prev_str
        answer = min(answer, len(comp_str))
    
    return answer

def solution(s):
    answer = len(s)
    
    for size in range(1, len(s)):
        
        tmp = ""
        cur = s[:size]
        cnt = 1
        
        for i in range(size, len(s) + size, size): # 마지막 스트링까지 더해주기 위해 범위 설정
            if cur == s[i:i+size]:
                cnt+=1
                continue
            
            if cnt == 1:
                tmp += cur
            else:
                tmp += str(cnt) + cur
            cur = s[i:i+size]
            cnt = 1
        
        answer = min(answer, len(tmp))
    
    return answer

import textwrap

def solution(s):
    inputLen = len(s)
    answer = None
    for i in range(1,inputLen//2+2):
        stack = textwrap.wrap(s,i) #i 크기 만큼 나누기
        presentLen  = inputLen
        isDuplicate = 0 #중복된 횟수
        present = 0
        for present in range (len(stack)-1):
            if stack[present] == stack[present+1]: #중복되었을 때
                isDuplicate +=1 
                presentLen -= i # i크기 만큼 줄어듬
            else:
                if isDuplicate != 0: #중복 종료
                    presentLen += len(str(isDuplicate+1)) #중복된 횟수의 크기만큼 늘어남
                    # 첫번째는 안쓰고 두번째부터 쓰기 때문에 +1
                    isDuplicate = 0
        if isDuplicate !=0:
            presentLen += len(str(isDuplicate+1)) #마지막이 중복일 경우
        answer = presentLen if answer is None else min(answer,presentLen)            
    return answer
#솔직히 더해가는게 더 좋을듯

import math

def word_spliter(word, step):
    pos = step
    s_len = len(word)
    remain = s_len % step
    
    while pos <= s_len:
        yield word[pos - step:pos]
        
        pos += step
        
    if remain > 0:
        yield word[-remain:]
    


def solution(s):
    s_len = len(s)
    
    cnt = {}
    for step in range(1, math.ceil(s_len / 2) + 1):
        compressed = []
        count = 1
        last = ''
        
        for c in word_spliter(s, step):
            if last == c:
                count += 1
            
            else:
                if count > 1:
                    compressed.append(str(count))
                compressed.append(last)
                
                last = c
                count = 1
                
        if count > 1:
            compressed.append(str(count))
        compressed.append(last)
        

        cnt[step] = len(''.join(compressed))
    
    return min(cnt.values())

def solution(n):
    answer = ''
    
    while n > 0:
        n, r = divmod(n,3)
        answer += str(r)
    return int(answer, 3)

def solution(n):
    answer = 0
    
    n3 = ""
    while n >= 3:
        n3 += str(n % 3)
        n//=3
    
    n3+=str(n) if n > 0 else ""
    
    mul3 = 1
    for i in range(len(n3) - 1, -1, -1):
        answer += int(n3[i]) * mul3
        mul3 *= 3
    
    return answer

def solution(n):
    triple = convert3(n)
    sum = 0
    for i in range(len(triple)):
        sum += triple[i] * (3 ** i) 
    return sum

def convert3(num):
    list_s = []
    while(True):
        if num == 0:
            break
        list_s.insert(0, num % 3)
        num = num // 3
    return list_s

def solution(n):
    output =[]
    while n >2 :
        output.append(n%3)
        n = n//3
    output.append(n)
    digit = 1
    answer = 0
    for i in range(len(output)-1,-1,-1):
        answer += int(output[i]) * digit
        digit *= 3    
    return answer

def jinsu(n, r):
    result = []
    
    d, m = n, 0
    while d > 0:
        d, m = divmod(d, r)
        result.append(str(m))
        
    return ''.join(result)

def solution(n):
    return int(jinsu(n, 3), 3)

def solution(s):
    zero_cnt = 0
    cnt = 0
    while True:
        if s == "1":
            break
        zero_cnt += s.count("0")
        s = s.replace("0",'')
        s = bin(len(s))[2:] 
        cnt += 1
        
    return [cnt,zero_cnt]

def solution(s):
    answer = [0, 0]
    
    while s!="1":
        cnt = s.count("0")
        s = s.replace("0", "")
        
        length = len(s)
        s = bin(length)[2:]
        
        s = s[::-1]
        answer[0] += 1
        answer[1] += cnt
    
    return answer

def solution(s):
    answer = [0, 0]
    
    while s!="1":
        cnt = 0
        for num in s:
            if num == "0":
                cnt+=1
        s = s.replace("0", "")
        
        length = len(s)
        s = ""
        while length >= 2:
            s += str(length % 2)
            length //= 2
        s += str(length) if length > 0 else ""
        
        s = s[::-1]
        answer[0] += 1
        answer[1] += cnt
    
    return answer

def solution(s):
    list_s = list(s)
    before = len(list_s)
    countBin = 0
    count0 = 0
    while(True):
        if len(list_s) == 1 and list_s[0] == "1":
            break
        before = len(list_s)
        list_s = list(filter(is_one, list_s))
        count0 += before - len(list_s)
        list_s = convert2(len(list_s))
        countBin += 1
    return [countBin, count0]

def is_one(e):
    return True if e == "1" else False

def convert2(num):
    list_s = []
    while(True):
        if num == 0:
            break
        list_s.insert(0, str(num % 2))
        num = num // 2
    return list_s

def solution(s):
    count = 0
    zeroCount = 0
    while s != "1":
        count += 1
        zero = s.count("0") #0의 개수
        zeroCount += zero 
        s= changeToBinary(len(s)-zero) #0을 제외한 길이를 이진수로 변환 
    answer = [count, zeroCount]
    return answer

def changeToBinary(s):
    return bin(s).replace("0b","")

def solution(s):
    step_count = 0
    removed_zero = 0
    
    
    while s != '1':
        step_count += 1
        
        original_cnt = len(s)
        s = s.replace('0', '')
        removed_zero += (original_cnt - len(s))
        
        s = str(bin(len(s))[2:])
        
    
    return [step_count, removed_zero]

def solution(new_id):
    new_id = new_id.lower()
    
    allowed = "abcdefghijklmnopqrstuvwxyz0123456789-_."
    new_id = ''.join(c for c in new_id if c in allowed)
    
    result = []
    for c in new_id:
        if result and result[-1] == '.' and c == '.':
            continue
        result.append(c)
    new_id = ''.join(result)
    
    new_id = new_id.strip('.')
    
    if not new_id:
        new_id = 'a'
    
    new_id = new_id[:15].rstrip('.')
    
    while len(new_id) < 3:
        new_id += new_id[-1]
    
    return new_id

import re

def solution(new_id):
    st = new_id
    
    st = st.lower()
    st = re.sub('[^a-z0-9\-_.]', '', st)
    st = re.sub('[.]+', '.', st)
    st = re.sub('^[.]|[.]$', '', st)
    
    st = 'a' if len(st) == 0 else st[:15]
    
    st = re.sub('^[.]|[.]$', '', st)
    
    st = st if len(st) > 2 else st + "".join([st[-1] for i in range(3-len(st))])
    
    return st

import re

def solution(new_id):
    st = new_id
    
    st = st.lower()
    st = re.sub('[^a-z0-9\-_.]', '', st)
    st = re.sub('\.+', '.', st)
    st = re.sub('^[.]|[.]$', '', st)
    
    st = 'a' if len(st) == 0 else st[:15]
    
    st = re.sub('^[.]|[.]$', '', st)
    
    st = st if len(st) > 2 else st + "".join([st[-1] for i in range(3-len(st))])
    
    return st

def solution(new_id):
    new_id = new_id.lower()
    list_id = list(new_id)
    
    stack = []
    for i in range(len(list_id)):
        # 2 
        if not checkPolicy(list_id[i]):
            continue
        # 3    
        if len(stack) > 0:
            if list_id[i] == '.':
                if stack[-1] == list_id[i]:
                    continue
        stack.append(list_id[i])
    list_id = stack
    # 4
    if len(list_id) > 0 and list_id[0] == '.':
        list_id.pop(0)
    
    if len(list_id) > 0 and list_id[-1] == '.':
        list_id.pop()
    # 5
    if len(list_id) == 0:
        list_id.append('a')
    
    while(not (3 <= len(list_id))):
        list_id.append(list_id[-1])
        
    if not (len(list_id) <= 15):
        list_id = list_id[:15]
        if list_id[-1] == '.':
            list_id.pop()

    return ''.join(list_id)

def checkUpper(c):
    return 'A' <= c <= 'Z'

def convertToLower(c):
    return chr(ord(c) + (ord('a') - ord('A')))

def checkPolicy(c):
    if ('a' <= c <= 'z'):
        return True
    if (c.isdigit()):
        return True
    if (c == '-'):
        return True
    if (c == '_'):
        return True
    if (c == '.'):
        return True
    return False

def solution(new_id):
    new_id = new_id.lower()
    specialCheck = ""
    for i in range(len(new_id)):
        asciiNum = ord(new_id[i])
        if asciiNum == 45 or asciiNum ==46 or 48<=asciiNum<=57 or asciiNum == 95 or 97<=asciiNum<=122:
            specialCheck += new_id[i]
    isDotDuplicate = False
    answer = ""
    for i in range(len(specialCheck)):
        if specialCheck[i] == '.' :
            if not isDotDuplicate: 
                answer += specialCheck[i]
                isDotDuplicate = True
        else:
            answer += specialCheck[i]
            isDotDuplicate = False
    if answer[0] == ".":
        answer = answer[1:]
        if len(answer) == 0:
            return "aaa"
    if answer[-1] == ".":
        answer = answer[:-1]
        if len(answer) == 0:
            return "aaa"
    answer = answer[:15]
    if answer[-1] == ".":
        answer = answer[:-1]
    if len(answer) <= 2:
        while len(answer) < 3:
            answer += answer[-1]
    return answer

import re

def convert(new_id):
    new_id = new_id.lower()
    new_id = re.compile('[^a-z0-9\-_\.]').sub('', new_id)
    new_id = re.compile('\.{2,}').sub('.', new_id)
    new_id = re.compile('^\.').sub('', new_id)
    new_id = re.compile('\.$').sub('', new_id)
    
    if new_id == '':
        new_id = 'a'
        
    if len(new_id) >= 16:
        new_id = new_id[:15]
        new_id = re.compile('\.$').sub('', new_id)
        
    while len(new_id) < 3:
        new_id = new_id + new_id[-1]
        
    return new_id
    
    
def solution(new_id):
    return convert(new_id)

def solution(s):
    return (len(s) == 4 or len(s) == 6) and s.isdigit()

import re

def solution(s):
    r4 = re.fullmatch(r"\d{4}", s)
    r6 = re.fullmatch(r"\d{6}", s)
     
    return r4 != None or r6 != None

def solution(s):
    answer = True
    if not (len(s) == 6 or len(s) == 4):
        return False
    if(not s.isdigit()):
        answer = False

    return answer

def solution(s):
    answer = True
    
    if(not s.isdigit()):
        answer = False

    return answer

def solution(s):
    s_list = list(s)
    if not (len(s) == 6 or len(s) == 4):
        return False
    
    for c in s_list:
        if (not c.isdigit()):
            return False
    return True

def solution(s):
    if len(s) != 4 and len(s) != 6:
        return False
    for c in s:
        if c.isalpha():
            return False
    return True

import re
def solution(s):
    if len(s) != 4 and len(s) != 6:
        return False
    
    if re.compile('^[\d]+$').match(s) == None:
        return False
    
    return True

def solution(phone_number):
    return (len(phone_number) - 4)*"*" + phone_number[-4:]

def solution(phone_number):
    answer = ''
    hidden = '*' * (len(phone_number)-4)
    answer = hidden + phone_number[-4:]
    return answer

def solution(phone_number):
    numbers = list(phone_number)
    for i in range(len(numbers) - 4):
        numbers[i] = "*"

    return "".join(numbers)

def solution(phone_number):
    num = len(phone_number)-4 # 가려야할 문자의 수
    answer = ''
    for i in range(len(phone_number)):
        if num > 0:
            answer += "*"
            num -= 1
        else:
            answer += phone_number[i]
    return answer

def solution(phone_number):
    return ''.join(['*' * (len(phone_number) - 4)]) + phone_number[-4:]

from itertools import combinations

def calculation(eq1, eq2):
    x1, y1, c1 = eq1 # 직선1
    x2, y2, c2 = eq2 # 직선2

    # 기울기가 깉아 해가 없는 경우
    if x1*y2 == y1*x2: 
        return

    # 두 직선의 해
    x = (y1*c2-c1*y2)/(x1*y2-y1*x2)
    y = (c1*x2-x1*c2)/(x1*y2-y1*x2)

    # 두 직선의 해 x, y가 모두 정수라면 반환
    if x == int(x) and y == int(y):
        return [int(x), int(y)]

def solution(lines):
    points = []
    # 모든 선들의 교점 확인
    for eq1, eq2 in combinations(lines, 2):
        point = calculation(eq1,eq2)
        if point:
            points.append(point)

    # 그림의 시작점과 마지막점 찾기
    w1, w2 = min(points, key = lambda x : x[0])[0], max(points, key = lambda x : x[0])[0] + 1
    h1, h2 = min(points, key = lambda x : x[1])[1], max(points, key = lambda x : x[1])[1] + 1

    # 별을 포함하는 최소한의 크기 배열 생성
    answer = [['.'] * (w2 - w1) for _ in range((h2 - h1))]

    # 그림의 시작점을 기준으로 교점 위치 "*" 변환
    for x, y in points:
        answer[y-h1][x-w1] = '*'

    return [''.join(a) for a in answer][::-1]

def solution(line):
    arr = []
    n = len(line)
    for i in range(n):
        a,b,e = line[i]
        for j in range(i+1,n):
            c,d,f = line[j]
            if a * d == b * c:
                continue
            x = (b * f - e * d)/(a * d - b * c)
            y = (e * c - a * f)/(a * d - b * c)
            
            if x == int(x) and y == int(y) and (x,y) not in arr:
                arr.append((int(x), int(y)))
                
    arr.sort(key = lambda x : x[0])
    min_x, max_x = arr[0][0], arr[-1][0]
    arr.sort(key = lambda x : x[1])
    min_y, max_y = arr[0][1], arr[-1][1]
    
    answer = [["."for j in range(max_x-min_x+1)] for i in range(max_y-min_y+1)]
    for x, y in arr : 
        answer[y-min_y][x-min_x] = "*"
    return [''.join(row) for row in answer[::-1]]

def solution(line):
    crossing =[]
    xmin= None
    xmax= None
    ymin= None
    ymax= None
    for i in range(len(line)-1):
        for j in range(i+1, len(line)):
            a, b, e = line[i]
            c, d, f = line[j]
            if a*d - b*c != 0:
                x = (b*f - e*d) / (a*d - b*c)
                y = (e*c - a*f) / (a*d - b*c)
                if x == int(x) and y == int(y):
                    x = int(x)
                    y = int(y)
                    xmin = min(x, xmin) if xmin!=None else x 
                    xmax = max(x, xmax) if xmax!=None else x
                    ymin = min(y, ymin) if ymin!=None else y
                    ymax = max(y, ymax) if ymax!=None else y
                    crossing.append([x,y])
    answer = [['.' for _ in range(xmax-xmin+1)] for _ in range(ymax-ymin+1)]
    for x, y in crossing:
        answer[ymax-y][x-xmin] = '*'
    return [''.join(row) for row in answer]

def cross_point(A, B, E, C, D, F):
    if A * D - B * C == 0:
        return False
    
    return ((B * F - E * D) / (A * D - B * C), (E * C - A * F) / (A * D - B * C))

def solution(line):
    result = []
    filtered_result = []
            
    for a in line:
        for b in line:
            if a == b:
                continue
            
            result.append(cross_point(*a, *b))
    
    for r in result:
        if r is False: 
            continue
        if int(r[0]) != r[0] or int(r[1]) != r[1]:
            continue
            
        filtered_result.append((int(r[0]), int(r[1])))
    
    x_min = None
    x_max = None
    y_min = None
    y_max = None
    
    for result in filtered_result:
        if x_min is None or x_min > result[0]:
            x_min = result[0]
        if x_max is None or x_max < result[0]:
            x_max = result[0]
        if y_min is None or y_min > result[1]:
            y_min = result[1]
        if y_max is None or y_max < result[1]:
            y_max = result[1]
            
    bitmap = [['.' for _ in range(0, x_max - x_min + 1)] for _ in range(0, y_max - y_min + 1)]
        
    for result in filtered_result:
        x = result[0] - x_min
        y = result[1] - y_min
              
        bitmap[y][x] = '*'
              
    
    return list(map(lambda l: ''.join(l), reversed(bitmap)))

def solution(rows, columns, queries):
    answer = []
    matrix = [[(i * columns) + (j + 1) for j in range(columns)] for i in range(rows)]

    for x1, y1, x2, y2 in queries:
        #다 읽어서 저장
        nums = []

        #좌상단부터 시계방향
        for ny in range(y1 - 1, y2 - 1):
            nums.append(matrix[x1 - 1][ny])
        for nx in range(x1 - 1, x2 - 1):
            nums.append(matrix[nx][y2 - 1])
        for ny in range(y2 - 1, y1 - 1, -1):
            nums.append(matrix[x2 - 1][ny])
        for nx in range(x2 - 1, x1 - 1, -1):
            nums.append(matrix[nx][y1 - 1])

        #밀어서 넣기
        matrix[x1 - 1][y1 - 1] = nums[len(nums) - 1]
        nums_idx = 0
        min_num = nums[len(nums) - 1]
        for ny in range(y1, y2 - 1):
            matrix[x1 - 1][ny] = nums[nums_idx]
            nums_idx += 1
            min_num = min_num if min_num < matrix[x1 - 1][ny] else matrix[x1 - 1][ny]
        for nx in range(x1 - 1, x2 - 1):
            matrix[nx][y2 - 1] = nums[nums_idx]
            nums_idx += 1
            min_num = min_num if min_num < matrix[nx][y2 - 1] else matrix[nx][y2 - 1]
        for ny in range(y2 - 1, y1 - 1, -1):
            matrix[x2 - 1][ny] = nums[nums_idx]
            nums_idx += 1
            min_num = min_num if min_num < matrix[x2 - 1][ny] else matrix[x2 - 1][ny]
        for nx in range(x2 - 1, x1 - 1, -1):
            matrix[nx][y1 - 1] = nums[nums_idx]
            nums_idx += 1
            min_num = min_num if min_num < matrix[nx][y1 - 1] else matrix[nx][y1 - 1]
        answer.append(min_num)
    return answer

def solution(rows, columns, queries):
    grid = [[0 for _ in range(columns)] for _ in range(rows)]
    answer = []

    n = 1
    for i in range(rows):
        for j in range(columns):
            grid[i][j] = n
            n += 1
    
    for qu in queries:
        start_row, start_col, end_row, end_col = [x-1 for x in qu]

        prev = grid[start_row][start_col]
        min_value = prev

        for col in range(start_col + 1, end_col + 1):
            grid[start_row][col], prev = prev, grid[start_row][col]
            min_value = min(min_value, prev)

        for row in range(start_row + 1, end_row + 1):
            grid[row][end_col], prev = prev, grid[row][end_col]
            min_value = min(min_value, prev)

        for col in range(end_col - 1, start_col - 1, -1):
            grid[end_row][col], prev = prev, grid[end_row][col]
            min_value = min(min_value, prev)

        for row in range(end_row - 1, start_row - 1, -1):
            grid[row][start_col], prev = prev, grid[row][start_col]
            min_value = min(min_value, prev)

        answer.append(min_value)
    
    return answer

def solution(rows, columns, queries):
    answer = []
    arr = []
    rowCnt = 0
    for i in range(0, rows):
        arr.append([])
        for j in range(0, columns):
            arr[i].append(i * columns + j + 1)
    
    for q in queries:
        q[0] -= 1
        q[1] -= 1
        q[2] -= 1
        q[3] -= 1
        
        # 행, 열
        leftTop = arr[q[0]][q[1]] 
        rightTop = arr[q[0]][q[3]]
        rightBottom = arr[q[2]][q[3]]
        leftBottom = arr[q[2]][q[1]]
        
        min = 10001
        for i in range(q[1], q[3] + 1):
            min = arr[q[0]][i] if arr[q[0]][i] < min else min
            min = arr[q[2]][i] if arr[q[2]][i] < min else min
        
        for i in range(q[0], q[2] + 1):
            min = arr[i][q[3]] if arr[i][q[3]] < min else min
            min = arr[i][q[1]] if arr[i][q[1]] < min else min
        answer.append(min)
            
            
        if(q[3] != q[1]):
            for i in range(q[3], q[1] + 1, -1):
                arr[q[0]][i] = arr[q[0]][i - 1]
            arr[q[0]][q[1] + 1] = leftTop
        
        
        if(q[2] != q[0]):
            for i in range(q[2], q[0] + 1, -1):
                arr[i][q[3]] = arr[i - 1][q[3]]
            arr[q[0] + 1][q[3]] = rightTop
        
        
        if(q[1] != q[3]):
            for i in range(q[1], q[3] - 1):
                arr[q[2]][i] = arr[q[2]][i + 1]
            arr[q[2]][q[3] - 1] = rightBottom
        
        
        if(q[0] != q[2]):
            for i in range(q[0], q[2] - 1):
                arr[i][q[1]] = arr[i + 1][q[1]]
            arr[q[2] -1][q[1]] = leftBottom
        
        
    print(arr)
    return answer

def solution(rows, columns, queries):
    answer = []
    grid={}
    for query in queries:
        rowMin, rowMax = min(query[0], query[2]), max(query[0], query[2])
        columnMin, columnMax = min(query[1], query[3]), max(query[1], query[3])
        minGridVal = None
        firstGridVal = None
        for i in range(rowMin, rowMax):
            val = grid.get((i+1,columnMin))
            if i is rowMin:
                firstGridVal = grid.get((i,columnMin))
            if val is None:
                val = ((i)*columns)+columnMin
            grid[(i,columnMin)] = val
            
            minGridVal = val if minGridVal is None else min(val, minGridVal)
        for i in range(columnMin, columnMax):
            val = grid.get((rowMax,i+1))
            if val is None:
                val = ((rowMax-1)*columns)+i+1
            grid[(rowMax,i)] = val
            minGridVal = min(val, minGridVal)
        for i in range(rowMax, rowMin, -1):
            val = grid.get((i-1,columnMax))
            if val is None:
                val = ((i-2)*columns)+columnMax
            grid[(i,columnMax)] = val
            minGridVal = min(val, minGridVal)
        for i in range(columnMax, columnMin, -1):
            if i is columnMin+1:
                val = firstGridVal
            else:
                val = grid.get((rowMin,i-1))
            if val is None:
                val = ((rowMin-1)*columns)+i-1
            grid[(rowMin,i)] = val
            minGridVal = min(val, minGridVal)                
        answer.append(minGridVal)
    return answer

def solution(rows, columns, queries):
    matrix_original = [[y * columns + x + 1 for x in range(columns)] for y in range(rows)]
    matrix_result = [[y * columns + x + 1 for x in range(columns)] for y in range(rows)]
    
    lowest_list = []
    
    
    for q in queries:
        y1, x1, y2, x2 = q
        
        y = y1 - 1
        next_num = matrix_result[y][x1 - 1]
        lowest = next_num
        
        for x in range(x1 - 1, x2 - 1):
            if next_num < lowest:
                lowest = next_num
                
            store = matrix_result[y][x + 1]
            matrix_result[y][x + 1] = next_num
            next_num = store
        
        x = x2 - 1
        for y in range(y1 - 1, y2 - 1):
            if next_num < lowest:
                lowest = next_num
                
            store = matrix_result[y + 1][x]
            matrix_result[y + 1][x] = next_num
            next_num = store
            
        y = y2 - 1
        for x in range(x2 - 1, x1 - 1, -1):
            if next_num < lowest:
                lowest = next_num
                
            store = matrix_result[y][x - 1]
            matrix_result[y][x - 1] = next_num
            next_num = store 
        
        x = x1 - 1
        for y in range(y2 - 1, y1 - 1, -1):
            if next_num < lowest:
                lowest = next_num
                
            store = matrix_result[y - 1][x]
            matrix_result[y - 1][x] = next_num
            next_num = store 
            
        lowest_list.append(lowest)
        
    return lowest_list

def solution(n):
    #크기에 맞게 리스트 생성
    result = [[0 for j in range(i + 1)] for i in range(n)]

    #초기값 설정
    num = 1
    for i in range(n):
        result[i][0] = num
        num+=1

    #초기값 설정 및 숫자 채우기 시작
    go = n-1
    state = 0
    x, y = n-1, 0
    while go > 0:
        for _ in range(go): #방향에 따라 좌표 이동
            if state%3 == 0:
                y+=1
            elif state%3 == 1:
                x-=1
                y-=1
            else:
                x+=1
            result[x][y] = num
            num+=1
        state+=1
        go-=1

    #평탄화 후 반환
    return sum(result, [])

def solution(n):
    answer = []
    arr = []
    dr = [1, 0, -1]
    dc = [0, 1, -1]
    
    
    for r in range(n):
        arr.append([])
        for c in range(r + 1):
            arr[r].append(0)
    
    cnt = 1
    r = 0
    c = 0
    angle = 0
    size = n * (n + 1) // 2
    
    while(cnt <= size):
        arr[r][c] = cnt
        nr = r + dr[angle]
        nc = c + dc[angle]
        cnt += 1
        
        if(0 <= nr < n and 0 <= nc <= nr and arr[nr][nc] == 0):
            r, c = nr, nc
        else:
            angle = (angle + 1)%3
            r += dr[angle]
            c += dc[angle]
        
    for row in arr:
        for e in row:
            answer.append(e)
            
    return answer

def solution(n):
    triangle = [[0] * (i + 1) for i in range(n)]
    
    x,y = 0,-1
    
    n = len(triangle)
    value = 1
    for i in range(n):
        for _ in range(i, n):
            if i % 3 == 0:
                y += 1
            elif i % 3 == 1:
                x += 1
            else:
                x -= 1
                y -= 1
            triangle[y][x] = value
            value += 1
    return sum(triangle,[])

def solution(n):
    size = n * (n + 1) // 2
    answer = [0] * size
    present_val = 1
    x, y = 0, 0
    whereToGo = 0  #0 is go down diagonal 1 is go right 2 is go up diagonal 
    dx = [1, 0, -1] # x direction
    dy = [0, 1, -1]

    for i in range(1, n + 1):
        for _ in range(n - i + 1):
            index = x * (x + 1) // 2 + y
            answer[index] = present_val
            present_val += 1
            if _ == n - i:
                whereToGo = (whereToGo + 1) % 3
            x += dx[whereToGo]
            y += dy[whereToGo]

    return answer

def solution(n):
    def is_pos_ok(x, y, arr):
        if x >= len(arr) or x > y:
            return False
        if y >= len(arr):
            return False

        if arr[y][x] != None:
            return False

        return True

    arr = [[None for _ in range(n)] for _ in range(n)]
    arr[0][0] = 1
    x, y = (0, 0)

    mode = "DOWN"
    idx = 1

    while True:
        if mode == "DOWN":
            if is_pos_ok(x, y + 1, arr):
                y += 1
                idx += 1
            else:
                if is_pos_ok(x + 1, y, arr) is False:
                    break
                mode = "RIGHT"

        elif mode == "RIGHT":
            if is_pos_ok(x + 1, y, arr):
                x += 1
                idx += 1
            else:
                if is_pos_ok(x - 1, y - 1, arr) is False:
                    break
                mode = "SLASH"

        elif mode == "SLASH":
            if is_pos_ok(x - 1, y - 1, arr):
                x -= 1
                y -= 1
                idx += 1
            else:
                if is_pos_ok(x, y + 1, arr) is False:
                    break

                mode = "DOWN"

        arr[y][x] = idx

    result = []
    for i in range(len(arr)):
        for j in range(i + 1):
            result.append(arr[i][j])

    return result

def solution(places):
    def checkCondition(k, x, y):
        len1 = [[0, 1, 0, -1], [1, 0, -1, 0]]
        len2_1 = [[0, 2, 0, -2], [2, 0, -2, 0]]
        len2_2 = [[1, 1, -1, -1], [1, -1, -1, 1]]

        for i in range(4):
            nx = x + len1[0][i]
            ny = y + len1[1][i]

            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
                continue
            if places[k][nx][ny] == "P":
                return False

            nx = x + len2_1[0][i]
            ny = y + len2_1[1][i]

            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
                continue
            if places[k][nx][ny] == "P" and places[k][(x + nx) // 2][(y + ny) // 2] == "O":
                return False

            nx = x + len2_2[0][i]
            ny = y + len2_2[1][i]

            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
                continue
            if places[k][nx][ny] == "P":
                if places[k][x + len1[0][i]][y + len1[1][i]] == "O" or places[k][x + len1[0][(i + 1) % 4]][y + len1[1][(i + 1) % 4]] == "O":
                    return False
        return True

    result = []
    for k in range(5):
        flag = True
        for i in range(5):
            if flag == False:
                break
            for j in range(5):
                if places[k][i][j] != "P":
                    continue
                if checkCondition(k, i, j) == False:
                    flag = False
                    break
        result.append(1 if flag else 0)

    return result

def solution(places):
    def is_valid_place(place):
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    if j + 1 < 5 and place[i][j + 1] == 'P':
                        return False
                    if i + 1 < 5 and place[i + 1][j] == 'P':
                        return False
                    if i + 1 < 5 and j + 1 < 5 and place[i + 1][j + 1] == 'P':
                        if place[i + 1][j] == 'O' or place[i][j + 1] == 'O':
                            return False
                    if i + 1 < 5 and j - 1 >= 0 and place[i + 1][j - 1] == 'P':
                        if place[i + 1][j] == 'O' or place[i][j - 1] == 'O':
                            return False
                    if j + 2 < 5 and place[i][j + 2] == 'P' and place[i][j + 1] == 'O':
                        return False
                    if i + 2 < 5 and place[i + 2][j] == 'P' and place[i + 1][j] == 'O':
                        return False
        return True

    answer = []
    for place in places:
        if is_valid_place(place):
            answer.append(1)
        else:
            answer.append(0)
    return answer

def solution(places):
    answer= []
    for place in places:
        if checkCol(place) == 0:
            answer.append(0)
            continue
        if checkRow(place) == 0:
            answer.append(0)
            continue
        if checkDiagonal(place) == 0:
            answer.append(0)
            continue
        answer.append(1)
    return answer 

def checkCol(place):
    for i in range(5):
            if 'POP' in place[i] or 'PP' in place[i]:
                return 0
    return 1

def checkRow(place):
    for i in range(5):
        row = ''
        for j in range(5):
            row += place[j][i]
        if 'POP' in row or 'PP' in row:
            return 0
    return 1
def checkDiagonal(place):
    for i in range(4):
        for j in range(5):
            if place[i][j] == 'P':
                if j<4 and  place[i+1][j+1] == 'P':
                        if place[i+1][j] == 'O' or place[i][j+1] == 'O':
                            return 0
                if j>0:
                    if place[i+1][j-1] == 'P':
                        if place[i+1][j] == 'O' or place[i][j-1] == 'O':
                            return 0
    return 1

def getDistance(r1, c1, r2, c2):
    return abs(r1 - r2) + abs(c1 - c2)

def isOkay(place):
    for x in range(5):
        for y in range(5):
            if place[y][x] != 'P':
                continue
                
            can_left = x > 0
            can_right = x < 4
            can_up = y > 0
            can_down = y < 4
            
            if x > 1 and place[y][x - 1] == 'O' and place[y][x - 2] == 'P':
                return 0
            if x < 3 and place[y][x + 1] == 'O' and place[y][x + 2] == 'P':
                return 0
            if y > 1 and place[y - 1][x] == 'O' and place[y - 2][x] == 'P':
                return 0
            if y < 3 and place[y + 1][x] == 'O' and place[y + 2][x] == 'P':
                return 0
            
            if can_left and place[y][x - 1] == 'P':
                return 0

            if can_up and place[y - 1][x] == 'P':
                return 0

            if can_left and can_up:
                if place[y][x - 1] == 'O' and place[y - 1][x - 1] == 'P':
                    return 0
                if place[y - 1][x] == 'O' and place[y - 1][x - 1] == 'P':
                    return 0

            if can_right and place[y][x + 1] == 'P':
                return 0

            if can_right and can_up:
                if place[y][x + 1] == 'O' and place[y - 1][x + 1] == 'P':
                    return 0
                if place[y - 1][x] == 'O' and place[y - 1][x + 1] == 'P':
                    return 0

            if can_down and place[y + 1][x] == 'P':
                return 0

            if can_left and can_down:
                if place[y][x - 1] == 'O' and place[y + 1][x - 1] == 'P':
                    return 0
                if place[y + 1][x] == 'O' and place[y + 1][x - 1] == 'P':
                    return 0

            if can_right and can_down:
                if place[y][x + 1] == 'O' and place[y + 1][x + 1] == 'P':
                    return 0
                if place[y + 1][x] == 'O' and place[y + 1][x + 1] == 'P':
                    return 0

    return 1
    
def solution(places):
    return list(map(isOkay, places))

def bfs_init(x, y, place):
    x_org, y_org = x, y
    queue = []
    
    def bfs(x, y, distance):
        if x == x_org and y == y_org:
            return True
        
        if distance >= 2 or x < 0 or x > 4 or y < 0 or y > 4:
            return True
        
        if place[y][x] == 'P':
            return False
        
        if place[y][x] == 'X':
            return True
        
        if place[y][x] == 'O':
            queue.append((x - 1, y, distance + 1))
            queue.append((x + 1, y, distance + 1))
            queue.append((x, y - 1, distance + 1))
            queue.append((x, y + 1, distance + 1))
            
            
    
    if place[y][x] != 'P':
        return True

    queue.append((x - 1, y, 0))
    queue.append((x + 1, y, 0))
    queue.append((x, y - 1, 0))
    queue.append((x, y + 1, 0))
    
    while len(queue) > 0:
        cur = queue.pop(0)
        
        if bfs(*cur) is False:
            return 0
        
    return 1

def place(place):
    for x in range(5):
        for y in range(5):
            if bfs_init(x, y, place) == 0:
                return 0
            
    return 1
    
    
def solution(places):
    result = []
    for p in places:
        result.append(place(p))
    
    
    return result

def solution(arr1, arr2):
    n, m, p = len(arr1), len(arr2), len(arr2[0])
    answer = [[0 for j in range(p)] for i in range(n)]

    for i in range(n):
        for j in range(p):
            for k in range(m):
                answer[i][j] += arr1[i][k] * arr2[k][j]

    return answer

def solution(arr1, arr2):
    n, m = len(arr1), len(arr2[0])
    answer = [[0 for _ in range(m)] for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            for k in range(len(arr2)):
                answer[i][j] += arr1[i][k] * arr2[k][j]
    return answer

def solution(arr1, arr2):
    answer = []
    rowCnt = len(arr1)
    colCnt = len(arr2[0])
    cnt = len(arr1[0])
    
    for r in range(0, rowCnt):
        answer.append([])
        for c in range(0, colCnt):
            sum = 0
            for i in range(0, cnt):
                sum += arr1[r][i] * arr2[i][c] 
            answer[r].append(sum)
    
    return answer

def solution(arr1, arr2):
    answer = []
    for arr1Col in arr1:
        answerCol = []
        for arr2Row in zip(*arr2):
            answerCol.append(sum([a*b for a,b in zip(arr1Col, arr2Row)]))
        answer.append(answerCol)
    return answer

def solution(arr1, arr2):
    multiply_len = len(arr2)
    
    result = [[0 for _ in range(len(arr2[0]))] for _ in range(len(arr1))]
    
    for y1 in range(len(arr1)):
        for x2 in range(len(arr2[0])):
            s = 0
            
            for x1 in range(len(arr1[0])):
                s += arr1[y1][x1] * arr2[x1][x2]

            result[y1][x2] = s
            
    return result