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

n,m,d = map(int, input().split())

grid = [list(map(int, input().split())) for _ in range(n)]

q = int(input())

for _ in range(q):
    l,r = map(int, input().split())
    prev_x= -1
    prev_y = -1
    s = 0

    for j in range(l,r+1,d):
        for k in range(n):
            if j in grid[k]:
                y = (grid[k].index(j))+1
                x = k+1
                break
        if prev_x == -1 and prev_y == -1:
            prev_x = x
            prev_y = y
        else:
            s += abs(prev_x-x) + abs(prev_y-y)
            prev_x = x
            prev_y = y
    print(s)
            
                


### FIXED CODE ###

n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m+1):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))


def cumsum(l):
    s = 0
    for v in l:
        s += v
        yield s


a = (0,) + tuple(cumsum(A))
b = (0,) + tuple(cumsum(B))
ans = 0
m = M
for i in range(N + 1):
    if a[i] > K:
        continue
    for j in range(m, -1, -1):
        if a[i] + b[j] <= K:
            k = j
            break
        else:
            continue
    ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


def cumsum(l):
    s = 0
    for v in l:
        s += v
        yield s


a = [0] + list(cumsum(A))
b = [0] + list(cumsum(B))
ans = 0
n = N + 1
m = M
for i in range(n):
    if a[i] > K:
        continue
    for j in range(m, -1, -1):
        if a[i] + b[j] <= K:
            m = j
            break
        else:
            continue
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

N,P = map(int,input().split())
c = int(P**(1/N))+1
for i in range(c,0,-1):
    if P%(i**N)==0:
        print(i)
        exit()

### FIXED CODE ###

N,P = map(int,input().split())
r = round(P**(1/N))
for i in range(r,0,-1):
    if P%(i**N)==0:
        print(i)
        exit()
### BUGGY CODE ###

import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [(n,n)]
r = [(n,n)]
mc = n
mr = n
for _ in range(q):
    m, q = list(map(int, input().split()))
    if m == 1:
        for col, pos in r:
            if col >= q:
                break
        if q < mc:
            mc = q
            for i,(_, row) in enumerate(c):
                if row >= q:
                    break
            c.insert(i, (pos, q))
        if q not in [1,n]:
            count -= max(0, pos - 2)
    else:
        for row, pos in c:
            if row >= q:
                break
        if q < mr:
            mr = q
            for i,(_, col) in enumerate(r):
                if col > q:
                    break
            r.insert(i, (pos, q))
        if q not in [1,n]:
            count -= max(0, pos - 2)
print(count)



### FIXED CODE ###

import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * (n + 1)
r = [n] * (n + 1)
mc = n
mr = n
for _ in range(q):
    m,q = list(map(int, input().split()))
    if m == 1:
        if q <= mc:
            count -= mr -2
            for p in range(q+1, mc):
                c[p] = mr
            c[q] = 0
            mc = q
        else:
            count -= c[q] - 2
    else:
        if q <= mr:
            count -= mc -2
            for p in range(q+1, mr):
                r[p] = mc
            r[q] = 0
            mr = q
        else:
            count -= r[q] - 2
print(count)
### BUGGY CODE ###

n=int(input())
lisa=[]
ans=1
add=[]
coua=0
for i in range(n):
    a=input()
    lisa.append(a)
    coua=lisa.count(a)
    if ans<coua:
        add=[]
    if ans<=coua:
        ans=coua
        add.append(a)
add=sorted(set(add))
for i in range(len(add)):
    print(add[i])

### FIXED CODE ###

n=int(input())
S=[]
ans=0
import collections
for i in range(n):
    s=input()
    S.append(s)
S=sorted(S)
c=collections.Counter(S)
ANS=[]
for i in range(n-1):
    if (S[i]!=S[i+1] and ans<c[S[i]]) or i==n-2:
        ans=c[S[i]]#Sの？番目がSにいくつあるのか
        ANS.append(ans)
inko=""
ans=max(ANS)
for i in range(n):
    if c[S[i]]==ans and S[i]!=inko:
        print(S[i])
        inko=S[i]
