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

import math
from bisect import bisect_left

MOD = 10**9 + 7


def main():
    N, K = map(int, input().split())
    R = int(math.sqrt(N))
    if N // R == R:
        M = R * 2 - 1
    else:
        M = R * 2
    mapping = [0] * (M+1)
    for i in range(1, R+1):
        mapping[i] = i
        mapping[-i] = N//i
    cnt = [0] * (M+1)
    for i in range(1, M+1):
        cnt[i] = mapping[i] - mapping[i-1]
    dp = [[0] * (M+1) for _ in range(K+1)]
    dp[0] = list(cnt)
    for i in range(M):
        dp[0][i+1] += dp[0][i]

    for i in range(K-1):
        for j in range(1, M+1):
            v = N // mapping[j]
            idx = bisect_left(mapping, v)
            dp[i+1][j] = dp[i][idx]
        for j in range(M):
            dp[i+1][j+1] = (dp[i+1][j] + dp[i+1][j+1] * cnt[j+1]) % MOD
    print(dp[K-1][M])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math

MOD = 10**9 + 7


def main():
    N, K = map(int, input().split())
    R = int(math.sqrt(N))
    if N // R == R:
        M = R * 2 - 1
    else:
        M = R * 2
    mapping = [0] * (M+1)
    for i in range(1, R+1):
        mapping[i] = i
        mapping[-i] = N//i
    cnt = [0] * (M+1)
    for i in range(1, M+1):
        cnt[i] = mapping[i] - mapping[i-1]
    dp = [[0] * (M+1) for _ in range(K+1)]
    dp[0] = list(cnt)
    for i in range(M):
        dp[0][i+1] += dp[0][i]

    for i in range(K-1):
        for j in range(1, M+1):
            if j <= R:
                idx = -j
            else:
                idx = M - j + 1
            dp[i+1][j] = dp[i][idx]
        for j in range(M):
            dp[i+1][j+1] = (dp[i+1][j] + dp[i+1][j+1] * cnt[j+1]) % MOD
    print(dp[K-1][M])


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

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

# s = 'ACACTACG'
# lr = [
#     [3, 7],
#     [2, 3],
#     [1, 8],
# ]

wa = []
for index, val in enumerate(s):
    if "AC" == s[index - 1:index + 1]:
        wa.append(1)
    else:
        wa.append(0)

for row in lr:
    start = row[0]
    end = row[1]

    sss = sum(wa[start:end])
    print(sss)


### FIXED CODE ###

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

# s = 'ACACTACG'
# lr = [
#     [3, 7],
#     [2, 3],
#     [1, 8],
# ]

wa = [0]

for index in range(1, len(s)):

    if s[index - 1] == 'A' and s[index] == 'C':
        wa.append(wa[index - 1] + 1)
    else:
        wa.append(wa[index - 1])

for row in lr:
    start = row[0] - 1
    end = row[1] - 1

    diff = wa[end] - wa[start]
    print(diff)
### BUGGY CODE ###

s = list(input())
n = len(s)
c = 0
while True:
  k = 0
  can = False
  for i in range(n-1):
    if k < n-1:
      if s[k] == "B" and s[k+1] == "W":
        s[k] = "W"
        s[k+1] = "B"
        can = True
        c += 1
        k += 2
      else:
        k += 1
  if not can:
    print(c)
    break

### FIXED CODE ###

s = list(input())
n = len(s)
i = []
for j in range(n):
  if s[j] == "W":
    i.append(j)
c = 0
for k in range(len(i)):
  c += i[k]-k
print(c)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
B = [0]*N

S = K - Q
for i in range(N):
    B[i] += S + A.count(i+1)

#for i in range(N):
    if B[i] > 0:
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
B = [K-Q]*N

for i in range(Q):
    B[A[i]-1] += 1
    
