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


def main():
  s = input()
  n = len(s)

  mod = 2019

  counts = [0] * mod
  counts[0] += 1

  prev = int(s[-1])
  counts[prev % mod] += 1
  for i in range(2, n + 1):
    t = prev + int(s[-i]) * 10 ** (i - 1)
    counts[t % mod] += 1
    prev = t

  ans = 0
  for count in counts:
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()


### FIXED CODE ###


def main():
  s = map(int, input()[::-1])

  mod = 2019

  counts = [0] * mod
  counts[0] = 1
  t = 0
  x = 1
  for num in s:
    t = (t + num * x) % mod
    counts[t] += 1
    x = (x * 10) % mod

  ans = 0
  for count in counts:
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()
### BUGGY CODE ###

n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)


### FIXED CODE ###

n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+(m+d)*m*(m-1)-M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+(m+d)*m*(m-1)-M
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)
### BUGGY CODE ###

import itertools
N=int(input())
listA=list(map(int,input().split()))
listA.sort()
listA2=[0]*N
for i in listA:
  listA2[i-1]+=1
for i in range(1,N+1):
  if i in listA:
    print(listA2[i-1])
  else:
    print(0)

### FIXED CODE ###

import itertools
N=int(input())
listA=list(map(int,input().split()))
listA.sort()
listA2=[0]*N
for i in listA:
  listA2[i-1]+=1
listA=set(listA)  
for i in range(1,N+1):
  if i in listA:
    print(listA2[i-1])
  else:
    print(0)
### BUGGY CODE ###

N = int(input())

def m_dis(x1, y1, x2, y2):
	return abs(x2 - x1) + abs(y2 - y1)

table_p = {}
table_m = {}

points = []
for _ in range(N):
	x, y = map(int, input().split())
	points.append((x, y))
	a = x + y
	b = x - y
	if a in table_p:
		table_p[a].append((x, y))
	else:
		table_p[a] = [(x, y)]
	if b in table_m:
		table_m[b].append((x, y))
	else:
		table_m[b] = [(x, y)]

list_p = []
list_m = []
for a, ps in table_p.items():
	list_p.append((a, ps[0]))

for b, ps in table_m.items():
	list_m.append((b, ps[0]))

list_p.sort()
list_m.sort()

topvalue = 0

for x, y in points:
	topvalue = max(topvalue, 
		m_dis(x, y, list_p[0][1][0], list_p[0][1][1]),
		m_dis(x, y, list_p[-1][1][0], list_p[-1][1][1]),
		m_dis(x, y, list_m[0][1][0], list_m[0][1][1]),
		m_dis(x, y, list_m[-1][1][0], list_m[-1][1][1]))

print(topvalue)


### FIXED CODE ###

N = int(input())

def m_dis(x1, y1, x2, y2):
	return abs(x2 - x1) + abs(y2 - y1)

points = []
for _ in range(N):
	x, y = map(int, input().split())
	points.append((x, y))

x, y = points[0]

maxvalue_p = x + y
minvalue_p = x + y
maxvalue_m = x - y
minvalue_m = x - y
maxvalue_p_p = points[0]
minvalue_p_p = points[0]
maxvalue_m_p = points[0]
minvalue_m_p = points[0]

for x, y in points:
	p = x + y
	m = x - y
	if maxvalue_p == None or maxvalue_p < p:
		maxvalue_p = p
		maxvalue_p_p = (x, y)
	if minvalue_p == None or minvalue_p > p:
		minvalue_p = p
		minvalue_p_p = (x, y)
	if maxvalue_m == None or maxvalue_m < m:
		maxvalue_m = m
		maxvalue_m_p = (x, y)
	if minvalue_m == None or minvalue_m > m:
		minvalue_m = m
		minvalue_m_p = (x, y)

topvalue = 0

for x, y in points:
	topvalue = max(topvalue, 
		m_dis(x, y, maxvalue_p_p[0], maxvalue_p_p[1]),
		m_dis(x, y, minvalue_p_p[0], minvalue_p_p[1]),
		m_dis(x, y, maxvalue_m_p[0], maxvalue_m_p[1]),
		m_dis(x, y, minvalue_m_p[0], minvalue_m_p[1]))

