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

# coding: utf-8
# Your code here!
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
@lru_cache(maxsize=None)
def dp(x):
    for i in a:
        if x < i:
            return -1
        else:
            if dp(x-i) == -1:
                return 1
    return -1


if dp(k)==1:
    print("First")
else:
    print("Second")






    




### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

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

# 1:先手　-1:後手
memo = [0]*(k+1)
def dp(x):
    if memo[x] != 0:
        return memo[x]
    for i in a:
        if x < i: break
        else:
            if dp(x-i) == -1:
                memo[x] = 1
                return 1
    memo[x] = -1
    return -1

if dp(k)==1:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

s = list(map(ord, list(input())))
ls = len(s)
lk = int(input())
if lk*2 >= ls: print(ls); exit(0)
lk *= 2
dp = [[[0]*(lk+1) for _ in range(ls+1)] for i in range(ls+1)]
for k in range(lk+1):
  for i in range(ls):
    for j in range(ls):
      if s[i] == s[-j-1]:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i][j][k] + 1)
      else:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i+1][j][k], dp[i][j+1][k], (k > 0)*(dp[i][j][k-1] + 1))
print(max(dp[ls][ls]))

### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()
### BUGGY CODE ###

n, q = list(map(int , input().split()))
s = input()

for cnt in range(q):
  l, r = list(map(int , input().split()))
  print(s[l-1:r].count('AC'))

### FIXED CODE ###

# 累積和の考え方
#   listに積み重ねた数値を出しておくことで特定範囲の数値を求める時間を短縮する
#   例：ABBBBAABBBBAB があるときに(l,r)にAがいくつ含まれるかを求める場合は以下のように(1長い)listを作る
#      BBABBBAABBBBAA
#      000111123333345
#   このリストの文字列のr-lで出せる(3,7)ならstr[7]-str[3]を出すと3-1で2となる

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

# 累積和のリストを作成
cumsum = [0]*(n+1)
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        cumsum[i+1]+=cumsum[i]+1
    else:
        cumsum[i+1]=cumsum[i]

# 012345   index
# 123456   input
# ACACAC   s
# 0011223  cumsum
for left, right in lr:
    print(cumsum[right]-cumsum[left])
### BUGGY CODE ###

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

ab_list = []
tree_dict = {}
for i in range(N-1):
    a, b = map(int, input().split())
    ab_list.append(a)
    ab_list.append(b)

    if a not in tree_dict:
        tree_dict[a] = [b]
    else:
        tree_dict[a].append(b)

value_dict = {k:0 for k in list(set(ab_list))}

p_list = []
x_list = []
for i in range(Q):
    p, x = map(int, input().split())
    p_list.append(p)
    x_list.append(x)

for p, x in zip(p_list, x_list):
    f = 0
    kk_list = [p]
    while(1):
        if len(kk_list) == 0:
            f = 1
            break
        k = kk_list[0]
        value_dict[k] += x
        if k in tree_dict:
            kk_list += tree_dict[k]
        kk_list.pop(0)
        if f == 1:
            break

print(' '.join([str(v) for k, v in value_dict.items()]))

### FIXED CODE ###

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

ab_list = []
tree_dict = {}
for i in range(N-1):
    a, b = map(int, input().split())
    ab_list.append(a)
    ab_list.append(b)

    if a not in tree_dict:
        tree_dict[a] = [b]
    else:
        tree_dict[a].append(b)

value_list = list(set(ab_list))

px_dict = {}
for i in range(Q):
    p, x = map(int, input().split())
    if p in px_dict:
        px_dict[p] += x
    else:
        px_dict[p] = x

out = ""
for v in value_list:
    if v in px_dict:
        x = px_dict[v]
        if v in tree_dict:
            tree_list = tree_dict[v]
            for t in tree_list:
                if t in px_dict:
                    px_dict[t] += x
                else:
                    px_dict[t] = x
        o = str(px_dict[v])
    else:
        o = str(0)
    out += o + " "

print(out[:-1])
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
s = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    ab = abs(l[i]-l[j])
    for k in range(j+1,n):
      if l[k] >= l[i] + l[j]:
        break
      if ab < l[k]:
        s += 1
