PS를 위한 파이썬 정리

# 한 줄 읽기
s = input()
 
# 공백으로 구분된 입력을 리스트로
arr = list(map(int, input().split()))
 
# 여러 개의 값
n, m = map(int, input().split())
 
# 정수 리스트
line = list(map(int, input().split()))

# n개 행, m개 열
n, m = map(int, input().split())
grid = []
for _ in range(n):
    row = list(map(int, input().split()))
    grid.append(row)
 
# 리스트 컴프리헨션 버전, 위의 반복문과 동일하다.
grid = [list(map(int, input().split())) for _ in range(n)]

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

arr = [1, 2, 3, 4, 5]
 
# 방법 1: 언팩킹
print(*arr)  # 1 2 3 4 5
 
# 방법 2: join (문자열)
print('\n'.join(map(str, arr)))  # 1\n2\n3\n4\n5
 
# 방법 3: 루프
for x in arr:
    print(x)

import sys
result = []
for _ in range(n):
    result.append(str(answer))
print('\n'.join(result))

arr.append(x)          # 맨 뒤에 추가
arr.extend([4, 5])     # 여러 원소 추가
arr.pop()              # 맨 뒤 제거, 반환
arr.pop(0)             # 첫 원소 제거 (O(n))
arr.insert(i, x)       # i번 위치에 삽입 (O(n))
arr.remove(x)          # 첫 x 제거 (O(n))
arr.reverse()          # 역순
arr.sort()             # 정렬 (인자 가능)
arr.count(x)           # x의 개수
arr.index(x)           # x의 위치

t = (0, 2)             # 생성 (인덱스, 우선순위) 같은 묶음 값에 자주 쓴다
t[0]                   # 인덱싱으로 값 꺼내기 → 0
t[1]                   # → 2
 
idx, priority = t      # 언패킹으로 값 꺼내기 (t[0], t[1]과 같은 값)
 
# enumerate, dict.items(), zip은 모두 튜플을 만든다
# 반복문/제너레이터 표현식에서 바로 언패킹해서 받을 수 있다
for idx, priority in enumerate([2, 1, 3]):
    print(idx, priority)

d[key] = value         # 할당
d.get(key, default)    # key 없으면 default 반환
d.pop(key)             # key 제거, 값 반환
d.keys()               # 모든 key
d.values()             # 모든 value
d.items()              # (key, value) 쌍
d.update(other_dict)   # 다른 딕셔너리로 업데이트

s.add(x)               # 추가
s.remove(x)            # 제거 (없으면 에러)
s.discard(x)           # 제거 (없으면 무시)
s.pop()                # 임의의 원소 제거
s & t                  # 교집합
s | t                  # 합집합
s - t                  # 차집합
s ^ t                  # 대칭차 (둘 중 하나만)

# Falsy: 0, None, [], {}, "", (), False
if not x:       # x가 거짓 값이면
    pass
 
# Truthy: 0이 아닌 수, 비어있지 않은 컨테이너, True
if x:           # x가 참 값이면
    pass

x = 10 if condition else 20

arr = [1, 2, 3, 4, 6, 7]
 
for x in arr:
    if x == 5:
        print("found")
        break
else:
    print("not found")

n = int(input())
cnt = 0
 
for i in range(n):
    alpha = []
    s = input()
    prev = ''
    for t in s:
        if prev == t:
            prev = t
            continue
        if t in alpha:
            break
        else:
            alpha.append(t)
            prev = t
    else:
        cnt += 1
 
print(cnt)

# 1차원
squares = [x**2 for x in range(10)]
 
# 조건부
evens = [x for x in range(10) if x % 2 == 0]
 
# 중첩
pairs = [(x, y) for x in range(3) for y in range(3)]
 
# 조건부 (if-else)
result = [x if x % 2 == 0 else -x for x in range(5)]  # [0, -1, 2, -3, 4]

arr = [0] * 5                                    # 1D
grid = [[0] * 4 for _ in range(3)]               # 2D (올바른 방법)
grid = [[0] * 4] * 3                             # 2D (X: 같은 행 참조)

import copy
 
