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

import collections
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if visited[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
Q = collections.deque([])
Q.append(1)
while Q:
  n = Q.popleft()
  visited[n] = 1
  for o in e[n]:
    if visited[o[0]] == 0:
      if o[1] + earn[n] - P > earn[o[0]]:
        Q.append(o[0])
        earn[o[0]] = o[1] + earn[n] - P
    else:
      if earn[o[0]] < o[1] + earn[n] - P:
        if isConnected(o[0]) == True:
          print(-1)
          exit(0)
  visited[n] = 0
print(max(earn[N], 0))



### FIXED CODE ###

import collections
import sys
import time
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
st = time.time()
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  nt = time.time() - st
  if nt > 1.95:
    print(max(earn[N], 0))
    exit(0)
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
#SA = sorted(A)

D = []
for _ in range(M):
  B, C = map(int, input().split())
  D += B * [C]

A += D
SA = sorted(A, reverse=True)
#X = min(N, len(SD))
#SD = SD[:X]

print(sum(SA[:N]))
  


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
#SA = sorted(A)

D = []
for _ in range(M):
  B, C = map(int, input().split())
  D.append([B, C])

SD = sorted(D, key=lambda x:x[1], reverse=True)

for b, c in SD:
  A += b * [c]
  if len(A) > N*2:
    break

SA = sorted(A, reverse=True)
#X = min(N, len(SD))
#SD = SD[:X]

print(sum(SA[:N]))
### BUGGY CODE ###

s = input()
t = input()

x = 0

for i in range(len(s)):
    if x >30:
        print('No')
        exit()
    if s[i]!=t[i]:
        a = s[i]
        b = t[i]
        for j in range(len(s)):
            if s[j] == a:
                s = s[:j] + b + s[j+1:]
            elif s[j] == b:
                s = s[:j] + a + s[j+1:]
        x += 1

if s==t:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
t = input()

while s != '':
    if [i for i, x in enumerate(s) if x == s[0]] == [i for i, x in enumerate(t) if x == t[0]]:
        s = s.replace(s[0],'')
        t = t.replace(t[0],'')
    else:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

import sys
from collections import defaultdict

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    n, d, a = geta(int)
    mon = []
    ans = 0

    for _ in range(n):
        x, h = geta(int)
        mon.append([x, (h + a - 1) // a])

    mon.sort()

    for i, mi in enumerate(mon):
        if mi[1] <= 0:
            continue

        ans += mi[1]
        rb = mi[0] + 2 * d

        for mj in mon[i + 1:]:
            if mj[0] > rb:
                break

            mj[1] -= mi[1]

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
from queue import deque

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    n, d, a = geta(int)
    mon = []
    ans = 0

    for _ in range(n):
        x, h = geta(int)
        mon.append([x, (h + a - 1) // a])

    mon.sort()

    bom = deque()
    cur = 0
    for i, mi in enumerate(mon):

        while len(bom) != 0 and bom[0][0] < mi[0]:
            b = bom.popleft()
            cur -= b[1]

        if mi[1] <= cur:
            continue
        else:
            b1 = mi[1] - cur
            bom.append((mi[0] + 2 * d, b1))
            cur += b1
            ans += b1

    print(ans)


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

n,m=map(int,input().split())
c=sum([list(map(int,input().split())) for i in range(m)],[])
from collections import Counter as co
for i in co(c).values():
    if i%2:print("NO");exit()
print("YES")

### FIXED CODE ###

n,m=map(int,input().split())
l=[0]*(n+1)
for i in range(m):
    a,s=map(int,input().split())
    l[a]+=1
    l[s]+=1
for i in l:
    if i%2:print("NO");exit()
print("YES")
### BUGGY CODE ###

import numpy as np
import copy
#import time

N = int(raw_input().replace("\n", ""))

a_array = np.asarray(sorted([int(raw_input().replace("\n", "")) for i in xrange(N)]))
len_array = a_array.shape[0]

if len_array % 2 == 0:
    elm_is = [len_array/2 -1, len_array/2]
else:
    elm_is = [(len_array-1)/2]
aa_array = a_array[elm_is]

#s_time = time.time()


sum_diffs = []
#for elm_i, start_elm in enumerate(a_array):
for elm_i, start_elm in zip(elm_is, aa_array):
    mask = np.ones(len_array, dtype=bool)
    target_elm = start_elm

    sum_diff = 0
    for count in xrange(len_array - 1):
        #c_time = time.time()
        mask[elm_i] = False
        masked_a_array = a_array[mask]
        relative_a_array = np.abs(masked_a_array[[0, -1]] - target_elm)
        #relative_a_array = np.abs(masked_a_array - target_elm)
        target_elm_index1 = np.argmax(relative_a_array)
        target_elm_index = 0 if target_elm_index1 == 0 else len(masked_a_array) - 1
        target_elm = masked_a_array[target_elm_index]
        sum_diff += relative_a_array[target_elm_index1]
        
        #print("mae:", time.time() - c_time)
        #c_time = time.time()
        count_ = -1
        for mask_i, elm in enumerate(mask):
            if elm:
                count_ += 1
                if count_ == target_elm_index:
                    elm_i = mask_i
                    break
        #print("ato:", time.time() - c_time)
    
    sum_diffs.append(sum_diff)

print max(sum_diffs)
#print(time.time() - s_time)

### FIXED CODE ###

import numpy as np
import copy

N = int(raw_input().replace("\n", ""))

a_array = np.asarray(sorted([int(raw_input().replace("\n", "")) for i in xrange(N)]))

len_array = len(a_array)

coffs = np.ones(len(a_array), dtype=bool) * 2

if len_array % 2 == 0:
    coffs = [-2] * ((len_array - 1) / 2) + [-1] + [1] + [2] * ((len_array -1) / 2)
    out = np.dot(a_array, coffs)
else:
    coffs1 = [-2] * ((len_array-3) / 2) + [-1] * 2 + [2] * ((len_array-1) / 2)
    coffs2 = [-2] * ((len_array-1) / 2) + [1] * 2 + [2] * ((len_array-3) / 2)
    out1 = np.dot(a_array, coffs1)
    out2 = np.dot(a_array, coffs2)
    out = max(out1, out2)

print out
### BUGGY CODE ###

import math

x = int(input())

a = 0
b = 0
while a ** 5 < x:
    a += 1
a -= 1

b = -(x - a ** 5)

f = False
if b < 0:
    b = -b
    f = True
    
for i in range(5):
    b = math.sqrt(b)

if f == True:
    b = -b

i = 1
while b - int(b) != 0.0:
    ap = a + i
    b = -(x - ap ** 5)

    f = False
    if b < 0:
        b = -b
        f = True
        
    for i in range(5):
        b = math.sqrt(b)

    if f == True:
        b = -b

    if b - int(b) == 0.0:
        break

    asub = a - i
    b = -(x - asub ** 5)

    f = False
    if b < 0:
        b = -b
        f = True
        
    for i in range(5):
        b = math.sqrt(b)

    if f == True:
        b = -b
    i += 1

print(a, int(b))

### FIXED CODE ###

import math

x = int(input())

f = False
for a in range(-200,200):
    for b in range(-200, 200):
        if a ** 5 - b ** 5 == x:
            print(a, b)
            f = True
            break
    if f == True:
        break
### BUGGY CODE ###

s=list(input())
t=list(input())
sl = [s.count(e) for e in s]
tl = [t.count(e) for e in t]
if sl==tl:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s=list(input())
t=list(input())
s_res = sorted(set(s), key=s.index)
t_res = sorted(set(t), key=t.index)
sl = [s.count(e) for e in s_res]
tl = [t.count(e) for e in t_res]
if sl==tl:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

for i in li:
    ans *= i

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

if li.count(0) > 0:
    print(0)
    exit()

for i in li:
    ans = ans * i
    if ans > 10**18:
        print(-1)
        exit()

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

S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


all=1  #Joutai-su

for i in range(1,l):

	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+all
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]*3+all
		dp[i][2]+=dp[i-1][2]*3+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]*3+dp[i-1][2]
		all*=3

	dp[i][1]%=mod
	dp[i][2]%=mod
	dp[i][3]%=mod


print dp[-1][-1]%mod


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

r, c, k = map(int, input().split())
vals = [[0]*c for _ in range(r)]
for _ in range(k):
    x, y, v = map(int, input().split())
    vals[x-1][y-1] = v
dp = [[[0]*4 for j in range(c)] for i in range(r)]
for i in range(r):
    for j in range(c):
        if i > 0:
            tmp = 0
            for k in range(4):
                if tmp < dp[i-1][j][k]:
                    tmp = dp[i-1][j][k]
            dp[i][j][0] = tmp
        if j > 0:
            for k in range(4):
                if dp[i][j][k] < dp[i][j-1][k]:
                    dp[i][j][k] = dp[i][j-1][k]
        if vals[i][j] != 0:
            for k in range(3, 0, -1):
                if dp[i][j][k] < dp[i][j][k-1] + vals[i][j]:
                    dp[i][j][k] = dp[i][j][k-1] + vals[i][j]
print(max(dp[r-1][c-1]))

### FIXED CODE ###

from sys import stdin
input = stdin.readline

r, c, k = map(int, input().split())
vals = [[0]*c for _ in range(r)]
for _ in range(k):
    x, y, v = map(int, input().split())
    vals[x-1][y-1] = v
dp = [[0]*4 for j in range(c)]
for j in range(c):
    if j > 0:
        for k in range(4):
            dp[j][k] = dp[j-1][k]
    if vals[0][j] > 0:
        for k in reversed(range(3)):
            if dp[j][k+1] < dp[j][k] + vals[0][j]:
                dp[j][k+1] = dp[j][k] + vals[0][j]
for i in range(1, r):
    tmp = [[max(dp[j]), 0, 0, 0] for j in range(c)]
    for j in range(c):
        if j > 0:
            for k in range(4):
                if tmp[j][k] < tmp[j-1][k]:
                    tmp[j][k] = tmp[j-1][k]
        if vals[i][j] > 0:
            for k in reversed(range(3)):
                if tmp[j][k+1] < tmp[j][k] + vals[i][j]:
                    tmp[j][k+1] = tmp[j][k] + vals[i][j]
    dp = tmp
print(max(dp[-1]))
### BUGGY CODE ###

import numpy as np


N = int(input())
A = list(map(int, input().split()))
count = 0
num_list = []
A_list = []


if N == 1:
    if A[0] == 0:
        count += 1
    print(count)
else:
    num = A[0]
    num_list.append(A[0])
    for i in A[1:]:
        num += i
        num_list.append(num)
    A2 = np.array(num_list)
    A_list += list(A2)
    for n, i in enumerate(A):
        A2 = A2 - i
        A2 = A2[1:]
        if len(A) - 1 != n:
            A_list += list(A2)
    print(A_list.count(0))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dic = {0:1}
sum_n = 0
count = 0


for a in A:
    sum_n += a
    if sum_n in dic:
        count += dic[sum_n]
        dic[sum_n] += 1
    else:
        dic[sum_n] = 1


print(count)
### BUGGY CODE ###

def solve(i,j,dp,w,v):
    if dp[i][j]!=0:
        return dp[i][j]
    else:
        if i==0:
            dp[i][j]=0
            return dp[i][j]
        if j<w[i-1]:
            dp[i][j]=solve(i-1,j,dp,w,v)
            return dp[i][j]
        else:
            dp[i][j]=max(solve(i-1,j,dp,w,v),solve(i-1,j-w[i-1],dp,w,v)+v[i-1])
            return dp[i][j]
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[0 for j in range(W+1)] for i in range(N+1)]
print(solve(N,W,dp,w,v))


### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[0 for i in range(W+1)]
dp=np.array(dp)
for i in range(N):
    dp[w[i]:]=np.maximum(dp[w[i]:],dp[:W-w[i]+1]+v[i])
print(dp.max())
### BUGGY CODE ###

def gcdf(a,n):
#    print("a:",a)
    a0=a[0]
    ramin=10**9
    ramin0=20**9
    while ramin0!=ramin:
        ramin0=ramin
        for i in range(n):
            a[i]=a[i]%a0
            if a[i]==0:
                a[i]=a0
#            ra=a[i]%a0
#            print(i,a[i],a0,ramin)
            if ramin>a[i] and a[i]!=0:
                ramin=a[i]
        a0=min(a)
#        print("a:",a,ramin)
    return ramin


#n=2
#a=[1000000000, 1000000000]
#n=4
#a=[15, 18, 24, 36]
n=int(input())

a=[]
for i in map(int,input().split()):
    a.append(i)

#print(a)
if n==2:
    print(max(a))
else:
    gcdv=0
#    a.sort()
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy,n-1)
#        gcdx=gcd(acpy)
#        gcdx=functools.reduce(gcd,acpy)
#        gcdx=functools.reduce(math.gcd,acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)

### FIXED CODE ###

def gcdf(a):
    a.sort()
#    print("a2:",a)
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
#    print("a2:",a)
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

#n=8
#a=[746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#ans=[19]
#n=2
#a=[1000000000, 1000000000]
#n=5
#a=[15, 18, 24, 36, 81]
#n=3
#a=[7, 6, 8]
n=int(input())
a=[]
for i in map(int,input().split()):
    a.append(i)
if n==2:
    print(max(a))
elif n<2**10:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n**(1/2))
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
#        print(mi,gcdf(am),len(am),gcdf(rgcd1))
        for i in range(len(am)):
            acpy=list(am)
