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

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

n = inp()
x = ip()
ans = 'pairwise coprime'
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    #print(t)
    if t != 1:
        ans = 'setwise coprime'
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    for i in range(n-1):
        for j in range(i+1,n):
            t = gcd(x[i],x[j])
            if t != 1:
                ans = 'setwise coprime'
                break
        if ans == 'setwise coprime':
            break
print(ans)


### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(wv[i][1]):
        dp[i+1][j] = dp[i][j]
    for j in range(wv[i][1], v_max+1):
        dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
for j in range(v_max, 0, -1):
    if dp[N][j] <= W:
        print(j)
        break

### FIXED CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if i+1 == N and dp[i+1][j] <= W:
            ans = j
print(ans)
### BUGGY CODE ###

H,W = map(int,input().split())
field = [list(input()) for _ in range(H)]
#print(field)

L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
  for w in range(W):
    if field[h][w] == "#":
      L[h][w] = 0
    elif w == 0:
      L[h][w] = 1
    else:
      L[h][w] = L[h][w-1] + 1
#print(L)
for h in range(H):
  for w in range(W-1,-1,-1):
    if field[h][w] == "#":
      R[h][w] = 0
    elif w == W-1:
      R[h][w] = 1
    else:
      R[h][w] = R[h][w+1] + 1
#print(R)
for h in range(H-1,-1,-1):
  for w in range(W):
    if field[h][w] == "#":
      D[h][w] = 0
    elif h == H-1:
      D[h][w] = 1
    else:
      D[h][w] = D[h+1][w] + 1
#print(D)     
for h in range(H):
  for w in range(W):
    if field[h][w] == "#":
      U[h][w] = 0
    elif h == 0:
      U[h][w] = 1
    else:
      U[h][w] = U[h-1][w] + 1
#print(U)
ans = 0
for h in range(H):
  for w in range(W):
    ans = max(ans,L[h][w] + R[h][w] + D[h][w] + U[h][w] - 3)
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
field = [list(input()) for _ in range(H)]
#print(field)

L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]

#print(L)
for h in range(H):
  for w in range(W-1,-1,-1):
    if field[h][w] == "#":
      R[h][w] = 0
    elif w == W-1:
      R[h][w] = 1
    else:
      R[h][w] = R[h][w+1] + 1
#print(R)
for h in range(H-1,-1,-1):
  for w in range(W):
    if field[h][w] == "#":
      D[h][w] = 0
    elif h == H-1:
      D[h][w] = 1
    else:
      D[h][w] = D[h+1][w] + 1
#print(D)     
#print(U)
ans = 0
for h in range(H):
  for w in range(W):
    if field[h][w] == "#":
      L[h][w] = 0
    elif w == 0:
      L[h][w] = 1
    else:
      L[h][w] = L[h][w-1] + 1
    if field[h][w] == "#":
      U[h][w] = 0
    elif h == 0:
      U[h][w] = 1
    else:
      U[h][w] = U[h-1][w] + 1
    ans = max(ans,L[h][w] + R[h][w] + D[h][w] + U[h][w] - 3)

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

from functools import lru_cache
N, A = map(int, input().split())
X = [int(x) for x in input().split()]

@lru_cache(1000000000, False)
def solve(i, n, s):
    if s < 0:
        return -1
    if N-i+1 < n:
        return -1
    if n == 0:
        if s == 0:
            return 1
        else:
            return -1
    if i == N:
        return -1
    s1 = solve(i+1, n-1,s-X[i])
    s2 = solve(i+1, n, s)
    if s1 == -1 and s2 == -1:
        return -1
    if s1 == -1:
        return s2
    if s2 == -1:
        return s1
    return s1 + s2


answer = 0
for n in range(1, N+1):
    s = solve(0, n, n*A)
    if s != -1:
        #print(n, s)
        answer += s
print(answer)

def test():
    import itertools
    for a in itertools.combinations(X,3):
        if sum(a) == A*3:
            print(a)

### FIXED CODE ###

N, A = map(int, input().split())
X = sorted([int(x) for x in input().split()])
from collections import defaultdict , Counter
dp = defaultdict(Counter)

dp[0] = Counter({0:1})

for i in range(1, N+1):
    x = X[i-1]
    k = 0
    update = []
    for s, counter in list(dp.items()):
        for nCard, count in counter.items():
            update.append((s+x, nCard+1, count))

    for key, value, diff in update:
        dp[key][value] += diff

