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

S=input()
Q=int(input())

R=0

for i in range(Q):
    temp=list(input().split())
    if int(temp[0])==1:
        R+=1
    elif int(temp[0])==2:
        F=int(temp[1])
        c=temp[2]
        if F==1:
            if R%2==0:
                S=c+S
            else:
                S=S+c
        elif F==2:
            if R%2==0:
                S=S+c
            else:
                S=c+S

if R%2==1:
    ans=""
    for i in range(len(S)):
        ans+=S[-(1+i)]
    print(ans)
else:
    print(S)



### FIXED CODE ###

S=input()
Q=int(input())

R=0
S1=""
S2=""
for i in range(Q):
    temp=list(input().split())

    if int(temp[0])==1:
        S=S1+S+S2
        S1=""
        S2=""
        R+=1
    elif int(temp[0])==2:
        F=int(temp[1])
        c=temp[2]
        if F==1:
            if R%2==0:
                S1=c+S1
            else:
                S2=S2+c
        elif F==2:
            if R%2==0:
                S2=S2+c
            else:
                S1=c+S1
S=S1+S+S2

if R%2==1:
    ans=S[-1::-1]
    print(ans)
else:
    print(S)
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
alrdy = []
 
def is_anagrams(word1, word2):
    def get_counter(s):
        return Counter(s.upper().replace(' ', ''))
 
    return get_counter(word1) == get_counter(word2)

dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]
cnt = 0
while len(s) > 1:
  remove_list = []
  for i in range(len(s)-1):
    remove_list.append(i)
    for j in range(i+1, len(s)):
      if is_anagrams(s[i], s[j]):
        cnt += 1
        remove_list.append(j)
  s = dellist(s, remove_list)
print(cnt)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
existed = {}
cnt = 0
for i in range(n):
  sorted_s = ''.join(sorted(s[i]))
  if sorted_s in existed:
    cnt += existed[sorted_s]
    existed[sorted_s] += 1
  else:
    existed[sorted_s] = 1
print(cnt)
### BUGGY CODE ###

# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    H, W = [int(x) for x in sys.stdin.readline().split()]
    grid = ['#' * (W + 2)]
    for _ in range(H):
        s = '#' + sys.stdin.readline().rstrip() + '#'
        grid.append(s)
    grid.append('#' * (W + 2))

    l, r, u, d = [[[0 for _ in range(W+2)] for _ in range(H+2)] for _ in range(4)]
    for i in range(1, H+1):
        for j in range(1, W+1):
            l[i][j] = l[i][j-1] + 1 if grid[i][j] == '.' else 0
            r[i][-j-1] = r[i][-j-1+1] + 1 if grid[i][-j-1] == '.' else 0
            u[i][j] = u[i-1][j] + 1 if grid[i][j] == '.' else 0
            d[-i-1][j] = d[-i-1+1][j] + 1 if grid[-i-1][j] == '.' else 0

    lighted_squares = []
    for h in range(1, H+1):
        for w in range(1, W+1):
            if grid[h][w] == 'w':
                lighted_squares.append(0)
            else:
                lighted_squares.append(l[h][w] + r[h][w] + u[h][w] + d[h][w] - 3)

    ans = max(lighted_squares)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np 

h, w = map(int, sys.stdin.readline().split())
grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(h)], dtype='U')
grid = np.pad(grid, 1, mode='constant')

def main():
    cnt = np.zeros((h+2, w+2))
    cnt[grid == '.'] = np.inf
    
    l = cnt.copy()
    r = cnt.copy()
    u = cnt.copy()
    d = cnt.copy()

    for i in range(1, w+1):
        l[1:h+1, i] = np.minimum(l[1:h+1, i], l[1:h+1, i-1]+1)
        i = w + 1 - i
        r[1:h+1, i] = np.minimum(r[1:h+1, i], r[1:h+1, i+1]+1)
    
    for i in range(1, h+1):
        u[i, 1:w+1] = np.minimum(u[i, 1:w+1], u[i-1, 1:w+1]+1)
        i = h + 1 - i
        d[i, 1:w+1] = np.minimum(d[i, 1:w+1], d[i+1, 1:w+1]+1)
    
    res = np.maximum(l + r + u + d - 3, 0).astype(np.int64)
    return np.amax(res)

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

H,W,N = map(int,input().split())

from collections import defaultdict
t =defaultdict(int)
L = defaultdict(int)

for i in range(N):
    a,b = map(int,input().split())
    t[(a-1,b-1)] = 1
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            L[(a+p-1,b+q-1)] = 1



