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

from collections import deque

h,w = map(int, input().split())
# 場外を追加
A = [['*']*(w+2)] + [['*']+[s for s in input()]+['*'] for _ in range(h)] + [['*']*(w+2)]
visited = [[0]*(w+2) for _ in range(h+2)]

dq = deque()
n=0
directions = [[0,1],[1,0],[0,-1],[-1,0]]
# 初期配置の黒をキューに追加
for hi in range(1,h+1):
    for wi in range(1,w+1):
        if A[hi][wi] == '#':
            dq.append([hi,wi,n])
            visited[hi][wi] = 1
# キューが空になるまで
while dq:
    hi,wi,n = dq.popleft()

    for d in directions:
        new_hi, new_wi = hi+d[0],wi + d[1]
        # 「黒くしてない白マス」をキューに追加
        if visited[new_hi][new_wi] == 0 and A[new_hi][new_wi] == '.':
            dq.append([new_hi,new_wi,n+1])
            visited[new_hi][new_wi] = 1
print(n)

### FIXED CODE ###

from collections import deque

h,w = map(int, input().split())
A = [[s for s in input()] for _ in range(h)]

visited = [[-1]*(w) for _ in range(h)]
dq = deque()
directions = [[0,1],[1,0],[0,-1],[-1,0]]

# 初期配置の黒をキューに追加
for hi in range(h):
    for wi in range(w):
        if A[hi][wi] == '#':
            dq.append([hi,wi])
            visited[hi][wi] = 0

# キューが空になるまで
while dq:
    hi,wi = dq.popleft()
    for d in directions:
        nhi, nwi = hi+d[0],wi + d[1]
        # 場外ならスキップ
        if nhi<0 or nhi>=h or nwi<0 or nwi>=w: continue 
        # 「黒くしてない白マス」をキューに追加
        if visited[nhi][nwi] == -1 and A[nhi][nwi] == '.':
            dq.append([nhi,nwi])
            visited[nhi][nwi] = visited[hi][wi] + 1

ans = -1
for x in visited:
    ans = max(ans,max(x))
print(ans)
### BUGGY CODE ###

from collections import deque
from copy import deepcopy
H, W = map(int, input().split())
maze = [[]for i in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        maze[i].append(S[j])

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
ans = 0
Q = deque()

for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if (sx == gx) and (sy == gy):
                    continue
                if (maze[sy][sx] == '#') or (maze[gy][gx] == '#'):
                    continue
                mazenow = deepcopy(maze)
                Q.clear()
                Q.append((sy, sx))
                mazenow[sy][sx] = 0
                flag = True
                while (len(Q) >= 0) and flag:
                    y, x = Q.popleft()
                    for i in range(4):
                        ny = y + dy[i]
                        nx = x + dx[i]
                        if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W):
                            continue
                        elif (ny == gy) and (nx == gx):
                            ans = max(ans, mazenow[y][x] + 1)
                            flag = False
                            break
                        elif mazenow[ny][nx] == '.':
                            mazenow[ny][nx] = mazenow[y][x] + 1
                            Q.append((ny, nx))

print(ans)





### FIXED CODE ###

from collections import deque
from copy import deepcopy
H, W = map(int, input().split())
maze = [[]for i in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        maze[i].append(S[j])

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
ans = 0
Q = deque()

for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        mazenow = deepcopy(maze)
        Q.clear()
        Q.append((sy, sx))
        mazenow[sy][sx] = 0
        flag = True
        max_maze_now = 0
        while len(Q) > 0:
            y, x = Q.popleft()
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W):
                    continue
                elif mazenow[ny][nx] == '.':
                    mazenow[ny][nx] = mazenow[y][x] + 1
                    max_maze_now = max(max_maze_now, mazenow[ny][nx])
                    Q.append((ny, nx))
        ans = max(max_maze_now, ans)

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

from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]

res = 0
for i in range(H):
    for j in range(W):
        stack = deque([])
        flag = [[False for _ in range(W)] for _ in range(H)]
        stack.append([i, j])
        flag[i][j] = True
        start = S[i][j]
        while len(stack) > 0:
            y, x = stack.popleft()
            for nx, ny in ([1, 0], [0, 1], [-1, 0], [0, -1]):
                if 0<= x + nx < W and 0 <= y + ny < H:
                    if S[y][x] != S[y+ny][x+nx] and flag[y+ny][x+nx] == False:
                        stack.append([y+ny, x+nx])
                        flag[y+ny][x+nx] = True
                        if S[y+ny][x+nx] != start:
                            res += 1
            
                
            
            
