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

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peer_nodes = [[] for _ in range(N)]
edge_colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peer_nodes[a].append(b)
    if not a in peer_nodes[b]:
        peer_nodes[b].append(a)
    edge_colors[a][b] = 0

#print(peer_nodes,edge_colors)

def draw_color_return_max_colors(node):
    max_colors = 0
    peers = peer_nodes[node]
    if len(peers) == 0:
        return 0
    used_colors = []
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        c = edge_colors[i][j]
        if c != 0:
            used_colors.append(c)
    #print('----', node, peers,used_colors)
    if len(used_colors) == len(peers):
        return 0
    color = 1
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        if edge_colors[i][j] > 0:
            continue
        else:
            while(color in used_colors):
                used_colors.remove(color)
                color += 1
            if edge_colors[i][j] == 0:
                used_colors.append(color)
                edge_colors[i][j] = color
    max_colors = max([0] + used_colors)
    for p in peers:
        max_colors = max(max_colors, draw_color_return_max_colors(p))

    return max_colors


print(draw_color_return_max_colors(pairs[0][0]))

for a,b in pairs:
    print(edge_colors[a][b])


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peers = [[] for _ in range(N)]
colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peers[a].append(b)
    colors[a][b] = 0


def draw(node, parent_edge_color):
    _peers = peers[node]
    if len(_peers) == 0:
        return 0
    color = 1
    max_nrof_color = 1
    for peer in _peers:
        #print(node,peer,color)
        if color == parent_edge_color:
            color +=1
        colors[node][peer] = color
        max_nrof_color = max(max_nrof_color, color, draw(peer, color))
        color += 1

    return max_nrof_color


print(draw(0,0))
for a,b in pairs:
    print(colors[a][b])
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(k):
    if a>0:
        a-=1
    elif b>0:
        b-=1
    else:
        pass
print(a,b)

### FIXED CODE ###

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

from collections import deque
def main():
    n = int(input())
    G = [[] for _ in range(n)]
    D = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append(b)
        D[a].append(c)
        G[b].append(a)
        D[b].append(c)
    q, k = list(map(int, input().split()))
    k -= 1
    stack = deque([k, ])
    ans = [-1] * n
    ans[k] = 0
    while stack:
        x = stack.popleft()
        for dx, l in zip(G[x], D[x]):
            if ans[dx] == -1:
                ans[dx] = ans[x] + l
                stack.appendleft(dx)
    for _ in range(q):
        x, y = list(map(lambda x: int(x) - 1, input().split()))
        print(ans[x] + ans[y])

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
import sys
def input():
    return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append([b, c])
        G[b].append([a, c])
    q, k = list(map(int, input().split()))
    k -= 1
    stack = deque([k, ])
    ans = [-1] * n
    ans[k] = 0
    while stack:
        x = stack.popleft()
        for (dx, l) in G[x]:
            if ans[dx] == -1:
                ans[dx] = ans[x] + l
                stack.appendleft(dx)
    for _ in range(q):
        x, y = list(map(lambda x: int(x) - 1, input().split()))
        print(ans[x] + ans[y])

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

import numpy as np

N,M,R=map(int,input().split())
r=list(map(int,input().split()))

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))



Dis=[None]*(N+1)

for i in range(N+1):
    Dis[i]=[float("inf")]*(N+1)

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]


#ワーシャル–フロイド法を使って最短距離Disを求める

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(1,N+1):#町jとの最短距離は、
            Dis[i][j]=min(Dis[i][j],Dis[i][k]+Dis[j][k])
    
        
import itertools
    
PERM=list(itertools.permutations(r,R))

ANS=10**8
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
        if DIST>ANS:
            break
    ANS=min(ANS,DIST)


print(ANS)


### FIXED CODE ###

#import numpy as np
import itertools
import time

N,M,R=map(int,input().split())
r=list(map(int,input().split()))

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))


#Dis=np.full((N+1,N+1),float("inf"))

Dis=[None]*(N+1)
for i in range(1,N+1):
    Dis[i]=[100000000]*(N+1)

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]



