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

def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch,cw)]
    q2=[]
    def mark(c,h,w):
        if 0<=h<H and 0<=w<W and s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        c,h,w=q1.pop()
        mark(c,h,w)
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2.clear()
    ans=s[dh][dw]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()


### FIXED CODE ###

def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        #if 0<=h<H and 0<=w<W and s[h][w]==-1:
        if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()
### BUGGY CODE ###

n = int(input())
arr = input().split()
def mult():
    if 0 in arr:
        print(0)
        return 0
    a = 1
    for i in arr:
        a = a * int(i)
    if a > 1000000000000000000:
        print(-1)
        return 0
    else: 
        print(a)
        return 0

mult()


### FIXED CODE ###

n = int(input())
arr = input().split()


def mult():
    if "0" in arr:
        return 0
    else:
        a = 1
        for i in arr:
            a = a * int(i)
            if a > 1000000000000000000:
                return -1
        return a

print(mult())
### BUGGY CODE ###

a=int(input())
b=list(map(int,input().split()))
ans=0
for i in range(a):
  for j in range(a):
    if b[i]%b[j]==0 and not i==j:
      break
    elif j==a-1:
      ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(sum(cnt_d[ai] == 1 for ai in a))
### BUGGY CODE ###

k=int(input())
s=input()
n=len(s)
mod=pow(10,9)+7

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] 
g2=[1,1] 
inverse=[0,1]
for i in range(2,n+k+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

import numpy as np
tmp=[pow(25,i,mod)*cmb(i+n-1,n-1,mod) for i in range(k+1)]
f=np.array(tmp)
g=np.zeros(k+1,int)
g[0]=1
for ki in range(1,k+1):
  g[ki]=f[ki]+26*g[ki-1]
  g[ki]%=mod
print(g[k])


### FIXED CODE ###

k=int(input())
s=input()
n=len(s)
mod=pow(10,9)+7

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] 
g2=[1,1] 
inverse=[0,1]
for i in range(2,n+k+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

f=[pow(25,i,mod)*cmb(i+n-1,n-1,mod) for i in range(k+1)]
g=[0]*(k+1)
g[0]=1
for ki in range(1,k+1):
  g[ki]=f[ki]+26*g[ki-1]
  g[ki]%=mod
print(g[k])
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		edge[match_dict[(x,y)]].append(match_dict[(z,w)])
		parent[match_dict[(z,w)]].append(match_dict[(x,y)])
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
if len(candidate) == 0:
	print(-1)
	exit()
day = 0
while True:
	new_candidate = []
	go_next = False
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			if all([finish[p] for p in parent[e]]):
				new_candidate.append(e)
				go_next = True
	day += 1
	candidate = new_candidate
	if not go_next:
		break

all_finished = all(finish)
if all_finished:
	print(day)
else:
	print(-1)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]


day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day if all(finish) else -1)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(0,m):
    b, c = map(int, input().split())
    for j in range(0,b):
        if a[j] < c:
            a[j] = c
        else:
            break
    if b != n:
        if a[b] < c:
            temp = []
            for j in range(0, n-b):
                if a[b] < c:
                    temp.append(a.pop(b))
                else:
                    break
            a = temp + a
print(sum(a))

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b_c_hash = {}
c_list = []
for i in range(0,m):
    b, c = map(int, input().split())
    if c in b_c_hash:
        b_c_hash[c] += b
    else:
        b_c_hash[c] = b
        c_list.append(c)
c_list.sort(reverse=True)
k = 0
flag = 0
for c in c_list:
    for i in range(0, b_c_hash[c]):
        if k == n:
            flag = 1
            break
        if a[k] < c:
            a[k] = c
            k += 1
        else:
            flag = 1
            break
    if flag == 1:
        break
print(sum(a))
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
m=0
for i in range(1,n+1):
    s=i/b
    num=math.floor(a*s)
    num-=a*math.floor(s)
    if num>=m:
        m=num
    
print(m)

### FIXED CODE ###

a,b,n=map(int,input().split())
if b>n:
    print(int(a*n/b)-a*int(n/b))