#            del acpy[i]
#            acpy.append(gcdrg1)
            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
for _ in range(int(input())):
    x, y = map(int, input().split())
    for i in range(n):
        if l[i] == x:
            l[i] = y
    print(sum(l))

### FIXED CODE ###

def freq(my_list):
    count = {} 
    for i in my_list: 
        count[i] = count.get(i, 0) + 1
    return count

n = int(input())
l = list(map(int, input().split()))
s,f = sum(l), freq(l)
for _ in range(int(input())):
    x, y = map(int, input().split())
    if x in f.keys():
        v = f[x]
        if y in f.keys():
            f[y]+=v
            f.pop(x)
        else:
            f[y]=f.pop(x)
        s += (y-x)*v
    print(s)
### BUGGY CODE ###

n,m = map(int, input().split())
ans = set(range(1,n+1))
for i in range(m):
    l,r = map(int, input().split())
    tmp = set(range(l,r+1))
    ans = ans & tmp

print(len(ans))

### FIXED CODE ###

n,m = map(int, input().split())
ans = 0
L = -100000000
R = 100000000
for i in range(m):
    l,r = map(int, input().split())
    if l > L:
        L = l
    if r < R:
        R = r

print(len(range(L,R+1)))
### BUGGY CODE ###

from collections import Counter
n=int(input())
name=[]
initial=[]
for _ in range(n):
    s=input()
    if s[0] in ["M","A","R","C","H"] and not s in name:
        name.append(s)
        initial.append(s[0])
