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

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]

def count(n):
    A = [0]
    c = 0
    i = 1
    while(n):
        if n & 1:
            A.append(i)
            c += 1
        n >>= 1
        i += 1
    A.append(H)
    return c, A


ans = 2000
for n in range(1 << (H-1)):
    c, A = count(n)
    X = [0]*(len(A)-1)
    j = 0
    flag=True
    while j < W:
        for k in range(len(A)-1):
            for i in range(A[k], A[k+1]):
                if S[i][j] == "1":
                    X[k] += 1
        for x in X:
            if x > K:
                if flag:
                    c += 10000
                    break
                flag = True
                c += 1
                X = [0]*(len(A)-1)
                break
        else:
            flag = False
            j += 1
        if c > 10000:
            break
    ans = min(ans, c)
print(ans)


### FIXED CODE ###

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]

def count(n):
    A = [0]
    c = 0
    i = 1
    while(n):
        if n & 1:
            A.append(i)
            c += 1
        n >>= 1
        i += 1
    A.append(H)
    return c, A


ans = 2000
for n in range(1 << (H-1)):
    c, A = count(n)
    X = [0]*(len(A)-1)
    j = 0
    flag=True
    while j < W:
        for k in range(len(A)-1):
            for i in range(A[k], A[k+1]):
                if S[i][j] == "1":
                    X[k] += 1
        for x in X:
            if x > K:
                if flag:
                    c += 10000
                    break
                flag = True
                c += 1
                X = [0]*(len(A)-1)
                break
        else:
            flag = False
            j += 1
        if c > 10000:
            break
    ans = min(ans, c)
print(ans)
### BUGGY CODE ###

print("".join([ [ "{0}\n".format(NQ_S[1][0][LR[0]-1:LR[1]].count('AC')) for LR in [list(map(int, input().split())) for i in range(NQ_S[0][1])] ] for NQ_S in [[[int(x) for x in input().split()],[str(x) for x in input().split()]]] ][0])[:-1])

### FIXED CODE ###

print("".join([ [ [ "{0}\n".format(NQ_S[2][LR[1]-1]-NQ_S[2][LR[0]-1]) for LR in  [list(map(int, input().split())) for i in range(NQ_S[0][1])]] for x in [[NQ_S[2].append(NQ_S[2][i-1]+1) if NQ_S[1][0][i-1]=='A' and NQ_S[1][0][i]=='C' else NQ_S[2].append(NQ_S[2][i-1]) for i in range(1,len(NQ_S[1][0]))]]] for NQ_S in [[[int(x) for x in input().split()],[str(x) for x in input().split()],[0]]] ][0][0])[:-1])
### BUGGY CODE ###

N=int(input())
S=input()
re_list=[]
ele = list(map(str, S))
for i in range(1,len(ele)+1):
    for j in range(i+1,len(ele)+1):
        for k in range(j+1,len(ele)+1):
            re_str=ele[i-1]+ele[j-1]+ele[k-1]
            re_list.append(re_str)
re_list=list(set(re_list))
print(len(re_list))


### FIXED CODE ###

N=int(input())
S=input()
re_list=[]
ele = list(map(str, S))
v_list=[]
vi_list=[]
flag = 0
count = 0
for i in range(1000):
    if i < 10:
        v_list.append("00"+str(i))
    elif i < 100:
        v_list.append("0" + str(i))
    else:
        v_list.append(str(i))

for i in range(1000):
    for j in range(N):
        if ele[j] == v_list[i][0] and flag == 0:
            flag = 1
            continue
        if ele[j] == v_list[i][1] and flag == 1:
            flag = 2
            continue
        if ele[j] == v_list[i][2] and flag == 2:
            count += 1
            break
    flag = 0
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
n = len(p)
ans = 10 ** 9

for i in range(2 ** n):
    total = 0
    cnt = 0
    for j in range(n):
        if((i >> j) & 1):
            total += p[j]
            cnt += 1
    if cnt == K and ans > total:
        ans = total
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
print(sum(p[:K]))
### BUGGY CODE ###

