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

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

dist = [[-1]*W for _ in range(H)]

black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

dist = [[-1]*W for _ in range(H)]

black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

K = int(input())
if K%2 == 0 or K%5 == 0:
    print(-1)
    exit()
temp = 7
for i in range(1,10**6):
    if temp%K == 0:
        print(i)
        exit()
    temp += 7*pow(10,i)%K

print(-1)
exit()

### FIXED CODE ###

K = int(input())
if K%2 == 0 or K%5 == 0:
    print(-1)
    exit()
temp = 7%K
for i in range(1,10**6):
    if temp%K == 0:
        print(i)
        exit()
    temp += 7*pow(10,i,K)

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

import sys
from collections import deque
N, M = map(int, input().split())
Edge = [[] for _ in range(N+1)]
comp = set()
for _ in range(M):
    p, q, c = map(int, sys.stdin.readline().split())
    Edge[p].append((q, c))
    Edge[q].append((p, c))
    comp.add(c)
dist = {(1, 0): 0}
Q = deque()
Q.append((1, 0))
visited = set()
while Q:
    vn, cp = Q.pop()
    if (vn, cp) in visited:
        continue
    visited.add((vn, cp))
    for vf, cf in Edge[vn]:
        if (vf, cp) in visited:
            continue
        if cp == cf:
            dist[(vf, cf)] = min(dist.get((vf, cf), 10**9), dist.get((vn, cp), 10**9))
            Q.append((vf, cf))
        else:
            dist[(vf, cf)] = min(dist.get((vf, cf), 10**9), 1 + dist.get((vn, cp), 10**9))
            Q.appendleft((vf, cf))
L = [dist.get((N, c), 10**9) for c in comp]
if not L or min(L) == 10**9:
    print(-1)
else:
    print(min(L))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
inf = 10**9+7
def dijkstra(N, s, Edge):    
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dn + df < dist[vf]:
                dist[vf] = dn + df
                hp(Q, (dn + df,vf))
    return dist

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C


N, M = map(int, readline().split())

Edge = []
VS = set(range(N))
geta = 20
Edge = [tuple(map(int, readline().split())) for _ in range(M)]
for a, b, c in Edge:
    a -= 1
    b -= 1
    VS |= {(c<<geta) | a, (c<<geta) | b}
   
_, Cv = compress(list(VS))

Vnum = len(Cv)

nEdge = [[] for _ in range(Vnum)]

for a, b, c in Edge:
    a -= 1
    b -= 1
    ca = Cv[(c<<geta) | a]
    cb = Cv[(c<<geta) | b]
    nEdge[ca].append((0, cb))
    nEdge[cb].append((0, ca))
    nEdge[a].append((1, ca))
    nEdge[ca].append((0, a))
    nEdge[b].append((1, cb))
    nEdge[cb].append((0, b))

dist = dijkstra(Vnum, 0, nEdge)
if dist[N-1] >= inf:
    dist[N-1] = -1
print(dist[N-1])
### BUGGY CODE ###

from collections import deque


def main():
    input()  # n
    friendliness = [int(x) for x in input().split()]
    friendliness.sort()
    friendliness = deque(friendliness)
    edges = []
    popped1 = friendliness.pop()
    popped2 = friendliness.pop()
    edges.append((popped1, popped2))
    edges.append((popped2, popped1))
    ans = popped1
    while friendliness:
        popped = friendliness.pop()
        tmp_data = (-1, -1)  # max_comfort, edge_index
        for i, edge in enumerate(edges):
            x = min(edge)
            if x > tmp_data[0]:
                tmp_data = (x, i)
        ans += tmp_data[0]
        edge_tmp = edges[tmp_data[1]]
        edges[tmp_data[1]] = (edge_tmp[0], popped)
        edges.append((popped, edge_tmp[1]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    n = int(input())  # n
    friendliness = [int(x) for x in input().split()]
    friendliness.sort()
    friendliness = deque(friendliness)
    edges = deque()
    popped = friendliness.pop()
    edges.append(popped)
    ans = 0
    counter = 0
    while friendliness:
        ans += edges.popleft()
        counter += 1
        popped = friendliness.pop()
        edges.append(popped)
        edges.append(popped)
    print(ans)


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

from fractions import gcd
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(p, q, a, n, l=1):

    #if n==1:
    #    #print(p, q, a, n, l, 1 if p==1 and q<=a and q>=l else 0)
    #    return 1 if p==1 and q<=a and q>=l else 0
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = l if p==0 else max(l, int(q/p))
    while n*q >= denom*p and denom <= a:  #n/denom >= p/q:
        p_, q_ = p*denom-q, q*denom
        if p_ <= 0:
            denom += 1
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)

        denom += 1
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))



