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

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

L = []

def ans(tf):
  if tf:
    print("Yes")
  else:
    print("No")

for x in a:
  for i in range(len(L)):
    if L[i][0] == x:
      L[i][1] += 1
      break
  else:
    L.append([x, 1])
    if len(L) >= 3:
      ans(False)

if len(L) == 1:
  x = L[0][0]
  if x == N - 1 or x <= N // 2:
    ans(True)
  else:
    ans(False)
else:
  x, xn = L[0]
  y, yn = L[1]
  if abs(x - y) != 1:
    ans(False)
    exit()
  if x < y:
    x, y = y, x
    xn, yn = yn, xn
  if yn >= x:
    ans(False)
    exit()
  n = x - yn
  if n <= xn // 2:
    ans(True)
  else:
    ans(False)

### FIXED CODE ###

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

L = []

def ans(tf):
  if tf:
    print("Yes")
  else:
    print("No")
  exit()

for x in a:
  for i in range(len(L)):
    if L[i][0] == x:
      L[i][1] += 1
      break
  else:
    L.append([x, 1])
    if len(L) >= 3:
      ans(False)

if len(L) == 1:
  x = L[0][0]
  if x == N - 1 or x <= N // 2:
    ans(True)
  else:
    ans(False)
else:
  x, xn = L[0]
  y, yn = L[1]
  if abs(x - y) != 1:
    ans(False)
    exit()
  if x < y:
    x, y = y, x
    xn, yn = yn, xn
  if yn >= x:
    ans(False)
    exit()
  n = x - yn
  if n <= xn // 2:
    ans(True)
  else:
    ans(False)
### BUGGY CODE ###

N=int(input())
a=[]
for _ in range(N):
    a.append(int(input()))
for i in range(N):
    new=a[:i]+a[i+1:]
    print(max(new))

### FIXED CODE ###

N=int(input())
a=[]
for _ in range(N):
    a.append(int(input()))
x=sorted(a,reverse=True)
m1=x[0]
m2=x[1]
for i in a:
    if i==m1:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

N = int(input())
P = list(map(float, input().split()))

dp = [[0.0] * (N+1) for _ in range(N+1)]

dp[0][0] = 1

for i in range(1, N+1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j] * (1-P[i-1])
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * P[i-1]

ans = 0.0
for i in range(N//2+1, N+1):
    ans += dp[N][i]

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(float, input().split()))

dp = [[0.0] * (N+1) for _ in range(N+1)]

dp[0][0] = 1

for i in range(N):
    for j in range(i+1):
        dp[i+1][j] += dp[i][j] * (1-P[i])
        dp[i+1][j+1] += dp[i][j] * P[i]

ans = 0.0
for i in range(N//2+1, N+1):
    ans += dp[N][i]

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

a,b = map(int,input().split())

count = 1

for i in range(a,b+1):
    count *= i

if count == 0:
    print("Zero")
elif count > 0:
    print("Positive")
else:
    print("Negative")

### FIXED CODE ###

a,b = map(int,input().split())

if 0 < a <= b:
    print("Positive")
elif a <= b < 0:
    if (b - a + 1) % 2 == 0:
        print("Positive")
    else:
        print("Negative")
else:
    print("Zero")
### BUGGY CODE ###

S = input()
s = list(S)
for i in range(len(s)):
    s[i] = int(s[i])
p = []
p.append(s[len(s)-1])
for i in range(1,len(s)):
    p.append((p[i-1]+s[len(s)-i-1]*(10**i))%2019)
p.sort()
u = 0
for i in range(len(p)):
    if p[i] == 0:
        u = u+1
    else:
        break
r = 1
q = []
for i in range(len(p)-1):
    if p[i] == p[i+1]:
        r = r+1
    else:
        if r != 1:
            q.append(r)
            r = 1
w = 0
for i in range(len(q)):
    w = w + int(q[i]*(q[i]-1)/2)
print(w+u)

### FIXED CODE ###

S = input()
s = list(S)
for i in range(len(s)):
    s[i] = int(s[i])
p = []
p.append(s[len(s)-1])
for i in range(1,len(s)):
    p.append((p[i-1]+s[len(s)-i-1]*pow(10,i,2019))%2019)
p.sort()
u = 0
for i in range(len(p)):
    if p[i] == 0:
        u = u+1
    else:
        break
r = 1
q = []
for i in range(len(p)-1):
    if p[i] == p[i+1]:
        r = r+1
    else:
        if r > 1:
            q.append(r)
            r = 1
q.append(r)
w = 0
for i in range(len(q)):
    w = w + int(q[i]*(q[i]-1)/2)
print(w+u)
### BUGGY CODE ###

import heapq


def dijkstra(s):
    color=["white" for _ in range(n)]
    D=[inf for _ in range(n)]

    M=[[] for _ in range(n)]
    for i in range(n-1):
        M[i].append((1,i+1))
        M[i+1].append((1,i))
    M[x-1].append((1,y-1))
    M[y-1].append((1,x-1))

    D[s]=0

    H=[(0,s)]
    heapq.heapify(H)

    while len(H)>=1:
        u=heapq.heappop(H)[1]
        if color[u]=="black":continue
        color[u]="black"

        V=[(i,j) for i,j in M[u] if color[j]!="black"]
        while len(V)!=0:
            for i,j in V:
                if D[u]+i<D[j]:
                    D[j]=D[u]+i
                    color[j]="gray"
                    heapq.heappush(H,(D[j],j))
            break
    return D


inf=float("inf")
n,x,y=map(int,input().split())

A=[0]*n
for i in range(n):
    for j in dijkstra(i)[:i]:
        A[j] +=1

for i in A[1:]:
    print(i)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)


