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

import sys
sys.setrecursionlimit(10000)

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.size = [1]*n

    def find(self,a):
        if self.parent[a] == a:
            return a
        else:
            return self.find(self.parent[a])

    def unite(self,a,b):
        a_parent = self.find(a)
        b_parent = self.find(b)
        if a_parent == b_parent:
            return
        else:
            if self.size_of(b_parent) > self.size_of(a_parent): 
                self.parent[a_parent] = self.parent[b_parent]
                self.size[b_parent] += self.size[a_parent]
            else:
                self.parent[b_parent] = self.parent[a_parent]
                self.size[a_parent] += self.size[b_parent]
                
    def size_of(self,a):
        return self.size[self.find(a)]
    
    def is_same(self,a,b):
        return self.parent(a) == self.parent(b)


N,M,K = map(int, input().split())
uf = UnionFind(N+1)
friends = []
blocks = []
for i in range(N+1):
    blocks.append([])
    friends.append(0)

for i in range(M):
    a,b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.unite(a,b)
    
for j in range(K):
    x,y = map(int, input().split())
    blocks[x].append(y)
    blocks[y].append(x)

for i in range(1,N+1):
    print(uf.size_of(i) - friends[i] - len([x for x in range(1,N+1) if i in blocks[x] and uf.find(i) == uf.find(x)])-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.size = [1]*n

    def find(self,a):
        if self.parent[a] == a:
            return a
        else:
            return self.find(self.parent[a])

    def unite(self,a,b):
        a_root = self.find(a)
        b_root = self.find(b)
        if a_root == b_root:
            return
        else:
            if self.size_of(b_root) > self.size_of(a_root): 
                self.parent[a_root] = self.parent[b_root]
                self.size[b_root] += self.size[a_root]
            else:
                self.parent[b_root] = self.parent[a_root]
                self.size[a_root] += self.size[b_root]
                
    def size_of(self,a):
        return self.size[self.find(a)]
    
    def is_same(self,a,b):
        return self.find(a) == self.find(b)


N,M,K = map(int, input().split())
uf = UnionFind(N+1)
friends = []
blocks = [0]*(N+1)
for i in range(N+1):
    blocks.append([])
    friends.append(0)

for i in range(M):
    a,b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.unite(a,b)
    

for j in range(K):
    x,y = map(int, input().split())
    if uf.is_same(x,y):
        blocks[x] += 1
        blocks[y] += 1

for i in range(1,N+1):
    print(uf.size_of(i) - friends[i] - blocks[i] -1)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    
    a_sum = []
    for i in range(1, len(a)):
        a_sum.append(sum(a[:len(a)-i]))

    total = 0
    a.reverse()

    for i in range(len(a_sum)):
        total += a[i]*a_sum[i]
    
    print(total % (10**9+7))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    
    temp = 0
    a_sum = []

    for i in range(len(a)):
        temp += a[i]
        a_sum.append(temp)

    total = 0
    a_sum.reverse()
    a.reverse()

    for i in range(1, len(a_sum)):
        total += a[i-1]*a_sum[i]
    
    print(total % (10**9+7))

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

from itertools import product

X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort(reverse=True)
lst_B.sort(reverse=True)
lst_C.sort(reverse=True)


lst_A_K = lst_A[:K]
lst_B_K = lst_B[:K]
lst_C_K = lst_C[:K]


lst_AB = sorted([a+b for a, b in product(lst_A_K, lst_B_K)], reverse=True)
lst_AB_K = lst_AB[:K]

lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]

for i in range(K):
    print(lst_ABC_K[i])


### FIXED CODE ###

import sys
from itertools import product


X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort(reverse=True)
lst_B.sort(reverse=True)
lst_C.sort(reverse=True)

# lst_A_K = lst_A[:K]
# lst_B_K = lst_B[:K]
lst_C_K = lst_C[:K]


lst_AB = sorted([a+b for a, b in product(lst_A, lst_B)], reverse=True)
lst_AB_K = lst_AB[:K]

lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]

print(*lst_ABC_K, sep="\n")
### BUGGY CODE ###

inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
 
