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

n, p = map(int, input().split())
s = input()
a = []
c = 0
if p == 2:
    b = [0]*n
    for i in range(n):
        if int(s[i])%2 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
elif p == 5:
    b = [0]*n
    for i in range(n):
        if int(s[i])%5 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
else:
    b = [0]*p
    b[0] += 1
    for i in range(n):
        a.append(int(s[i:n])%p)
    for i in range(n):
        b[a[i]] += 1
    for i in range(p):
        c += int(b[i]*(b[i]-1)/2)
print(c)

### FIXED CODE ###

n, p = map(int, input().split())
s = input()
a = []
c = 0
if p == 2:
    b = [0]*n
    for i in range(n):
        if int(s[i])%2 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
elif p == 5:
    b = [0]*n
    for i in range(n):
        if int(s[i])%5 == 0:
            b[i] += 1
    for i in range(n):
        if b[i] == 1:
            c += i+1
else:
    b = [0]*p
    b[0] = 1
    d = [1]
    a.append(int(s[-1])%p)
    for i in range(n-1):
        d.append(d[-1]*10%p)
    for i in range(1, n):
        a.append((int(s[-i-1])*d[i]+a[i-1])%p)
    for i in range(n):
        b[a[i]] += 1
    for i in range(p):
        c += int(b[i]*(b[i]-1)/2)
print(c)
### BUGGY CODE ###

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

for i in range(q):
  l, r = [int(j) for j in input().split()]
  l -= 1
  r -= 1
  s_tmp = s[l:r+1]
  print(s_tmp.count('AC'))

### FIXED CODE ###

n,q = [int(i) for i in input().split()]
s = input()
l = []
r = []
for i in range(q):
  l_tmp, r_tmp = [int(j) for j in input().split()]
  l.append(l_tmp-1)
  r.append(r_tmp-1)
  
ac_cnt = s.count('AC')
r_cnt = [ac_cnt]
l_cnt = [0]
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    r_cnt.append(r_cnt[i-1]-1)
    l_cnt.append(l_cnt[i-1]+1)
  else:
    r_cnt.append(r_cnt[i-1])
    l_cnt.append(l_cnt[i-1])
    
for i in range(q):
  ans = r_cnt[l[i]] + l_cnt[r[i]] - ac_cnt
  print(ans)
### BUGGY CODE ###

import numpy as np
i = input()
N = list(map(int, input().split(' ')))
def one_turn(l):
  l.sort()
  n = l[0]
  n2 = l[1]
  
  return np.array([n,n2]+[ i-n for i in l[2:] if ((i%n != 0)or(i%n2 != 0)) ])

if len(set(N)) == 1 :
  print(N[0])
else :
  N = np.array(N)
  while True :
    N = one_turn(N)
    if N[0] == 1 :
      print(1)
      break
    if len(N) == 1 :
      print(N[0])
      break

### FIXED CODE ###

import numpy as np
i = input()
N = list(set(map(int, input().split(' '))))
def one_turn(l):
  l.sort()
  n = l[0]
  return np.array(list(set([n]+[ l[i]%n for i in range(1,len(l)) if ((l[i]%n != 0))])))

if len(set(N)) == 1 :
  print(N[0])
else :
  N = np.array(N)
  while True :
    N = one_turn(N)
    if N[0] == 1 :
      print(1)
      break
    if len(N) == 1 :
      print(N[0])
      break
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    dp = [0] * (N + 2)
    dp[-2] = 1
    for i in range(N - 1, -1, -1):
        if i in A:
            continue
        elif i + 1 in A:
            dp[i] = dp[i + 2]
        elif i + 2 in A:
            dp[i] = dp[i + 1]
        elif i + 1 in A and i + 2 in A:
            break
        else:
            dp[i] = dp[i + 1] + dp[i + 2]
    print(dp[0] % 1000000007)


main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    A = [0] * (N + 2)
    for _ in range(M):
        A[int(input())] = 1
    dp = [0] * (N + 2)
    dp[-2] = 1
    for i in range(N - 1, -1, -1):
        if A[i] == 1:
            continue
        dp[i] = dp[i + 1] + dp[i + 2]
    print(dp[0] % 1000000007)


main()
### BUGGY CODE ###

n, q = map(int, input().split())
b = input()
a = [[int(x) for x in input().split()] for _ in range(q)]
ans=[0]
for j in range(len(b)-1):
        if b[j:j+2] == "AC":
            ans.append(1)
        else:
            ans.append(0)
for i in a:
    print(sum(ans[i[0]:i[1]]))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [[int(x) for x in input().split()] for _ in range(q)]