print(s)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
s = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    high = n-1
    low = j+1
    ab = l[i] + l[j]
    if l[j+1] >= ab:
      continue
    while high - low > 1:
      mid = (high+low)//2
      if l[mid] < ab:
        low = mid
      else:
        high = mid
    if l[high] < ab:
      s += high - j
    else:
      s += low - j
print(s)
### BUGGY CODE ###

import itertools

def calc(vlist):
    sum = vlist[0]
    for i in range(len(vlist) - 1):
        sum = ((sum + vlist[i+1]) / 2)        

    return sum

try:
    n = int(input())
    
    v = [int(x) for x in input().split(' ')]
    
    pattern = itertools.permutations(v)
    
    results = []
    for plist in pattern:
      results.append(calc(plist))
      
    print(max(results))
    
except ValueError:
    print("数値を入力してください")

### FIXED CODE ###

def calc(vlist):
    sum = vlist[0]
    for i in range(len(vlist) - 1):
        sum = ((sum + vlist[i+1]) / 2)

    return sum
   
try:
    n = int(input())

    v = [int(x) for x in input().split(' ')]
    v.sort()
    
    print(calc(v))
    
except ValueError:
    print("数値を入力してください")
### BUGGY CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
L = [min(abs(A[i]-A[j]), K -abs(A[i]-A[j])) for i in range(N-1) for j in range(i+1,N)]
print (K-max(L))

### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
ans = min(A[-1]-A[0],K-(A[-1]-A[0]))
for i in range(N-1):
  ans = max(ans,A[i+1]-A[i])
