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

R,G,B,N = list(map(int,input().split()))
r_max = N//R+1
g_max = N//G+1
b_max = N//B+1
ans = 0
for r in range(r_max):
	g_max = (N-r*R)//G+1
	for g in range(g_max):
		if (N-r*R-g*G)%B == 0 and N-r*R-g*G >= 0:
			ans += 1
print(ans)


### FIXED CODE ###

R,G,B,N = list(map(int,input().split()))
r_max = N//R+1
ans = 0
for r in range(r_max):
	g_max = (N-r*R)//G+1
	for g in range(g_max):
		if (N-r*R-g*G)%B == 0:
			ans += 1
print(ans)
### BUGGY CODE ###

N,Y = map(int,input().split())
for yukichi in range(int(Y/10000)+1):
        for ichiyo in range(int(Y/5000)+1):
            hideyo = N-yukichi-ichiyo
            if(10000*yukichi+5000*ichiyo+1000*hideyo == Y and hideyo >= 0):
                print(yukichi,ichiyo,hideyo)
                exit()
print("-1 -1 -1")


### FIXED CODE ###

N,Y = map(int,input().split())
for yukichi in range(N+1):
        for ichiyo in range(N+1):
            hideyo = N-yukichi-ichiyo
            if(10000*yukichi+5000*ichiyo+1000*hideyo == Y and hideyo >= 0):
                print(yukichi,ichiyo,hideyo)
                exit()
