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

from collections import deque
S=input()
N=int(input())
Q=[input() for i in range(N)]
T=deque(S)
for i in range(N):
    if Q[i][0]=="2":
        if Q[i][2]=="1":
            T.appendleft(Q[i][4])
            S=list(T)
        if Q[i][2]=="2":
            T.append(Q[i][4])
            S=list(T)
    if Q[i][0]=="1":
        S=list(T)
        S=S[::-1]
        T=deque(S)
print(''.join(S))

### FIXED CODE ###

from collections import deque
S=input()
N=int(input())
Q=[input() for i in range(N)]
T=deque(S)
cnt=0
for i in range(N):
    if Q[i][0]=="1":
        cnt+=1
    if cnt%2==0:
        if Q[i][0]=="2":
            if Q[i][2]=="1":
                T.appendleft(Q[i][4])
            if Q[i][2]=="2":
                T.append(Q[i][4])
    if cnt%2==1:
        if Q[i][0]=="2":
            if Q[i][2]=="1":
                T.append(Q[i][4])
            if Q[i][2]=="2":
                T.appendleft(Q[i][4])
if cnt%2==1:
    T.reverse()
print(''.join(T))
### BUGGY CODE ###

n = int(input())
x, y, h = [], [], []

for i in range(n):
    X, Y, H = map(int, input().split())
    x.append(X)
    y.append(Y)
    h.append(H)

for X in range(101):
    for Y in range(101):
        for i in range(n):
            H = h[i] + abs(x[i] - X) + abs(y[i] - Y)
            if all(h[j] == max(H - abs(x[j] - X) - abs(y[j] - Y), 0) for j in range(n)):
                print(X, Y, H)
                break

### FIXED CODE ###

n = int(input())
x, y, h = [], [], []

for i in range(n):
    X, Y, H = map(int, input().split())
    x.append(X)
    y.append(Y)
    h.append(H)

for X in range(101):
    for Y in range(101):
        for i in range(n):
            H = h[i] + abs(x[i] - X) + abs(y[i] - Y)
            if all(h[j] == max(H - abs(x[j] - X) - abs(y[j] - Y), 0) for j in range(n)):
                print(X, Y, H)
                break
### BUGGY CODE ###

from numpy import array as arr
N = int(input())
a = arr(list(map(int,input().split())))
n = 0
for i in range(1,N+1):
    for j in range(N+1-i):
        if a[j:j+i].sum() == 0:
            n += 1
print(n)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
s = [0]*(len(a)+1)
for i in range(len(a)):
    s[i+1] = s[i] + a[i]
b = {}
for x in s:
    if str(x) not in b:
        b[str(x)] = 1
    else:
        b[str(x)] += 1
n = 0
for x in b:
    n += b[x]*(b[x]-1)/2
print(int(n))
### BUGGY CODE ###

n=int(input())
prime=[]
tmp = 2
for i in range(2, 55555):
    if prime:
        for j in range(len(prime)):
            if i % prime[j] == 0:
                break
            else:
                if j == len(prime) - 1:
                    prime.append(i)
    else:
        if n > tmp:
            prime.append(i)
print(prime[0:n])


### FIXED CODE ###

n = int(input())
ans=[]
def sosu(x):
    for i in range(2,x):
        if x % i ==0:
            return False
    return True

for i in range(11,55555,5):
    if sosu(i) and i % 5 ==1:
        ans.append(i)
        if len(ans) >= n:
            break

print(' '.join([str(s) for s in ans]))
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=2**30]*h*w
d[~w+a*w+b]=1
q=[(a-1,b-1)]
for s,t in q:
 p=d[s*w+t]+1
 for y,x in(-1,0),(0,-1),(0,1),(1,0):
  for z in range(k):
   if(h>(i:=s+y*~z)>-1<(j:=t+x*~z)<w)-1or'.'<m[i][j]or d[i*w+j]<p:break
   q+=(i,j),;d[i*w+j]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