else:
    print(int(a*(b-1)/b)-a*int((b-1)/b))
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
A = [list(input()) for i in range(h)]

queue = deque([])
Distance = [[-1 for i in range(w)]for j in range(h)]

for i in range(h):
  for j in range(w):
    if A[i][j]=='#':
      queue.append([i,j])
      Distance[i][j] = 0

while queue:
    x,y = queue.popleft()
    if x!=0:
        if A[x-1][y] == '.' and Distance[x-1][y] == -1:
            queue.append([x-1,y])
            Distance[x-1][y] = Distance[x][y] + 1
    if x!=h-1:
        if A[x+1][y] == '.' and Distance[x+1][y] == -1:
            queue.append([x+1,y])
            Distance[x+1][y] = Distance[x][y] + 1
    if y!=0:
        if A[x][y-1] == '.' and Distance[x][y-1] == -1:
            queue.append([x,y-1])
            Distance[x][y-1] = Distance[x][y] + 1
    if y!=w-1:
        if A[x][y+1] == '.' and Distance[x][y+1] == -1:
            queue.append([x,y+1])
            Distance[x][y+1] = Distance[x][y] + 1

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans,Distance[i][j])

print(ans)

### FIXED CODE ###

def main():
    from collections import deque

    h,w = map(int,input().split())
    A = []
    for i in range(h):
        A += list(input())

    queue = deque([])
    Distance = [-1]*(h*w)

    for i in range(h):
        for j in range(w):
            if A[i*w+j]=='#':
                queue.append([i,j])
                Distance[i*w+j] = 0

    ans = 0

    while queue:
        x,y = queue.popleft()
        d = Distance[x*w+y]
        if x!=0 and Distance[(x-1)*w+y] == -1:
                queue.append([x-1,y])
                ans = Distance[(x-1)*w+y] = d+1
        if x!=h-1 and Distance[(x+1)*w+y] == -1:
                queue.append([x+1,y])
                ans = Distance[(x+1)*w+y] = d+1
        if y!=0 and Distance[x*w+y-1] == -1:
                queue.append([x,y-1])
                ans = Distance[x*w+y-1] = d+1
        if y!=w-1 and Distance[x*w+y+1] == -1:
                queue.append([x,y+1])
                ans = Distance[x*w+y+1] = d+1

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

def mv(nodes,mvinfo):
    dists=set()
    for node in nodes:
        dists=dists | set(mvinfo[node-1])
    return dists


N,M=[int(e) for e in input().split(' ')]

# 1step
mv1=[[] for n in range(N)]

for i in range(M):
    u,v=[int(e) for e in input().split(' ')]
    mv1[u-1].append(v)
S,T=[int(e) for e in input().split(' ')]

# 1step to 3steps
mv3=[]
for i in range(N):
    mv3.append(list(mv(mv(mv1[i],mv1),mv1)))


# search
reached=set()
for i in range(1,1+N):
    if i==1:
        dists=set(mv3[S-1])
    else:
        dists=mv(dists,mv3)

    if T in dists:
        break

else:
    i=-1
print(i)



### FIXED CODE ###

#import queue
from collections import deque
INF=-1

N,M=[int(e) for e in input().split(' ')]

to=[[] for _ in range(N)]

for i in range(M):
    u,v=[int(e) for e in input().split(' ')]
    to[u-1].append(v-1)
S,T=[int(e)-1 for e in input().split(' ')]

dist=[[INF for i in range(3)] for j in range(N)]

q=deque([])
q.append([S,0])

dist[S][0]=0

while(q):
    v,l=q.popleft()
    for v_to in to[v]:
        nl=(l+1)%3
        if dist[v_to][nl] != INF:
            continue
        dist[v_to][nl]=dist[v][l]+1
        q.append([v_to,nl])
ans=dist[T][0]
if ans == INF:
    ans = -1
else:
    ans=ans//3

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

import queue

N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]

node = [0] * (N+1)
nxt = [[] for _ in range(N+1)]

for ab in AB:
    a, b = ab[0], ab[1]
    nxt[a].append(b)
    nxt[b].append(a)

for px in PX:
    p,x = px[0], px[1]
    node[p] += x