# 방법 1: copy 라이브러리
grid2 = copy.deepcopy(grid)
 
# 방법 2: 리스트 컴프리헨션
grid2 = [row[:] for row in grid]

from itertools import combinations
from collections import deque
import copy
 
best = 0
for walls in combinations(blanks, 3):
    tmp = copy.deepcopy(grid) 
    for x, y in walls:
        tmp[x][y] = 1
 
    q = deque(...)
    while q:
        x, y = q.popleft()
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and tmp[nx][ny] == 0:
                tmp[nx][ny] = 2
                q.append((nx, ny))
 
    count = sum(row.count(0) for row in tmp)
    best = max(best, count)

for i in range(len(grid)):
    for j in range(len(grid[i])):
        value = grid[i][j]

square = lambda x: x**2
print(square(5))  # 25
 
add = lambda x, y: x + y
print(add(3, 4))  # 7

arr = [3, 1, 4, 1, 5]
 
# sorted(): 새로운 정렬된 리스트 반환
result = sorted(arr)  # [1, 1, 3, 4, 5]
 
# sort(): 리스트 내부에서 정렬 (반환값 없음)
arr.sort()  # arr = [1, 1, 3, 4, 5]

# 절댓값
arr = [3, -1, -4, 2]
sorted(arr, key=abs)  # [-1, 2, 3, -4]
 
# 문자열 길이
words = ["apple", "pie", "a"]
sorted(words, key=len)  # ["a", "pie", "apple"]
 
# 두 번째 원소
pairs = [(1, 3), (1, 1), (2, 2)]
sorted(pairs, key=lambda x: x[1])  # [(1, 1), (2, 2), (1, 3)]

import re
 
def solution(files):
    t = []
    for f in files:
        match = re.match(r'([^0-9]+)([0-9]+)(.*)', f)
        head, number, tail = match.group(1), match.group(2), match.group(3)
        t.append((head.lower(), int(number), f)) 
 
    t = sorted(t, key=lambda x: (x[0], x[1])) 
 
    return [s[2] for s in t]

# 첫 번째 요소는 오름차순, 두 번째는 내림차순
students = [("Alice", 85), ("Bob", 85), ("Charlie", 90)]
sorted(students, key=lambda x: (x[1], -ord(x[0][0])))
 
# 또는 방법 2: 여러 번 sort() (역순으로, stable sort)
students.sort(key=lambda x: x[0])     # 이름순
students.sort(key=lambda x: x[1], reverse=True)  # 점수 내림차순

arr.sort().sort()  # X - 에러

arr = [1, 3, 2, 5, 4]
sum(arr)           # 15
max(arr)           # 5
min(arr)           # 1
 
words = ["a", "abc", "ab"]
max(words, key=len)  # "abc"
 
sum(arr, 10)       # 25 (10부터 시작)

for i, val in enumerate(arr):
    print(i, val)  # (0, 1), (1, 3), (2, 2), ...
 
for i, val in enumerate(arr, start=1):
    print(i, val)  # (1, 1), (2, 3), ...

for val in reversed(arr):
    print(val)
 
# 리스트로 변환
rev_arr = list(reversed(arr))

arr = [1, 2, 3]
any(arr)           # True
all(arr)           # True
 
arr = [0, 1, 2]
any(arr)           # True
all(arr)           # False
 
any(x > 5 for x in arr)  # 5보다 큰 값이 있나?
all(x > 0 for x in arr)  # 모두 양수인가?

found = False
for x in arr:
    if x > 5:
        found = True
result = found
 
result = any(x > 5 for x in arr)

pairs = [(0, 2), (1, 1), (2, 3)]  # (인덱스, 우선순위)
 
any(priority > 2 for idx, priority in pairs)  # 우선순위가 2보다 큰 게 있나?

dq = deque(enumerate(priorities))
current = dq.popleft()
 
if any(b > current[1] for a, b in dq): 
    dq.append(current)

quotient, remainder = divmod(17, 5)  # (3, 2)

a = [1, 2, 3]
b = [4, 5, 6]
for x, y in zip(a, b):
    print(x, y)  # (1, 4), (2, 5), (3, 6)
 
