Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(20)
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
startwithone=[i for i in number if i[0]==1]
notstartwithone=[i for i in number if i[0]!=1]
if len(startwithone)==0:
  print(0)
  exit()
if len(startwithone)==0:
  if n==2:
    print(1)
    exit()
  print(0)
  exit()
ans=0
flag2=0
def find(x):
  if root[x]==x:
    return x
  return find(root[x])
def check(x,y):
  return find(x)==find(y)
def union(x,y):
  if find(1)==find(x):
    root[y]=x
  else:
    root[x]=y
def dfs(i,flag):
  global ans
  global root
  global flag2
  flag2=flag
  if bin(flag)[2:].count("1")!=n-2 or len(notstartwithone)<i:
    if len(notstartwithone)<i:
      return 0
    dfs(i+1,flag|2**i)
    dfs(i+1,flag)
  root=[i for i in defroot]
  rank=[i for i in defrank]
  for j in range(len(notstartwithone)):
    if flag&2**j>0:
      union(notstartwithone[j][0],notstartwithone[j][1])
  for j in range(1,n):
    if check(j,j+1)==False:
      return 0
  if len(set(root))==n:
    ans+=1
for i in startwithone:
  root=[i for i in range(n+1)]
  rank=[0]*(n+1)
  union(i[0],i[1])
  defroot=[i for i in root]
  defrank=[i for i in rank]
  dfs(0,0)
print(ans)

### FIXED CODE ###

import sys
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
visit=[0]*(n+1)
visit[1]=1
node=[[] for i in range(n+1)]
for i in number:
  node[i[0]].append(i[1])
  node[i[1]].append(i[0])
ans=0
def dfs(x):
  global ans
  if visit.count(1)==n:
    ans+=1
    return 0
  for i in node[x]:
    if visit[i]==0:
      visit[i]=1
      dfs(i)
      visit[i]=0
  return 0
dfs(1)
print(ans)
c=[]
for i in range(3):
  c += [map(int,input())]
 
if c[0][0] + c[1][1]+ c[2][2] == c[1][0] + c[2][1] + c[0][2] == c[2][0] + c[0][1] + c[1][2]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

c=[]
for i in range(3):
  A = list(map(int, input().split()))
  c.append(A)
if c[0][0] + c[1][1]+ c[2][2] == c[1][0] + c[2][1] + c[0][2] == c[2][0] + c[0][1] + c[1][2]:
  print('Yes')
else:
  print('No')
n=int(input())
m=int(input())
print((n-1)*(m-1))

### FIXED CODE ###

n,m=map(int,input().split())
print((n-1)*(m-1))
def culc(n):
    if n%2==0:
        return (n+1)*(n/2)-n
    if n%2==1:
        return (n+1)*((n-1)/2)+(n+1)/2-n

N = int(input())
if N == 1:
    print(0)
else:
    print(int(culc(N)))

### FIXED CODE ###

S = input()
T = input()
count = 0
for i in range(3):
    if S[i]==T[i]:
        count += 1
print(count)
from operator import mul
from functools import reduce

