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

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

P = 10**9+7
bit = [0 for i in range(60)]

# 各bit独立に1が何個あるか数える
for a in A:
    S = bin(a)
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
ans = 0
for i,a in enumerate(bit):
    ans += a*(N-a)*(2**i)
    ans %= P

print(ans)


### FIXED CODE ###

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

ans = 0
P = 10**9+7
bit = [0 for i in range(70)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(70):
    ans += (2**i)*bit[i]*(N-bit[i])
    ans %= P

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

MOD = 10**9 + 7
S = input()
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                rem = (k * (10**(N-i-1))) % 13
                dp[i+1][(j + rem) % 13] += dp[i][j]
                dp[i+1][(j + rem) % 13] %= MOD
    else:
        rem = (int(S[i]) * (10**(N-i-1))) % 13
        for j in range(13):
            dp[i+1][(j + rem) % 13] += dp[i][j]
            dp[i+1][(j + rem) % 13] %= MOD
print(dp[N][5])

### FIXED CODE ###

from itertools import product

MOD = 10**9 + 7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for d in range(N):
    if S[d] == '?':
        for i, j in product(range(13), range(10)): # '?' = j
            rem = ((10 * i) % 13 + j) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
    else:
        for i in range(13):
            rem = ((10 * i) % 13 + int(S[d])) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
print(dp[N][5])
### BUGGY CODE ###

def main(n, p):

    cnt = 0

    for i in range(n):
        # print(f"pi={p[i]}, pj={p[:i+1]}")
        if all(map(lambda pj: p[i] <= pj, p[:i+1])):
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    n = int(input())
    p = list(map(int, input().split()))
    main(n, p)

### FIXED CODE ###

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

cnt = 0
pjmin = P[0]
for pi in P:
    if pi <= pjmin:
        cnt +=1
        pjmin = pi
        if pi ==1:
            break
print(cnt)
### BUGGY CODE ###

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

mod = 10**9 + 7

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+5):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if j == n-1:
            ans += inv[n-1-i] * (x[j] - x[i]) % mod * fac[n-1] % mod
        else:
            ans += (inv[j-i] - inv[j-i+1]) * (x[j] - x[i]) % mod * fac[n-1] % mod
        ans %= mod

print(ans)


### FIXED CODE ###

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

mod = 10**9 + 7

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+5):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

ans = 0
j_inv = []
num = 0
for j in range(1, n):
    num += inv[j]
    num %= mod
    j_inv.append(num)

for i in range(n-1):
    ans += j_inv[i] * (x[i+1] - x[i])
    ans %= mod

ans *=fac[n-1]
ans %= mod

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

# ABC122C - GeT AC
n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
for i, j in arr:
    cnt = 0
    for k, l in zip(s[i - 1 : j - 1], s[i:]):
        if k + l == "AC":
            cnt += 1
    print(cnt)

### FIXED CODE ###

# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = [0] * (n + 1)
for i in range(n):
    if s[i : i + 2] == "AC":
        cnt[i + 1] = cnt[i] + 1
    else:
        cnt[i + 1] = cnt[i]
for i, j in arr:
    print(cnt[j - 1] - cnt[i - 1])
### BUGGY CODE ###

n=int(input())
ans=0

for a in list(map(int,input().split())):
  while not a%2:
    ans+=1
    a//2
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
for a in A:
    while a % 2 == 0:
        a /= 2
        cnt += 1
print(cnt)
### BUGGY CODE ###

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

l.sort(reverse = 1)
ans = 0
flg = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        indL = j
        indR = len(l)-1
        while 1:
            if indL == indR:
                flg = 1
                break
            if l[i] < l[indL] + l[indR]:
                ans += (indR - indL)
                break
            else:
                indR -= 1
        if flg == 1:
            flg = 0
            break
                
print(ans)

### FIXED CODE ###

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

l.sort(reverse = 1)
ans = 0

for i in range(n-2):
    indL = i+1
    indR = len(l)-1
    while 1:
        if indL == indR:
            break
        if l[i] < l[indL] + l[indR]:
            ans += (indR - indL)
            indL += 1
        else:
            indR -= 1
                
print(ans)
### BUGGY CODE ###

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

for i in range(Q):
  ans = 0
  tmp = input().split()
  l = int(tmp[0])
  r = int(tmp[1])
  
  deleted = S[l-1:r]

  for j in range(len(deleted)-1):  
    if deleted[j] == 'A' and deleted[j+1] == 'C':
      ans += 1
  
  print(ans)
  ans = 0