### BUGGY CODE ###

K,S = map(int, input().split())
ans = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if S == x+y+z:
                ans += 1
                break

print(ans)

### FIXED CODE ###

K,S = map(int, input().split())
ans = 0

for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-x-y <= K:
            ans += 1

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

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
### BUGGY CODE ###

N,K = map(int,input().split())
ball = [int(j) for j in input().split()]
kind = []
for i in range(1,N+1):
    temp = ball.count(i)
    kind.append(temp)
if kind.count(0)>=N-K:
    print(0)
else:
    kind.sort()
    sumNum = 0
    for i in range(N-K):
        sumNum += kind[i]
    print(sumNum)

### FIXED CODE ###

import collections
from operator import itemgetter
N,K = map(int,input().split())
ball = [int(j) for j in input().split()]

kind = dict(collections.Counter(ball))

if len(kind) <= K:
    print(0)
else:
    skind = sorted(kind.items(),key=itemgetter(1))
    sumNum = 0
    for i in range(len(skind)-K):
        sumNum += skind[i][1]
    print(sumNum)
### BUGGY CODE ###

n=int(input())
a=list(map(lambda x:('0'*62+bin(int(x))[2:])[-62:],input().split()))
mod=pow(10,9)+7
ans=0
for i in range(61):# 2^iの位
  bit1=0
  for ai in a:
    bit1+=int(ai[-i-1])
  ans+=pow(2,i,mod)*bit1*(n-bit1)
  ans%=mod
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n=int(input())
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  ans=0
  bit=[0]*61 #bit[i]:2^iの位が1である物の個数
  for ai in a:
    for j in range(61):
      if ((ai>>j) & 1):
        bit[j]+=1
  for i in range(61):
    ans+=(pow(2,i)%mod)*bit[i]*(n-bit[i])
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

S=input()
count=0
while 1:
    tmp=S.count('BW')
    if tmp==0:
        break

    count+=tmp
    S=S.replace('BW','WB')[S.find('B'):S.rfind('W')+1]
print(count)

### FIXED CODE ###

S=input()

tmp=[i for i, x in enumerate(S) if x == 'W']
print(sum(tmp)-sum(range(len(tmp))))
### BUGGY CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
dig = 0
while N:
    dig += N % 10
if N % dig == 0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = input()[:-1]
dig = 0
for c in N:
    dig += int(c)
if int(N) % dig == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N, M = list(map(int,input().split()))

LR = []

for i in range(M):
    LR.append(list(map(int,input().split())))

cnt = 0

for i in range(1,N+1):
    for lr in LR:
        if i < lr[0] or i > lr[1]:
            break
    else:
        cnt += 1

print(cnt)
    

### FIXED CODE ###

N, M = list(map(int,input().split()))

Nmin = 1
Nmax = N

for i in range(M):
    L, R = list(map(int,input().split()))
    Nmin = max(L,Nmin)
    Nmax = min(R,Nmax)

print(max(Nmax-Nmin+1,0))
### BUGGY CODE ###

