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

S= input()
q=int(input())
h=0
for i in range(q):
    a=input()


    if a[0]=="1":
        h+=1
    else:
        if h%2==0:
            if a[2] == "1":
                S=a[4]+S
            else:
                S=S+a[4]
        else:
            if a[2] == "2":
                S=a[4]+S
            else:
                S=S+a[4]

if h%2==0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

S= input()
q=int(input())
h=0
a=[]
for i in range(q):
    a.append(input())
t=""
w=""
for i in range(1,q+1):
    if a[q-i][0]=="2":
        if a[q - i][2] == "1":
            if h%2==0:
                t=t+a[q-i][4]
            else:
                w =  w+a[q - i][4]
        else:
            if h%2==0:
                w=w+a[q-i][4]
            else:
                t = t + a[q - i][4]
    else:
        h+=1
if h%2==0:
    print(t+S+w[::-1])
else:
    print(t+S[::-1]+w[::-1])
### BUGGY CODE ###

from collections import defaultdict,deque
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((r*10**15+l*10**8+i))
queries.sort()
curR = 0
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return
for j in range(Q):
    SUM = queries[j]
    r = SUM // 10**15
    SUM %= 10**15
    l = SUM // 10**8
    SUM %= 10**8
    i =SUM
    while curR < r:
        curR += 1
        if lastAppeared[c[curR]] != -1:
            last = lastAppeared[c[curR]]
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])