# 행렬 전치
matrix = [[1, 2], [3, 4], [5, 6]]
transposed = list(zip(*matrix))  # [(1, 3, 5), (2, 4, 6)]

nums = list(map(int, ["1", "2", "3"]))  # [1, 2, 3]
 
evens = list(filter(lambda x: x % 2 == 0, range(10)))  # [0, 2, 4, 6, 8]

from collections import deque
 
q = deque()
q.append(1)        # 오른쪽에 추가
q.appendleft(0)    # 왼쪽에 추가
q.pop()            # 오른쪽 제거, 반환
q.popleft()        # 왼쪽 제거, 반환
q[0]               # 첫 원소 접근

from collections import Counter
 
s = "aabbcc"
c = Counter(s)     # Counter({'a': 2, 'b': 2, 'c': 2})
c['a']             # 2
c.most_common(2)   # [('a', 2), ('b', 2)]

from collections import defaultdict
 
d = defaultdict(int)
d['a'] += 1        # key 없어도 0으로 초기화 후 1 추가
 
d = defaultdict(list)
d['group'].append(1)  # key 없어도 빈 리스트로 초기화

total[car] += 10       # total[car]를 먼저 "읽어서" 10을 더하는 것과 같다
                       # car가 없으면 읽을 값 자체가 없어서 KeyError
 
in_time[car] = now     # 그냥 새 값으로 덮어쓴다, 이전에 있었는지는 상관없다
                       # 일반 dict로 충분하다

import heapq
 
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
 
heapq.heappop(heap)  # 1
heapq.heappop(heap)  # 2
 
nums = [3, 1, 2]
heapq.heapify(nums)  # O(n)

heap = []
heapq.heappush(heap, -3)
heapq.heappush(heap, -1)
val = -heapq.heappop(heap)  # 3

import heapq
 
def solution(scoville, K):
    heapq.heapify(scoville)
 
    if scoville[0] >= K: 
        return 0
 
    answer = 0
    while len(scoville) > 1: 
        l1, l2 = heapq.heappop(scoville), heapq.heappop(scoville)
        t = l1 + l2 * 2
        heapq.heappush(scoville, t)
        answer += 1
        if scoville[0] >= K:
            return answer
 
    return -1

from itertools import permutations
 
arr = [1, 2, 3]
for perm in permutations(arr):
    print(perm)  # (1,2,3), (1,3,2), (2,1,3), ...
 
# r개 선택 (순열)
for perm in permutations(arr, 2):
    print(perm)  # (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)

from itertools import combinations
 
arr = [1, 2, 3]
for comb in combinations(arr, 2):
    print(comb)  # (1,2), (1,3), (2,3)

from itertools import product
 
for p in product([1, 2], ['a', 'b']):
    print(p)  # (1,'a'), (1,'b'), (2,'a'), (2,'b')
 
# repeat 파라미터로 자신과의 곱
for p in product([1, 2], repeat=2):
    print(p)  # (1,1), (1,2), (2,1), (2,2)

from itertools import combinations_with_replacement
 
arr = [1, 2, 3]
for comb in combinations_with_replacement(arr, 2):
    print(comb)  # (1,1), (1,2), (1,3), (2,2), (2,3), (3,3)

import bisect
 
arr = [1, 3, 5, 7, 9]
 
# bisect_left: x가 들어갈 위치 (x 미만인 요소 개수)
bisect.bisect_left(arr, 5)   # 2
bisect.bisect_left(arr, 4)   # 2
 
# bisect_right: x 이하인 요소 개수
bisect.bisect_right(arr, 5)  # 3
bisect.bisect_right(arr, 4)  # 2
 
# insort: 정렬 상태 유지하며 삽입
bisect.insort(arr, 6)  # arr = [1, 3, 5, 6, 7, 9]

# arr에서 4 이상 7 이하인 값의 개수
left = bisect.bisect_left(arr, 4)
right = bisect.bisect_right(arr, 7)
count = right - left

import math
 
