Baekjoon Lv.2

def push(bracket):
    global top
    if top < 100:
        top += 1
        stack[top] = bracket # def 밖에서 괄호를 가려 받게 했으므로 push에 따로 조건걸 필요 X

def small_pop():
    global top
    global nope
    if top == -1:
        nope = True
        return

    if stack[top] == '(':
        top -= 1 # 여는 괄호와 일치하면 균형하므로 top -1
    else:
        nope = True # 아님 불균형

def big_pop():
    global top
    global nope
    if top == -1:
        nope = True
        return

    if stack[top] == '[':
        top -= 1 # 여는 괄호와 일치하면 균형하므로 top -1
    else:
        nope = True # 아님 불균형

while True:
    word_line = input() # 한줄씩 입력
    stack = [0] * 101 # 100칸을 넘는 경우가 없다고 했으므로...
    top = -1
    nope = False

    if word_line == '.':
        break  # . 이 나오면 break.

    for i in word_line:
        if i == '(' or i == '[':
            push(i) # 새로운 여는 괄호면 스택에 추가
        elif i == ')':
            small_pop() # 소괄호 판독기
        elif i == ']':
            big_pop() # 대괄호 판독기

    if top != -1:
        nope = True # top이 남아있으면 불균형함

    if nope == True:
        print('no') # 불균형하면 no 출력
        nope = False
    else:
        print('yes') # 균형이면 yes 출력
        nope = False

def stack_machine(par_text):

    global answer, top

    if par_text == '(': # 만약 여는 괄호라면
        stack.append(par_text) # 스택에 추가
        top += 1 # 스택의 제일 높은 위치 갱신
        return answer
    elif par_text == ')': # 만약 닫는 괄호라면
        if top < 0: # 스택이 비어있는데 추가할려하면 불균형 하므로 No 리턴
            answer = 'NO'
            return answer
        else: # 스택이 있다면
            stack.pop() # 꺼내고
            top -= 1 # 제일 높은 위치 갱신
            return answer

testcase = int(input())

for _ in range(testcase):
    par_input = input()

    stack = [] # 초기 설정: stack
    top = -1  # 초기 설정: top
    answer = 'YES' # 초기 설정: answer

    for i in par_input:
        answer = stack_machine(i) # 답 입력 받음, def 호출
        if answer == 'NO': # 이미 NO로 판단되었다면 break.
            break

    if top != -1: # 스택이 남아있다면 불균형하므로 NO
        answer = 'NO'

    print(answer)

import sys

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

stack = []
for _ in range(testcase):
    input_commend = sys.stdin.readline().split()

    if input_commend[0] == 'pop':
        if len(stack) < 1:
            print('-1')  # 없으면 -1
        else:
            print(stack.pop())  # 있으면 그 값을 pop 하고 top -1
    elif input_commend[0] == 'size':
        print(len(stack))  # 현재 사이즈는 top+1(top은 현재 스택 제일 윗값의 인덱스(주소값)이므로 항상 1이 적다. 따라서 1 더하면 지금 현재 저장값이다)
    elif input_commend[0] == 'empty':
        if len(stack) == 0:
            print('1')  # 비어있으면 1
        else:
            print('0')  # 뭔가 있으면 0
    elif input_commend[0] == 'top':
        if len(stack) < 1:
            print('-1')  # 없으면 -1
        else:
            print(stack[len(stack)-1])  # 스택의 탑값을 인덱스로 불러와서 출력
    else:
        stack.append(input_commend[1])  # push 하고 top +1

import sys
from collections import deque

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

que_list = deque([])

for _ in range(testcase):
    commend_input = sys.stdin.readline().split()

    if commend_input[0] == 'pop':
        if len(que_list) < 1: # 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
            print('-1')
        else: # 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다.
            print(que_list.popleft())
    elif commend_input[0] == 'size': # 큐에 들어있는 정수의 개수를 출력한다.
        print(len(que_list))
    elif commend_input[0] == 'empty':
        if len(que_list) < 1:
            print('1') # 큐가 비어있으면 1
        else:
            print('0') # 아니면 0을 출력한다.
    elif commend_input[0] == 'front': # 큐의 가장 앞에 있는 정수를 출력한다.
        if len(que_list) < 1: # 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
            print('-1')
        else:
            print(que_list[0])
    elif commend_input[0] == 'back': # 큐의 가장 뒤에 있는 정수를 출력한다
        if len(que_list) < 1: # 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
            print('-1')
        else:
            print(que_list[len(que_list)-1])
    else:
        que_list.append(commend_input[1]) # 정수 X를 큐에 넣는 연산이다.