sum_r = sum(A)
ans = ''
for i in range(N):
    amount = sum_r
    for j in range(N//2):
        #print((i+1+j*2)%N)
        amount -= A[(i+1+j*2)%N]*2
    ans += str(amount) + ' '
print(ans.rstrip())




### FIXED CODE ###

import sys
# input = sys.stdin.readline()
N = int(input())
A = list(map(int,input().split()))
sum_r = 0
# print(A[0::2])
# print(A[1::2])
sum_odd = 0
sum_even = 0
for i in range(N):
    a = A[i]
    sum_r += a
    if i % 2 == 0:
        sum_odd += a
    else:
        sum_even += a

ans = ''
rolling_even = sum_even 
rolling_odd = sum_odd - A[0]
#print(sum_r,sum_even)
X_i = sum(A) - 2 * sum(A[1::2])
sys.stdout.write(str(X_i))
for i in range(N-1):
    X_i_plus_1 = 2 * A[i] - X_i
    sys.stdout.write(' ' + str(X_i_plus_1))
    X_i = X_i_plus_1
# ans += str(sum_r - 2 * rolling_even) + ' ' + str(sum_r - 2 * rolling_odd)
# sys.stdout.write(ans + ' ')
# mepo = A[1]
# mope = A[0]
# for i in range(2,N):
#     tmp = sum_r

#     if i % 2 == 0:
#         # rolling_even += A[(i-2)%N] - A[(i-1)%N]
#         mepo = A[(i-1)]
#         rolling_even += mope - mepo
#         tmp = sum_r - 2 * rolling_even
#     else:
#         mope = A[(i-1)]
#         rolling_odd += mepo - mope
#         tmp = sum_r - 2 * rolling_odd
#     sys.stdout.write(' '+str(tmp))
#     ans += ' ' + str(tmp)
# sys.stdout.write('\n')
### BUGGY CODE ###

# input
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

# process
max_a = max(A)
dp = [10**9]*(H+max_a)
dp[0] = 0

for i in range(H):
    if dp[i] == 10**9:
        continue
    for j in range(N):
        t = dp[i]+B[j]
        if dp[i+A[j]] > t:
            dp[i+A[j]] = t

# output
print(min(dp[H:]))


### FIXED CODE ###

import numpy as np

# input
H, N = map(int, input().split())

AB = [list(map(int, input().split())) for _ in range(N)]
A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T

# process
dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)

# output
print(dp[H])
### BUGGY CODE ###

h,w,m = map(int,input().split())
dh = [0]*(h+1)
dw = [0]*(w+1)
l=[[0 for i in range(w+1)] for j in range(h+1)]
for _ in range(m):
    x,y = map(int,input().split())
    dh[x]+=1
    dw[y]+=1
    l[x][y]=1
m = max(dh)
hi = dh.index(m)
c=m
m = 0
for i in range(1,w+1):
    d = dw[i]
    if l[hi][i]==1:
        d-=1
    m = max(m,d)
c+=m
print(c)

### FIXED CODE ###

from collections import defaultdict
h,w,m = map(int,input().split())
dh = defaultdict(int)
dw = defaultdict(int)
l=defaultdict(tuple)
for _ in range(m):
    x,y = map(int,input().split())
    dh[x]+=1
    dw[y]+=1
    l[(x,y)]=1
m = 0
for i in range(1,h+1):
    if dh[i]>m:
        m = dh[i]
        hi=i
c=m
m = 0
for i in range(1,w+1):
    d = dw[i]
    if l[(hi,i)]==1:
        d-=1
    m = max(m,d)
c+=m
m = 0
wi=0
for i in range(1,w+1):
    if dw[i]>m:
        m = dw[i]
        wi=i
c2=m
m = 0
for i in range(1,h+1):
    d = dh[i]
    if l[(i,wi)]==1:
        d-=1
    m = max(m,d)
c2+=m
print(max(c,c2))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
for i in range(q):
  b[i],c[i]=map(int,input().split())

s=sum(a)

for i in range(q):
  cnt=a.count(b[i])
  s+=cnt*(c[i]-b[i])
  for _ in range(cnt):
    a.remove(b[i])
    a.append(c[i])
  print(s)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
for i in range(q):
  b[i],c[i]=map(int,input().split())

s=sum(a)

#このコードはO(10**10)になる可能性があり、重すぎる
"""
for i in range(q):
  while b[i] in a:
    s+=c[i]-b[i]
    a.remove(b[i])
    a.append(c[i])
  print(s)
"""

cnt_list=[0]*(10**5+1)
for i in range(n):
  cnt_list[a[i]]+=1

for i in range(q):
  s+=(c[i]-b[i])*cnt_list[b[i]]
  cnt_list[c[i]]+=cnt_list[b[i]]
  cnt_list[b[i]]=0
  print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')

N, K=map(int, input().split())
h=list(map(int, input().split()))
dp = [10**5] * (N+K)
dp[0] = 0
dp[1] = dp[0] + abs(h[0]-h[1])
for i in range(2, N):
    dp[i] = min([dp[i-k] + abs(h[i-k]-h[i]) for k in range(1, K+1)])
print(dp[N-1])

### FIXED CODE ###

