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

from math import sqrt
from collections import defaultdict

N = int(input())
dic = defaultdict(int)

def func(N):
  if N == 1:
    return 1
  
  for i in range(2, N+1):
    if N % i == 0:
      N = N // i
      dic[i] += 1
      return func(N)

func(N)

def func2(k):
  n = 1
  count = 1
  while count * (count+1) // 2 <= k:
    count += 1
  return count-1

res = 0

for value in dic.values():
  if value > 0:
    res += func2(value)

print(res)

### FIXED CODE ###

from math import sqrt
from collections import defaultdict

N = int(input())

def prime_factorize(n):
    a = defaultdict(int)
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a
  
ps = prime_factorize(N)

def func2(k):
  n = 1
  count = 1
  while count * (count+1) // 2 <= k:
    count += 1
  return count-1

res = 0

for value in ps.values():
  if value > 0:
    res += func2(value)

print(res)
### BUGGY CODE ###

from statistics import median_low

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

for i in range(len(xs)):
    print(median_low(xs[0:i] + xs[i+1:len(xs)]))


### FIXED CODE ###

# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import collections
import math
import numpy as np

#### START
n = int(input())
li = list(map(int,input().split()))
s_li = sorted(li)
left_num = s_li[n//2-1]
right_num = s_li[n//2]
for i in li:
    if i>left_num:
        print(left_num)
    else:
        print(right_num)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(c[i] + 1)/ 2 for i in range(a)]
e = [sum(d[i:b + i]) for i in range(a - b + 1)]
g = max(e)
print(g)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = sum(d[:b])
f = e
for i in range(a - b):
	f -= d[i]
	f += d[i + b]
	if f > e:
		e = f
print(e)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N=I()
  A=LI()

  g=0
  for x in A:
    g=math.gcd(g,x)
  if g>1:
    return 'not coprime'

  sosu=[0]*1000100
  for x in A:
    if x==1:
      continue
    sosu[x]+=1
    if sosu[x]>1:
      return 'setwise coprime'
    for y in range(2,int(math.sqrt(x))+1):
      if x%y!=0:
        continue
      z=x//y
      if y==z:
        sosu[y]+=1
        if sosu[y]>1:
          return 'setwise coprime'
      else:
        sosu[y]+=1
        if sosu[y]>1:
          return 'setwise coprime'
        sosu[z]+=1
        if sosu[z]>1:
          return 'setwise coprime'

  return 'pairwise coprime'

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N=I()
  A=LI()

  g=0
  for x in A:
    g=math.gcd(g,x)
  if g>1:
    return 'not coprime'

  sosu=[0]*1000100
  for x in A:
    if x==1:
      continue
    sosu[x]+=1
    if sosu[x]>1:
      return 'setwise coprime'
    for y in range(2,int(math.sqrt(x))+1):
      if x%y!=0:
        continue
      z=x//y
      if y==z:
        sosu[y]+=1
        if sosu[y]>1:
          return 'setwise coprime'
      else:
        sosu[y]+=1
        if sosu[y]>1:
          return 'setwise coprime'
        sosu[z]+=1
        if sosu[z]>1:
          return 'setwise coprime'

  return 'pairwise coprime'

# main()
print(main())
### BUGGY CODE ###

# ABC 158 D
S=list(input())
Q=int(input())
inv=0
for _ in [0]*Q:
    s=input()
    if s=='1':
        inv+=1
    else:
        t,f,c=s.split()
        if ((f=='1') ^ (inv%2==1)):
            S=[c]+S
        else:
            S=S+[c]
if inv%2:
    S=S[::-1]
print(*S,sep='')

### FIXED CODE ###

# ABC 158 D
from collections import deque

S=list(input())
q=deque(S)
Q=int(input())
inv=0
for _ in [0]*Q:
    s=input()
    if s=='1':
        inv+=1
    else:
        t,f,c=s.split()
        if ((f=='1') ^ (inv%2==1)):
            q.appendleft(c)
        else:
            q.append(c)
S=[]
if inv%2:
    while q:
        S.append(q.pop())
else:
    while q:
        S.append(q.popleft())
    
print(*S,sep='')
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={(i,b-1)}
    IN[b-1]|={i}
P=[0]*N
while len(start)>0:
    now=start.pop()
    for b,nex in OUT[now]:
        IN[nex].remove(b)
        if len(IN[nex])==0:
            start|={nex}
            P[nex]=now+1
for p in P:
    print(p)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(int)
for i in range(N+M-1):
    a,b=map(int,input().split())
    OUT[a-1]|={b-1}
    IN[b-1]+=1
P=[0]*N
start={i for i in range(N) if IN[i]==0}
while len(start)>0:
    now=start.pop()
    for nex in OUT[now]:
        IN[nex]-=1
        if IN[nex]==0:
            start|={nex}
            P[nex]=now+1
[print(p) for p in P]
### BUGGY CODE ###

k, s = map(int, input().split())
li = []
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if z == s - (x + y):
                li.append('{} {} {}'.format(x, y, z))
li
print(len(set(li)))

### FIXED CODE ###

k, s = map(int, input().split())
li = []
a=0
for x in range(k+1):
    for y in range(k+1):
            if 0 <= s - (x + y) <= k:
                a += 1
a
print(a)
### BUGGY CODE ###

import numpy as np
a,b,q = map(int,input().split())
s = np.array([int(input()) for i in range(a)])
t = np.array([int(input()) for i in range(b)])
x = np.array([int(input()) for i in range(q)])

def distance(s,t,xi):
  s_ = s-xi
  if len(s_[s_<=0])!=0:
    s_m = s_[s_<=0].max()
  else:
    s_m =-np.inf
  if len(s_[s_>=0]) !=0:
    s_p = s_[s_>=0].min()
  else:
    s_p = np.inf
    
  t_ = t-xi
  if len(t_[t_<=0])!=0:
    t_m = t_[t_<=0].max()
  else:
    t_m = -np.inf
  if len(t_[t_>=0]) !=0:
    t_p = t_[t_>=0].min()
  else:
    t_p = np.inf
  return min(abs(min(s_m,t_m)),abs(t_p-s_m)+min(abs(t_p),abs(s_m))\
         ,abs(max(t_p,s_p)),abs(s_p-t_m)+min(abs(s_p),abs(s_p)))
 
for i in x:
  print(distance(s,t,i))

### FIXED CODE ###

import numpy as np
import bisect
a,b,q = map(int,input().split())
s = np.array([-np.inf]+[int(input()) for i in range(a)]+[np.inf])
t = np.array([-np.inf]+[int(input()) for i in range(b)]+[np.inf])
x = np.array([int(input()) for i in range(q)])


  
def distance(s,t,xi):
  s_ = bisect.bisect_left(s,xi)
  s_m = abs(s[s_-1]-xi)
  s_p = abs(s[s_]-xi)
  t_ = bisect.bisect_left(t,xi)
  t_m = abs(t[t_-1]-xi)
  t_p = abs(t[t_]-xi)
  
  return min(max(s_m,t_m),s_m+t_p+min(s_m,t_p),s_p+t_m+min(s_p,t_m),max(s_p,t_p))
 
for i in x:
  print(int(distance(s,t,i)))
### BUGGY CODE ###

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

ans=1

for num in a:
    ans*=num

Inf=10**18

if ans>Inf:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

Inf=10**18

if zero>=1:
    print(0)
else:
    ans=1
    a.sort(reverse=True)
    for num in a:
        ans*=num
        if ans>Inf:
            print(-1)
            exit()
    
    print(ans)
### BUGGY CODE ###

kazu, hissatu = map(int,input().split())
hairetu = list(map(int,input().split()))

toru = kazu-hissatu

if toru<=0:
  print(0)
else:
  for i in range(hissatu):
    hairetu.remove(max(hairetu))
  print(sum(hairetu))

### FIXED CODE ###

kazu, hissatu = map(int,input().split())
hairetu = list(map(int,input().split()))

toru = kazu-hissatu

if toru<=0:
  print(0)
else:
  hairetu.sort()
  print(sum(hairetu[:(kazu)-hissatu]))
### BUGGY CODE ###

n = int(input())
s = list(str(input()))
q = int(input())

def segfunc(x,y):
    return x | y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=set(init_val[i])
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = set(y)
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = list(str(input()))
q = int(input())

s = [ord(c)-ord('a') for c in s]

#def segfunc(x,y):
    #return x | y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]={init_val[i]}
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1] | seg[2*i+2]

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = seg[k*2+1] | seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = (res | seg[p]) | seg[q]
    return res

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, sys.stdin.readline().split())
    if t == '2':
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))
    else:
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
### BUGGY CODE ###