### FIXED CODE ###

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

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()

    ans = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if S[i] == S[j]:
                continue

            for k in range(j + 1, N):
                if S[j] != S[k] and S[k] != S[i] and j - i != k - j:
                    ans += 1

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main4():
    N = int(input())
    S = input()

    R = set()
    G = set()
    B = set()

    for i in range(len(S)):
        if   S[i] == "R":
            R.add(i)
        elif S[i] == "G":
            G.add(i)
        elif S[i] == "B":
            B.add(i)

    ans = 0
    for r in R:
        for g in G:
            a, b = sorted([r, g])
            tmp = len(B)

            if ((b + a) % 2 == 0) and ((b + a) // 2) in B:
                tmp -= 1

            if (2*a - b) in B:
                tmp -= 1

            if (2*b - a) in B:
                tmp -= 1

            ans += tmp
                
    print(ans)

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

s = input()
q = int(input())



for i in range(q):
    inp = input().split()
    if inp[0] == "1":
        s = s[::-1]
    elif inp[1] == "1":
        s = inp[2] + s
    else:
        s = s + inp[2]


print(s)



### FIXED CODE ###

from collections import deque

#inp = list(map(lambda x: int(x), input().split()))
#n,k = map(lambda x: int(x), input().split())
#p_n = list(map(lambda x:int(x),input().split()))


s = deque(input())
q = int(input())


cnt = 0
for i in range(q):
    inp = input().split()
    if inp[0] == "1":
        cnt += 1
    else:
        if inp[1] == "1":
            if cnt % 2 == 0:
                s.appendleft(inp[2])
            else:
                s.append(inp[2])
        else:
            if cnt % 2 == 0:
                s.append(inp[2])
            else:
                s.appendleft(inp[2])

ans = list(s)

if cnt % 2 == 1:
    ans = ans[::-1]

print(''.join(ans))
### BUGGY CODE ###

h,w,d=map(int,input().split())
a=[]
box=[[] for i in range(h*w+1)]
wi=0
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        box[ai[j]]=[i,j]

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    ansi=0
    for j in range(l,r,d):
        ansi+=abs(box[j][0]-box[j+d][0])+abs(box[j][1]-box[j+d][1])
    print(ansi)


### FIXED CODE ###

h,w,d=map(int,input().split())
a=[]
box=[[] for i in range(h*w+1)]
wi=0
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        box[ai[j]]=[i,j]

p=[0]
for i in range(1,h*w+1):
    if(i-d>0):
        p.append(p[i-d]+abs(box[i][0]-box[i-d][0])+abs(box[i][1]-box[i-d][1]))
    else:
        p.append(0)

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(p[r]-p[l])
### BUGGY CODE ###

n = int(input())
S = input()
min = 3 * 10 ** 15
for i in range(n):
    tmp = S[0:i].count("W") + S[i+1:n].count("E")
    if min > tmp:
        min = tmp
print(min)


### FIXED CODE ###

n = int(input())
S = input()
W = 0
E = 0
T = [0 for i in range(n)]  
for i in range(n-1):
    if S[i] == "W": W+=1
    if i > 0:
        T[i+1] += W 

for i in range(n-1,0,-1):
    if S[i] == "E": E+=1
    if i < n-1:
        T[i-1] += E
print(min(T))
### BUGGY CODE ###

def maxHeapify(i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < len(A) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < len(A) and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(largest)

def heapInsert(key):
    i = len(A)
    A.append(key)
    parent = (i - 1) // 2
    while i > 0 and A[parent] < A[i]:
        A[i], A[parent] = A[parent], A[i]
        i = parent
        parent = (parent - 1) // 2

def heapMaxPop():
    max_key = A[0]
    if len(A) > 1:
        A[0] = A.pop()
    else:
        del A[0]
    maxHeapify(0)
    print(max_key)


A = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapInsert(k)
    elif x[1] == 'x':
        heapMaxPop()
    else:
        pass

### FIXED CODE ###

def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey
    setHeapDown_max(heap, pos)

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

ans = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        ans.append(heapPop_max(S))
    else:
        pass

print(*ans, sep = '\n')
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = inpl()
l = 0; r = n-1
res = []
while r > l:
    pl = None
    mx = 0
    ind = -1
    for i in range(l,r+1):
        if abs(a[i]) > mx:
            mx = abs(a[i])
            ind = i
            if a[i] > 0:
                pl = True
            else:
                pl = False
    if mx == 0:
        break
    if pl:
        for i in range(ind,r):
            i += 1
            res.append([i,i+1])
            res.append([i,i+1])
        r = ind
    else:
        for i in range(l,ind)[::-1]:
            i += 1
            res.append([i+1,i])
            res.append([i+1,i])
        l = ind
print(len(res))
for x in res:
    print(*x)


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = inpl()
mx = 0
pl = None
ind = -1
res = []
for i,x in enumerate(a):
    if abs(x) > mx:
        mx = abs(x)
        ind = i
        pl = True if x > 0 else False
if mx == 0:
    print(0)
    quit()
if not pl: mx *= -1
for i in range(n):
    if i == ind: continue
    res.append([ind+1,i+1])
    a[i] += mx
if pl:
    for i in range(n-1):
        res.append([i+1,i+2])
else:
    for i in range(n-1)[::-1]:
        res.append([i+2,i+1])
print(len(res))
for x in res:
    print(*x)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
print(len([n for n in A if n == 1]))
for i, num in enumerate(A):
    ORG = A[:]
    ORG.pop(i)
    me = i + 2
    print(ORG.count(me))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
x = [0] * N
for s in A:
    x[s-1] += 1
for s in x:
    print(s)
### BUGGY CODE ###

n = input()
m = input()
wcount = 0
rcount = 0
for i in m:
    if i == "W":
        wcount += 1
    else:
        rcount += 1
new_m = "R"*rcount + "W"*wcount
r_l = []
w_l = []
for i in range(len(m)):
    if m[i] == "W":
        w_l.append(i)
    else:
        r_l.append(i)
m = list(m)
new_m = list(new_m)
count = 0
while m != new_m:
    m[w_l[0]],m[r_l[-1]] = m[r_l[-1]],m[w_l[0]]
    w_l.pop(0)
    r_l.pop(-1)
    count += 1

print(count)

### FIXED CODE ###

n = input()
m = input()
maxr = m.count("R")
maxw = m.count("W")

min_move = len(m)
max_r = m.count("R")
max_w = m.count("W")
right = 0
left = 0
for i in range(len(m)):
    if m[i] == "W":
        left += 1
    else:
        max_r -= 1
    if max(left,max_r) < min_move:
        min_move = max(left,max_r)
if maxw == 0 or maxr == 0:
    print(0)
else:
    print(min_move)
### BUGGY CODE ###

n = int(input())
sl = []
for i in range(n):
    s = list(input())
    s.sort()
    sl.append(s)
sl.sort()
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if sl[i] == sl[j]:
            ans += 1
        else:
            break
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
sl = []
for i in range(n):
    s = list(input())
    s.sort()
    sl.append("".join(s))
d = Counter(sl)

def cul(n):
    return n*(n - 1)//2

ans = 0
val = d.values()
for i in val:
    if i > 1:
        ans += cul(i)
print(ans)
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    # 約数を列挙　n=10^12までいける
    def make_divisors(n, a_set, a_cnt):
        if a_cnt[n] > 1:
            return True

        deleted_set = a_set - {n}
        # divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                # divisors.append(i)
                if i in deleted_set:
                    return True
                if i != n // i:
                    # divisors.append(n // i)
                    if n // i in deleted_set:
                        return True

        # divisors.sort()
        return False

    n = ni()
    a = na()

    a_set = set(a)

    a_cnt = collections.Counter(a)

    ans = 0
    for ai in a_set:
        if not make_divisors(ai, a_set, a_cnt):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)
    lista = list(seta)
    lista.sort()

    table = [True for _ in range(10 ** 6 + 1)]
    ans = 0

    for ai in lista:
        if table[ai]:
            if cnta[ai] == 1:
                ans += 1
            for i in range(ai, 10 ** 6 + 1, ai):
                table[i] = False

    print(ans)


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

import sys
import numpy as np


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n, q = map(int, read().split())
    a = np.array([0] + [int(i) for i in read().split()]).cumsum()
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            a[query[1] + 1:] += query[2]
        else:
            print(a[query[2]] - a[query[1]])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


class FenwickTree:
    def __init__(self, n):
        self._n = n
        self._a = [0] * n

    def add(self, i, x):
        i += 1
        while i <= self._n:
            self._a[i - 1] += x
            i += i & -i

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

    def _sum(self, r):
        s = 0
        while r > 0:
            s += self._a[r - 1]
            r -= r & -r
        return s


def main():
    n, q = map(int, read().split())
    fw = FenwickTree(n)
    for i, ai in enumerate(map(int, read().split())):
        fw.add(i, ai)
    for _ in range(q):
        query = [int(i) for i in read().split()]
        if query[0] == 0:
            fw.add(query[1], query[2])
        else:
            print(fw.sum(query[1], query[2]))


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

#!python3

iim = lambda: map(int, input().rstrip().split())

def mod_add(a, b, mod):
    return (a + b) % mod

def mod_mul(a, b, mod):
    return a * b % mod

def mod_power(x, y, mod):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return mod_power(x, y//2, mod)**2 % mod
    else            : return mod_power(x, y//2, mod)**2 * x % mod

def mod_div(a, b, mod):
    return mod_mul(a, mod_power(b, mod-2, mod), mod)

def factor(n):
    ans = []
    i = 0
    while n & 1 == 0:
        n >>= 1
        i += 1

    if i > 0:
        ans.append((2, i))

    for i in range(3, int(n**.5) +1, 2):
        x, y = divmod(n, i)

        if y == 0:
            j = 1
            x1 = x
            while True:
                x1, y = divmod(x, i)
                if y == 0:
                    x = x1
                    j += 1
                else:
                    ans.append((i, j))
                    break
            n = x

    if n > 1:
        ans.append((n, 1))
    return ans

def resolve():
    N = int(input())
    A = list(iim())
    mod = 10**9 + 7

    c = 1
    c2 = dict()
    for a in A:
        for n, m in factor(a):
            if n in c2:
                c2[n] = max(c2[n], m)
            else:
                c2[n] = m

    c3 = 1
    for n, m in c2.items():
        c3 *= n**m%mod % mod

    s = 0
    for a in A:
        s = mod_add(s, mod_div(c3, a, mod), mod)

    print(s)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

def factor(n):
    ans = []
    i = 0
    while n & 1 == 0:
        n >>= 1
        i += 1

    if i > 0:
        ans.append((2, i))

    for i in range(3, int(n**.5) +1, 2):
        x, y = divmod(n, i)

        if y == 0:
            j = 1
            x1 = x
            while True:
                x1, y = divmod(x, i)
                if y == 0:
                    x = x1
                    j += 1
                else:
                    ans.append((i, j))
                    break
            n = x

    if n > 1:
        ans.append((n, 1))
    return ans

def resolve():
    N = int(input())
    A = list(iim())
    mod = 10**9 + 7

    c = 1
    c2 = dict()
    for a in A:
        for n, m in factor(a):
            if n in c2:
                c2[n] = max(c2[n], m)
            else:
                c2[n] = m

    c3 = 1
    for n, m in c2.items():
        c3 *= n**m%mod % mod

    s = 0
    for a in A:
        s += c3*pow(a, mod-2, mod)%mod
        s %= mod

    print(s)

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

import math

k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1, k+1):
            d = math.gcd(i,j)
            ans += math.gcd(d, l)
            
print(ans)


### FIXED CODE ###

import math

k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1, k+1):
            d = math.gcd(i,j)
            ans += math.gcd(d, l)

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

#!/usr/bin/env python3
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
n,a,b = map(int,input().split())
mod = 10**9 + 7
print((2**n - 1 - cmb(n,a) - cmb(n,b))%mod)

### FIXED CODE ###

#!/usr/bin/env python3
def fac(n,a):
  ans = 1
  for i in range(n,n-a,-1):
    ans *= i
    ans %= mod
  return ans
def cmb(n, a, mod):
    ans = fac(n,a)
    inv = fac(a,a-1)
    return (ans*pow(inv,mod-2,mod)) % mod

n,a,b = map(int,input().split())
mod = 10**9 + 7
#他人のコードパクったけど高速化の理由不明
"""
def pow(n,b,mod):
  if n == 0: return 1
  if n % 2: return 2 * pow(n//2,b,mod)**2 % mod
  else: return pow(n//2,b,mod)**2 % mod"""
print((pow(2,n,mod) - 1 - cmb(n,a,mod) - cmb(n,b,mod))%mod)
### BUGGY CODE ###


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

max_SumA = (M*(M+1))//2
AB.sort(key= lambda x:(-x[1],-x[0]))
memo = [0]*(10**5+1)#請け負うと決めた仕事の数
ans = 0
for a,b in AB:
    for idx in range(M-a,-1,-1):
        if memo[idx] == 0:#仕事が請けられる
            ans += b
            memo[idx]=1
            break
print(ans)
    


### FIXED CODE ###


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

AB.sort(key= lambda x:(-x[1],-x[0]))
memo = [0]*(10**5+1)#請け負うと決めた仕事の日
work = [float('inf')]*(10**5+1)

noMore = float('inf') #これ以上の日数が振り込みにかかる仕事は受けれない
ans = 0
for a,b in AB:
    if a< noMore:
        flag = 1
        for idx in range(min(M-a,work[a]),-1,-1):
            if memo[idx] == 0:#仕事が請けられる
                ans += b
                memo[idx]=1
                flag = 0
                work[a] = idx
                break
        if flag ==1:
            noMore = a
    
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
index_A = [i for i, v in enumerate(S) if v == 'A']

for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    for j in index_A:
        if l-1 <= j <= r-2:
            if S[i + 1] == 'C':
                ans += 1
    print(ans)


### 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 : i + 2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

#https://atcoder.jp/contests/abc051/tasks/abc051_b
K, S = map(int, input().split(' '))

cnt = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                cnt += 1
print(cnt)

### FIXED CODE ###

#https://atcoder.jp/contests/abc051/tasks/abc051_b
K, S = map(int, input().split(' '))
cnt = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - (x + y)
        if 0 <= z <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

h,w,k=map(int,input().split())
S=[input() for i in range(h)]

LIS=[]

def saiki(x,st):
    if x==h-1:
        LIS.append(st)
        return
    else:
        saiki(x+1,st+st[-1])
        saiki(x+1,st+str(int(st[-1])+1))

saiki(0,"0")

DIC1={c:0 for c in "0123456789"}
DIC2={c:0 for c in "0123456789"}
ans=10**9
for cod in LIS:
    for ele in DIC1:
        DIC1[ele]=0
    cnt=int(cod[-1])
    end=False
    for i in range(w):
        for ele in DIC2:
            DIC2[ele]=0
        for q in range(h):
            if S[q][i]=="1":
                DIC2[cod[q]]+=1
        if max(DIC2.values())>k:
            end=True
            break
        flg=True
        for ele in DIC1:
            if DIC1[ele]+DIC2[ele]>k:
                flg=False
                break
        if flg:
            for ele in DIC1:
                DIC1[ele]+=DIC2[ele]
        else:
            for ele in DIC1:
                DIC1[ele]=DIC2[ele]
            cnt+=1
    if end:
        continue
    ans=min(ans,cnt)
    #print(cod,cnt)
print(ans)


### FIXED CODE ###

h,w,k=map(int,input().split())
S=[input() for i in range(h)]

LIS=[]

def saiki(x,st):
    if x==h-1:
        LIS.append(st)
        return
    else:
        saiki(x+1,st+st[-1])
        saiki(x+1,st+str(int(st[-1])+1))

saiki(0,"0")

DIC1={c:0 for c in "0123456789"}
DIC2={c:0 for c in "0123456789"}
ans=10**9
for cod in LIS:
    for ele in DIC1:
        DIC1[ele]=0
    cnt=int(cod[-1])
    end=False
    for i in range(w):
        for ele in DIC2:
            DIC2[ele]=0
        for q in range(h):
            if S[q][i]=="1":
                DIC2[cod[q]]+=1
        if max(DIC2.values())>k:
            end=True
            break
        flg=True
        for ele in DIC1:
            if DIC1[ele]+DIC2[ele]>k:
                flg=False
                break
        if flg:
            for ele in DIC1:
                DIC1[ele]+=DIC2[ele]
        else:
            for ele in DIC1:
                DIC1[ele]=DIC2[ele]
            cnt+=1
    if end:
        continue
    ans=min(ans,cnt)
    #print(cod,cnt)
print(ans)
### BUGGY CODE ###

#E
import heapq
n = int(input())
a = [int(input()) for _ in range(n)]
b = a[:]
heapq.heapify(b)


cnt = 0

while len(a)>0:
    a_l = a.pop(0)
    for i in range(len(a)-1,-1,-1):
        if a[i] > a_l:
            a_r = a.pop(i)
            break
    for j in range(len(a)-1,-1,-1):
        if a_l < a[j] < a_r:
            a_r = a.pop(j)
            
    cnt += 1

print(cnt)

### FIXED CODE ###

#E
from collections import deque
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
result = deque()

for i in a:
    idx = bisect.bisect_left(result,i)
    if idx == 0:
        result.appendleft(i)
        
    else:
        result[idx-1] = i
        
print(len(result))