N, K=map(int, input().split())
h=list(map(int, input().split()))
dp = [10**5] * N
dp[0] = 0
for i in range(1, N):
    x = max(0, i-K)
    dp[i] = min([dp[j]+abs(h[j]-h[i]) for j in range(x, i)])
print(dp[-1])
### BUGGY CODE ###

def main():
    n = int(input())
    l = list(map(int,input().split()))
    l1 = l.count(1)
    l2 = l.count(2)
    l3 = l.count(3)

    dp = [[[0]*(l3+1) for i in range(l2+l3+1)] for j in range(n+1)]

    for i in range(1,n+1):
        for j in range(min(i,l2+l3)+1):
            for k in range(min(j,l3)+1):
                s = i-j
                t = j-k
                count = n
                if s > 0:
                    count += dp[s-1][t][k]*s
                    
                if t > 0 :
                    count += dp[s+1][t-1][k]*t
                if k > 0 :
                    count += dp[s][t+1][k-1]*k

                count *= 1/(s+t+k)
                dp[s][t][k] = count

    print(dp[l1][l2][l3])
if __name__ == "__main__":
    main()



### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):#n=i+j+k
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
l=0
r=0
s=[0 for i in range(N+1)]
s[0]=0

for i in range(1,N+1):
    s[i]=S[0:i].count('AC')

for i in range(Q):
    l,r=map(int,input().split())
    
    print(s[r]-s[l])




'''
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())

s=[0 for i in range(N+1)]
s[0]=0

for i in range(1,N+1):
    s[i]=S[0:i].count('AC')

for i in range(Q):
    print(s[r[i]]-s[l[i]])
'''


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
l=0
r=0

s=[]
s.append(0)

for i in range(1,N):
    if(S[i-1]=='A' and S[i]=='C'):

        s.append(s[i-1]+1)

    else:
        s.append(s[i-1])

for i in range(Q):

    l,r=map(int,input().split())

    print(s[r-1]-s[l-1])
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))

cnt = 0
for i in range(1, n):
    if min(p[:i]) > p[i]:
        cnt += 1
print(cnt + 1)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))

cnt = 0
p_min = p[0]
for i in range(n):
    p_min = min(p_min, p[i])
    if p_min == p[i]:
        cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
A = (int(x) for x in input().split())
sum  = 1
flag = 0
for i in A:
    if(i == 0):
        print(0)
        flag=1
        break
    else:
        sum = sum * i
if(flag==0):
    if(sum > 10**18):
        print(-1)
    else:
        print(sum)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
sum  = 1
flag = 0
for i in A:
    if(i == 0):
        print(0)
        flag=2
        break
if(flag==0):
    for i in A:
        sum = sum * i
        if(sum > 10**18):
            flag=1
            break
if(flag==0):
    print(sum)
elif(flag==1):
    print(-1)
### BUGGY CODE ###

#! python3
# doubly_linked_list.py

keys = []

n = int(input())
for i in range(n):
    command = input()
    if command == 'deleteFirst':
        keys.pop(0)
    elif command == 'deleteLast':
        keys.pop(-1)
    else:
        command, x = command.split(' ')
        if command == 'insert':
            keys.insert(0, int(x))
        elif command == 'delete':
            if int(x) in keys:
                keys.remove(int(x))

print(' '.join([str(k) for k in keys]))


### FIXED CODE ###

#! python3
# doubly_linked_list.py

from collections import deque

keys = deque([])

n = int(input())

for i in range(n):
    command = input()
    if command == 'deleteFirst':
        keys.popleft()
    elif command == 'deleteLast':
        keys.pop()
    else:
        command, x = command.split(' ')
        if command == 'insert':
            keys.appendleft(int(x))
        elif command == 'delete':
            if int(x) in keys:
                keys.remove(int(x))

print(' '.join([str(k) for k in keys]))
### BUGGY CODE ###

# coding: utf-8
import copy

N = int(input())


ss = list()

base = dict([[chr(ord('a') + i),  0] for i in range(26)])
for k in range(N):
    a = copy.copy(base)
    s = input()
    for c in s:
        a[c] += 1

    ss.append(a)

res = 0
for i in range(N-1):
    for j in range(i+1, N):
        flag = True
        for k in range(26):
            c = chr(ord('a')+k)
            if ss[i][c] != ss[j][c]:
                flag = False
                break
        if flag:
            res += 1


print(res)

### FIXED CODE ###

# coding: utf-8
import copy

N = int(input())

d = dict()

res = 0
for i in range(N):
    s = input()
    s = ''.join(sorted(s))

    if s in d.keys():
        res += d[s]
        d[s] += 1
    else:
        d[s] = 1