def dfs(edge_graph_list, v, visited):
    visited[v] = True # 방문했으니 True로 바꿈
    for i in edge_graph_list[v]:
        if not visited[i]: # 해당 노드에 방문하지 않았다면...
            dfs(edge_graph_list, i, visited) # 그 노드를 기준으로 다시 dfs 실행(재귀)

node_num = int(input())

edge_num = int(input())

edge_graph_list = [[] for _ in range(node_num + 1)] # 그래프 초기화

for _ in range(edge_num): # 엣지 입력
    a, b = list(map(int, input().split()))
    edge_graph_list[a].append(b)
    edge_graph_list[b].append(a) # 양방향 연결

visited = [False] * (node_num + 1) # visit 노드의 수는 공백인 0을 제외시킬거라 총 길이 +1 을 한다.
infected_pc = 0 # 감염된 pc 수

dfs(edge_graph_list, 1, visited) # 1번 pc가 고정 감염 숙주이므로 여기서부터 시작.

for i in range(len(visited)):
    if visited[i] == True:
        infected_pc += 1 # 감염된 상태라면 변수에 +1

print(infected_pc - 1) # 1번 컴퓨터는 최초 숙주이므로 바이러스에 걸리게되는 컴퓨터 수에서 제외

from collections import deque

player = int(input())  # 플레이어 수
apartment_game = int(input())  # 아파트 게임 횟수
hand_position = list(map(int, input().split()))  # 손 위치
gyosun = list(map(int, input().split()))  # 사실상 이게 게임 횟수(교선이가 부른 수)

lose_people = []

game_start_position = deque(hand_position) # 게임 시작 직후 포지션
for i in gyosun: # 게임 시작
    for j in range(1, i): # 3이라 불렀으면 1, 2, 3 게임을 함
        game_start_position.append(game_start_position.popleft()) # 맨 아랫손을 꺼내서 맨 위로 둠
    lose_people.append(game_start_position[0]) # 3을 부를때 맨 아랫자리에 있는 사람이 패배 그래서 i+1이 아니다.

print(*lose_people) # 진 사람 언패킹해서 출력

import sys

command_num = int(sys.stdin.readline()) # 명령 갯수

stack = [] # 스택
top = -1 # 스택의 가장 윗 값 인덱스

for cn_idx in range(1, command_num+1):
    command_input = list(sys.stdin.readline().split()) # 명령 입력

    if command_input[0] == '2': # 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
        if top == -1:
            print(-1)
        else:
            print(stack.pop())
            top -= 1
    elif command_input[0] == '3': # 3: 스택에 들어있는 정수의 개수를 출력한다.
        print(len(stack))
    elif command_input[0] == '4': # 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
        if top == -1:
            print(1)
        else:
            print(0)
    elif command_input[0] == '5': # 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.
        if top == -1:
            print(-1)
        else:
            print(stack[len(stack)-1])
    else: #  X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
        stack.append(command_input[1])
        top +=1

from collections import deque
import sys

member_num = int(sys.stdin.readline()) # 전체 줄 서있는 사람 수

# 대기 줄 리스트, 대기줄에서는 맨 앞사람이 나가야하므로, deque를 활용해보기로 하였음.
mem_list = deque(map(int, sys.stdin.readline().split()))

enter_num = 1 # 다음에 들어갈 사람을 알려주는 index 번호

waiting_num = -1 # 대기 zone index 번호(top 역할)
waiting_list = [] # 대기 zone 구역 리스트

escape_code = 0 # 반복문 탈출용