add_list = [0]
for i in range(len(s)-1):
    if s[i:i+2] == "AC":
        add_list.append(add_list[i]+1)
    else:
        add_list.append(add_list[i])
for i in t:
    ans = add_list[i[1]-1] - add_list[i[0]-1]
    print(ans)
### BUGGY CODE ###

def edu_dp_f_lcs():
    s = input()
    t = input()
    slen = len(s)
    tlen = len(t)
    dp = [[0] * (tlen+1) for _ in range(slen+1)]
    for i in range(slen):
        for j in range(tlen):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    l = dp[slen][tlen]
    i = slen-1
    j = tlen-1
    ans = ''
    while l > 0:
        if s[i] == t[j]:
            ans = s[i]+ans
            j -= 1
            i -= 1
            l -= 1
        elif dp[i+1][j+1] == dp[i][j+1]:
            i-=1
        else:
            j-=1
    print(ans)

edu_dp_f_lcs()

### FIXED CODE ###

def edu_dp_f_lcs():
    s = input()
    t = input()
    slen = len(s)
    tlen = len(t)
    dp = [[0] * (tlen+1) for _ in range(slen+1)]
    for i in range(slen):
        for j in range(tlen):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    l = dp[slen][tlen]
    i = slen-1
    j = tlen-1
    ans = ''
    while l > 0:
        if s[i] == t[j]:
            ans = s[i]+ans
            j -= 1
            i -= 1
            l -= 1
        elif dp[i+1][j+1] == dp[i][j+1]:
            i-=1
        else:
            j-=1
    print(ans)

edu_dp_f_lcs()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [int(s) for s in A]

	BC = []
	for i in range(M):
		b, c = map(int, input().split(" "))
		BC.append((c, b))

	BC.sort(reverse=True)
	A.sort()

	for i in BC:
		c, b = i
		if A[0] >= c:
			continue

		tmp = bisect_left(A, c)
		if tmp <= b:
			A[:tmp] = [c] * tmp
		elif tmp > b:
			A[:b] = [c] * b

		A.sort()


	ans = 0
	for i in A:
		ans += i
	print(ans)


if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [(int(s) * (-1), 1) for s in A]
	heapq.heapify(A)

	for i in range(M):
		b, c = map(int, input().split(" "))
		heapq.heappush(A, (c * (-1), b))
	
	ans = []
	for i in range(N):
		t, con = heapq.heappop(A)
		for _ in range(con):
			if len(ans) == N:
				print(sum(ans))
				sys.exit()
			ans.append(t * (-1))
	print(sum(ans))


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

a,b = map(int,input().split())
jobs = []
while True:
    try:
        jobs.append(list(map(int,input().split())))
    except:
        break;
score = 0
for i in range(b):
  max_now = 0
  deli = []
  for j in range(len(jobs)):
    job = jobs[j]
    if job[0] <= i + 1:
      if max_now < job[1]:
        max_now = job[1]
        deli = job
  score += max_now 
  if deli != []:
    jobs.remove(deli)
print(score)

### FIXED CODE ###

import heapq

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

ans = 0
j = 0
for i in range(1, m + 1):
    while j < n and li[j][0] <= i:
        heapq.heappush(heap,-li[j][1])
        j += 1
    if heap:
        ans += -heapq.heappop(heap)
 
print(ans)
### BUGGY CODE ###

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

def Lsearch(B,key):
    B.append(key)
    for i in range(len(B)):
        if B[i] == key:
            if i != len(B)-1:
                B.pop() #pythonは参照渡しが基本なので元のリストに戻しておく
                return i
            else:
                B.pop()
                return -1

num,count,tmp,pt,flag = 1,0,0,0,0
if Lsearch(A,1) == -1:
    flag = 1
else:
    while pt < len(A):
        if Lsearch(A[pt:],num) != -1:
            tmp = Lsearch(A[pt:],num) + 1
            count += tmp - 1
            pt = pt + tmp
            num += 1
        else:
            count += len(A[pt:])
            break

if flag == 0:
    print(count)
else:
    print(-1)


### FIXED CODE ###

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

num,pt,n_pt,count = 1,-1,0,0
while n_pt < len(A):
    if A[n_pt] == num:
        count += n_pt - pt -1
        pt = n_pt
        num += 1
    n_pt += 1
if pt != -1:
    count += len(A) - pt -1
    print(count)
else:
    print(-1)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
m = [0] * n
m[0] = 0
for i in range(1, n):
    m[i] = min(m[j] + abs(h[j] - h[i]) for j in range(max(0, i-k),i))