for i in range(N):
#if A.count(i+1) > S :
#      B[i] += S + A.count(i+1)

    if B[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N = int(input())
A = input().split()
for i in range(N):
  count = 0
  for j in range(N-1):
    aj = int(A[j])
    if i+1 == aj:
      count += 1
  print(count)


### FIXED CODE ###

N = int(input())
A =[int(n) for n in input().split()]
b = [0]*N
for i in A:
  b[i-1]+=1
for i in range(N):
  print(b[i])
### BUGGY CODE ###

import bisect

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

total = 0
for i in range(n-1):
    for j in range(i+1, n):
        l2 = l[j+1:]
        total += bisect.bisect_left(l2, l[j]+l[i]) - bisect.bisect_right(l2, l[j]-l[i])
print(total)

### FIXED CODE ###

import bisect

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

total = 0
for i in range(n-1):
    for j in range(i+1, n):
        l2 = l[j+1:]
        total += bisect.bisect_left(l2, l[j]+l[i])
print(total)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

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

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    n,q = map(int, input().split())
    s = input()
    l = [0]*(n+1)
    for i in range(n):
        if s[i:i+2]=='AC':
            l[i+1]=l[i] + 1
        else:
            l[i+1]=l[i]

    for _ in range(q):
        a, b = map(int, input().split())
        print(l[b-1]-l[a-1])


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

import bisect
import math
n = int(input())
a = sorted(map(int, input().split()))

ai = a[-1]
half_ai = ai // 2

i_left = bisect.bisect_left(a, half_ai)
i_right = bisect.bisect_right(a, half_ai)
if (a[i_left] == half_ai):
    print(ai, half_ai)
    exit()

le = (math.factorial(ai) // math.factorial(ai -
                                           a[i_left - 1])) // math.factorial(a[i_left - 1])
ri = (math.factorial(ai) // math.factorial(ai - \
      a[i_right])) // math.factorial(a[i_right])

if (le >= ri):
    print(ai, a[i_left - 1])
else:
    print(ai, a[i_right])


### FIXED CODE ###

import bisect
n = int(input())
a = sorted(map(int, input().split()))

ai = a[-1]
half_ai = ai // 2

i_left = bisect.bisect_left(a, half_ai)
i_right = bisect.bisect_right(a, half_ai)
if (a[i_left] == half_ai):
    print(ai, half_ai)
    exit()

if (i_left == i_right and i_left == 0):
    print(ai, a[0])
    exit()

if (abs(half_ai - a[i_left - 1]) >=
        abs(half_ai - a[i_right]) and i_right != len(a) - 1):
    print(ai, a[i_right])
else:
    print(ai, a[i_left - 1])
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(2*k+1)
for i in range(k+1):
    for j in a:dp[i+j]|=~dp[i]
if dp[k]:
    print('First')
else:
    print('Second')

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[False]*(2*k+1)
for i in range(k+1):
    for j in a:dp[i+j]|=not dp[i]
if dp[k]:
    print('First')
else:
    print('Second')
### BUGGY CODE ###

import sys
import math

n,q = map(int, input().split())
s = input()
l = [0] * q
r = [0] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())

for j in range(q):
    print( s[l[j] - 1:r[j]].count('AC'))


### FIXED CODE ###

import sys
import math

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

left = [0] * n

for i in range(n):
    if i:
        if s[i-1:i+1] == 'AC':
            left[i] = left[i - 1] + 1
        else:
            left[i] = left[i - 1] 
for i in range(q):
    l, r = map(int, input().split())
    print(left[r - 1] - left[l - 1])