print("-1 -1 -1")
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
from heapq import heapify, heappop, heappush
dis = []
for k in range(N):
  dis.append((-(A[k]-A[k]//2), k, 0))
heapify(dis)
while M:
  M -= 1
  item = heappop(dis)
  index = item[1]
  cnt = item[2] + 1
  discount = A[index]//pow(2, cnt) - A[index]//pow(2, cnt+1)
  heappush(dis, (-discount, index, cnt))

ans = 0
while dis:
  item = dis.pop()
  ans += A[item[1]]//pow(2, item[2])

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
from heapq import heapify, heappop, heappush
dis = []
for k in range(N):
  dis.append((-(A[k]-A[k]//2), k, 0))
heapify(dis)
while M:
  M -= 1
  item = heappop(dis)
  index = item[1]
  cnt = item[2] + 1
  discount = A[index]//pow(2, cnt) - A[index]//pow(2, cnt+1)
  heappush(dis, (-discount, index, cnt))

ans = 0
while dis:
  item = dis.pop()
  ans += A[item[1]]//pow(2, item[2])

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

a,b,c,k = map(int, input().split())
ans = 0
while(k>0):
  if a>0:
    a-=1
    ans += 1
  elif b>0:
    b-=1
  else:
    ans-=1
  k-=1
print(ans)

### FIXED CODE ###

a,b,c,k = map(int, input().split())
ans = 0
if k <= a:
  ans = k
elif k <= a+b:
  ans = a
else:
  ans = a-(k-a-b)
print(ans)
### BUGGY CODE ###

import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]

def dfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]
ans = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == '#':
            continue
        for gy in range(H):
            for gx in range(W):
                if S[gy][gx] == '#' or (sy==gy and sx==sy):
                    continue
                ans = max(ans,dfs(sy,sx,gy,gx))
print(ans)

### FIXED CODE ###

import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]

def dfs(sy, sx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist
ans = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == '#':
            continue
        d = dfs(sy,sx)
        for i in range(H):
            for k in range(W):
                ans = max(ans,d[i][k])
print(ans)
### BUGGY CODE ###

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

def gcd(a):
    k = []
    for i in range(1,a+1):
        if a%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

ka = gcd(a)
kb = gcd(b)

print(len(ka)+len(kb)-len(set(ka+kb)))

### FIXED CODE ###

def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}
 
a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
l = [1 for i in range(n) for j in range(i+1,n+1) if sum(A[i:j]) == 0]
print(sum(l))

### FIXED CODE ###

n = int(input())

S = [0]
for i,s in enumerate(input().split()):
    S.append(int(s)+S[i])
S.sort()
S.append(10000000000)
count = 0
p = S[0]
l = 0
for i in range(n+2):
    if p != S[i]:
        count += (i-l)*(i-l-1)//2
        l = i
        p = S[i]
print(count)
### BUGGY CODE ###

def fun(a, b, c):
    global ans
    for i in range(len(a)):
        for j in range(len(b)):
            if (a[i] > b[j]):
                continue
            for k in range(len(c)):
                if (b[j] > c[k]):
                    continue
                if b[j] - a[i] != c[k] - b[j]:
                    ans += 1


n = int(input())
s = input()
r = [0] * n
g = [0] * n
b = [0] * n
rr = 0
gg = 0
bb = 0
ans = 0
for i in range(n):
    if s[i] == "R":
        r[rr] = i
        rr += 1
    if s[i] == "G":
        g[gg] = i
        gg += 1
    if s[i] == "B":
        b[bb] = i
        bb += 1

r = r[:rr]
g = g[:gg]
b = b[:bb]

fun(r, g, b)
fun(r, b, g)
fun(g, r, b)
fun(g, b, r)
fun(b, r, g)
fun(b, g, r)

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
rr = 0
gg = 0
bb = 0
for i in range(n):
    if s[i] == "R":
        rr += 1
    if s[i] == "G":
        gg += 1
    if s[i] == "B":
        bb += 1

ans = rr * gg * bb

for j in range(n):
    for i in range(min(j+1, n-j)):
        if s[j - i] != s[j] and s[j] != s[j + i] and s[j + i] != s[j - i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())
count=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if (x+y+z)==s:
                count+=1
print(count)

### FIXED CODE ###

k,s=map(int,input().split())
count=0
z=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if(0<=z)&(z<=k):
            count+=1
            
print(count)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

def make_modinv_list(n, mod=10**9+7):
    inv_list = [0]*(n+1)
    inv_list[1] = 1
    for i in range(2, n+1):
        inv_list[i] = (mod - mod//i * inv_list[mod%i] % mod)
    return inv_list

mod = 998244353
N = int(readline())
A = list(map(int, readline().split()))
C = max(A) + 1
inv_list = make_modinv_list(C, mod)
h = [0] * C
for x in A:
    h[x] = (h[x] + x) % mod
for i in range(1, C):
    for j in range(i*2, C, i):
        h[i] = (h[i] + h[j]) % mod
g = [0] * C
for i in range(1, C):
    g[i] = h[i] * h[i] % mod
for i in range(C-1, 0, -1):
    for j in range(i*2, C, i):
        g[i] = (g[i] - g[j]) % mod
ans = 0
for i in range(1, C):
    ans = (ans + g[i] * inv_list[i]) % mod
ans -= sum(A)
print(ans * inv_list[2] % mod)    


### FIXED CODE ###

import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def solve():
  n = ni()
  a = nl()
  m = max(a)
  mod = 998244353
  l = [0]*(m+1)
  for x in a:
    l[x] += x
  sieve = [1]*(m+1)
  sieve[0] = sieve[1] = 0
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(m//i, 0, -1):
        sieve[j*i] = 0
        l[j] += l[j*i]
      sieve[i] = 1
  for i in range(m+1):
    l[i] = l[i] * l[i] % mod
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(1, m//i + 1):
        l[j] -= l[j*i]
  s = -sum(a)
  for i in range(1, m+1):
    if l[i]:
      s = (s + l[i] * modinv(i, mod)) % mod
  print(s * modinv(2, mod) % mod)
  return

solve()
### BUGGY CODE ###

n, k = list(map(int, input().split(' ')))
s = list(map(int, list(input())))
pres = []
i = 0
while i < n:
    ka = 0
    while s[i] == s[i+ka]:
        ka += 1
        if ka+i >= n:
            break
    pres.append([s[i],ka])
    i += ka
ia = 0
result = []
while ia < len(pres):
    h = 0
    if pres[ia][0] == 0:
        if ia + 2*k <= len(pres):
            for p in range(2*k):
                h += pres[p+ia][1]
            result.append(h)
        else:
            for p in range(len(pres)-ia):
                h += pres[p+ia][1]
            result.append(h)
    else:
        if ia + 2*k+1 <= len(pres):
            for p in range(2*k+1):
                h += pres[ia+p][1]
            result.append(h)
        else:
            for p in range(len(pres)-ia):
                h += pres[ia+p][1]
            result.append(h)
    ia += 1
print(max(result))

### FIXED CODE ###

n, k = map(int, input().split())
s = list(map(int, list(str(input()))))
c = 0
ran = [0,0]
for i in range(n):
    if s[c] == s[i]:
        ran[-1] += 1
    else:
        ran.append(i+1)
        c = i
result = []
for i in range(1, len(ran)):
    if s[ran[i-1]] == 1:
        result.append(ran[min(i+2*k,len(ran)-1)]-ran[i-1])
    else:
        result.append(ran[min(i+2*k-1, len(ran)-1)]-ran[i-1])
print(max(result))
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

ans = 0
p.sort(reverse = True)
q.sort(reverse = True)
r.sort(reverse = True)
p = p[:x]
q = q[:y]

P = sum(i for i in p)
Q = sum(j for j in q)
ans = P+Q
apples = p+q
apples.sort()
for i in range(len(r)):
  if apples[i] < r[0]:
    ans = ans-apples[i] + r[0]
    del r[0]
  else:
    break
print(ans)

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

ans = 0
p.sort(reverse = True)
q.sort(reverse = True)
r.sort(reverse = True)
p = p[:x]
q = q[:y]

P = sum(i for i in p)
Q = sum(j for j in q)
ans = P+Q
apples = p+q
apples.sort()
for i in range(len(r)):
  if apples[i] < r[0]:
    ans = ans-apples[i] + r[0]
    del r[0]
  else:
    break
print(ans)
### BUGGY CODE ###

s=input()
if len(s)<5:
  print(0)
  exit()
ans=0
for i in range(len(s)):
  j=i+4
  while j<len(s):
    if int(s[i:j+1])%2019==0:
      ans+=1
    j+=1
print(ans)

### FIXED CODE ###

s=input()
res=0
t=1
p=[0]*2019
for i in map(int,s[::-1]):
  res+=i*t
  res%=2019
  p[res]+=1
  t*=10
  t%=2019
print(p[0]+sum((i*(i-1)//2) for i in p))
### BUGGY CODE ###

import numpy as np

N = int(input())
S = np.array(list(input()))

R = (S=='R').sum()
G = (S=='G').sum()
B = N - R - G

ans = R * G * B

for i in range(0, N-2):
  for j in range(i+1,N-1):
    k = 2 * j - i
    if k >= N:
      break
    else:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        ans -= 1

print(ans)

### FIXED CODE ###

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

R = S.count('R')
G = S.count('G')
B = N - R - G

ans = R * G * B

for i in range(0, N-2):
  for j in range(i+1,N-1):
    k = 2 * j - i
    if k >= N:
      break
    else:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        ans -= 1

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

N = int(input())
A = list(map(int, input().split()))
x = 0
m = A[0]

for x in range(1, N):
    m *= A[x]
if m > 10**18:
    m = -1
print(m)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))

    if 0 in A:
        print(0)
        return

    m = 1
    for x in A:
        m *= x
        if m > 10**18:
            print(-1)
            return
    print(m)
main()
### BUGGY CODE ###

x = input()
i = 1
while (x != '0'):
 print("Case{}: {}".format(i, x));
 i += 1;

### FIXED CODE ###

i = 1
while True:
    x = int(input().strip())
    if x == 0:
        break
    else:
        print ("Case {}: {}".format(i,x))
        i += 1
### BUGGY CODE ###

from itertools import permutations
n, m, r = map(int, input().split())
list_r = [one_r-1 for one_r in map(int, input().split())]

dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
  dist[i][i] = 0
for i in range(m):
  a, b, c = map(int, input().split())
  dist[a-1][b-1] = c
  dist[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      if dist[i][j] > dist[i][k] + dist[k][j]:
        dist[i][j] = dist[i][k] + dist[k][j]

result = float("inf")
for one_cand in permutations(list_r):
  temp = 0
  for i in range(r-1):
    temp += dist[one_cand[i]][one_cand[i+1]]
  if temp < result:
    result = temp
print(result)

### FIXED CODE ###

from itertools import permutations
import sys

def main():
    
    N, M, R = map(int, sys.stdin.readline().split())
    r = [i - 1 for i in map(int, sys.stdin.readline().split())]
    
    d = [[float('inf')] * N for _ in range(N)]
    
    for i in range(N):
        d[i][i] = 0
        
    for i in range(M):
        a, b, c = map(int,sys.stdin.readline().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
        
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    ans = 10**12
    
    for each in permutations(r):
        t_dis = 0
        for i in range(R-1):
            t_dis += d[each[i]][each[i+1]]  
        
        ans = min(ans, t_dis)
    
    print(ans)

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

N=int(input())
 
A=list(map(int,input().split()))
 
result=1
for a in A:
    result=result*a
if result>10**18:
    result=-1
print(result)

### FIXED CODE ###

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

if 0 in A:
    print(0)
else:
    result=1
    for a in A:
        result=result*a
        if result>10**18:
            result=-1
            break
    print(result)
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
# https://twitter.com/maspy_stars/status/1185552225474498560
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def test(k):
    bc = np.bincount(A)
    bc.sort()
    bc = bc[np.searchsorted(bc, 1):]
    bc = bc[::-1]
    ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    return ret


C = np.bincount(A)
C.sort()


def solve(k):
    cnt = N // k
    if C[-1] <= cnt:
        # 全部取れるとしていい
        # 最後に2つ以上余ると max_c <= cnt に矛盾する
        return cnt

    S = N
    i = 1
    while i < k:
        # 最大値は毎回取ることにしてもう見ない
        S -= C[-i]
        cnt = S // (k - i)
        max_c = C[-i - 1]
        if max_c <= cnt:
            return cnt
        i += 1
    return 0


ans = [0] * N
for k in reversed(range(1, N + 1)):
    ans[k - 1] = test(k)
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
# https://twitter.com/maspy_stars/status/1185552225474498560
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def test(k):
    bc = np.bincount(A)
    bc.sort()
    bc = bc[np.searchsorted(bc, 1):]
    bc = bc[::-1]
    ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    return ret


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    s = 0
    ret = []
    for a in it:
        s += a
        ret.append(s)
    return ret


C = [0] * (N + 1)
for a in A:
    C[a] += 1
C.sort()
cs = list(reversed(cumsum(reversed(C))))


def solve(k):
    cnt = N // k
    if C[-1] <= cnt:
        # 全部取れるとしていい
        # 最後に2つ以上余ると max_c <= cnt に矛盾する
        return cnt

    # S = N
    # i = 1
    # while i < k:
    #     # 最大値は毎回取ることにしてもう見ない
    #     S -= C[-i]
    #     cnt = S // (k - i)
    #     max_c = C[-i - 1]
    #     if max_c <= cnt:
    #         return cnt
    #     i += 1

    ng = 0
    ok = k
    while abs(ng - ok) > 1:
        i = (ng + ok) // 2
        s = N - cs[-i]
        cnt = s // (k - i)
        max_c = C[-i - 1]
        if max_c <= cnt:
            ok = i
        else:
            ng = i
    if ok < k:
        i = ok
        s = N - cs[-i]
        return s // (k - i)
    else:
        return 0


ans = [0] * N
for k in reversed(range(1, N + 1)):
    ans[k - 1] = solve(k)
print(*ans, sep='\n')
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))

costs = [0] * N
for i in range(1,N):
  s = max(i-K, 0)
  tmp = [float('inf') for _ in range(K)]
  for j in range(s,i):
    tmp[j-s] = costs[j] + abs(h[i] - h[j])
  costs[i] = min(tmp)
print(costs[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))

def aa (n,k,ll):
  dp = [0] * n
  for i in range(1,n):
    s = max(i-k,0)
    mn = float('inf')
    for a,b in zip(dp[s:i],ll[s:i]):
      cur = a + abs(ll[i]-b)
      if cur < mn:
        mn = cur
  
    dp[i] = mn
  print(dp[-1])

aa(N,K,h)
### BUGGY CODE ###

n=int(input())
a=input().split()
for i in range(n):
	a[i]=int(a[i])
sp=' '
ans=''
for i in range(1,n+1):
	if i!=1:
		ans+=sp
	ans+=str(a.index(i)+1)
print(ans)

### FIXED CODE ###

n=int(input())
a=input().split()
lans=[int(i) for i in range(n)]
sp=' '
ans=''

for i in range(n):
	lans[int(a[i])-1]=i+1
ans+=str(lans[0])
for i in range(1,n):
	ans+=sp
	ans+=str(lans[i])
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
def get_(h,k):
    for i in range(n-k+1):
        yield h[i:k+i]
a=list(get_(h,k))
ans=10**9+1
for i in a:
    if max(i)-min(i)<ans:
        ans=max(i)-min(i)
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()

print(min(h[i+k-1] - h[i] for i in range(n-k+1)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
Amin = min(A)
tmp = sorted([list(map(int,input().split())) for i in range(M)],key = lambda x:-x[1])

cnt = 0
t = []
for i in range(M):
    t=t+[tmp[i][1]]*tmp[i][0]
    cnt+= tmp[i][0]
    if cnt >=N:
        break
    if cnt<N and tmp[i][1] <= A[cnt-1]:
        break
for i in range(min(N,len(t))):
    if A[i] < t[i]:
        A[i] = t[i]
print(sum(A))



### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
r = np.array(range(N))
#r1 = np.array(range(1,N+1))
#r2 = np.array(range(N,0,-1))
#X = (A-r1)
#Y = (A-r2)
#print(X)
#print(Y)
ans = 0
for i in range(N):
  X = A+A[i]
  #r1 = np.array(range(-i,N-i))
  #r2 = r1*(-1)
  ans += sum((X+r-i)==0)
  ans += sum((X-r+i)==0)
  #ans += (sum((X-X[i]*(1))==0)-1)
  #ans += (sum((Y-Y[i]*(1))==0)-1)
print(ans//2)


### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
r = np.array(range(N))
X = r+A
Y = r-A
ans = 0
x_dic = {}
y_dic = {}
for x in X:
    if x in x_dic:
        x_dic[x] += 1
    else:
        x_dic[x] = 1
  
for y in Y:
    if y in y_dic:
        y_dic[y] += 1
    else:
        y_dic[y] = 1

for x in x_dic:
    if x in y_dic:
        ans += x_dic[x]*y_dic[x]        
print(ans)
#print(X,x_dic,Y,y_dic)
### BUGGY CODE ###

n = int(input())

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

lines = []
t = 0
lines.append((-1,0,0))
for i in range(1,n+1):
    lines.append((t,t+time[i],v[i]))
    t+=time[i]
lines.append((t,t+1,0))
def f(x):
    speed = 10**18
    for x1,x2,vv in lines:
        if x<x1:
            speed = min(speed,vv+x1-x)
        elif x>x2:
            speed = min(speed,vv+x-x2)
        else:
            speed = min(speed,vv)
    return speed
dp = [0]*(2*t)
for i in range(2*t):
    dp[i] = f(i/2)
dp.append(0)
res = 0
for a in range(2*t):
    res += (dp[a]+dp[a+1])
print(res*0.25)


### FIXED CODE ###

n = int(input())

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

lines = []
t = 0
lines.append((-1,0,0))
for i in range(1,n+1):
    lines.append((t,t+time[i],v[i]))
    t+=time[i]
lines.append((t,t+1,0))
def f(x):
    speed = 10**18
    for x1,x2,vv in lines:
        if x<x1:
            speed = min(speed,vv+x1-x)
        elif x>x2:
            speed = min(speed,vv+x-x2)
        else:
            speed = min(speed,vv)
    return speed
dp = [0]*(2*t)
for i in range(2*t):
    dp[i] = f(i/2)
dp.append(0)
res = 0
res = sum(dp)*2-dp[0]-dp[-1]
print(res*0.25)
### BUGGY CODE ###

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

n = int(input())
node_list = []
nodes = [[] for _ in range(n)]
edges = dict()
for _ in range(n - 1):
	a, b = map(int, input().split())
	node_list.append((a - 1, b - 1))
	nodes[a - 1].append(b - 1)
	nodes[b - 1].append(a - 1)
	edges[(a - 1, b - 1)] = 0

used = [False] * n
que = deque()
que.append(0)
while len(que) > 0:
	ni = que.pop()
	if used[ni]:
		continue
	used_colors = [edges[tuple(sorted((ni, e)))] for e in nodes[ni]]
	unused = deque([c for c in range(n, 0, -1) if not c in used_colors])
	for node in nodes[ni]:
		[a, b] = sorted([ni, node])
		if edges[(a, b)] == 0:
			edges[(a, b)] = unused.pop()
		que.append(node)

	used[ni] = True

print(max(edges.values()))
for node in node_list:
	print(edges[node])


### FIXED CODE ###

from collections import deque

n = int(input())
nodes = [[] for _ in range(n)]
node_list = []
for _ in range(n - 1):
	a, b = map(int, input().split())
	nodes[a - 1].append(b - 1)
	node_list.append(b - 1)
 
que = deque([0])
ans = [0] * n
while len(que) > 0:
	ni = que.pop()
	color = 1
	for node in nodes[ni]:
		if color == ans[ni]:
			color += 1
		ans[node] = color
		color += 1
		que.append(node)
 
print(max(ans))
for node in node_list:
	print(ans[node])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N, M = list(map(int, input().split()))
G = [[] for _ in range(N)]

for _ in range(M):
    x, y = list(map(lambda x: int(x) - 1, input().split()))
    G[x].append(y)

dp = [-1]*(N)

def f(v):
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for nv in G[v]:
        ans = max(ans, f(nv) + 1)
    return ans

for i in range(N):
    dp[i] = f(i)

print(max(dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N, M = list(map(int, input().split()))
G = [[] for _ in range(N)]

for _ in range(M):
    x, y = list(map(lambda x: int(x) - 1, input().split()))
    G[x].append(y)

dp = [-1]*(N)

def f(v):
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for nv in G[v]:
        ans = max(ans, f(nv) + 1)
    dp[v] = ans
    return ans

ans = 0
for i in range(N):
    ans = max(ans, f(i))

print(max(dp))