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

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[0] * (W+2)]
    D += ([[0] + [float("inf")]*W + [0] for i in range(H)])
    D.append([0]*(W+2))
    G = [["#"]*(W+2)]
    for i in range(H):
        line = [i for i in input().strip()]
        for j in range(W):
            if line[j] == "#":
                ls.append([i+1, j+1, 0])
                D[i+1][j+1] = 0
        G.append(["#"]+line+["#"])
    G.append([["#"]*(W+2)])

    direction = [[1,0], [-1,0], [0,1], [0,-1]]
    while len(ls) > 0:
        h, w, depth = ls.popleft()
        for dh, dw in direction:
            if depth + 1 < D[h+dh][w+dw] and G[h+dh][w+dw] != "#":
                ls.append([h+dh, w+dw, depth+1])
                D[h+dh][w+dw] = depth + 1

    ans = 0
    for h in range(H):
        ans = max(ans, max(D[h]))
        
    return ans
    
print(bfs())

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

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

s = str(input())
q = int(input())
queries = list()
for ii in range(0,q):
  queries.append(input())
  
#print(queries)
# True -> straight, False -> back
order_flag = True

for query in queries:
  if query.startswith("1"):
    order_flag = not order_flag
  elif query.startswith("2"):
    if query[2] == "1":
      if order_flag:
        s = query[4] + s
      else:
        s = s + query[4]
    elif query[2] == "2":
      if order_flag:
        s = s + query[4]
      else:
        s = query[4] + s

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

### FIXED CODE ###

from collections import deque

s = deque(list(input()))
#print(s)
q = int(input())
queries = list()
for ii in range(0,q):
  queries.append(input())
  
#print(queries)
# True -> straight, False -> back
order_flag = True

for query in queries:
  if query.startswith("1"):
    order_flag = not order_flag
  elif query.startswith("2"):
    if query[2] == "1":
      if order_flag:
        s.appendleft(query[4])
      else:
        s.append(query[4])
    elif query[2] == "2":
      if order_flag:
        s.append(query[4])
      else:
        s.appendleft(query[4])
        
if order_flag:
  print(''.join(list(s)))
else:
  s.reverse()
  print(''.join(list(s)))
### BUGGY CODE ###

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

result = 0
for i in range(N):
    for j in range(i + A[i], N):
        if abs(i - j) == A[i] + A[j]:
            result += 1
print(result)


### FIXED CODE ###

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

c1 = {}
c2 = {}

for i in range(N):
    c1.setdefault(i + A[i], 0)
    c1[i + A[i]] += 1
    c2.setdefault(i - A[i], 0)
    c2[i - A[i]] += 1

result = 0
for k in set(c1).intersection(c2):
    result += c1[k] * c2[k]
print(result)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,P=map(int,input().split())

i=1
ans=1

if N==1:
    print(P)
else:
    try:
        while i**N<=P:#最大値適当
            if P%(i**N)==0:
                ans=i
            i+=1
        print(ans)
    except:
        print(ans)
        
#うんち