### BUGGY CODE ###

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

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

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

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(60):
    if bit[i] != 0 and bit[i] != N:
        ans += (2**i)*bit[i]*(N-bit[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 ###

from collections import deque
import copy

def bfs():
  H, W = list(map(int, input().split()))
  field = [[i=='#' for i in input()] for _ in range(H)]
  count = 0
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while q:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0<=ny<H and 0<=nx<W and not field[ny][nx]:
          field[ny][nx] = True
          nq.append((ny, nx))
    if nq:
      q = copy.copy(nq)
    else:
      break
    count += 1
  print(count)
      
bfs()

### FIXED CODE ###

from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

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

N,K = (int(i) for i in input().split())

ans=0

MAX = int(2*N/K+1)

for alpha in range(1,MAX):
    for beta in range(1,MAX):
        for gamma in range(1,MAX):
            a = K*(alpha-beta+gamma)
            b = K*(alpha+beta-gamma)
            c = K*(-alpha+beta+gamma)
            if(all([a>0,b>0,c>0]) and
            all([a<=N*2,b<=N*2,c<=N*2]) and
            all([a%2==0,b%2==0,c%2==0])
            ):
                ans+=1

print(ans)

### FIXED CODE ###

N,K = (int(i) for i in input().split())

if K%2==1:
    print((N//K)**3)
else:
    print((N//K)**3+((N-K//2)//K+1)**3)
### BUGGY CODE ###

N, M = map(int, input().split())
F = [list(map(int, (input().split()))) for i in range(M)]
tmp = [[] for i in range(N)]

for i in range(M):
    tmp[F[i][0]-1].append(F[i][1])

for i in range(N):
    tmp[i].sort()
    
for i in range(M):
    X = tmp[F[i][0]-1].index(F[i][1])+1
    print(('0'*(6-len(str(F[i][0]))) + str(F[i][0])) + '0'*(6-len(str(X))) + str(X))

### FIXED CODE ###

N, M = map(int, input().split())
#tmp = [[] for i in range(N)]
tmp = []
res = ['' for i in range(M)]
count = [1 for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    tmp.append([A,B,i])

tmp.sort(key=lambda tmp: tmp[1])

for i in range(M):
    res[tmp[i][2]] += '0'*(6-len(str(tmp[i][0]))) + str(tmp[i][0]) + '0'*(6-len(str(count[tmp[i][0]]))) + str(count[tmp[i][0]])
    count[tmp[i][0]] += 1

for i in range(M):
    print(res[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a_ = sorted(a)
if len(a)==2:
    print(a_[1],a_[0])
    exit()
a = a_[::-1]
import bisect
import math
def combinations_count(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
ret = 0
for i in range(n//2):
    k = bisect.bisect_left(a_,a[i]//2)
    if a[i]//2-a_[k]>a_[k+1]-a[i]//2:
        k += 1
    cmb = combinations_count(a[i],a_[k])
    if ret<cmb:
        ans = [a[i],a_[k]]
        ret = cmb
print(ans[0],ans[1])


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a_ = sorted(a)
if len(a)==2:
    print(a_[1],a_[0])
    exit()
a = a_[::-1]
k = 10**9
for i in range(1,n):
    if k>abs(a[0]/2-a[i]):
        k=abs(a[0]/2-a[i])
        ans = [a[0],a[i]]
print(ans[0],ans[1])
### BUGGY CODE ###

N, K = [int(x) for x in input().strip().split(" ")]
hs = [int(x) for x in input().strip().split(" ")]
d = [0] * N

for i in range(N-1):
    i = i+1
    tmp = pow(10, 18)
    for j in range(K):
        j = j + 1
        if i-j < 0:
            continue
        tmp = min(tmp, d[i-j] + abs(hs[i-j] - hs[i]))
    d[i] = tmp
print(d[-1])


### FIXED CODE ###

N, K = [int(x) for x in input().strip().split(" ")]
hs = [int(x) for x in input().strip().split(" ")]
d = [0] * N

for i in range(N-1):
    i = i+1
    tmp = pow(10, 18)
    for j in range(K):
        j = j + 1
        if i-j < 0:
            continue
        tmp = min(tmp, d[i-j] + abs(hs[i-j] - hs[i]))
    d[i] = tmp
print(d[-1])
### BUGGY CODE ###

n = int(input())
s = input()

Q = int(input())

for i in range(Q):
  order = list(map(str, input().split()))

  if int(order[0]) == 1:
    iq, cq = int(order[1])-1, order[2]
    s = s[:iq] + cq + s[iq+1:]
  else:
    lq, rq = int(order[1])-1, int(order[2])-1
    substr = s[lq:rq+1]
    print(len(set(substr)))

### FIXED CODE ###

class BIT:
  def __init__(self,n):
    self.s = [0]*(n+1)
    self.n = n
  
  def add(self,val,idx):
    while idx < self.n+1:
      self.s[idx] = self.s[idx] + val
      idx += idx&(-idx)
    return
  
  def get(self,idx):
    res = 0
    while idx > 0:
      res = res + self.s[idx]
      idx -= idx&(-idx)
    return res
 
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
n = int(input())
S = [ord(s) - ord('a') for s in input()[:-1]]
 
bits = [BIT(n) for i in range(26)]
 
for i,s in enumerate(S):
  bits[s].add(1,i+1)
 
Q = int(input())
ans = []
for _ in range(Q):  
  flag,x,y = input().split()

  if flag == "1":
    i = int(x)
    c = ord(y) - ord('a')
    bits[S[i-1]].add(-1,i)
    bits[c].add(1,i)
    S[i-1] = c
  else:
    l = int(x)
    r = int(y)
    res = 0
    for i in range(26):
      res += (bits[i].get(r) > bits[i].get(l-1))
    ans.append(str(res))

print("\n".join(ans))
### BUGGY CODE ###

N,A=map(int, input().split())
x=list(map(int, input().split()))
dp=[[[0]*(sum(x)+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(0,N+1):
    for k in range(0, N+1):
        for s in range(0, sum(x)+1):
            if j>=1 and s<x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]
            elif j>=1 and k>=1 and s>=x[j-1]:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            elif j==0 and k==0 and s==0:
                dp[0][0][0]=1
            else:
                dp[j][k][s]=0
ans=0
for k in range(1,N+1):
    if k*A<=sum(x):
        ans+=dp[N][k][k*A]
print(ans)


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

INFTY = 10**12
Q = [1 for _ in range(INFTY)]
Q[0]=0
Q[1]=0
for i in range(2,int(INFTY**0.5)+1):
    for j in range(i*i,INFTY,i):
        Q[j]=0
A = []
for i in range(INFTY):
    if Q[i]==1:
        A.append(i)
N,P = map(int,input().split())
C = {}
for a in A:
    if P%a==0:
        C[a] = 0
        while P%a==0:
            P = P//a
            C[a] += 1
b = 1
for a in C:
    b *= a**(C[a]//N)
print(b)

### FIXED CODE ###

INFTY = 10**6
Q = [1 for _ in range(INFTY)]
Q[0]=0
Q[1]=0
for i in range(2,int(INFTY**0.5)+1):
    for j in range(i*i,INFTY,i):
        Q[j]=0
A = []
for i in range(INFTY):
    if Q[i]==1:
        A.append(i)
N,P = map(int,input().split())
C = {}
for a in A:
    if P%a==0:
        C[a] = 0
        while P%a==0:
            P = P//a
            C[a] += 1
if P>1:
    C[P] = 1
b = 1
for a in C:
    b *= a**(C[a]//N)
print(b)
### BUGGY CODE ###

import collections


def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(m):
        b, c = map(int, input().split())
        A = sorted(A + [c] * b, reverse=True)[0:n]
    print(sum(A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections


def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    bc = [list(map(int, input().split())) for _ in range(m)]
    A.sort()
    bc.sort(key=lambda x: x[1], reverse=True)
    i, j = 0, 0

    while i < n and j < m:
        if A[i] >= bc[j][1]:
            break
        A[i] = bc[j][1]
        i += 1
        bc[j][0] -= 1
        if bc[j][0] == 0:
            j += 1
    print(sum(A))


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

import sys
from collections import defaultdict
n, m = map(int, sys.stdin.readline().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dic = defaultdict(list)
for ele in a_b:
    dic[ele[0]].append(ele[1])

L =[]
money = 0
for d in range(1, m+1):
    if dic[d]:
        L+= dic[d]
    if L:
        L.sort()
        money += L[-1]
        L.pop()
print(money)

### FIXED CODE ###

import sys
from collections import defaultdict
import heapq
input = sys.stdin.readline
n, limit = map(int, input().split())
dic = defaultdict(list)

for _ in range(n):
    a, b = map(int, input().split())
    dic[a].append(b)

L = []
ans = 0
for i in range(limit+1):
    for val in dic[i]:
        heapq.heappush(L, -val)
    if len(L):
        ans -= heapq.heappop(L)
print(ans)
### BUGGY CODE ###

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

csum = [0]
rcsum = [0]
for i in range(n):
    csum.append(s[i:n].count('AC'))
    #rcsum.append(s[n-i:n].count('AC'))


# print(csum)
# print(rcsum)

for _ in range(q):
    l, r = map(int, input().split())
    print(csum[l]-csum[r])
    #print('回答：', csum[l], rcsum[n-r])


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i-1:i+1] == "AC" else 0)

lr = []
for i in range(Q):
    tmp_lr = list(map(int, input().split()))
    lr.append(tmp_lr)

for l, r in lr:
    print(t[r]-t[l])
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
count = 0
a_li = []
b_li = []
for i,l in enumerate(li):
    a_li.append([i+1,l])
    b_li.append([l,i+1])
for a in a_li:
    if a in b_li:
        count += 1
print(count//2)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
count = 0
#print(li)
for i,l in enumerate(li):
    #print(i,l-1,li[l-1])
    if li[l-1] == i+1:
        count+= 1
print(count//2)
### BUGGY CODE ###

#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""
import sys
import itertools

__author__ = 'bugttle <bugttle@gmail.com>'


def main():
    [N, M, X] = list(map(int, input().split()))

    l = []
    for n in range(N):
        l.append(list(map(int, input().split())))
    # print(l)

    min_cost = sys.maxsize
    for p in itertools.permutations(range(N)):
        # print(p)
        cost = 0
        status = [0]*M
        for n in p:
            cost += l[n][0]
            isCompleted = True
            for m in range(M):
                status[m] += l[n][m + 1]
                if status[m] < X:
                    isCompleted = False
            # print(status)
            if isCompleted:
                # print('fin')
                # print(cost)
                if cost < min_cost:
                    min_cost = cost
                break
    if min_cost == sys.maxsize:
        print(-1)
    else:
        print(min_cost)
            
                    

                # status[m] += l[n][m]
    # for n in range(N):
    #     for m in range(M):
    #         print([n, m])
    # cost = 0
    # status = [[0]*M]*N
    # for n in range(N):
    #     for m in range(M):
    #         print(l[n][m + 1])
    #         # status[n][m] = l[n][m + 1]
    # print(status)

    


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
"""AtCoder Beginner Contest 167: C - Skill Up
https://atcoder.jp/contests/abc167/tasks/abc167_c
"""

N, M, X = 0, 0, 0
BOOKS = []


def calc_price(book_combinations):
    price = 0
    understandings = [0] * M
    for i in range(len(book_combinations)):
        if book_combinations[i]:
            price += BOOKS[i][0]
            for j in range(len(BOOKS[i][1:])):
                understandings[j] += BOOKS[i][j + 1]
    for u in understandings:
        if u < X:  # couldn't understand
            return -1
    return price


def main():
    global N, M, X, BOOKS
    N, M, X = list(map(int, input().split()))
    BOOKS = [list(map(int, input().split())) for i in range(N)]

    ans = float('inf')
    for i in range(1, 2 ** N):  # => 1: at least one book should be buy
        price = calc_price([(i >> j) & 1 for j in range(N)])
        if 0 < price and price < ans:
            ans = price
    if ans == float('inf'):
        ans = -1
    print(ans)


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

import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def S(): return input().rstrip()
def LIR(n): return [S().split() for i in range(n)]

def main():
    s = S()
    Q = I()
    Qu = LIR(Q)
    for que in Qu:
        if que[0] == '1':

            s = s[::-1]
        else:
            if que[1] == '1':
                s = que[2]+s
            else:
                s = s+que[2]
    print(s)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def S(): return input().rstrip()
def LIR(n): return [S().split() for i in range(n)]

def main():
    s = S(); Q = I()
    mode = 2
    d = deque(s)

    for i in range(Q):
        query = S()
        if query[0] == "1": mode = 3 - mode
        else:
            t, f, c = map(str, query.split())
            if (int(f) + mode)% 2  == 0: d.append(c)
            else: d.appendleft(c)
    if mode == 2: print(''.join(d))
    else: print(''.join(list(d)[::-1]))

if __name__ == '__main__':
    main()