print(topvalue)
### BUGGY CODE ###

import sys

X, K, D = list(map(int, input().split()))

p = X
_p = 0
k = 0

if abs(p) > K*D:
    print(abs(p)-K*D)
    sys.exit()

if p < 0:
    while 1:
        _p = p
        p += D
        k += 1
        if p > 0:
            break
    if (K-k) % 2 == 0:
        print(abs(p))
    else:
        print(abs(_p))
elif p > 0:
    while 1:
        _p = p
        p -= D
        k += 1
        if p < 0:
            break
    if (K-k) % 2 == 0:
        print(abs(p))
    else:
        print(abs(_p))
else:
    if K % 2 == 0:
        print(0)
    else:
        print(D)


### FIXED CODE ###

import sys

X, K, D = list(map(int, input().split()))

p = X
_p = 0
k = 0

if abs(p) > K*D:
    print(abs(p)-K*D)
    sys.exit()

if p < 0:
    for i in range(K):
        _p = p
        p += D
        k += 1
        if p > 0:
            break
    if (K-k) % 2 == 0:
        print(abs(p))
    else:
        print(abs(_p))
elif p > 0:
    for i in range(K):
        _p = p
        p -= D
        k += 1
        if p < 0:
            break
    if (K-k) % 2 == 0:
        print(abs(p))
    else:
        print(abs(_p))
else:
    if K % 2 == 0:
        print(0)
    else:
        print(D)
### BUGGY CODE ###


from collections import defaultdict

def main():
    #bfならどう解く？
    #O(n2)で解ける
    N = int(input())
    S = input()
    
    length = 1
    ans = 0
    while length<= N//2:
        seen = defaultdict(set)
        for start in range(length):
            for idx in range(start, N-length+1, length):
                sub = S[idx:idx+length]
                if sub in seen:
                    for prev_idx in seen[sub]:
                        if prev_idx + length <= idx:
                            ans = length
                            break
                seen[sub].add(idx)
        length += 1
    
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()

    ans = 0
    dp = [[0] * (N+1) for _ in range(N+1)]
    for i in range(N-1, -1, -1):
        for j in range(N-1, i, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                tmp = min(dp[i][j], j-i)
                ans = max(ans, tmp)
    print(ans)

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

import sys

s = input()
t = list(input())

string = s
length = 1

for i in range(len(t)):
	if s.find(t[i])==-1:
		print(-1)
		sys.exit()
	if string.find(t[i])==-1:
		string = string + s
		length += 1
	string = string[string.find(t[i])+1 : ]
	
print(length*len(s)-len(string))

### FIXED CODE ###

import sys

s = input()
t = list(input())

string = s
length = 1

for i in range(len(t)):
	if s.find(t[i])==-1:
		print(-1)
		sys.exit()
	if string.find(t[i])==-1:
		string = s
		length += 1
	string = string[string.find(t[i])+1 : ]
	
print(length*len(s)-len(string))
### BUGGY CODE ###

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

count = 0
for i in range(A,B+1):
    if((i%C !=0) and (i%D !=0)):
        count+=1

print(count)

### FIXED CODE ###

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

def gcd(x,y):

    if(y>x):
        x,y = y,x
    if(x%y==0):
        return y
    else:return gcd(y,x%y)


def lcm(x,y):
    return x*y//gcd(x,y)

Bika = B - B//C -B//D + B//lcm(C,D)
Aika = A-1 - (A-1)//C -(A-1)//D + (A-1)//lcm(C,D)

print(Bika-Aika)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
uno = a.count(1)
dos = a.count(2)
tres = n - uno - dos
dp = [[[0]*(n+1) for _ in range(dos+tres+1)] for j in range(tres+1)]
for k in range(tres+1):
  for j in range(dos+tres-k+1):
    for i in range(n+1-j-k):
      if i+j+k == 0: continue
      v = i+j+k
      res = n
      if i: res += i * dp[k][j][i-1]
      if j: res += j * dp[k][j-1][i+1]
      if k: res += k * dp[k-1][j+1][i]
      dp[k][j][i] = res / v
print(dp[tres][dos][uno]) 

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
uno = a.count(1)
dos = a.count(2)
tres = n - uno - dos
dp = [[[0]*(n+1) for _ in range(dos+tres+1)] for j in range(tres+1)]
for k in range(tres+1):
  for j in range(dos+tres-k+1):
    for i in range(n+1-j-k):
      if i+j+k == 0: continue
      v = i+j+k
      res = n
      if i: res += i * dp[k][j][i-1]
      if j: res += j * dp[k][j-1][i+1]
      if k: res += k * dp[k-1][j+1][i]
      dp[k][j][i] = res / v
print(dp[tres][dos][uno])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
#start = time.clock()
#i = 0
a,b=[],[]
check = re.compile('insert')
n=input()
#while True:
for x in xrange(n):
    (i,f)=map(str, raw_input().split())
    if check.search(i):
        a.append(f)
    else:
#        b.append(f)
#print a
#print b
#for y in b:
        if f in a:
            print 'yes'
        else:
            print 'no'

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
#start = time.clock()
#i = 0
#check = 'insert'
n=input()
a=set()
for x in xrange(n):
    (i,f)=map(str, raw_input().split())
    if i=='insert':
        a.add(f)
    else:
        if f in a:
            print 'yes'
        else:
            print 'no'
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])
C = sorted([[int(i) for i in input().split()] for i in range(M)], reverse = True, 
           key = lambda x: x[1])
 