def BFS(s):
    color=["white" for _ in range(n)]
    D=[float("inf") for _ in range(n)]

    color[s-1]="gray"
    D[s-1]=0
    queue=deque([s-1])

    while len(queue)!=0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                color[i]="gray"
                D[i]=D[u]+1
                queue.append(i)
        color[u]="black"

    return D


n,x,y=map(int,input().split())

M=[[] for _ in range(n)]
for i in range(n-1):
    M[i].append(i+1)
    M[i+1].append(i)
M[x-1].append(y-1)
M[y-1].append(x-1)

C=[0]*n
for i in range(n):
    for j in BFS(i+1)[i:]:
        C[j] +=1

for i in C[1:]:
    print(i)
### BUGGY CODE ###

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

# N is the number of vertices
# M is the number of edges

g = {}
for v in range(1, N+1):
    g[v] = []

for _ in range(M):
    u,v = map(int, input().split())
    g[u].append(v)

S,T = map(int, input().split())
# S is start
# T is target


def move(start, steps):
    current_locations = set()
    next_locations = set()
    current_locations.add(start)

    for _ in range(steps):
        nxt = set()
        for v in current_locations:
            for v2 in g.get(v, ()):
                nxt.add(v2)
        current_locations = nxt

    return current_locations

visiting = [(S,0)]
visited = {}

while visiting:
    v,kkp = visiting.pop(0)
    if v in visited:
        continue

    visited[v] = kkp
    if v == T:
        break

    for v2 in move(v,3):
        if v2 in visiting or v2 in visited:
            continue
        visiting.append((v2,kkp+1))

if T in visited:
    print(visited[T])
else:
    print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
E = {}
for v in range(1,N*3+1):
    E[v] = []
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v+N)
    E[u+N].append(v+2*N)
    E[u+2*N].append(v)
S, T = map(int, input().split())
dist = [-1 for _ in range(3*N)]
dist[S-1] = 0

q = []
q.append(S)
while q:
    n = q.pop(0)
    if n == T:
        break
    for t in E[n]:
        if dist[t-1] < 0:
            dist[t-1] = dist[n-1] + 1
            q.append(t)