def printCounter(counter):
    if len(counter) == 0:
        return ""
    return dict(counter)
if False:
    for s in range(0, max(X)*N):
        print("%2d" % s, "|", printCounter(dp[s]))

answer = 0
for s, counter in dp.items():
    q, r = divmod(s, A)
    if r != 0:
        continue
    answer += counter[q]
print(answer-1)
### BUGGY CODE ###

import sys
 
n=0
m=0
id_list=[]
 
def calculate(x):
  _x = x + 1
  for id_list_index in range(0, m):
    if not((_x >= id_list[id_list_index][0]) and (_x <= id_list[id_list_index][1])) :
      return False
 
  return True
  
  
is_arg_ok = False
try:
  n, m  = map(int, input().split())
  for i in range(0, m):
    gate_min, gate_max = map(int, input().split())
    id_list.append([gate_min, gate_max])
  is_arg_ok = True
  
except:
  print('arg error')
  sys.exit(1)
 
 
result = len(list(filter(lambda n: calculate(n), range(0, n))))
print(result)
sys.exit(0)

### FIXED CODE ###

import sys
n=0
m=0

n, m  = map(int, input().split())
_min, _max  = map(int, input().split())
for i in range(1, m):
  gate_min, gate_max = map(int, input().split())
  if (_max > gate_max):
    _max = gate_max
   
  if _min < gate_min:
    _min = gate_min
 
result_list = list(filter(lambda x : (_min <= x) and (x <= _max), range(1, n+1)))
result = len(result_list)

print(result)
sys.exit(0)
### BUGGY CODE ###

#ABC951B/Sum_of_Three_Integers

K, S = map(int, input().split())
ans = 0
for X in range(0, K+1):
    Y = X
    Z = X
    if X + Y + Z == S:
        ans += 1
for X in range(0, K+1):
    Y = X
    for Z in range(0, K+1):
        if X != Z and X + Y + Z == S:
            ans += 3
for X in range(0, K-1):
    for Y in range(X+1, K):
        for Z in range(Y+1, K+1):
            if X + Y + Z == S:
                ans += 6
print(ans)

### FIXED CODE ###

#ABC951B/Sum_of_Three_Integers

K, S = map(int, input().split())
ans = 0
for x in range(0, K+1):
    for y in range(0, K+1):
        z = S - x - y
        if 0 <= z and z <= K:
            ans += 1
print(ans)
### BUGGY CODE ###



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

idx = [0] * (N+3)
cnt = 1
for a in A:
    idx[a] = cnt
    cnt += 1
idx[N+1] = N+1
idx[N+2] = 0

sets = [0,N+1]

ans = 0
import bisect
for i in reversed(range(1,N+1)):
    index = idx[i]
    tmplist = sets
    L = len(tmplist)
    left1 = max(bisect.bisect_left(tmplist,index)-1, 0)
    left2 = max(left1-1,0)
    right1 = min(bisect.bisect_left(tmplist,index), L-1)
    right2 = min(right1+1, L-1)
    
    l1 = tmplist[left1]
    l2 = tmplist[left2]
    r1 = tmplist[right1]
    r2 = tmplist[right2]
    ans += i * ((r1-index)*(l1-l2) + (index-l1)*(r2-r1))
    insert_index = bisect.bisect_left(tmplist,index)
    sets = tmplist[:insert_index] + [index] + tmplist[insert_index:]
    
    
print(ans)
    





### FIXED CODE ###


# 1-indexed　Binary Indexed Tree
class BIT:
    def __init__(self, n, init_list):
        self.num = n+1
        self.tree = [0]*self.num
        for i,e in enumerate(init_list):
            self.update(i,e)

    def update(self,k,x):
        k = k+1
        while k < self.num:
            self.tree[k] += x
            k += (k&(-k))
        return 
    
    # sum([l,r))
    def query(self, l,r):
        ret = 0
        while r>0:
            ret += self.tree[r]
            r -= r&(-r)
        while l>0:
            ret -= self.tree[l]
            l -= l&(-l)
        
        return ret


N = int(input())
A = list(map(int,input().split()))
#%%
idxlist = [0]*N
for i,a in enumerate(A):
    idxlist[a-1] = i+2