#ワーシャル–フロイド法を使って最短距離Disを求める

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(i,N+1):#町jとの最短距離は、
            length=Dis[i][k]+Dis[j][k]
            if Dis[i][j]>length:
                Dis[i][j]=length
                Dis[j][i]=length


  
PERM=list(itertools.permutations(r))



ANS=float("inf")
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
        if DIST>ANS:
            break
    if ANS>DIST:
        ANS=DIST

print(int(ANS))
### BUGGY CODE ###

import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 15

count = 0
for x in range(k+1):
    if s < x:
        break
    for y in range(k+1):
        if s < x + y:
            break
        for z in range(k+1):
            if x + y + z == s:
                count = count + 1
                break
print(count)


### FIXED CODE ###

import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 14

count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z <= k and 0 <= z:
            count += 1
print(count)
### BUGGY CODE ###

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

for i in a:
    ans *= i

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

### FIXED CODE ###

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

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


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

l = []

for i in range(N):
    a, b = map(int, input().split())
    l += [a] * b

print(sorted(l)[K-1])

### FIXED CODE ###

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

l = []

for i in range(N):
    a, b = map(int, input().split())
    l.append((a,b))
def c(x):
    return  x[0]
l = sorted(l, key=c)
t = 0
for a,b in l:
    t2 = t
    t += b
    if t2 <= K and t >= K:
        break

print(a)
### BUGGY CODE ###

a = 0
n = int(input())
while n != 0:
  a += n % 10
  n = n // 10 

if a % 9 == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a = 0
s = input()
for c in s:
  a += int(c)

