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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
c=Counter(lis)
dp=[[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
def dfs(x,y,z):
    if x+y+z>n or (x<0 or y<0 or z<0) or (x>n or y>n or z>n):
        return 0
    elif dp[x][y][z]>=0:
        return dp[x][y][z]
    else:
        dp[x][y][z]=(n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
        return (n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
print(dfs(c[1],c[2],c[3]))
'''print(dp[0])
print(dp[1])
print(dp[2])
print(dp[3])'''
#print(dp[c[1]][c[2]][c[3]])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # 0個の皿がx0枚、1個の皿がx1枚、2個の皿がx2枚、3個の皿がx3枚
    # x0=n-x1-x2-x3
    ca={1:a.count(1),2:a.count(2),3:a.count(3)}
    memo=[[[-1]*(n+2) for _ in range(n+2)] for _ in range(n+2)]
    memo[0][0][0]=0
    for x3 in range(ca[3]+1):
        for x2 in range(ca[2]+ca[3]+1-x3):
            for x1 in range(ca[1]+ca[2]+ca[3]+1-x3-x2):
                if (x1,x2,x3)==(0,0,0):continue
                tmp=0
                if x1>0:tmp+=memo[x1-1][x2][x3]*x1
                if x2>0:tmp+=memo[x1+1][x2-1][x3]*x2
                if x3>0:tmp+=memo[x1][x2+1][x3-1]*x3
                tmp+=n
                tmp/=x1+x2+x3
                memo[x1][x2][x3]=tmp
    print(memo[ca[1]][ca[2]][ca[3]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

import numpy as np
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
#s = np.array(s)
#s = (s == ".") * 1
def neext(a):
    l, m = a[0], a[1]
    return [(l, m+1), (l, m-1), (l+1, m), (l-1, m)]
def solve(i, j):
    if s[i][j] == '#':
        return 0
    else:
        pre = 0
        p = [[-1] * w for _ in range(h)]
        check = deque([((i, j), 0)])#(from,now, dist)
        while check:
            now, d = check.popleft()
            p[now[0]][now[1]] = d
            pre = max(pre, d)
            for b, c in neext((now[0], now[1])):
                if b < 0 or c < 0 or b >= h or c >= w:
                    continue 
                if p[b][c] != -1 or s[b][c] == '#':
                    continue
                else:
                    check.append(((b, c), d + 1))
        return pre
ans = 0
for H in range(len(s)):
    for W in range(len(s[0])):
        ans = max(ans, solve(H, W))
print(ans)

### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
for i in range(len(s)):
    for j in range(len(s[0])):
        if s[i][j] == '#':
            continue
        pre = 0
        p = np.full((h, w), -1)
        p[i][j] = 0
        check = deque([((i, j), 0)])#(from,now, dist)
        while check:
            now, d = check.popleft()
            pre = max(pre, d)
            for k, l in [(1,0), (-1,0),(0,1), (0,-1)]:
                b = now[0] + k
                c = now[1] + l
                if b < 0 or c < 0 or b >= h or c >= w:
                    continue 
                elif p[b][c] == -1 and s[b][c] != '#':
                    check.append(((b, c), d + 1))
                    p[b][c] = d + 1
        ans = max(ans, pre)

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

import fractions
k = int(input())
 
sum = 0
for x1 in range(1,k+1):
  for x2 in range(1,k+1):
    for x3 in range(1,k+1):
      for i in range(1, 2):
        ans = fractions.gcd(x1,x2)
        ans = fractions.gcd(ans,x3)
        sum += ans
 
print(sum)

### FIXED CODE ###

import fractions
k = int(input())

l = [[-1 for _ in range(k+1)] for _ in range(k+1)]

for i in range(1,k+1):
  for j in range(1,k+1):
     if l[i][j] == -1:
        ans = fractions.gcd(i,j)
        l[i][j] = ans
        l[i][i] = ans
sum = 0
#1種類
for i in range(1,k+1):
  sum += i
#２種類
for i in range(1,k):
  for j in range(i+1,k+1):
    sum += l[i][j]*6

#3種類
for i in range(1,k-1):
  for j in range(i+1,k):
    for m in range(j+1,k+1):
      sum += l[l[i][j]][m]*6

print(sum)
### BUGGY CODE ###

# E - ∙ (Bullet)
import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

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

pow2_mod = [1] + [0] * (N * 10)
for i in range(1, N * 10):
    pow2_mod[i] = pow2_mod[i-1] * 2 % MOD

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        #d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        # いずれもマイナスの場合、傾きはプラスになる
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            #d_T[(B, -A)] += 0
        # 片方がマイナスの場合、必ずAがマイナスになるよう揃える
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow2_mod[s_cnt] - 1 # Sから1匹以上選ぶ組合せ
    tmp += pow2_mod[t_cnt] - 1 # Tから1匹以上選ぶ組合せ
    tmp += 1 # どちらも選ばない組合せ
    ans = (ans * tmp)%MOD

ans -= 1 # 最終的に1匹も選ばない組合せ
ans += zeros # (0, 0)のイワシの数

print(ans%MOD)

### FIXED CODE ###

# E - ∙ (Bullet)
import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

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

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        # いずれもマイナスの場合、傾きはプラスになる
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            d_T[(B, -A)] += 0
        # 片方がマイナスの場合、必ずAがマイナスになるよう揃える
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow(2, s_cnt, MOD) - 1
    tmp += pow(2, t_cnt, MOD) - 1
    tmp += 1
    ans = (ans * tmp)%MOD

ans -= 1
ans += zeros

print(ans%MOD)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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


ans = 0
for i in range(n):
    init = a_list[:]
    init.pop(i)
    gcd = gcd_list(init)
    if ans < gcd:
        ans = gcd

print(ans)

### FIXED CODE ###

from fractions import gcd

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

rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))

gcd_list = [gcd(r,l) for r, l in zip(rs, ls[::-1])]
print(max(gcd_list))
### BUGGY CODE ###

S=input()
T=input()

s=len(S)
t=len(T)
#DPテーブル作成
dp=[['']*(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] + S[i]
        else:
            dp[i+1][j+1] =  max([ dp[i+1][j] , dp[i][j+1] ],key=len)
# print(*dp,sep="\n")

res = ''
while s != 0 and t != 0:
    if dp[s][t] == dp[s-1][t]:
        s -= 1
    elif dp[s][t] == dp[s][t-1]:
        t -= 1
    else:
        s -= 1
        t -= 1
        res = S[s] + res

# print(dp[s][t])
print(res)

### FIXED CODE ###

S=input()
T=input()

s,t=len(S),len(T)
#DPテーブル作成
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] ])
# print(*dp,sep="\n")

res = ''
while s != 0 and t != 0:
    if dp[s][t] == dp[s-1][t]:
        s -= 1
    elif dp[s][t] == dp[s][t-1]:
        t -= 1
    else:
        s -= 1
        t -= 1
        res = S[s] + res

# print(dp[s][t])
print(res)
### BUGGY CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
ab_list = []
for _ in range(M):
    a, b = map(int, input().split())
    ab_list.append([a,b])    

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}
def func(v,c):
    if nodes_color[v] == 0:
        nodes_color[v] = c
    elif nodes_color[v] == -c:
        return False
    else:
        return True
    
    for ab in ab_list:
        if v in ab:
            for a in ab:
                if a==v:
                    continue
                if not func(a, -c):
                    return False
    return True

# def bipartite_graph_check():
#     for i in range(1,N+1):
#         if nodes_color[i] == 0:
#             if not func(i,1):
# #                 print("Not Bipartite graph")
#                 return False
#     return True

if func(1,1):
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))


