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

#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
arr = np.array(arr)
x_min  = arr[:,0].min()
x_max = arr[:,0].max()
y_min = arr[:,1].min()
y_max =  arr[:,1].max()
mx = arr[:,2].max()
for i in range(x_min,x_max+1):
    for j in range(y_min,y_max+1):
        for k in range(mx,mx+101):
            for x,y,h in arr:
                if(max(k-abs(i-x)-abs(j-y),0)!=h):
                    break
            else:
                print (i,j,k)
                exit()


### FIXED CODE ###

#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
narr = np.array(arr)
x_min  = narr[:,0].min()
x_max = narr[:,0].max()
y_min = narr[:,1].min()
y_max =  narr[:,1].max()
mx = narr[:,2].max()
for k in range(mx+100,mx-1,-1):
    for i in range(x_min,x_max+1):
        for j in range(y_min,y_max+1):
            for x,y,h in arr:
                h_ = max(k-abs(i-x)-abs(j-y),0)
                if h_ != h:
                    break
            else:
                print (i,j,k)
                exit()
### BUGGY CODE ###

n = int(input())
s = list(input())
b = 27
mod = pow(2, 61) - 1
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
d = {}
for i in range(m, 0, -1):
    h = 0
    for j in range(i):
        h += (x[i - j - 1] * (ord(s[j]) - 96) % mod)
        h %= mod
    d[h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d:
            if (j - m + 1 - d[h]) >= i:
                print(i)
                exit()
        else:
            d[h] = j - m + 1
print(0)

### FIXED CODE ###

n = int(input())
s = list(input())
b = 27
mod = 67280421310721
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
h0 = [0] * m
h0[0] = ord(s[0]) - 96
d = [{} for _ in range(m + 1)]
for i in range(1, m):
    h0[i] = (h0[i - 1] * b + (ord(s[i]) - 96)) % mod
for i in range(m, 0, -1):
    h = h0[i - 1]
    d[i][h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d[i]:
            if (j - i + 1 - d[i][h]) >= i:
                print(i)
                exit()
        else:
            d[i][h] = j - i + 1
print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int,input().split()))
q = int(input())
M=[list(map(int,input().split())) for _ in range(q)]
Sum = sum(A)
d={}
for i in range(n):
    if A[i] not in d:
        d[A[i]]=1
    else:
        d[A[i]]+=1
for i in M:
    a,b=i[0],i[1]
    if a not in d:
        L = list(d.items())
        print(sum([x*y for x,y in L]))
        continue
    elif b in d:
        d[b]+=d[a]
    else:
        d[b]=d[a]
    d.pop(a)
    L = list(d.items())
    print(sum([x*y for x,y in L]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int,input().split()))
q = int(input())
M=[list(map(int,input().split())) for _ in range(q)]
Sum = sum(A)
d={}

for i in range(n):
    if A[i] not in d:
        d[A[i]]=1
    else:
        d[A[i]]+=1

for i in M:
    prev = 0
    a,b=i[0],i[1]
    if a not in d:
        print(Sum)
        continue
    
    elif b in d:
        prev = d[b]*b
        d[b]+=d[a]
    else:
        d[b]=d[a]
    
    Sum += d[b]*b-d[a]*a-prev

    d.pop(a)
    print(Sum)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
MOD = 10**9+7

MAXN = 2*10**5+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

n, k = map(int, (input().split()))
ans = 0
for m in range(min(n-1,k)+1):
    ans += nCr(n,m) * nCr(n-1, n-m-1) % MOD
    ans %= MOD
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
MOD = 10**9+7

MAXN = 2*10**5+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

n, k = map(int, (input().split()))
ans = 0
for m in range(min(n-1,k)+1):
    ans += nCr(n,m) * nCr(n-1, n-m-1) % MOD
    ans %= MOD
print(ans)
### BUGGY CODE ###

def main():
    N,K=map(int,open(0).read().split())
    keta=1
    flag=0
    while flag==0:
        if K**keta<=N and K**(keta+1)>N:
            print(keta+1)
            return
        keta= keta+1
main()

### FIXED CODE ###

def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
    
def main():
    N,K=map(int,input().split())
    print(len(Base_10_to_n(N,K)))
main()
### BUGGY CODE ###

from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    for x, y in xy:
        if x < x0 or x1 < x:
            continue
        elif y < y0 or y1 < y:
            continue
        count += 1
    return count

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])

for a, b in comb:
    x0 = xsort[a][0]
    x1 = xsort[b][0]
    for c, d in comb:
        y0 = ysort[c][1]
        y1 = ysort[d][1]
        if count_points_in_rec(x0, x1, y0, y1) == k:
            ans = min(ans, (x1-x0) * (y1-y0))