### FIXED CODE ###

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

for i in range(1, N+1):
  t[i] = t[i-1] + (1 if S[i-1:i+1] == 'AC' else 0)
  
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
si = S.replace("AC","11")
si = si.translate(str.maketrans({"T":"0","G":"0","A":"0","C":"0"}))
for q in range(Q):
  l, r = map(int, input().split())
  if l>=2 and S[l-2:l]=="AC" and S[r-1:r+1]=="AC":
    print(int((sum(map(int,list(si[l-1:r])))-2)/2))
  elif l>=2 and S[l-2:l]=="AC":
    print(int((sum(map(int,list(si[l-1:r])))-1)/2))
  elif S[r-1:r+1]=="AC":
    print(int((sum(map(int,list(si[l-1:r])))-1)/2))
  else:
    print(int(sum(map(int,list(si[l-1:r])))/2))

### FIXED CODE ###

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

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


ans = 2018
if l-n >= 672:
    ans = 0
else:
    ll = l % 2019
    for i in range(ll,ll + n-l +1):
        for j in range(ll,ll + n-l +1):
            if i != j:
                jj = j % 2019
                ansss = i*jj%2019
                if ansss == 0:
                    ans = 0
                    break
                elif ansss < ans:
                    ans = ansss

print(ans)

### FIXED CODE ###

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

ll = l % 2019
ans = 2018
if l-n >= 672:
    ans = 0
else:
    for i in range(ll,ll + n-l +1):
        if i % 673 == 0:
            ans = 0
            break
        else:
            for j in range(ll,ll + n-l +1):
                if i != j:
                    ansss = i*j%2019
                    if ansss == 0:
                        ans = 0
                        break
                    elif ansss < ans:
                        ans = ansss

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

def main():
    h,w = map(int,input().split()) 
    x=[[0 for _ in range(w)] for _ in range(h)]
    a=[]
    for _ in range(h):
        a.append(list(input()))
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                x[i][j]=1
    cnt=0
    while True:
        key=0
        b=[]
        for i in range(h):
            for j in range(w):
                key1=0
                if x[i][j]==0:
                    key=1
                    if j<w-1 and a[i][j+1]=="#":
                        x[i][j]=1
                        key1=1
                    elif 0<j and a[i][j-1]=="#":
                        x[i][j]=1
                        key1=1
                    elif i<h-1 and a[i+1][j]=="#":
                        x[i][j]=1
                        key1=1
                    elif 0<i and a[i-1][j]=="#":
                        x[i][j]=1
                        key1=1
                if key1==1:
                    b.append([i,j])
        while b!=[]:
            [n,m]=b[0]
            a[n][m]="#"
            b.pop(0)
        if key==0:
            break
        else:
            cnt+=1
    print(cnt)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    h,w = map(int,input().split())
    a=[]
    que=[]
    for _ in range(h):
        a.append(list(input()))
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                que.append([i,j])
                a[i][j]=0
    ans=0
    while que!=[]:
        tank=[]
        for i,j in que:
            if j<w-1 and a[i][j+1]==".":
                tank.append([i,j+1])
                a[i][j+1]=a[i][j]+1
            if 0<j and a[i][j-1]==".":
                tank.append([i,j-1])
                a[i][j-1]=a[i][j]+1
            if i<h-1 and a[i+1][j]==".":
                tank.append([i+1,j])
                a[i+1][j]=a[i][j]+1
            if 0<i and a[i-1][j]==".":
                tank.append([i-1,j])
                a[i-1][j]=a[i][j]+1
        que=tank
        ans+=1
    print(ans-1)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

mod = 998244353
omega = pow(3,119,mod)
rev_omega = pow(omega,mod-2,mod)

