inspirit941

def solution(s: str):
    def expand(left: int, right: int) -> str:
      # 현재 left idx, right idx가 같은 문자열일 경우
      # 윈도우 크기를 좌우로 1씩 넓힌다.
        while left >= 0 and right <= len(s) and s[left] == s[right-1]:
            left -= 1
            right += 1
        return s[left+1:right-1]
    # 연산 필요없는 경우
    if len(s) < 2 or s == s[::-1]:

inspirit941

inspirit941

import sys
r, c = map(int, sys.stdin.readline().split())
maps = []
for y in range(r):
    arr = list(sys.stdin.readline().replace("\n",""))
    maps.append(arr)

# 많은 파이프를 심으려면, 최대한 우상향으로 접근해야 함.
dirs = [(-1,1),(0,1),(1,1)]
end_line = len(maps[0])-1

inspirit941

import sys
from collections import defaultdict
# taller[i] = i보다 키 큰 사람의 집합
# shorter[i] = i보다 키 작은 사람의 집합
taller, shorter = defaultdict(set), defaultdict(set)

n, m = map(int, sys.stdin.readline().split())
for _ in range(m):
    # a는 b보다 키가 작다
    a, b = map(int, sys.stdin.readline().split())

inspirit941

import sys
n = int(sys.stdin.readline())
memo = {1:1,2:1,3:1,4:2,5:2}
def find_result(number : int) -> int:
    if number in memo:
        return memo[number]
    memo[number] = find_result(number-1) + find_result(number-5)
    return memo[number]

for _ in range(n):

inspirit941

import sys
from collections import deque
maps = []
birds = []
r, c = map(int, sys.stdin.readline().split())
for y in range(r):
    arr = list(sys.stdin.readline().replace("\n",""))
    maps.append(arr)
    for x in range(len(arr)):
        if arr[x] == "L":

inspirit941

import sys
from collections import deque
r, c, n = map(int, sys.stdin.readline().split())
bombs = []
maps = []
for y in range(r):
    maps.append(list(sys.stdin.readline().replace("\n","")))
    for x in range(len(maps[0])):
        if maps[y][x] == 'O':
            maps[y][x] = (0+3, maps[y][x])

inspirit941

def dfs(idx, price):
    global answer
    if idx >= len(days):
        answer = min(answer, price)
        return
    # 1일 이용권 결제
    if days[idx] == 0:
        dfs(idx+1, price)
    else:
        dfs(idx+1, price + (days[idx] * prices[0]))

inspirit941

import sys
import bisect
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

table = [arr[0]]
for idx in range(1, n):
    # 현재까지의 부분수열 최댓값보다 더 큰 값일 경우
    if arr[idx] > table[-1]:
        table.append(arr[idx])

inspirit941

import sys
from collections import defaultdict, deque

n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
connected = defaultdict(set)
for _ in range(m):
    parent, child = map(int, sys.stdin.readline().split())
    connected[parent].add(child)