print(ans)

### FIXED CODE ###

from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
cum = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + ([xsort[i][0], ysort[j][1]] in xy)

def count_points_in_rec(x0, x1, y0, y1):
    point = cum[x1+1][y1+1] - cum[x0][y1+1] - cum[x1+1][y0] + cum[x0][y0]
    return point

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])
for a, b in comb:
    for c, d in comb:
        if count_points_in_rec(a, b, c, d) == k:
            ans = min(ans, (xsort[b][0]-xsort[a][0]) * (ysort[d][1]-ysort[c][1]))
print(ans)
### BUGGY CODE ###

N = int(input())
A = tuple(map(int,input().split()))
B = list(A)
O = []
S = ''

for i in range(N):
    n = 0
    a = min(B)
    for n in range(len(A)):
        if A[n] == a:
            S += str(n+1) + ' '
            B.remove(min(B))

print(S.lstrip(' '))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
O = [0] * N

for i , a  in enumerate(A): #リストAのインデックスiと値a
    O[a-1] = i+1

print(*O)
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
ab=t3(n-1)

d={i:[] for i in range(1,n+1)}
for a,b in ab:
    d[a].append(b)
    d[b].append(a)

l=list(d.items())
l.sort(key=lambda x:-len(x[1]))
m=len(l[0][1])

d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for node,list1 in l:
    a=node
    color=1
#     print(node,list1)
    for b1 in list1:
        if node>b1:
            a,b=b1,node
        else:
            a,b=node,b1
#         print(a,b)
        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1
#     print(d2)
print(m)
for line in ab:
    print(d2[line])

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
ab=t3(n-1)

d={i:[] for i in range(1,n+1)}
for a,b in ab:
    d[a].append(b)
    d[b].append(a)

l=list(d.items())
l.sort(key=lambda x:-len(x[1]))
m=len(l[0][1])

d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for node,list1 in l:
    a=node
    color=1
#     print(node,list1)
    for b1 in list1:
        if node>b1:
            a,b=b1,node
        else:
            a,b=node,b1
#         print(a,b)
        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1
#     print(d2)
print(m)
for line in ab:
    print(d2[line])
### BUGGY CODE ###

N = int(input())
A = tuple(map(int, input().split()))
print(sum(1 for i in range(N - 1) for j in range(i + 1, N) if A[i] > A[j]))


### FIXED CODE ###

INF = float("inf")
cnt = 0
def merge(A, left, mid, right):
    global cnt
    L = A[left: mid] + [INF]
    R = A[mid: right] + [INF]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            cnt += j
            i += 1
        else:
            A[k] = R[j]
            j += 1
def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(cnt)
### BUGGY CODE ###

n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
def dp(n,W,w,p):
  
  if n==0 or W==0:
    return 0
  elif t[n][W]!=-1:
    return t[n][W]
  else:
    if w[n-1]<=W:
      t[n][W]=max(p[n-1]+dp(n-1,W-w[n-1],w,p),dp(n-1,W,w,p))
    else:
      t[n][W]=dp(n-1,W,w,p)
    return t[n][W]

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit))

### FIXED CODE ###

n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))
### BUGGY CODE ###

def check(a, numlist):
	goal = a+sum(numlist)
	if goal %2 == 1:
		return False
	goal /=2
	oklist =[0]
	for x in numlist:
		addlist = [ok+x for ok in oklist]
		oklist += addlist
	return goal in oklist



s = [len(x) for x in input().split('T')]
x,y = [int(i) for i in input().split()]
x = x-s[0]
sx = s[2::2]
sy = s[1::2]
if check(x,sx) and check(y,sy):
	print("Yes")
else:
	print("No")

### FIXED CODE ###

def check(a, numlist):
	goal = a+sum(numlist)
	if goal %2 == 1:
		return False
	goal /=2
	okset ={0}
	for x in numlist:
		addset = {ok+x for ok in okset}
		okset |= addset
	return goal in okset

s = [len(x) for x in input().split('T')]
x,y = [int(i) for i in input().split()]
x = x-s[0]
sx = s[2::2]
sy = s[1::2]
if check(x,sx) and check(y,sy):
	print("Yes")
else:
	print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
b = []
c = []
l = [list(map(int, input().split())) for i in range(q)]
for i in range(len(l)):
    b.append(l[i][0])
    c.append(l[i][1])
for i in range(q):
    if b[i] in a:
        for j in range(len(a)):
            if a[j] == b[i]:
                a[j] = c[i]
        print(sum(a))
    else:
        print(sum(a)) 
        

### FIXED CODE ###

import collections
 
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for i in range(Q)]
 
sum_ = sum(A)