print(res)
### BUGGY CODE ###

import collections

N,K=map(int,input().split())
P=list(map(int,input().split()))
cnt=0
tmp=0
ans=0
count=0
for i in range(N-K+1):
	#print(P[i:i+K])
	if cnt<sum(P[i:i+K]):
		cnt=sum(P[i:i+K])
		tmp=i
Q=P[tmp:tmp+K]
count=collections.Counter(Q)
C_K=list(count.keys())
C_V=list(count.values())
R=len(count)
for i in range(R):
	ans+=(C_K[i]*(C_K[i]+1)/(2*C_K[i])*C_V[i])
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
E=[0]*N

for i in range (N):
	E[i]=((P[i]+1)/2)

L=[0]*(N+1)
L[0]=0

for i in range (N):
	L[i+1]=L[i]+E[i]

ans=0

for i in range (K,N+1):
	ans=max(ans,L[i]-L[i-K])

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

# -*- using:utf-8 -*-
class main:
  def function(x, k, d):
    for i in range(k):
      if abs(x + d) >= abs(x - d):
        x = x - d
      else:
        x = x + d
    print(abs(x))

if __name__ == "__main__":
  x, k, d = map(int, input().split())
  main.function(x,k,d)

### FIXED CODE ###

# -*- using:utf-8 -*-

class main:
  def function(x, k, d):
    if x >= k * d:
      ans = x - k * d
    else:
      r = x // d
      n = k - r
      if n % 2 == 0:
        ans = x % d
      else:
        ans = abs(x % d - d)
    return ans

if __name__ == "__main__":
  x, k, d = map(int, input().split())
  x = abs(x)
  ans = main.function(x, k, d)
  print(ans)
### BUGGY CODE ###

def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])
    
    min_cost = {}
    def solve_cost(i, j):
        if (i, j) in min_cost:
            return min_cost[i, j]
        if i == 0 or j == 0:
            return 0
        min_cost[i, j] = min(solve_cost(i, j - 1), solve_cost(i - 1, j)) + dp[i][j]
        return min_cost[i, j]
    
    return solve_cost(h, h)
  
h, w = map(int, input().split())
s = [input() for i in range(h)]

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)

### FIXED CODE ###

def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])

    dq = [[INF] * (h + 1) for i in range(h + 1)]
    dq[0][0] = 0
    for i in range(h):
        dq[i + 1][0] = dq[i][0] + dp[h - i][h]
        dq[0][i + 1] = dq[0][i] + dp[h][h - i]  
    for i in range(h):
        for j in range(h):
            dq[i + 1][j + 1] = min(dq[i + 1][j] + dp[h - (i + 1)][h - j],
                                   dq[i][j + 1] + dp[h - i][h - (j + 1)])

    return dq[h][h]


h, w = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 5
OFFSET = 500

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)
### BUGGY CODE ###

from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2
def ok(x):
    S = list(accumulate(1 if a >= x else -1 for a in A))
    ms = min(min(S), 0)
    S = [1] + [s - ms + 1 for s in S]
    L = max(S) + 1
    B = [0] * L
    c = 0
    for s in S:
        i = s
        while i > 0:
            c += B[i]
            i -= i & -i
        i = s
        while i < L:
            B[i] += 1
            i += i & -i
    return c >= NN

B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
    m = (l + r) // 2
    if ok(B[m]):
        l = m
    else:
        r = m
print(B[l])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
NN = ((N + 1) * N // 2 + 1) // 2

def ok(x):
    B = [0] * (2 * N + 1)
    res, cum, cur = 0, 0, 0
    B[0] += 1
    for a in A:
        if a >= x:
            cum += 1
            cur += B[cum]+1
        else:
            cur -= B[cum]-1
            cum -= 1
        B[cum] += 1
        res += cur
    return res >= NN

B = sorted(set(A))
l = 0
r = len(B)
while r - l > 1:
    m = (l + r) // 2
    if ok(B[m]):
        l = m
    else:
        r = m
print(B[l])
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int,input().split()))
dp = [0]*n
for i in range(n):
  tmp = []
  for j in range(1,k+1):
    if i-j >= 0:
    	tmp.append(dp[i-j] + abs(h[i]-h[i-j]))
  dp[i] = min(tmp) if len(tmp) != 0 else 0
print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int,input().split()))