A = [N+1]*2 + A + [N+1]*2
#%%
ans = 0
seg = BIT(N+4,[1]*2+[0]*N+[1]*2)

def judge(l,r,key):
    if l>r:
        l,r = r,l
    res = seg.query(l,r+1)
    if res>key:
        return False
    else:
        return True

def bsearch(idx,ng,key):
    ok = idx
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if judge(idx,mid,key):
            ok = mid
        else:
            ng = mid
    return ng


for idx in reversed(idxlist):
    if A[idx]==N:
        seg.update(idx,1)
        continue
    ng_l = 0
    ng_r = N+3
    
    L1 = bsearch(idx,ng_l,0)
    L2 = bsearch(idx,ng_l,1)
    R1 = bsearch(idx,ng_r,0)
    R2 = bsearch(idx,ng_r,1)
    
    coef = 0
    if A[L1]!=N+1:
        coef += (L1-L2)*(R1-idx)
    if A[R1]!=N+1:
        coef += (R2-R1)*(idx-L1)
    ans += A[idx]*coef
    seg.update(idx,1)
    
print(ans)
### BUGGY CODE ###

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

A.insert(0,-1)
root = [1]
next = A[1]
rf = 0

for _ in range(K):
    if next not in root:
        root.append(next)
        next = A[next]
    else:
        rf = root.index(next)
        root = root[rf:]
        break

print(root[(K - rf) % len(root)])


### FIXED CODE ###

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

A.insert(0,-1)
root = [1]

for _ in range(N-1):
    root.append(A[root[-1]])

if K > N:
    start = root.index(root[-1])
    index = (K - start) % (len(root) - start - 1) + start
    ans = root[index]
else:
    ans = root[K]

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

import sys
def input():
    return sys.stdin.readline()[:-1]

n, k = map(int, input().split())
s = str(input())

u = s + s[::-1]
ss = s

times = min(n, k)
for i in range(times):
    for j in range(n):
        part = u[j:j+n]
        if part < ss:
            ss = part
    s = ss
    u = s[::-1] + s

print(s)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

n, k = map(int, input().split())
s = str(input())

u = s + s[::-1]
ss = s

if n < k**2:
    smallest = sorted(s)[0]
    print(smallest * n)

else:
    times = min(n, k)
    for i in range(times):
        for j in range(n):
            part = u[j:j+n]
            if part < ss:
                ss = part
        s = ss
        u = s[::-1] + s
    print(s)
### BUGGY CODE ###

N,M = list(map(int,input().split()))
MAX = 1000000000
S = []
Room = [MAX for i in range(N)]#2 - N
Room[0] = 0
ACCESS = [0 for i in range(N-1)]
for _ in range(M):
    a,b = list(map(int,input().split()))
    S.append([a,b])
    S.append([b,a])
for i in S:
    if i[0] == 1:
        Room[i[1]-1] = 1
        ACCESS[i[1]-2] = 1
        #S.remove(i)
depth = 1
while max(Room) > MAX/2:
    for i in range(len(Room)):
        if Room[i] ==depth:
            for j in S:
                if (j[0] == i+1)*(Room[j[1]-1]>MAX/2):
                    Room[j[1]-1] = depth+1
                    ACCESS[j[1]-2] = i+1
    depth += 1
print('Yes')
for i in ACCESS:
    print(i)

### FIXED CODE ###

N,M = list(map(int,input().split()))
MAX = 1000000000
import queue
dist = [MAX for i in range(N)]
pre = [-1 for i in range(N)]
To = [[] for i in range(N)]#indexに向かっている部屋番号の集合

que = queue.Queue()

for _ in range(M):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    To[a].append(b)
    To[b].append(a)
dist[0] = 0
que.put(0)
while(not que.empty()):
    v = que.get()
    for u in To[v]:
        if pre[u] != -1: continue
        dist[u] = dist[v] + 1
        que.put(u)
        pre[u] = v
        
        
print('Yes')
for i in pre[1:N]:
    print(i+1)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
p=1
for i in l:
    p*=i
if(p>10**18):
    print(-1)
else:
    print(p)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
p=1
l.sort()
for i in l:
    p*=i
    if(p==0):
        print(0)
        exit()
    if(p>10**18):
        print(-1)
        exit()
print(p)
### BUGGY CODE ###

from sys import stdin
import sys