# 要素の出現回数をカウント
counter = dict(collections.Counter(A))
# print(counter)
 
for i in range(Q):
    b, c = BC[i]
    if not b in counter:
        counter[b] = 0
    if not c in counter:
        counter[c] = 0
    cnt = counter[b]
    sum_ += (c-b)*cnt
    print(sum_)
    counter[b] -= cnt
    counter[c] += cnt
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H, W, D = map(int, input().split())
L = [[int(v) for v in input().split()] for _ in range(H)]
Q = int(input())
QL = [[int(v) for v in input().split()] for _ in range(Q)]

m = [None] * (H * W)
for i in range(H):
    for j in range(W):
        m[L[i][j] - 1] = (i, j)
        
for l, r in QL:
    ans = 0
    c = l - 1
    x, y = m[c]
    while c != r - 1:
        c += D
        nx, ny = m[c]
        
        ans += abs(x - nx) + abs(y - ny)
        x, y = nx, ny
        
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W, D = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(H)]
Q = int(input())
QL = [[int(v) - 1 for v in input().split()] for _ in range(Q)]

m = [None] * (H * W)
for i in range(H):
    for j in range(W):
        m[L[i][j]] = (i, j)

dp = [None] * (H * W)
for i in range(D):
    dp[i] = 0
    for j in range(i + D, H * W, D):
        x, y = m[j - D]
        nx, ny = m[j]
        
        dp[j] = dp[j - D] + abs(x - nx) + abs(y - ny)

for qx, qy in QL:
    print(dp[qy] - dp[qx])
### BUGGY CODE ###

H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    minB = min(B)
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            dp[h + 1] = min(dp[h + 1], dp[h] + minB)
            hp = min(h + A[n], H)
            dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))

### FIXED CODE ###

H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            hp = min(h + A[n], H)
            dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))
### BUGGY CODE ###

import sys
import collections

n, m = map(int, sys.stdin.readline().split())
p = list(range(n))
r = [set([i]) for i in range(n)]


def li_(): return [int(x)-1 for x in sys.stdin.readline().split()]


def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


def union(x, y):
    x, y = find(x), find(y)
    p[y] = x
    r[x] = r[x] | r[y]
    r[y] = r[x]


flist = [0] * m
elist = [0] * m
for i in range(m):
    flist[i], elist[i] = li_()

flist.reverse()
elist.reverse()

ans = [0] * m
ans[0] = int(n*(n-1)/2)

for i in range(m-1):
    a, b = flist[i], elist[i]
    if find(a) != find(b):
        union(a, b)
    tmp = ans[0]
    for j in range(n):
        find(j)
    c = sorted(collections.Counter(p).values(), reverse=True)
    for j in c:
        if j == 1:
            break
        tmp -= int(j * (j - 1) / 2)
    ans[i + 1] = tmp
    if tmp == 0:
        break

for i in range(m):
    print(ans[m-i-1])


### FIXED CODE ###


import sys
import collections

n, m = map(int, sys.stdin.readline().split())
p = list(range(n))
r = [1] * n


def li_(): return [int(x)-1 for x in sys.stdin.readline().split()]


def find(x):
    global p
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


def union(x, y):
    x, y = find(x), find(y)
    if y > x:
        x, y = y, x
    p[y] = x
    r[x] += r[y]
    r[y] = r[x]


flist = [0] * m
elist = [0] * m
for i in range(m):
    flist[i], elist[i] = li_()

flist.reverse()
elist.reverse()

ans = [0] * m
ans[0] = int(n*(n-1)/2)

for i in range(m-1):
    a, b = flist[i], elist[i]
    if find(a) != find(b):
        ans[i + 1] = ans[i] - r[find(a)]*r[find(b)]
        union(a, b)
    else:
        ans[i+1] = ans[i]
    if ans[i+1] == 0:
        break

for i in range(m):
    print(ans[m-i-1])
### BUGGY CODE ###

from collections import defaultdict


def main():
    S = input()
    S = S[::-1]
    MOD = 10**9 + 7

    DP_table = defaultdict(int)
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    power_ten = 1
    for i in range(1, len(S)):
        digit = S[i]
        power_ten *= 10
        if digit == '?':
            for j in range(10):
                devided = j * power_ten
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * power_ten + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

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

# 最初に入れておくとinputが早くなる
import sys
input = sys.stdin.readline

# スタック最大数をセット
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
ans = [0] * n

for i in range(0, a[0]*2+1, 2):
    ans[0] = i
    tempa = a.copy()
    for j in range(n):
        tempa[j % n] = ans[j % n] // 2
        if(j+1 != n):
            ans[(j+1) % n] = (a[j]-tempa[j])*2
    if (ans[0] == (a[n - 1] - tempa[n - 1]) * 2):
        break