c=Counter(initial)
num=[v for k,v in c.items()]

if len(num)<3:
    print(0)
else:
    ans=0
    for i in range(len(num)-2):
        for j in range(i+1,len(num)-1):
            for k in range(j+1,len(num)):
                #print(i,j,k)
                ans+=num[i]*num[j]*num[k]
    print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
name=[]
initial={"M":0,
         "A":0,
         "R":0,
         "C":0,
         "H":0}
for _ in range(n):
    s=input()
    if s[0] in ["M","A","R","C","H"]:
        initial[s[0]]+=1
num=[v for k,v in initial.items()]

if len(num)<3:
    print(0)
else:
    ans=0
    for i in range(len(num)-2):
        for j in range(i+1,len(num)-1):
            for k in range(j+1,len(num)):
                #print(i,j,k)
                ans+=num[i]*num[j]*num[k]
    print(ans)
### BUGGY CODE ###

def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    for j in range(tlen):
      if s[i] == t[j]:
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
  result = ''
  i = slen
  j = tlen
  while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      i -= 1
    elif dp[i][j - 1] == dp[i][j]:
      j -= 1
    else:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()


### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

N = int(input())
S = input()
ans = min(S.count("#"), S.count("."))
for i in range(N):
	tmp = S[: i].count("#") + S[i:].count(".")
	if ans > tmp:
		ans = tmp
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
A = [S.count(".")]
for i in range(N):
	if S[i] == "#":
		A.append(A[i] + 1)
	else:
		A.append(A[i] - 1)