# A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
# A,B = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
# A, B = [str(x) for x in stdin.readline().rstrip().split()]
N = int(input())
S = list(input())
r = []
g = []
b = []
for i in range(N):
    if S[i] == 'R':
        r.append(i+1)
    elif S[i] == 'G':
        g.append(i+1)
    else:
        b.append(i+1)
# print(r)
# print(g)
# print(b)
cnt = 0
for i in range(len(r)):
    for j in range(len(g)):
        for k in range(len(b)):
            x = min(r[i], g[j], b[k])
            y = max(r[i], g[j], b[k])
            if r[i] != x and r[i] != y:
                if r[i]-x != y-r[i]:
                    cnt += 1
            elif g[j] != x and g[j] != y:
                if g[j]-x != y-g[j]:
                    cnt += 1
            else:
                if b[k]-x != y-b[k]:
                    cnt += 1
print(cnt)

### FIXED CODE ###

from sys import stdin
import sys

# A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
# A,B = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
# A, B = [str(x) for x in stdin.readline().rstrip().split()]
N = int(input())
S = list(input())
r = []
g = []
b = []
for i in range(N):
    if S[i] == 'R':
        r.append(i+1)
    elif S[i] == 'G':
        g.append(i+1)
    else:
        b.append(i+1)
# print(r)
# print(g)
# print(b)
cnt = len(r)*len(g)*len(b)
for i in range(N):
    for j in range(i+1, N):
        k = 2*j-i
        if k < N and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            cnt -= 1
print(cnt)
### BUGGY CODE ###

while True:
    n = input()
    if n==0: break
    s=[]
    x=[]
    for i in range(n):
        x.append(input())
    for i in range(n):
        for j in range(i,n):
            s.append(sum(x[i:j+1]))
    print max(s)

### FIXED CODE ###

n=input()
while n:
    x=-100000
    m=x
    s=0
    while n:
        x=input()+max(0,x)
        m=max(m,x)
        n-=1
    print m
    n=input()
### BUGGY CODE ###

x,y = map(int,input().split())
p = list(map(int,input().split()))

bigPoint = 0
bigNumber = 0

for i in range(x-y+1):

    number = sum(p[i:i+y])

    if number > bigNumber:
        bigNumber = number
        bigPoint = i

print((bigNumber + y) / 2)


### FIXED CODE ###

def main():
    x,y = map(int,input().split())
    p = list(map(int,input().split()))

    number = sum(p[0:y])
    bigNumber = number

    for i in range(x-y):

        number = number - p[i] + p[i+y]

        if number > bigNumber:
            bigNumber = number

    print((bigNumber + y) / 2)

main()
### BUGGY CODE ###

n, m = (int(x) for x in input().split())
ab = []
for _ in range(m):
    a=int(input())
    ab.append(a)
dp = [0]*(n+1)
dp[0] = 1

for i in range(1,n+1):
    dp[i] += (dp[i-1]+dp[i-2])%1000000007
    if i in ab:
        dp[i] = 0
print(dp[-1])

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
 
dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
    if i in a:
        dp[i] = 0
print(dp[N])
### BUGGY CODE ###

s = list(input())
t = list(input())

n = len(s)
m = len(t)

dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

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

ans = ''
i = n
j = m
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans;
        i -= 1
        j -= 1

print(ans)

### FIXED CODE ###

s = list(input())
t = list(input())

n = len(s)
m = len(t)

dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

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