# tempa[1 % 3] = ans[1 % 3]/2
# ans[2 % 3] = (a[1]-tempa[1])*2
# tempa[2 % 3] = ans[2 % 3]/2
# ans[3 % 3] = (a[2 % 3]-tempa[2 % 3])*2
# tempa[3 % 3] = ans[3 % 3] / 2
# print(a)
# print(tempa)
print(*ans)

### FIXED CODE ###

# 最初に入れておくとinputが早くなる
import sys
import numpy as np
input = sys.stdin.readline

# スタック最大数をセット
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
b = 0
for i in range(1, n-1, 2):
    b += a[i]
ans[0] = sum(a)-2*b

tempa = [0]*n
for j in range(n):
    tempa[j] = ans[j % n] // 2
    if(j+1 != n):
        ans[(j + 1) % n] = (a[j] - tempa[j]) * 2
    #print(a, tempa, ans)
print(*ans)
### BUGGY CODE ###

n, q = list(map(int, input().split()))
s = input()

def f(i):
    cnt = 0
    for j in range(i-1):
        #print(s[j:j+2])
        if s[j:j+2] == 'AC':
            cnt += 1
    return cnt

for _ in range(q):
    l, r = list(map(int, input().split()))
    #print(s[l-1:r])
    print(f(r) - f(l))

### FIXED CODE ###

n, q = list(map(int, input().split()))
s = input()

#def f(i):
#    cnt = 0
#    for j in range(i-1):
#        #print(s[j:j+2])
#        if s[j:j+2] == 'AC':
#            cnt += 1
#    return cnt

ftab = [0]*(n+1)
cnt = 0

for i in range(n-1):
    if s[i:i+2] == 'AC':
        cnt += 1
    ftab[i+2] = cnt

for _ in range(q):
    l, r = list(map(int, input().split()))
    #print(s[l-1:r])
    print(ftab[r] - ftab[l])
### BUGGY CODE ###

import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

count_list = [0 for i in range(61)]
def counts(count_list, a):
    for i in range(61):
        if a <= 0:
            break
        count_list[i] += a % 2
        a = a // 2
    return count_list

A.reverse()
ans = 0
for i in range(N-1):
    count_list = counts(count_list, A[i])
    hikaku = counts([0 for i in range(61)], A[i + 1])
    for j in range(61):
        if hikaku[j] == 1:
            ans += (i+1 - count_list[j]) * 2 ** j % mod
        else:
            ans += count_list[j] * 2 ** j % mod
        ans = ans % mod
print(ans)


### FIXED CODE ###

import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

count_list = [0 for i in range(61)]
def counts(count_list, a):
    for i in range(61):
        if a <= 0:
            break
        count_list[i] += a % 2
        a = a // 2
    return count_list

A.reverse()
ans = 0
ans_list = [0 for i in range(61)]
for i in range(N-1):
    count_list = counts(count_list, A[i])
    hikaku = counts([0 for i in range(61)], A[i + 1])
    for j in range(61):
        if hikaku[j] == 1:
            ans_list[j] += i+1 - count_list[j]
        else:
            ans_list[j] += count_list[j]

for i in range(61):
    ans += ans_list[i] * (2 ** i % mod)
    ans = ans % mod
print(ans)
### BUGGY CODE ###

N = int(input())
N1 = []

for n in range(1, (N + 1)):
    N1.append(2 * n)

for i in N1:
    if i % N == 0:
        print(i)
        break


### FIXED CODE ###

N = int(input())
if N % 2 == 0:
    print(N)
else:
    print(2*N)
### BUGGY CODE ###

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

base = M // N
while (M - (base * N)) % base != 0:
	base -= 1
print(base)


### FIXED CODE ###

import math

def get_divs(a):
	divs = [1, a]
	for n in range(2, int(a ** 0.5)):
		if a % n == 0:
			divs.append(n)
			divs.append(a // n)
	return divs

def main():
	N, M = map(int, input().split())

	divs = get_divs(M)
	divs.sort()
	divs.reverse()
	divs = filter(lambda x:x <= M // N, divs)

	for div in divs:
		if (M - N * div) % div == 0:
			print(div)
			break

main()
### BUGGY CODE ###

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

ans = 0
for i in range(N - 1):
    ans += A[i] * ((sum(A[i + 1:]) % mod)) % mod
print(ans % mod)

### FIXED CODE ###

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

cum = [0 for _ in range(N)]
cum[0] = A[0]
for i in range(N - 1):
    cum[i + 1] = (cum[i] + A[i + 1]) % mod

ans = 0
for i in range(N - 1):
    ans += (A[i] * (cum[N - 1] - cum[i])) % mod
print(ans % mod)