x,y = map(int,input().split())
mod = 10**9 + 7

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return (over // under)

if (x+y)%3 != 0:
    print(0)
    exit()
else:
    s = (x+y)//3

t = min((x-s),(y-s))


print(cmb(s,t)%mod)

### FIXED CODE ###

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
    
x,y = map(int,input().split())


if (x+y)%3 != 0 or not(x <= 2*y and y <= 2*x):
    print(0)
    exit()
else:
    s = (x+y)//3
 
t = min((x-s),(y-s))

print(combination(s,t))
O = input()
E = input()
dif_len = len(O) - len(E)
password = ''

if dif_len == 0:
    for i in range(max_len):
        password += O[i] + E[i]
elif dif_len > 0:
    for i in range(len(O)):
        if i != len(O) - 1:
            password += O[i] + E[i]
        else:
            password += O[i]
else:
    for i in range(len(E)):
        if i != len(E) - 1:
            password += O[i] + E[i]
        else:
            password += E[i]

print(password)

### FIXED CODE ###

O = input()
E = input()
dif_len = len(O) - len(E)
password = ''

if dif_len == 0:
    for i in range(len(O)):
        password += O[i] + E[i]
elif dif_len > 0:
    for i in range(len(O)):
        if i != len(O) - 1:
            password += O[i] + E[i]
        else:
            password += O[i]

print(password)
#input()
ans=1
for i in map(int,input().split()):ans*=i
print(int(ans))

### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b.replace('.',''))
print((a*b)//100)
n=int(input())
#print(n)                                                                                                     
#a=input().split()                                                                                            
a=[int(x) for x in input().split()]
#a=map(int,input().split())                                                                                   
#print(a)                                                                                                     
#print(a[0]+a[1])                                                                                             
count=0
while True:
    flag=0
#    print(a)                                                                                                 
    for i in range(n):
        if((a[i] % 2)==0):
#        if((a[i]!=1) and (a[i] % 2)==0):                                                                     
            flag+=0
            a[i]=a[i]/2
        else:
            flag+=1
#    print(flag)                                                                                              
    if(flag!=0):
        break
    else:
        count+=1
#        print(count)                                                                                         

print(count)


### FIXED CODE ###

a=int(input())
b1=a // 100
b2=a % 100
c1=b2 // 10
c2=b2 % 10
print(b1+c1+c2)
def f(s,t,k):
 n=len(s)
 a=max(t,int(s[0]))
 if k>n:z=0
 elif a==0:z=f(s[1:],t,k)
 elif k==1:z=a+(n-1)*9
 else:
  z=0
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))

### FIXED CODE ###

def f(s, t, k):
 n = len(s)
 if k > n: return 0
 a = max(t, int(s[0]))
 if a == 0: return f(s[1:], t, k)
 if k == 1: return a + (n - 1) * 9
 z = 0
 if k - 1 <= n: z += f(s[1:], 9, k)
 z += (a - 1) * f(s[1:], 9, k - 1)
 z += f(s[1:], t, k - 1)
 return z

s = input()
k = int(input())
print(f(s, 0, k))
n = input()
h = list(map(int,input().split()))

total = 0
maxN = 0
for num in h:
  if  num >= maxN:
    total += 1
  
  maxN = max(maxN,num)

print(total)

### FIXED CODE ###

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

total = 0

if a >= b :
    total = a
    a -= 1
else:
    total = b
    b -=  1

if a>= b :
    total = total + a
else:
    total = total + b

print(total)
import numpy as np

grid = []
#for i in range(1):
array = list(map(int,input().strip().split()))
#    grid.append(array)
#print(array)
a = array[0]
b = array[1]

min8 = a/0.08
max8 = (a+1)/0.08
min10 = b/0.1
max10 = (b+1)/0.1

def lists(a,b):
    if a%1==0:
        a2 = a
    else:
        a2 = int(a)+1
    if b%1==0:
        b2 = b-1
    else:
        b2 = int(b)
    return np.arange(a2,b2+1)

list8 = lists(min8,max8)
list10 = lists(min10,max10)
#print(list8,list10)
hosii = list(set(list8)&set(list10))
if len(hosii)>0:
    print(int(np.min(hosii)))
else:
    print(-1)

### FIXED CODE ###

import numpy as np

bus = input()

if bus == "AAA":
    print("No")
elif bus == "BBB":
    print("No")
else:
    print("Yes")
N,M=map(int, input().split())
wa={}
ac=[]
key=[]

    
for i in range(M):
    p,s=input().split()
    if p not in ac:
        if p not in key:
            key.append(p)
            wa[P[i]]=0

        if s=="WA":
            wa[p]+=1
        else:
            ac.append(p)
ans=0
for i in key:
    if i in ac:
        ans+=wa[i]
print(len(ac),ans)



### FIXED CODE ###

N,M=map(int,input().split())
AC={}
WA={}
for i in range(M):
    a,b=input().split()
    if not(a in AC.keys()):
        if b=="AC":
            AC[a]=1
        else:
            if a in WA.keys():
                WA[a]+=1
            else:
                WA[a]=1