import sys
import bisect

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = MAP()
B = MAP()
C = MAP()

A.sort()
B.sort()
C.sort()

cand_a = [0] * N
for i,a in enumerate(A):
	cand_a[i] = N - bisect.bisect_right(B, a)

cand_b = [0] * N
for i,b in enumerate(B):
	cand_b[i] = N - bisect.bisect_right(C, b)

cand_c = [0] * N
for i,b in enumerate(cand_b):
	cand_c[i] = sum(cand_b[i:])

ans = sum([cand_c[N-a] for a in cand_a if a])
print(ans)

### FIXED CODE ###

import sys
import bisect
import numpy as np

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = MAP()
B = MAP()
C = MAP()

A.sort()
B.sort()
C.sort()

cand_a = [0] * N
for i,a in enumerate(A):
	cand_a[i] = N - bisect.bisect_right(B, a)
#print(cand_a)

cand_b = [0] * N
for i,b in enumerate(B):
	cand_b[i] = N - bisect.bisect_right(C, b)
	
cand_b = list(np.cumsum(list(reversed(cand_b))))
#print(cand_b)

ans = 0
for a in cand_a:
	if a: ans += cand_b[a-1]

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

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

count = 0
while(1):
  if sum(lis) % 2 == 1:
    print(count)

### FIXED CODE ###