ans = [0]*10
for k in L.keys():
    a,b = k[0],k[1]
    if a < 1 or b < 1 or a >H-2 or b >W-2:
        continue

    c = 0
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            c +=t[(a+p,b+q)]

    ans[c] += 1

ans[0] = (H-2)*(W-2) - sum(ans)
for i in range(10):
    print(ans[i])


### FIXED CODE ###

H,W,N = map(int,input().split())

from collections import defaultdict
t =defaultdict(int)
L = defaultdict(int)

for i in range(N):
    a,b = map(int,input().split())
    t[(a-1,b-1)] = 1
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            if a+p < 2 or b+q < 2 or a+p >H-1 or b+q >W-1:
                continue
            L[(a+p-1,b+q-1)] += 1
ans = [0]*10
for v in L.values():
    ans[v] += 1

ans[0] = (H-2)*(W-2) - sum(ans)
for i in range(10):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
 
a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1
 
 
if n % 2 == 0:
    possible_list = [i for i in range(1, n, 2)]
    for k, v in a_dict.items():
        if v != 2 or k not in possible_list:
            print(0)
            exit()
else:
    possible_list = [i for i in range(0, n, 2)]
    if a_dict[0] != 1:
        print(0)
        exit()
    else:
        a_dict[0] = 2
        for k, v in a_dict.items():
            if v != 2 or k not in possible_list:
                print(0)
                exit()
 