N, M, K = map(int, input().split())
relate = [[0] * N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    relate[a][b] = 1
    relate[b][a] = 1
from collections import deque
# g : グラフ
# 例 [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8]]
# i : 始点
def bfs(s):

    #訪れたかどうか
    d = [False] * N
    #初期設定
    que = deque()
    que.append(relate[s])
    d[s] = True
    
    while que:
        p = que.popleft()
        for i, j in enumerate(p):
            if j == 0 or d[i]:
                continue
            else:
                d[i] = True
                que.append(relate[i])
    return d
import copy
d = [bfs(i) for i in range(N)]
block_d = copy.deepcopy(d)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    block_d[a][b] = 0
    block_d[b][a] = 0
for i in range(N):
    d[i][i] = 0
    block_d[i][i] = 0
    print(sum(block_d[i]) - sum(relate[i]))


### FIXED CODE ###

N, M, K = map(int, input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

d = UnionFind(N)
num_fri = [0] * N
for i in range(M):
    a, b = map(int, input().split())
    d.union(a - 1, b - 1)
    num_fri[a - 1] += 1
    num_fri[b - 1] += 1
#num = [d.size(i) for i in range(N)]
for i in range(K):
    a, b = map(int, input().split())
    if d.same(a - 1, b - 1):
        num_fri[a - 1] += 1
        num_fri[b - 1] += 1
for i in range(N):
    print((d.size(i) - 1) - num_fri[i], end=' ')
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,left,right):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            left = i - A[i]
            right = i + A[i] + 1
            if left < 0:
                left = 0
            if right > N:
                right = N
            B[left:right] += 1
        A = B
    return A


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    res = loop(N,K,A,0,0)

    print(*res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    return A


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    if K >= 43:
        M = 43
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

H,W = map(int, input().split())

b = []
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            b.append(i)
        i += 1

checked = []
t = 0
while len(checked) != W*H:
    t += 1
    tb = []
    for i in b:
        if i-W >= 0:
            tb.append(i-W)
        if i%W > 0:
            tb.append(i-1)
        if i%W < W-1:
            tb.append(i+1)
        if i+W < H*W:
            tb.append(i+W)
        checked.append(i)
    b = list(set(tb))
    checked = list(set(checked))
"""
    print("<<<< %d >>>>" %(t-1))
    for h in range(H):
        s = ""
        for w in range(W):
            if h*W+w in checked:
                s += "#"
            else:
                s += "."
        print(s)
"""
print(t-1)


### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)
### BUGGY CODE ###

n = int(input())
a = [0]
a.extend(list(map(int, input().split())))
max_a = max(a)
counter = [0]*(max_a+1)
combi = [0]*(max_a+1)
for num in a:
    counter[num] += 1
# print(counter)
for i in range(1, max_a+1):
    if counter[i] >= 2:
        for j in range(max_a+1):
            if i != j:
                combi[j] += counter[i]*(counter[i]-1)//2
            else:
                combi[j] += (counter[i]-1)*(counter[i]-2)//2
for j in range(1,n+1):
    print(combi[a[j]])

### FIXED CODE ###

n = int(input())
a = [0]
a.extend(list(map(int, input().split())))
max_a = max(a)
counter = [0]*(max_a+1)
combi_common = 0
for num in a:
    counter[num] += 1
for i in range(1, max_a+1):
    if counter[i] >= 2:
        combi_common += counter[i]*(counter[i]-1)//2
for j in range(1,n+1):
    cou = counter[a[j]]
    if cou >= 2:
        out = combi_common + ((cou-1)*(cou-2) - cou*(cou-1))//2
    else:
        out = combi_common
    print(out)
### BUGGY CODE ###

N = int(input())
n = N
L = []

print(str(N) + ':', end = '')

for i in range(2, n+1):
    while n%i == 0:
        n = n/i
        print(' ' + str(i), end = '')

print()

        #L.append(i)
        
#print(' '.join(map(str, L)))



### FIXED CODE ###

N = int(input())
n = N
m = N ** 0.5
L = []
i = 3

print(str(N) + ': ', end = '')

while n%2 == 0:
    n = n/2
    L.append(2)

while i <= m:
    while n%i == 0:
        n = n/i
        L.append(i)
    i += 2

if n not in L:
    L.append(int(n))  

if 1 in L:
    L.remove(1)

if len(L) == 0:
    L.append(N)

print(' '.join(map(str, L)))
### BUGGY CODE ###

black = "B"
white = "W"
s = ""

def main():
    global s
    s = [c for c in input()]
    ans = one()
    tmp = ans
    while tmp != 0:
        tmp = one()
        ans += tmp
    print(ans) 

def one():
    global s
    ans = 0
    for i in range(len(s) - 1):
        if s[i] == black and s[i+1] == white:
            s[i], s[i+1] = s[i+1], s[i]
            ans += 1
    return ans

main()


### FIXED CODE ###

black = "B"
white = "W"

def move_cost(s):
    a = 0
    count = 0
    for i, c in enumerate(s):
        if c == white:
            a += i
            count += 1
    count -= 1
    return a - count*(count+1)//2


print(move_cost(input()))
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for k in range(1, n+1):
    for j in range(1, k):
        for i in range(1, j):
            if s[i-1]!=s[j-1] and s[i-1]!=s[k-1] and s[j-1]!=s[k-1] and j-i!=k-j:
                ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R")*s.count("G")*s.count("B")

for j in range(1, n-1):
    for i in range(j):
        k = 2*j - i
        if k<n and s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
bc=[]
for i in range(m):
    b,c=map(int,input().split())
    bc.append([b,c])
bc.sort(key=lambda x:x[1],reverse=True)
for i in range(m):
    for j in range(min(bisect.bisect_left(a,bc[i][1]), bc[i][0])):
        a[j]=bc[i][1]
    a.sort()

print(sum(a))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append([1,a[i]])
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[1], reverse=True)
c=0
ans=0
for i in range(n+m):
    ans+=l[i][1]*l[i][0]
    c+=l[i][0]
    if c>n:
        ans-=l[i][1]*(c-n)
        break
print(ans)
### BUGGY CODE ###

s = input()

def make_num(x,y):
    return int(s[x:y])

ans=0
for i in range(len(s)-3):
    for j in range(i+4, len(s)+1):
        if make_num(i,j)%2019==0:
            ans+=1
print(ans)

### FIXED CODE ###

S = input()
count = 0
l = [0] * 2019 #mod2019 は0~2018まで
l[0] = 1
mod = 2019
tmp = 0

for i in range(1, len(S) + 1):
    tmp = (tmp + int(S[len(S) - i]) * pow(10, i - 1, mod)) % mod
    #print(tmp)
    l[tmp] += 1

#print(l)
for j in range(2019):
    if l[j] >= 2:
        count += l[j] * (l[j] - 1) // 2

print(count)
### BUGGY CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

S = input()
T = input()
ls = len(S)+1
lt = len(T)+1
'''
dp = dp2(0, ls, lt)

moji = [['']*ls for i in range(lt)]
#print(moji)
for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                moji[i][j] = moji[i][j-1]
print(moji)
print(moji[lt-1][ls-1])
'''
#dp = dp2(0, ls, lt)

dp = [[[0, ''] for j in range(ls)] for i in range(lt)]
#print(moji)
#print(dp)

for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j][0] = dp[i-1][j-1][0]+1
            dp[i][j][1] = dp[i-1][j-1][1] + S[j-1]
        else:
            if dp[i-1][j][0] >= dp[i][j-1][0]:
                dp[i][j][0] = dp[i-1][j][0]
                dp[i][j][1] = dp[i-1][j][1]
            else:
                dp[i][j][0] = dp[i][j-1][0]
                dp[i][j][1] = dp[i][j-1][1]