if a % 9 == 0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    H,W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]

    S = (80+80)*80
    dp = [[[0]*(S+1) for _ in range(W)] for __ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    for i in range(H):
        for j in range(W):
            for s in range((i+j+1)*80+1):
                if i < H-1:
                    ni = i + 1
                    nj = j
                    t = abs(A[ni][nj] - B[ni][nj])
                    ns = s + t
                    if ns <= S:
                        dp[ni][nj][ns] |= dp[i][j][s]
                    ns = abs(s - t)
                    dp[ni][nj][ns] |= dp[i][j][s]
                if j < W-1:
                    ni = i
                    nj = j + 1
                    t = abs(A[ni][nj] - B[ni][nj])
                    ns = s + t
                    if ns <= S:
                        dp[ni][nj][ns] |= dp[i][j][s]
                    ns = abs(s - t)
                    dp[ni][nj][ns] |= dp[i][j][s]
    for s in range(S+1):
        if dp[H-1][W-1][s]:
            print(s)
            break

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    H,W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

    M = 160*80
    dp = [[0 for _ in range(W)] for __ in range(H)]
    dp[0][0] = 1 << (C[0][0] + M)
    for i in range(H):
        for j in range(W):
            for ni,nj in [(i,j+1),(i+1,j)]:
                if ni >= H or nj >= W: continue
                t = C[ni][nj]
                dp[ni][nj] |= dp[i][j] << t
                dp[ni][nj] |= dp[i][j] >> t
    
    a = dp[H-1][W-1]
    ans = 0
    while True:
        if a & (1 << (M+ans)) or a & (1 >> (M-ans)): break
        ans += 1
    print(ans)

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

n = int(input())

ans = 0

result = 0;
for i in range(1, n):
  result += i
print(result)



### FIXED CODE ###

n = int(input())
print((n * (n-1)) // 2)
### BUGGY CODE ###

a,b=map(int,input().split())
x=[1]
y=[1]
for i in range(2,a//2+1):
  if a%i==0:
    x.append(i)
    while a%i==0:
      a=a//i
    if a==1:
      break
for i in range(2,b//2+1):
  if b%i==0:
    y.append(i)
    while b%i==0:
      b=b//i
    if b==1:
      break
print(len(set(x)&set(y)))

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
k=fractions.gcd(a,b)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    
    return arr

 
print(len(factorization(k))+1)
### BUGGY CODE ###

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
sys.setrecursionlimit(4100000)
from functools import lru_cache
INF = 1 << 60

#ここから書き始める
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
x = []
for i in range(m):
    b, c = map(int, input().split())
    x.append([c, b])
x.sort(reverse=True)
# print("x =", x)
# print("a =", a)
ans = sum(a)
for i in range(n):
    flag = True
    for j in range(m):
        if x[j][0] > a[i] and x[j][1] > 0:
            ans += x[j][0] - a[i]
            x[j][1] -= 1
            flag = False
            break
    if flag:
        break
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
  
for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

ta_c,ao_c,num = map(int,input().split())

for i in range(num):
    if ta_c > 0:
        ta_c -=1
    elif ao_c >0:
        ao_c -=1

print(ta_c,ao_c)

### FIXED CODE ###

ta_c,ao_c,num = map(int,input().split())

if num <= ta_c:
    print(ta_c-num,ao_c)
elif ta_c < num <= ta_c + ao_c:
    ao_c = ta_c+ao_c - num
    ta_c = 0
    print(ta_c,ao_c)
else:
    ta_c, ao_c = 0,0
    print(ta_c,ao_c)
### BUGGY CODE ###

h,n = map(int,input().split())
magic = [ list(map(int,input().split())) for i in range(n)]
INF = float("inf")

dp =  [[INF]*(h+1) for i in range(n+1)]

"""
i番目までの魔法の中から攻撃力の合計が
jを超えるように選んだときの消費精神力の最小値
"""

for i in range(n):
    for j in range(h):
        if j < magic[i][0]:#その魔法で一撃
             dp[i+1][j+1] = min(dp[i][j+1],magic[i][1])
        elif j >= magic[i][0] and 0<= j+1-magic[i][0] <= h:
            dp[i+1][j+1] = min(dp[i][j+1],dp[i][j+1-magic[i][0]]+magic[i][1],dp[i+1][j+1-magic[i][0]]+magic[i][1])#その魔法を連打したときが考慮されていない
        
print(dp[n][h])



### FIXED CODE ###

h,n = map(int,input().split())
magic = [ list(map(int,input().split())) for i in range(n)]
INF = float("inf")

dp =  [[INF]*(h+1) for i in range(n+1)]

"""
i番目までの魔法の中から攻撃力の合計が
jを超えるように選んだときの消費精神力の最小値
"""

for i in range(n):
    for j in range(h):
        if j < magic[i][0]:#その魔法で一撃
             dp[i+1][j+1] = min(dp[i][j+1],magic[i][1])
        elif j >= magic[i][0] and 0<= j+1-magic[i][0] <= h:
            dp[i+1][j+1] = min(dp[i][j+1],dp[i][j+1-magic[i][0]]+magic[i][1],dp[i+1][j+1-magic[i][0]]+magic[i][1])#その魔法を連打したときが考慮されていない
        
print(dp[n][h])
### BUGGY CODE ###

S = list(input())
N = len(S)
BCidxs = []
i = 0
while i < N:
  if "".join(S[i:i+2]) == "BC":
    BCidxs.append(i)
  i += 1
ans = 0
L = len(BCidxs)
i = 0
while i < L:
  idx = BCidxs[i]
  if "".join(S[idx-1:idx+2]) == "ABC":
    ans += 1
    S[idx-1] = "B"
    S[idx] = "C"
    S[idx+1] = "A"
    BCidxs[i] -= 1
  else:
    i += 1
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
ans = 0
cnt = 0
i = 0
while i < N:
  if S[i] == "A":
    cnt += 1
    i += 1
  elif "".join(S[i:i+2]) == "BC":
    ans += cnt
    i += 2
  else:
    cnt = 0
    i += 1
print(ans)
### BUGGY CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan
import cmath as cma
import copy as cp
import sys
import re
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n = iinput()
a = iarr()
ans = 1
for num in a: ans *= num
ans = -1 if ans>10**18 else ans
print(ans)


### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n = iinput()
a = iarr()

ans = 1
for num in a:
    ans *= num
    if ans > 10**18: ans = -1; break
if 0 in a: ans = 0
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
sum=[]
sum.append(0)
for i in range(n):
    sum.append(sum[i]+a[i])
#print(sum)
ans=0
for i in range(n+1):
    for j in range(i+1,n+1):
        if sum[j]-sum[i]==0:
            ans +=1
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
s=[]
s.append(0)
for i in range(n):
    s.append(s[i]+a[i])
s.sort()
a=Counter(s).most_common()
#print(a)
ans=0
for i in range(len(a)):
    ans += ((a[i][1]-1)*a[i][1])//2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
from math import cos, sin, pi
n, L = map(int, input().split())
t = [int(input()) for _ in range(n)]
ans = [0, 0]
for i in range(n):
    for j in range(i + 1, n):
        k = (n - 1 - j + i) - (j - i - 1)
        ans[0] += cos(pi * (t[i] + t[j]) / L) * k
        ans[1] += sin(pi * (t[i] + t[j]) / L) * k
for i in range(2):
    ans[i] /= n * (n - 1) * (n - 2) / 6
print(*ans, sep=' ')


### FIXED CODE ###

#!/usr/bin/env python3
from math import cos, sin, pi
n, L = map(int, input().split())
t = [int(input()) for _ in range(n)]
ans = [0, 0]
for i in range(n):
    for j in range(i + 1, n):
        k = (n - 1 - j + i) - (j - i - 1)
        ans[0] += cos(pi * (t[i] + t[j]) / L) * k
        ans[1] += sin(pi * (t[i] + t[j]) / L) * k
for i in range(2):
    ans[i] /= n * (n - 1) * (n - 2) / 6
print(*ans, sep=' ')
### BUGGY CODE ###

n,a,b=map(int,input().split())
HP=[int(input()) for i in range(n)]
ng=0
ok=10**10
for i in range(40):
    check=(ok+ng)//2
    c=a-b
    cnt=0
    d=list(map(lambda x: x-check*b,HP))
    for j in d:
        cnt+=max(0,(j+c-1)//c)
    if check < cnt:
        ng=check
    else:
        ok=check
print(ok)

### FIXED CODE ###

n,a,b=map(int,input().split())
HP=[int(input()) for i in range(n)]
ng=0
ok=10**10
for i in range(40):
    check=(ok+ng)//2
    c=a-b
    cnt=0
    d=list(map(lambda x: x-check*b,HP))
    for j in d:
        cnt+=max(0,(j+c-1)//c)
    if check < cnt:
        ng=check
    else:
        ok=check
print(ok)
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())
summ = 0

# 組み合わせの数
# a, b, cが同じは1pattern
# a, b, cのうち、２つが同じパターンは３
# a, b, cのうち、全て異なるパターンは6
# つまり、３つの数の組み合わせの数を求め、各パターン倍すればよい

# タプルで集合を作成する
# st = set()
# # # for a in range(1, K+1):
# # #     for b in range(1, K+1):
# # #         for c in range(1, K+1):
# # #             sort_abc = sorted([a, b, c])
# # #             st.add(tuple(sort_abc))
# # # # print(st)
# # # for s in st:
# # #     if s[0] == s[1] == s[2]:
# # #         summ += reduce(math.gcd, s)
# # #         # print(0, s)
# # #     elif s[0] == s[1] or s[0] == s[2] or s[1] == s[2]:
# # #         summ += 3*reduce(math.gcd, s)
# # #         # print(1, s)
# # #     else:
# # #         summ += 6*reduce(math.gcd, s)
# # #         # print(2, s)
# # # print(summ)

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            summ += reduce(math.gcd, [a, b, c])
print(summ)


### FIXED CODE ###

import math
k = int(input())
ans = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        num = math.gcd(i, j)
        for l in range(1, k+1):
            ans += math.gcd(num, l)

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

a,b,c,d = map(int,input().split())
f = [i for i in range(a,b+1) if not ((i%c==0)or(i%d==0))]
print(len(f))

### FIXED CODE ###

import fractions
a,b,c,d = map(int,input().split())
e,f,g = (a-1)//c,(a-1)//d,(a-1)//(c * d // fractions.gcd(c, d))
h,i,j = b//c,b//d,b//(c * d // fractions.gcd(c, d))
ans = (b-a+1)-((h+i-j)-(e+f-g))
print(ans)
### BUGGY CODE ###

MOD = 10**9+7


def make_combination_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def sum_rect(r, c, table):
    return (mod_combination(r+c+2, r+1, table)-1) % MOD


def main():
    r1, c1, r2, c2 = map(int, input().split())
    table = make_combination_table((r2+1)*(c2+1))
    r1 -= 1
    c1 -= 1

    ans = sum_rect(r2, c2, table)
    ans -= sum_rect(r2, c1, table)
    ans -= sum_rect(r1, c2, table)
    ans += sum_rect(r1, c1, table)
    print(ans)


main()


### FIXED CODE ###

MOD = 10**9+7


def make_combination_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i % MOD
    return (fact, ifact)


def mod_combination(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def sum_rect(r, c, table):
    return (mod_combination(r+c+2, r+1, table)-1) % MOD


def main():
    r1, c1, r2, c2 = map(int, input().split())
    table = make_combination_table((r2+c2+2))
    r1 -= 1
    c1 -= 1

    ans = sum_rect(r2, c2, table)
    ans %= MOD
    ans -= sum_rect(r2, c1, table)
    ans %= MOD
    ans -= sum_rect(r1, c2, table)
    ans %= MOD
    ans += sum_rect(r1, c1, table)
    ans %= MOD
    print(ans)


main()
### BUGGY CODE ###

from collections import defaultdict

def inside(x, y):    
    return 0 <= x <= h - 3 and 0 <= y <= w - 3

h, w, n = (int(_) for _ in input().split())
black = defaultdict(int)
for i in range(n):
    a, b = (int(_) - 1 for _ in input().split())
    for j in range(3):
        for k in range(3):
            x, y = a - j, b - k
            if not inside(x, y):
                continue
            black[(x, y)] += 1
ans = [0 for i in range(10)]
ans[0] = (h-2)*(w-2) - len(black)
for k in black:
    ans[black[k]] += 1
for i in range(10):
    print(ans[i])

            
    


### FIXED CODE ###

from collections import defaultdict

def inside(x, y):    
    return 0 <= x <= h - 3 and 0 <= y <= w - 3

h, w, n = (int(_) for _ in input().split())
black = defaultdict(int)
for i in range(n):
    a, b = (int(_) - 1 for _ in input().split())
    for j in range(3):
        for k in range(3):
            x, y = a - j, b - k
            if not inside(x, y):
                continue
            black[(x, y)] += 1
ans = [0 for i in range(10)]
ans[0] = (h-2)*(w-2) - len(black)
for k in black:
    ans[black[k]] += 1
for i in range(10):
    print(ans[i])
### BUGGY CODE ###

from itertools import groupby
N, K = map(int, input().split())
S = [len(list(g)) for k, g in groupby(input())]
i = 0
while i < K and len(S) > 2:
    S.insert(0, S.pop(0) + S.pop(0) + S.pop(0))
    i += 1
if i < K and len(S) == 2:
    S.append(S.pop(0) + S.pop(0))
print(sum(S) - len(S))


### FIXED CODE ###

from itertools import groupby
from collections import deque
N, K = map(int, input().split())
S = [len(list(g)) for k, g in groupby(input())]
S = deque(S)
i = 0
while i < K and len(S) > 2:
    S.append(S.pop() + S.pop() + S.pop())
    i += 1
if i < K and len(S) == 2:
    S.append(S.pop() + S.pop())
print(sum(S) - len(S))
### BUGGY CODE ###

h = int(input())

count = 0
result = 1
while True:
    h = h//2
    count += 1
    result += 2**count
    if h == 1:
        break

print(result)

### FIXED CODE ###

h = int(input())

count = 0
result = 1

if h == 1:
    print(1)
    exit()

while True:
    h = h//2
    count += 1
    result += 2**count
    if h == 1:
        break

print(result)
### BUGGY CODE ###

a = int(input())
b = list(map(int, input().split()))
for i in range(1,a):
    print(b.count(i))
print(0)

### FIXED CODE ###

def main():
    a = int(input())
    b = list(map(int, input().split()))
    c = [0]*a
    for i in b:
        c[i-1] += 1
    for j in c:
        print(j)
if __name__ == '__main__':
    main()