cnt = 0
B = []
for i in range(M):
    B += [C[i][1]] * C[i][0]
    cnt += C[i][0]
    
x = min(N, len(B))

for i in range(x):
    A[i] = max(A[i], B[i])
    
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])
C = sorted([[int(i) for i in input().split()] for i in range(M)], reverse = True, 
           key = lambda x: x[1])

cnt = 0
B = []
for i in range(M):
    if cnt > N:
        break
    B += [C[i][1]] * C[i][0]
    cnt += C[i][0]
    
B.sort(reverse = True)

x = min(N, len(B))

for i in range(x):
    A[i] = max(A[i], B[i])
    
print(sum(A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
mod = 10**23 + 117

d = {}

S = [input()[:-1] for i in range(n)]

S.sort(key = lambda x:len(x))

ans = 0
for s in S:
    if len(s) == 1:
        if -1 in d.keys():
            array = d[-1]
            ans += array[ord(s) - ord("a")]
        else: d[-1] = [0]*26
        d[-1][ord(s) - ord("a")] += 1
    else:
        h = 0
        cnt = [0]*26
        for t in s:
            cnt[ord(t) - ord("a")] += 1
        if -1 in d.keys():
            array = d[-1]
            for i in range(26):
                if cnt[i] > 0 and array[i] > 0:ans += 1
        for t in s[len(s) - 1:0:-1]:
            num = ord(t) - ord("a")
            h += num + 1
            h *= 29
            h %= mod
            cnt[num] -= 1
            if h in d.keys():
                array = d[h]
                for i in range(26):
                    if cnt[i] > 0 and array[i] > 0:ans += 1
        if h not in d.keys(): d[h] = [0]*26
        d[h][ord(s[0]) - ord("a")] += 1
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
mod = 10**23 + 117

d = {}

S = [input()[:-1] for i in range(n)]

S.sort(key = lambda x:len(x))

ans = 0
for s in S:
    if len(s) == 1:
        if -1 in d.keys():
            array = d[-1]
            ans += array[ord(s) - ord("a")]
        else: d[-1] = [0]*26
        d[-1][ord(s) - ord("a")] += 1
    else:
        h = 0
        cnt = [0]*26
        for t in s:
            cnt[ord(t) - ord("a")] += 1
        if -1 in d.keys():
            array = d[-1]
            for i in range(26):
                if cnt[i] > 0 and array[i] > 0:ans += 1
        for t in s[len(s) - 1:0:-1]:
            num = ord(t) - ord("a")
            h += num + 1
            h *= 29
            h %= mod
            cnt[num] -= 1
            if h in d.keys():
                array = d[h]
                for i in range(26):
                    if cnt[i] > 0 and array[i] > 0:ans += 1
        if h not in d.keys(): d[h] = [0]*26
        d[h][ord(s[0]) - ord("a")] += 1
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
new=[0]*N
A.sort()
insuu=[0]*(A[N-1]+1)
pf={}
l=[]
ans=1
cnt=0
p=(10**9)+7
for i in range(N):
    m = A[i]
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1
    #print(pf)
    keys=list(pf.keys())
    values=list(pf.values())
    pf={}
    for j in range(len(keys)):
        if insuu[keys[j]]<values[j]:
            insuu[keys[j]]=values[j]
        l.append([keys[j],values[j]])
        #print(insuu)
    #print(l)
    l=[]
for i in range(1,A[N-1]+1,1):
    if insuu[i]>0:
        ans=ans*pow(i,insuu[i])
for i in range(N):
    new[i]=ans//A[i]
#print(ans,new)
for i in range(N):
    cnt=(cnt+new[i])%p
print(cnt)
#print(l)	#これでlistになった

### FIXED CODE ###

def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
new=[0]*N
A.sort()
insuu=[0]*(A[N-1]+1)
pf={}
l=[]
ans=1
cnt=0
p=(10**9)+7

for i in range(N):
    m = A[i]
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1
    #print(pf)
    keys=list(pf.keys())
    values=list(pf.values())
    pf={}
    for j in range(len(keys)):
        if insuu[keys[j]]<values[j]:
            insuu[keys[j]]=values[j]
        #print(insuu)
    #print(l)
for i in range(1,A[N-1]+1,1):
    if insuu[i]>0:
        ans=ans*pow(i,insuu[i])
#print(ans)
for i in range(N):
    #print((ans*modinv(A[i],p))%p)
    cnt=(cnt+(ans*modinv(A[i],p))%p)%p
print(cnt%p)
### BUGGY CODE ###

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

### FIXED CODE ###

import numpy as np
N=int(input())
A=list(map(int,input().split()))
ans=np.zeros(N)
count=0
for i in A:
  ans[i-1]=count+1
  count+=1
for j in ans:
  print(int(j),end=" ")
### BUGGY CODE ###

S = input()
T = input()

def solve(S,T):
    # print(W)
    s = len(S)
    t = len(T)
    dp = [[['',0] for _ in range(t+1)] for _ in range(s+1)]
    for i in range(s):
        for j in range(t):
            if S[i]==T[j]:
                dp[i+1][j+1][0] = dp[i][j][0]+S[i]
                dp[i+1][j+1][1] = dp[i][j][1]+1
            elif dp[i][j+1][1]>dp[i+1][j][1]:
                dp[i+1][j+1] = dp[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
    ans = dp[-1][-1][0]
    return ans
print(solve(S,T))

### FIXED CODE ###

S = input()
T = input()

def solve(S,T):
    # print(W)
    s = len(S)
    t = len(T)
    dp = [[0]*(t+1) for _ in range(s+1)]
    for i in range(s):
        for j in range(t):
            if S[i]==T[j]:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
    ans = ''
    i,j = s,t
    while i>0 and j>0:
        if dp[i][j]==dp[i-1][j]:
            i -= 1
        elif dp[i][j]==dp[i][j-1]:
            j -= 1
        else:
            ans = S[i-1]+ans
            i-=1
            j-=1
    return ans
print(solve(S,T))
### BUGGY CODE ###

N = int(input())
P = [int(p) for p in input().split()]
# 先頭は必ずカウント
count = 1
prev_index = N
for c in range(1, N):
    if P[c] == min(P[:c+1]):
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
count = 0
min_num = N
for c in input().split():
    p = int(c)
    min_num = min(min_num, p)
    if min_num == p:
        count += 1
print(count)
### BUGGY CODE ###

#import numpy as np
import sys
input=sys.stdin.readline

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

#p=np.array(list(map(int,input().split())))
func=lambda x: ((int(x)+1.)/2.)
p=list(map(func,input().split()))

#p=(p+1.)/2.
max_p=0

for i in range(n-k+1):
    #s=np.sum(p[i:i+k])
    s=sum(p[i:i+k])
    if  max_p < s:
        max_p=s

print(max_p)

### FIXED CODE ###

#import numpy as np
import sys
input=sys.stdin.readline

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

#p=np.array(list(map(int,input().split())))
func=lambda x: ((int(x)+1.)/2.)
p=list(map(func,input().split()))

#p=(p+1.)/2.
s=sum(p[0:k])
max_p=s

#for i in range(n-k+1):
for i in range(n-k):
    #s=np.sum(p[i:i+k])
    s=s-p[i]+p[i+k]
    if  max_p < s:
        max_p=s

print(max_p)
### BUGGY CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        tmp = l[j+1:]
        ans += bisect_left(tmp,a+b)
        
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        k = bisect_left(l,a+b)
        ans += k-j-1
print(ans)
### BUGGY CODE ###

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

cnt = 0
dist = [a[0]-1]
for ai in a[1:]:
    cnt += dist.count(-ai)
    dist.append(ai)
    dist = list(map(lambda x: x-1, dist))

print(cnt)

### FIXED CODE ###

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

# i < j
# j - i = Aj + Ai
# j - Aj = i + Ai

ans = 0
adds = dict()
for j in range(n):
    sub = j - a[j]
    if sub in adds.keys():
        ans += adds[sub]

    add = j + a[j]
    if add in adds.keys():
        adds[add] += 1
    else:
        adds[add] = 1

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

L, R = map(int, input().split())
MOD = 2019
ans = L*R%MOD
for i in range(L, R):
    for j  in range(i+1, R+1):
        if ans > i*j%MOD:
            ans = i*j%MOD
            if ans == 0:
                break
    if ans == 0:
        break
print(ans)


### FIXED CODE ###

L, R = map(int, input().split())
MOD = 2019
ans = L*R%MOD
for i in range(L, R):
    for j  in range(i+1, R+1):
        if ans > i*j%MOD:
            ans = i*j%MOD
        if ans == 0:
            break
    if ans == 0:
        break
print(ans)
### BUGGY CODE ###

ans = 0
A,B = map(int,input().split())
for i in range(A,B+1):
  ans = ans ^ i
print(ans)

### FIXED CODE ###

A,B = map(int,input().split())
def xor(n):
  m = 0
  if n % 4 == 0:
    m = n
  elif n % 4 == 1:
    m = 1
  elif n % 4 == 2:
    m = n + 1
  return m
a = xor(A-1)
b = xor(B)
print(a ^ b)
### BUGGY CODE ###

s = input()
a = int(s)
mods = [a%2019]
for i in range(len(s)):
  a = a-int(s[i])*10**(len(s)-i-1)
  mods.append(a%2019)
mod_N = {}
for i in mods:
  if not i in mod_N:
    mod_N[i] = 1
  else:
    mod_N[i] += 1
ans = 0
for i in mod_N:
  ans += int(mod_N[i]*(mod_N[i]-1)/2)
print(ans)

### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

from math import sqrt
from decimal import *

getcontext().prec = 40000

a, b, c = map(int, input().split())

tmp = 2 * sqrt(Decimal(a)) * sqrt(Decimal(b))
print("Yes" if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt() else "No")


### FIXED CODE ###

from math import sqrt
from decimal import *


a, b, c = map(int, input().split())

tmp = 2 * sqrt(Decimal(a)) * sqrt(Decimal(b))
print("Yes" if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt() else "No")
### BUGGY CODE ###


import numpy as np
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
move2 = [
    (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), \
    (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), \
    (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), \
    (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), \
    (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
q = deque()
one_time = deque()
q.append([ch, cw])
while q:
    x, y = q.popleft()
    one_time.append((x, y))
    for (i, j) in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append((v1, v2))
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for (i, j) in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append((v1, v2))
print(ans[dh][dw])

### FIXED CODE ###

from collections import deque
 
 
# In[30]:
 
 
def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

ans = 0
for left in range(N):
    ans += 1    # left equal right
    xor_sum = an[left]
    arith_sum = an[left]
    for right in range(left + 1, N):
        xor_sum ^= an[right]
        arith_sum += an[right]
        if xor_sum == arith_sum:
            ans += 1
        else:
            break

print(ans)

### FIXED CODE ###

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

ans = 0
right = 0
arith_sum = 0
for left in range(N):
    while right < N and arith_sum ^ an[right] == arith_sum + an[right]:
        arith_sum += an[right]
        right += 1
    ans += right - left
    if left == right:
        right += 1
    else:
        arith_sum -= an[left]

print(ans)