y=0
for i in AC.keys():
    if i in WA.keys():
        y+=WA[i]
print(sum(AC.values()),y)
def f(H):
    if H == 1:
        return 1
    return 2 * f(H//2) + 1


def solve():
    H = int(input())
    print(f(H))


if __name__ == "__main__":
    solve()

### FIXED CODE ###

def ev(n):
    return (n+1) / 2


N, K = map(int, input().split())
p = list(map(int, input().split()))
prev = ev(p[0])
ans = sum([ev(i) for i in p[:K]])
total = ans

for i in range(1, N-K+1):
    total -= prev
    total += ev(p[i+K-1])
    prev = ev(p[i])
    ans = max(ans, total)

print(ans)
k,n=map(int,input().split())
x=list(map(int,input().split()))

if n==1:
	res=0
else:
	y=sorted(x)
	z=[0]*(n-1)
	for i in range(n-1):
		z[i]=y[i+1]-y[i]
	v=sorted(z,reverse=True)
	w=0
	for i in range(k-1):
		w+=v[i]
	res=y[n-1]-y[0]-w

print(res)

### FIXED CODE ###

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

if k>=n or n==1:
	res=0
else:
	y=sorted(x)
	z=[0]*(n-1)
	for i in range(n-1):
		z[i]=y[i+1]-y[i]
	v=sorted(z,reverse=True)
	w=0
	if k>1:
		for i in range(k-1):
			w+=v[i]
		res=y[n-1]-y[0]-w
	else:
		res=y[n-1]-y[0] 

print(res)
N = str(input())

if N[-1] = 7 or N[-2] = 7 or N[-3] = 7:
    print("Yes")
else:
  	print("No")

### FIXED CODE ###

N = str(input())

if N[-1] == "7" or N[-2] == "7" or N[-3] == "7":
    print("Yes")
else:
  	print("No")
N = int(input())
a = input().split()
num=[]
tex=[]
count=0
for i in range(N):
	num.append(int(a[i]))
	if num[i] < 0 :
		count +=1
	elif num[i] == 0:
		count2 +=1
if count%2 ==0 or count2 > 0:
	res = sum(num)
else:
	tex=[i for i, x in enumerate(num) if x <0]
	res =sum(num)-min(tex[0],tex[-1])
print(res)

### FIXED CODE ###

N = int(input())
a = input().split()
num=[]
numabs=[]
tex=[]
count=0
count2=0
for i in range(N):
	num.append(int(a[i]))
	numabs.append(abs(num[i]))
	if num[i] < 0 :
		count +=1
	elif num[i] == 0:
		count2 +=1
if count%2 ==0 or count2 > 0:
	res = sum(numabs)
else:
	res =sum(numabs)-2*min(numabs)
print(res)
import math
 
N, X = map(int, input().split())
x = list(map(int,input().split()))
D = abs(x[0]-X)
for i in x:
    D = math.gcd(D,abs(i-X))
print(D)

### FIXED CODE ###

c, d = (int(i) for i in input().split())  
a = [int(i) for i in input().split()]
b = a.copy()
 
k = 0
for i in a:
    b[k] = abs(i - d)
    k += 1
 
m = min(b) 
 
def dec():
 
    i = m
    while i > 0:
        if m% i == 0: 
            k = 0
            for j in b:
                if j%i ==0:
                    k +=1
                if k==len(b):
                    return i
                
            if i == m:
                i -= i//2
                
        i -=1
 
 
 
 
                
print(dec())
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

diff = [0 for i in range(N)]
for i in range(N):
  diff[i] = V[i] - C[i]
diff = list(reversed(sorted(diff)))
i, ans = 0, 0
while diff[i] > 0:
  ans += diff[i]
  i += 1
print(ans)

### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0
for i in range(N):
  if V[i] > C[i]:
    ans += V[i] - C[i]
print(ans)
import math
r=int(input())
l=math.pi*r*2
s=(r**2)*math.pi
print("{0:5f} {1:5f}".format(l, s))

### FIXED CODE ###

import math
r=float(input())
l=math.pi*r*2
s=(r**2)*math.pi
print("{1:6f} {0:6f}".format(l, s))
A=input()
s = input()
C=input()
x = s[0].upper()
print("A"+x+"C")

### FIXED CODE ###

s=input()
print("A"+s[8]+"C")
import sys
import threading

S = int(input())
A = [-1 for _ in range(S+1)]
A[0] = 0
A[1] = 0
A[2] = 0
A[3] = 1
A[4] = 1
A[5] = 1

for i in range(S+1):
  if A[i] == -1:
    A[i] = A[i-1] + A[i-3]
print(A[S]%(10**9+7))

### FIXED CODE ###

import sys
import threading

S = int(input())
A = [-1 for _ in range(2001)]
A[0] = 0
A[1] = 0
A[2] = 0
A[3] = 1

for i in range(S+1):
  if A[i] == -1:
    A[i] = A[i-1] + A[i-3]

print(A[S]%(10**9+7))
n,x,y=map(int,input().split())
adlist=[[1,2]]
for i in range(n-2):
    adlist.append([i+1,i+2,i+3])
adlist.append([n-1,n])

adlist[x-1].append(y)
adlist[y-1].append(x)


def dfs(start,count,goal,finish,ans):
    finish.add(start)#もう訪れたところ
   
   # print(finish)
    if count==goal:
        #print("DFGH")
        ans+=1
        #print(ans)
        count=0
    for i in adlist[start-1]:
        #print("DFG")
        if i not in finish:#通ったところに入っていないなら通れるということ   
            #print(i)
            dfs(i,count+1,goal,finish,ans)
    return ans

#print(adlist)
global ans
for i in range(1,n):
    
    ans=0
    finish=set()
    print(dfs(1,0,i,finish,0))

#print(adlist)

### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0]*n
x -= 1
y -= 1
for i in range(n-1):
    for j in range(i+1, n):
        # print("DFGH")
        ans[min(j-i, abs(x-i)+abs(y-j)+1)] += 1

for i in range(1, n):
    print(ans[i])
import sys

def main():
    k = input().replace('\n','').split()
    a = input().replace('\n','').split()
    u = input().replace('\n','')
    a[k.index(u)]=int(a[k.index(u)]) - 1
    print(str(a[0]) + ' ' + a[1])
if __name__ == '__main__':
    input = sys.stdin.readline
    main()


### FIXED CODE ###

import sys

def main():
    k = input().replace('\n','').split()
    a = input().replace('\n','').split()
    u = input().replace('\n','')
    a[k.index(u)]=int(a[k.index(u)]) - 1
    print(str(a[0]) + ' ' + str(a[1]))
if __name__ == '__main__':
    input = sys.stdin.readline
    main()
a, b, k = map(int, input().split())
l1 = [i for i in range(1, a) if (a % i == 0)]
l2 = [i for i in range(1, b) if (b % i == 0)]
l = list(set(l1) & set(l2))
l.sort()
print(l[k-1])

### FIXED CODE ###

a, b, c = map(int, input().split())
print(b // a) if (b // a) < c else print(c)
import numpy as np
n,k,q=map(int,input().split())	
listA=[] #appendのために宣言が必要
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
a=np.repeat(k,n)
for word in listA:
    a[word]-=1
result=[]
for i in range(len(a)):
    if a[i]<=0:
        result.append('No')
    else:
        result.append('Yes')
print(result)

### FIXED CODE ###

import numpy as np
n,k,q=map(int,input().split())	
listA=[] #appendのために宣言が必要
while True:
    try:
        listA.append(int(input()))
    except:
        break;
a=np.repeat(k-q,n)
for word in listA:
    a[word-1]+=1
result=[]
for i in range(len(a)):
    if a[i]<=0:
        print('No')
    else:
        print('Yes')
n = input()
s = ''
for i in range(n):
  s += 'ACL'
print(s)

### FIXED CODE ###

n = int(input())
s = ''
for i in range(n):
  s += 'ACL'
print(s)
num = input()
get = num // 15

print((num * 800) - (get * 200))

### FIXED CODE ###

num = int(input())
get = num // 15

print((num * 800) - (get * 200))
X=input()
if X<30:
    print("No\n")
else:
    print("Yes\n")

### FIXED CODE ###

X=int(input())
if X<30:
    print("No")
else:
    print("Yes")
p = str(input())
s = list(p)
k = int(input())

ss = list(set(sorted(s)))
zis = []
for i in ss:
    zis.append(i)
    indexes = [p for p, x in enumerate(s) if x == i]            
    count = 0
    onedict = []
    
    for ii in range(len(indexes)):
        onedict.append(i)
        
    while count <= len(s)  + 1 and len(onedict) <= k + 1:
        count = count + 1
        
        if True:
            quint = indexes
            for sss in range(len(onedict)):
                try:
                    pppp = onedict[sss]
                    pppp = pppp + s[ int(quint[sss])+ count]
                    onedict.append(pppp)
                except:
                    pass
            for jj in onedict:
                zis.append(jj)


zissort = list(sorted(list(set(zis))))

print(zissort[k-1])
                


### FIXED CODE ###


s = str(input())
k = int(input())
kouho = [s]

for i in range(len(s)):
    for plus in range(k+1):
        st = s[i:i + plus]
        kouho.append(st)
so = list(sorted(set(kouho)))
if '' in so:
    so.remove('')
    
print(so[k-1])
N = int(input())
A = list(map(int,input().split()))
absA = [abs(i) for i in A]
minusA = [i for i in A if i<0]
mina = min(absA)
if (0 in A) or (len(minusA)%2 == 0):
    print(sum(absA))
else:
    print(absA -2*mina)
    

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
absA = [abs(i) for i in A]
minusA = [i for i in A if i<0]
mina = min(absA)
if (0 in A) or (len(minusA)%2 == 0):
    print(sum(absA))
else:
    print(sum(absA) -2*mina)
n = int(input())
x = int(input())
t = int(input())
print((n//x+1)*t)

### FIXED CODE ###

n, x, t = map(int, input().split())
if n % x == 0:
  print(int(n/x*t))
else:
  print(int((n//x+1)*t))
N,M = map(int, input().split())
appear_list = [[]for i in range(N)]
flag = 0
for i in range(M):
  s,c = map(int, input().split())
  appear_list[s-1].append(str(c))
ans = ""

for i in range(len(appear_list)):
  if len(set(appear_list[i])) > 1:
    flag = 1
    break
  elif len(set(appear_list[i])) == 1: 
    if appear_list[i][0] == "0" and len(ans) == 0 and i < (N-1):
      flag = 1
      break
    ans += appear_list[i][0]
  else:
    if len(ans) > 0:
	    ans += "0"
if flag == 0:
  print(int(ans))
else:
  print(-1)
  
  

### FIXED CODE ###

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

appear_list = [[]for i in range(N)]
flag = 0
ans = ""
for i in range(M):
  s,c = map(int, input().split())
  if len(appear_list[s-1]) == 0:
    appear_list[s-1].append(str(c))
  if len(appear_list[s-1]) ==1 and appear_list[s-1][0] != str(c):
    flag = 1
    break

for i in range(len(appear_list)):
  if i == 0:
    if len(appear_list[i]) == 0 and i != N-1:
      ans += "1"
    elif len(appear_list[i]) == 0 and i == N-1:
      ans += "0"
    elif appear_list[i][0] == "0" and i != N-1:
      flag = 1
      break
    else:
      ans += appear_list[i][0]
  else:
    if len(appear_list[i]) == 0:
      ans += "0"
    else:
      ans += appear_list[i][0]
if flag == 0:
  print(int(ans))
else:
  print(-1)
A, B, C = list(map(int, input().split()))
ABC = [A, B, C].sort()
A = ABC[0]
B = ABC[1]
C = ABC[2]

ans = 0

A = (C-A)//2
B =(C-B)//2

ans += (C-A)//2+(C-B)//2

if A == B == C:
    print(ans)
elif A ==C:
    print(ans+1)
else:
    print(ans+2)

### FIXED CODE ###

A, B, C = list(map(int, input().split()))
ABC = [A, B, C]
ABC.sort()
A = ABC[0]
B = ABC[1]
C = ABC[2]
ans = 0

if (C-A) >= 2:
    ans += (C-A)//2
    A += 2*((C-A)//2)
if (C-B) >= 2:
    ans += (C-B)//2
    B += 2*((C-B)//2)
 
if A == B == C:
    print(ans)
elif A ==B:
    print(ans+1)
else:
    print(ans+2)
n=int(input())
s=str(input())
for _ in range(n-1):
  s = s + str(input())
n=s.count("ABC")
print(n)

### FIXED CODE ###

n=int(input())
s=str(input())
print(s.count("ABC"))
#151c
n,w=map(int,input().split())
ac=0
wa=[0]*w
wa_cnt=0
ac_flg=[0]*n
for i in range(w):
	p,s=input().split()
	p=int(p)-1
	if ac_flg[p]==1:
		continue
	else:
		if s=='AC':
			ac_flg[p]=1
			ac+=1
			wa[p] +=wa_cnt
			wa_cnt=0
		else:
			wa_cnt+=1

wa_ans=0
for i in (n):
	wa_ans+=wa[i]

print(ac,wa_ans)

### FIXED CODE ###

#151c
n,w=map(int,input().split())
ac=0
wa=[0]*n
wa_cnt=[0]*n
ac_flg=[0]*n
for i in range(w):
	p,s=input().split()
	p=int(p)-1
	if ac_flg[p]==1:
		continue
	else:
		if s=='AC':
			ac_flg[p]=1
			ac+=1
			wa[p] =wa_cnt[p]
			#wa_cnt=0
		else:
			wa_cnt[p]+=1

wa_ans=0
for i in range(n):
	wa_ans+=wa[i]

print(ac,wa_ans)
import queue


# directions
x_dir = [0, 1, 0, -1]
y_dir = [1, 0, -1, 0]


visited = [[True for i in range(1000)] for j in range(1000)]
maps = []

# bfs algorithm
def bfs(h, w, cheese, sx, sy, moves):
    que = queue.Queue()
    que.put((moves, sx, sy))

    for i in range(h):
        for j in range(w):
            visited[i][j] = (maps[i][j] != 'X')

    visited[sy][sx] = False

    while que.qsize() > 0:
        c_moves, c_x, c_y = que.get()
        if maps[c_y][c_x] == cheese:
            return (c_moves, c_x, c_y)

        for i in range(4):
            n_x = c_x + x_dir[i]
            n_y = c_y + y_dir[i]

            if(0 <= n_x < w and 0 <= n_y < h and visited[n_y][n_x]):
                que.put((c_moves+1, n_x, n_y))
                visited[n_y][n_x] = False

    return (-1, -1, -1)


# simulate mouse
def simulate(h, w, n, sx, sy):
    moves = 0
    x, y = sx, sy

    #visited = [[True for i in range(w)] for j in range(h)]

    for i in range(1, n+1, 1):
        moves, x, y = bfs(h, w, str(i), x, y, moves)

    return str(moves)


# main function
def main():
    str = (input()).split()

    H = int(str[0])
    W = int(str[1])
    N = int(str[2])

    del str

    #maps = []
    sx, sy = 0, 0
    for i in range(H):
        maps.append(input())
        for j in range(W):
            if maps[i][j] == 'S':
                sx, sy = j, i

    print(simulate(H, W, N, sx, sy))


if __name__ == '__main__':
    main()

### FIXED CODE ###

# directions
x_dir = [0, 1, 0, -1]
y_dir = [1, 0, -1, 0]

# map info
visited = []
maps = []

# bfs algorithm
def bfs(h, w, cheese, sx, sy, moves):
    que = [(moves, sx, sy)]

    for i in range(h):
        for j in range(w):
            visited[i][j] = (maps[i][j] != 'X')

    visited[sy][sx] = False

    while len(que) > 0:
        c_moves, c_x, c_y = que.pop(0)
        if maps[c_y][c_x] == cheese:
            return (c_moves, c_x, c_y)

        for i in range(4):
            n_x = c_x + x_dir[i]
            n_y = c_y + y_dir[i]

            if(0 <= n_x < w and 0 <= n_y < h and visited[n_y][n_x]):
                que.append((c_moves+1, n_x, n_y))
                visited[n_y][n_x] = False

    return (-1, -1, -1)

# main function
if __name__ == '__main__':
    inputs = (input()).split()

    H = int(inputs[0])
    W = int(inputs[1])
    N = int(inputs[2])

    visited = [[True for i in range(W)] for j in range(H)]
    maps = ["" for i in range(H)]

    x, y = 0, 0
    for i in range(H):
        maps[i] = input()
        for j in range(W):
            if maps[i][j] == 'S':
                x, y = j, i

    moves = 0
    for i in range(1, N+1, 1):
        moves, x, y = bfs(H, W, str(i), x, y, moves)

    print(str(moves))
S, T = input().split()
a, b = map(int, input().split())
U = input().strip()
print(a - S == U, b - S == T)

### FIXED CODE ###

S, T = input().split()
a, b = map(int, input().split())
U = input().strip()
print(a - (S == U), b - (T == U))
N = int(input())　
if N <1000:
	print("ABC") 
else:
	print("ABD") 
	

### FIXED CODE ###

N = int(input())
if N <1000:
	print("ABC")
else:
	print("ABD")
import sys
import math

x, y = map(int, input().split())

if (2 * x - y) % 3 != 0 or (2 * y - x) % 3 != 0:
    print(0)
    sys.exit()

k = (2 * x - y) // 3
l = (2 * y - x) // 3

ans = math.factorial(k + l) // (math.factorial(k) * math.factorial(l))

print(ans % (10 ** 9 + 7))


### FIXED CODE ###

fac = [0] * 700000
finv = [0] * 700000
inv = [0] * 700000
mod = 1000000007

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, 700000):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod

x, y = map(int, input().split())

if (x + y) % 3 == 0:
    k = (2 * x - y) // 3
    l = (2 * y - x) // 3
    if k >= 0 and l >= 0:
        print(fac[k + l] * (finv[k] * finv[l] % mod) % mod)
    else:
        print(0)
else:
    print(0)
a, b, c = map(int,input().split())

print(mak(0,c-(a-b)))


### FIXED CODE ###

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

print(max(0,c-(a-b)))
N, K = map(int, input().split())
H = list(map(int, input().split()))


dp = [0 for _ in range(N)]
dp[1] = abs(H[1] - H[0])
# dp[i] = i+1につくまでの最小のコスト
for i in range(2, N):
    if i < K:
        A = [dp[i-k] + abs(H[i-k] - H[i]) for k in range(1, i+1)]
        dp[i] = min(A)
    else:
        A = [dp[i - k] + abs(H[i - k] - H[i]) for k in range(1, K+1)]
        dp[i] = min(A)


print(dp[-1])


### FIXED CODE ###

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


dp = [0 for _ in range(N)]
dp[1] = abs(H[1] - H[0])
# dp[i] = i+1につくまでの最小のコスト
for i in range(2, N):
    dp[i] = min((dp[i-1]+abs(H[i-1]-H[i])), (dp[i-2]+abs(H[i-2]-H[i])))


print(dp[-1])
N, *A = map(int, open('0').read().split())
l = 0
r = 0
s = A[l]
x = A[l]
ans = 0
flag = True
for l in range(N):
  while s==x and flag:
    r += 1
    if r==N:
      flag = False
      break
    s += A[r]
    x ^= A[r]
  ans += r-l
  s -= A[l]
  x ^= A[l]
print(ans)

### FIXED CODE ###

N = int(input())
INF = 1<<22
a = [int(c) for c in input().split()]+[INF]
l = 0
r = 1
s = a[l]
x = a[l]
ans = 0
for l in range(N):
  if l==r:
    r += 1
  while r<=N:
    if s!=x:
      break
#    print(a[r])
    s += a[r]
    x ^= a[r]
    r += 1
  s -= a[l]
  x ^= a[l]
  ans += r-l-1
#  print(l,r)
print(ans)