print(2 ** (n // 2) % (10 ** 9 + 7))


### FIXED CODE ###

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

a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1

 
if n % 2 == 0:
    possible_list = {i: True for i in range(1, n, 2)}
    for k, v in a_dict.items():
        if v != 2 or k not in possible_list:
            print(0)
            exit()
else:
    possible_list = {i: True for i in range(0, n, 2)}
    if a_dict[0] != 1:
        print(0)
        exit()
    else:
        a_dict[0] = 2
        for k, v in a_dict.items():
            if v != 2 or k not in possible_list:
                print(0)
                exit()
 
print(2 ** (n // 2) % (10 ** 9 + 7))
### BUGGY CODE ###

from itertools import combinations, chain

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


def h_divide(Sss, div_is):
    result = []
    for s, e in zip(chain([0], div_is), chain(div_is, [H])):
        result.append(Sss[s:e])
    return result


def _v_end(Sss, start, K):
    count = 0
    for i in range(start, W):
        s = sum(map(lambda Ss: Ss[i], Sss))
        if count + s > K:
            return i - 1
        count += s
    return W - 1


def v_end(Ssss, start, K):
    return min(map(lambda Sss: _v_end(Sss, start, K), Ssss))


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < start:
            return -1
        if end == W - 1:
            break
        result += 1
        start = end + 1
    return result


h_cands = list(range(1, H))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        Ssss = h_divide(Sss, list(comb))
        cnt = v_div_count(Ssss, K)
        if cnt < 0:
            continue
        if ans < 0 or ans > n + cnt:
            ans = n + cnt
print(ans)


### FIXED CODE ###

from itertools import combinations, chain

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


def h_divide(Sss, div_is):
    result = []
    for s, e in zip(chain([0], div_is), chain(div_is, [len(Sss)])):
        result.append(Sss[s:e])
    return result


def _v_end(Sss, start, K):
    count = 0
    for i in range(start, len(Sss[0])):
        s = sum(map(lambda Ss: Ss[i], Sss))
        if count + s > K:
            return i - 1
        count += s
    return len(Sss[0]) - 1


def v_end(Ssss, start, K):
    result = -1
    for Sss in Ssss:
        end = _v_end(Sss, start, K)
        if end < start:
            return -1
        if result < 0 or result > end:
            result = end
    return result


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < 0:
            return -1
        if end == len(Ssss[0][0]) - 1:
            break
        result += 1
        start = end + 1
    return result


h_cands = list(range(1, len(Sss)))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        if ans > 0 and n >= ans:
            continue
        Ssss = h_divide(Sss, list(comb))
        cnt = v_div_count(Ssss, K)
        if cnt < 0:
            continue
        if ans < 0 or ans > n + cnt:
            ans = n + cnt
print(ans)
### BUGGY CODE ###

import numpy as np

n,m = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(m)]
n = np.zeros(n)
for l,r in LR:
  n[l-1:r] += 1
print(sum(n == m))

### FIXED CODE ###

n,m = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(m)]
L = max([i[0] for i in LR])
R = min([i[1] for i in LR])
print(max(R-L+1,0))
### BUGGY CODE ###

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

nlist = []
for i in range(N):
    a, b = map(int, input().split())
    if len(nlist) == 0:
        nlist.append((a, b))
    else:
        for i, (na, nb) in enumerate(nlist):
            if a <= na:
                nlist.insert(i, (a, b))
                break
            elif i == len(nlist) - 1:
                nlist.insert(i + 1, (a, b))
                break

cur_pos = 0
for a, b in nlist:
    cur_pos += b
    if cur_pos >= K:
        print(a)
        break

### FIXED CODE ###

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

dic = {}
for i in range(N):
    a, b = map(int, input().split())
    if a in dic:
        dic[a] += b
    else:
        dic[a] = b
keys = list(dic.keys())
keys.sort()

cur_pos = 0
for key in keys:
    b = dic[key]
    cur_pos += b
    if cur_pos >= K:
        print(key)
        break
### BUGGY CODE ###

N=int(input())
G=[[] for i in range(N)]
a=[]
b=[]

for i in range(N-1):
    ai,bi=map(int,input().split())
    a.append(ai-1)
    b.append(bi-1)
    G[ai-1].append(bi-1)
    G[bi-1].append(ai-1)

L=[]
for i in G:
    L.append(len(i))

K=max(L)
print(K)

k=[0]*N

from collections import deque

q=deque([0])
C=[[-1]*N for i in range(N)]
p=[-1]*N

while q:
    x=q.popleft()
    for i in G[x]:
        if C[x][i]!=-1:continue
        if p[x]==k[x]:
            k[x]+=1

        C[x][i] = k[x]
        C[i][x] = k[x]
        p[i] = k[x]
        k[x] += 1


        q.append(i)

for i in range(N-1):
    print(C[a[i]][b[i]]+1)




### FIXED CODE ###

N=int(input())
G=[[] for i in range(N)]
a=[]
b=[]

for i in range(N-1):
    ai,bi=map(int,input().split())
    a.append(ai-1)
    b.append(bi-1)
    G[ai-1].append(bi-1)
    G[bi-1].append(ai-1)

k=[0]*N

from collections import deque

q=deque([0])
visited=[0]*N
ans={}
p=[-1]*N

kmx=0
while q:
    x=q.popleft()
    visited[x]=1
    cnt=1
    for i in G[x]:
        if visited[i]!=0:continue
        if p[x]==cnt:
            cnt+=1
        ans[(x,i)]=cnt
        ans[(i,x)]=cnt

        p[i] = cnt
        cnt += 1
        kmx=max(kmx,cnt-1)
        q.append(i)

print(kmx)
for i in range(N-1):
    print(ans[(a[i],b[i])])
### BUGGY CODE ###

N,K=map(int,input().split())
x=[int(i) for i in input().split()]

import bisect

zp=bisect.bisect_left(x,0)
cost=[]

for i in range(max(0,zp-K),min(zp+1,N-K+1)):
    x2=x[i:i+K]
    c=min(abs(min(x2[0],0)),max(0,x2[-1]))*2 + max((-1)*x2[0],x2[-1])
    cost.append(c)

print(min(cost))

### FIXED CODE ###

N,K=map(int,input().split())
x=[int(i) for i in input().split()]

cost=10**13

for i in range(N-K+1):
    c=x[i+K-1]-x[i]+min(abs(x[i]),abs(x[i+K-1]))
    cost=min(cost,c)

print(cost)
### BUGGY CODE ###

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

cout = 0



for i in range(0,n):
    if i == 0:
        cout = cout + 1
    else:
        if min(p[0:i+1]) == p[i]:
            cout = cout + 1



print(cout)



### FIXED CODE ###

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

cout = 1
saisyou = p[0]

for i in range(n-1):
    if p[i+1] <= saisyou:
        cout = cout + 1
        saisyou = p[i+1]

print(cout)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
L = []
R = []
B = []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

for a, b in zip(L,R):
    A = S[a-1:b]
    print(A.count("AC"))

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
A = [0]*N


for i in range(1, N):
    if S[i-1] == "A" and S[i] =="C":
        A[i] = A[i-1]+1
    else:
        A[i] = A[i-1]

for i in range(Q):
    a, b = map(int, input().split())
    print(A[b-1] - A[a-1])
### BUGGY CODE ###

import itertools
import math

d, g = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(d)]

res = float('inf')
for indices in itertools.permutations(range(d)):
    count = 0
    s = 0
    for i in indices:
        p, c = ls[i]
        if s + 100 * (i + 1) * p >= g:
            count += math.ceil((g - s) / (100 * (i + 1)))
            break
        else:
            count += p
            if count >= res:
                break
            s += 100 * (i + 1) * p + c
            if s >= g:
                break
    res = min(res, count)
print(res)

### FIXED CODE ###

import itertools
import math

d, g = map(int, input().split())
ls = [[100 * (i + 1)] + list(map(int, input().split())) for i in range(d)]
s0 = [a * p for a, p, _ in ls]
s1 = [a * p + c for a, p, c in ls]

res = float('inf')
for indices in itertools.permutations(range(d)):
    count = 0
    s = 0
    for i in indices:
        if s + s0[i] >= g:
            count += math.ceil((g - s) / (100 * (i + 1)))
            break
        else:
            count += ls[i][1]
            if count >= res:
                break
            s += s1[i]
            if s >= g:
                break
    res = min(res, count)
print(res)
### BUGGY CODE ###

from collections import deque
def sol():
    n,k=map(int,input().split())
    p=list(map(int,input().split()))
    minp=[0]*(n-k+1)
    maxp=[0]*(n-k+1)
    q1=deque([0])
    q2=deque([0])
    for i in range(1,k):
        while p[q1[-1]]>p[i]:
            q1.pop()
            if len(q1)==0:
                break
        while p[q2[-1]]<p[i]:
            q2.pop()
            if len(q2)==0:
                break
        q1.append(i)
        q2.append(i)
    for i in range(n-k+1):
        minp[i]=p[q1[0]]
        maxp[i]=p[q2[0]]
        if i==n-k:
            break
        if q1[0]==i:
            q1.popleft()
        if q2[0]==i:
            q2.popleft()
        while p[q1[-1]]>p[i+k]:
            q1.pop()
            if len(q1)==0:
                break
        while p[q2[-1]]<p[i+k]:
            q2.pop()
            if len(q2)==0:
                break
        q1.append(i+k)
        q2.append(i+k)

    d=[False]*(n-k+1)
    d[0]=all(p[i]<p[i+1] for i in range(k-1))
    i=1
    while i<n-k+1:
        if p[i+k-2]>p[i+k-1]:
            i+=k-1
        else:
            if d[i-1]:
                d[i]=True
            else:
                if p[i]<p[i+1]:
                    d[i]=all(p[j]<p[j+1] for j in range(i,i+k-1))
            i+=1

    ans=int(any(d))
    if not d[0]:
        ans+=1
    for i in range(n-k):
        if d[i+1]:
            continue
        if not (p[i]==minp[i] and p[i+k]==maxp[i+1]):
            ans+=1

    print(ans)
sol()

### FIXED CODE ###

from collections import deque
n,k=map(int,input().split())
p=list(map(int,input().split()))

minp=[0]*(n-k+1)
maxp=[0]*(n-k+1)
q1=deque([0])
q2=deque([0])
for i in range(1,k):
    while p[q1[-1]]>p[i]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i)
    q2.append(i)