import math

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



### FIXED CODE ###

from math import gcd

k = int(input())
sum = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for m in range(1, k + 1):
            sum += gcd(gcd(i, j), m)
print(sum)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)

dp = [[-1 for i in range(1001)] for j in range(n)]

cnt = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    tgt = l[i] - l[j]
    if dp[j+1][tgt] != -1:
      cnt += dp[j+1][tgt]
    else:
      cptr = ((n-1) + (j+1)) // 2
      fixed = [-1] * n
      while fixed[cptr] == -1:
        if l[cptr] > tgt:
          fixed[cptr] = 0
          cptr = ((n-1) + (cptr+1)) // 2
        else:
          fixed[cptr] = 1
          cptr = ((cptr) + (j+1)) // 2
      inc = cptr - j - fixed[cptr]
      cnt += inc
      dp[j+1][tgt] = inc
#      print('J='+str(j)+', CPTR='+str(cptr)+', CNT='+str(cnt))

print(cnt)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)

lptr = [-1] * 1001
lptr[0] = n - 1
for i in range(1, 1001):
  maxptr = n -1
  minptr = 0
  fixed = [-1] * n
  cptr = (maxptr + minptr + 1) // 2

  while fixed[cptr] == -1:

#    print(str(cptr)+','+str(l[cptr]))
    if l[cptr] > i:
      fixed[cptr] = 0
      minptr = cptr
    else:
      fixed[cptr] = 1
      maxptr = cptr
    cptr = (maxptr + minptr + 1) // 2
      
  lptr[i] = cptr - fixed[cptr]

#print(lptr)

    
cnt = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    tgt = l[i] - l[j]
    if lptr[tgt] > j:
      cnt += lptr[tgt] - j

print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-



S = list("Z"+str(input()))
idx = 1
l = len(S)

ans = 0
while(idx <= l-3):
  if S[idx]+S[idx+1]+S[idx+2] == "ABC":
    ans += 1
    S[idx],S[idx+1],S[idx+2] = ["B","C","A"]
    idx -= 1
  else:
    idx += 1

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-


S = str(input()).replace("BC","D")

ans,stk = 0,0
for c in S:
  if c == "A":
    stk += 1
  elif c == "D":
    ans += stk
  else:
    stk = 0
print(ans)
### BUGGY CODE ###

import math
from functools import lru_cache
from operator import mul
from functools import reduce


def resolve():
    import sys
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    B = A[::-1]

    @lru_cache(maxsize=None)
    def combinations_count__(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    @lru_cache(maxsize=None)
    def combinations_count(n, r):
        r = min(r, n - r)
        numer = reduce(mul, range(n, n - r, -1), 1)
        denom = reduce(mul, range(1, r + 1), 1)
        return numer // denom

    sum = 0
    for i in range(K-1, N):
        sum += combinations_count(i, K-1) * A[i] % MOD - combinations_count(i, K-1) * B[i] % MOD

    print(sum % MOD)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import math
from functools import lru_cache
from operator import mul
from functools import reduce


def resolve():
    import sys
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    B = A[::-1]

    @lru_cache(maxsize=None)
    def combinations_count__(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    @lru_cache(maxsize=None)
    def combinations_count____(n, r):
        r = min(r, n - r)
        numer = reduce(mul, range(n, n - r, -1), 1)
        denom = reduce(mul, range(1, r + 1), 1)
        return numer // denom

    def combinations_count_(n, r):
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n

        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]

        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot

        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])

        return result

    def modinv(a, mod=10**9+7):
        return pow(a, mod-2, mod)

    def combinations_count(n, r, mod=10**9+7):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod
    
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

    sum = 0
    for i in range(K-1, N):
        sum += combinations_count(i, K-1) * A[i] % MOD - combinations_count(i, K-1) * B[i] % MOD

    print(sum % MOD)


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

n, m, r = list(map(int, input().split()))
rs = list(map(int, input().split()))
# construct map
import numpy as np
dists = np.ones((n + 1, n + 1)) * float('inf')
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
for i in range(1, n + 1):
    dists[i, i] = 0