import numpy as np

N = int(input())

lis = np.array(list(map(int, input().split())))

count = 0
while(1):
  if np.mod(lis, 2).sum() != 0:
    print(count)
    break
  else:
    lis = lis // 2
  count = count + 1
### BUGGY CODE ###

from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    num = 0
    mods = Counter()
    for i, s in enumerate(reversed(S)):
        num += int(s) * (10 ** i)
        mods[num % P] += 1
    mods[0] += 1
    for i, s in enumerate(S):
        c = num % P
        cnt += mods[c] - 1
        mods[c] -= 1
        num -= int(s) * (10 ** (N - 1 - i))

print(cnt)


### FIXED CODE ###

from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    T = [0] * (N + 1)
    mods = Counter({0: 1})
    for i, s in enumerate(reversed(S)):
        T[N - 1 - i] = (T[N - i] + int(s) * pow(10, i, P)) % P
        mods[T[N - 1 - i]] += 1
    for t in T:
        mods[t] -= 1
        cnt += mods[t]

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

z=int(input())
i=1
re=0
f=3
b=1
while z>i:
  b=1
  while True:
    x=i*b
    if z>x:
      re+=1
    else:
      break
    b+=1
  i+=1
print(re)

### FIXED CODE ###

z=int(input())
i=1
re=0
b=1
d=1
while z>i:
  b=1
  while True:
    x=i*(i+b)
    if z>x:
      re+=2
    else:
      break
    b+=1
  i+=1
while True:
  if d*d<z:
    d+=1
    re+=1
  else:
    break
print(re)
### BUGGY CODE ###