while True:
    if waiting_list:  # waiting zone에 사람이 있다면
        escape_code += 1 # 여기 if문 지나감
        if waiting_list[waiting_num] == enter_num:  # 만약 제일 뒤에 있는 사람이 입장 번호랑 같다면...
            waiting_list.pop()  # 빼고 입장시키기
            waiting_num -= 1  # 대기 top -1
            enter_num += 1  # 다음 번호 호출
            escape_code = 0
            continue

    if mem_list: # 본래 줄에 사람이 있다면
        escape_code += 1 # 여기 if문 지나감
        if mem_list[0] == enter_num: # 줄에 맨 앞에 서있는 번호가 들어가야할 번호랑 같다면...
            mem_list.popleft() # mem_list에서 제거하고, entered_list에 추가
            enter_num += 1 # 다음 번호 호출
            escape_code = 0
            continue

        elif mem_list[0] != enter_num: # 줄에 맨 앞에 서있는 번호가 들어가야할 번호랑 다르다면
            waiting_list.append(mem_list.popleft())  # 아닐 시 waiting_list 추가
            waiting_num += 1  # 대기 top +1
            escape_code = 0
            continue

    if not mem_list and not waiting_list : # 전부 제대로 받았다면
        break

    if escape_code == member_num: # 전부 제대로 받을 수 없는 상태라면
        break

if enter_num - 1 == member_num: # 만약 전부 제대로 받았다면
    print('Nice')
else: # 만약 전부 제대로 받을 수 없는 상태라면, 만약 mem_list에 없는데도 waiting_list 만 있는 경우를 고려한 코드
    print('Sad')

from collections import deque

people_len, delete_num = map(int, input().split()) # 전체 인원수, 삭제시킬 단위 숫자

josephus_que = deque() # 큐 선언

answer = [] # 빈 정답 리스트

for i in range(1, people_len + 1):
    josephus_que.append(str(i)) # 요세푸스 맵 제작

index = delete_num - 1 # 인덱스는 -1해야 정답.

while josephus_que: # 큐가 전부 없어질때 까지 반복
    for _ in range(index):
        josephus_que.append(josephus_que.popleft()) # pop 시킬 지점까지 원형 큐 형태 사용.
    answer.append(josephus_que.popleft()) # 삭제시킬 지점이 오면 answer로 pop시키기.

answer = ', '.join(answer) # 출력 형식을 맞추기 위한 언패킹

print(f'<{answer}>')

from collections import deque

testcase = int(input())

for tc_idx in range(1, testcase + 1):
    total_page, target_page = map(int, input().split()) # 총 페이지 수와 목표 페이지 수를 받음
    print_list = deque(map(int, input().split())) # 프린트 대기 내역을 queue로 받음
    print_cnt = 0 # 지금까지 출력한 양을 기록할 변수

    while True: # 목표치에 닿을때까지 무한 반복
        if print_list[0] < max(print_list): # 만약 우선순위가 더 높은게 있다면
            print_list.append(print_list.popleft()) # 뒷 순서로 미룬다.
            if target_page == 0: # 만약 지금 페이지가 목표 페이지 였다면
                target_page += len(print_list) - 1 # 밀려난 만큼 인덱스도 재지정한다.
            else: # 아니라면
                target_page -= 1 # 앞으로 순서가 당겨졌을테니 1씩 감소시킨다.
        else: # 만약 우선순위가 더 높은게 없다면(즉, 출력해야한다면)
            if target_page == 0: # 만약 목표 페이지라면
                print_list.popleft() # 출력하고
                print_cnt += 1 # 프린트 수에 1 추가 후
                break # 반복문을 종료시킨다.
            print_list.popleft() # 아니라면, 출력하고
            target_page -= 1 # 순서가 당겨졌으니 1 마이너스 하고
            print_cnt += 1 # 프린트 수에 1 추가한다.

    print(print_cnt)

def solve(start):
    global cnt
    visited[start] = 1 # 현재 방문한 돌다리를 1로 바꾼다.
    if start + jump_len[start] < len(jump_len) and visited[start + jump_len[start]] != 1: # 오른쪽 돌로 가게 만드는 if문
        cnt += 1 # 방문 돌 갯수 추가
        solve(start + jump_len[start]) # 재귀로 다음 방문할 돌 찾기
    if start - jump_len[start] > -1 and visited[start - jump_len[start]] != 1: # 왼쪽 돌로 가게 만드는 if문
        cnt += 1 # 방문 돌 갯수 추가
        solve(start - jump_len[start]) # 재귀로 다음 방문할 돌 찾기
    return # 더 이상 갈 수 있는 돌이 없거나 방문할 돌이 없다면 return