from itertools import product, permutations
for i, j in product(range(1, 1 + n), repeat=2):
    for k in range(j + 1, n + 1):
        dists[j, k] = dists[k, j] = min(dists[j, k], dists[j, i] + dists[i, k])

ans = float('inf')
for path in permutations(rs):
    val = sum(dists[i, j] for i, j in zip(path, path[1:]))
    val = int(val)
    if val < ans:
        ans = val

print(ans)

### FIXED CODE ###

n, m, r = list(map(int, input().split()))
rs = list(map(int, input().split()))
# construct map
import numpy as np
dists = np.ones((n + 1, n + 1)) * float('inf')
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
for i in range(1, n + 1):
    dists[i, i] = 0

from itertools import product, permutations
for i, k in product(range(1, 1 + n), repeat=2):
    dists[:, k] = np.minimum(dists[:, k], dists[:, i] + dists[i, k])

ans = float('inf')
for path in permutations(rs):
    val = sum(dists[i, j] for i, j in zip(path, path[1:]))
    val = int(val)
    if val < ans:
        ans = val

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

n=int(input())
a=list(map(int,input().split()))
d=0
for i in range(0,n-1):
    for j in range(i+1,n):
        b=a[i]
        c=a[j]
        if b==c:
            d=1
            break
if d==0:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

n=int(input())
a=set(map(int,input().split()))
b=len(a)
if n==b:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline
import numpy as np
 
def main():
    H,W,K = map(int,input().split())
    a = [input() for _ in range(H)]
    
    x = np.zeros((H,W+1),dtype=int)
    for i in range(H):
        for j in range(W):
            if a[i][j] == "1":
                x[i][j+1] = 1
            else:
                x[i][j+1] = 0

    ans = 10**5
    for i in range(1<<H-1):
        use = np.zeros((H,W+1),dtype=int)
        u,now,count = 0,0,0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                count += 1
                bl = x[u:j+1,:]
                bl = np.sum(bl,axis=0)
                u = j+1
                use[now] = bl
                now += 1
        bl = np.sum(x[u:,:],axis=0)
        use[now] = bl
        r,vol = 1,np.zeros((1,H),dtype=int)
        while r<=W:
            f = use[:,r]
            vol += f
            if np.max(vol)>K:
                count += 1
                vol = f
            r += 1
        ans = min(ans,count)
        
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = S = [list(map(int, list(input()))) for _ in range(H)]
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        bl,yorn = [0 for _ in range(l)],True
        for right in range(W):
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().replace("\n","").split()))

for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter

n = int(input())
a = list(map(int, input().replace("\n","").split()))

"""
for i in range(1,n+1):
    print(a.count(i))
"""

S = Counter(a)

for i in range(1,n+1):
    print(S[i])
### BUGGY CODE ###

def gcd(x,y):
    if x <= y:
        z = x
        x = y
        y = z
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

n = int(input())
s = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            a = gcd(i+1,j+1)
            b = gcd(a,k+1)
            s += b
print(s)



### FIXED CODE ###

import math
n = int(input())
s = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        a = math.gcd(i,j)
        for k in range(1,n+1):
            b = math.gcd(a,k)
            s += b
print(s)
### BUGGY CODE ###

import numpy as np

ans = 1
n = int(input())
A = [int(i) for i in input().split()]
A = np.array(A,dtype='object')
ans = np.prod(A)
if ans ==0:
    print(0)
    exit()

if ans > 10**18:
    print('-1')
    exit()
print(int(ans))

### FIXED CODE ###

ans = 1
n = int(input())
A = [int(i) for i in input().split()]
A.sort()
for i in A:
    if i==0:
        print('0')
        exit()
    ans *= i
    if ans>10**18:
        print('-1')
        exit()
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [inf]*n
def dfs(s):
    if len(edge[s]) == 0:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    m = 0
    tmp.sort(reverse=True)
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])
### BUGGY CODE ###