### FIXED CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())
 
# 隣接リスト
l = [[] for i in range(N+1)] 
for i in range(M):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

nibu = True
stack = [1]

nodes_color[1] = 1

while stack:
    node = stack.pop()
    for next_node in l[node]:
        if nodes_color[next_node]==0:
            stack.append(next_node)
            nodes_color[next_node] = - nodes_color[node]
        else:
            if nodes_color[next_node]==nodes_color[node]:
                nibu = False
                break
    if not nibu:
        break

if nibu:
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))
### BUGGY CODE ###

from fractions import Fraction
from decimal import Decimal

n=int(input())
a=[Fraction(Decimal(input())) for _ in range(n)]

num=[aa.numerator*10**9//aa.denominator for aa in a]

cnt=[[0]*50 for _ in range(50)]
pair=[]

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for c2,c5 in pair:
    for cc2 in range(18-c2,50):
        for cc5 in range(18-c5,50):
            ans+=cnt[cc2][cc5]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)

### FIXED CODE ###

from fractions import Fraction
from decimal import Decimal

n=int(input())
a=[Fraction(Decimal(input())) for _ in range(n)]

num=[aa.numerator*10**9//aa.denominator for aa in a]

cnt=[[0]*50 for _ in range(50)]
pair=[]

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for i in range(49,-1,-1):
    for j in range(49,-1,-1):
        if i+1<49:
            cnt[i][j]+=cnt[i+1][j]
        if j+1<49:
            cnt[i][j]+=cnt[i][j+1]

        if i+1<49 and j+1<49:
            cnt[i][j]-=cnt[i+1][j+1]

for c2,c5 in pair:
    ans+=cnt[max(0,18-c2)][max(0,18-c5)]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)
### BUGGY CODE ###

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