print(-1 if dist[T-1] < 0 else dist[T-1] // 3)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import numpy as np
from numba import jit



r, c, k = map(int, input().split())
itm = [[0]*(c) for _ in range(r)]
for i in range(k):
    ri, ci, vi = map(int, input().split())
    itm[ri-1][ci-1] = vi


@jit
def f(r,c,itm):
    dp = np.zeros((3005, 3005, 4), dtype=np.int64)
    for i in range(r):
        for j in range(c):
            nowv = itm[i][j]
            dp[i][j][1:] = np.maximum(dp[i][j][1:], dp[i][j][:3] + nowv)
            dp[i+1][j][0] = max(dp[i+1][j][0], max(dp[i][j]))
            dp[i][j+1][:] = np.maximum(dp[i][j+1][:], dp[i][j][:])
    print(max(dp[r-1][c-1]))

f(r,c,itm)

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

r, c, k = map(int, input().split())
itm = [[0]*(c) for _ in range(r)]
for i in range(k):
    ri, ci, vi = map(int, input().split())
    itm[ri-1][ci-1] = vi

dp0 = [[0]*4 for c_ in range(3005)]
dp1 = [[0]*4 for c_ in range(3005)]

for i in range(r):
    for j in range(c):
        nowv = itm[i][j]
        dp0[j][3] = max(dp0[j][3], dp0[j][2] + nowv)
        dp0[j][2] = max(dp0[j][2], dp0[j][1] + nowv)
        dp0[j][1] = max(dp0[j][1], dp0[j][0] + nowv)

        dp0[j+1][0] = max(dp0[j+1][0], dp0[j][0])
        dp0[j+1][1] = max(dp0[j+1][1], dp0[j][1])
        dp0[j+1][2] = max(dp0[j+1][2], dp0[j][2])
        dp0[j+1][3] = max(dp0[j+1][3], dp0[j][3])

        dp1[j][0] = max(dp1[j][0], max(dp0[j]))
    dp0 = dp1.copy()

print(max(dp1[c-1]))
### BUGGY CODE ###

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

C = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  L, R = list(map(int, input().split()))
  for j in range(1, L+1):
    for k in range(R, N+1):
      C[j][k] += 1

for i in range(Q):
  p, q = list(map(int, input().split()))
  print(C[p][q])

### FIXED CODE ###

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

C = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  L, R = list(map(int, input().split()))
  C[L][R] += 1

A = [[0] * (N+1) for i in range(N)]
for i in range(1,N+1):
  A[0][i] = C[i][i]
for i in range(1,N):
  A[1][i] = A[0][i] + A[0][i+1] + C[i][i+1]
for i in range(2,N):
  for j in range(1,N+1-i):
    A[i][j] = A[i-1][j] + A[i-1][j+1] - A[i-2][j+1] + C[j][i+j]
    
for i in range(Q):
  p, q = list(map(int, input().split()))
  print(A[q-p][p])
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

ans = sum(A)
for i in range(N):
  if A[i] < 0:
    if i != N-1:
      A[i] = A[i] * -1
      A[i+1] = A[i+1] * -1
      ans = max(ans, sum(A))

print(ans)


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

count = 0
for i in range(N):
  if A[i] <0:
    count = count + 1
    A[i] = A[i] * -1

if 0 in A:
  ans = sum(A)
else:
  if count%2 == 0:
    ans = sum(A)
  else:
    ans = sum(A) - 2*min(A)

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

N,*s=open(0).read().split()
s = ["".join(sorted(s_)) for s_ in s]
cnt = 0
for i in range(len(s)):
  cnt += (s.count(s[0])-1)
  s.pop(0)
print(cnt)

### FIXED CODE ###

n,*S=open(0).read().split()

from collections import defaultdict
dic = defaultdict(int)

for s in S:
  dic["".join(sorted(s))]+=1

print(sum([(v*(v-1))//2 for v in dic.values()]))
### BUGGY CODE ###

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)
n = int(input())
a = list(map(int, input().split()))
res = prod(a)
if res > (10**18):
    print(-1)
    exit()
print(res)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
res = 1
A.sort()
for i in range(N):
    res *= A[i]
    if res > (10 ** 18):
        print(-1)
        exit()
    elif res == 0:
        print(0)
        exit()
print(res)
### BUGGY CODE ###

import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<1:
    print('No')
    sys.exit()
v = cnt.index(4)
used = [False]*n
for v0 in G[v]:
    now = v0
    used[v0] = True
    while True:
        for nv in G[now]:
            if used[nv]:
                continue
            now = nv
            used[now] = True
        if now == v0:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')
        

### FIXED CODE ###

import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<=1:
    print('No')
    sys.exit()
v = cnt.index(4)
for v0 in G[v]:
    now = v0
    p = v
    while True:
        for nv in G[now]:
            if nv == p:
                continue
            p = now
            now = nv
            break
        if now == v:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')
### BUGGY CODE ###

n=int(input())
al=list(map(int,input().split()))
arr=[0,0,0]
for i in al:
    arr[i-1]+=1
dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
vis=[[[False for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
 
def solve(a,b,c):
    if a==b==c==0:
        return 0
    if vis[a][b][c]:
        return dp[a][b][c]
    vis[a][b][c]=True
    if c:
        dp[a][b][c]+=solve(a,b+1,c-1)*c/n
    if b:
        dp[a][b][c]+=solve(a+1,b-1,c)*b/n
    if a:
        dp[a][b][c]+=solve(a-1,b,c)*a/n
    dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    return dp[a][b][c]

print(solve(arr[0],arr[1],arr[2]))

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1-c):
            for a in range(n-b-c+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

from scipy.misc import comb

def main():
    N, M, K = LI()

    rows = M*M*sum([d * (N-d) for d in range(1, N)])
    cols = N*N*sum([d * (M-d) for d in range(1, M)])
    ans = (rows + cols) * comb(M*N-2, K-2, exact=True) % MOD

    print(ans)

main()

### FIXED CODE ###

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def main():
    N, M, K = LI()

    rows = M*M*sum([d * (N-d) for d in range(1, N)])
    cols = N*N*sum([d * (M-d) for d in range(1, M)])
    ans = (rows + cols) * cmb(M*N-2, K-2, MOD) % MOD

    print(ans)

main()
### BUGGY CODE ###

s = list(map(int, list(input())))[::-1]
n = len(s)
c = [0]*2019
c[0]+=1
t = 0
ten = 1
for i in range(n):
    t = (t+s[i]*ten) % 2019
    ten*=10
    c[t]+=1
ans = 0
ans = sum(cc*(cc-1)//2 for cc in c)
print(ans)

### FIXED CODE ###

s = input()

n = len(s)
c = [0]*2019
c[0]+=1
t = 0
digit = 1
for ss in s[::-1]:
    t = (t+int(ss)*digit) % 2019
    digit = (digit * 10) % 2019
    c[t]+=1
ans = 0
ans = sum(cc*(cc-1)//2 for cc in c)
print(ans)
### BUGGY CODE ###

s=input()
K=int(input())
if len(s)<5:
    s_len = len(s)
else:
    s_len = 5
ans=list()
for length in range(1,s_len + 1):
    for pos in range(0,len(s)-length+1):
        tmp = s[pos:pos+length]
        if tmp not in ans:
            ans.append(tmp)
            ans.sort()

print(ans[K-1])


### FIXED CODE ###

s=input()
K=int(input())
if len(s)<5:
    s_len = len(s)
else:
    s_len = 5
ans=list()
for length in range(1,s_len + 1):
    for pos in range(0,len(s)-length+1):
        tmp = s[pos:pos+length]
        if tmp not in ans:
            ans.append(tmp)
    ans.sort()
    if len(ans)>5:
        del ans[5:len(ans)+1]


print(ans[K-1])
### BUGGY CODE ###

N,Q = map(int,input().split())
G = [[]for i in range(N+1)]

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = [0]*(N+1)
for i in range(Q):
    p,x = map(int,input().split())
    C[p] += x

stack = [1]
list = []
while len(stack) > 0:
    a = stack.pop(0)
    list.append(a)
    for b in G[a]:
        G[b].remove(a)
        stack.append(b)
        C[b] += C[a]
C.pop(0)
print(*C)

### FIXED CODE ###

N,Q = map(int,input().split())
G = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
C = [0]*(N)
for i in range(Q):
    p,x = map(int,input().split())
    C[p-1] += x
from collections import deque
d=deque()
d.append(0)
t = [False]*(N)
t[0] = True
while d:
    a = d.popleft()
    for b in G[a]:
        if not t[b]:
            t[b] = True
            d.append(b)
            C[b] += C[a]
print(*C)
### BUGGY CODE ###

N, K = map(int, input().split())
lis = list(map(int, input().split()))
p = 10**9+7
fac_lis = [[0] for i in range(N)]
fac_lis[0] = 1
max_ans = 0
min_ans = 0

for i in range(1,N):
  fac_lis[i] = fac_lis[i-1]*(i+1)

def combi(n,k,num_lis,big_num):
  if n == k:
    return 1
  else:
  	return num_lis[n-1]*pow(num_lis[k-1], big_num-2, big_num)*pow(num_lis[n-k-1], big_num-2, big_num) % big_num

lis.sort()
for i in range(K-1,N):
  max_ans += lis[i]*combi(i, K-1, fac_lis, p) % p
  
for i in range(N-K+1):
  min_ans += lis[i]*combi(N-(i+1), K-1, fac_lis, p) % p

ans = (max_ans - min_ans) % p
print(ans)

### FIXED CODE ###

# フェルマーの小定理
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
m = 1000000007
 
fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % m
 
 
def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m
 
 
A.sort(reverse=True)
maxX = 0
for i in range(N - K + 1):
    maxX += A[i] * mcomb(N - (i + 1), K - 1)
    maxX %= m

A.sort()
minX = 0
for i in range(N - K + 1):
    minX += A[i] * mcomb(N - (i + 1), K - 1)
    minX %= m

print((maxX - minX) % m)
### BUGGY CODE ###

from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def bfs(field, sx, sy, gx, gy, seen):
    queue = deque([(sx, sy)])
    seen[sx][sy] += 1
    
    while queue:
        x, y = queue.popleft()
        if (x, y) == (gx, gy):
            return seen[x][y]

        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            nx = x + dx
            ny = y + dy
            
            if seen[nx][ny] == -1 and field[nx][ny] != "#":
                seen[nx][ny] = seen[x][y] + 1
                queue.append((nx, ny))


def main():
    H,W = map(int, readline().split())
    c = ["#" * (W + 2)]
    for _ in range(H):
        c.append("#" + readline().strip() + "#")
    c.append("#" * (W + 2))

    ans = 0
    for sx in range(1,H+1):
        for sy in range(1,W+1):
            if c[sx][sy] == "#":
                continue
            for gx in range(1,H+1):
                for gy in range(1,W+1):
                    if (gx, gy) == (sx, sy):
                        continue
                    if c[gx][gy] == "#":
                        continue
                    seen = [[-1] * (W + 2) for i in range(H+2)]
                    dist = bfs(c, sx, sy, gx, gy, seen)
                    ans = max(ans, dist)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def bfs(field, sx, sy, seen):
    queue = deque([(sx, sy)])
    seen[sx][sy] += 1
    
    while queue:
        x, y = queue.popleft()

        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            nx = x + dx
            ny = y + dy
            
            if seen[nx][ny] == -1 and field[nx][ny] != "#":
                seen[nx][ny] = seen[x][y] + 1
                queue.append((nx, ny))

    return seen[x][y]


def main():
    H,W = map(int, readline().split())
    c = ["#" * (W + 2)]
    for _ in range(H):
        c.append("#" + readline().strip() + "#")
    c.append("#" * (W + 2))

    ans = 0
    for sx in range(1,H+1):
        for sy in range(1,W+1):
            if c[sx][sy] == ".":
                seen = [[-1] * (W + 2) for i in range(H+2)]
                dist = bfs(c, sx, sy, seen)
                ans = max(ans, dist)

    print(ans)


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

S=input()
Q=int(input())
q=[input().split() for _ in range(Q)]

for i in range(Q):
    if q[i][0]=="1":
        S=S[::-1]
    else:
        if q[i][1]=="1":
            S=q[i][2]+S
        elif q[i][1]=="2":
            S=S+q[i][2]
print(S)

### FIXED CODE ###

S=input()
Q=int(input())
q=[input().split() for _ in range(Q)]

count=0
f=""
b=""

for i in range(Q):
    if q[i][0]=="1":
        count+=1
    else:
        if q[i][1]=="1":
            if count%2==0:
                f=q[i][2]+f
            else:
                b+=q[i][2]
        elif q[i][1]=="2":
            if count%2==1:
                f=q[i][2]+f
            else:
                b+=q[i][2]

if count%2==1:
    S=f+S+b
    print(S[::-1])
else:
    print(f+S+b)
### BUGGY CODE ###

import math, heapq
N, K = map(int, input().split())

a = list(map(int, input().split()))
a.sort(reverse=True)
lst = []
for i in a:
    lst.append([-i, 0])

heapq.heapify(lst)

for i in range(K):
    p = heapq.heappop(lst)
    p[1] += 1
    p[0] = p[0] * p[1] / (p[1] + 1)
    heapq.heappush(lst, p)
p = heapq.heappop(lst)
print(math.ceil(-p[0]))

### FIXED CODE ###

import math
N, K = map(int, input().split())

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

def cal(x):
    s = 0
    for aa in a:
        s += math.ceil(aa / x) - 1
    if s <= K: return True
    else: return False

l = 0
r = max(a)
while abs(r - l) > 1:
    mid = (l + r) // 2
    if cal(mid):
        r = mid
    else:
        l = mid
print(r)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mod = 7 + 10**9
A = []
leng = len(format(max(a), 'b'))
bit_acc = [0 for i in range(leng)]
for i in range(n):
    A.append(list(map(int, format(a[i], 'b').zfill(leng))))
for i in range(leng):
    bit_acc[i] = sum([A[j][i] for j in range(n)]) 
ans = 0
p = [pow(2,leng - j - 1,mod) for j in range(leng)]
for i in range(n):
    for j in range(leng):
        if A[i][j] == 1:
            ans += (n - bit_acc[j]) * p[j]
        else:
            ans += bit_acc[j] * p[j]
print((ans * 500000004) % mod)



### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()