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

def string_formation():
    s = str(input().strip())
    q = int(input())
    flag = 0
    for _ in range(q):
        line = input()
        if len(line) == 1:
            flag = (flag + 1) % 2
        else:
            if (line[2] == '1' and flag == 1) \
            or (line[2] == '2' and flag == 0):
                s += line[-1]
            else:
                s = line[-1] + s
    if flag: return ''.join(reversed(s))

    return s
print(string_formation())

### FIXED CODE ###

S = input()
Q = int(input())
flip = 0
head = []
tail = []
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    F = int(F)-1
    if F^flip == 1:
      tail.append(C)
    else:
      head.append(C)
  else:
    flip ^= 1
if flip:
  head, tail = tail, head
  S = S[::-1]
head = ''.join(head[::-1])
tail = ''.join(tail)
print(head+S+tail)
### BUGGY CODE ###

from collections import deque, defaultdict

S = input()

L = int(S)
S = S[::-1]
cnt = defaultdict(int)

tmp = 0
answer = 0
for i, s in enumerate(S):
    tmp += int(s) * 10 ** i
    if tmp % 2019 == 0:
        answer += cnt[0] + 1
    else:
        answer += cnt[tmp % 2019]
    cnt[tmp % 2019] += 1
    #print(tmp, answer)

print(answer)

### FIXED CODE ###

from collections import deque, defaultdict

S = input()

L = int(S)
S = S[::-1]
cnt = defaultdict(int)

tmp = 0
answer = 0
for i, s in enumerate(S):
    tmp = (tmp + int(s) * pow(10, i, 2019)) % 2019
    #print(tmp)
    if tmp % 2019 == 0:
        answer += cnt[0] + 1
    else:
        answer += cnt[tmp % 2019]
    cnt[tmp % 2019] += 1
    #print(tmp, answer)

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

def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())+1
    dp=[0]*n*2
    for h,a in zip(map(int,input().split()),map(int,input().split())):
        l,r,s=n,h+n,0
        while l<r:
            if l&1:
                t=dp[l]
                if t>s:s=t
                l+=1
            if r&1:
                r-=1
                t=dp[r]
                if t>s:s=t
            l>>=1
            r>>=1
        s+=a
        i=h+n
        if s>dp[i]:
            dp[i]=s
            i>>=1
            while i:
                s,t=dp[i+i],dp[i-~i]
                if t>s:s=t
                if s>dp[i]:dp[i]=s
                else:break
                i>>=1
    print(dp[1])
main()

### FIXED CODE ###

class SegTree():
    def __init__(self,size,unit,f):
        self.size=size
        self.data=[unit for _ in range(2*size)]
        self.unit=unit
        self.f=f
    def update(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=f(c[i],x)
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def query(self,l,r):
        c,f=self.data,self.f
        x,y=self.unit,self.unit
        l+=self.size
        r+=self.size
        while l<r:
            if l&1:
                x=f(x,c[l])
                l+=1
            if r&1:
                r-=1
                y=f(c[r],y)
            l>>=1
            r>>=1
        return f(x,y)
def main():
    n,*a=map(int,open(0).read().split())
    dp=SegTree(n+1,0,lambda a,b:a if a>b else b)
    for h,a in zip(a,a[n:]):dp.update(h,dp.query(0,h)+a)
    print(dp.data[1])
main()
### BUGGY CODE ###

#bit全探索する
INF = 5000

def dp(n, a, b, c, Ma, Mb):
    INF =  5000
    if n == 0: #終端
        List = [[0, 0, 0], [a[n], b[n], c[n]]]
        if a[n] * Mb == b[n] * Ma:
            cost = c[n]
        else:
            cost = INF
    else: #n-1をもとにnについて計算
        previous = dp(n-1, a, b, c, Ma, Mb)
        List = previous[0].copy()
        cost = previous[1]
        for x in previous[0]:
            C = x[2] + c[n]
            if C < cost:
                A = x[0] + a[n]
                B = x[1] + b[n]
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C         
    return List, cost


N, Ma, Mb = map(int, input().split())
a, b, c = [], [], []
for i in range(N):
    Lst = [int(x) for x in input().split()]
    a.append(Lst[0])
    b.append(Lst[1])
    c.append(Lst[2])
ans = dp(N-1, a, b, c, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
### BUGGY CODE ###

import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heapq.heappush(q, e)
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])
    return d


N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    s, t, c = map(int, input().split())
    E[s-1].append([c, t-1])