gates = []
for i in range(M):
    gates.append(tuple(map(int, input().split())))


s = set(range(gates[0][0], gates[0][-1] + 1)) 
for g in gates[1:]:
    tmp_s = set(range(g[0], g[-1] + 1))
    s = s.intersection(tmp_s)

print(len(s))

### FIXED CODE ###

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

L = []
R = []
for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

l_max = max(L)
r_min = min(R)

if l_max <= r_min:
    print(r_min - l_max + 1)
else:
    print(0)
### BUGGY CODE ###


Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=set()
a=2
count=0
for a in range(2,M):
    if a in numlst:
        numlst.remove(a)
        if a:
            sosuulst.add(a)
        numLst=list(numlst)
        for i in numLst:
            if i%a==0:
                numlst.remove(i)
        if (a+1)//2 in sosuulst:
            count+=1
    if a>=3:
        lst[a]=count
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


### FIXED CODE ###


Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])
### BUGGY CODE ###

N, M, P = map(int, input().split())
E = [[] for _ in range(N)]
RE = [[] for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, c])
  RE[b - 1].append(a - 1)
Reachable = [[False, False] for _ in range(N)]
Q = [0]
while(Q):
  q = Q.pop(0)
  Reachable[q][0] = True
  for adj, _ in E[q]:
    if not Reachable[adj][0]:
      Q.append(adj)
Q = [N - 1]
while(Q):
  q = Q.pop(0)
  Reachable[q][1] = True
  for adj in RE[q]:
    if not Reachable[adj][1]:
      Q.append(adj)
R = [r[0] and r[1] for r in Reachable]
D = [None] * N
D[0] = 0
for _ in range(N):
  for s in range(N):
    if D[s] == None:
      continue
    for adj, coin in E[s]:
      if not R[adj]:
        continue
      if D[adj] == None:
        D[adj] = D[s] + coin - P
      else:
        D[adj] = max(D[adj], D[s] + coin - P)
for s in range(N):
  if D[s] == None:
    continue
  for adj, coin in E[s]:
    if not R[adj]:
      continue
    if D[adj] == None:
      continue
    elif D[adj] < D[s] + coin - P:
      D[-1] = None
if D[-1] == None:
  print(-1)
else:
  print(max(D[-1], 0))

### FIXED CODE ###

N, M, P = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
  print(-1)
else:
  print(max(D[-1], 0))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

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

def soin(a):
    fa = []
    i = 2
    d = a
    last = 1
    while d>1:
        if d % i == 0:
            if last == i:
                fa[-1][1]=fa[-1][1]+1
            else:
                fa.append([i,1])
            d=d//i
            last = i
        else:
            i += 1
    return(fa)

#print(soin(n))
q = soin(m)
answer = 1