math.gcd(12, 8)         # 4
math.lcm(12, 8)         # 24
math.comb(5, 2)         # 10 (5C2)
math.perm(5, 2)         # 20 (5P2)
math.factorial(5)       # 120
math.sqrt(16)           # 4.0
math.ceil(3.2)          # 4
math.floor(3.8)         # 3
math.isqrt(17)          # 4 (정수 제곱근)

memo = {}
def fib(n):
    if n in memo:        # 이미 계산한 적 있으면
        return memo[n]   # 저장된 값 반환
    if n < 2:
        return n
    memo[n] = fib(n-1) + fib(n-2)  # 계산하고 저장
    return memo[n]

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

17 // 5    # 3 (몫)
17 / 5     # 3.4 (실수)
17 % 5     # 2 (나머지)

a, b = b, a  # 파이썬 스타일

ord('A')      # 65
chr(65)       # 'A'
ord('a') - ord('A')  # 32 (대소문자 차이)

s = "hello"
s[1:3]        # "el"
s[::-1]       # "olleh" (역순)
s.replace('l', 'L')  # "heLLo" (새 문자열)
 
# 문자열은 불변이므로 s[0] = 'H' 불가능
# 리스트로 변환 후 다시 문자열로
chars = list(s)
chars[0] = 'H'
s = ''.join(chars)

s = "123"
arr = list(s)          # ['1', '2', '3']
s = ''.join(arr)       # "123"
 
# 문자가 아닌 경우
nums = [1, 2, 3]
s = ''.join(map(str, nums))  # "123"

from collections import Counter, defaultdict
 
s = "aabbcc"
 
# 방법 1: Counter
freq = Counter(s)
freq['a']    # 2
 
# 방법 2: dict.get()
freq = {}
for c in s:
    freq[c] = freq.get(c, 0) + 1
 
# 방법 3: defaultdict
freq = defaultdict(int)
for c in s:
    freq[c] += 1

visited = set()
visited.add((0, 0))
if (0, 0) in visited:
    print("이미 방문")

float('inf')   # 양의 무한대
-float('inf')  # 음의 무한대
 
min_val = float('inf')
min_val = min(min_val, 10)  # 10

arr = [3, 1, 2, 1, 3]
result = sorted(set(arr))  # [1, 2, 3]

from collections import defaultdict
 
n = int(input())
s = list(map(int, input().split()))
ss = sorted(s)
 
rank = defaultdict(int)
cnt = 0
for i in range(1, len(ss)):
    if ss[i] != ss[i - 1]: 
        cnt += 1
    rank[ss[i]] = cnt
 
print(*[rank[x] for x in s])

left = max(a1, a2)
right = min(b1, b2)
if left <= right:
    # [left, right]가 겹치는 부분
    length = right - left + 1

def solution(array, commands):
    answer = []
 
    for c in commands:
        i, j, k = c
        ta = sorted(array[i - 1:j]) 
        answer.append(ta[k - 1]) 
 
    return answer

import math
 
def solution(n):
    sieve = [1] * (n + 1)
    sieve[0] = 0
    sieve[1] = 0
 
    for i in range(2, int(math.sqrt(n)) + 1):
        if sieve[i]:
            for j in range(i * i, n + 1, i):
                sieve[j] = 0
 
    return sum(sieve) 

def solution(s):
    stk = []
    for ch in s:
        if stk and stk[-1] == ch: 
            stk.pop() 
        else:
            stk.append(ch)
 
    return 1 if not stk else 0

stk = []
for i, p in enumerate(prices):
    while stk and prices[stk[-1]] > p:  # 스택 top의 "값"은 prices[stk[-1]]로 조회
        idx = stk.pop()                  # 꺼내는 건 인덱스
        answer[idx] = i - idx            # 그 인덱스 자리에 답을 채움
    stk.append(i)

def solution(prices):
    answer = [0] * len(prices)
    stk = []
 
    for i, p in enumerate(prices):
        while stk and prices[stk[-1]] > p:
            idx = stk.pop() 
            answer[idx] = i - idx 
        stk.append(i)
 
    for idx in stk:
        answer[idx] = (len(prices) - 1) - idx
 
    return answer

from collections import deque
 
def solution(priorities, location):
    dq = deque(enumerate(priorities))
    order = 0
 
    while dq:
        current = dq.popleft()
 
        if any(b > current[1] for a, b in dq): 
            dq.append(current) 
        else:
            order += 1
            if current[0] == location:
                return order

import heapq
 
def solution(scoville, K):
    heapq.heapify(scoville)
 
    if scoville[0] >= K: 
        return 0
 
    answer = 0
    while len(scoville) > 1: 
        l1, l2 = heapq.heappop(scoville), heapq.heappop(scoville)
        t = l1 + l2 * 2
        heapq.heappush(scoville, t)
        answer += 1
        if scoville[0] >= K:
            return answer
 
    return -1

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

from collections import Counter
 
def solution(want, number, discount):
    s = []
    for i in range(len(want)):
        for j in range(number[i]):
            s.append(want[i])
    wc = Counter(s)
 
    answer = 0
    for i in range(len(discount) - 9):
        tc = Counter(discount[i:i + 10])
        if wc == tc: 
            answer += 1
 
    return answer

i = 0
j = 0
while i < len(arr):
    # i로 윈도우 확장
    window_size = i - j + 1
 
    # 조건 확인 및 j 진행
    while condition:
        # j로 윈도우 축소
        j += 1
 
    i += 1

arr = [2, 3, 1, 2, 4, 3]
s = 7
 
i = 0
j = 0
min_len = float('inf')
current_sum = 0
 
while i < len(arr):
    current_sum += arr[i]
    i += 1
 
    while current_sum >= s:
        min_len = min(min_len, i - j)
        current_sum -= arr[j]
        j += 1
 
print(min_len)  # 2 ([4, 3])

# X: 축소하기 전에 윈도우 크기를 미리 계산
while i < len(arr):
    csum += arr[i]
    wsize = i - j + 1        # j가 아직 줄어들기 전 값
    while csum > k:
        csum -= arr[j]
        j += 1
    if csum == k and wsize < best:
        ...                   # 실제 최종 구간 크기와 다른 값으로 비교하게 됨
    i += 1
 
# O: 축소가 다 끝난 뒤에 계산
while i < len(arr):
    csum += arr[i]
    while csum > k:
        csum -= arr[j]
        j += 1
    wsize = i - j + 1        # j가 다 줄어든 뒤의 진짜 값
    if csum == k and wsize < best:
        ...
    i += 1

def solution(sequence, k):
    answer = []
    i, j = 0, 0
    csum = 0
    bw = float('inf')
 
    while i < len(sequence):
        csum += sequence[i]
        while csum > k:
            csum -= sequence[j]
            j += 1
        wsize = i - j + 1
        if csum == k and wsize < bw:
            answer = [j, i]
            bw = wsize
        i += 1
 
    return answer

left = 0
right = len(arr) - 1
 
while left < right:
    total = arr[left] + arr[right]
    if total > target:
        right -= 1    # 합이 크면 오른쪽을 줄이고
    elif total < target:
        left += 1     # 합이 작으면 왼쪽을 늘린다
    else:
        break         # 정확히 맞으면 종료

arr = [-99, -2, -1, 4, 98]
 
left = 0
right = len(arr) - 1
best = float('inf')
ans_l, ans_r = 0, 0
 
while left < right:
    total = arr[left] + arr[right]
 
    if abs(total) < best:
        best = abs(total)
        ans_l, ans_r = arr[left], arr[right]
 
    if total > 0:
        right -= 1
    elif total < 0:
        left += 1
    else:
        break
 
print(ans_l, ans_r)  # -99 98

n = int(input())
s = list(map(int, input().split()))
 
left = 0
right = n - 1
best = float('inf')
ansl, ansr = 0, 0
 
while left < right:
    total = s[left] + s[right]
 
    if abs(total) < best: 
        best = abs(total) 
        ansl, ansr = s[left], s[right] 
 
    if total > 0:
        right -= 1
    elif total < 0:
        left += 1
    else:
        break
 
print(ansl, ansr)

n = len(arr)
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i+1] = prefix[i] + arr[i]
 