for i in range(N-1):
    E[i+1].append([0, i])

A = dijkstra(0, N, E)

ans = A[N-1]
if ans == float("inf"):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, E):
    inf = float('inf')
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    heapq.heapify(q)
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = map(int, input().split())
        E[s-1].append([c, t-1])
    for i in range(N-1):
        E[i+1].append([0, i])

    A = dijkstra(0, E)

    ans = A[N-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


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

import re
n, q = map(int, input().split())
S = input()
for _ in range(q):
    l, r = map(int, input().split())
    SS = S[l-1:r]
    rl = re.findall(r'AC', SS)
    print(len(rl))



### FIXED CODE ###

n, q = map(int, input().split())
S = input()
CS = [0]
cur = 0
for i in range(1, n):
    if S[i-1] + S[i] == 'AC':
        cur += 1
        CS.append(cur)
    else:
        CS.append(cur)

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

n=int(input())
s=[int(input()) for i in range(n)]
memo=[[0]*20000 for i in range(200)]
def dp(score, i):
    if i==n:
        if score%10==0:
            memo[i][score]=0
            return 0
        else:
            memo[i][score]=score
            return score
    if memo[i][score]>0:
        return memo[i][score]
    memo[i][score]=max(dp(score+s[i-1], i+1), dp(score, i+1))
    return memo[i][score]
print(dp(0,0))

### FIXED CODE ###

n=int(input())
s=[int(input()) for i in range(n)]
memo=[[-1]*20000 for i in range(200)]
def dp(score, i):
    if i==n:
        if score%10==0:
            memo[i][score]=0
            return 0
        else:
            memo[i][score]=score
            return score
    if memo[i][score]>=0:
        return memo[i][score]
    memo[i][score]=max(dp(score+s[i-1], i+1), dp(score, i+1))
    return memo[i][score]
print(dp(0,0))
### BUGGY CODE ###

N = int(input())
A = sorted((map(int,input().split())))
B = [True]*N

for i in range(N):
    if B[i]:
        for j in range(i, N):
            if B[j] and j != i:
                if A[j] == A[i]:
                    B[i] = False
                    B[j] = False
                elif A[j] % A[i] == 0:
                    B[j] = False
ans = 0
for i in range(N):
    if B[i]:
        ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
A = sorted((map(int,input().split())))
a_Max = A[-1]
B = [0]*a_Max

for a in A:
    if B[a-1] == 0:
        B[a-1] = 1
        for j in range(2,a_Max+1):
            if a*j > a_Max:
                break
            B[a*j-1] = 2
    elif B[a-1] == 1:
        B[a-1] = 2
            
ans = 0
for b in B:
    if b == 1:
        ans += 1

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

def GCD(x,y):
    x,y=max(x,y),min(x,y)
    if x%y==0:
        return y
    else:
        return GCD(y,x%y)

def LCM(x,y):
    return x*y//GCD(x,y)

# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

# factorial x!
def fact(x):
    global mod
    res=1
    for i in range(2,x+1):
        res=res*i%mod
    return res

# combination nCr
def combi(n,r):
    if r<0 or r>n:
        return 0
    else:
        return fact(n)*inv(fact(r))*inv(fact(n-r))%mod

# is a prime
def ispr(n):
    if n==1:
        return False
    elif n==2:
        return True
    elif n%2==0:
        return False
    else:
        k=3
        while k**2<=n:
            if n%k==0:
                return False
            else:
                k+=2
        return True

mod = 10 ** 9 + 7

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

l = 1
for Ai in A:
    l = LCM(l, Ai)
    # print(Ai, l)

ans = 0
for Ai in A:
    temp = l * inv(Ai) % mod
    # print(temp)
    ans = (ans + temp) % mod

print (ans)

### FIXED CODE ###

# prim factorization
def prfct(n):
    l=[]
    if n%2==0:
        m=0
        while n%2==0:
            n//=2
            m+=1
        l.append((2,m))
    p=3
    while p**2<=n:
        if n%p==0:
            m=0
            while n%p==0:
                n//=p
                m+=1
            l.append((p,m))
        p+=2
    if n>1:
        l.append((n,1))
    return l

# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

mod = 10 ** 9 + 7

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

mp = {}

pfs = []
for Ai in A:
    pf = prfct(Ai)
    for pr, pw in pf:
        if pr not in mp:
            mp[pr] = pw
        else:
            mp[pr] = max(mp[pr], pw)
    pfs.append(pf)
# print(pfs)
# print(mp)

l = 1
for pr in mp:
    pw = mp[pr]
    l *= pow(pr, pw, mod)
# print(l)

ans = 0

for pf in pfs:
    temp = 1
    for prw in pf:
        pr, pw = prw
        temp = temp * pow(pr, pw, mod) % mod
    temp2 = l * inv(temp) % mod
    ans = (ans + temp2) % mod

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

from fractions import gcd
k = int(input())

res = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        t = gcd(a, b)
        for c in range(1, k+1):
            res += gcd(t, c)

print(res)


### FIXED CODE ###

import math
k = int(input())
res = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        t = math.gcd(a, b)
        for c in range(1, k+1):
            res += math.gcd(t, c)
print(res)
### BUGGY CODE ###

n = int(input())
A = []
for i in range(n):
    A.append(int(input()))
    
A.sort()
B = []
for i in range(n):
    if(i==0):
        B.append(A.pop(0))
    elif(i==n-1):
        if(abs(B[0]-A[0])>abs(B[-1]-A[0])):
            B.insert(0, A.pop())
        else:
            B.append(A.pop())
    elif(not(i%4==0 or (i+1)%4==0)):
        if(i%2==0):
            B.insert(0, A.pop())
        else:
            B.append(A.pop())
    else:
        if(i%2==0):
            B.insert(0, A.pop(0))
        else:
            B.append(A.pop(0))

res = 0
for i in range(n-1):
    res += abs(B[i]-B[i+1])

print(res)
    

### FIXED CODE ###

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

A.sort(reverse=True)

def p1(l):
    if N%2 == 1:
        ans = 0
        ans += sum(l[:(N-3)//2])*2
        ans += sum(l[(N-3)//2:(N-3)//2+2])
        ans += sum(l[(N-3)//2+2:])*(-2)
        return ans
    else:
        ans = 0
        ans += sum(l[:(N-2)//2])*2
        ans += sum(l[(N-2)//2:(N-2)//2+1])
        ans += sum(l[(N-2)//2+1:(N-2)//2+2])*(-1)
        ans += sum(l[(N-2)//2+2:])*(-2)
        return ans

def p2(l):
    if N%2 == 1:
        ans = 0
        ans += sum(l[:(N-1)//2])*2
        ans += sum(l[(N-1)//2:(N-1)//2+2])*(-1)
        ans += sum(l[(N-1)//2+2:])*(-2)
        return ans
    else:
        ans = 0
        ans += sum(l[:(N-2)//2])*2
        ans += sum(l[(N-2)//2:(N-2)//2+1])
        ans += sum(l[(N-2)//2+1:(N-2)//2+2])*(-1)
        ans += sum(l[(N-2)//2+2:])*(-2)
        return ans
print(max(p1(A),p2(A)))
### BUGGY CODE ###

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

box.sort()

while(1):

    for index,item in enumerate(box):
        if index != 0 and item != 0:
            if item % box[0] == 0:
                box[index] = 0
                box.remove(0)
            else:
                box[index] = item % box[0]
        
    box.sort(reverse=True)
    #print(box)
    if len(box) == 1:
        break
    box.sort()

print(box[0],end='')

### FIXED CODE ###

from fractions import gcd

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

for i,item in enumerate(a):
    if i != 0:
        ans = gcd(ans,item)

print(ans,end='')
### BUGGY CODE ###

from collections import Counter
from operator import mul
from functools import reduce

N = int(input())

line = [int(x) for x in input().split()]
counter = Counter(line)

result = {}

for i in range(N):
    target = line[i]
    collection = 0
    if target in result:
        print(result[target])
    else:
        for key, value in counter.items():
            if key == target:
                value -= 1

            collection += int((value * (value-1) / 2))
        result[target] = collection
        print(collection)


### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce

N = int(input())

line = [int(x) for x in input().split()]
counter = Counter(line)

collect = {key: int(value * (value - 1) / 2)
           for key, value in counter.items()}
min_collect = {key: int((value - 1) * (value - 2) / 2)
               for key, value in counter.items()}

max_value = sum(collect.values())

for i in line:
    print(min_collect[i] + max_value - collect[i])
### BUGGY CODE ###

import itertools

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

ans = float("inf")
for n_horizontal_cut in range(H):
    for horizontal_cut_idx in list(itertools.combinations(list(range(1,H)), n_horizontal_cut)):
        horizontal_cut_idx = [0] + list(horizontal_cut_idx) + [H]
        n_vertical_cut = 0
        n_white_choco = [0] * (n_horizontal_cut+1)
        for w in range(W):
            tmp_idx = 0
            tmp_n_white_choco = n_white_choco.copy()
            for h in range(H):
                if h >= horizontal_cut_idx[tmp_idx+1]:
                    tmp_idx += 1
                if S[h][w] == 1:
                    n_white_choco[tmp_idx] += 1
            if max(n_white_choco) > K:
                n_vertical_cut += 1
                n_white_choco = [n_white_choco[i] - tmp_n_white_choco[i] for i in range(n_horizontal_cut+1)]
        ans = min(ans, n_horizontal_cut + n_vertical_cut)

print(ans)

### FIXED CODE ###

import itertools, copy

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

ans = float("inf")
for n_horizontal_cut in range(H):
    for horizontal_cut_idx in list(itertools.combinations(list(range(1,H)), n_horizontal_cut)):
        horizontal_cut_idx = [0] + list(horizontal_cut_idx) + [H]
        n_vertical_cut = 0
        n_white_choco = [0] * (n_horizontal_cut+1)
        for w in range(W):
            tmp_idx = 0
            tmp_n_white_choco = copy.copy(n_white_choco)
            for h in range(H):
                if h >= horizontal_cut_idx[tmp_idx+1]:
                    tmp_idx += 1
                if S[h][w] == 1:
                    n_white_choco[tmp_idx] += 1
            if max(n_white_choco) > K:
                n_vertical_cut += 1
                n_white_choco = [n_white_choco[i] - tmp_n_white_choco[i] for i in range(n_horizontal_cut+1)]
                if max(n_white_choco) > K: # 1列の区間でホワイトチョコ数がオーバーする場合
                    break
        else:
            ans = min(ans, n_horizontal_cut + n_vertical_cut)

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

x,y,z,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
c=[int(x) for x in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

s=list()

for l in range(x):
    for m in range(y):
      for n in range(z):
        if l*m*n>k:
           break
        s.append(a[l]+b[m]+c[n])
 
s.sort(reverse=True)
for i in range(k):
  print(s[i])


### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
c=[int(x) for x in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

s=list()

for l in range(x):
  if l>k:
    break 
  for m in range(y):
    if l*m>k:
      break
    for n in range(z):
      if l*m*n>k:
        break
      s.append(a[l]+b[m]+c[n])
 
s.sort(reverse=True)
for i in range(k):
  print(s[i])
### BUGGY CODE ###

import sys

# D - Wizard in Maze
def get_index(s):
	return int(s) - 1


def search(h, w):
  global que
  
  if can_reach(h, w):
    que.append([h, w])


def can_reach(h, w):
	global H
	global W
	global maze
	
	if h < 0 or h >= H or w < 0 or w >= W:
		return False
	elif maze[h][w] == '#':
		return False
	else:
		return True
	

from collections import deque
import copy

H, W = map(int, input().split())
Ch, Cw = map(get_index, input().split())
Dh, Dw = map(get_index, input().split())

maze = []

for _ in range(H):
	maze.append(input())

costs = [[-1] * W for _ in range(H)]
que = deque()
que.append([Ch, Cw])

next_que = deque()
next_que.append([Ch, Cw])

# コスト(ワープ魔法を使った回数)
i = 0

while len(next_que) > 0:
  que = copy.deepcopy(next_que)
  next_que.clear()
  
  # コストiで到達可能なマスを列挙
  while len(que) > 0:
	  h, w = que.popleft()
	  costs[h][w] = i
	
	  next_que.append([h, w])
	
	  # 上下左右に隣接するマスを探索
	  search(h + 1, w)
	  search(h - 1, w)
	  search(h, w + 1)
	  search(h, w - 1)
	 
  i += 1

print(costs[Dh][Dw])


### FIXED CODE ###

import sys

# D - Wizard in Maze
def get_index(s):
	return int(s) - 1


def search_nearby(h, w):
# 上下左右に隣接するマスを探索
	search(h + 1, w, False)
	search(h - 1, w, False)
	search(h, w + 1, False)
	search(h, w - 1, False)


def search_using_warp(h, w):
  # ワープ魔法で移動できるマスを探索
  for i in range(-2, 3):
    search(h - 2, w + i)
    search(h + 2, w + i)

  for i in range(-2, 3):
    if i != 0:
      search(h - 1, w + i)
      search(h + 1, w + i)

  search(h, w + 2)
  search(h, w - 2)


def search(h, w, is_using_warp = True):
  global is_reached
  global que
  global next_que

  if can_reach(h, w):
	  is_reached[h][w] = True
	  next_que.append([h, w])

	  if not is_using_warp:
	    que.append([h, w])


def can_reach(h, w):
	global H
	global W
	global maze

	if h < 0 or h >= H or w < 0 or w >= W:
		return False
	elif maze[h][w] == '#':
		return False
	elif is_reached[h][w]:
		return False
	else:
		return True


from collections import deque
import copy

H, W = map(int, input().split())
Ch, Cw = map(get_index, input().split())
Dh, Dw = map(get_index, input().split())

maze = []

for _ in range(H):
	maze.append(input())

is_reached = [[False] * W for _ in range(H)]

next_que = deque()
next_que.append([Ch, Cw])
mp = 0

while len(next_que) > 0:
  que = copy.deepcopy(next_que)

	# コストiで到達可能なマスを列挙
  while len(que) > 0:
    h, w = que.popleft()
    is_reached[h][w] = True

    search_nearby(h, w)

  if is_reached[Dh][Dw]:
    print(mp)
    exit()

  que = copy.deepcopy(next_que)
  next_que.clear()
  mp += 1

	# コストiで到達可能なマスを列挙
  while len(que) > 0:
    h, w = que.popleft()
    is_reached[h][w] = True

    search_using_warp(h, w)

  if is_reached[Dh][Dw]:
    print(mp)
    exit()

print(-1)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [readline().rstrip().decode() for _ in range(h)]
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
sg = []
memo = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            sg.append((i, j))
        else:
            memo[i][j] = True
ans = 0
for ss in sg:
    for g in sg:
        if ss == g:
            continue
        q = [ss]
        cnt = 0
        dist = deepcopy(memo)
        dist[ss[0]][ss[1]] = True
        while q:
            cnt += 1
            qq = []
            for y, x in q:
                for dy, dx in move:
                    xx, yy = x + dx, y + dy
                    if xx < 0 or yy > h - 1 or yy < 0 or xx > w - 1:
                        continue
                    if dist[yy][xx]:
                        continue
                    dist[yy][xx] = True
                    qq.append((yy, xx))
            q = qq
            if g in q:
                ans = max(ans, cnt)
                break
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = []
start = []
dist = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            start.append((i, j))
        else:
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = []
while start:
    check = deepcopy(dist)
    q = [start.pop()]
    check[list(q)[0][0]][list(q)[0][1]] = True
    cnt = -1
    while q:
        cnt += 1
        qq = []
        memo = len(q)
        memo_cnt = 0
        for y, x in q:
            for dy, dx in test:
                yy, xx = y + dy, x + dx
                if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or check[yy][xx]:
                    memo_cnt += 1
                    continue
                else:
                    check[yy][xx] = True
                    qq.append((yy, xx))
        q = qq
    ans.append(cnt)
else:
    print(max(ans))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
l=[0]*q
r=[0]*q
c=[0]*n
ans=0
for i in range(q):
    l[i],r[i]=map(int,input().split())
t=0
for i in range(n-1):
    if s[i]=='A' and s[i+1]=='C':
        c[t]=i+1
        t+=1
for i in range(q):
    t=0
    while(c[t]!=0):
        if c[t]>=l[i] and c[t]<r[i]:
            ans+=1
        t+=1
    print(ans)
    ans=0

### FIXED CODE ###

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

def main():
    from math import log2,ceil
    from collections import defaultdict
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=tuple(map(int,input().split()))
    mod=10**9+7
    cnt=defaultdict(lambda :0)

    for temp in a:
        if temp==0:continue
        digit=len(bin(temp))-2
        for j in range(ceil(digit)+1):
            if (temp>>j)&1:
                cnt[j]=cnt[j]+1

    #print(cnt)
    ans=0
    for digit,count in cnt.items():
        ans=(ans+pow(2,digit)*count*(n-count))%mod
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=tuple(map(int,input().split()))
mod=10**9+7
cnt=[0]*60

for temp in a:
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(digit):
        if (temp>>j)&1:
            cnt[j]=cnt[j]+1

#print(cnt)
ans=0
for i in range(60):
    if cnt[i]==0:continue
    ans=(ans+pow(2,i)*cnt[i]*(n-cnt[i]))%mod
print(ans%mod)