visited = [False] * (N+1)
q = queue.Queue()
q.put(1)
visited[1] = True
while not q.empty():
    v = q.get()
    visited[v] = True
    for nv in nxt[v]:
        if not visited[nv]:
            node[nv] += node[v]
            q.put(nv)

for i in range(1, N+1):
    print(node[i], end=' ')
print()


### FIXED CODE ###

import sys
import queue

input = sys.stdin.readline

N, Q = map(int, input().split())

node = [0] * (N+1)
nxt = [[] for _ in range(N+1)]

for _ in range(N-1):
    a,b = map(int, input().split())
    nxt[a].append(b)
    nxt[b].append(a)

for _ in range(Q):
    p,x = map(int, input().split())
    node[p] += x

visited = [False] * (N+1)
q = queue.Queue()
q.put(1)
while not q.empty():
    v = q.get()
    visited[v] = True
    for nv in nxt[v]:
        if not visited[nv]:
            node[nv] += node[v]
            q.put(nv)

for i in range(1, N+1):
    print(node[i], end=' ')
print()
### BUGGY CODE ###

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

h,w = map(int,input().rstrip().split())
sy,sx = map(int,input().rstrip().split())
gy,gx = map(int,input().rstrip().split())
a = [list(input().rstrip())for _ in range(h)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

dx=[1,0,-1,0,  2,1,0,-1,-2,  2,1,-1,-2,  2,-2,  2,1,-1,-2,  2,1,0,-1,-2]
dy=[0,1,0,-1,  2,2,2,2,2,  1,1,1,1,  0,0,  -1,-1,-1,-1,  -2,-2,-2,-2,-2]
m = len(dx)

def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 #warp回数
    goal = False

    while q:
        p = q.pop()
        
        #print((p[0],p[1]),d[p[1]][p[0]])
        if p[0] == gx and p[1] == gy:
            goal = True

        for i in range(m):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if i < 4:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]]
            else:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]] + 1

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())

### FIXED CODE ###

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

h,w = map(int,input().rstrip().split())
sy,sx = map(int,input().rstrip().split())
gy,gx = map(int,input().rstrip().split())
a = [list(input().rstrip())for _ in range(h)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 #warp回数
    goal = False
    local_area = deque([])

    while q:
        p = q.popleft()
        local_area.append((p[0],p[1]))
        if p[0] == gx and p[1] == gy:
            goal = True
            break

        for i in range(4):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[ny][nx] == float("inf"):
                q.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]]
        if len(q) == 0 and goal == False:
            while local_area:
                p = local_area.popleft()
                for i in range(-2,3):
                    for j in range(-2,3):
                        nx = p[0]+i 
                        ny = p[1]+j
                        if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[ny][nx] == float("inf"):
                            q.append((nx,ny))
                            d[ny][nx] = d[p[1]][p[0]] + 1                        

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())
### BUGGY CODE ###

#python 3
n,m = map(int,input().split())
keys = []
for i in range(m):
	a,b = map(int,input().split())
	c = map(int,input().split())
	mask = 0
	for x in c:
		mask += 2**(x-1)
	keys.append((mask,a))
#print(keys)
dp = []
M = 2**n
for i in range(m+1):
	dp.append([10**10]*(M))

for i in range(m+1):
	dp[i][0] = 0
	
for i in range(m):
	key = keys[i]
	for j in range(M):
		dp[i+1][j|key[0]] = min(dp[i+1][j|key[0]], dp[i][j]+key[1])
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])

if dp[m][M-1] > 10**9:
	print(-1)
else:
	print(dp[m][M-1])

### FIXED CODE ###

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

M = 1<<n
dp = [10**9]*M
dp[0] = 0
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 1<<(x-1)
	for j in xrange(M):
		dp[j|mask] = min(dp[j|mask], dp[j]+a)
	#print dp
 
if dp[M-1] >= 10**9:
	print -1
else:
	print dp[M-1]
### BUGGY CODE ###

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

S = list(map(int,input().split()))
T = list(map(int,input().split()))

sm = [[0] * (M+1) for _ in range(N+1)]