def factorize(n):
  prime_list = []
  factorize_list = []
  i = 2
  while i <= n:
    for p in prime_list:
      if i % p == 0:
        break
    else:
      prime_list.append(i)
      k = 0
      while n % i == 0:
        n //= i
        k += 1
      factorize_list.append(k)
    i += 1
  return(factorize_list)

def H(n,k):
  h = 1
  L = n + k - 1
  k = min(n-1,k)
  for j in range(k):
    h *= L-j
  for j in range(k):
    h //= j+1
  return h

ans = 1
for k in factorize(M):
  ans *= H(N,k) % MOD
  ans %= MOD

print(ans)

### FIXED CODE ###

import math

R = 10**9 + 7

def combination(n,k):
    if 2*k > n:
        k = n - k

    r = 1
    for i in range(n-k+1,n+1):
        r = (r*i)

    r = (r//math.factorial(k))

    return r

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

decomposition = []
i = 2
while i * i <= M:
    if M % i == 0:
        decomposition.append(0)
        while M % i ==0:
            decomposition[-1] = decomposition[-1] + 1
            M = M//i
    i = i + 1
if M > 1:
    decomposition.append(1)

H = [ combination(N+k-1,k) % R for k in decomposition]
r = 1
for h in H:
    r = (r*h) % R

print(r)
### BUGGY CODE ###

import copy
import functools
import fractions

n=int(input())
lstA=list(map(int,input().split()))
maximum=max(lstA)
gcdlst=[]

for i in range(n):
    cplstA=copy.copy(lstA)
    del cplstA[i]
    gcdlst.append(functools.reduce(fractions.gcd, cplstA))

print(max(gcdlst))

### FIXED CODE ###

#import sys
#input=sys.stdin.readline

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    n = int(input())
    A = list(map(int, input().split()))
    gcdA = [0]*n
    gcdB = [0]*n
    gcdA[0] = A[0]
    gcdB[n-1] = A[n-1]
    for i in range(1, n):
        gcdA[i] = gcd(A[i], gcdA[i-1])
        gcdB[n-i-1] = gcd(A[n-i-1], gcdB[n-i])
    ans = max(gcdA[n-2], gcdB[1])
    for i in range(1, n-1):
        ans = max(ans, gcd(gcdA[i-1], gcdB[i+1]))
    print(ans)


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

a=int(input())
ai=[int(i) for i in input().split()]

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

for i in range(len(ai)):
    print(sum([cmb(x,2) for x in [sorted(ai[:i]+ai[i+1:]).count(x) for x in set(sorted(ai[:i]+ai[i+1:])) if sorted(ai[:i]+ai[i+1:]).count(x)>1]]))

### FIXED CODE ###

import collections
a=int(input())
ai = list(map(int, input().split()))
c = collections.Counter(ai)
val=0
for i in c.values():
    val+=i*(i-1)//2
for i in range(len(ai)):
    b=c[ai[i]]
    print(val-b+1)
### BUGGY CODE ###

# atcoder problems solving
# League
import sys
input= sys.stdin.readline
from collections import deque
N = int(input())
graph = {(i, j): [] for i in range(1, N+1) for j in range(i+1, N+1)}
indegree = {(i, j): 0 for i in range(1, N+1) for j in range(i+1, N+1)}

for i in range(N):
    a = list(map(int, input().split()))
    for j in range(N-2):
        x, y = a[j], a[j+1]
        z, w = i+1, i+1
        graph[(min(z,x),max(z, x))].append((min(w,y),max(w, y)))
        indegree[(min(w,y),max( w,y))] += 1

d = deque()
e = deque()
visited = {(i, j): False for i in range(1, N+1) for j in range(i+1, N+1)}
cnt = 1
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if indegree[(i, j)] == 0:
            d.append((i, j))
            visited[(i, j)] = True
while d:
    while d:
        x = d.popleft()
        for node in graph[x]:
            indegree[node] -= 1
            if indegree[node] == 0:
                e.append(node)
                visited[node]=True
    if e:
        d = e
        e = deque()
        cnt += 1
flag = bool(all(visited[(i, j)] == True for i in range(1, N+1)
                for j in range(i+1, N+1)))

if flag:
    print(cnt)
else:
    print(-1)

### FIXED CODE ###

n=int(input())
import time
T=time.time()
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    if time.time()-T>1.5:
        flag=False
        semi=True
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
    print(-1)
  if semi:
    print(499500)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
if n % 2 == 1:
    for i in range(1,n//2+1):
        if l.count(2*i) != 2:
            print(0)
            exit()
    print(pow(2,n//2))
else:
    for i in range(n//2):
        if l.count(2*i+1) != 2:
            print(0)
            exit()
    print(pow(2,n//2))


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort()
mod = 10**9+7
if n % 2 == 1:
    if l[0] != 0:
        print(0)
        exit()
    count = 2
    for i in range(1,n-1,2):
        
        if l[i] != count or l[i] != l[i+1]:
            print(0)
            exit()
        count += 2
    print(pow(2,n//2,mod))
else:
    count = 1
    for i in range(0,n-1,2):
        if l[i] != count or l[i] != l[i+1]:
            print(0)
            exit()
        count += 2
    print(pow(2,n//2,mod))
### BUGGY CODE ###

# coding: utf-8 
r, g, b, n = map(int, input().split())
cnt = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        if n-i*r-j*g>=0 and (n-i*r-j*g)%b==0:
            cnt+=1
print(cnt)


### FIXED CODE ###

# coding: utf-8 
r, g, b, n = map(int, input().split())
cnt = 0
for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n-i*r-j*g)%b==0:
            cnt+=1
print(cnt)
### BUGGY CODE ###

#!/usr/bin/python3
import sys
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = sys.stdin.readline

# main
n = int(readline())
xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
# [..., (x_i, y_i, i), ...]
# sort by x
xy.sort()

root = int(math.sqrt(len(xy)))

low = [x for x, y, i in xy[::root]]
high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
    ret = []
    for i in range(bisect_left(high, sx), bisect_right(low, tx)):
        k, v = xy[i]
        for i in range(bisect_left(k, sy), bisect_right(k, ty)):
            if sx <= v[i][0] <=tx:
                ret.append(v[i][2])
    if ret:
        ret.sort()
        print('\n'.join(map(str,ret)))
    print()

### FIXED CODE ###

#!/usr/bin/python3
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    n = int(readline())
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(n)]
    # [..., (x_i, y_i, i), ...]
    # sort by x
    xy.sort()

    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i + root], key=itemgetter(1)) for i in range(0, len(xy), root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()

main()
### BUGGY CODE ###

S, T = input(), input()

def lcs(S, T):
  LS = len(S)
  LT = len(T)
 
  dp=[["" for _ in range(LT + 1)] for _j in range(LS + 1)]
  # dp[Sのi番目][Tのj番目] := それまでの最大長
 
  for i in range(LS):
    for j in range(LT):
      if S[i] == T[j]:
        dp[i + 1][j + 1] += dp[i][j] + S[i]
      else:
        if len(dp[i + 1][j]) >= len(dp[i][j + 1]):
          dp[i + 1][j + 1] = dp[i + 1][j]
        else:
          dp[i + 1][j + 1] = dp[i][j + 1]
  return dp[-1][-1]

print(lcs(S, T))

### FIXED CODE ###

S = input()
T = input()
 
lenS = len(S)
lenT = len(T)
 
lcs = [[0 for i in range(lenT + 1)] for j in range(lenS + 1)]
 
for i in range(lenS):
  for j in range(lenT):
    if S[i] == T[j]:
      lcs[i + 1][j + 1] = lcs[i][j] + 1
    else:
      lcs[i + 1][j + 1] = max(lcs[i + 1][j], lcs[i][j + 1])
#for i in range(lenS + 1):
#  print(lcs[i])

i, j = lenS, lenT
answer = ""
while i != 0 and j != 0:
  if lcs[i - 1][j] == lcs[i][j] - 1:
    if lcs[i][j - 1] == lcs[i][j] - 1:
      answer += S[i - 1]
      i -= 1
    j -= 1
  else:
    i -= 1
  #print(i, j, lcs[i][j], answer)
print(answer[::-1])
### BUGGY CODE ###

#C問題
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 0
div = 0
flag = 1
while flag == 1:
    flag = 0
    for i in range(N):
        if B[i]-B[i-1]-B[(i+1)%N] >= A[i]:
            div = (B[i]-A[i])//(B[i-1]+B[(i+1)%N])
            B[i] -= (B[i-1]+B[(i+1)%N])*div
            ans+=div
            flag = 1
            
print(ans if A == B else -1)

### FIXED CODE ###

#C問題
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 0
div = 0
flag = 1
while flag == 1:
    flag = 0
    for i in range(N):
        if B[i]-B[i-1]-B[(i+1)%N] >= A[i]:
            div = (B[i]-A[i])//(B[i-1]+B[(i+1)%N])
            B[i] -= (B[i-1]+B[(i+1)%N])*div
            ans+=div
            flag = 1
            
print(ans if A == B else -1)
### BUGGY CODE ###

n=int(input())
s=input()

passwords =[]

for a in range(n-2):
    for b in range(a+1,n-1):
        for c in range(b+1,n):
            
            pw = s[a] + s[b] + s[c] 
            passwords.append(pw)
            passwords = list(set(passwords))
            
            # print(pw)

print(len(passwords))

### FIXED CODE ###

n=int(input())
s=input()

score = 0

for p in range(1000):
    
    pw = str(p).zfill(3)
    
    start = 0
    n_match = 0
    
    for j in range(3):
        for i in range(start, len(s)):
            
            if s[i] == pw[j]:
                start = i+1
                n_match = n_match+1
                
                if j == 3-1:
                    # print(pw)
                    score = score+1
                
                break
        if n_match <= j:
            break
            
print(score)
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
B = []

for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(M):
    A.append(B[i])
    B.append(A[i])

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        if visited not in result:
            result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(2*M):
                if A[i] == start:
                    path(B[i], visited)
            visited.pop()

path(1, [])
print(len(result))


### FIXED CODE ###

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

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(M):
                if A[i][0] == start:
                    path(A[i][1], visited)
                if A[i][1] == start:
                    path(A[i][0], visited)
            visited.pop()

path(1, [])
result = list(map(list, set(map(tuple, result))))
print(len(result))
### BUGGY CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n=int(input())

l=list(map(int,input().split()))
a=1
for i in range(0,n):
	a=a*l[i]


if a>10**18:
		print(-1)


if a<10**18+1:
	print(a)	 

### FIXED CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n=int(input())

l=sorted(list(map(int,input().split())))

a=1
if l[0]==0:
	print("0")

else:
	for i in range(0,n):
		a=a*l[i]
		if a>10**18:
			print(-1)
			break
		
	if a<10**18+1:
		print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    xy=[tuple(map(int,input().split())) for _ in range(n)]
    ans=INF
    from itertools import product
    for a,b in product(range(n),repeat=2):
        for c,d in product(range(a+1,n),range(b+1,n)):
            x0,x1=sorted([xy[a][0],xy[c][0]])
            y0,y1=sorted([xy[b][1],xy[d][1]])
            if k<=sum((x0<=x<=x1 and y0<=y<=y1) for x,y in xy):
                ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    X=[0]*n
    Y=[0]*n
    for i in range(n):
        X[i],Y[i]=map(int,input().split())
    ans=INF
    for a in range(n):
        for b in range(n):
            for c in range(a+1,n):
                for d in range(b+1):
                    x0,x1=sorted([X[a],X[c]])
                    y0,y1=sorted([Y[b],Y[d]])
                    count=0
                    for i in range(n):
                        if x0<=X[i]<=x1 and y0<=Y[i]<=y1:
                            count+=1
                    if count>=k:
                        ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()
### BUGGY CODE ###

from itertools import combinations

N = int(input())
SSS = [input() for _ in range(N)]

# Filter1
filter_1 = {'M', 'A', 'R', 'C', 'H'}
canditates = [S for S in SSS if S[0] in filter_1]

n_satisfied = 0
for cand in combinations(canditates, 3):
    cond1 = cand[0][0] != cand[1][0]
    cond2 = cand[1][0] != cand[2][0]
    cond3 = cand[2][0] != cand[0][0]
    if cond1 and cond2 and cond3:
        n_satisfied += 1

print(n_satisfied)


### FIXED CODE ###

# WIP
from itertools import combinations

N = int(input())
SSS = [input() for _ in range(N)]

# Filter1
filter_1 = {'M', 'A', 'R', 'C', 'H'}
canditates = [S for S in SSS if S[0] in filter_1]
cand_inits = [c[0] for c in canditates]
cand_inits_set = set(cand_inits)
init_counts = {init_c: cand_inits.count(init_c) for init_c in filter_1}

n_combi = 0
for init_combi in combinations(cand_inits_set, 3):
    tmp_combi = 1
    for init_c in init_combi:
        tmp_combi *= init_counts[init_c]

    n_combi += tmp_combi

print(n_combi)
### BUGGY CODE ###


def anagram(list1, list2):

    anagramFlg = 1

    for i in range(len(list1)):
        if list1[i] != list2[i]:
            anagramFlg = 0
            break

    return anagramFlg


n = int(input())

inputList=[]
for i in range(n):
    line = input()
    inputList.append(line)

# print(inputList)

sortedList = []
for i in range(n):
    tmpList = list(inputList[i])
    tmpList.sort()
    sortedList.append(tmpList)

cnt = 0

for i in range(n):
    for j in range(i+1, n):
        if anagram(sortedList[i], sortedList[j]) == 1:
            cnt += 1

print(cnt)













### FIXED CODE ###


def combinatnion(num, cmb):
    nmrtr = 1
    dnmntr = 1

    for i in range(cmb):
        nmrtr = nmrtr * (num - i)
        dnmntr = dnmntr * (i + 1)

    ans = int(nmrtr/dnmntr)
    return ans

n = int(input())

inputList=[]
for i in range(n):
    line = input()
    inputList.append(line)

# print(inputList)

sortedList = []
dic = {}
for i in range(n):
    tmpList = list(inputList[i])
    tmpList.sort()
    tmpword = "".join(tmpList)

    if tmpword in dic:
        dic[tmpword] = dic[tmpword] + 1
    else:
        dic[tmpword] = 1

    # print(dic)

# print(tmpword)

cnt = 0
for val in dic.values():
    if val != 1:
        cnt += combinatnion(val, 2)

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

N,K=map(int,input().split())
L=[]
for i in range(N):
    s,d=map(int,input().split())
    L.append([s,d])

High=10**30
Low =0
for i in range(300):
    Mid=(High + Low)/2
    cnt=0
    for j in range(N):
        cnt+=max(0,1+(Mid - L[j][0])//L[j][1])
    if cnt>=K:
        High = Mid
    elif cnt<K:
        Low = Mid
    #print(Mid)
import math
print(math.ceil(Mid))

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,K=map(int,input().split())
L=[]
for i in range(N):
    s,d=map(int,input().split())
    L.append([s,d])

High=10**20
Low =0
while High - Low >1:
    Mid=(High + Low)//2
    cnt=0
    for j in range(N):
        if Mid-L[j][0]<0:
            continue
        else:
            cnt+=max(0,1+(Mid - L[j][0])//L[j][1])
    if cnt>=K:
        High = Mid
    else:
        Low = Mid
    #print(High , Low)
Mid=int(Mid)
ans=0
for j in range(N):
    ans+=max(0,1+(Mid - L[j][0])//L[j][1])
if ans>=K:
    print(Mid)
else:
    print(Mid+1)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
ans = 0
nr = n // r
ng = n // g
for i in range(nr + 1):
    for j in range(ng + 1):
        tmp = n - i * r - j * g
        if tmp % b == 0 and tmp >= 0:
            ans += 1
print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n + 1):
    for j in range(n + 1):
        if i * r + j * g == n:
            ans += 1
        elif (n - (i * r + j * g)) >= 0 and (n - (i * r + j * g)) % b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

from itertools import combinations
from collections import Counter
n, k = map(int, input().split())
As = list(range(n+1))
s = 0
for i in range(k, n+2):
	l = Counter(list(map(sum, combinations(As, i))))
	s+=len(l)%(10**9+7)
print(s%(10**9+7))

### FIXED CODE ###

n, k = map(int, input().split())
import numpy
res = numpy.cumsum(range(n+2))
s=0
for i in range(k, n+2):
	s += (res[n+1] - res[n+1-i] - res[i] +1)%(10**9 +7)
print(s%(10**9 +7))