stone_bridge = int(input()) # 돌다리 갯수
jump_len = list(map(int, input().split())) # 돌다리당 표시된 점프 거리
start = int(input()) - 1 # 시작지점. 인덱스로 쓰일거라 -1 처리

cnt = 1 # 방문한 돌 갯수. 무조건 시작점인 첫번째 돌다리는 건넌다.

visited = [0] * stone_bridge # 방문한 돌다리 확인용

solve(start) # def 호출

print(cnt)

import sys

white_square = [[0] * 101 for _ in range(101)] # 백지장 제작, 101로 설정한 이유는 0인덱스 줄,칸은 안 쓸 예정이라서.
square_num = int(sys.stdin.readline()) # 사각형 갯수
cnt = 0 # 값 변수

for s_num in range(square_num): # 사각형 갯수만큼 반복
    x_start, y_start = map(int, sys.stdin.readline().split()) # X축, Y축 시작점 입력
    for i in range(y_start, y_start+10): # 사각형은 10칸씩 ( 세로 )
        for j in range(x_start, x_start+10): # 사각형은 10칸씩 ( 가로 )
            white_square[i][j] = 1 # 해당 칸은 1로 입력

for i in range(1, 101):
    for j in range(1, 101):
        if white_square[i][j] == 1: # 만약 해당 칸이 1이었다면,
            cnt += 1 # 색칠된 칸 수 1 추가

print(cnt)

import sys

def dfs(start):
    global cnt
    visited[start] = 1 # 도착한 곳에 1 추가.
    if visited[indexed_list[start]] == 1: # 만약 순환순열이 끝났다면 cnt를 1 추가하고 멈춘다.
        cnt += 1
        return
    else:
        dfs(indexed_list[start]) # 재귀하여 순열을 완성환다.


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

for tc_idx in range(1, testcase + 1):
    num_len = int(sys.stdin.readline())
    num_list = list(map(int, sys.stdin.readline().split()))
    indexed_list = [x - 1 for x in num_list] # num_list에서 입력받은 값들을 전부 index 값에 맞게 변환시켜준다.
    visited = [0] * num_len # DFS를 위한 visited 정의

    cnt = 0  # 순환하는 순열의 갯수를 저장하는 변수.  즉, 이 문제의 답.

    for i in range(len(indexed_list)):
        if visited[i] == 0: # 1이면 그 변수는 시작지점이 아니므로 패스
            dfs(i) # dfs def 호출

    print(cnt)

from collections import deque


def dfs(start_dfs):
    dfs_result.append(start_dfs) # 현재 노드 리스트에 추가
    visited_dfs[start_dfs] = 1 # 방문한 노드의 visited 주소를 1로 변경
    for i in node_map_list[start_dfs]: # node_map_list에서 다음 노드로 갈 좌표를 찾기
        if visited_dfs[i] == 0: # 만약 해당 노드가 방문한 적 없는 노드라면
            dfs(i) # 재귀한다.


def bfs(start_bfs):
    bfs_deque = deque() # 빈 덱 생성
    bfs_deque.append(start_bfs) # 현재 위치를 덱에 추가
    visited_bfs[start_bfs] = 1 # 방문한 노드의 visited 주소를 1로 변경
    while bfs_deque: # 덱이 계속 존재하는 한 반복됨
        current = bfs_deque.popleft() # 현 위치를 popleft해서 받음
        bfs_result.append(current) # 그리고 현 노드를 리스트에 추가
        for i in node_map_list[current]: # node_map_list에서 다음 노드로 갈 좌표를 찾기
            if visited_bfs[i] == 0: # 만약 방문한 적 없는 노드라면
                visited_bfs[i] = 1 # 해당 노드를 방문처리하고
                bfs_deque.append(i) # deque에 append한다.


node_num, edge_num, start_node = map(int, input().split())

node_map_list = [[] for _ in range(node_num + 1)]  # 빈 리스트를 만든다. +1을 한 이유는 0번째 칸을 쓰지않음으로서 인덱스와 일치시키기 위함