for i in q:
#    print(i,i[1])
    r = i[1]
    answer = answer * (math.factorial(n+r-1)//math.factorial(n-1)//math.factorial(r))

answer = answer % (10**9+7)

print(answer)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

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

def soin(a):
    fa = []
    i = 2
    d = a
    last = 1
    while d>1:
        if d % i == 0:
            if last == i:
                fa[-1][1]=fa[-1][1]+1
            else:
                fa.append([i,1])
            d=d//i
            last = i
        else:
            i += 1
        if i * i > a:
            fa.append([a,1])
            break

    return(fa)

#print(soin(n))
q = soin(m)
answer = 1

for i in q:
#    print(i,i[1])
    r = i[1]
    a = 1
    for j in range(n,n+r):
        a = a * j
    for j in range(r):
        a = a // (j+1)
    answer = answer * a % (10**9+7)

print(answer)
### BUGGY CODE ###

import sys


def _sum_ob_divisors(n):
    def f(n, x):
        y = n // x
        return y * (y + 1) * x / 2
    return sum(f(n, i) for i in range(1, n + 1))


def _sum_ob_divisors(n):
    L = [1] * (n + 1)
    for i in range(2, n + 1):
        for j in range(i, n + 1, i):
            L[j] += 1
    # print(f'{L=}')
    return sum(i * x for i, x in enumerate(L))


def sum_ob_divisors(f):
    n = int(f.read())

    return _sum_ob_divisors(n)


def main():
    ans = sum_ob_divisors(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

# import numpy as np

def _sum_ob_divisors(n):
    def f(n, x):
        y = n // x
        return y * (y + 1) * x // 2
    return sum(f(n, i) for i in range(1, n + 1))


# def _sum_ob_divisors(n):
#     L = [1] * (n + 1)
#     # L = np.ones(n + 1, dtype=np.int64)
#     for i in range(2, n + 1):
#         for j in range(i, n + 1, i):
#             L[j] += 1
#         # L[i:n + 1:i] += 1
#     # print(f'{L=}')
#     return sum(i * x for i, x in enumerate(L))


def sum_ob_divisors(f):
    n = int(f.read())

    return _sum_ob_divisors(n)


def main():
    ans = sum_ob_divisors(sys.stdin.buffer)
    print(ans)


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

N,M = map(int,input().split(' '))
LRC = []
for i in [0]*M:
    l,r,c= list(map(int,input().split(' ')))
    LRC.append((l,r,c))

INF = 10**20
d = [INF] * (N+1)
d[1] = 0
for i in range(2,N+1):
    for l,r,c in LRC:
        if not (l <= i <= r):
            continue
        for n in range(l,i):
            d[i] = min(d[n]+c, d[i])
if d[N] == INF:
    print(-1)
    exit()
print(d[N])
        



### FIXED CODE ###

import sys
from heapq import heappop, heappush
from collections import defaultdict
input = sys.stdin.buffer.readline

INF = 10**20
N,M = map(int,input().split())
g = defaultdict(list)
for i in range(2,N+1):
    g[i].append((i-1,0))
for i in range(1,M+1):
    l,r,c = list(map(int,input().split()))
    g[l].append((r,c))

d = [INF] * (N+1)
d[1] = 0
que = []
heappush(que,(1,0))
while que:
    s, dist = heappop(que)
    if d[s] < dist:
        continue
    for t,c in g[s]:
        if d[t] > d[s] + c:
            d[t] = d[s] + c
            heappush(que,(t,d[t]))
if d[N] == INF:
    print(-1)
    exit()
print(d[N])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

res = 0

for i in range(N // R + 1):
    for j in range(N // G + 1):
        b = N - R * i - G * j
        if b >= 0 and b % B == 0:
            res += 1

print(res)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

res = 0

for i in range(N // R + 1):
    for j in range((N - R * i) // G + 1):
        b = N - R * i - G * j
        if b >= 0 and b % B == 0:
            res += 1

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

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

E = []
for i in P:
    E.append((i+1)/2)
# print(E)

sum_E = [0, ]
for i in range(N):
    sum_E.append(sum(E[0:i+1]))
# print(sum_E)

sum_K = []
ans = 0
for i in range(N-K+1):
    if sum_E[i+K] - sum_E[i] > ans:
        ans = sum_E[i+K] - sum_E[i]
print(ans)


### FIXED CODE ###

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

E = []
for i in P:
    E.append((i+1)/2)
# print(E)

sum_E = [0, ]
for i in range(N):
    sum_E.append(sum_E[i] + E[i])
# print(sum_E)

sum_K = []
ans = 0
for i in range(N-K+1):
    if sum_E[i+K] - sum_E[i] > ans:
        ans = sum_E[i+K] - sum_E[i]
print(ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

ans = ns()
q = ni()
now = 0
for i in range(q):
    query = ns().split(' ')
    if query[0] == '1':
        now = 1 - now
    else:
        f, c = query[1], query[2]
        if f == '1':
            if now == 1:
                ans += c
            else:
                ans = c + ans
        else:
            if now != 1:
                ans += c
            else:
                ans = c + ans

if now == 1:
    print(ans[::-1])
else:
    print(ans)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

ans = collections.deque(ns())
q = ni()
now = 0
for i in range(q):
    query = ns().split(' ')
    if query[0] == '1':
        now = 1 - now
    else:
        f, c = query[1], query[2]
        if f == '1':
            if now == 1:
                ans.append(c)
            else:
                ans.appendleft(c)
        else:
            if now != 1:
                ans.append(c)
            else:
                ans.appendleft(c)

if now == 1:
    for i in range(len(ans)):
        print(ans[-(i+1)], end="")
else:
    for i in range(len(ans)):
        print(ans[i], end="")
print()
### BUGGY CODE ###

N = int(input().strip())

X = {}
Y = {}

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = set()
  if y not in Y: Y[y] = set()
  X[x].add(y)
  Y[y].add(x)

count = 0

for x1, y_set1 in X.items():
  if len(y_set1) < 2: continue

  for y in y_set1:
    for x2 in Y[y]:
      if x2 == x1: continue
      count += len(y_set1 - X[x2])
      X[x2] |= y_set1

print(count)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input().strip())

X = {}
Y = {}
G = (X, Y)

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = []
  if y not in Y: Y[y] = []
  X[x].append(y)
  Y[y].append(x)


def dfs_visit(visited, u, i):
  if u in visited[i]: return
  visited[i].add(u)
  for v in G[i][u]:
    dfs_visit(visited, v, (i + 1) % 2)


count = 0
i = 0
while len(X) > 0:
  visited = (set(), set())
  x = X.__iter__().__next__()
  dfs_visit(visited, x, 0)

  for x in visited[0]:
    count += len(visited[1]) - len(X.pop(x))

print(count)