print(min(A))
### BUGGY CODE ###


from decimal import *
getcontext().prec = 28
n, k = map(int,input().split())
a = list(map(int,input().split()))
inner = Decimal(0)
outer = Decimal(0)
for i in range(0,n):
    for j in range(0,n):
        if a[i] > a[j]:
            outer += 1
            if i < j:
                inner += 1

b = (Decimal(Decimal(inner) * Decimal(k)) + Decimal(Decimal(outer) * Decimal(Decimal(k) * Decimal(k-1)) / 2))
print(Decimal(Decimal(b)%Decimal(1000000007)))

### FIXED CODE ###

from decimal import *
n, k = map(int,input().split())
a = list(map(int,input().split()))
inner = 0
outer = 0
for i in range(0,n):
    for j in range(0,n):
        if a[i] > a[j]:
            outer += 1
            if i < j:
                inner += 1

print((Decimal(((inner) * (k)) + Decimal((outer) * Decimal((k) * (k-1)) / 2))%(1000000007)))
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int,input().split())),reverse = True)
A = [i for i in A if A.count(i) // 2 >= 1]

ans = 0

for i in range(len(A)):
  m = A[0]
  if A.count(0) >= 4:
    ans = m ** 2
    break
  else:
    if A[i] != m:
      n = A[i]
      ans = m * n
      break

print(ans)

### FIXED CODE ###

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

edge = []

for i in range(1,N):
  if A[i] == A[i - 1] and A[i] not in edge:
    edge.append(A[i])
  elif A[i] == A[i - 3]:
    edge.append(A[i])
  
  if len(edge) == 2:
    break
    
if len(edge) <= 1:
  print(0)
else:
  print(edge[0] * edge[1])
### BUGGY CODE ###

N = int(input())
ans = 0
mod = 10**9 + 7
i = 1
while N > 0:
    r = N % 10
    N = N // 10
    if r == 1:
        if i == 1:
            ans = 3
        else:
            ans = ans*2 % mod
            ans = (ans + 3**(i-1))%mod
    else:
        if i == 1:
            ans = 1
    i += 1
print(ans)


### FIXED CODE ###

L = input()
n = len(L)
mod = 10**9+7
pow3 = [1]
for i in range(1,n):
    x = (3*pow3[i-1])%mod
    pow3.append(x)
ans = 0
for i in range(1,n+1):
    if L[-i] == '1':
        if i == 1:
            ans = 3
        else:
            ans = ans*2 % mod
            ans = (ans + pow3[i-1])%mod
    else:
        if i == 1:
            ans = 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
i=0
k=0
while i<=n-1:
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d)
        flag=True
        for j in range(q-i):
            x[i + j][1] -= w
            if x[i+j][1]<=0:
                if flag:
                    k+=1
            else:
                flag=False
    i=i+k
    k=0
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # iがダメージの有効期限を超過している場合
    while len(qq)>0 and i > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
print(ans)
### BUGGY CODE ###

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

for i in range(1,N+1):
    print(IDs.count(i))

### FIXED CODE ###

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

from collections import Counter

c=Counter(IDs)

for i in range(1,N+1):
    print(c[i])