### FIXED CODE ###

from fractions import gcd

def solve(p, q, a, n, l=1):
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = max(l, q//p)
    p_denom = denom*p
    while n*q >= p_denom and denom <= a:  #n/denom >= p/q:
        p_, q_ = p_denom-q, q*denom
        if p_ <= 0:
            denom += 1
            p_denom += p
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)
        denom += 1
        p_denom += p
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))
### BUGGY CODE ###

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

while n <= m:
    if m % n == 0:
        break
    n += 1

print(m//n)

### FIXED CODE ###

import math
n,m = map(int,input().split())	
r = m
k = 0
a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
for i in range(len(a)):
    if m%a[i] == 0 and m >= a[i]:
        r = m//a[i]
        break
if r == m and m >= 199:
    r = m//199
if n > r:
    k = 1

while n <= r :
    if m % n == 0:
        break
    n += 1
if n == r + 1 or k == 1:
    print(1)
else:
    print(m//n)
### BUGGY CODE ###

import heapq

def main():
    q=int(input())
    res = 0

    x=list(map(int,input().split()))
    a=x[1]
    res += x[2]
    asmall = [a*-1]
    alarge = [a]
    heapq.heapify(asmall)
    heapq.heapify(alarge)

    r1 = a
    r2 = a

    for _ in range(q-1):
        x=list(map(int,input().split()))
        if x[0] ==1:
            a = x[1]
            res += x[2]
            if r1 <= a and a <= r2: pass
            else: res += min(abs(a-r1),abs(a-r2))
            mid1 = asmall[0] * -1
            if mid1 > a:
                heapq.heappush(alarge,heapq.heappop(asmall) * -1)
                heapq.heappush(asmall,-a)
                heapq.heappush(asmall,-a)
            else:
                mid2 = alarge[0]
                if mid2 >= a:
                    heapq.heappush(asmall,-a)
                    heapq.heappush(alarge,a)
                else:
                    heapq.heappush(asmall,heapq.heappop(alarge) * -1)
                    heapq.heappush(alarge,a)
                    heapq.heappush(alarge,a)
            r1 = asmall[0] * -1
            r2 = alarge[0]
        if x[0] == 2:
            print(str(r1)+" "+str(res))

main()

### FIXED CODE ###

import heapq
import sys 
input = sys.stdin.readline

def main():
    q=int(input())
    res = 0

    x=list(map(int,input().split()))
    a=x[1]
    res += x[2]
    asmall = [a*-1]
    alarge = [a]
    heapq.heapify(asmall)
    heapq.heapify(alarge)

    r1 = a
    r2 = a

    for _ in range(q-1):
        x=list(map(int,input().split()))
        if x[0] ==1:
            a = x[1]
            res += x[2]
            if r1 <= a and a <= r2: pass
            else: res += min(abs(a-r1),abs(a-r2))
            mid1 = asmall[0] * -1
            if mid1 > a:
                heapq.heappush(alarge,heapq.heappop(asmall) * -1)
                heapq.heappush(asmall,-a)
                heapq.heappush(asmall,-a)
            else:
                mid2 = alarge[0]
                if mid2 >= a:
                    heapq.heappush(asmall,-a)
                    heapq.heappush(alarge,a)
                else:
                    heapq.heappush(asmall,heapq.heappop(alarge) * -1)
                    heapq.heappush(alarge,a)
                    heapq.heappush(alarge,a)
            r1 = asmall[0] * -1
            r2 = alarge[0]
        if x[0] == 2:
            print(str(r1)+" "+str(res))

main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
print(ans if ans <= 10**18 else '-1')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [i for i in a if i != 1]
ans = 1
if len(b) < 100:
    for i in range(len(b)):
        ans *= b[i]
else:
    ans = 10**18+1
if 0 in b:
    ans = 0
print(ans if ans <= 10**18 else '-1')
### BUGGY CODE ###

from collections import Counter

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= (n-i)
    ret //= i+1
  return ret    

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

ans = 0
if p == 2:
  for i in range(n):
    if int(s[i])%2 == 0:
      ans += (i+1)
      
elif p == 5:
  for i in range(n):
    if int(s[i])%5 == 0:
      ans += (i+1)
      
else:      
  mods = [0]*(n+1)
  t = ''
  for i in range(n):
    t = s[-i-1] + t
    mods[i] = int(t)%p    
  c = Counter(mods)
  for k,v in c.items():
    if v > 1:
      ans += nCr(v,2)

print(ans)      

### FIXED CODE ###

from collections import Counter

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

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += (i+1)

else:      
  mods = [0]*p
  mods[0] = 1
  m = 0
  d = 1  
  for i in range(n):
    m = (m + int(s[-i-1])*d) % p
    d = (d * 10) % p    
    mods[m] += 1
  
  for i in range(p):
    ans += mods[i]*(mods[i]-1)//2

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

from math import floor
n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, floor(p**(1/n))+2):
        if p % i**n ==0:
            res = i
    print(res)


### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, round(p**(1/n))+1):
        if p % i**n ==0:
            res = i
    print(res)
### BUGGY CODE ###

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

ans = int(0)
x = int(N//R)
y = int(N//G)

for i in range(x+1):
    for j in range(y+1) :
        s = int(N-R*i-G*j)
        if s%B==0 and s>=0 : ans +=1

print(ans)

### FIXED CODE ###

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

ans = int(0)
x = int(N//R)

for i in range(x+1):
    t = N-i*R
    y = int(t//G)
    for j in range(y+1) :
        s = int(t-G*j)
        if s%B==0 : ans +=1

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

from sys import stdin
from itertools import permutations
def main():
    N,M,R = map(int,stdin.readline().split())
    r = list(map(int,stdin.readline().split()))
    r = tuple(map(lambda x: x-1,r))
    dist = [[2**60]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = map(int,stdin.readline().split())
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C
    for i in range(N):
        dist[i][i] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
    dist = tuple(map(lambda x: tuple(x),dist))
    ans = 2**60
    for t in tuple(permutations(r,R)):
        tmp = 0
        for i in range(R-1):
            tmp += dist[t[i]][t[i+1]] 
        ans = min(ans,tmp)
    
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
from itertools import permutations
def main():
    N,M,R = map(int,stdin.readline().split())
    r = list(map(int,stdin.readline().split()))
    r = tuple(map(lambda x: x-1,r))
    dist = [[2**60]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = map(int,stdin.readline().split())
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C
    for i in range(N):
        dist[i][i] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
    dist = tuple(map(lambda x: tuple(x),dist))
    ans = 2**60
    for t in tuple(permutations(r,R)):
        tmp = 0
        for i in range(R-1):
            tmp += dist[t[i]][t[i+1]] 
        ans = min(ans,tmp)
    
    print(ans)

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

import sys

sys.setrecursionlimit(500000)


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

e_list = [[] for i in range(N)]

for i in range(M):
    x,y = list(map(int,input().split()))
    x,y = x-1,y-1
    e_list[x].append(y)

from functools import lru_cache

@lru_cache(maxsize=N*10)
def DFS(v):
    if len(e_list[v])==0:
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    if res>ans:
        ans = res
print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(500000)


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

e_list = [[] for i in range(N)]

for i in range(M):
    x,y = list(map(int,input().split()))
    x,y = x-1,y-1
    e_list[x].append(y)

memo = [-1]*N

def DFS(v):
    if memo[v]!=-1:
        return memo[v]
    if len(e_list[v])==0:
        memo[v] = 0
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    memo[v] = res
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    if res>ans:
        ans = res
print(ans)
### BUGGY CODE ###

import sys
N = int(input())
for i in range(1,3501):
  for j in range(max(i-1,1),3501):
    if (4*i*j - N*i -N*j) != 0:
      w = (N*i*j)/(4*i*j - N*i -N*j)
      if w > 0 and w.is_integer():
        print(i,j,int(w))
        sys.exit()

### FIXED CODE ###

import sys
N = int(input())
for i in range(1,3501):
  for j in range(max(i-1,1),3501):
    if (4*i*j - N*i -N*j) != 0:
      w = (N*i*j)/(4*i*j - N*i -N*j)
      if w > 0 and w.is_integer():
        print(i,j,int(w))
        sys.exit()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
A=[]
for i in range(h):
    a_list=list(map(int,input().split()))
    A.append(a_list)
B=[]
for i in range(h):
    b_list=list(map(int,input().split()))
    B.append(b_list)
dp=[set() for i in range(w)]
dp[0].add(0)
for i in range(h):
    for j in range(w):
        s=set()
        for x in dp[j]:
            y=abs(x+(A[i][j]-B[i][j]))
            z=abs(x+(B[i][j]-A[i][j]))
            s.add(y)
            s.add(z)
        dp[j]=s
        if j<w-1:
            dp[j+1]=s|dp[j+1]
ans=min(dp[w-1])
print(ans)        
    


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
A=[]
for i in range(h):
    a_list=list(map(int,input().split()))
    A.append(a_list)
B=[]
for i in range(h):
    b_list=list(map(int,input().split()))
    B.append(b_list)
dp=[]
for i in range(w):
    sub_list=[False]*12802
    dp.append(sub_list)
dp[0][0]=True
for i in range(h):
    for j in range(w):
        c=A[i][j]-B[i][j]
        l=[False]*12802
        for x in range(12802):
            if dp[j][x]:
                l[abs(x+c)]=True
                l[abs(x-c)]=True
                if j<w-1:
                    dp[j+1][abs(x+c)]=True
                    dp[j+1][abs(x-c)]=True
        dp[j]=l
ans=20000
for x in range(12802):
    if dp[w-1][x]:
        ans=min(ans,x)
print(ans)
### BUGGY CODE ###

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

ans = 0
min_v = N
for i in range(0, N):
    if P[i] > min_v:
        continue
    for j in range(0, i+1):
        if P[i] > P[j]:
            break

        if i == j:
            ans += 1
            min_v = P[i]

print (ans)




### FIXED CODE ###

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

ans = 0
min_v = P[0]

for i in range(0, N):
    if P[i] <= min_v:
        ans += 1
        min_v = P[i]

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

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    x, y, z = count[1], count[2], count[3]
    
    memo = dict()
    
    def dp(a, b, c):
        if (a, b, c) in memo:
            return memo[(a, b, c)]
        
        if a == b == c == 0:
            return 0
        
        if a < 0 or b < 0 or c < 0:
            return 0
        
        if a + b + c > N:
            return 0
        
        res = N
        res += a*dp(a-1, b, c)
        res += b*dp(a+1, b-1, c)
        res += c*dp(a, b+1, c-1)
        res /= a+b+c
        
        memo[(a, b, c)] = res
        return res
    
    ans = dp(x, y, z)
    
    print(ans)
        
        
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

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


N = int(input())
memo = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

def dp(a, b, c):
    if a == b == c == 0: return 0
    if memo[a][b][c] != -1:
        return memo[a][b][c]
    
    res = N
    if a > 0: res += a*dp(a-1, b, c)
    if b > 0: res += b*dp(a+1, b-1, c)
    if c > 0: res += c*dp(a, b+1, c-1)
    res /= a+b+c
    
    memo[a][b][c] = res
    return res

def main():
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    x, y, z = count[1], count[2], count[3]

    
    ans = dp(x, y, z)
    
    print(ans)
        

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

import heapq

N, M = tuple(map(int, input().split()))
A = list(map(int, input().split()))
B, C = [], []
for _ in range(M):
    b, c = tuple(map(int, input().split()))
    B.append(b)
    C.append(c)

heapq.heapify(A)
for b, c in zip(B, C):
    for _ in range(b):
        min_val = A[0]
        if min_val < c:
            A[0] = c
            heapq.heapify(A)
        else:
            break
print(sum(A))

### FIXED CODE ###

import heapq

N, M = tuple(map(int, input().split()))
A = list(map(int, input().split()))
BC = []
for _ in range(M):
    BC.append(tuple(map(int, input().split())))

BC.sort(key=lambda x: x[1], reverse=True)
heapq.heapify(A)
for (b, c) in BC:
    for _ in range(b):
        min_val = A[0]
        if min_val < c:
            heapq.heappop(A)
            heapq.heappush(A, c)
        else:
            break
print(sum(A))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
g = []
ans = 0
for j in range(60):
    d = 0
    for i in range(n):
        d += a[i]&1
        a[i] >>= 1
    g.append(d)
for i in range(60):
    ans += g[i]*(n-g[i])*(pow(2,i,1000000007))
    ans = ans % (1000000007)
print(ans%(1000000007))

### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1) # 自分がnp.sumを利用したがどうしても正解になれなかった。なぜ？
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)
### BUGGY CODE ###

from collections import defaultdict

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

for i in range((N//G)+1):
    for j in range((N//B)+1):
        d[i*G+j*B] += 1

ans = 0
for i in range((N//R)+1):
    ans += d[N-(R*i)]
print(ans)

### FIXED CODE ###

from collections import defaultdict

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

for i in range((N//G)+1):
    for j in range((N//B)+1):
        d[i*G+j*B] += 1

ans = 0
for i in range((N//R)+1):
    ans += d[N-(R*i)]
print(ans)
### BUGGY CODE ###

N, k = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
isPossible = False

K = [k]

for a in A:
	if a > k:
		break
	if k - a in A:
		isPossible = True
		break
	elif a in K:
		isPossible = True
		break
	else:
		K.append(k-a)


if k > max(A):
	isPossible = False

if isPossible:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

### FIXED CODE ###

from fractions import gcd
N, K = map(int, input().split())
A = list(map(int, input().split()))
if K in A:
  print('POSSIBLE')
elif K > max(A):
  print('IMPOSSIBLE')
else:
  A_gcd = A[0]
  for i in range(1, N):
    A_gcd = gcd(A_gcd, A[i])

  if K % A_gcd == 0:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

s = input()
n = len(s)

li = [int(s[-1])]

for i in range(n-1):
    t = int(s[-i-2])
    li.append((li[-1] + t * 10 ** (i+1)) % 2019)

dict1 = {}
for i in li:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1

ans = 0

for v in dict1.values():
    ans += v * (v-1) // 2

if 0 in dict1:
    ans += dict1[0]

print(ans)


### FIXED CODE ###

s = input()
n = len(s)

li = [0] * n
li[0] = int(s[-1])

for i in range(n-1):
    t = int(s[-i-2])
    li[i+1] = (li[i] + t * pow(10, i+1, 2019)) % 2019

dict1 = {}
for i in li:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1

ans = 0

for v in dict1.values():
    ans += v * (v-1) // 2

if 0 in dict1:
    ans += dict1[0]

print(ans)