#print(dp)
print(dp[lt-1][ls-1][1])

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

S = input()
T = input()
ls = len(S)+1
lt = len(T)+1

dp = dp2(0, ls, lt)

#moji = [['']*ls for i in range(lt)]
#print(moji)
for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            #moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                #moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                #moji[i][j] = moji[i][j-1]
#print(moji)
#print(moji[lt-1][ls-1])
ans = ''
i = lt-1
j = ls-1
while i > 0 and j > 0:
    if dp[i][j] > dp[i-1][j-1] and S[j-1]==T[i-1]:
        ans += S[j-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

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

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

RGB = sorted([R, G, B], reverse=True)
max1 = N // RGB[0] 

count = 0
for r in range(max1+1):
    max2 = min([N-r, (N-r*RGB[0])//RGB[1]])
    for g in range(max2+1):
        Bb = N - (r*RGB[0] + g*RGB[1])
        if Bb >= 0 and Bb % RGB[2] == 0:
            count += 1
print(count)

### FIXED CODE ###

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

RGB = sorted([R, G, B], reverse=True)
max1 = N // RGB[0] 

count = 0
for r in range(max1+1):
    max2 = min([N-r, (N-r*RGB[0])//RGB[1]])
    for g in range(max2+1):
        if (N - (r*RGB[0] + g*RGB[1])) % RGB[2] == 0:
            count += 1
print(count)