N=int(input())
D=list(map(int,input().split(' ')))
M=int(input())
T=list(map(int,input().split(' ')))
ans='YES'
for t in T:
  if t not in D:
    ans='NO'
    break
  else:
    D.pop(D.index(t))
print(ans)

### FIXED CODE ###

import collections
N=int(input())
D=list(map(int,input().split(' ')))
M=int(input())
T=list(map(int,input().split(' ')))
cd = collections.Counter(D)
ct = collections.Counter(T)
ans = 'YES'
for t in list(ct.keys()):
	if ct[t]>cd[t]:
		ans = 'NO'
		break
print(ans)
### BUGGY CODE ###

mod = 10 ** 9 + 7

N = int(input())

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


result = 0
Zcount = 0
Bit0 = 0
Bit1 = 0
while Zcount < 60:
    for i in range(0, len(A)):
        if A[i] % 2 == 0:
            Bit0 += 1
            A[i] //= 2
        else:
            Bit1 += 1
            A[i] //= 2
    result += (2 ** Zcount) * (Bit0 * Bit1)
    Zcount += 1
    Bit0 = 0
    Bit1 = 0
print(result % mod)

### FIXED CODE ###

import numpy as np

mod = 10 ** 9 + 7

N = int(input())
 
AList = np.array(input().split(), dtype=np.int64)
count = 0
for i in range(60):
    Plus = np.count_nonzero(AList >> i & 1)
    count += 2 ** i * (Plus * (N - Plus))
print(count % mod)
### BUGGY CODE ###

import numpy as np
def s():
    return raw_input()
def li():
    return map(int,raw_input().split())

st = []
X = list(s())

st.append(X[0])
X.pop(0)
#for i in range(len(X)-2):
while len(X) > 0:
    st.append(X[0])
    X.pop(0)
    if len(st) >= 2:
        if st[-1] == 'T' and st[-2] == 'S':
            st.pop()
            st.pop()
print len(st)


### FIXED CODE ###

import numpy as np
def s():
    return raw_input()
def li():
    return map(int,raw_input().split())

st = []
X = list(s())
N = len(X)
X.reverse()
st.append(X[-1])
X.pop()
#for i in range(len(X)-2):
for i in range(N-1):
    st.append(X[-1])
    X.pop()
    if len(st) >= 2:
        if st[-1] == 'T' and st[-2] == 'S':
            st.pop()
            st.pop()
print len(st)
### BUGGY CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List
import array
import numpy as np

# from typing import Dict
from typing import Tuple

# from typing import Sequence


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = np.zeros((0, 2), dtype="int64")
    for i in range(M):
        args = input().split()
        codList = np.append(codList, np.array([[int(args[0]), int(args[1])]]), axis=0)

    columnSumList = np.zeros(W, dtype="int64")
    rowSumList = np.zeros(H, dtype="int64")

    maxColumnSum = 0
    maxColumIndexList: array[int] = []
    maxRowSum = 0
    maxRowIndexList: array[int] = []
    for item in codList:
        columnSum = columnSumList[item[1] - 1] + 1
        if columnSum > maxColumnSum:
            maxColumnSum = columnSum
            maxColumIndexList = [item[1]]
        elif columnSum == maxColumnSum:
            maxColumIndexList.append(item[1])

        rowSum = rowSumList[item[0] - 1] + 1
        if rowSum > maxRowSum:
            maxRowSum = rowSum
            maxRowIndexList = [item[0]]
        elif rowSum == maxRowSum:
            maxRowIndexList.append(item[0])

        columnSumList[item[1] - 1] = columnSum
        rowSumList[item[0] - 1] += 1

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            data = np.array([row, column])
            isMatch = False
            for item in codList:
                if np.allclose(item, data):
                    isMatch = True

            if isMatch:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


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

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    num = s
    dp = [0] * 13
    if num != '?':
        num = int(num)
        for j in range(13):
            dp[(10*j+num)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
            dp[j] %= MOD

answer = dp[5]
print(answer%MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])