ans = ''
i = n
j = m
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans;
        i -= 1
        j -= 1

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
from math import log2
from bisect import bisect_left,bisect_right
a.sort()
# 0未満の個数
mn=bisect_left(a,0)
# 0の個数
zn=bisect_right(a,0)-mn
# 0より大きい個数
pn=n-mn-zn
am=a[:mn]
am=[-x for x in am[::-1]]
ap=a[mn+zn:]
# 自分より小さい数字がk個未満のうち最大の値を求める
# 自分より小さい数字がk個未満ならTrue
def func(x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,x//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k

if mn*pn<k:
    l,r=0,max(a[0]*a[1],a[-1]*a[-2])+1
else:
    l,r=a[0]*a[-1]-1,0
while r-l>1:
    x=(l+r)//2
    if func(x):
        l,r=x,r
    else:
        l,r=l,x
print(l)

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
a=np.array(list(map(int,input().split())))
a.sort()
p=a[a>0]
z=np.count_nonzero(a==0)
m=a[a<0]
r=10**19
l=-r
while r-l>1:
    # 区間[l,r]を半分に分けて探索。最終的にrが求める値になるようにする。
    # b以下のものがk個以上あるような、最小のbを求める。bを大きくする→b以下のものも増える。b以下のものがめちゃくちゃある→bを減らす。
    b=(l+r)//2
    c=0
    if b>=0:
        c+=z*n
    # 配列aに対し、配列b//pの要素たちをそれぞれsearchsortedする。結果の配列はb//pと同じ形になる。
    c+=a.searchsorted(b//p,side='right').sum()
    # 配列aに対し、配列b//mの要素たちをそれぞれsearchsortedする。結果の配列はb//mと同じ形になる。
    c+=n*len(m)-a.searchsorted(-(-b//m),side='left').sum()
    c-=np.count_nonzero(a*a<=b)
    if c//2>=k:
        r=b
    else:
        l=b
print(r)
### BUGGY CODE ###

s=input()
q=int(input())
cnt=0
for i in range(q):
  k=input()
  if k[0]=='1':
    cnt+=1
  else:
    if k[2]=='1':
      if cnt%2==0:
        s=k[4]+s
      else:
        s+=k[4]
    elif k[2]=='2':
      if cnt%2!=0:
        s=k[4]+s
      else:
        s+=k[4]
if cnt%2==0:
  pass
else:
  s=s[::-1]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
cnt=0
l=''
r=''
for i in range(q):
  k=input()
  if k[0]=='1':
    cnt+=1
  else:
    if k[2]=='1':
      if cnt%2==0:
        l=k[4]+l
      else:
        r+=k[4]
    elif k[2]=='2':
      if cnt%2!=0:
        l=k[4]+l
      else:
        r+=k[4]
if cnt%2==0:
  s=l+s+r
else:
  s=l+s+r
  s=s[::-1]
print(s)
### BUGGY CODE ###

N = int(input())
mojiretu = [input() for _ in range(N)]
mojiretu2 = []
answer = 0

for n in mojiretu:
  mojiretu2.append(''.join(sorted(list(n))))
 
for index, moji in enumerate(mojiretu2):
  i = index+1
  while i < N:
    if moji == mojiretu2[i]:
      answer+=1
    i+=1

print(answer)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
from itertools import groupby

def solve(N: int, s: "List[str]"):
    s = [sorted(s[i]) for i in range(N)]
    s.sort()
    group = groupby(s)
    answer = 0
    for key, group in group:
        a = len(list(group))
        answer += int(a*(a-1)/2) if a > 1 else 0
    print(answer)
   


    # for i in range(N):
    #     a = 1
    #     pop_index = []
    #     for j in range(i+1,len(ss)):
    #         if ss[i] == ss[j]:
    #             a += 1
    #             pop_index.append(j)
        
    #     ss = [ss[i] for i in range(len(ss)) if i not in pop_index]
    #     answer += int(a*(a-1)/2) if a > 1 else 0
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, s)

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

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

for number in range(1,n+1):
    for i in range(1,n+2-number):
        if(accum[number+i-1]-accum[i-1]==0):
            ans+=1
            
print (ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
ans=0
accum = [0]*(n+1)
accum[0]=0
for i in range(n):
    accum[i+1]=a[i]+accum[i]

z=Counter(accum)
for k,v in z.items():
    ans+=v*(v-1)/2
    
print(int(ans))
### BUGGY CODE ###

import heapq
n, m = map(int, input().split())
a_lst = list(map(int, input().split()))
bc_lst = [list(map(int, input().split())) for _ in range(m)]

aa_lst = a_lst[:]

heapq.heapify(aa_lst)
for bc in bc_lst:
    for i in range(bc[0]):
        if aa_lst[0] < bc[1]:
            heapq.heapreplace(aa_lst, bc[1])
        
print(sum(aa_lst))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a_lst = list(map(int, input().split()))
bc_lst = [list(map(int, input().split())) for _ in range(m)]

bc_lst = sorted(bc_lst, key = lambda x: -x[1])
aa_lst = a_lst[:]

heapq.heapify(aa_lst)
for bc in bc_lst:
    for i in range(bc[0]):
        if aa_lst[0] < bc[1]:
            heapq.heapreplace(aa_lst, bc[1])
        else:
            break
        
print(sum(aa_lst))