inspirit941

def solution(budgets, M):
    mins, maxs = 0, max(budgets)
    answer = 0
    while mins <= maxs:
        mid = (mins + maxs) // 2
        temp = [i if i < mid else mid for i in budgets]
        if sum(temp) > M:
            maxs = mid - 1
        elif sum(temp) <= M:
            answer = mid

inspirit941

import sys
from collections import defaultdict
nations = sys.stdin.readline().split()
percentage = defaultdict(int)
expected_score = defaultdict(int)
schedule = []
for _ in range(3):
    temp = []
    for _ in range(2):
        temp.append(sys.stdin.readline().split())

inspirit941

cities = int(input())
_ = int(input())
parent = {i:i for i in range(1, cities+1)}
def parent_find(x):
    if x == parent[x]:
        return x
    p = parent_find(parent[x])
    parent[x] = p
    return parent[x]

inspirit941

import sys
import math
from collections import deque, defaultdict
r, c = map(int, sys.stdin.readline().split())
maps = []
for _ in range(r):
    maps.append(list(map(int, sys.stdin.readline().split())))

# 1. 각 섬별로 라벨링하기.
def bfs(start, maps, continent_name):

inspirit941

import sys
from collections import deque, defaultdict
r, c = map(int, sys.stdin.readline().split())
maps = []
for _ in range(r):
    maps.append(list(map(int, sys.stdin.readline().split())))

def bfs(start, maps, visited):   
    ice = defaultdict(int)
    queue = deque()

inspirit941

import sys
arr = list(sys.stdin.readline())
stack = []
answer = 0
prev = None

for i in range(len(arr)):
    if arr[i] == '(':
        stack.append(arr[i])
    elif prev == '(' and arr[i] == ')':

inspirit941

import sys
sys.stdin = open('input.txt')
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
answer = [0 for _ in range(len(arr))]
stack = []

for i in range(len(arr)-1, -1, -1):
    while stack and arr[stack[-1]] < arr[i]:
        answer[stack.pop()] = i+1

inspirit941

import sys
from collections import Counter
r, c, k = map(int, sys.stdin.readline().split())
maps = []
for _ in range(3):
    temp = list(map(int, sys.stdin.readline().split()))
    maps.append(temp)

time = 0
find = False

inspirit941

import sys
from copy import deepcopy
import math
n, m = map(int, sys.stdin.readline().split())
maps = []
cctvs = []
for y in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    for x in range(m):
        if 1 <= temp[x] <= 5:

inspirit941

from collections import defaultdict
import copy
def dfs(start, table, arr, result, n_tickets):
    # 이동한 경로를 저장함
    arr.append(start)
    for i in range(len(table[start])):
        # 이미 방문했으면 건너뛴다
        if table[start][i] == True:
            continue
        else: