Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]


def main():
    n = ni()

    print(sum(range(n)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]


def main():
    n = ni()

    print(n * (n - 1) // 2)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

A = []
B = []
cnt = 0
ans = 0

for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)


while cnt < m:
    A_min = min(A)
    A_min_index = A.index(A_min)
    if cnt + B[A_min_index] < m:
        ans += A_min * B[A_min_index]
        cnt += B[A_min_index]
        A.pop(A_min_index)
        B.pop(A_min_index)
    else:
        for i in range(B[A_min_index]):
            if cnt == m:
                break
            ans += A_min
            cnt += 1

print(ans)


### FIXED CODE ###

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

ans = 0

for a,b in drink:
    ans += a*min(b,m)
    m -= min(b,m)
    if m == 0:
        break

print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 0
for i in range(n):
    for j in range(i+1,n):
        if abs(a[i]+a[j])==abs(i-j):
            s += 1
print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
X = dict()
ans = 0
for i in range(n):
    R = i + a[i]
    if not R in X:
        X[R]=1
    else: X[R]+=1

for i in range(n):
    L = i - a[i]
    if L in X:
        ans+=X[L]
print(ans)
### BUGGY CODE ###

from collections import defaultdict

def main():
    num, max_weigh = map(int, input().split())
    now_dp = defaultdict(int)
    next_dp = defaultdict(int)
    now_dp[0] = 0

    for i in range(num):
        weight, value = map(int, input().split())
        for now_weigh in list(now_dp.keys()):
            next_dp[now_weigh] = max(now_dp[now_weigh], next_dp[now_weigh])
            if now_weigh + weight <= max_weigh:
                next_dp[now_weigh + weight] = max(now_dp[now_weigh] + value, now_dp[now_weigh + weight])
        now_dp = next_dp
        next_dp = defaultdict(int)
    print(max(list(now_dp.values())))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import numpy as np




def main():
    num, lim_weight = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    dp = np.full(10 ** 5 + 1, np.inf)

    for i in range(num):
        weight, value = data[i]
        prev = dp.copy()
        dp[:value] = np.minimum(prev[:value], weight)
        dp[value:] = np.minimum(prev[value:], prev[:-value] + weight)

        # print(dp[:100])
    ans = np.max(np.where(dp <= lim_weight)) + 1
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
counted = 0

def make_divisors(n):
    count = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            count += 1
            if i != n // i:
                count += 1
    return count

for i in range(1,n):
  counted +=  make_divisors(i)

print(counted)

### FIXED CODE ###

n = int(input())
counted = 0

for i in range(1,n):
  counted +=  (n-1)//i

print(counted)
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    S = defaultdict(int)
    for i in range(N):
        S[sr()] += 1
    max_k_list = sorted([kv[0] for kv in S.items() if kv[1] == max(S.values())])
    for l in max_k_list:
        print(l)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    S = defaultdict(int)
    for i in range(N):
        S[sr()] += 1
    max_value = max(S.values())
    max_k_list = sorted([kv[0] for kv in S.items() if kv[1] == max_value])
    for l in max_k_list:
        print(l)
resolve()
### BUGGY CODE ###

n = int(input())
d = []
for _ in range(n):
  di = str(input())
  if di not in d:
    d.append(di)
print(len(d))

### FIXED CODE ###

n = int(input())
s = [""]*n
for i in range(n):
  si = str(input())
  s[i] = si
s.sort()
c = 0
s.append("A")
for i in range(n):
  if s[i] != s[i+1]:
    c += 1
print(c)
### BUGGY CODE ###

s = input()
q = int(input())
rev = 0
ans = 'S'

for _ in range(q):
  query = list(input().split())
  if int(query[0]) == 1:
    rev += 1
  else:
    if int(query[1]) == 1:      # 先頭
      if rev%2 == 0:
        ans = query[2] + ans
      else:
        ans = ans + query[2]
    else:                       # 末尾
      if rev%2 == 0:
        ans = ans + query[2]
      else:
        ans = query[2] + ans

mes = ans.replace("S", s)
if rev%2 == 0:
  print(mes)
else:
  print(mes[::-1])



### FIXED CODE ###

import collections

s = input()
q = int(input())
rev = 0
ans = collections.deque(['S'])

for _ in range(q):
  query = list(input().split())
  if int(query[0]) == 1:
    rev += 1
  else:
    if int(query[1]) == 1:      # 先頭
      if rev%2 == 0:
        ans.appendleft(query[2])
      else:
        ans.append(query[2])
    else:                       # 末尾
      if rev%2 == 0:
        ans.append(query[2])
      else:
        ans.appendleft(query[2])

ans = ''.join(ans)
mes = ans.replace("S", s)
if rev%2 == 0:
  print(mes)
else:
  print(mes[::-1])
### BUGGY CODE ###

alphabet = "abcdefghijklmnopqrstuvwxyz"
a_len = len(alphabet)
table = {c: idx for idx, c in enumerate(alphabet)}

s = input()
k = int(input())

ans = ""
for i in range(len(s[:-1])):
    gap = a_len - table[s[i]]
    if gap <= k:
        ans += "a"
        k -= gap
    elif k == 0:
        ans += s[i:-1]
    else:
        ans += s[i]

ans += alphabet[(table[s[-1]] + k) % a_len]
print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    s = rl().rstrip()
    K = int(rl())
    
    ans = []
    for si in s:
        if si == 'a':
            ans.append('a')
            continue
        cnt = ord('z') - ord(si) + 1
        if cnt <= K:
            ans.append('a')
            K -= cnt
        else:
            ans.append(si)
    
    ans[-1] = chr(ord('a') + (ord(ans[-1]) - ord('a') + K % 26) % 26)
    print(''.join(ans))


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

N, A, B = map(int, input().split())

num_blue = 0
num_all = 0
while 1:
    num_blue += A
    num_all += A
    if N <= num_all:
        num_blue -= num_all - N
    num_all += B
    if N <= num_all:
        break
    

print(num_blue)

### FIXED CODE ###

N, A, B = map(int, input().split())
num_put = A + B
num_blue = N // num_put * A + min(A, N % num_put)
print(num_blue)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))

visited = [1]
last = 1

for i in range(K):
    t = A[last - 1]
    if t in visited:
        z = K - i - 1
        r = visited[visited.index(t):]
        l = len(r)
        print(r[z % l])
        exit()
    else:
        visited.append(t)
        last = t

print(visited[-1])



### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))

visited = {1: 0}
index = 0
last = 1

for i in range(K):
    t = A[last - 1]
    index += 1
    if t in visited:
        z = K - i - 1
        l = index - visited[t]
        print([k for k, v in visited.items() if v == visited[t] + (z % l)][0])
        exit()
    else:
        visited[t] = index
        last = t

print(last)
### BUGGY CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n=n0()
a=n1()

ans=0
for i in range(n):
    h=a[i]
    B=list(range(-i,-i+n))
    C=[0]*n
    for j in range(n):
        C[j]=abs(B[j])-a[j]-h
    ans+=C.count(0)
print(ans//2)

### FIXED CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

from collections import defaultdict
n=n0()
a=[0]
a.extend(n1())

m1=[i+a[i] for i in range(n+1)]
m2=[j-a[j] for j in range(n+1)]

d1=defaultdict(list)
d2=defaultdict(list)
for i in range(1,n+1):
    d1[m1[i]].append(i)
    d2[m2[i]].append(i)

ans=0
for i in d1:
    ans+=len(d1[i])*len(d2[i])
            
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = []
for x in A:
    tmp_lst = []
    for _ in range(60):
        tmp = x // 2
        tmp_lst.append(x - tmp * 2)
        x = tmp
    B.append(tmp_lst)

ans = 0
for i in range(60):
    tr, fl = 0, 0
    for x in B:
        if x[i]:
            tr += 1
        else:
            fl += 1
    ans += (tr * fl) * 2 ** i
    ans = ans % (10 ** 9 + 7)
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = []
for x in A:
    tmp_lst = []
    for _ in range(60):
        tmp = x // 2
        tmp_lst.append(x - tmp * 2)
        x = tmp
    B.append(tmp_lst)

ans = 0
for i in range(60):
    tr, fl = 0, 0
    for x in B:
        if x[i]:
            tr += 1
        else:
            fl += 1
    ans += (tr * fl) * 2 ** i
    ans = ans % (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read

N, M = map(int, readline().split())

if M == 0:
    print('Yes')
    exit()

LRD = map(int, read().split())
graph = [[] for _ in range(N + 1)]

# 根からの距離、根は複数の可能性あり
distance = [-1] * (N + 1)
child = [0] * (N + 1)

for L, R, D in zip(LRD, LRD, LRD):
    graph[L].append((R, D))
    child[R] += 1

for i in range(1, N + 1):
    if child[i]:
        continue

    # 以下iは根
    distance[i] = 0
    stack = [i]
    while stack:
        V = stack.pop()
        for v, d in graph[V]:
            if distance[v] == -1:
                distance[v] = distance[V] + d
            else:
                if distance[v] != distance[V] + d:
                    print('No')
                    exit()

            stack.append(v)

# 例4のような循環タイプは上のfor内で処理されない
if -1 in distance[1:]:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

import sys
readline = sys.stdin.readline
read = sys.stdin.read

N, M = map(int, readline().split())

if M == 0:
    print('Yes')
    exit()

LRD = map(int, read().split())
graph = [[] for _ in range(N + 1)]

# 根からの距離、根は複数の可能性あり
distance = [-1] * (N + 1)
child = [0] * (N + 1)

for L, R, D in zip(LRD, LRD, LRD):
    graph[L].append((R, D))
    child[R] = 1

for i in range(1, N + 1):
    if child[i]:
        continue

    # 以下iは根
    distance[i] = 0
    stack = [i]
    while stack:
        V = stack.pop()
        for v, d in graph[V]:
            if distance[v] == -1:
                distance[v] = distance[V] + d
                stack.append(v)
            else:
                if distance[v] != distance[V] + d:
                    print('No')
                    exit()

# 例4のような循環タイプは上のfor内で処理されない
if -1 in set(distance[1:]):
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

import math
N=int(input())
total=0
for i in range(N):
    total+=i
print(total)

### FIXED CODE ###

N=int(input())
print(N*(N-1)//2 if N>2 else 1 if N==2 else 0)
### BUGGY CODE ###

n,k=map(int,input().split())
listn=[]
for a in range(n):
    b,c=map(int,input().split())
    listn+=[b]*c
listn.sort()
print(listn[k-1])

### FIXED CODE ###

class Number:
    def __init__(self,number,qty):
        self.qty=qty
        self.number=number

n,k=map(int,input().split())
listn=[]
for a in range(n):
    b,c=map(int,input().split())
    listn.append(Number(b,c))
listn.sort(key=lambda x:x.number)
count=k
for a in listn:
    if a.qty>=count:
        print(a.number)
        break
    else:
        count-=a.qty
### BUGGY CODE ###

# -*- coding:utf-8 -*-
N = int(input())
"""
a_list=[]

for _ in range(N):
    a_list.append(int(input()))
"""
a_list = [int(input()) for i in range(N)]


cnt_push = 1
button_list = []
cur_but_posi = a_list[0]

while True:
    #cur_but_posi = a_list[cur_but_posi - 1]
    if cur_but_posi == 2:
        print(cnt_push)
        break
    elif cur_but_posi in button_list:
        print(-1)
        break
    else:
        button_list.append(cur_but_posi)
        cur_but_posi = a_list[cur_but_posi - 1]    
        cnt_push += 1    



### FIXED CODE ###

import sys

l = [int(i) - 1 for i in sys.stdin]

N = l[0] + 1

a = l[1:]

done = [False] * N

i = 0

ans = 0

while True:
    if done[i] == False:
        done[i] = True
        ans += 1
        if a[i] == 1:
            break
        i = a[i]
    else:
        ans = -1
        break

print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


def main():
    s = input()
    q = int(input())

    queries = [input().split() for i in range(q)]

    flg = True
    for query in queries:
        if "1" == query[0]:
            flg = not flg
        elif "2" == query[0]:
            if ("1" == query[1] and flg) or ("2" == query[1] and not flg):
                s = query[2] + s
            else:
                s += query[2]

    if flg:
        print(s)
    else:
        print(s[::-1])


if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    s = input()
    q = int(input())

    queries = (input().split() for i in range(q))

    flg = True
    result = s
    pre = ""
    post = ""
    for query in queries:
        if "1" == query[0]:
            flg = not flg
        elif "2" == query[0]:
            if ("1" == query[1] and flg) or ("2" == query[1] and not flg):
                pre = query[2] + pre
            else:
                post += query[2]

    if flg:
        print(pre + result + post)
    else:
        print((pre + result + post)[::-1])


if __name__ == '__main__':
    main()
### BUGGY CODE ###

# C - gacha
from bisect import *
N = int(input())
ans = []
for _ in range(N):
    S = input()
    i = bisect_left(ans,S)
    if i>=len(ans) or ans[i]!=S:
        insort_left(ans,S)
print(len(ans))

### FIXED CODE ###

# C - gacha
N = int(input())
ans = set()
for _ in range(N):
    S = input()
    ans.add(S)
print(len(ans))
### BUGGY CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    parents = [[] for _ in range(N+1)]
    childs = [[] for _ in range(N+1)]
    for i in range(N+M-1):
        a, b = map(int, input().split())
        childs[a].append(b)
        parents[b].append(a)
    root = -1
    for i in range(1, N+1):
        if len(parents[i]) == 0:
            root = i
            break
    originalParent = [-1] * (N+1)
    q = deque([])
    q.append((root, 0))
    while(len(q)):
        n, parent = q.popleft()
        originalParent[n] = parent
        for c in childs[n]:
            q.append((c, n))
    for i in range(1, N+1):
        print(originalParent[i])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque, defaultdict


def main():
    N, M = map(int, input().split())
    childs = defaultdict(list)
    parents = defaultdict(int)
    for i in range(N+M-1):
        a, b = map(int, input().split())
        childs[a].append(b)
        parents[b] += 1
    q = deque(x for x in range(1, N+1) if parents[x] == 0)
    ans = defaultdict(int)
    while(len(q)):
        n = q.popleft()
        for c in childs[n]:
            parents[c] -= 1
            if parents[c] == 0:
                q.append(c)
                ans[c] = n
    for i in range(1, N+1):
        print(ans[i])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod


def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


def check3(m):
    dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod


def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


def check3(m):
    dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)
### BUGGY CODE ###

def given(_dummy=int(input())): return [int(_) for _ in input().split()]


def solve(ary):
    if len(set(ary)) < 2:
        return len(ary) // 2

    even, odd = [], []
    for i, _ in enumerate(ary):
        even.append(_) if i % 2 == 0 else odd.append(_)

    even_key, odd_key = list(set(even)), list(set(odd))

    res = len(ary)
    most = 0

    if len(even_key) != 1:
        l_cache = 0
        for n in even:
            curr = max(l_cache, even.count(n))
            if l_cache != curr:
                most = n
            l_cache = curr

        res -= l_cache
    else:
        res -= len(even)

    if len(odd_key) != 1:
        r_cache = 0
        for n in odd:
            if n == most:
                continue
            curr = max(r_cache, odd.count(n))
            r_cache = curr

        res -= r_cache
    else:
        res -= len(odd)

    return res


print(solve(given()))

### FIXED CODE ###

from collections import Counter

def solve(size=int(input()), ary=list(map(int, input().split()))):
    even, odd = Counter(ary[::2]), Counter(ary[1::2])
    even[0], odd[0] = 0, 0
    (e, em), (_, es) = even.most_common(2)
    (o, om), (_, os) = odd.most_common(2)
    return size - max(em + os, es + om) if e == o else size - em - om

print(solve())
### BUGGY CODE ###

h,w = map(int, input().split())
maze = [input() for i in range(h)]
route_total = [[h*w] * w for i in range(h)]

black_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            black_list.append([i+1,j+1])
 
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]

stack = MyStack()
for black in black_list:
    route = [[0] * w for i in range(h)]
    stack.push(black[0],black[1])
    route[black[0]-1][black[1]-1] = 0
    while len(stack.stack) > 0:
        y,x = stack.pop()
        route_num = route[y-1][x-1] + 1
        if y != h:
            if maze[y][x-1] == '.' and route[y][x-1] == 0:
                stack.push(y+1,x)
                route[y][x-1] = route_num
                route_total[y][x-1] = min(route_num,route_total[y][x-1])
        if y != 1:
            if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
                stack.push(y-1,x)
                route[y-2][x-1] = route_num
                route_total[y-2][x-1] = min(route_num,route_total[y-2][x-1])
        if x != w:
            if maze[y-1][x] == '.' and route[y-1][x] == 0:
                stack.push(y,x+1)
                route[y-1][x] = route_num
                route_total[y-1][x] = min(route_num,route_total[y-1][x])
        if x != 1:
            if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
                stack.push(y,x-1)
                route[y-1][x-2] = route_num
                route_total[y-1][x-2] = min(route_num,route_total[y-1][x-2])

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            ans = max(route_total[i][j],ans)
 
print(ans)

### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()
 
"""))