print(res//2)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]
flag = [[-1 for _ in range(W)] for _ in range(H)]

now = 0
for i in range(H):
    for j in range(W):
        if flag[i][j] == -1:
            stack = deque([]) 
            stack.append([i, j])
            flag[i][j] = now
            while len(stack) > 0:
                y, x = stack.popleft()
                for nx, ny in ([1, 0], [0, 1], [-1, 0], [0, -1]):
                    if 0<= x + nx < W and 0 <= y + ny < H:
                        if S[y][x] != S[y+ny][x+nx] and flag[y+ny][x+nx] == -1:
                            stack.append([y+ny, x+nx])
                            flag[y+ny][x+nx] = now
            now += 1
    
Black = [0 for _ in range(now+1)]
White = [0 for _ in range(now+1)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            Black[flag[i][j]] += 1
        else:
            White[flag[i][j]] += 1
   
res = 0
for i in range(now + 1):
    res += Black[i] * White[i]
    
print(res)
### BUGGY CODE ###

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

tmp = 0
for i in range(B - 1, N + 1, B):
    if (s := (A * i) // B - A * (i // B)) > 0:
        tmp = max(s, tmp)
    else:
        break
    
for i in range(N, N - N % B - 1, -1):
    tmp = max((A * i) // B - A * (i // B), tmp)

print(tmp)



### FIXED CODE ###

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

def f(num):
    return(A * num) // B - A * (num // B)

print(f(min(B - 1, N)))
### BUGGY CODE ###

class edge():
    def __init__(self,to,cost):
        self.to = to
        self.cost = cost

from heapq import *
class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def empty(self):
        return len(self.queue) == 0
    def size(self):
        return len(self)

from numpy import array,inf


def djikstra(s):
    que = PriorityQueue()
    d = [inf]*V
    d[s] = 0
    que.push((0,s))
    while(not que.empty()):
        p = que.pop()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                que.push((d[e.to],e.to))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = {}
Gb = {}
for i in range(n):
    Ga[i]=[]
    Gb[i]=[]
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append(edge(v-1,a))
    Ga[v-1].append(edge(u-1,a))
    Gb[u-1].append(edge(v-1,b))
    Gb[v-1].append(edge(u-1,b))

G = Ga
S = djikstra(s-1)
G = Gb
T = djikstra(t-1)

M = array(S)+array(T)

for i in range(n):
    print(10**15-min(M[i:]))


### FIXED CODE ###

from heapq import *
from numpy import array,inf


def djikstra(G,s):
    que = []
    d = [inf]*V
    d[s] = 0
    visited = [False] * V
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(G[v])):
            e = G[v][i]
            if visited[e[0]]:
                continue
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = [[] for i in range(n)]
Gb = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

S = djikstra(Ga,s-1)

T = djikstra(Gb,t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

for i in range(n):
    print(ans[i])
### BUGGY CODE ###

n = input()
li = list(map(int, input().split()))
a = 1
if 0 in li:
    print(0)
else:
    for x in li:
        a *= x
    if a > 10**18:
        print(-1)
    else:
        print(a)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

def main():
    from math import gcd
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    mod = 1000000007

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

    lcm = A[0]
    for i in range(1, N):
        lcm = lcm * A[i] // gcd(lcm, A[i])

    ans = 0
    for i in range(N):
        ans += lcm // A[i]
        ans %= mod

    print(ans)


main()

### FIXED CODE ###

def main():
    from math import gcd
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    mod = 1000000007

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

    lcm = 1
    for i in A:
        lcm = lcm * i // gcd(lcm, i)
    lcm %= mod

    ans = 0
    for i in A:
        ans += lcm * pow(i, mod-2, mod)
        ans %= mod

    print(ans)


main()
### BUGGY CODE ###

def solve():
    alpha = "abcdefghijklmnopqrstuvwxyz"
    inp1, inp2 = input(), input()
    sz = dict(zip(list(alpha), [0] * 26))
    tz = dict(zip(list(alpha), [0] * 26))
    siz = dict(zip(list(alpha), [set([]) for _ in range(26)]))
    tiz = dict(zip(list(alpha), [set([]) for _ in range(26)]))
    for i in range(len(inp1)):
        sz[inp1[i]] += 1
        tz[inp2[i]] += 1
        siz[inp1[i]].add(i)
        tiz[inp2[i]].add(i)
        if (sz[inp1[i]] != tz[inp2[i]]
                or siz[inp1[i]] ^ tiz[inp2[i]]):
            print("No")
            return
    print("Yes")


solve()


### FIXED CODE ###

def solve():
  from collections import Counter
  s = [i for i in sorted(Counter(input()).values())]
  t = [i for i in sorted(Counter(input()).values())]
  print(["No","Yes"][s==t])

solve()
### BUGGY CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N:
        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in range(len(Graph_list[current])):
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:

        # 全ての点に到達している場合
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の点に移動する        
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)
### BUGGY CODE ###

from bisect import bisect_left, insort_left
N = int(input())
A = list(map(int, input().split()))


# 各数の出現場所を持ってソート: 1-indexed
A_with_position = sorted([[a, i] for i, a in enumerate(A, start=1)])


# 出現したもののindex
appeared_index = [0, N + 1]

ans = 0
for a, i in A_with_position:
    li = bisect_left(appeared_index, i) - 1
    ri = bisect_left(appeared_index, i)
    
    lx, rx = appeared_index[li], appeared_index[ri]
    ans += a * (i - lx) * (rx - i)

    insort_left(appeared_index, i)

print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))

d = [0] * (N+1)
for i in range(N):
    d[a[i]] = i

left = list(range(N+1))
right = list(range(N+1))

ans = 0
for i in range(N, 0, -1):
    di = d[i]
    ans += i * (right[di]-di+1) * (di-left[di]+1)
    right[left[di] - 1] = right[di]
    left[right[di] + 1] = left[di]

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

def resolve():
    N,K,Q = list(map(int,input().split()))
    A = [input() for i in range(Q)]
    P = [K for i in range(N)]

    def calc(n):
        return n-1

    for i in range(Q):
        P = list(map(calc,P))
        P[int(A[i])-1] += 1

    for i in range(N):
        if P[i] <= 0:
            print("No")
        else:
            print("Yes")
resolve()

### FIXED CODE ###

def resolve():
    N,K,Q = list(map(int,input().split()))
    A = [input() for i in range(Q)]
    P = [K] * N

    def calc(n):
        return n-Q

    for i in range(Q):
        P[int(A[i])-1] += 1

    P = list(map(calc, P))

    for i in range(N):
        if P[i] <= 0:
            print("No")
        else:
            print("Yes")
resolve()
### BUGGY CODE ###

L, R = ( int(a) for a in input().split() )
mi = 2018
for i in range( L, R ):
    for j in range( i + 1, R + 1 ):
        mi = min( mi, ( i * j ) % 2019 )
        if mi == 0:
            break
print( mi )

### FIXED CODE ###

l, r = map(int, input().split())
x = []
for i in range(l, r):
    for j in range(i + 1, r + 1):
        mod = i * j % 2019
        x.append(mod)
        if mod == 0:
            print(0)
            exit()
print(min(x))
### BUGGY CODE ###

k, t = map(int, raw_input().split())
a = map(int, raw_input().split())

while len(a) > 1:
    a[-2] = abs(a[-1] - a[-2])
    while not a[-1]:
        a.pop()

if not a:
    print 0
else:
    print a[0] - 1

### FIXED CODE ###

k, t = map(int, raw_input().split())
a = map(int, raw_input().split())

while len(a) > 1:
    a.sort()
    tmp = abs(a.pop() - a.pop())
    if tmp:
        a.append(tmp)

if not a:
    print 0
else:
    print a[0] - 1
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = sorted(list( map(int, input().split()) ))
f = sorted(list( map(int, input().split()) ), reverse=True)

lft = -1
rgt = 10**12
while rgt-lft > 1:
    mid = ( rgt+lft ) // 2
    cnt = 0

    for i, e in enumerate(a):
        cnt += max( 0, e-mid//f[i] )

    if cnt <= k:
        rgt = mid
    else:
        lft = mid

print(rgt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = sorted(list( map(int, input().split()) ))
f = sorted(list( map(int, input().split()) ), reverse=True)

lft = -1
rgt = 10**12
while rgt-lft > 1:
    mid = ( rgt+lft ) // 2
    cnt = 0

    for i, e in enumerate(a):
        cnt += max( 0, e-mid//f[i] )

    if cnt <= k:
        rgt = mid
    else:
        lft = mid

print(rgt)
### BUGGY CODE ###

n, m = map(int, input().split())
x = list()
for i in range(m):
    temp = list(map(int, input().split()))
    tempall = set()
    for j in range(temp[0],temp[1]+1):
        tempall.add(j)
    x.append(tempall)

ans = set(x[0])
for i in range(m):
    ans = ans & x[i]

print(len(ans))

### FIXED CODE ###

n, m = map(int, input().split())
l = [1,n]
for i in range(m):
    temp = list(map(int, input().split()))
    l[0] = max(l[0],temp[0])
    l[1] = min(l[1],temp[1])

print(int(max(l[1]-l[0]+1, 0)))
### BUGGY CODE ###

n = int(input())
a = [[] for i in range(n)]

a = [int(i) for i in input().split()]
b = [[] for i in range(n+1)]

for i in a:
    b[i].append(i)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def ans(N):
    if N >= 2:
        return(cmb(N,2))
    else: return(0)

for i in a:
    cnt = 0
    for j in b:
        try:
            if i == j[0]: cnt += ans(len(j)-1)
            else: cnt += ans(len(j))
        except:
            continue
    print(cnt)


### FIXED CODE ###

from operator import mul
from functools import reduce

n = int(input())
a = [[] for i in range(n)]

a = [int(i) for i in input().split()]
b = [0]*(n+1)

for i in a:
    b[i] +=1

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def ans(N):
    if N >= 2:
        return(cmb(N,2))
    else: return(0)

cnt=0
for j in b: cnt += ans(j)
for i in a:
    temp = cnt
    temp = temp - (ans(b[i])- ans(b[i]-1))
    print(temp)
### BUGGY CODE ###

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

start = m//n

for i in range(start,0,-1):
    if m%i==0:
        print(i)
        break

### FIXED CODE ###

def main():
    n,m = map(int,input().split())

    start = m//n

    for i in range(start,0,-1):
        if m%i==0:
            print(i)
            break

main()
### BUGGY CODE ###

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

i = 1
count = 0
while A*i <= (T+0.5):
  count += i * T
  
print(count)

### FIXED CODE ###

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

i = 1
count = 0
while A*i <= (T+0.5):
  count += B
  i += 1
  
print(count)
### BUGGY CODE ###

s = list(input())
idx = ['s', 'e']
for i in range(len(s)):
    if s[i] == 'A' and idx[0] == 's':
        idx[0] = i
        if idx[0] != 's' and idx[1] != 'e':
            break
    if s[::-1][i] == 'Z' and idx[1] == 'e':
        idx[1] = -i
        if idx[0] != 's' and idx[1] != 'e':
            break
if idx[1] == 0:
    print(len(s[idx[0]:]))
else:
    print(len(s[idx[0]:idx[1]]))


### FIXED CODE ###

s = str(input())
print(s.rfind('Z') - s.find('A') + 1)
### BUGGY CODE ###

n = int(input())
heights = [int(ch) for ch in input().split()]
ans = 0
for i in range(len(heights)):
    h = heights[i]
    for j in range(i+h+1,len(heights)):
        interval = j-i
        sum = h+heights[j]
        if sum == interval:
            ans+=1
print(ans)



### FIXED CODE ###

n = int(input())
heights = [int(ch) for ch in input().split()]
ans = 0
dict = {}
for i in range(len(heights)):
    key = i+heights[i]
    if key in dict.keys():
        dict[key] += 1
    else:
        dict[key] = 1
for i in range(len(heights)):
    key = i-heights[i]
    if key in dict.keys():
        ans+=dict[key]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# atcoder 
# Türkçe konuşyorum
# Türkler var mı?
# memnün oldum
import sys
import math


sys.setrecursionlimit(10 ** 8)

#def divmin
#for i in range(d, 1, -1):
#    if(d % i == 0):
#        print(i)
def pgcd(a, b):
    while b!=0:
        a,b=b,a%b
    return a

def msum(a, b, c):
    if (a <= b) and (a <= c): 
        return math.gcd(a, math.gcd(b,c))
        #while(a >= 1):
        #    if (b % a == 0) and (c % a == 0):
        #        return a
            
    elif (b <= a) and (b <= c):
        return(math.gcd(b, math.gcd(a,c)))
    elif (c <= a) and (c <= b):
        return math.gcd(c, math.gcd(a,b))
    else:
        print("Grande érreur dans ta tête!!!")

def çözmek(num):
    csum = 0
    for i in range(1, num+1):
        for j in range(1, num+1):
            for l in range(1, num+1):
                #print(i,j,l)
                csum += msum(i,j,l)


    return csum


if __name__ == "__main__":
    K = int(input())
    print(çözmek(K))


### FIXED CODE ###

#!/usr/bin/env python3
# atcoder 
# Türkçe konuşyorum
# Türkler var mı?
# memnün oldum
import sys
import math


sys.setrecursionlimit(10 ** 8)

#def divmin
#for i in range(d, 1, -1):
#    if(d % i == 0):
#        print(i)
def pgcd(a, b):
    while b!=0:
        a,b=b,a%b
    return a

def msum(a, b, c):
    if (a <= b) and (a <= c): 
        return math.gcd(a, math.gcd(b,c))
        #while(a >= 1):
        #    if (b % a == 0) and (c % a == 0):
        #        return a
            
    elif (b <= a) and (b <= c):
        return(math.gcd(b, math.gcd(a,c)))
    elif (c <= a) and (c <= b):
        return math.gcd(c, math.gcd(a,b))
    else:
        print("Grande érreur dans ta tête!!!")

def çözmek(num):
    csum = 0
    for i in range(1, num+1):
        for j in range(1, num+1):
            for l in range(1, num+1):
                #print(i,j,l)
                #csum += msum(i,j,l)
                csum += math.gcd(i, math.gcd(j,l))

    return csum


if __name__ == "__main__":
    K = int(input())
    print(çözmek(K))
### BUGGY CODE ###

import itertools
n = int(input())
li = []
lic = []
count = 0
for i in range(n):
    lic.append(i+1)
for i in range(n):
    lia = list(input())
    lia.sort()
    li.append(lia)
lib = list(itertools.combinations(lic,2))
for i in range(len(lib)):
    if li[lib[i][0]-1] == li[lib[i][1]-1]:
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
li = []
count = 0
f = 1
for i in range(n):
    a = input()
    li.append("".join(sorted(a)))
li.sort()
for i in range(n-1):
    if li[i] == li[i+1]:
        f += 1
    else:
        count += (f*(f-1))//2
        f = 1
count += (f*(f-1))//2
print(count)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
ans=float('inf')

for i in range(2,n-1):
    p,q,r,s=0,0,0,0
    left=sum(a[:i])
    right=sum(a[i:])
    # print()
    # print(left)
    # print(right)
    tmppq=[float('inf'),0,0]
    tmprs=[float('inf'),0,0]
    for j in range(i-1):
        p+=a[j]
        q=left-p
        if tmppq[0]>abs(p-q):
            tmppq=[abs(p-q),p,q]
    for j in range(i,n-1):
        r+=a[j]
        s=right-r
        if tmprs[0]>abs(r-s):
            tmprs=[abs(r-s),r,s]
    ans=min(ans,max(tmppq[1],tmppq[2],tmprs[1],tmprs[2])-min(tmppq[1],tmppq[2],tmprs[1],tmprs[2]))
print(ans)

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))

lst=ruiseki(a)
ans=float('inf')

kirekomi=[1,3]

for i in range(2,n-1):
    while 1:
        if abs(lst[kirekomi[0]]-(lst[i]-lst[kirekomi[0]]))>abs(lst[kirekomi[0]+1]-(lst[i]-lst[kirekomi[0]+1])):
            kirekomi[0]+=1
        else:
            break
    
    while 1:
        if abs((lst[n]-lst[kirekomi[1]])-(lst[kirekomi[1]]-lst[i]))>abs((lst[n]-lst[kirekomi[1]+1])-(lst[kirekomi[1]+1]-lst[i])):
            kirekomi[1]+=1
        else:
            break
    
    # print(kirekomi)
    p=lst[kirekomi[0]]
    q=lst[i]-lst[kirekomi[0]]
    r=lst[kirekomi[1]]-lst[i]
    s=lst[n]-lst[kirekomi[1]]
    anslst=[p,q,r,s]
    ans=min(ans,max(anslst)-min(anslst))
    # print(anslst)
print(ans)