dic = {}
h, w, d = map(int, input().split())
lis = [list(input().split()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        dic[int(lis[i][j])] = (i, j)
q = int(input())
for i in range(q):
    s, g = map(int, input().split())
    cnt = s
    res = 0
    while cnt < g:
        x = dic[cnt + d][0] - dic[cnt][0]
        y = dic[cnt + d][1] - dic[cnt][1]
        res += abs(x) + abs(y)
        cnt += d
    print(res)


### FIXED CODE ###

dic = {}
h, w, d = map(int, input().split())
lis = [list(input().split()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        dic[int(lis[i][j])] = (i, j)
n = h * w
su = [0] * (n + 1)
for k in range(1, n - d + 1):
    x = dic[k + d][0] - dic[k][0]
    y = dic[k + d][1] - dic[k][1]
    su[k + d] = su[k] + abs(x) + abs(y)

q = int(input())
for i in range(q):
    s, g = map(int, input().split())
    print(su[g] - su[s])
### BUGGY CODE ###

n,a = (int(i) for i in input().split())
x = list(int(i) for i in input().split())
count = 0
for i in x:
    if i == 8:
        count+=1
res = 0
for i in range(1,2**n):
    bit = bin(i)[2:]
    k = bit.count("1")
    sum = 0
    for i in range(1,len(bit)+1):
        if bit[-i]=="1":
            sum += x[-i]
    if sum==a*k:
        res += 1

print(res)
    

### FIXED CODE ###

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

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


X = max(max(x), A)

dp = [[0 for i in range(2*N*X+1)] for j in range(N+1)]

dp[0][N*X] = 1

y = []

for i in range(N):
    tmp = x[i]-A
    y.append(tmp)

for i in range(N):
    for j in range(2*N*X+1):
        if j-y[i]<0 or j-y[i]>2*N*X:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j] + dp[i][j-y[i]]
            
print(dp[N][N*X]-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

mod = 10**9+7

kkai = [1]
for i in range(1, 10 ** 6):
    kkai.append(kkai[-1] * i % mod)


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    if b == 0:
        return 1
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


child = [0] * n


def dfs1(i=0, r=-1):
    s = 1
    for j in e[i]:
        if j == r:
            continue
        s += dfs1(j, i)
    child[i] = s
    return s


dfs1()

a = [0] * n


def dfs2(i=0, r=-1):
    s = 1
    t = 0
    for j in e[i]:
        if j == r:
            continue
        t += child[j]
        s *= dfs2(j, i)
        s %= mod
        s *= comb(t, child[j])
        s %= mod
    a[i] = s
    return s


dfs2()

b = [0] * n


def dfs3(i=0, r=-1):
    if r == -1:
        b[i] = a[i]
    else:
        s = b[r] * comb(n-1, child[i]-1) % mod
        re = comb(n-1, child[i])
        s *= pow(re, mod - 2, mod)
        s %= mod
        b[i] = s

    for j in e[i]:
        if j == r:
            continue
        dfs3(j, i)


dfs3()

print("\n".join(map(str, b)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

mod = 10**9+7

kkai = [1]
for i in range(1, 2*10 ** 5):
    kkai.append(kkai[-1] * i % mod)


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    if b == 0:
        return 1
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


child = [0] * n


def dfs1(i=0, r=-1):
    s = 1
    for j in e[i]:
        if j == r:
            continue
        s += dfs1(j, i)
    child[i] = s
    return s


dfs1()
a = [0] * n


def dfs2(i=0, r=-1):
    s = kai(child[i]-1)
    t = 1
    for j in e[i]:
        if j == r:
            continue
        s *= dfs2(j, i)
        s %= mod
        t *= kai(child[j])
        t %= mod
    s *= pow(t, mod - 2, mod)
    s %= mod
    a[i] = s
    return s


dfs2()
b = [0] * n


def dfs3(i=0, r=-1):
    if r == -1:
        b[i] = a[i]
    else:
        s = b[r] * child[i] % mod
        s *= pow(n-child[i], mod - 2, mod)
        s %= mod
        b[i] = s

    for j in e[i]:
        if j == r:
            continue
        dfs3(j, i)


dfs3()
print("\n".join(map(str, b)))
### BUGGY CODE ###

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

if a <= 0 and b >= 0:
    print("Zero")
else:
    for i in range(b - a + 1):
        if a + i < 0:
            c *= -1
    if c == 1:
        print("Positive")
    else:
        print("Negative")

### FIXED CODE ###

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

if a <= 0 and b >= 0:
    print("Zero")
elif a > 0:
    print("Positive")
else:
    if (b - a + 1) % 2 == 0:
        print("Positive")
    else:
        print("Negative")
### BUGGY CODE ###

import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    counter = 1
    while counter != n:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
        counter += 1
    return res

#########################
n = int(input())

#隣接リストの作成 edge[i]:[コスト,行先]
edge = [[] for i in range(n)]
p = [[0,0,0] for i in range(n)]
for i in range(n):
    X,Y = map(int,input().split())
    p[i] = [X,Y,i]
x_sort=sorted(p,key=lambda x:x[0])
y_sort=sorted(p,key=lambda x:x[1])
for i in range(1,n):
    edge[x_sort[i][2]].append([min(abs(x_sort[i][0]-x_sort[i-1][0]),abs(x_sort[i][1]-x_sort[i-1][1])),x_sort[i-1][2]])
    edge[x_sort[i-1][2]].append([min(abs(x_sort[i][0]-x_sort[i-1][0]),abs(x_sort[i][1]-x_sort[i-1][1])),x_sort[i][2]])
    edge[y_sort[i][2]].append([min(abs(y_sort[i][0]-y_sort[i-1][0]),abs(y_sort[i][1]-y_sort[i-1][1])),y_sort[i-1][2]])
    edge[y_sort[i][2]].append([min(abs(y_sort[i][0]-y_sort[i-1][0]),abs(y_sort[i][1]-y_sort[i-1][1])),y_sort[i-1][2]])
print(prim_heap())

### FIXED CODE ###

import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################
n = int(input())

#隣接リストの作成 edge[i]:[コスト,行先]
edge = [[] for i in range(n)]
p=[]
edge=[[] for i in range(n)]
for i in range(n):
    p.append(tuple(map(int,input().split()))+tuple([i]))
x_sorted=sorted(p,key=lambda x:x[0])
y_sorted=sorted(p,key=lambda x:x[1])
for i in range(n-1):
    edge[x_sorted[i][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i+1][2]))
    edge[x_sorted[i+1][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i][2]))
    edge[y_sorted[i][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i+1][2]))
    edge[y_sorted[i+1][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i][2]))

print(prim_heap())
### BUGGY CODE ###

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

u = s + s[::-1]
ss = s

for i in range(k):
    for j in range(n):
        part = u[j:j+n]
        if u[j:j+n] < ss:
            ss = part
    s = ss
    u = s[::-1] + s

print(s)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

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

u = s + s[::-1]
ss = s

if n < k**2:
    smallest = sorted(s)[0]
    print(smallest * n)

else:
    times = min(n, k)
    for i in range(times):
        for j in range(n):
            part = u[j:j+n]
            if part < ss:
                ss = part
        s = ss
        u = s[::-1] + s
    print(s)
### BUGGY CODE ###

alen = input()
ai = input()
alen,ai = int(alen), [int(i) for i in ai.split(" ")]
print(sum([sum([1 if k==0 else 0 for k in [sum(ai[i:j]) for j in range(i+1,alen+1)]]) for i in range(alen)]))


### FIXED CODE ###

a=int(input())
b=list(map(int, input().split(" ")))
c=0
d=0
e={0:1}
for i in b:
 c+=i
 d+=e.get(c,0)
 e[c]=e.get(c,0)+1

print(d)