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

import math

def comb(n, k, m):
  nf  = math.factorial(n)   % m
  kf  = math.factorial(k)   % m
  nkf = math.factorial(n-k) % m
  return nf * pow_mod(kf*nkf%m, m-2, m) % m

def pow_mod(a, b, m):
  if b == 0:
    return 1
  elif b%2 == 0:
    d = pow_mod(a, b//2, m) % m
    return d * d % m 
  else:
    d = pow_mod(a, (b-1)//2, m)
    return  d * d * a % m

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]

ans = 0
mod = 10**9 + 7

if (x + y) % 3 != 0:
  ans = 0
else:
  n = (x + y) // 3
  if min(x, y) < n:
    ans = 0
  elif min(x,y) == n:
    ans = 1
  else:
    r = min(x, y) - n
    ans = comb(n, r, mod)

print(ans)

### FIXED CODE ###

import math

def comb(n, k, m):
  f = [1] * (n+1)
  for i in range(1, n+1):
    f[i] = f[i-1] * i % m
  return f[n] * pow_mod(f[k]*f[n-k]%m, m-2, m) % m

def pow_mod(a, b, m):
  if b == 0:
    return 1
  elif b%2 == 0:
    d = pow_mod(a, b//2, m) % m
    return d * d % m 
  else:
    d = pow_mod(a, (b-1)//2, m)
    return  d * d * a % m

tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]

ans = 0
mod = 10**9 + 7

if (x + y) % 3 != 0:
  ans = 0
else:
  n = (x + y) // 3
  if min(x, y) < n:
    ans = 0
  elif min(x,y) == n:
    ans = 1
  else:
    r = min(x, y) - n
    ans = comb(n, r, mod)

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

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 2
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
m = [0] * MAX
t = set()
for i in range(n):
  m[a[i]] += 1
  if m[a[i]] == 1:
    t.add(a[i])
  elif m[a[i]] == 2:
    t.discard(a[i])
#print(m[:30])
mx = max(a)
ans = 0
tlen = len(t)
for idx in range(tlen):
  i = t.pop()
  #if m[i] != 1:
    #continue
  divs = make_divisors(i)
  flg = True
  #print('i : ', i)
  #print(divs)
  for j in range(len(divs)):
    div = divs[j]
    if div == i:
      continue
    
    if m[div] > 0:
      flg = False
      break
  if flg:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

sieve = [True] * MAX
counts = [0] * MAX
a.sort()
ans = 0
sieve[0] = False
sieve[1] = False
for i in range(n):
  counts[a[i]] += 1
  if not sieve[a[i]]:
    continue
  for j in range(a[i]*2, MAX, a[i]):
    sieve[j] = False
  if counts[a[i]] == 1:
    ans += 1
  elif counts[a[i]] == 2:
    ans -= 1
    
print(ans)
### BUGGY CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
#template
#issueから始める
N = int(input())
L = inputlist()
L.sort()
ans = 0
from bisect import bisect_left
for i in range(N-2):
    for j in range(i+1,N-1):
        lia = L[j+1:]
        indexa = bisect_left(lia,L[i]+L[j])
        ans += indexa
print(ans)


### FIXED CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
N = int(input())
L = inputlist()
L.sort()
ans = 0
from bisect import bisect_left
for i in range(N-2):
    for j in range(i+1,N-1):
        lia = L[j+1:]
        indexa = bisect_left(lia,L[i]+L[j])
        ans += indexa
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(map(int, list(input())))
ans = 0
for i in range(1000):
    c = 0
    for j in s:
        if i % 10 == j:
            if c == 2:
                ans += 1
                break
            c += 1
            i //= 10
print(ans)

### FIXED CODE ###

n = int(input())
s = list(map(int, list(input())))

ans = 0

def dfs(depth, id):
    global ans
    for i in range(10):
        for j in range(id, n):
            if i == s[j]:
                if depth < 2:
                    dfs(depth + 1, j + 1)
                else:
                    ans += 1
                break

dfs(0, 0)
print(ans)
### BUGGY CODE ###

s=raw_input()
l=len(s)

str=""
i=0
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		str+="A"
		i+=1
		cnt+=1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		str+="D"
		i+=2
		ans+=cnt
	else:
		str+="X"
		i+=1
		cnt=0


print ans

### FIXED CODE ###

s=raw_input()
l=len(s)

i=0
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		i+=1
		cnt+=1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		i+=2
		ans+=cnt
	else:
		i+=1
		cnt=0


print ans
### BUGGY CODE ###

A,B = (int(i) for i in input().split())

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

print(ans)


### FIXED CODE ###

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

ans=0

for i in range(4):
    if (A+i)%4==0:
        break
    ans=ans^(A+i)
for i in range(B-3,B+1):
    if i%4==3:
        end=i+1
        break

for i in range(end,B+1):
    ans=ans^i

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    n, k = ZZ()
    A = ZZ() + [0]

    for _ in range(k):
        nA = [0] * (n+1)
        for i in range(n):
            nA[max(0, i-A[i])] += 1
            nA[min(n, i+1+A[i])] -= 1
        for i in range(1, n+1): nA[i] += nA[i-1]
        A = nA
    print(*A[:-1])

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    n, k = ZZ()
    A = ZZ()+[0]

    for _ in range(k):
        if all([A[i] >= n for i in range(n)]): break
        nA = [0] * (n+1)
        for i in range(n):
            nA[max(0, i-A[i])] += 1
            nA[min(n, i+1+A[i])] -= 1
        for i in range(1, n+1): nA[i] += nA[i-1]
        A = nA
    print(*A[:-1])

    return

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

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    regy = [0]*h
    regx = [0]*w
    c = [[0]*w for i in range(h)]
    for x in s:
        regy[x[0]] += 1
        regx[x[1]] += 1
        c[x[0]][x[1]] = 1
    maxy = 0
    indy = []
    for i in range(h):
        if maxy < regy[i]:
            indy = [i]
            maxy = regy[i]
        elif maxy == regy[i]:
            indy.append(i)
    maxx = 0
    indx = []
    for i in range(w):
        if maxx < regx[i]:
            indx = [i]
            maxx = regx[i]
        elif maxx == regx[i]:
            indx.append(i)

    ans = maxy + maxx
    tmp = 1
    if len(indy)*len(indx) > m:
        tmp = 0
    else:
        for y in indy:
            for x in indx:
                if c[y][x] == 0:
                    tmp = 0
    print(ans - tmp)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    ay = [0]*h
    ax = [0]*w
    for x in s:
        ay[x[0]] += 1
        ax[x[1]] += 1

    my = max(ay)
    mx = max(ax)
    
    by = bx = 0
    for y in ay:
        if y == my:
            by += 1
    for x in ax:
        if x == mx:
            bx += 1
            
    ans = my + mx
    tmp = 0
    for x in s:
        if ay[x[0]]+ax[x[1]]==ans:
            tmp += 1
    if tmp == by*bx:
        ans -= 1
    print(ans)
    
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

N, M = map(int,input().split())
L = []
for i in range(M):
    p, y = map(int,input().split())
    L.append((p,y))
PY = sorted(L, key = lambda x: x[1])
from collections import defaultdict
d = defaultdict(list)
for p,y in PY:
    d[p].append(y)
for i in range(M):
    p,y = L[i]
    print("{:06}{:06}".format(p, d[p].index(y)+1))

### FIXED CODE ###

N, M = map(int,input().split())
L = []
for i in range(M):
    p, y = map(int,input().split())
    L.append((p,y,i))
PY = sorted(L)
from collections import defaultdict
d = defaultdict(int)
ID = [None]*M
for p,y,i in PY:
    d[p] += 1
    ID[i] = d[p]
for i in range(M):
    p,y,j = L[i]
    print("{:06}{:06}".format(p, ID[i]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
if N == 0 and A[0] == 1:
    print(1)
else:
    nodes = [0]*(N+1)
    s_d = 0 # 飽和してないノードが残ってる深さ
    cap_d = 1 - A[0]
    failed = False
    for i, a in enumerate(A):
        # a個の葉をなるべく浅いノードから取る
        while a > 0:
            # これ以上分岐することろがなければ失敗
            if i < s_d or cap_d <= 0:
                failed = True
                break
            # s_dから枝を取れるだけ取る
            x = min(cap_d - nodes[s_d], a)
            a -= x
            nodes[s_d:i+1] = [node + x for node in nodes[s_d:i+1]]
            # s_dがいっぱいになったら深さを一つ進める
            if nodes[s_d] >= cap_d:
                cap_d -= A[s_d]
                cap_d *= 2
                s_d += 1
        if failed:
            break
    print(-1 if failed else sum(nodes))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cap = [[0, 0] for _ in range(N+1)]
cap[-1] = [A[-1], A[-1]]
for i in range(N-1,-1,-1):
    cap[i][0] = (cap[i+1][0] + 2 - 1)//2
    cap[i][1] = cap[i+1][1] + A[i]
ans = 1
nodes = 1
failed = nodes < cap[0][0]
for i in range(N):
    nodes = min((nodes - A[i])*2, cap[i+1][1])
    if nodes < cap[i+1][0]:
        failed = True
        break
    ans += nodes
print(-1 if failed else ans)
### BUGGY CODE ###

n = int(raw_input().strip())
ais = map(int, raw_input().strip().split())

curr = [0 for _ in xrange(n)]
total = [0 for _ in xrange(n)]

for i in xrange(n):
    for j in xrange(n):
        if i == j:
            continue
        total[j] += abs(curr[j] - ais[i])
        curr[j] = ais[i]

for i in xrange(n):
    total[i] += abs(curr[i])
    print total[i]


### FIXED CODE ###

n = int(raw_input().strip())
ais = map(int, raw_input().strip().split())

sp = abs(ais[0]) + abs(ais[-1]) + sum([abs(ais[i + 1] - ais[i]) for i in xrange(n - 1)])

total = [sp for _ in xrange(n)]
for i in xrange(n):
    if i == 0:
        total[i] -= abs(ais[0] - 0)
        total[i] -= abs(ais[1] - ais[0])
    elif i == n - 1:
        total[i] -= abs(0 - ais[n - 1])
        total[i] -= abs(ais[n - 1] - ais[n - 2])
    else:
        total[i] -= abs(ais[i + 1] - ais[i])
        total[i] -= abs(ais[i] - ais[i - 1])

    if i == n - 1:
        total[i] += abs(0 - ais[n - 2])
    elif i == 0:
        total[i] += abs(ais[1] - 0)
    else:
        total[i] += abs(ais[i + 1] - ais[i - 1])

    print total[i]
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
for i in range(N):
    tmp = A.copy()
    tmp.pop(i)
    print(max(tmp))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(list(set(A)))
max_v = B[-1]
max_c = A.count(max_v)
for i in range(N):
    tmp = A[i]
    if tmp != max_v:
        print(max_v)
    else:
        if max_c > 1:
            print(max_v)
        else:
            print(B[-2])
### BUGGY CODE ###

n=int(input())
s=input()
sm=0
for x in [(x,y,z) for x in range(10) for y in range(10) for z in range(10)]:
    token=0
    for i in range(n):
        if x[token]==int(s[i]):
            token+=1
            if token==3 : break
    if token==3 : sm+=1
print(sm)

### FIXED CODE ###

n=int(input())
s=input()
sm=0
for x in [(x,y,z) for x in range(10) for y in range(10) for z in range(10)]:
    token=0
    for i in range(n):
        if x[token]==int(s[i]):
            token+=1
            if token==3 : break
    if token==3 : sm+=1
print(sm)
### BUGGY CODE ###

import math
import collections
from operator import mul
from functools import reduce
import bisect

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

s=input()
k=int(input())
a=[]
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        a.append(s[i:j])
        a=sorted(list(set(a)))[:k]
a=sorted(list(set(a)))
print(a[k-1])









### FIXED CODE ###

import math
import collections
from operator import mul
from functools import reduce
import bisect

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

s=input()
k=int(input())
a=[]
for i in range(len(s)):
    for j in range(i+1,min(i+2+k,len(s)+1)):
        a.append(s[i:j])
a=sorted(list(set(a)))
print(a[k-1])
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
s = 1
if n%2!=0:
  l1 = [i for i in range(0,n,2)]
  for i in l1:
    a = l.count(i)
    if (i==0 and a==1) or (i!=0 and a==2):
      s *= 2
    else:
      s = 0
      break
  else:
    s //= 2
else:
  l1 = [i for i in range(1,n,2)]
  for i in l1:
    a=l.count(i)
    if a==2:
      s *= 2
    else:
      s = 0
      break
print(int(s))
      
    

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
s = 1
if n%2!=0:
  if l.count(0)!=1:
    s =0
  else:
    l.remove(0)
    if len(set(l))==(n-1)//2:
      s = 2**((n-1)//2)
    else:
      s =0
else:
    if len(set(l))==n//2:
      s = 2**(n//2)
    else:
      s = 0
print(int(s)%(10**9+7))
### BUGGY CODE ###

N, M = map(int, input().split())
a = [0]*M
b = [0]*M
for i in range(M):
  a[i], b[i] = map(int, input().split())
c = []
for i in range(M):
  if b[i] == N:
    c.append(a[i])
if len(c) != 0:
  for i in range(M):
    if a[i] == 1:
      for j in range(len(c)):
        if b[i] == c[j]:
          print("POSSIBLE")
          exit()
print("IMPOSSIBLE")

### FIXED CODE ###

N, M = map(int, input().split())
edges = [[] for i in range(N)]

for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edges[a].append(b)

for i in edges[0]:
  if N-1 in edges[i]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

import numpy as np

N = int(input())
S = input()

S = S.replace("R", "1")
S = S.replace("G", "2")
S = S.replace("B", "3")
count = 0

if N < 3:
  print(count)
else:
  for i in range(2, N):
    #選択した部分より手前と後ろに分ける
    a, b = list(S[:i-1]), list(S[i:])
    #手前反転
    a.reverse()
    A = np.array([int(j) for j in a])
    C = np.reshape(A, (len(a), 1))
    B = np.array([int(k) for k in b])
    D = np.reshape(B, (1, len(b)))
    E = np.dot(C, D) * int(S[i-1])
    F = np.diag(E)
    count += np.count_nonzero(E == 6) - np.count_nonzero(F == 6)
  print(count)

### FIXED CODE ###


N = int(input())
S = list(input())
R = []
G = []
B = []

cnt = 0

for i in range(N):
  if S[i] == "R":
    R.append(i)
  elif S[i] == "G":
    G.append(i)
  else:
    B.append(i)

B = set(B)
b = len(B)  

for i in R:
  for j in G:
    check = 0
    m = min(i, j)
    M = max(i, j)
    r = M - m
    left = m - r
    right = M + r
    if r % 2 == 0:
      center = m + r//2
      if center in B:
        check += 1
    if left in B:
      check += 1
    if right in B:
      check += 1
    cnt += b - check

print(cnt)
### BUGGY CODE ###

import numpy as np

n = int(input())

a = list(map(int, input().split()))
a_array = np.array(a)
base_array = np.array(range(n))+1

ans = 0

# print(a_array)
# print(base_array)

for i in range(n-1):
  sum_array = a_array[i+1:] + a_array[i]
  # print(sum_array)
  sum_array = sum_array - base_array[:-(i+1)]
  res = np.count_nonzero(sum_array == 0)
  ans += res
#for i in range(n-1):
#  for j in range(i+a[i]+1, n):
#    if j-i == a[i] + a[j]:
#      ans += 1

print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())

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

x = {}
y = {}

ans = 0

for i in range(n):
  x.setdefault((i+a[i]), []).append(i) 
  y.setdefault((i-a[i]), []).append(i)

z = list(set(x.keys()) & set(y.keys()))

# print(x)
# print(y)
# print(z)

for i in z:
  if x[i][len(x[i])-1] < y[i][0]:
    n = len(y[i]) * len(x[i])
    ans += n
    # print(x[i])
    # print(y[i])
    # print(n)
    # print(ans)

  else:
    for j in range(len(x[i])):
      # print(x[i])
      # print(x[i][j])
      # print(y[i])
      ans += sum(1 for k in y[i] if x[i][j] < k)

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

s=input()
sl=list(map(int,list(s)))
n=len(s)
sums=[0]*(n+1)
ans=0
for i in range(1,n+1):
    sums[i]=sums[i-1]+sl[i-1]
for i in range(n-4):
    for j in range(i+4,n):
        if (sums[j+1]-sums[i])%3==0:
            if int(s[i:j+1])%2019==0:
                ans+=1
print(ans)

### FIXED CODE ###

s=list(map(int,list(input())))[::-1]
n=len(s)
chk=[0]*2019
chk[0]=1
t,m,ans=1,0,0
for i in s:
    m=(m+t*i)%2019
    ans+=chk[m]
    chk[m]+=1
    t=t*10%2019
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    b = format(a, '0'+str(MAXBIT)+'b')
    for d in range(MAXBIT):
        # C[d].update([b[d]])
        C[d].append(int(b[d]))
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += (num0 * num1) * (2 ** (MAXBIT-d-1))
    ans %= MOD
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    for d in range(MAXBIT):
        C[d].append(a >> d & 1)
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += ((num0 * num1) % MOD) * pow(2, d, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c=0
l=[0]
for i in range(n):
  l.append(l[i]+a[i])
L=collections.Counter(l)
for j in range(len(L)):
  x=L.most_common()[j][1]
  c+=int(x*(x-1)/2)
print(c)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c=0
l=[0]
for i in range(n):
  l.append(l[i]+a[i])
L=collections.Counter(l)
for j in L.values():
  c+=int(j*(j-1)/2)
print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a_uni = list(set(a))

for k in range(n):
    b = a.copy()
    del b[k]
    count = 0
    for i in a_uni:
        ol = b.count(i)
        count += ol * (ol - 1) // 2
    print(count)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))


a_ol = Counter(a)
def_count = 0
for item in a_ol.items():
    a_co = item[1]
    def_count += a_co * (a_co - 1)

def_count //= 2

for k in a:
    print(def_count - a_ol[k] + 1)
### BUGGY CODE ###

from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
     [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != "#":
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PY, PX in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != "#":
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
        [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

x=0
k=int(input())
r = range(1, k + 1)
x = sum([gcd(a, b, c) for a in r for b in r for c in r])
print(x)

### FIXED CODE ###

from math import gcd

k = int(input())

r = range(1, k + 1)
ans = sum([gcd(gcd(a, b), c) for a in r for b in r for c in r])
print(ans)
### BUGGY CODE ###

# D - Multiple of 2019
s = input()[::-1]
length = len(s)
a = []
for i in range(len(s)):
    a.append(int(s[i]) * pow(10, i) % 2019)
print(0) if int(s) < 2019 else print(sum(sum(a[j:i+j]) % 2019 == 0 for i in range(4, length) for j in range(length-i+1)))

### FIXED CODE ###

import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])