for i in range(n-k+1):
    minp[i]=p[q1[0]]
    maxp[i]=p[q2[0]]
    if i==n-k:
        break
    if q1[0]==i:
        q1.popleft()
    if q2[0]==i:
        q2.popleft()
    while p[q1[-1]]>p[i+k]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i+k]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i+k)
    q2.append(i+k)

d=[0]*n
d[0]=1
for i in range(1,n):
    if p[i]>p[i-1]:
        d[i]=d[i-1]+1
    else:
        d[i]=1

ans=int(k in d)
if d[k-1]!=k:
    ans+=1
for i in range(n-k):
    if d[i+k]>=k:
        continue
    if not (p[i]==minp[i] and p[i+k]==maxp[i+1]):
        ans+=1

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

import sys
args = sys.stdin.readlines()
n, m = map(int, args[0].split(' '))
ids = set(range(1, n+1))

for gate in args[1:]:
  l, r = map(int, gate.split(' '))  
  ids = ids & set(range(l, r+1))
  
print(len(ids))


### FIXED CODE ###

import sys
args = sys.stdin.readlines()
n, m = map(int, args[0].split(' '))
l_1 = 1
r_1 = n

for gate in args[1:]:
  l, r = map(int, gate.split(' '))  
  if l > l_1:
    l_1 = l
  if r < r_1:
    r_1 = r

ids = r_1 - l_1 + 1
if ids < 0:
  print(0)
else:
  print(ids)
### BUGGY CODE ###

N,K = map(int,input().split())
LR = []
for i in range(K):
  L,R = map(int,input().split())
  LR += list(range(L,R+1))
