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

import sys
input = sys.stdin.readline

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
a = primes(100000)
resemble = []
for i in a:
    if i == 2 or (i+1)//2 not in a:
        pass
    else:
        resemble.append(i)
n = int(input())
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
#print(ans[:30])
for i in range(n):
    l,r = map(int,input().split())
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print(q[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
a = primes(100000)
resemble = []
for i in range(len(a)):
    if a[i]:
        if a[(i+1)//2]:
            resemble.append(i)
n = int(input())
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
#print(ans[:30])
for i in range(n):
    l,r = map(int,input().split())
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print(q[i])
### BUGGY CODE ###

n, m = map(int, input().split(' '))
submits = [input().split() for i in range(m)]

WA_nums = dict()
AC = []
penalty = 0
for submit in submits:
    p, s = submit
    if p in AC:
        continue
    if s == 'AC':
        if p in WA_nums:
            penalty += WA_nums[p]
        AC.append(p)
    else:
        if p in WA_nums:
            WA_nums[p] += 1
        else:
            WA_nums[p] = 1

print(len(AC), penalty)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

WAs = [0] * n
correct = 0
penalty = 0
for i in range(m):
    p, s = input().strip().split(' ')
    p = int(p) - 1
    if WAs[p] == -1:
        continue
    if s == 'AC':
        penalty += WAs[p]
        correct += 1
        WAs[p] = -1
    else:
        WAs[p] += 1

print(correct, penalty)
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    mod = 10**9+7
    count = 0

    for i in range(n-1):
        for j in range(i+1,n):
            count += (a[i]*a[j])%mod
    print(count%mod)



### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    mod = 10**9+7
    sumA = sum(a)
    sumB = 0
    count = 0

    for i in range(n-1):
        sumB+=a[i]
        count += ((sumA-sumB)*a[i])%mod
    print(count%mod)
### BUGGY CODE ###

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

ans=0
for i in range(M,N+2): #M~N+1までやる
    min=sum(list(range(0,i)))
    max=sum(list(range(N+1-i,N+1)))

    ans+=max-min+1

print(ans)

### FIXED CODE ###

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

list=[]
a=1
for i in range(N+2):
    if i==0 or i==N+1:
        list.append(1)
    else:
        list.append(N*i+a)
        a-=2*i

ans=0
for i in range(M,N+2):
    ans+=list[i]

print(ans%1000000007)
### BUGGY CODE ###

l,r = map(int,input().split())

min = 99999999
for i in range(l,r):
  for j in range(i+1,r+1):
    value = (i*j)%2019
    if min > value:
      min = value
    if min == 0:
      break
print(min)

### FIXED CODE ###

l,r = map(int,input().split())

r = min(r, l+4038)

min = 99999999
for i in range(l,r):
  for j in range(i+1,r+1):
    value = (i*j)%2019
    if min > value:
      min = value
print(min)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for _ in range(q):
    l, r = map(int, input().split())
    if r == len(s):
        print(s[l -1:].count('AC'))
    else:
        print(s[l - 1: r].count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
total = [0] * len(s)
for i in range(1, len(s)):
    if s[i] == 'C' and s[i - 1] == 'A':
        total[i] = total[i - 1] + 1
    else:
        total[i] = total[i - 1]
for _ in range(q):
    l, r = map(int, input().split())
    if l == 1:
        print(total[r - 1])
    else:
        print(total[r - 1] - total[l - 1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=[]
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
heapq.heapify(hq)
ans=0
while hq:
    count,i,j=heapq.heappop(hq)
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            heapq.heappush(hq, (count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)

    
    


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq
from collections import deque
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
# heapq.heapify(hq)
ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)
### BUGGY CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

# 2進数のカウンターを使って全探索する

ans = 0
cnt = 0 # カウンター

def get_value(b):
    """
    バイナリ値bを受け取り、X-Yを計算する
    """
    X = 0
    Y = 0
    for i in range(N):
        if b[i] == "1":
            X += V[i]
            Y += C[i]
    return X - Y

while cnt < 2 ** N:
    b = bin(cnt)[2:]
    ans = max(ans, get_value("0" * (N - len(b)) + b))
    cnt += 1

print(ans)

### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

# V_i > C_iなら選ぶ

ans = 0 # 価値の合計

for i in range(N):
	if V[i] > C[i]:
		ans += V[i] - C[i]

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

def main():

    s = str(input())
    t = str(input())

    dp = [[0]*3100 for _ in range(3100)]

    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

    i = len(s)
    j = len(t)
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(s[i-1])
            i -= 1
            j -= 1
    ans.reverse()
    print(''.join(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

s = str(input())
t = str(input())

dp = [[0]*3100 for _ in range(3100)]
# dp[i+1][j+1]: s[i], t[j]まで見たときのLCSの長さ

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

i = len(s)
j = len(t)
ans = ''
while i>0 and j>0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    ans = s[i-1] + ans
    i -= 1
    j -= 1
print(ans)
### BUGGY CODE ###

def resolve():
    N = int(input())
    S = input()
    cnt = 0
    for i in range(0, N-3):
        si = S[i]
        for a in retA(si):
            idx1 = S.find(a, i)
            while idx1 != -1:
                b = retB(a, si)
                cnt += S[idx1+1:].count(b)
                if 2*idx1 - i < N:
                    if S[2*idx1 - i] == b:
                        cnt -= 1
                idx1 = S.find(a, idx1+1)

    print(cnt)

def retA(a):
    if a == 'R':
        A = ('G', 'B')
    elif a == 'G':
        A = ('R', 'B')
    elif a == 'B':
        A = ('R', 'G')
    return A

def retB(a, x):
    if (a == 'R' or x == 'R') and (a == 'G' or x == 'G'):
        b = 'B'
    elif (a == 'B' or x == 'B') and (a == 'G' or x == 'G'):
        b = 'R'
    elif (a == 'B' or x == 'B') and (a == 'R' or x == 'R'):
        b = 'G'
    return b

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    N = int(input())
    S = input()
    rc = S.count('R')
    bc = S.count('B')
    gc = S.count('G')

    cnt = rc * bc * gc

    for i in range(0, N):
        for d in range(0, N):
            j = i + d
            k = j + d
            if N < k+1:
                break
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                cnt -= 1
    print(cnt)

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

#!/usr/bin/env python3
import sys
from collections import defaultdict

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        sArr = [0] * N
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                sArr[i - 1] = int(S[-1])%P
            else:
                sArr[i-1]  = (int(S[-i])*C + sArr[i-2])%P
            counts[sArr[i-1]]+=1
            C*=10
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        current = 0
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                current = int(S[-1])%P
            else:
                current = (int(S[-i])*C + current)%P
            counts[current]+=1
            C=C*10%P
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

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

n,k=map(int,input().split())
H=list(map(int,input().split()))
dp=[10**9]*n
dp[0]=0

i=0
for i in range(n):
    min_step=10**9
    for j in range(1,k+1):
        if i+j>=n:break
        step=abs(H[i]-H[i+j])
        dp[i+j]=min(dp[i]+step,dp[i+j])

print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n

for i in range(1,n):
    dp[i]=min(dp[j] + abs(h[j]-h[i]) for j in range(max(0,i-k),i))

print(dp[-1])
### BUGGY CODE ###


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

left=[]
right=[]
for i in range(M):
    l,r=map(int, input().split())
    left.append(l)
    right.append(r)
#left=np.array(left)
#right=np.array(right)
for i in range(Q):
    p,q=map(int, input().split())
    #l=left>=p
    #r=right<=q
    #ans=(l*r).sum()
    ans=0
    for j in range(M):
        l=left[j]
        r=right[j]
        if p<=l and r<=q:
            ans+=1
    print(ans)

### FIXED CODE ###

N,M,Q=map(int, input().split())
L=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r=map(int, input().split())
    L[l][r]+=1

#print(L)
for i in range(1,N+1):
    for j in range(1,N+1):
        L[i][j]+=L[i][j-1]+L[i-1][j]-L[i-1][j-1]

#print(L)

for i in range(Q):
    p,q=map(int, input().split())
    ans=L[q][q]-L[p-1][q]-L[q][p-1]+L[p-1][p-1]
    print(ans)
### BUGGY CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    S = input().rstrip()

    all = {'R','G','B'}

    res = 0

    for i in range(N-2):
        first = S[i]
        for j in range(i+1,N-1):
            temp = S[j]
            if temp == first:
                continue
            else:
                second = temp
                now = {first,second}
            for k in range(j+1,N):
                if j-i == k-j:
                    continue
                temp = S[k]
                if temp not in now:
                    res += 1

    print(res)




main()


### FIXED CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    S = input().rstrip()

    R = set([])
    G = set([])
    B = set([])

    for i in range(N):
        temp = S[i]
        if temp == 'R':
            R.add(i)
        elif temp == 'G':
            G.add(i)
        else:
            B.add(i)

    all = [R,G,B]

    M = [len(R),len(G),len(B)]
    res = M[0] * M[1] * M[2]
    index = M.index(max(M))

    most = all.pop(index)
    first = all[0]
    second = all[1]

    count = 0

    for f in first:
        for s in second:
            temp1 = s * 2 - f
            temp2 = f * 2 - s
            temp3 = (f + s) // 2
            if (True) & (temp1 in most):
                count += 1
            if (True) & (temp2 in most):
                count += 1
            if (s + f) % 2 == 0:
                if temp3 in most:
                    count += 1

    res -= count
    print(res)




main()
### BUGGY CODE ###

s=input()
t=input()
exi={chr(97+i): False for i in range(26)}
jump={chr(97+i): [] for i in range(26)}
length=len(s)
pointer=0
flag=True
for i,ch in enumerate(s*2):
    exi[ch]=True
    jump[ch].append(i)
for i in range(26):
    if jump[chr(97+i)] !=[]:
        buf=[min(filter(lambda x:x>=j,jump[chr(97+i)]))-j+1 for j in range(length)]
    else:
        buf=0
    jump[chr(97+i)]=buf
for ch in t:
    if exi[ch]:
        pointer+=jump[ch][pointer%length]
    else:
        flag=False
        break
if flag:
    print(pointer)
else:
    print(-1)    

### FIXED CODE ###

s=input()
t=input()
length=len(s)
exi={chr(97+i): False for i in range(26)}
jump={chr(97+i): [0 for _ in range(2*length)] for i in range(26)}
cru={chr(97+i):0 for i in range(26)}
pointer=0
flag=True
for i,ch in enumerate(s*2):
    exi[ch]=True
    for j in range(cru[ch],i+1):
        jump[ch][j]=1+i-j
    cru[ch]=i+1
for ch in t:
    if exi[ch]:
        pointer+=jump[ch][pointer%length]
    else:
        flag=False
        break
if flag:
    print(pointer)
else:
    print(-1)
### BUGGY CODE ###

from itertools import product

n = int(input())
s = input()

temp_dict = {
    "R": [],
    "G": [],
    "B": [],
}
for i, c in enumerate(s):
    temp_dict[c].append(i)
# print(temp_dict)

ans = 0
for temp in list(product(temp_dict["R"], temp_dict["G"], temp_dict["B"])):
    temp = sorted(list(temp))
    if temp[1] - temp[0] != temp[2] - temp[1]:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r * g * b
for i in range(n - 2):
    for j in range(i + 2, n, 2):
        if s[i] != s[(i + j) >> 1] != s[j] != s[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

def main():
  _max = max
  _range = range
  _input = input
  h, w = map(int, _input().split())
  s = [_input() + '#' for _ in _range(h)]
  s.append('#' * (w + 1))

  rt = [[-1] * w for _ in _range(h + 1)]
  tstart = [-1] * (w + 1)
  i = 0
  while i < h + 1:
    si = s[i]
    rti = rt[i]
    ystart = -1
    j = 0
    while j < w + 1:
      tj = tstart[j]
      if si[j] == '#':
        if ystart != -1:
          jy = j - ystart
          for k in _range(ystart, j):
            rti[k] += jy
          ystart = -1
        if tj != -1:
          itj = i - tj
          for k in _range(tj, i):
            rt[k][j] += itj
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tj == -1:
          tstart[j] = i
      j += 1
    i += 1

  print(_max(map(_max, rt)))

main()


### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
def lcm(a,b):
  return a*b//gcd(a,b)
def lcmlist(l):
  n=l[0]
  for i in l[1:]:
    n=lcm(n,i)
  return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
  ans%=1000000007
print(ans)

### FIXED CODE ###

def PrimeFactorization(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


def lcmlist(l):
    from collections import defaultdict
    d = defaultdict(int)
    for i in set(l):
        for k, v in PrimeFactorization(i).items():
            if v > d[k]:
                d[k] = v
    n = 1
    for k, v in d.items():
        n *= k ** v
    return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
ans%=1000000007
print(ans)
### BUGGY CODE ###

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

def get_prime(p):
  result = []
  if p==1:
    return result
  else:
    integers = [1 for _ in range(p+1)]
    integers[0] = 0
    integers[1] = 0
    for i in range(p+1):
      if integers[i] == 1:
        result.append(i)
        for j in range(i,p+1,i):
          integers[j] = 0
    return result
P = get_prime(10**6)
  
def soinsu(a):
  result = []
  i = 0
  p = P[i]
  n = a
  while p <= n:
    if n%p == 0:
      result.append(p)
      while n%p == 0:
        n //= p
    i + 0
    p = P[i]
  return result

dict_prime = dict()

for a in A:
  for p in soinsu(a):
    if p in dict_prime.keys():
      dict_prime[p] += 1
    else:
      dict_prime[p] = 1

if len(dict_prime)==0:
  answer = 'pairwise coprime'
else:
  v = max(dict_prime.values())
  if v == N:
    answer = 'not coprime'
  elif v == 1:
    answer = 'pairwise coprime'
  else:
    answer = 'setwise coprime'

print(answer)

### FIXED CODE ###

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

def get_count(p):
  integers = [1 for _ in range(p+1)]
  integers[0] = 0
  integers[1] = 0
  counts = [0 for _ in range(p+1)]
  for a in A:
    counts[a] += 1
  answer = 0
  for i in range(p+1):
    if integers[i] >= 1:
      count = 0
      for j in range(i,p+1,i):
        count += counts[j]
        integers[j] = 0
      answer = max(answer,count)
  return answer

count = get_count(max(A))
if count == N:
  answer = 'not coprime'
elif count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)
### BUGGY CODE ###

from collections import deque, defaultdict
from time import time

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
S = time()

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1950:
        print(N * (N - 1) // 2)
        exit()
    if not isChanged:
        break

print(-1)


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')


def sol():
    N = int(input())
    A = [deque()] + [deque(map(int, input().split())) for _ in range(N)]

    days = [0] * (N + 1)
    now = [0] * (N + 1)

    que = deque([i + 1 for i in range(N)])

    while que:
        i = que.popleft()
        if not A[i]:
            continue

        a = A[i].popleft()
        if now[a] == i:
            days[a] = days[i] = max(days[a], days[i]) + 1
            que.append(i)
            que.append(a)
            now[a] = now[i] = 0
        else:
            now[i] = a

    for i in range(1, N + 1):
        if A[i]:
            print(-1)
            return
    print(max(days))


sol()
### BUGGY CODE ###

#xorの性質
#AxorA=0、交換法則、結合法則が成立、bitごとに独立して考える！
n=int(input())
a=list(map(int,input().split()))
res=0
for j in range(60):
  s=0 #1の数
  for i in a:
    if (i>>j & 0b1)==0b1:
      s+=1
  res+=2**j*(n-s)*s
print(res%(10**9+7))

### FIXED CODE ###

#xorの性質
#AxorA=0、交換法則、結合法則が成立、bitごとに独立して考える！

import numpy as np

n=int(input())
a=np.array(list(map(int,input().split())))
res=0
for j in range(60):
  s=0 #1の数
  """
  for i in a:
    if (i>>j & 0b1)==0b1:
      s+=1
  """
  s=np.count_nonzero(a>>j&1)
  r=2**j*(n-s)*s
  res=(res+r)%(10**9+7)
print(res)