Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7

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

for i in range(n+1):
    count[a[i]-1] += 1
    if count[a[i]-1] == 2:
        right = i
        left = a.index(a[i])
        break

def nCr_mod_p(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for i in range(1,n+2):
    ans = nCr_mod_p(n+1,i,p) - nCr_mod_p(n-right+left,i-1,p)
    print(ans%p)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7

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

for i in range(n+1):
    count[a[i]-1] += 1
    if count[a[i]-1] == 2:
        right = i
        left = a.index(a[i])
        break

def nCr_mod_p(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

for i in range(2, N + 2):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for i in range(1,n+2):
    ans = nCr_mod_p(n+1,i,p) - nCr_mod_p(n-right+left,i-1,p)
    print(ans%p)
n=int(input())
a=list(map(int,input().split()))
ans=[i for i in range(n)]
for i in range(n):
    ans[i]=a.index(i+1)+1
print(*ans)

### FIXED CODE ###

n=int(input())
print((-(-n//2))/n)
def prime_number(x):
    if x==2 or x==3:
        return True
    else:
        if x%2==0 or x%3==0:
            return False
        else:
            divisor_lst = [1,x]
            for i in range(1,x+1):
                if i not in divisor_lst and x%i==0:
                    return False
                    break
            else:
                return True

n = int(input())

if prime_number(n):
    print(n-1)
else:
    i = 1
    divisor_lst = []
    while i<=j:
        i += 1
        j = n//i
        if n%i==0:
            divisor_lst.append([i,j])

    n_x = divisor_lst[-1][0]
    n_y = divisor_lst[-1][1]
    print(n_x+n_y-2)

### FIXED CODE ###

n = int(input())

need_lst = []
for i in range(1,int(n**(1/2)+1)):
    if n%i==0:
        need = i+n//i
        need_lst.append(need-2)

print(min(need_lst))
n,k = map(int, input().split())
a = list(map(int, input().split()))
visit = [-1 for i in range(n)]
root = []
now = 1
length = 0
root.append(now)
if k > n:
    for i in range(n):
        if visit[now - 1] != 1:
            visit[now - 1] = 1
            now = a[now - 1]
            root.append(now)
            length += 1
        else:break
    start = 0
    for i in range(n):
        if root[i] == now:
            start = i
            break
    length -= start + 1
    k -= start
    k %= length
    ans = root[start]
    for i in range(k):
        ans = root[start + i]
    print(ans)
else:
    for i in range(k):
        now = a[now - 1]
    print(now)

### FIXED CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))
visit = [-1 for i in range(n)]
root = []
now = 1
length = 0
root.append(now)
if k > n:
    for i in range(n):
        if visit[now - 1] != 1:
            visit[now - 1] = 1
            now = a[now - 1]
            root.append(now)
            length += 1
        else:break
    start = 0
    for i in range(n):
        if root[i] == now:
            start = i
            break
    length -= start
    k -= start
    k %= length
    ans = root[start + k]
    print(ans)
else:
    for i in range(k):
        now = a[now - 1]
    print(now)
# ABC044 B - 美しい文字列 / Beautiful Strings
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

S = si()
SS = set()
for s in S:
    SS.add(s)

for ss in SS:
    if S.count(SS)%2==1:
        print('No')
        exit()
print('Yes')


### FIXED CODE ###

# ABC044 B - 美しい文字列 / Beautiful Strings
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

S = si()
SS = set()
for s in S:
    SS.add(s)

for ss in SS:
    if S.count(ss)%2==1:
        print('No')
        exit()
print('Yes')
from bisect import bisect_left
N, *A = map(int, open(0).read().split())

B = A[:]
A_MAX = max(B)
B.remove(A_MAX)

ans = []
while len(B) > 1:
    B.sort()
    x = B.pop()
    y = B.pop()
    if y >= 0:
        idx = bisect(B, x - y)
        B = B[:idx] + [x - y] + B[idx:]
        ans.append([x, y])
    else:
        idx = bisect(B, y - x)
        B = B[:idx] + [y - x] + B[idx:]
        ans.append([y, x])
    
if B[0] <= 0:
    print(A_MAX - B[0])
    ans.append([A_MAX, B[0]])
else:
    print(B[0] - A_MAX)
    ans.append([B[0], A_MAX])
for i in range(N - 1):
    print(*ans[i])

### FIXED CODE ###

N, *A = map(int, open(0).read().split())

x = sorted([v for v in A if v >= 0])
y = sorted([v for v in A if v < 0], reverse=True)

ans = []
if len(y) == 0:
    cnt = x[0]
    for v in x[1:-1]:
        ans.append((cnt, v))
        cnt -= v
    ans.append((x[-1], cnt))
    print(x[-1] - cnt)
elif len(x) == 0:
    cnt = y[0]
    for v in y[1:]:
        ans.append((cnt, v))
        cnt -= v
    print(cnt)
else:
    for v in x[:-1]:
        ans.append((y[0], v))
        y[0] -= v
        
    cnt = x[-1]
    for v in y:
        ans.append((cnt, v))
        cnt -= v
    print(cnt)
    
for v in ans:
    print(*v)
N = int(input())
for n in range(1, 3501):
    for w in range(i, 3501):
        t = (N*n*w) % (4*n*w - N*w - N*w)
        if t == 0:
            print(t,n,w)
            exit()


### FIXED CODE ###

N = int(input())
for n in range(1, 3501):
    for w in range(n, 3501):

        try:
            t = (N*n*w) % (4*n*w - N*w - N*n)
        except:
            continue

        if t == 0 and 4*n*w - N*w - N*n>=0:
            print((N*n*w) // (4*n*w - N*w - N*n), n, w)
            exit()
N, K=map(int, input().split())
x = list(map(int, input().split()))
ans = pow(10, 10)
for i in range(N-K+1):
    temp1 = abs(x[i]) + abs(x[i]-x[i+K-1])
    #temp2 = abs(x[i+K-1]) + abs(x[i]-x[i+K-1])
    ans = min(ans, temp1, temp2)
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
x = list(map(int, input().split()))
ans = pow(10, 10)
for i in range(N-K+1):
    temp_l = abs(x[i]) + abs(x[i]-x[i+K-1])
    temp_r = abs(x[i+K-1]) + abs(x[i]-x[i+K-1])
    ans = min(ans, temp_l, temp_r)
print(ans)
D =int(input())
print('Christmas' if D==25 else 'Christmas Eve' if D==24 else 'Christmas Eve Eve' if D==23 else 'Christmas Eve Eve Eve' if D==22)

### FIXED CODE ###

D =int(input())
print('Christmas'+' Eve'*(25-D))
a = list(map(int, input().split()))
if a[0] == a[1]:
    print(a[3])
elif a[0] == a[2]:
    print(a[1])
elif a[1] == a[2]:
    print(a[0])


### FIXED CODE ###

a = list(map(int, input().split()))
if a[0] == a[1]:
    print(a[2])
elif a[0] == a[2]:
    print(a[1])
elif a[1] == a[2]:
    print(a[0])
N, K=map(int,input().split())
A=list(map(int,input().split()))
B=sorted([(a,abs(a)) for a in A],key=lambda x:x[1],reverse=True)
R=10**9+7
P=1
minus=0
last_neg=-1
last_pos=-1
for i in range(K):
    if B[i][0]>0:
        if last_pos != -1:
            P = (P * B[last_pos][1]) % R
        last_pos=i
    else:
        if last_neg != -1:
            P = (P * B[last_neg][1]) % R
        minus+=1
        last_neg=i
if minus%2==1:
    first_neg=-1
    first_pos=-1
    count=[0,0]
    for i in range(K,N):
        if count[0]==0 and B[i][0]>0:
            first_pos=i
            count[0]=1
            if last_neg<last_pos:
                count[1]=1
                break
        elif count[1]==0 and B[i][0]<0:
            first_neg=i
            count[1]=1
            if last_pos<last_neg:
                count[0]=1
                break
        elif count==[1,1]:
            break
    if first_pos==-1 and last_pos==-1:
        P = 1
        for i in range(K):
           P = (P * B[N - i - 1][0]) % R
        print(P)
        exit()
    list_product=[]
    if first_neg!=-1:
        list_product.append((P*B[last_neg][1]*B[first_neg][1]) %R)
    if first_pos!=-1 and last_pos!=-1:
        list_product.append((P*B[last_pos][1]*B[first_pos][1]) %R)
    print(max(list_product))
else:
    if last_pos!=-1:
        print((P*B[last_pos][1]*B[last_neg][1]) %R)
    else:
        print((P*B[last_neg][1]) % R)

### FIXED CODE ###

import copy
N, K=map(int,input().split())
A=list(map(int,input().split()))
B=sorted([(a,abs(a)) for a in A],key=lambda x:x[1],reverse=True)
R=10**9+7
P=1
minus=0
last_neg=-1
last_pos=-1
for i in range(K):
    if B[i][0]>0:
        if last_pos != -1:
            P = (P * B[last_pos][1]) % R
        last_pos=i
    elif B[i][0]<0:
        if last_neg != -1:
            P = (P * B[last_neg][1]) % R
        minus+=1
        last_neg=i
    else:
        print(0)
        exit()
F=copy.copy(P)
if last_pos!=-1:
    F=(F*B[last_pos][1]) % R
if last_neg!=-1:
    F=(F*B[last_neg][1]) % R
if minus%2==1:
    if K == N:
        print(-F %R)
        exit()
    first_neg=-1
    first_pos=-1
    count=[0,0]
    for i in range(K,N):
        if count[0]==0 and B[i][0]>0:
            first_pos=i
            count[0]=1
        elif count[1]==0 and B[i][0]<0:
            first_neg=i
            count[1]=1
        elif count==[1,1]:
            break
    if first_pos==-1 and last_pos==-1:
        P = 1
        for i in range(K):
           P = (P * B[N - i - 1][0]) % R
        print(P)
        exit()
    if first_pos==-1 and first_neg==-1:
        print(0)
        exit()
    list_product=[]
    if first_neg!=-1 and last_pos!=-1:
        list_product.append(B[last_neg][1]*B[first_neg][1])
    if first_pos!=-1:
        P1=B[first_pos][1]
        if last_pos!=-1:
            P1=P1*B[last_pos][1]
        list_product.append(P1)
    print(max(list_product)*P %R)
else:
    print(F)
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def main():
    n = int(input())
    a = list(map(int, input().split()))
    left = [0 for _ in range(n)]
    right = [0 for _ in range(n)]
    for i in range(1, n):
        l = math.gcd(a[i - 1], a[i])
        r = math.gcd(a[n - i - 1], a[n - i - 2])
        left[i] = l
        right[n - i - 2] = r

    m = max(left[0], right[n - 1])
    for i in range(n - 1):
        m = max(m, left[i - 1], right[i + 1])
    print(m)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd

def main():
    n = int(input())
    a = list(map(int, input().split()))
    left = [0]
    right = [0]
    for i in range(1, n):
        g = gcd(left[-1], a[i - 1])
        left.append(g)
    for i in range(n - 2, -1, -1):
        g = gcd(right[-1], a[i + 1])
        right.append(g)
    right.reverse()
    m = 0
    for i in range(0, n):
        m = max(m, gcd(left[i], right[i]))
    print(m)
    
if __name__ == '__main__':
    main()
N = int(input())
a = list(map(int, input().split()))
res = a[:]
 
for i in range(n, 0, -1):
    ans[i] = sum(ans[i : : i]) % 2 
print(sum(res))
print(*[i + 1 for i in range(n) if res[i]])

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
res = [0] + a[:]
for i in range(N, 0, -1):
  res[i] = sum(res[i : : i]) % 2 
print(sum(res))
print(*[i for i in range(N + 1) if res[i]])
A, B, C = list(map(int, input().split()))
li = [A,B,C].sort()
ans = sum(li[:2]) + li[2] * 10

print(ans)

### FIXED CODE ###

A, B, C = list(map(int, input().split()))

ans = A + B + C + 9 * max(A, B, C)

print(ans)
X = input()
ans = 'Yes' if X >= 30 else 'No'
print(ans)

### FIXED CODE ###

X = input()
ans = 'Yes' if int(X) >= 30 else 'No'
print(ans)
import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())
c+=[0]
qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*n

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)
from math import log2

N = input()
number = input()

a = number.split()
n_list=[]
count=0



for num in a:
    num = int(num)
    if num % 2 == 0:
        n_list.append(num)


if n_list != []:
    maxnum = max(n_list)
    maxnum = log2(maxnum)
    for num2 in n_list:
        for i in range(maxnum):
            if num2 % 2**(i+1) == 0:
                count+=1


print(count)

### FIXED CODE ###

from math import log2

N = input()
number = input()

a = number.split()
n_list=[]
count=0



for num in a:
    num = int(num)
    if num % 2 == 0:
        n_list.append(num)


if n_list != []:
    maxnum = max(n_list)
    maxnum = log2(maxnum)
    maxnum = int(maxnum)
    for num2 in n_list:
        for i in range(maxnum):
            if num2 % 2**(i+1) == 0:
                count+=1


print(count)
first = input().split()
n = int(first[0])
r = int(first[1])
while n != 0 or r != 0:
    i = 0
    card = list(range(n))
    while i < r:
        sh = input().split()
        p, c = list(map(int,sh))
        card = card[p-1:p+c-2:] + card[0:p-2:] + card[p+c-1:n:]
        i = i + 1
    print(n - int(card[0]))
    next = input().split()
    n, r = list(map(int,next))

### FIXED CODE ###

first = input().split()
n = int(first[0])
r = int(first[1])
while n != 0 or r != 0:
    i = 0
    card = list(range(1,n+1))[::-1]
    while i < r:
        sh = input().split()
        p, c = list(map(int,sh))
        card = card[p-1:p+c-1] + card[:p-1] + card[p+c-1:]
        i = i + 1
    print(card[0])
    next = input().split()
    n, r = list(map(int,next))
n = int(input())
a = []
for i in range(n):
  s, p = list(map(int, input().split()))
  a.append([s,-p,i])
a.sort()
for i in a:
  print(i[-1])


### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  s, p = input().split()
  a.append([s,-int(p),i])
a.sort()
for i in a:
  print(i[-1]+1)
a,b = map(int,input().split())

if a*b%2 == 0:
     print (Even)
else:
     print (Odd)


### FIXED CODE ###

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

if a*b%2 == 0:
     print ('Even')
else:
     print ('Odd')
a,b = map(int,input().split())
print(b+a)

### FIXED CODE ###

a,b = input().split()
print(b+a)
import math
r=float(input())

print(math.PI*r**2, 2*math.PI*r)



### FIXED CODE ###

import math

r = float(input())

S = math.pi * r * r
l = 2 * r * math.pi

print('{0:f} {1:f}'.format(S,l))
n,m = map(int,input().split())
a = list(int(input())for i in range(m))
mod = 10**9+7
b = [0] * (n-1)
b[0] = 1
b[1] = 1
for i in a:
    b[i] = -1

for i in range(2,n+1):
    if b[i] == -1:
        continue
    if b[i-1] != -1:
        b[i] += b[i-1]
    if b[i-2] != -1:
        b[i] += b[i-2]

print(b[-1]%mod)

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=10**9+7
b=[0]*(n+1)
b[0]=1
b[1]=1

for i in a:
    b[i]=-1

for i in range(2,n+1):
    if b[i]==-1:
        continue
    if b[i-1]!=-1:
        b[i]+=b[i-1]
    if b[i-2]!=-1:
        b[i]+=b[i-2]
        
print(b[-1]%mod)
import numpy as np

anum = {}
ans = 0

N = int(input())
strings = [''.join(sorted(input())) for i in range(N)]

for i in s:
    if i in anum:
        ans += anum[i]
    else:
        anum[i] = 1

print(ans)


### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]
dict = {}
ans = 0

for i in s:
    if i in dict:
        ans += dict[i]
        dict[i] += 1
    else:
        dict[i] = 1

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


j_Aj=[0]
i_Ai=[0]*(10**9+2*10**5)

for j,aj in enumerate(a):
    j_Aj.append(j+1-aj)
ans=0
for j,j_aj in enumerate(j_Aj):
    if j==0:
        continue
    if j_aj>=2:
        ans+=i_Ai[j_aj]
    i_Ai[j+a[j-1]]+=1
print(ans)


### FIXED CODE ###

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

j_Aj = [0]

for j, aj in enumerate(a):
    j_Aj.append(j + 1 - aj)
maxj=max(j_Aj)
i_Ai = [0] * (maxj+1)
ans = 0
for j, j_aj in enumerate(j_Aj):
    if j == 0:
        continue
    if j_aj >= 2:
        ans += i_Ai[j_aj]
    if j + a[j - 1]<=maxj:
        i_Ai[j + a[j - 1]] += 1
print(ans)
def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
MOD = 1_000_000_007
aaa = list(map(int, input().split()))
if N == K:
    print(prod(aaa, MOD))
    exit()
aaa.sort(key=lambda x : abs(x))
if sum(a < 0 for a in aaa[-K:]) % 2 == 0:
    print(prod(aaa[-K:], MOD))
else:
    if all(a <= 0 for a in aaa):
        bbb = aaa[:K]
    else:
        try:
            x1, y1 = max([a for a in aaa[-K:] if a > 0]), max([a for a in aaa[:-K] if a < 0])
        except:
            x1, y1 = 1, -(10**9+1)
        try:
            x2, y2 = max([a for a in aaa[-K:] if a < 0]), max([a for a in aaa[:-K] if a >= 0])
        except:
            x2, y2 = -(10**9+1), 1
        bbb = aaa[-K:]
        if abs(x2 * y1) > abs(x1 * y2):
            bbb.remove(x1)
            bbb.append(y1)
        else:
            bbb.remove(x2)
            bbb.append(y2)
    print(prod(bbb, MOD))


### FIXED CODE ###

def prod(li, MOD):
    ret = 1
    for a in li:
        ret *= a
        ret %= MOD
    return ret

N, K = map(int, input().split())
MOD = 1_000_000_007
aaa = list(map(int, input().split()))
if N == K:
    print(prod(aaa, MOD))
    exit()
aaa.sort(key=lambda x : abs(x))
if sum(a < 0 for a in aaa[-K:]) % 2 == 0:
    print(prod(aaa[-K:], MOD))
else:
    if all(a <= 0 for a in aaa):
        bbb = aaa[:K]
    else:
        try:
            x1, y1 = min([a for a in aaa[-K:] if a > 0]), min([a for a in aaa[:-K] if a < 0])
        except:
            x1, y1 = 1, 0
        try:
            x2, y2 = max([a for a in aaa[-K:] if a < 0]), max([a for a in aaa[:-K] if a >= 0])
        except:
            x2, y2 = 1, 0
        bbb = aaa[-K:]
        if abs(x2 * y1) > abs(x1 * y2):
            bbb.remove(x1)
            bbb.append(y1)
        else:
            bbb.remove(x2)
            bbb.append(y2)
    print(prod(bbb, MOD))
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, k = map(int, input().split())
for i in range(1, k+1):
  print(combinations_count(k-1, i-1) * combinations_count(i+1+(n-k)-(i-1)-1, (n-k)-(i-1)) % 1000000007) 

### FIXED CODE ###

import math

def myfactorial(n):
  return math.factorial(n)

def combinations_count(n, r):
  return (myfactorial(n) // (myfactorial(n - r) * myfactorial(r))) % 1000000007

n, k = map(int, input().split())
for i in range(1, k+1):
  if n-k+1 < i:
    print(0)
  else:
    print(combinations_count(k-1, i-1) * combinations_count(n-k+1, i) % 1000000007)
if int(input()) > 30 print('Yes') else print('No')

### FIXED CODE ###

print('Yes') if (int(input())) >= 30 else print('No')
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
s = input()
q = I()
straight = True
ans = deque(s)
for i in range(q):
    A = input().split()
    if A[0] == '1':
        straight = not straight
    else:
        if straight:
            if A[1] == '1':
                ans.append(A[2])
            else:
                ans.appendleft(A[2])
        else:
            if A[1] == '1':
                ans.appendleft(A[2])
            else:
                ans.append(A[2])
if straight:
    print(*ans,sep='')
else:
    print(*an[::-1],sep='')


### FIXED CODE ###

from collections import deque
d = deque([])
ans = input()
d.append(ans)
q = int(input())
rev = True # Trueなら後ろに # Falseなら前に
for i in range(q):
    Query = list(map(str,input().split()))
    if Query[0] == '2':
        if Query[1] == '1':
            if rev:
                d.append(Query[2])
            else:
                d.appendleft(Query[2])
        elif Query[1] == '2':
            if rev:
                d.appendleft(Query[2])
            else:
                d.append(Query[2])
    else:
        rev = rev^True
output = ""
while d:
    output += d.pop()
if rev:
    print(output)
else:
    print(output[::-1])
import numpy as np
N , W = map(int, input().split())
goods = np.array([list(map(int , input().split())) for _ in range(N)])
dp = np.zeros((N + 1 , W + 1) , dtype = np.int)

for i in range(0,N):
    w, v = goods[i]
    dp[i + 1, w:] = np.maximum(dp[i,w:] , dp[i,:-w] + v)
    dp[i + 1, :] = np.maximum(dp[i + 1,:],dp[i,:])
print(int(dp[N,W]))

### FIXED CODE ###

N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
value_sum = sum(value)
dp = []
for _ in range(N + 1):
    dp_val = [float('inf') for _ in range(value_sum + 1)]
    dp.append(dp_val)
dp[0][0] = 0

for idx in range(N):
    for v in range(value_sum + 1):
        if value[idx] <= v:
            dp[idx + 1][v] = min(dp[idx][v], dp[idx][v - value[idx]] + weight[idx])
        else:
            dp[idx + 1][v] = dp[idx][v]
ans = 0
# print(dp)
for i in range(value_sum + 1):
    if dp[-1][i] <= W:
        ans = i
print(ans)