print (K-ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(N//R+1):
    for j in range((N-R*i)//G+1):
        if (N-R*i-G*j)%B == 0 and (N-R*i-G*j)>=0:
            ans += 1
print(ans)



### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for i in range(N//R+1):
    for j in range((N-R*i)//G+1):
        if (N-R*i-G*j)%B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
num = []
count = 0
for i in range(N):
    S.append(input())
    num.append(1)
    for j in range(S[i].count('a')):
        num[i] *= 103
    for j in range(S[i].count('b')):
        num[i] *= 107
    for j in range(S[i].count('c')):
        num[i] *= 109
    for j in range(S[i].count('d')):
        num[i] *= 113
    for j in range(S[i].count('e')):
        num[i] *= 127
    for j in range(S[i].count('f')):
        num[i] *= 2
    for j in range(S[i].count('1')):
        num[i] *= 3
    for j in range(S[i].count('h')):
        num[i] *= 5
    for j in range(S[i].count('i')):
        num[i] *= 7
    for j in range(S[i].count('j')):
        num[i] *= 11
    for j in range(S[i].count('k')):
        num[i] *= 13
    for j in range(S[i].count('l')):
        num[i] *= 17
    for j in range(S[i].count('m')):
        num[i] *= 19
    for j in range(S[i].count('n')):
        num[i] *= 23
    for j in range(S[i].count('o')):
        num[i] *= 29
    for j in range(S[i].count('p')):
        num[i] *= 31
    for j in range(S[i].count('q')):
        num[i] *= 37
    for j in range(S[i].count('r')):
        num[i] *= 41
    for j in range(S[i].count('s')):
        num[i] *= 43
    for j in range(S[i].count('t')):
        num[i] *= 47
    for j in range(S[i].count('u')):
        num[i] *= 73
    for j in range(S[i].count('v')):
        num[i] *= 79
    for j in range(S[i].count('w')):
        num[i] *= 83
    for j in range(S[i].count('x')):
        num[i] *= 89
    for j in range(S[i].count('y')):
        num[i] *= 97
    for j in range(S[i].count('z')):
        num[i] *= 101

for i in range(N):
    for j in range(i+1, N):
        if num[i] == num[j]:
            count += 1

print(count)


### FIXED CODE ###

N = int(input())
S = []
count = 0

dic = {}
for i in range(N):
    S.append(input())
    S[i] = sorted(S[i])
    S[i] = ''.join(S[i])
    if dic.setdefault(S[i], 0) > 0:
        count += dic[S[i]]
        dic[S[i]] += 1
    else:
        dic[S[i]] = 1
print(count)
### BUGGY CODE ###

N=int(input())
b=1
for a in range(1,N+1):
    b*=a
count=0
for c in range(1,b+1):
    if b%c==0:
        count+=1
    else:
        pass
print(count%(10**9+7))


### FIXED CODE ###

N=int(input())
b=1
for a in range(1,N+1):
    b*=a
numbers=[2]
for c in range(3,N+1):
    count=0
    for d in numbers:
        if not c%d==0:
            count+=1
        else:
            pass
    if count==len(numbers):
        numbers.append(c)
    else:
        pass
answers=[]
while b>1:
    for e in numbers:
        kazu=0
        while b%e==0:
            b=b//e
            kazu+=1
        answers.append(kazu)
kotae=1
for f in answers:
    kotae*=(f+1)
print(kotae%(10**9+7))
### BUGGY CODE ###

s=input()+'T'
x,y=list(map(int,input().split()))
x+=10000
y+=10000
n=len(s)
i=0

while i<n and s[i]=='F':
    i+=1

dx=[[0]*20000 for _ in range(10000)]
dy=[[0]*20000 for _ in range(10000)]

dx[0][i+10000]=1
dy[0][10000]=1

lstx=[]
lsty=[]
d='x'
cnt=0

while i<n:
    if s[i]=='F':
        cnt+=1
    else:
        if cnt>0:
            if d=='x':
                lstx.append(cnt)
            else:
                lsty.append(cnt)
        
        if d=='x':
            d='y'
        else:
            d='x'
        cnt=0
    
    i+=1

for i,cx in enumerate(lstx):
    for j in range(20000):
        if dx[i][j]==0:
            continue
        if j+cx<20000:
            dx[i+1][j+cx]=1
        if j-cx>-1:
            dx[i+1][j-cx]=1

for i,cy in enumerate(lsty):
    for j in range(20000):
        if dy[i][j]==0:
            continue
        if j+cy<20000:
            dy[i+1][j+cy]=1
        if j-cy>-1:
            dy[i+1][j-cy]=1

if dx[len(lstx)][x]==1 and dy[len(lsty)][y]==1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s=input()+'T'
x,y=list(map(int,input().split()))
x+=8000
y+=8000
n=len(s)
i=0

while i<n and s[i]=='F':
    i+=1

dx=[[0]*16001 for _ in range(2)]
dy=[[0]*16001 for _ in range(2)]

dx[0][i+8000]=1
dy[0][8000]=1

lstx=[]
lsty=[]
d='x'
cnt=0

while i<n:
    if s[i]=='F':
        cnt+=1
    else:
        if cnt>0:
            if d=='x':
                lstx.append(cnt)
            else:
                lsty.append(cnt)
        
        if d=='x':
            d='y'
        else:
            d='x'
        cnt=0
    
    i+=1

for i,cx in enumerate(lstx):
    for j in range(16001):
        if dx[i%2][j]==0:
            continue
        if j+cx<16001:
            dx[(i+1)%2][j+cx]=1
        if j-cx>-1:
            dx[(i+1)%2][j-cx]=1
    dx[i%2]=[0]*16001

for i,cy in enumerate(lsty):
    for j in range(16001):
        if dy[i%2][j]==0:
            continue
        if j+cy<16001:
            dy[(i+1)%2][j+cy]=1
        if j-cy>-1:
            dy[(i+1)%2][j-cy]=1
    dy[i%2]=[0]*16001

if dx[(len(lstx))%2][x]==1 and dy[(len(lsty))%2][y]==1:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from collections import Counter 
n=int(input())
a=list(map(int,input().split()))
a=Counter(a)
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  if a[c]:
    a[c]+=a[b]
  else:a[c]=a[b]
  a[b]=0
  print(sum(sorted(a.elements())))
  

### FIXED CODE ###

from collections import Counter 
n=int(input())
a=list(map(int,input().split()))
sm=sum(a)
a=Counter(a)
q=int(input())
for _ in range(q):
  b,c=map(int,input().split())
  i=a[b]
  if a[c]:
    a[c]+=i
  else:a[c]=i
  sm+=(c-b)*i
  print(sm)
  a[b]=0
### BUGGY CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = tuple(map(int, input().split()))
table = [[0] * (S + 1) for _ in range(N + 1)]
table[0][0] = 1
for n in range(N):
    for s in range(S + 1):
        now = table[n][s]
        table[n + 1][s] = (table[n + 1][s] + now * 2) % MOD
        if s + A[n] <= S:
            table[n + 1][s + A[n]] = (table[n + 1][s + A[n]] + now) % MOD
print(table[N][S])

### FIXED CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = tuple(map(int, input().split()))
table = [[0] * (S + 1) for _ in range(N + 1)]
table[0][0] = 1
for n in range(N):
    for s in range(S + 1):
        now = table[n][s]
        table[n + 1][s] = (table[n + 1][s] + now * 2) % MOD
        if s + A[n] <= S:
            table[n + 1][s + A[n]] = (table[n + 1][s + A[n]] + now) % MOD
print(table[N][S])
### BUGGY CODE ###

def dec(X, d):
    X[1] -= d
    return X


N = int(input())
task = [list(map(int, input().split())) for _ in range(N)]

task.sort(key=lambda x: x[1])

while task:
    if task[0][1] - task[0][0] < 0:
        print("No")
        exit()
    task = list(map(lambda x: dec(x, task[0][0]), task[1:]))

print("Yes")


### FIXED CODE ###

def dec(X, d):
    X[1] -= d
    return X


N = int(input())
task = [list(map(int, input().split())) for _ in range(N)]

task.sort(key=lambda x: x[1])
time = 0
for i in range(N):
    time += task[i][0]
    if time > task[i][1]:
        print("No")
        exit()

print("Yes")
### BUGGY CODE ###

import collections

def factor(m):
  q = m
  r = []
  i = 2
  while q != 1:
    if q % i:
      i += 1
    else:
      r.append(i)
      q //= i
  return r

n, m = map(int, input().split())
p = 10 ** 9 + 7

r = factor(m)
v = collections.Counter(r)
c = 1
for value in v.values():
  temp = 1
  for i in range(value):
    temp *= value + n - 1 - i
  for i in range(value):
    temp //= i + 1
  temp %= p
  c = c * temp % p
print(c)
  
  
  

### FIXED CODE ###

import collections

def factor(m):
  q = m
  r = []
  i = 2
  while i * i <= m:
    if q % i:
      i += 1
    else:
      r.append(i)
      q //= i
  if q != 1:
    r.append(q)
  return r

n, m = map(int, input().split())
p = 10 ** 9 + 7

r = factor(m)
v = collections.Counter(r)
c = 1
for value in v.values():
  temp = 1
  for i in range(value):
    temp *= value + n - 1 - i
  for i in range(value):
    temp //= i + 1
  temp %= p
  c = c * temp % p
print(c)
### BUGGY CODE ###

import math
def main():
    A,B,N = map(int, input().split())

    max1 = 0
    k = math.ceil(B/A)
    for x in range(k,N+1):
        tmp = int(A*x/B) - A*int(x/B)
        max1 = max(max1,tmp)
    print(max1)

main()


### FIXED CODE ###

def main():
    A,B,N = map(int, input().split())

    x = min(B-1,N)
    max1 = int(A*x/B) - A*int(x/B)
    print(max1)

main()
### BUGGY CODE ###

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

a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % (10**9 +7)
    val[0] = val[1]
    val[1] = ans
    if i in a:
        val[1] = 0


print(ans)

### FIXED CODE ###

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

a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = val[-2] + val[-1]
    val.append(ans)
    if len(a) > 0:
        if i == a[0]:
            val[-1] = 0
            a.pop(0)

print(ans % (10**9 +7))
### BUGGY CODE ###

"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
と思ったけど、普通に最小公倍数を求めると、値が大きくなりすぎて処理できない。
なので、積は求めずに、素因数の足し引きだけ処理する。
"""
from math import gcd
from collections import Counter
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
factors = []
for i in range(N):
    a = A[i]
    tmp = []
    ceil = int(a**0.5)+1
    for d in range(2,ceil):
        for _ in range(100):
            if a%d==0:
                a//=d
                tmp.append(d)
            else:
                break
    if a != 1:
        tmp.append(a)
    factors.append(Counter(tmp))
    if i == 0:
        l = Counter(tmp)

for i in range(1,N):
    diff = factors[i]-l
    l += diff

ans = 0
for factor in factors:
    diff = l - factor
    tmp = 1
    for k,v in diff.items():
        tmp *= pow(k,v,mod)
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans)

### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()
### BUGGY CODE ###

from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        if i == j:
            continue
        ans += bisect_left(l, l[i] + l[j], lo=j + 1) - j - 1
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        if i == j:
            continue
        ans += bisect_left(l, l[i] + l[j], lo=j + 1) - j - 1
print(ans)
### BUGGY CODE ###

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

ans = 0

for i in range(N):
    for j in range(N):
        if j == i:
            continue
        if A[i] % A[j] == 0:
            break
    else:
        ans += 1

print(ans)

### FIXED CODE ###

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

dp = [True]*(A[-1]+1)

ans = 0

for i in range(len(A)):
    if dp[A[i]]:
        if (i == len(A)-1) or (A[i] != A[i+1]):
            ans += 1
    try:
        k = 1
        while(True):
            dp[k*A[i]] = False
            k += 1
    except:
        pass

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

y=int(input())
b=[[i,j,k]  for i in range(1,y+1) for j in range(1,y+1) for k in range(1,y+1) ]
c=[]
for l in range(y**3):
    import math
    a = b[l]
    if a[0]==1 or a[1]==1 or a[2]==1:
        c.append(1)
    elif a[0]==a[1]==a[2]:
        c.append(a[0])    
    else:    
        ans1 = math.gcd(a[0], a[1])
        ans2 =math.gcd(ans1,a[2])
        c.append(ans2)
print(sum(c))  

### FIXED CODE ###

import math
y=int(input())
cnt=0
for i in range (1,y+1):
    for k in range(1,y+1):
        for j in range(1,y+1):
            a = [i,j,k]#リスト
            ans = a[0]
            for x in range(len(a)):
                ans = math.gcd(ans, a[x])
            cnt+=ans
print(cnt)
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    div = pow(10, 9) + 7

    # print(A)
    d = dict()
    for i in range(N+1):
        if A[i] not in d: d[A[i]] = [i]
        else: d[A[i]].append(i)

    i1, i2 = 0, 0
    for a in d:
        if len(d[a]) == 2:
            i1, i2 = d[a]
            break
    M = i1 + N-i2
    # print(N, i1, i2)

    # N+1_C_l
    pow1 = [1, 1]
    for i in range(2, N+2):
        pow1.append(pow1[-1]*i % div)
    pow2 = [1, 1]
    for i in range(2, N+2):
        j = powquick(i, div-2, div)
        # print((i * j) % div)
        pow2.append(pow2[-1]*j % div)

    # print(pow1)
    # print(pow2)
    for l in range(1, N+2):
        v = (pow1[N+1]*pow2[l]*pow2[N+1-l]) % div
        # print(v)
        if l <= M+1:
            v -= (pow1[M]*pow2[l-1]*pow2[M-l+1]) % div
        print(v % div)

def powquick(x, y, div):
        if y == 0: return 1
        if y == 1: return x % div
        if y % 2 == 0: return pow(powquick(x, y // 2, div), 2) % div
        if y % 2 == 1: return pow(powquick(x, y// 2, div), 2) * x % div


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    div = pow(10, 9) + 7

    # print(A)
    d = dict()
    for i in range(N+1):
        if A[i] not in d: d[A[i]] = [i]
        else: d[A[i]].append(i)

    i1, i2 = 0, 0
    for a in d:
        if len(d[a]) == 2:
            i1, i2 = d[a]
            break
    M = i1 + N-i2
    # print(N, i1, i2)

    # N+1_C_l
    pow1 = [1, 1]
    for i in range(2, N+2):
        pow1.append(pow1[-1]*i % div)

    # pow2 = [1, 1]
    # for i in range(2, N+2):
    #     j = powquick(i, div-2, div)
    #     pow2.append(pow2[-1]*j % div)

    pow2 = [1, 1]
    inv = [0, 1]
    for i in range(2, N+2):
        inv.append((-inv[div % i]) *(div // i) % div)
        pow2.append(pow2[-1] * inv[-1] % div)

    for l in range(1, N+2):
        v = (pow1[N+1]*pow2[l]*pow2[N+1-l]) % div
        # print(v)
        if l <= M+1:
            v -= (pow1[M]*pow2[l-1]*pow2[M-l+1]) % div
        print(v % div)

def powquick(x, y, div):
        if y == 0: return 1
        if y == 1: return x % div
        if y % 2 == 0: return pow(powquick(x, y // 2, div), 2) % div
        if y % 2 == 1: return pow(powquick(x, y// 2, div), 2) * x % div


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

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

st=False#順方向

for _ in range(Q):
    query=input()
    if len(query)==1:
        st= not st
    else:
        _,F,C=query.split()
        F=int(F)
        if st==False:
            if F==1:
                S=C+S
            else:
                S=S+C
        else:
            if F==1:
                S=S+C
            else:
                S=C+S

if st==False:
    ans=S
else:
    ans=S[::-1]
print(ans)
        
    

### FIXED CODE ###

from collections import deque

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

st=False#順方向

for _ in range(Q):
    query=input()
    if len(query)==1:
        st= not st
    else:
        _,F,C=query.split()
        F=int(F)
        if st==False:
            if F==1:
                S.appendleft(C)
            else:
                S.append(C)
        else:
            if F==1:
                S.append(C)
            else:
                S.appendleft(C)

if st==False:
    ans=S
else:
    ans=reversed(S)

ans="".join(list(ans))
print(ans)
### BUGGY CODE ###

from numpy import ceil,array,sum

def is_ok(m):

    tmp = h - m*B

    if not any(tmp):
        return True

    rem = 0
    for i in tmp[tmp>0]:
        rem += ceil(i/(A-B))

    if rem > m:
        return False

    return True

N,A,B = map(int,input().split())
h = array(list(int(input()) for _ in range(N)))
s = sum(sum(h))
##二分散策

r = 10**10
l = 0

while abs(l-r) > 1:

    m = (r+l)//2

    if is_ok(m):
        r = m
    else:
        l = m

print(r)

### FIXED CODE ###

import sys
from math import ceil

def input():
    return sys.stdin.readline().strip()

def check(k):
    tmp = list(h)
    for i in range(N):
        tmp[i] -= B*k
    if sum([int(i<=0) for i in tmp]) == N:
        return True

    lf = 0
    for i in tmp:
        if i > 0:
            lf += ceil(i/(A-B))

    if lf <= k:
        return True
    else:
        return False

N,A,B = map(int,input().split())
h = tuple(int(input()) for _ in range(N))

left = -1
right = 1e9

while abs(left-right) > 1:

    mid = (left+right)//2
    if check(mid):
        right = mid
    else:
        left = mid

print(int(right))
### BUGGY CODE ###

import numpy as np
n=int(input())
s=list(input())
t=np.zeros((26,n+1))
for i in range(n):
    t[ord(s[i])-97][i+1]+=1
t=np.cumsum(t,axis=1)
for i in range(int(input())):
    a,b,c=map(str,input().split())
    if a=="1":
        if s[int(b)-1]!=c:
            t[ord(s[int(b)-1])-97][int(b):]-=1
            t[ord(c)-97][int(b):]+=1
            s[int(b)-1]=c
    else:
        d=0
        b,c=int(b),int(c)
        for j in range(26):
            if t[j][c]!=t[j][b-1]:
                d+=1
        print(d)

### FIXED CODE ###

import bisect
n=int(input())
s=list(input())
a={chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(a[c],i+1)
for i in range(int(input())):
    p,q,r=list(map(str,input().split()))
    if p=="1":
        q=int(q)
        b=s[q-1]
        if b!=r:
            a[b].pop(bisect.bisect_left(a[b],q))
            bisect.insort(a[r],q)
            s[q-1]=r
    else:
        d=0
        for l in a.values():
            g=bisect.bisect_left(l,int(q))
            if g<len(l) and l[g]<=int(r):
                d+=1
        print(d)