def calc():
  dp = [0]*n
  for i in range(n):
    tmp = []
    for j in range(1,k+1):
      if i-j >= 0:
          tmp.append(dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min(tmp) if len(tmp) != 0 else 0
  return dp[n-1]

print(calc())
### BUGGY CODE ###

import bisect

def main():
    N = int(input())
    P = list(map(int, input().split()))

    ans = 0
    first = P[0]-1

    while len(P) != 0:
        ans += 1
        m = min(P)
        if m == first:
            ans+=1
            break
        i = P.index(m)
        P = P[0:i]



    print(ans)

    return 0

if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect
import numpy as np

def main():
    N = int(input())
    P = list(map(int, input().split()))


    ans = 1
    f = P[0]

    for i in range(1, N):
        f_o = P[i]
        if f >= f_o:
            ans+=1
            f = f_o
    print(ans)
    return 0


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

s = [input()]
q_number = int(input())
reverse_flag = 1
for i in range(q_number):
  temp = input().split()
  if temp[0] == "1": 
    reverse_flag = reverse_flag * -1
  else:
    headstails = int(temp[1])*reverse_flag 
    if headstails == 1 or headstails == -2:
      s.insert(0,temp[2])
    else:
      s.append(temp[2])
      
s = "".join(s)
if reverse_flag == -1:
  s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q_number = int(input())
reverse_flag = 1
head = ""
tail = ""
for i in range(q_number):
  temp = input().split()
  if temp[0] == "1": 
    reverse_flag = reverse_flag * -1
  else:
    headstails = int(temp[1])*reverse_flag 
    if headstails == 1 or headstails == -2:
      head = temp[2] + head
    else:
      tail = tail + temp[2]
      
if reverse_flag == 1:
  print(head+s+tail)
else:
  print(tail[::-1]+s[::-1]+head[::-1])
### BUGGY CODE ###

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

    ans = 10 ** 6

    def calc(lst): #lst: 区切りを与える
        n = sum(lst) + 1 #n+1個に縦を区切る
        tmp = [0] * n
        count = n - 1 #区切る本数
        for w in range(W):
            position = 0
            now = [0] * n
            for h in range(H):
                if S[h][w] == '1': #ホワイトチョコレートのとき
                    now[position] += 1
                if lst[h] == 1:
                    position += 1
            
            flag = True
            for i in range(n):
                if tmp[i] + now[i] > K:
                    flag = False

            if flag:
                for i in range(n):
                    tmp[i] += now[i]
            else:
                count += 1
                for i in range(n):
                    tmp[i] = now[i]
        for i in range(n):
            if now[i] > K:
                count += 10 ** 6
                
        return count

    for i in range(2 ** (H - 1)):
        lst = [0] * (H)
        for j in range(H - 1):
            if (i >> j) & 1:
                lst[j] = 1
        ans = min(calc(lst), ans)

    print (ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

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

import numpy as np

n, m = map(int, input().split())
DP = [[np.array([0, 0, 0]) for j in range(m+1)] for i in range(8)]

for _ in range(n):
    xyz = list(map(int, input().split()))
    for sign in range(8):
        check = np.zeros(3, dtype=np.int)
        for i in range(3):
            if (sign >> i) & 1:
                check[i] = 1
            else:
                check[i] = -1

        for i in range(m-1, -1, -1):
            candidate = DP[sign][i] + xyz
            delta = DP[sign][i+1] - DP[sign][i]
            delta_value = sum(delta*check)
            if delta_value < sum(xyz*check):
                DP[sign][i+1] = DP[sign][i] + xyz

ans = 0
for i in range(8):
    total = sum(np.abs(DP[i][m]))
    ans = max(ans, total)

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
cakes = []
for i in range(n):
    x, y, z = map(int, input().split())
    cakes.append([x, y, z])

ans = []
for sign in range(8):
    check = [0, 0, 0]
    for i in range(3):
        if (sign >> i) & 1:
            check[i] = 1
        else:
            check[i] = -1

    cakes.sort(reverse=True, key=lambda x: x[0]*check[0] + x[1]*check[1] + x[2]*check[2])
    value = [0, 0, 0]
    for i in range(m):
        a, b, c = cakes[i]
        value[0] += a
        value[1] += b
        value[2] += c
        
    candidate = 0
    for i in range(3):
        candidate += abs(value[i])

    ans.append(candidate)

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

n = int(input())
a_list = list(map(int, input().split()))
count = 0
Jlist = []
for j in range(2, n+1):
    if j > a_list[j-1]:
        for i in range(1, j):
            if j -i == a_list[i-1] + a_list[j-1]:
                count += 1

print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
count = 0
d={}
for i in range(n):
    if i - a[i] in d:
        count+=d[i - a[i]]
    if i + a[i] in d:
        d[i+a[i]] += 1
    else:
        d[i+a[i]] = 1

print(count)