for _ in range(edge_num):
    start, end = map(int, input().split())  # 시작지점 종료지점을 각각 입력
    node_map_list[start].append(end)
    node_map_list[end].append(start)  # 양방향 에지 설정

for i in range(node_num + 1):
    node_map_list[i].sort()  # 내림 차순으로 정렬

visited_dfs = [0] * (node_num + 1) # dfs의 방문 리스트를 만든다
dfs_result = [] # 출력 저장용으로 빈 리스트 제작
dfs(start_node) # def 호출

print(*dfs_result) # 형변환 한 후 출력

visited_bfs = [0] * (node_num + 1) # bfs의 방문 리스트를 만든다.
bfs_result = [] # 출력 저장용으로 빈 리스트를 제작
bfs(start_node) # def 호출

print(*bfs_result) # 형변환 후 출력

import sys
sys.setrecursionlimit(10**6) # 재귀 허용 용량을 늘린다.

def delta_worm(start_x, start_y): # 지렁이가 투입될 장소 주변에 양배추가 추가로 더 있는지 확인하기 위한 def
    visited[start_y][start_x] = 1 # 일단 그 장소에 양배추가 심어져 있으니 방문했다 치고,

    delta_x = [1, -1, 0, 0]
    delta_y = [0, 0, 1, -1] # 델타 탐색을 위한 좌표 0 - 오른쪽, 1 - 왼쪽, 2 - 위쪽, 3 - 아래쪽

    for dir in range(4): # 네 방향 확인
        if start_x + delta_x[dir] >= 0 and start_x + delta_x[dir] < len_x and start_y + delta_y[dir] >= 0 and start_y + delta_y[dir] < len_y: # 리스트를 벗어나지 마렴.
            new_x = start_x + delta_x[dir] # 탐색할 x 좌표
            new_y = start_y + delta_y[dir] # 탐색할 y 좌표
            if cab_map[new_y][new_x] == 1 and visited[new_y][new_x] == 0: # 만약 해당 좌표에 양배추가 있고 방문한 적이 없다면,
                delta_worm(new_x, new_y) # 그 좌표를 중심점을 바꾸고 재귀한다.

testcase = int(sys.stdin.readline()) # 테스트 케이스 입력

for _ in range(1, testcase + 1): # 이 문제는 테스트 케이스를 따로 출력할 필요가 없으므로 _ 로 지정한다.
    len_x, len_y, cab_num = map(int, sys.stdin.readline().split()) # 배추밭의 가로갈이, 배추밭의 세로길이, 양배추 갯수
    cab_map = [[0] * len_x for _ in range(len_y)] # 양배추 지도
    visited = [[0] * len_x for _ in range(len_y)] # 방문 여부 지도

    for i in range(cab_num): # 양배추를 심어보자
        cab_x, cab_y = map(int, sys.stdin.readline().split()) # 양배추의 좌표를 입력
        cab_map[cab_y][cab_x] = 1 # 그 좌표에 양배추 심기(1 넣기)

    cnt = 0 # 필요한 지렁이의 갯수를 저장할 변수

    for y in range(len_y):
        for x in range(len_x):
            if visited[y][x] == 0 and cab_map[y][x] == 1: # 만약 방문한 적이 없고 양배추가 심어져 있다면
                delta_worm(x, y) # def 호출
                cnt += 1 # 지렁이 필요 갯수 1 추가

    print(cnt) # 결과 출력

import sys

def solve(current_num):
    global cnt, min_cnt

    if current_num > end: # 만약 재귀를 통하여 값이 end 값보다 높아지면 안 되므로 높아지는 즉시 return처리한다.
        return

    if current_num == end: # 만약 원하는 값이 되었을 떄
        if cnt < min_cnt: # min_cnt값이 현 cnt값보다 높은경우
            min_cnt = cnt # 그 값으로 교체한 후 return한다.
            return

    cnt += 1 # 재귀를 한번 시킬때마다 1씩 더하고
    one_add = int(str(current_num)+str(1)) # 오른쪽에 1을 계속 붙이는 경우 str로 형변환 시켜서 진행하면 편하다.
    solve(one_add) # 이 재귀는 끝자리에 1을 더한 경우의 재귀
    cnt -= 1 # return 되었다면 cnt를 다시 -1 한다. 잘못된 재귀를 취소처리하였으니.

    cnt += 1 # 다시 1을 더하고
    solve(current_num*2) # 2를 곱한 값으로 재귀한다.
    cnt -= 1 # 그래도 없으면 위와 같은 이유로 cnt를 -1한다.