N = 2*10**5
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inv = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inv[i]=( ( -inv[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inv[i]) % mod )
inv[0]=0

def _ntt(f,L,reverse=False):
    F=[f[i] for i in range(L)]
    n = L.bit_length() - 1
    base = omega
    if reverse:
        base = rev_omega

    if not n:
        return F

    size = 2**n
    wj = pow(base,2**22,mod)
    res = [0]*2**n

    for i in range(n,0,-1):
        use_omega = pow(base,2**(22+i-n),mod)
        res = [0]*2**n
        size //= 2
        w = 1
        for j in range(0,L//2,size):
            for a in range(size):
                res[a+j] = (F[a+2*j] + w * F[a+size+2*j]) % mod
                t = (w * wj) % mod
                res[L//2+a+j] = (F[a+2*j] + t * F[a+size+2*j]) % mod
            w = (w * use_omega) % mod
        F = res

    return res

def ntt(f,L=0):
    l = len(f)
    if not L:
        L = 1<<((l-1).bit_length())
    while len(f)<L:
        f.append(0)
    f=f[:L]
    F = _ntt(f,L)
    return F

def intt(f,L=0):
    l = len(f)
    if not L:
        L = 1<<((l-1).bit_length())
    while len(f)<L:
        f.append(0)
    f=f[:L]
    F = _ntt(f,L,reverse=True)
    inv = pow(L,mod-2,mod)
    for i in range(L):
        F[i] *= inv
        F[i] %= mod
    return F

def convolve(f,g,limit):
    l = len(f)+len(g)-1
    L = 1<<((l-1).bit_length())

    F = ntt(f,L)
    G = ntt(g,L)

    H = [(F[i] * G[i]) % mod for i in range(L)]

    h = intt(H,L)

    return h[:limit]

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

prod = [0]
res = 0
for i in range(N):
    poly = [0 for i in range(A[i]+1)]
    poly[-1] = 1
    poly[0] = 1
    prod[0] = (prod[0] + 1) % mod
    prod = convolve(prod,poly,S+1)
    if len(prod)==S+1:
        res += prod[S]
        res %= mod
print(res)

### FIXED CODE ###

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

dp=[[0 for i in range(0,S+1)] for j in range(0,N)]
for i in range(0,S+1):
    if i==A[0]:
        dp[0][i]=1

for i in range(1,N):
    for j in range(0,S+1):
        if j>A[i]:
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-A[i]])%mod
        elif j==A[i]:
            dp[i][j]=(dp[i-1][j]+(i+1))%mod
        else:
            dp[i][j]=dp[i-1][j]

ans=0
for i in range(0,N):
    ans=(ans+dp[i][S])%mod

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

import collections as co
S=input()
Q=int(input())
count=0
back=str()
front=str()
for i in range(Q):
    a=list(map(str,input().split()))
    if  int(a[0])==1:
        count+=1
        back_front=front[::-1]
        front_back=back[::-1]
        back=back_front
        front=front_back
    elif int(a[0])!=1 and int(a[1])==1:
        front=a[2]+front
    elif int(a[0])!=1 and int(a[1])==2:
        back=back+a[2]
    a.clear
if count%2==1:
    S=S[::-1]
S=front+S+back
print(S)

### FIXED CODE ###

import collections as co
S=input()
Q=int(input())
count=0
back=str()
front=str()
judge=True
for i in range(Q):
    a=list(map(str,input().split()))   
    if  int(a[0])==1:
        if judge==True:
            judge=False
        else:
            judge=True
    elif int(a[0])==2 and int(a[1])==1:
        if judge==True:
            front=a[2]+front
        if judge==False:
            back=back+a[2]
    else:
        if judge==True:
            back=back+a[2]
        if judge==False:
            front=a[2]+front
    a.clear
if judge==True:
    S=front+S+back
if judge==False:
    S=front+S+back
    S=S[::-1]
print(S)
### BUGGY CODE ###

R, G, B, N = map(int,input().split())

i = 0
j = 0
cnt = 0

while i*R <= N:
    while i*R + j*G <= N:
        temp = N - i*R - j*G
        if temp % B == 0:
            cnt += 1
        j += 1
    j = 0
    i += 1

print(cnt)

### FIXED CODE ###

R, G, B, N = map(int,input().split())
 
i = 0
j = 0
cnt = 0
 
while i*R <= N:
    while i*R + j*G <= N:
        temp = N - i*R - j*G
        if temp % B == 0:
            cnt += 1
        j += 1
    j = 0
    i += 1
 
print(cnt)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
S = input()
 
S += "X"
j = 0
count = 1
change = [] if S[0] != "0" else [0]
for j in range(len(S)-1):
  if S[j:j+2] == "10":
    change.append(count)
    count = 0
  elif S[j:j+2] == "01":
    change.append(count)
    count = 0
  count += 1

change.append(count-1)
#print(change)
max_len = 0
for i in range(0, len(change), 2):
  #print(i, sum(change[i:i+2*K+1]))
  max_len = max([sum(change[i:i+2*K+1]), max_len])
  
print(max_len)

### FIXED CODE ###

N, K = list(map(int, input().split()))
S = input()
 
S += "X"
i = 0
j = 0
max_len = 0
change = 0 if S[0] != "0" else 1
while j < len(S)-1:
  if change <= K:
    #print(i, j)
    max_len = max([j-i+1, max_len])
    if S[j:j+2] == "10":
      change += 1
    j += 1
  else:
    if S[i:i+2] == "01":
      change -= 1
    i += 1

print(max_len)
### BUGGY CODE ###

n = int(input())
inputs = input().split(" ")
l = [int(s) for s in inputs]

def calc(rl, ns, skip):
    v = rl[len(rl)-1]
    # print(rl,v,ns)
    lrl = len(rl)
    
    if lrl == 1:
        return ns
    if lrl == 2:
        v1 = rl[len(rl)-2]
        return ns+abs(v-v1)
    if lrl == 3:
        v1 = rl[len(rl)-2]
        v2 = rl[len(rl)-3]
        ns1 = ns + abs(v-v2)
        ns2 = ns + abs(v-v1) + abs(v1-v2)
        return min(ns1,ns2)
    else:
        v1 = rl[len(rl)-2]
        v2 = rl[len(rl)-3]
        return min(calc(rl[:len(rl)-1],ns+abs(v-v1),True),calc(rl[:len(rl)-2],ns+abs(v-v2),False))

print(calc(l,0,False))

### FIXED CODE ###

N = int(input())
h = list(map(int, input().split()))
 
suml = [1e5 for i in range(N)]
suml[0] = 0
suml[1] = abs(h[1] - h[0])
 
for e in range(2, N):
    suml[e] = min(
        abs(h[e]-h[e-1]) + suml[e-1],
        abs(h[e]-h[e-2]) + suml[e-2],
    )
 
# print(suml)
print(suml[N-1])
### BUGGY CODE ###

n, y = list(map(int, input().split()))
nasi = True
for d in range(0,n+1):
    if nasi == False:
        break
    for e in range(0,(n+1)-d):
        if nasi == False:
            break
        for f in range(0,(n+1)-d-e):
            if nasi == False:
                break
            if (((10000 * d) + (5000 * e) + (1000 * f)) == y) & (d+e+f==n):
                nasi = False
                print(d,e,f)
                break
if nasi == True:
    print('-1 -1 -1')

### FIXED CODE ###

n, y = list(map(int, input().split()))
nasi = True
for d in range(0,n+1):
    if nasi == False:
        break
    for e in range(0,(n+1)-d):
        if nasi == False:
            break
        f = n - d - e
        if ((10000 * d) + (5000 * e) + (1000 * f) == y):
            nasi = False
            print(d,e,f)
            break
if nasi == True:
    print('-1 -1 -1')
### BUGGY CODE ###

[A, B] = map(lambda x: int(x), input().split(" "))

def absolute_sub(x, y):
    if x > y:
        return x - y
    else:
        return -1*(x - y)

able = False

for i in range(max(A, B)):
    if absolute_sub(A, i) == absolute_sub(B, i):
        print(i)
        able = True

if not able:
    print("IMPOSSIBLE")

### FIXED CODE ###

[A, B] = map(lambda x: int(x), input().split(" "))
K = (A + B) / 2

if K.is_integer():
    print(int(K))
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for ls in dict.values():
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        _s = s[first]
        del dict[_s][(bisect.bisect_left(dict[_s], first))]
        s[first] = last
        bisect.insort_left(dict[last], first)

### FIXED CODE ###

import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for ls in dict.values():
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        _s = s[first]
        if _s == last:
            continue
        del dict[_s][(bisect.bisect_left(dict[_s], first))]
        s[first] = last
        bisect.insort_left(dict[last], first)
### BUGGY CODE ###

n,m=map(int,input().split())
out=[]
for i in range(m):
  out.append(int(input()))
dp=[0 for i in range(n+1)]
dp[0]=1
dp[1]=2
if 1 in out:
  dp[0]=0
  if 2 in out:
    dp[1]=0
  else:
    dp[1]=1
elif 2 in out:
  dp[1]=0
for i in range(2,n):
  if (i+1) in out:
    continue
  else:
    dp[i]=dp[i-1]+dp[i-2]
print (dp[n-1]%(10**9+7))



### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
if danger==[]:
  pass
elif danger[0]==1:
  arr[0]=0
  arr[1]=1
for i in range(m):
  arr[danger[i]-1]=-1
for i in range(n):
  if arr[i]==-1:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    a = input()
    s.append(a)

def sort_list(st):
    arr = []
    freq = []
    for moji in st:
        exist_in_st = False
        for i in range(len(arr)):
            if moji == arr[i]:
                freq[i] += 1
                exist_in_st = True
        if exist_in_st == False:
            arr.append(moji)
            freq.append(1)
    ans = []
    for st, num in zip(arr, freq):
        ans.append([st,num])
    ans.sort(key=lambda x:x[0])
    return  ans

def compare_lists(li1, li2):
    if len(li1) != len(li2):
        return False
    if len(li1) == len(li2):        
        for a1, a2 in zip(li1, li2):
            if  a1 != a2:
                return False
    return True

sts = []
nums = []
for new_st in s:
    new_st = sort_list(new_st)
    exist_in_sts = False
    for i in range(len(sts)):
        if (new_st == sts[i]):
            nums[i] += 1
            exist_in_sts = True
    if exist_in_sts == False:
        sts.append(new_st)
        nums.append(1)

ans = sum([int(x * (x - 1) / 2) for x in nums])
print(ans)

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(input())

dictS = {}
for new_st in s:
    new_st = "".join(sorted([x for x in new_st]))
    if new_st in dictS:
        dictS[new_st] += 1
    else:
        dictS[new_st] = 1

ans = sum([int(x * (x - 1) / 2) for x in dictS.values()])
print(ans)
### BUGGY CODE ###

N = int(input())

def prime_factorization(n):
    factor = []
    f = 2
    while f ** 2 <= n:
        if n % f == 0:
            factor.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        factor.append(n)
    return factor

p = prime_factorization(N)
from itertools import combinations as cb
from functools import reduce
from operator import mul

s = N+1
for i in range(1, len(p)//2+1):
    for j in cb(p, i):
        A = reduce(mul, j)
        B = N//A
        s = min(s, A+B)

print(s-2)

### FIXED CODE ###

N = int(input())
S = N+1
from math import sqrt
for a in range(int(sqrt(N))+2, 0, -1):
    b, y = divmod(N, a)
    if y != 0:
        continue
    S = min(S, a+b)
print(S-2)
### BUGGY CODE ###

import collections as c

n = int(input())

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

q = int(input())

cnt = [0]*100000

for i in range(100000):
    cnt[i] = a.count(i+1)

for i in range(q):
    b,c = map(int,input().split())
    x = cnt[b-1]
    cnt[b-1] = 0
    cnt[c-1] = cnt[c-1] + x
    ans = 0
    for s in range(100000):
        ans += (s+1)*cnt[s]
        
    print(ans)

### FIXED CODE ###

import collections as c

n = int(input())

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

q = int(input())

s = sum(a)

cnt = c.Counter(a)

for i in range(q):
    b,c = map(int,input().split())
    s += (c-b)*cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(s)
### BUGGY CODE ###

S = input()
B = []
res = 0
for s in range(len(S)):
    B.append(S[s])
Q = int(input())
for q in range(Q):
    C = []
    A = list(map(str, input().split()))
    if len(A) == 3:
        C.append(A[2])
    if int(A[0]) == 1:
        if res == 0:
            res = 1
        else:
            res = 0
    else:
        if int(A[1]) == 1:
            if res == 0:
                B = C + B
            else:
                B.append(A[2])
        else:
            if res == 0:
                B.append(A[2])
            else:
                B = C + B
if res == 0:
    print(''.join(B))
else:
    B = B[::-1]
    print(''.join(B))

### FIXED CODE ###

from collections import deque

S = input()
B = deque()
res = 0
for s in range(len(S)):
    B.append(S[s])
Q = int(input())
for q in range(Q):
    A = list(map(str, input().split()))
    if int(A[0]) == 1:
        if res == 0:
            res = 1
        else:
            res = 0
    else:
        if int(A[1]) == 1:
            if res == 0:
                B.appendleft(A[2])
            else:
                B.append(A[2])
        else:
            if res == 0:
                B.append(A[2])
            else:
                B.appendleft(A[2])
if res == 0:
    print(''.join(B))
else:
    B.reverse()
    print(''.join(B))