LR = sorted(LR)
MOD = 998244353
dp = [0]*N
dp[0] = 1
for i in range(1,N):
  for j in LR:
    if i-j<0: continue
    else: dp[i] += dp[i-j]
  dp[i] %= MOD
print(dp[-1])

### FIXED CODE ###

N,K = map(int,input().split())
LR = []
for _ in range(K): LR.append(list(map(int,input().split())))
MOD = 998244353
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  for L,R in LR:
    if i+L<N: dp[i+L] += dp[i]
    if i+R+1<N: dp[i+R+1] -= dp[i]
  if i>0: dp[i+1] = (dp[i+1]+dp[i])%MOD
print(dp[-1])
### BUGGY CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(20000)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = []
	for _ in range(n):
		row = 0
		for i, bit in enumerate(rli()):
			row |= (bit << i)
		A.append(row)

	subset = lambda x, y: (x & y) == x
	kth = lambda x, k: x & (1 << k)
	MOD = 10**9 + 7
	@lru_cache(None)
	def dp(i, not_matched):
		if i == n: return 1
		cnt = 0
		for j in range(n):
			if kth(not_matched, j) and kth(A[i], j):
				cnt += dp(i + 1, not_matched ^ (1 << j))
				cnt %= MOD
		return cnt % MOD

	ans = dp(0, (1 << n)-1)
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

### FIXED CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(20000)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

def main():
	MOD = 10**9 + 7
	n = int(rl())
	A = []
	for _ in range(n):
		row = []
		for bit in rli():
			row.append(bit)
		A.append(row)

	dp = [0 for _ in range(1 << n)]
	dp[0] = 1
	for mask in range((1 << n)-1):
		new = popcount(mask)
		for cand in range(n):
			if A[new][cand] and not (mask & (1 << cand)):
				nmask = mask ^ (1 << cand)
				dp[nmask] += (dp[mask] % MOD)
				dp[nmask] %= MOD
	print(dp[-1]) 
	stdout.close()

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

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

A={}

for i in range(N):
    A[i+1]=P[i]

f=True
U=[]
v=1

k=0

while (v not in U) and (k<=K):
    U.append(v)
    v=A[v]
    k+=1
    
if v not in U:
    print(U[-1])
else:
    g=U.index(v)
    U=U[g:]
    K-=g

    m=len(U)
    print(U[K%m])


### FIXED CODE ###

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

A={k+1:P[k] for k in range(N)}


U=list()
S=set()
x=1
k=0

while (x not in S) and (k<=K):
    U.append(x)
    S.add(x)
    
    x=A[x]
    k+=1

if k>K:
    print(U[-1])
else:
    d=U.index(x)
    V=U[d:]
    print(V[(K-d)%len(V)])
### BUGGY CODE ###

#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


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


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


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    ttl_bins = [[0]*60 for i in range(N)]
    for i in range(1, N):
        target = targets[N-i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            ttl_bins[N-i-1][keta] = ttl_bins[N -
                                             i][keta] + int(target_str[keta])

    ttl_final = [0]*60
    for i in range(N-1):
        target = targets[i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            keta_int = int(target_str[keta])
            if keta_int == 0:
                ttl_others_1 = ttl_bins[i][keta]
                ttl_final[59 - keta] += ttl_others_1
            if keta_int == 1:
                ttl_others_0 = (N - i - 1) - ttl_bins[i][keta]
                ttl_final[59 - keta] += ttl_others_0

    ans = 0
    for i in range(60):
        ans += ttl_final[i] * pow(2, i, MOD)
        ans %= MOD

    print(ans)


main()


### FIXED CODE ###

#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


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


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


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    ttl_bins = [0]*60
    for i in range(N):
        target = targets[i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            ttl_bins[keta] += int(target_str[keta])

    ans = 0
    for i in range(60):
        ttl = ttl_bins[i] * (N - ttl_bins[i])
        ans += pow(2, 59-i, MOD) * ttl
        ans %= MOD

    print(ans)


main()
### BUGGY CODE ###

n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
  if n<2:
    print(min(v,w))
    continue
  s,t=set(),set()
  while v:
    s|={v}
    v=(v+n-2)//n
  while w:
    t|={w}
    w=(w+n-2)//n
  print(max(s&t))

### FIXED CODE ###

n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
  if n<2:
    print(min(v,w))
    continue
  s,t=set(),set()
  while v:
    s|={v}
    v=(v+n-2)//n
  while w:
    t|={w}
    w=(w+n-2)//n
  print(max(s&t))