for i in range(1,N+1) :
    for j in range(1,M+1) :
        sm[i][j] = sm[i-1][j] + sm[i][j-1]
        if S[i-1] == T[j-1] :
            sm[i][j] += 1
        else :
            sm[i][j] -= sm[i-1][j-1]

ans = (sm[-1][-1] + 1) % (10**9 + 7)

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (M + 1) for _ in range(N + 1)]  # dp[s][t]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        v = dp[i - 1][j] + dp[i][j - 1]
        if s == t:
            v += 1
        else:
            v -= dp[i - 1][j - 1]
        dp[i][j] = v % MOD

print((dp[-1][-1] + 1) % MOD)
### BUGGY CODE ###

from fractions import Fraction

N, K = [int(a) for a in input().split()]

prob = 0

for i in range(1, N+1):
    j = i
    num_omote = 0
    while j < K:
        j *= 2
        num_omote += 1
    prob += Fraction(1, N) * Fraction(1, 2)**num_omote

print(float(prob))
    


### FIXED CODE ###

N, K = [int(a) for a in input().split()]

prob = 0

for i in range(1, N+1):
    j = i
    inverse_p = N
    while j < K:
        j *= 2
        inverse_p *= 2
    prob += 1/ inverse_p

print(prob)
### BUGGY CODE ###

N, K = map(int, input().split())
*H, = map(int, input().split())
INF = 10**12
dp = {i: INF for i in range(N+1)}
dp[0] = 0
dp[1] = abs(H[1] - H[0])
for i in range(2, N):
    dp[i] = min([dp[i-j] + abs(H[i] - H[i-j]) for j in range(1, min(i, K)+1)])
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
*H, = map(int, input().split())
INF = 10**12
dp = [INF]*N
dp[0] = 0
dp[1] = abs(H[1] - H[0])
for i in range(2, N):
    beg = min(i, K)
    h_now = H[i]
    dp[i] = min([d + abs(h_now - h) for d, h in zip(dp[i-beg:i], H[i-beg:i])])
print(dp[N-1])
### BUGGY CODE ###

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


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    while ds[x] != x:
        x = ds[x]

    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False


def main():
    N, M = map(int, input().split())
    ds = {}

    for i in range(N):
        dsMakeSet(ds, i+1)

    for i in range(M):
        X,Y,Z = map(int, input().split())
        dsUnion(ds, X, Y)
        
    print(len(set(dsFind(ds, x) for x in ds)))
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    x0 = x
    while ds[x] != x:
        x = ds[x]

    ds[x0] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False


def main():
    N, M = map(int, input().split())
    ds = {}

    for i in range(N):
        dsMakeSet(ds, i+1)

    n = 0
    for i in range(M):
        X,Y,Z = map(int, input().split())
        if dsUnion(ds, X, Y):
            n += 1
        
    print(N - n)
        

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

N,X,Y = map(int,input().split())
from collections import defaultdict as ddict
G = ddict(list)
for n in range(1,N):
    G[n].append(n+1)
    G[n+1].append(n)
G[X].append(Y)
G[Y].append(X)
def check(A):
    ret = True
    for a in A:
        if a == 0:
            ret = False
    return ret
from collections import deque
matrix = [[0 for n in range(0,N+1)] for nn in range(0,N+1)]
for i in range(1,N+1):
    Q = deque([i])
    pre_matrix = [0 for i in range(0,N+1)]
    while Q:
        q = Q.popleft()
        for c in G[q]:
            if matrix[i][c] == 0 or matrix[i][c] > matrix[i][q]+1:
                matrix[i][c] = matrix[i][q]+1
                matrix[c][i] = matrix[i][q]+1
            Q.append(c)
        if check(matrix[i][1:]):
            break
ans = ddict(int)
for i in range(1,N+1):
    for ii in range(i+1,N+1):
        ans[matrix[i][ii]] += 1
for n in range(1,N):
    print(ans[n])

### FIXED CODE ###

N,X,Y = map(int,input().split())
from collections import defaultdict as ddict
ans = ddict(int)
for n in range(N):
    for i in range(n+1,N):
        s = i+1
        d = n+1
        p1 = abs(s-d)
        p2 = abs(s-X)+abs(d-Y)+1
        p3 = abs(s-Y)+abs(d-X)+1
        ans[min(p1,p2,p3)] += 1