start, end = map(int, sys.stdin.readline().split()) # 시작값과 끝값을 받는다.

cnt = 1 # A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다...라는데 그냥 1부터 시작하면 된다.

min_cnt = 0xfffff # 셀수없는 최댓값을 무작위로 작성하였다.

solve(start) # 재귀 def 시작

if min_cnt == 0xfffff : # 만약 min_cnt 값이 변하지 않았다면,
    print(-1) # 그건 구할 수 없는 값이었으므로 -1로 출력한다.
else: # 그리고 답이 구해졌다면,
    print(min_cnt) # 그 min_cnt의 값을 출력한다.

import sys

input_num, min_len = map(int, sys.stdin.readline().split())

word_dict = {}

final_list = [] # 마지막 값을 저장하는 리스트

for i in range(input_num):
    input_word = input()
    if len(input_word) < min_len: # 만약 이 단어가 최소 요건 길이보다 짧다면
        pass # 무시
    elif input_word in word_dict: # 만약 dict안에 해당 값이 있다면
        word_dict[input_word] += 1 # value를 +1 한다.
    else: # 없다면
        word_dict[input_word] = 1 # 해당 key를 추가한다.

# 람다식을 이용해 정렬한다. 람다식에서 '-' 를 붙히면 내림차순으로 정렬된다.
sorted_list = sorted(word_dict.items(), key=lambda words: (-words[1], -len(words[0]), words[0]))

for i in sorted_list:
    print(i[0])

def checkboard(start_y, start_x):
    now_word = 'W' # 첫 케이스를 W로 정했을떄
    cnt = 0

    for i in range(start_y, start_y+8):
        if now_word == 'B': # 다음 체스판을 옮겨갔을때 B->B
            now_word = 'W'
        elif now_word == 'W': # W->W 의 경우도 대응 가능하도록 하기 위하여...
            now_word = 'B'
        for j in range(start_x, start_x+8): # 그럼 이제 체스판을 순회해보자, 체스판은 8*8
            if wordlist[i][j] != now_word: # 만약 체스판이 중복되는 칸이 아니라면
                now_word = wordlist[i][j] # 현재의 값을 저장하고 다음 칸을 살핀다.
            else: # 만약 같은 색이라면,
                if now_word == 'B': # B일 경우
                    now_word = 'W' # 현재 값을 W로 바꾸고
                    cnt += 1 # cnt를 1 추가한다. 원래는 W가 들어가야하는 칸인데, 바꿨다친다.
                else: # W일 경우
                    now_word = 'B' # 현재 값을 B로 바꾸고
                    cnt += 1 # cnt를 1 추가한다. 원래는 B가 들어가야하는 칸인데, 바꿨다친다.
    cnt_list.append(cnt) # 반복문이 끝나면 cnt_list에 cnt를 추가한다.

    now_word = 'B' # 첫 케이스를 B로 정했을때
    cnt = 0 # 다시 cnt를 0으로 초기화.

    for i in range(start_y, start_y+8): # 위의 반복문을 그~대로 똑같이 수행한다.
        if now_word == 'B':
            now_word = 'W'
        elif now_word == 'W':
            now_word = 'B'
        for j in range(start_x, start_x+8):
            if wordlist[i][j] != now_word:
                now_word = wordlist[i][j]
            else:
                if now_word == 'B':
                    now_word = 'W'
                    cnt += 1
                else:
                    now_word = 'B'
                    cnt += 1
    cnt_list.append(cnt) # 반복문이 끝나면 cnt_list에 cnt를 추가한다.

vertical, horizen = map(int, input().split()) # 세로, 가로
wordlist = [input() for _ in range(vertical)] # 단어 리스트
cnt_list = [] # 바꿔야하는 갯수 리스트 저장용