def range_sum(l, r):
    return prefix[r+1] - prefix[l]

arr = [1, 2, 3, 4, 5]
n = len(arr)
prefix = [0] * (n + 1)
 
for i in range(n):
    prefix[i+1] = prefix[i] + arr[i]
 
# [1, 3] 범위 합
print(prefix[4] - prefix[1])  # 9 (2+3+4)

rows, cols = len(grid), len(grid[0])
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
 
for i in range(1, rows + 1):
    for j in range(1, cols + 1):
        prefix[i][j] = grid[i-1][j-1] \
                       + prefix[i-1][j] \
                       + prefix[i][j-1] \
                       - prefix[i-1][j-1]

def range_sum_2d(r1, c1, r2, c2):
    return prefix[r2+1][c2+1] \
           - prefix[r1][c2+1] \
           - prefix[r2+1][c1] \
           + prefix[r1][c1]

grid = [[1, 2], [3, 4], [5, 6]]
rows, cols = len(grid), len(grid[0])
 
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(1, rows + 1):
    for j in range(1, cols + 1):
        prefix[i][j] = grid[i-1][j-1] \
                       + prefix[i-1][j] \
                       + prefix[i][j-1] \
                       - prefix[i-1][j-1]
 
def range_sum_2d(r1, c1, r2, c2):
    return prefix[r2+1][c2+1] \
           - prefix[r1][c2+1] \
           - prefix[r2+1][c1] \
           + prefix[r1][c1]
 
print(range_sum_2d(0, 0, 2, 1))  # 1+2+3+4+5+6 = 21

# 비교: a/b < c/d
# X: a/b < c/d (부동소수점 오차)
# O: a*d < c*b (정수 연산)

diff = [0] * (n + 1)
diff[l] += delta
diff[r + 1] -= delta
 
# 나중에 한 번만 누적합
for i in range(1, n):
    diff[i] += diff[i - 1]

n, m = len(board), len(board[0])
diff = [[0] * m for _ in range(n)]
 
for r1, c1, r2, c2, delta in updates:
    diff[r1][c1] += delta
    if c2 + 1 < m:
        diff[r1][c2 + 1] -= delta
    if r2 + 1 < n:
        diff[r2 + 1][c1] -= delta
    if r2 + 1 < n and c2 + 1 < m:
        diff[r2 + 1][c2 + 1] += delta
 
# 가로 누적합 → 세로 누적합, 순서를 지켜야 한다
for r in range(n):
    for c in range(1, m):
        diff[r][c] += diff[r][c - 1]
 
for c in range(m):
    for r in range(1, n):
        diff[r][c] += diff[r - 1][c]
 
# diff[r][c]가 (r, c) 칸에 최종적으로 적용된 값

def solution(board, skill):
    n = len(board)
    m = len(board[0])
    diff = [[0] * m for _ in range(n)]
 
    for s in skill: 
        type_, r1, c1, r2, c2, degree = s 
        delta = degree if type_ == 2 else -degree 
        diff[r1][c1] += delta 
        if c2 + 1 < m: 
            diff[r1][c2 + 1] -= delta 
        if r2 + 1 < n: 
            diff[r2 + 1][c1] -= delta 
        if r2 + 1 < n and c2 + 1 < m: 
            diff[r2 + 1][c2 + 1] += delta 
 
    for r in range(n):
        for c in range(1, m):
            diff[r][c] += diff[r][c - 1] 
 
    for c in range(m):
        for r in range(1, n):
            diff[r][c] += diff[r - 1][c] 
 
    answer = 0
    for r in range(n):
        for c in range(m):
            if board[r][c] + diff[r][c] >= 1:
                answer += 1
 
    return answer

from collections import deque
 
n = ...  # 노드 수
v = [False] * (n + 1)
 
def bfs(start):
    queue = deque()
    queue.append(start)
    v[start] = True
 
    while queue:
        node = queue.popleft()
 
        for neighbor in graph[node]:
            if not v[neighbor]:
                v[neighbor] = True
                queue.append(neighbor)