### FIXED CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N,P=map(int,input().split())
l=[0]*int(-(-P**0.5//1)+1)

if N==1:
    print(P)
    exit()

for i in range(2,int(-(-P**0.5//1)+1))[::-1]:
    p=P
    count=0
    while p%i==0:
        p/=i
        count+=1
        if count==N:
            print(i)
            exit()
print(1)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

D = defaultdict(int)
for a in A:
    for i in range(61):
        D[1 << i] += bool(a & (1 << i))

ans = 0
for key, value in D.items():
    ans += key * value * (N - value)
    ans %= MOD

print(ans % MOD)


### FIXED CODE ###

def main():
    def accumulate(array):
        for i in range(len(array) - 1):
            array[i + 1] += array[i]
        return array

    N = int(input())
    A = list(map(int, raw_input().split()))
    MOD = 10 ** 9 + 7

    X = [[0] * N for i in range(61)]
    for i, a in enumerate(A):
        for j in range(61):
            if (1 << j) & a:
                X[j][i] = 1

    for i in range(61):
        X[i] = accumulate(X[i])


    ans = 0
    for i, a in enumerate(A):
        for j in range(61):
            x = X[j][-1] - X[j][i]
            if (1 << j) & a:
                ans += ((1 << j) % MOD) * ((N - i - 1) - x)
                ans %= MOD

            else:
                ans += ((1 << j) % MOD) * x
                ans %= MOD


    print(ans % MOD)


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

import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]

    def size(self, x):
        return -self.parent[self.find(x)]

    def find(self, x):
        if (self.parent[x] < 0):
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if (x == y):
            return False
        if (self.size(x) < self.size(y)):
            self.parent[y] += self.parent[x]
            self.parent[x] = y
        else:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    N = int(input())
    x_list = []
    y_list = []
    x_app = x_list.append
    y_app = y_list.append
    for i in range(N):
        x, y = map(int, input().split())
        x_app([x, i])
        y_app([y, i])

    x_list.sort()
    y_list.sort()
    adj = []
    adj_app = adj.append
    for i in range(N-1):
        adj_app([x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]])
        adj_app([y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]])

    adj.sort()
    uf = UnionFind(N)
    ans = 0
    for edge in adj:
        if not uf.same(edge[1], edge[2]):
            ans += edge[0]
            uf.unite(edge[1], edge[2])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 6199094

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

import math
n,a,b = map(int,input().split())
mod = 10**9+7
ans = pow(2,n,mod)
def cmb(n,r,mod):
  a = math.factorial(n)%mod
  b = math.factorial(r)%mod
  c = math.factorial(n-r)%mod
  return a//(b*c)%mod
ans = ans-(cmb(n,a,mod)+cmb(n,b,mod))-1
print(ans)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7
ans = pow(2,n,mod)
def cmb(n,r,mod):
  if n == r:
    return 1
  p,q = 1,1
  r = min(r,n-r)
  for i in range(r):
    p = p*(n - i)%mod
    q = q*(i + 1)%mod
    Y = pow(q,10**9+5,mod)
  return p*Y%mod
ans = ans - cmb(n,a,mod) - cmb(n,b,mod) - 1
print(ans%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(pow(10, 6))

n = int(input())
nodes = [[] for _ in range(n)]
visited = [False for _ in range(n)]

def dfs(i, d):
  global nodes
  child_d = [(i, d)]
  for cn, c in nodes[i]:
    if not visited[cn]:
      visited[cn] = True
      child_d += dfs(cn, d+c)
  return child_d

for _ in range(n-1):
  u, v, w = map(int, input().split())
  nodes[u-1].append((v-1, w))
  nodes[v-1].append((u-1, w))

visited[0] = True
ans = dfs(0, 0)

for _, c in sorted(ans, key=lambda x: x[0]):
  if c % 2 == 0:
    print(0)
  else:
    print(1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(pow(10, 6))

n = int(input())
nodes = [[] for _ in range(n)]
visited = [False for _ in range(n)]
dist = [0 for _ in range(n)]

def dfs(i, d):
  dist[i] = d
  for cn, c in nodes[i]:
    if not visited[cn]:
      visited[cn] = True
      dfs(cn, d+c)

for _ in range(n-1):
  u, v, w = map(int, input().split())
  nodes[u-1].append((v-1, w))
  nodes[v-1].append((u-1, w))

visited[0] = True
dfs(0, 0)

for c in dist:
  if c % 2 == 0:
    print(0)
  else:
    print(1)
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
l_ls = sorted(map(int, input().split()))

ans = 0
for i, a in enumerate(l_ls):
    for j, b in enumerate(l_ls):
        if i >= j:
            continue

        ls = l_ls[:i] + l_ls[i+1:j] + l_ls[j+1:]

        left = bisect_left(ls, max(a-b, b-a)+1)
        right = bisect_left(ls, a+b)
        ans += right-left


print(ans//3)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l_ls = sorted(map(int, input().split()))

ans = 0

for i in range(n):
    for j in range(i+1, n):
        a, b = l_ls[i], l_ls[j]
        right = bisect_left(l_ls, a+b)
        ans += right-(j+1)

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

from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=[list(map(float,input().split()))for i in range(n)]
a=wf(s,directed=False).tolist()
if s!=a:
    print(-1)
else:
    c=0
    for i in range(n-1):
        for j in range(i+1,n):
            for d in range(n):
                if d!=i and d!=j:
                    if s[i][j]>=s[i][d]+s[d][j]:
                        break
            else:
                c+=int(s[i][j])
    else:
        print(c)

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=np.array([list(map(int,input().split()))for i in range(n)])
if np.any(s!=wf(s,directed=False)):
    print(-1)
else:
    c=0
    for i in range(n):
        s[i][i]=10**10
    for i in range(n):
        for j in range(i+1,n):
            d=np.min(s[i]+s[j])
            if s[i,j]!=d:
                c+=s[i,j]
    else:
        print(c)
### BUGGY CODE ###

N,M = map(int,input().split())
def f():
    for i in range(N,M+1):
        if M%i == 0:
            return M//i
print(f())

### FIXED CODE ###

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

m = M
f = {}
while m%2 == 0:
    f[2] = f.get(2,0) + 1
    m = m//2

k = 3
l = int(m**0.5)+1
while m != 1:
    if k > l:
        f[m] = f.get(m,0)+1
        break
    while m%k == 0:
        f[k] = f.get(k,0)+1
        m = m//k
    k += 2
C=[1]
for k in f:
    C_tmp = []
    for c in C:
        for i in range(f[k]):
            C_tmp.append(c*(k**(i+1)))
    C.extend(C_tmp)
ans_r = M
for c in C:
    if c>=N and c<ans_r:
        ans_r = c
print(M//ans_r)
### BUGGY CODE ###

import heapq

def main():
    N, M, S = map(int, input().split())
    AB = [[] for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        AB[u - 1].append((a, b, v - 1))
        AB[v - 1].append((a, b, u - 1))
        maxA = max(maxA, a)
    for i in range(N):
        AB[i].sort()

    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    while tc:
        t, u, s = heapq.heappop(cur)
        if T[u] == -1:
            T[u] = t
            tc -= 1
        ma = maxS
        for a, b, v in AB[u]:
            if s < a:
                break
            heapq.heappush(cur, (t + b, v, s - a))
        if s != maxS:
            c, d = CD[u]
            heapq.heappush(cur, (t + d, u, min(s + c, maxS)))
    print('\n'.join(map(str, T[1:])))

main()


### FIXED CODE ###

import heapq

def main():
    N, M, S = map(int, input().split())
    AB = [[] for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        AB[u - 1].append((a, b, v - 1))
        AB[v - 1].append((a, b, u - 1))
        maxA = max(maxA, a)
    for i in range(N):
        AB[i].sort()

    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    P = [-1] * N
    while tc:
        t, u, s = heapq.heappop(cur)
        if s <= P[u]:
            continue
        P[u] = s
        if T[u] == -1:
            T[u] = t
            tc -= 1
        for a, b, v in AB[u]:
            if s < a:
                break
            heapq.heappush(cur, (t + b, v, s - a))
        if s != maxS:
            c, d = CD[u]
            min_a = AB[u][0][0]
            k = max(1, (min_a - s + c  - 1) // c)
            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))
    print('\n'.join(map(str, T[1:])))

main()
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
town = [list(map(int,input().split()))+[i] for i in range(N)]

townx = sorted(town)
towny = sorted(town,key = lambda t : t[1])

heap = []
heapq.heapify(heap)

for i in range(N-1):
    heapq.heappush(heap,[abs(townx[i][0]-townx[i+1][0]),townx[i][2],townx[i+1][2]])
    heapq.heappush(heap,[abs(towny[i][1]-towny[i+1][1]),towny[i][2],towny[i+1][2]])

uf = UnionFind(N)
ans = 0

while heap:
    cost,t1,t2 = heapq.heappop(heap)
    if uf.same(t1,t2):
        continue
    uf.union(t1,t2)
    ans += cost
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
town = [list(map(int,input().split()))+[i] for i in range(N)]

townx = sorted(town)
towny = sorted(town,key = lambda t : t[1])

road = []

for i in range(N-1):
    road.append([abs(townx[i][0]-townx[i+1][0]),townx[i][2],townx[i+1][2]])
    road.append([abs(towny[i][1]-towny[i+1][1]),towny[i][2],towny[i+1][2]])

road.sort()

uf = UnionFind(N)
ans = 0

for r in road:
    cost,t1,t2 = r
    if uf.same(t1,t2):
        continue
    uf.union(t1,t2)
    ans += cost
    
print(ans)
### BUGGY CODE ###

a,b,k = map(int,input().split())
src = [i for i in range(a,b+1)]
if k > len(src):
    k = len(src)
li = []
for ki in range(k):
    li.append(src[ki])
for ki in reversed(range(k)):
    li.append(src[-(ki+1)])
for l in sorted(set(li)):
    print(l)

### FIXED CODE ###

a,b,k = map(int,input().split())
if k > b-a+1:
    k = b-a+1
li = set()
for i in range(k):
    li.add(a+i)
    li.add(b-i)
for l in sorted(li):
    print(l)
### BUGGY CODE ###

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

def solve(sh,sw):
  if S[sh][sw]=="#":
    return 0
  h,w=sh,sw
  cnt=1
  for _ in range(H):
    if h==0:
      break
    h-=1
    if S[h][w]=="#":
      break
    cnt+=1
  h=sh
  for _ in range(H):
    if h==H-1:
      break
    h+=1
    if S[h][w]=="#":
      break
    cnt+=1
  h=sh
  for _ in range(W):
    if w==0:
      break
    w-=1
    if S[h][w]=="#":
      break
    cnt+=1
  w=sw
  for _ in range(W):
    if w==W-1:
      break
    w+=1
    if S[h][w]=="#":
      break
    cnt+=1
  return cnt

ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,solve(i,j))
print(ans)

### FIXED CODE ###

import numpy as np

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

ups=np.zeros((H,W),dtype=int)
downs=np.zeros((H,W),dtype=int)
rights=np.zeros((H,W),dtype=int)
lefts=np.zeros((H,W),dtype=int)

for i in range(1,H):
    ups[i,:]=(ups[i-1,:]+1)*S[i-1,:]

for i in range(H-2,-1,-1):
    downs[i,:]=(downs[i+1,:]+1)*S[i+1,:]

for i in range(1,W):
    rights[:,i]=(rights[:,i-1]+1)*S[:,i-1]

for i in range(W-2,-1,-1):
    lefts[:,i]=(lefts[:,i+1]+1)*S[:,i+1]

ans=((ups+downs+lefts+rights)*S).max()+1
print(ans)
### BUGGY CODE ###

import math

n = int(input())
cnt=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            cnt +=  math.gcd(k,math.gcd(i,j))

print(cnt)

### FIXED CODE ###

import math

n = int(input())
cnt=0
for i in range(1,n+1):
    for j in range(1,n+1):
        t = math.gcd(i,j)
        for k in range(1,n+1):
            cnt +=  math.gcd(k,t)

print(cnt)
### BUGGY CODE ###

number=list(map(int,input().split()))
N,M,K=number[0],number[1],number[2]
A=list(map(int,input().split()))
B=list(map(int,input().split()))
i=len(A)
C=A
answer=0
l=M
if sum(A)>K:
    while sum(C)>=K:
        i-=1
        C=A[:i]
for j in range(len(C),0,-1):
    C=C[:j]
    while sum(B[:l])>K-sum(C):
        l-=1
        
    key=l+j
    answer=max(answer,key)
print(answer)

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    for j in range(13):
        if S[-(i + 1)] == "?":
            for c in range(10):  # cはi+1番目の桁の値
                dp[i + 1][(mul * c + j) % 13] += dp[i][j]
        else:
            c = int(S[-(i + 1)])  # cはi+1番目の桁の値
            dp[i + 1][(mul * c + j) % 13] += dp[i][j]
    mul *= 10

print(dp[len(S)][5] % INF)


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13

print(dp[len(S)][5])
### BUGGY CODE ###

n = int(input())
a_inputs = [int(i) for i in input().split()]

map_li = [[0 for i in range(n)] for j in range(n)]
ans = 0
for i in range(1,n+1):
    for j in range(i,n+1):
        if abs(a_inputs[i-1]+a_inputs[j-1])==(abs(i-j)):
            ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
a_inputs = [int(i) for i in input().split()]

dic_l={}
dic_r={}
for i in range(n):
    a = a_inputs[i]+(i+1)
    b = (i+1)-a_inputs[i]
    dic_l[a]=dic_l.get(a,0)+1
    dic_r[b]=dic_r.get(b,0)+1

ans=0
for key in dic_l.keys():
    ans+=dic_l[key]*dic_r.get(key,0)
    
print(ans)
### BUGGY CODE ###

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * (2 ** N)
for k in range(1, 2 ** N):
    dp[k] = (A[0], 0), (A[k], k)

digits = []
k = 1
while k < 2 ** N:
    digits.append(k)
    k <<= 1

for bit in range(2, N + 1):
    for ds in itertools.combinations(digits, bit):
        k = sum(ds)
        for rm1, rm2 in itertools.combinations(ds, 2):
            a, b = dp[k - rm1]
            c, d = dp[k - rm2]
            e, f = dp[k]
            ss = sorted({a, b, c, d, e, f})
            dp[k] = ss[-1], ss[-2]

ans = [0] * (2 ** N)
for k in range(1, 2 ** N):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2
ans = itertools.accumulate(ans[1:], max)
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')