for i in range(vertical - 7): # 만약 8 * 8 이상의 체스판이 주어졌을 경우
    for j in range(horizen - 7): # 차액만큼 시작점을 이동하면서 찾아야하기 때문에...
        checkboard(i, j) # checkboard def 호출

print(min(cnt_list)) # cnt_list 중에서 가장 적은 값을 출력하면 끝.

def recursion(num):
    global final_num
    if num > target_num: # 만약 num이 target_num을 초과해버렸다면.
        return # 성립되지 않는 경우의 수이므로 즉시 return
    elif num == target_num: # 만약 num이 target_num이 된다면,
        final_num += 1 # 방법의 수를 발견한 것이므로 final_num을 1 추가하고 return
        return
    else:
        recursion(num+1) # 1씩 더하는 재귀
        recursion(num+2) # 2씩 더하는 재귀
        recursion(num+3) # 3씩 더하는 재귀

testcase = int(input()) # 테스트 케이스 입력

for tc_idx in range(1, testcase+1):
    num = 0 # 시작점
    final_num = 0 # 답을 저장할 num
    target_num = int(input()) # 목표 숫자 입력
    recursion(num) # 재귀 def 호출

    print(final_num) # 답안 출력

def delta_move(start_x, start_y):
    global cango
    if start_x == horizen - 1 and start_y == vertical - 1: # 만약 가장 오른쪽 아래에 도달했다면
        cango = 'Yes' # 판정을 Yes로 설정하고 return
        return

    delta_y = [0, 1]
    delta_x = [1, 0] # 델타 리스트 정의

    for dir in range(2):
        if start_x + delta_x[dir] >= 0 and start_x + delta_x[dir] < horizen and start_y + delta_y[dir] >= 0 and start_y + delta_y[dir] < vertical: # 지도를 벗어나지 말것
            new_y = start_y + delta_y[dir]
            new_x = start_x + delta_x[dir]  # 탐색할 x 좌표 # 탐색할 y 좌표
            if visited[new_y][new_x] == 0 and roadtobitcoin[new_y][new_x] == 1 and cango == 'No': # 방문한 적 없고, 갈 수 있는 곳이며, 이미 목적지에 도달한 상태가 아니라면
                visited[new_y][new_x] = 1 # 그 쪽은 방문다고 하고
                delta_move(new_x, new_y) # 재귀하여 기준점을 변경


horizen, vertical = map(int, input().split()) # 가로와 세로
roadtobitcoin = [list(map(int, input().split())) for _ in range(vertical)] # 지도 입력 받기
visited = [[0] * horizen for _ in range(vertical)] # 방문 지도 정의

cango = 'No' # 최종 목표에 도달했는지를 나타내는 str

visited[0][0] = 1 # 0,0 에서 시작하므로 방문했다고 사전 지정
delta_move(0, 0) # 0,0 부터 시작

print(cango) # 답을 출력

def checker(start_x, start_y):
    global answer
    if start_x >= map_len or start_y >= map_len: # 지도 공간을 벗어난다면, 바로 리턴한다.
        return

    if game_map[start_y][start_x] == 0: # 만약 현 위치의 값이 0이라면 무한루프에 빠지므로 즉시 리턴
        return

    if game_map[start_y][start_x] == -1: # 최종 목표에 도달할 시
        answer = 'HaruHaru' # 출력할 문구를 HaruHaru로 변경
        return

    dy = [0, 1]
    dx = [1, 0] # 델타 탐색용 리스트

    for dir in range(2):
        new_x = game_map[start_y][start_x] * dx[dir] + start_x
        new_y = game_map[start_y][start_x] * dy[dir] + start_y # 젤리가 움직일 수 있는 곳은 현재 위치의 칸의 값 "만큼"
        if answer == 'HaruHaru': # 만약 목표장소에 도달했다면 즉시 리턴.
            return
        else: # 그게 아니라면
            checker(new_x, new_y) # 기준점을 이동 지점으로 바꾼 뒤 재귀

map_len = int(input()) # 맵 크기

game_map = [list(map(int, input().split())) for _ in range(map_len)] # 지도 제작

answer = 'Hing' # 기본 값을 'Hing'으로 지점

checker(0, 0) # check def 호출

print(answer) # 답 출력