for n in range(1,N):
    print(ans[n])
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
s = [0 for i in range(Q)]
for i in range(Q):
    l,r = map(int,input().split())
    j = l-1
    for j in range(l-1,r-1):
        if S[j] is "A" and S[j+1] is "C":
            s[i] += 1
for i in range(Q):
    print(s[i])

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
a =[0] * N
for i in range(N-1):
    if S[i] == "A" and S[i + 1] == "C":
        a[i + 1] = a[i] + 1
    else:
        a[i + 1] = a[i]
l, r = 0, 0
b = [0] * Q
for i in range(Q):
    l, r = map(int, input().split())
    b[i] = a[r-1] - a[l-1]
for i in range(Q):
    print(b[i])
### BUGGY CODE ###

l,r = map(int, input().split())
# l=2020
# r=2040

mini=l*r%2019
for i in range(l,r+1):
    for j in range(i+1,r+1):
        if(i*j%2019<mini):
            mini=i*j%2019
print(mini)

### FIXED CODE ###

l,r = map(int, input().split())
# l=10000000
# r=100000000

mini=l*r%2019
for i in range(l,r+1):
    for j in range(i+1,r+1):
        if(j%2019==0):
            mini=0
            break;
        
        if(i*j%2019<mini):
            mini=i*j%2019
    if mini==0:
        break;
print(mini)
### BUGGY CODE ###

X=int(input())

count=1

while(count==1):
    for n in range(2,X):
        if (X%n==0):
            X+=1
            break
        if (n*n>X):
            count=0
print(X)


### FIXED CODE ###

import math
X=int(input())

count=1

if X==2:
    count=0

while(count==1):
    for n in range(2,X):
        if (X%n==0):
            X+=1
            break
        if (n>math.sqrt(X)):
            count=0
            break
print(X)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    print(A.count(i+1))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
L = collections.Counter(A)
for i in range(N):
    print(L[i+1])
### BUGGY CODE ###

# Aizu Problem 0270: Modular Query

import sys, math, os, datetime

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


N, Q = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
for q in range(Q):
    m = int(input())
    print(max([a % m for a in A]))

### FIXED CODE ###

N,Q=map(int,raw_input().split())
c=map(int,raw_input().split())
 
mxc=max(c)
p=[0]*(mxc+1)
for i in c:
    p[i]=1
     
l=[0]*(mxc+1)
num=0
for i in range(mxc+1):
    l[i]=num
    if p[i]:
        num=i
         
for i in range(Q):
    q=int(raw_input())
    sp=mxc
    ans=0
    while 1:
        r=sp%q
        ans=max(ans,r)
        if sp-r<=0:break
        sp=l[sp-r]
    print ans
### BUGGY CODE ###

n = int(input())
arr = list(map(int,input().split()))
res = 1
for i in range(n):
  res = res*arr[i]
inf = int(1e18)
if(res > inf):
  print(-1)
else:
  print(res)

### FIXED CODE ###

n = int(input())
arr = list(map(int,input().split()))
res = 1
flag = 1
arr.sort()
inf = int(1e18)
for i in range(n):
  res = res*arr[i]
  if(res > inf):
    flag = 0
    break
 
if(flag == 0):
  print(-1)
else:
  print(res)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
from collections import Counter
MOD = 2019

def main():
    S = readline().rstrip()
    N = len(S)
    T = [0] * (N+1)
    for i in range(N-1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * 10**(N-1-i)) % MOD
    
    c = Counter(T)
    ans = 0
    for k, v in c.items():
        ans += (v * (v-1)) // 2
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
from collections import Counter
MOD = 2019

def main():
    S = list(map(int, list(readline().rstrip())))
    N = len(S)
    T = [0] * (N+1)
    e = 1
    for i in range(N-1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * e) % MOD
        e = e * 10 % MOD
    
    T = [t % MOD for t in T]
    c = Counter(T)
    ans = 0
    for k, v in c.items():
        ans += (v * (v-1)) // 2
    print(ans)


if __name__ == '__main__':
    main()