print(m[n-1])


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    m = [0] * n
    m[0] = 0
    for i in range(1, n):
        m[i] = min(m[j] + abs(h[j] - h[i]) for j in range(max(0, i-k),i))
    print(m[-1])

main()
### BUGGY CODE ###

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

result = A
for i in range(A+1, B+1):
    result ^= i

print(result)


### FIXED CODE ###

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

array = []
bin_B = bin(B)[2:]
digit_B = len(bin_B)

if (A-1) % 4 == 1 or (A-1) % 4 == 2:
    if B % 4 == 1 or B % 4 == 2:
        array.append('0')
    else:
        array.append('1')
else:
    if B % 4 == 1 or B % 4 == 2:
        array.append('1')
    else:
        array.append('0')

for i in range(2, digit_B+1):
    num = 2 ** i
    if (A-1) % num < (num // 2) or ((A-1) % num) % 2 == 1:
        if B % num < (num // 2) or (B % num) % 2 == 1:
            array.append('0')
        else:
            array.append('1')
    else:
        if B % num < (num // 2) or (B % num) % 2 == 1:
            array.append('1')
        else:
            array.append('0')

array.reverse()
result = ''
for i in array:
    result += i

print(int(result, 2))
### BUGGY CODE ###

from heapq import heappop,heappush

N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
inf=float("inf")

yx=[]
for x,y,i in xy:
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[] for i in range(N)]
for i in range(1,N):
    x1,y1,num1=xy[i-1]
    x2,y2,num2=xy[i]
    data[num1].append([num2,x2-x1])
    data[num2].append([num1,x2-x1])
    y1,x1,num1=yx[i-1]
    y2,x2,num2=yx[i]
    data[num1].append([num2,y2-y1])
    data[num2].append([num1,y2-y1])
que=[[0,0]]
flag=[inf]*N
while que:
    l,u=heappop(que)
    if flag[u]!=inf:
        continue
    else:
        flag[u]=l
        for v,y in data[u]:
            if flag[v]!=inf:
                continue
            else:
                heappush(que,[y,v])
print(sum(flag))

### FIXED CODE ###

from heapq import heappush,heappop
n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[0,0] for i in range(n)]
for i in range(n):
    x,y,a=xy[i]
    data[a][0]=i
    y,x,a=yx[i]
    data[a][1]=i
ans=0
que=[[0,0]]
flag=[0]*n
count=0
while count<=n:
    l,a=heappop(que)
    if flag[a]==1:
        continue
    ans+=l
    flag[a]=1
    count+=1
    if count==n:
        break
    b,c=data[a]
    xb=xy[b][0]
    yc=yx[c][0]
    if 1<=b<=n-2:
        xd,yd,d=xy[b-1]
        xe,ye,e=xy[b+1]
        if flag[d]==0:
            heappush(que,[abs(xd-xb),d])
        if flag[e]==0:
            heappush(que,[abs(xe-xb),e])
    elif b==0:
        xe,ye,e=xy[1]
        if flag[e]==0:
            heappush(que,[abs(xb-xe),e])
    else:
        xd,yd,d=xy[n-2]
        if flag[d]==0:
            heappush(que,[abs(xb-xd),d])
    if 1<=c<=n-2:
        yg,xg,g=yx[c+1]
        yf,xf,f=yx[c-1]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    elif c==0:
        yg,xg,g=yx[1]
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    else:
        yf,xf,f=yx[n-2]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
print(ans)
### BUGGY CODE ###

n,m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
lst = sorted(lst, key=lambda x:x[1], reverse=False)
ans = 0
#カバーできてないもののうち終了時間の最も早いものを取る
while len(lst)>0:
    ans+=1
    rest = []
    et = lst[0][1]
    for l in lst:
        if l[0]>=et:
            rest.append(l)
    lst = rest
print(ans)

### FIXED CODE ###

#O(n)で実装
n,m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
rest = sorted(lst, key=lambda x:x[1], reverse=False)
ans = 1
et = rest[0][1] #end_time
for i in range(len(rest)):
    if rest[i][0]>=et:
        et=rest[i][1]
        ans+=1
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    s = {}
    for _ in range(n):
        string = input()
        if string in s:
            s[string] += 1
        else:
            s[string] = 1
    s = sorted(list(s.items()), key=lambda x: (x[1], x[0]), reverse=True)
    lst = []
    max_num = s[0][1]
    for string, num in s:
        if num != max_num:
            break
        lst.append(string)
    for l in reversed(lst):
        print(l)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = {}
    for _ in range(n):
        string = input()
        if string in s:
            s[string] += 1
        else:
            s[string] = 1
    s = sorted(list(s.items()), key=lambda x: (x[1], x[0]), reverse=True)
    lst = []
    max_num = s[0][1]
    if n == len(s):
        for string, num in reversed(s):
            print(string)
    else:
        for string, num in s:
            if num != max_num:
                break
            lst.append(string)
    for l in reversed(lst):
        print(l)


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

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

max_len = dp[-1][-1]
#print(max_len)

ans = ""

i = ls
j = lt

for l in range(max_len):
    while dp[i-1][j] == max_len - l:
        i -= 1
    while dp[i][j-1] == max_len - l:
        j -= 1
    ans += s[i-1]


print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

max_len = dp[-1][-1]
ans = ""

i = ls
j = lt

while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans += s[i - 1]
        i -= 1
        j -= 1

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

def main():
    dist = []
    import numpy as np
    from collections import deque
    n, x, y = map(int,input().split())
    g = [[] for _ in range(n)] 
    for i in range(n-1):

        g[i] += i+1,
        g[i+1] += i,
    g[x-1] += y-1,
    g[y-1] += x-1,
    a = [0]*n
    for start in range(n):
        d = [-1] * n
        d[start] = 0
        q = deque([start])
        add,pop = q.append,q.popleft
        while q:
            v = pop()
            for nv in g[v]:
                if d[nv] < 0:
                    d[nv] = d[v]+1
                    add(nv)
        # for i in d:
        #     a[i] += 1
        dist.append(d)
    dist = np.array(dist).flatten()
    for i in range(1,n):
        print(int(np.count_nonzero(dist==i)/2))
    # print(' '.join(str(i//2) for i in a[1:]))
main()

### FIXED CODE ###

def main():
    from collections import deque
    n,x,y=map(int,input().split())
    e=[[]for _ in range(n)]
    for i in range(n-1):
        e[i]+=i+1,
        e[i+1]+=i,
    e[x-1]+=y-1,
    e[y-1]+=x-1,
    a=[0]*n
    for s in range(n):
        d=[-1]*n
        d[s]=0
        q=deque([s])
        add,pop=q.append,q.popleft
        while q:
            v=pop()
            for w in e[v]:
                if d[w]<0:
                    d[w]=d[v]+1
                    add(w)
        for i in d:a[i]+=1
    print(' '.join(str(i//2)for i in a[1:]))
main()
### BUGGY CODE ###

n = int(input())

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

ans = [0]*n
for i in range(n):
    li2 = li.copy()
    del li2[i]
    li3 = list(set(li2))
    for j in range(len(li3)):
        m = li2.count(li3[j])*(li2.count(li3[j])-1)/2
        ans[i] += m
for l in range(len(ans)):
    print(int(ans[l]))
 

### FIXED CODE ###

N=int(input())
K=list(map(int, input().split()))
from collections import Counter
ans = 0
C = Counter(K)
for k, v in C.items():
    ans += v*(v-1)//2

for a in K:
    e = C[a]
    print(ans-e*(e-1)//2+(e-1)*(e-2)//2)
### BUGGY CODE ###

H, W = list(map(int, input().split(" ")))
s_list = []
ans_list = []
for i in range(H):
    s = input()
    temp_list = []
    for temp in s:
        if temp == "#":
            temp_list.append(1)
        else:
            temp_list.append(0)
    s_list.append(temp_list)


def a(now_x, now_y, black, black_count, sum_count):
    global s_list, ans_list
    if now_x == W-1 and now_y == H-1:
        if black_count > 0:
            sum_count += black_count
        elif s_list[now_y][now_x] == 1:
            sum_count += 1
        ans_list.append(sum_count)
        return
    if s_list[now_y][now_x] == 1:
        black = True
        if now_x < W-1:
            a(now_x+1, now_y, black, black_count+1, sum_count)
        if now_y < H-1:
            a(now_x, now_y+1, black, black_count+1, sum_count)
    else:
        if black:
            sum_count += black_count
        black = False
        black_count = 0
        if now_x < W-1:
            a(now_x+1, now_y, black, black_count, sum_count)
        if now_y < H-1:
            a(now_x, now_y+1, black, black_count, sum_count)


a(0, 0, False, 0, 0)
print(min(ans_list))


### FIXED CODE ###

h, w = map(int, input().split())
s_list = []  # h, w
dp_dict = {}
for i in range(h):
    s = input()
    temp_list = []
    for temp in s:
        if temp == "#":
            temp_list.append(1)
        else:
            temp_list.append(0)
    s_list.append(temp_list)


def search(x, y, black):
    res = 0
    if (x, y, black) in dp_dict:
        return dp_dict[(x, y, black)]
    if x == w-1 and y == h-1:
        if s_list[y][x] == 1:
            if black:
                res = 0
            else:
                res = 1
        else:
            res = 0
    elif x == w-1:
        if s_list[y][x] == 1:
            if black:
                res = search(x, y+1, True)
            else:
                res = search(x, y+1, True)+1
        else:
            res = search(x, y+1, False)
    elif y == h-1:
        if s_list[y][x] == 1:
            if black:
                res = search(x+1, y, True)
            else:
                res = search(x+1, y, True)+1
        else:
            res = search(x+1, y, False)
    else:
        if s_list[y][x] == 1:
            if black:
                res = min([search(x+1, y, True), search(x, y+1, True)])
            else:
                res = min([search(x+1, y, True), search(x, y+1, True)])+1
        else:
            res = min([search(x+1, y, False), search(x, y+1, False)])
    dp_dict[(x, y, black)] = res
    return res


print(search(0, 0, False))
### BUGGY CODE ###

import numpy as np
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))


def bfs(start: list):
    global h, w, maze
    length = np.array([[-1 for _ in range(w)] for _ in range(h)])
    check = set()
    queue = [start]
    depth = 0
    while len(queue) > 0:
        [x, y, bx, by] = queue.pop(0)
        check.add((x, y))
        length[x][y] = length[bx][by] + 1

        depth += 1
        target = []
        if x != 0:
            target.append((x - 1, y))
        if x != h - 1:
            target.append((x + 1, y))
        if y != 0:
            target.append((x, y - 1))
        if y != w - 1:
            target.append((x, y + 1))

        for t in target:
            if t not in check:
                if maze[t[0]][t[1]] == ".":
                    queue.append([t[0], t[1], x, y])

    return length.max()


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

print(ans)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
maze = []

for i in range(h):
    maze.append(list(input()))

move = [[-1, 0], [1, 0], [0, -1], [0, 1]]


def bfs(start: list):
    global h, w, maze
    length = [[-1 for _ in range(w)] for _ in range(h)]
    check = [[False for _ in range(w)] for _ in range(h)]
    check[start[0]][start[1]] = True
    queue = deque([start])
    res = -1
    while len(queue) > 0:
        [x, y, bx, by] = queue.popleft()

        length[x][y] = length[bx][by] + 1
        res = max(res, length[x][y])

        for p in move:
            next_x = x + p[0]
            next_y = y + p[1]
            if (next_x < 0)or(next_x == h)or(next_y < 0)or(next_y == w):
                continue
            if not check[next_x][next_y]:
                check[next_x][next_y] = True
                if maze[next_x][next_y] == ".":
                    queue.append([next_x, next_y, x, y])

    return res


ans = -1

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs([i, j, i, j]))

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

def main():
    N, K, Q = map(int, input().split())
    A_list = [int(input()) for _ in range(Q)]
    player_score = [K for _ in range(N)]

    for player_answer in A_list:
        # 正解者スコア+1して, その後全体-1
        player_score[player_answer - 1] = player_score[player_answer - 1] + 1
        player_score = list(map(lambda i: i - 1, player_score))
    
    for score in player_score:
        print("Yes" if score > 0 else "No")
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, K, Q = map(int, input().split())
    A_list = [int(input()) for _ in range(Q)]
    player_score = [K for _ in range(N)]

    for player_answer in A_list:
        # 正解者スコア+1して, その後全体-n
        player_score[player_answer - 1] = player_score[player_answer - 1] + 1

    player_score = list(map(lambda i: i - len(A_list), player_score))
    
    for score in player_score:
        print("Yes" if score > 0 else "No")
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

R, G, B, N = map(int, raw_input().split())

count = 0
r_max = int(N / R)+1
g_max = int(N / G)+1

for r in xrange(r_max):
    rest_val = N - R*r
    for g in xrange(g_max):
        rest_val2 = rest_val - G * g
        if rest_val2 % B == 0 and rest_val2 >= 0:
            # print "r="+str(r)+",g="+str(g)+",b="+str(rest_val2/B)
            count += 1

print count

### FIXED CODE ###

R, G, B, N = map(int, raw_input().split())

count = 0
r_max = int(N / R)+1
g_max = int(N / G)+1

for r in xrange(r_max):
    rest_val = N - R*r
    for g in xrange(g_max):
        rest_val2 = rest_val - G * g
        if rest_val2 < 0: break
        if rest_val2 % B == 0:
            # print "r="+str(r)+",g="+str(g)+",b="+str(rest_val2/B)
            count += 1

print count