from collections import deque
 
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    dq = deque()
    dq.append((0, 0))
    dist = [[0] * m for _ in range(n)] 
    dist[0][0] = 1
 
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
 
    while dq:
        x, y = dq.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and dist[nx][ny] == 0: 
                dq.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1
 
    return dist[-1][-1] if dist[-1][-1] != 0 else -1

from collections import deque
 
queue = deque()
dist = {}
 
for source in sources:   # 시작점 전부 큐에 삽입
    queue.append(source)
    dist[source] = 0
 
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in dist:
            dist[neighbor] = dist[node] + 1
            queue.append(neighbor)

from collections import deque
 
m, n, h = map(int, input().split())
q = deque()
 
arr = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]
dist = [[[-1] * m for _ in range(n)] for _ in range(h)]
 
for k in range(h): 
    for j in range(n): 
        for i in range(m): 
            if arr[k][j][i] == 1: 
                q.append((k, j, i)) 
                dist[k][j][i] = 0
 
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
 
while q:
    z, y, x = q.popleft()
    for k in range(6):
        nx, ny, nz = x + dx[k], y + dy[k], z + dz[k]
        if 0 <= nx < m and 0 <= ny < n and 0 <= nz < h:
            if arr[nz][ny][nx] == 0 and dist[nz][ny][nx] == -1:
                dist[nz][ny][nx] = dist[z][y][x] + 1
                q.append((nz, ny, nx))
 
ans = -1
for k in range(h):
    for j in range(n):
        for i in range(m):
            if arr[k][j][i] == 0 and dist[k][j][i] == -1:
                print(-1)
                exit()
            ans = max(ans, dist[k][j][i])
 
print(ans)

from collections import deque
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def grid_bfs(grid, sr, sc):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(sr, sc)])
    visited = [[False] * cols for _ in range(rows)]
    visited[sr][sc] = True
 
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < rows and 0 <= ny < cols \
               and not visited[nx][ny] and grid[nx][ny] != 0:
                visited[nx][ny] = True
                queue.append((nx, ny))

import sys
sys.setrecursionlimit(10**6)
 
v = [False] * (n + 1)
 
def dfs(node):
    v[node] = True
    for neighbor in graph[node]:
        if not v[neighbor]:
            dfs(neighbor)

def solution(n, computers):
    visit = [0 for _ in range(n)]
 
    def dfs(node):
        visit[node] = 1
        for j in range(n):
            if computers[node][j] == 1 and not visit[j]: 
                dfs(j) 
 
    answer = 0
    for i in range(n):
        if not visit[i]:
            dfs(i)
            answer += 1
 
    return answer

v = [False] * (n + 1)
 
def dfs_stack(start):
    stack = [start]
    v[start] = True
 
    while stack:
        node = stack.pop()
        for neighbor in graph[node]:
            if not v[neighbor]:
                v[neighbor] = True
                stack.append(neighbor)

import heapq
 
INF = float('inf')
g = [[] for _ in range(v + 1)]  # g[s].append((c, e))
dist = [INF] * (v + 1)
visit = [False] * (v + 1)
 
q = []
heapq.heappush(q, (0, start))
dist[start] = 0
 
while q:
    cost, u = heapq.heappop(q)
    if visit[u]:
        continue
    visit[u] = True
    for w, t in g[u]:
        if cost + w < dist[t]:
            dist[t] = cost + w
            heapq.heappush(q, (dist[t], t))

import heapq
 
def solution(N, road, K):
    INF = float('inf')
    dist = [INF] * (N + 1)
    visit = [False] * (N + 1)
    q = []
    g = [[] for _ in range(N + 1)]
    for a, b, c in road: 
        g[a].append((c, b)) 
        g[b].append((c, a)) 
 
    heapq.heappush(q, (0, 1))
    dist[1] = 0
 
    while q:
        cost, u = heapq.heappop(q)
        if visit[u]:
            continue
        visit[u] = True
        for w, t in g[u]:
            if cost + w < dist[t]:
                dist[t] = cost + w
                heapq.heappush(q, (dist[t], t)) 
 
    return sum(d <= K for d in dist[1:])