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

#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = [LI() for _ in range(n)]
ans = inf
for i in range(n):
    ux,uy = xy[i]
    for j in range(n):
        dx,dy = xy[j]
        for k in range(n):
            rx,ry = xy[k]
            for l in range(n):
                lx,ly = xy[l]
                if uy <= dy and rx <= lx:
                    continue
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for j in range(i+1,n):
        dy = Y[j]
        for k in range(n):
            rx = X[k]
            for l in range(k+1,n):
                lx = X[l]
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)
### BUGGY CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
g = 1
for i in range(n):
    g = a[i] * g // gcd(a[i], g)
    #g %= mod

ans = 0
for i in range(n):
    ans += g * modinv(a[i])
    ans %= mod

print(ans)


### FIXED CODE ###

from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
l = 1
for i in range(n):
    l = a[i] // gcd(l, a[i]) * l
    

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

d = 0
for i in range(n):
    d += modinv(a[i])

print((l*d) % mod)
### BUGGY CODE ###

N = int(input())
s = [input().split() for i in range(N)]
count = 0

s = [''.join(sorted(str(i))) for i in s]
s_set = list(set(s))
for i in range(len(s_set)):
    count += sum(range(1, s.count(s_set[i])))
print(count)

### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]
s.sort()
count = 0
num = 1
for i in range(N-1):
    if s[i] == s[i+1]:
        num += 1
    else:
        count += num * (num - 1) // 2
        num = 1
print(count + num * (num - 1) // 2)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
from operator import itemgetter
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(key=itemgetter(0),reverse=True)
s=[0]*n
a.append([0,0])
for i,p in enumerate(a[:-1]):
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        y = [z[1] for z in a[:i+1]]
        s[min(y)-1] += (i+1)*q

for t in s:
    print(t)

### FIXED CODE ###

# -*- coding:utf-8 -*-
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(reverse=True)
z = [l[1] for l in a]
s=[0]*n
a.append([0,0])
min_a_i = float('inf')
for i,p in enumerate(a[:-1]):
    min_a_i = min(min_a_i, a[i][1])
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        s[min_a_i-1] += (i+1)*q

for t in s:
    print(t)
### BUGGY CODE ###

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

mod = 998244353
F = [1]
RF = []


def inv(x):
    res = 1
    k = mod - 2
    y = x
    while k:
        if k & 1:
            res = (res * y) % mod
        y = (y * y) % mod
        k //= 2
    return res


def init():
    for i in range(N):
        F.append((F[i] * (i + 1)) % mod)
    for i in F:
        RF.append(inv(i))


def comb(x, y):
    if y < 0 or x < y:
        return 0
    return (F[x] * ((inv(F[x - y]) * inv(F[y])) % mod)) % mod


ans = 0
init()
for a in range(N):
    b = (K - a * A) / B
    if b < 0:
        break
    if b.is_integer():
        ans += (comb(N, a) * (comb(N, int(b)))) % mod
print(ans % mod)


### FIXED CODE ###

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

mod = 998244353
fact = [1] * (N + 1)
ifact = [1] * (N + 1)


def init():
    for i in range(N):
        fact[i + 1] = fact[i] * (i + 1) % mod
        ifact[i + 1] = pow(fact[i + 1], mod - 2, mod)


def comb(x, y):
    if y < 0 or y > x:
        return 0
    return (fact[x] * ifact[x - y] * ifact[y]) % mod


ans = 0
init()
for a in range(N + 1):
    n = K - a * A
    if n < 0:
        break
    if n % B == 0:
        ans += (comb(N, a) * (comb(N, n // B))) % mod
print(ans % mod)
### BUGGY CODE ###

n,a,b = map(int,input().split())
def kai(g):
    p = 1 
    for i in range(1,g+1):
        p = p*i
    return p
def comb(n,k):
    return kai(n)/(kai(k)*kai(n-k))
print(int(2**n-1-comb(n,a)-comb(n,b)))

### FIXED CODE ###

n,a,b = map(int,input().split())
def cmb(n, r, mod):
    x = 1 
    y = 1
    for i in range(r):
        x = x*(n-i)%(mod)
    for i in range(1,r+1):
        y = y*i%(mod)
    return x * pow(y,mod-2,mod) %mod

v = int(pow(2,n,10**9+7)-1-cmb(n,a,10**9+7)-cmb(n,b,10**9+7))
if v >= 0:
    print(v)
else:
    if v+10**9+7 >= 0:
        print(v+10**9+7)
    else:
        print(v+2*(10**9+7))
### BUGGY CODE ###

import random
from copy import deepcopy

d = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for _ in range(d)]

def min_max(l):
    l_min = min(l)
    l_max = max(l)
    return [0.1+(i-l_min)/(l_max-l_min)for i in l]

dd = [max(s[i]) for i in range(d)]
qq = min_max(c)
dd = min_max(dd)

ddd = [i for i in range(d)]
qqq = [i for i in range(26)]

ans = []
last = [0]*26
for i in range(d):
    ma_po = -10**10
    ma_di = 0
    for j in range(26):
        po = s[i][j]
        for k in range(26):
            if k == j:
                continue
            po -= c[k]*(i+1-last[k])
        if po > ma_po:
            ma_po = po
            ma_di = j
    last[ma_di] = i+1
    ans.append(ma_di+1)

def score(l):
    lastd = [0]*26
    point = 0
    for j,k in enumerate(l):
        kk = k-1
        point += s[j][kk]
        lastd[kk] = j+1
        for l in range(26):
            point -= c[l]*(j+1-lastd[l])
    return point

ma = score(ans)

def random_search():
    global ans,ma
    li = deepcopy(ans)
    D = random.choices(ddd,k=1,weights=dd)[0]
    Q = random.choices(qqq,k=1,weights=qq)[0]
    li[D] = Q+1
    if score(li) > ma:
        ans = deepcopy(li)
        ma = score(li)

for i in range(28000):
    random_search()

for i in ans:
    print(i)

### FIXED CODE ###

import random

d = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for _ in range(365)]

for i in range(d):
    print(random.randrange(1, 27, 1))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter


def solve(N: int, a: "List[int]"):

    c = Counter(a)
    kitai = [[[0]*(N+2) for _ in range(N+2)] for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(c[2]+c[3]+1):
            for i in range(c[1]+c[2]+c[3]+1):
                if i == 0 and j == 0 and k == 0:
                    continue
                res = N
                if i:
                    res += kitai[k][j][i-1]*i
                if j:
                    res += kitai[k][j-1][i+1]*j
                if k:
                    res += kitai[k-1][j+1][i]*k
                res /= (i+j+k)
                kitai[k][j][i] = res
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):

    c = [0]*4
    for A in a:
        c[A] += 1

    J = min(c[2]+c[3]+1, N+1)
    I = min(c[1]+c[2]+c[3]+1, N+1)
    kitai = [[[0]*(I+1) for _ in range(J+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(J):
            for i in range(I):
                tot = i+j+k
                if tot == 0 or tot > N:
                    continue
                res = N + kitai[k][j][i-1]*i + \
                    kitai[k][j-1][i+1]*j + kitai[k-1][j+1][i]*k
                kitai[k][j][i] = res/tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


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

import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

def solve(blocks):
    n_vert_cut = 0
    n_block = blocks.shape[0]
    vals = np.zeros(n_block)

    for c in range(W):
        adds = blocks[:, c]
        if np.any(adds > K):
            return H * W
        
        sums = vals + adds
        if np.any(sums > K):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    ans = min(ans, solve(blocks))
print(ans)


### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
    
def main():
	num = int(input())
	sum = 0
	for i in range(num):
		a = i+1
		for j in range(num):
			b = j+1
			for k in range(num):
				c = k+1
				if a == b:
					sum += math.gcd(a,c)
				elif b == c or a == c:
					sum += math.gcd(a,b)
				else:
					sum += gcd(a,b,c)
	print (sum)

if __name__ == '__main__':
	main()


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import math

    
def main():
	num = int(input())
	sum = 0
	for i in range(num):
		a = i+1
		for j in range(num):
			b = j+1
			for k in range(num):
				c = k+1
				sum += math.gcd(math.gcd(a,b),c)
	print (sum)

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

import bisect

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
b=[int(i) for i in input().split()]
b.sort()
c=[int(i) for i in input().split()]
c.sort()
#print(n,a,b,c)

ans=0
for j in range(n):
    aa=bisect.bisect_right(b, a[j])
    if aa < n:
        for i in range(aa,n):
            bb=bisect.bisect_right(c, b[i])
            ans+=n-bb

print(ans)

### FIXED CODE ###

import bisect

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
c.sort()
#print(n,a,b,c)

ans=0
for j in range(n):
    aa=bisect.bisect_left(a, b[j])
    bb=bisect.bisect_right(c, b[j])
    ans+=aa*(n-bb)

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

# -*- coding: utf-8 -*-

S = input()
Symbol = list(S)
MOD =[1,0,0,0,0,0,0,0,0,0,0,0,0]

for D in Symbol:
    NMOD =[0,0,0,0,0,0,0,0,0,0,0,0,0]
    for N in range(10):
        if D != '?' and int(D) != N:
            continue
        #end if
        for M in range(13):
            NM = (M * 10 + N) % 13
            NMOD[NM] += MOD[M]
        #end for
    #end for
    for M in range(13):
        MOD[M] = NMOD[M]%1000000007
    #end for
#end for

print(MOD[5])


### FIXED CODE ###

# -*- coding: utf-8 -*-

R10 = range(10)
R13 = range(13)

S = input()
R = [[(M-N)*4 % 13 for N in R10] for M in R13]
AM = 10**9+7

MOD =[1]+[0]*12

for D in S:
    if D == '?':
        MOD = [sum([MOD[N] for N in M])%AM for M in R]
    else:
        C = int(D)
        MOD = [MOD[M[C]] for M in R]
    #end if
#end for

print(MOD[5])
### BUGGY CODE ###

import statistics
import copy

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

for i in range(N):
    buf = copy.copy(X)
    buf.pop(i)
    print(statistics.median(buf))

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)
a = Y[N // 2 - 1]
b = Y[N // 2]

for i in X:
    if i <= a:
        print(b)
    elif i >= b:
        print(a)
### BUGGY CODE ###

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

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

kitaiti = []
for p in P:
    kitaiti.append( (((p+1)*p)//2) / p )

maxs = 0
for i in range(K,N+1):
    temp = sum(kitaiti[i-K:i])
    if temp > maxs:
        maxs = temp

print(maxs)

### FIXED CODE ###

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N,K=input_int()
P= many_int()

kitaiti = [0]
for p in P:
    kitaiti.append((p+1)/2 )



maxs = 0
temp = sum(kitaiti[:K])
for i in range(N-K+1):

    temp += kitaiti[i+K]
    temp -= kitaiti[i]

    if temp > maxs:
        maxs = temp


print(maxs)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from functools import lru_cache

PRIME = 10 ** 9 + 7


@lru_cache(maxsize=None)
def digitmod13(n):
    return (10 ** n) % 13


def main():
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N)]
    S = S[::-1]
    # init
    first = S[0]
    if first == '?':
        for k in range(10):
            dp[0][k] = 1
    else:
        first = int(first)
        dp[0][first] = 1
    for i in range(1, N):
        c = S[i]
        if c == '?':
            for d in range(13):
                for k in range(10):
                    dp[i][(d + k * digitmod13(i)) % 13] += dp[i - 1][d]
        else:
            c = int(c)
            for d in range(13):
                dp[i][(d + c * digitmod13(i)) % 13] += dp[i - 1][d]
        for d in range(13):
            dp[i][d] %= PRIME
    
    print(dp[N - 1][5] % PRIME)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from functools import lru_cache

PRIME = 10 ** 9 + 7


@lru_cache(maxsize=None)
def digitmod13(y):
    if y == 0:
        return 1
    elif y == 1:
        return 10 % 13
    elif y % 2 == 0:
        return digitmod13(y // 2) ** 2 % 13
    else:
        return digitmod13(y // 2) ** 2 * 10 % 13


def main():
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N)]
    S = S[::-1]
    
    # init
    first = S[0]
    if first == '?':
        for k in range(10):
            dp[0][k] = 1
    else:
        first = int(first)
        dp[0][first] = 1
    
    # prepare table
    table = [[[(i + (j * k)) % 13 for k in range(13)] for j in range(10)] for i in range(13)]
    
    # dp
    for i in range(1, N):
        c = S[i]
        if c == '?':
            for d in range(13):
                for k in range(10):
                    mod = table[d][k][digitmod13(i)]
                    dp[i][mod] += dp[i - 1][d]
                    dp[i][mod] %= PRIME
        else:
            c = int(c)
            for d in range(13):
                mod = table[d][c][digitmod13(i)]
                dp[i][mod] += dp[i - 1][d]
                dp[i][mod] %= PRIME
    
    print(dp[N - 1][5] % PRIME)


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

s = list(input())
n = int(input())
q = [list(map(str, input().split())) for _ in range(n)]

for i in range(n):
    if q[i][0] == "1":
        s = s[::-1]
    if q[i][0] == "2":
        if q[i][1] == "1":
            s.insert(0, q[i][2])
        elif q[i][1] == "2":
            s.append(q[i][2])

print("".join(s))


### FIXED CODE ###

from collections import deque

d = deque(input())
q = int(input())

reverse = False

for _ in range(q):
    query = list(input().split())
    if query[0] == '1':
        if reverse:
            reverse = False
        else:
            reverse = True
        continue
    else:
        if query[1] == '1':
            if reverse:
                d.append(query[2])
            else:
                d.appendleft(query[2])
        else:
            if reverse:
                d.appendleft(query[2])
            else:
                d.append(query[2])

if reverse:
    d = list(reversed(d))


print("".join(map(str, d)))
### BUGGY CODE ###

import re

tmp = raw_input()

length = len(tmp)


for i in range(length):
    tmp = tmp.replace("01", "")
    tmp = tmp.replace("10", "")


length2 = len(tmp)

division = length - length2

print(division)

### FIXED CODE ###

import re

tmp = raw_input()

length = len(tmp)


tmp1 = tmp.replace("0", "")
tmp2 = tmp.replace("1", "")

if len(tmp1) > len(tmp2):
    tmp3 = len(tmp1) - len(tmp2)

else:
    tmp3 = len(tmp2) - len(tmp1)


division = length - tmp3

print(division)
### BUGGY CODE ###

s=list(input())
q=int(input())
for _ in range(q):
  t=list(input().split())
  if len(t)==1:
    s=s[::-1]
  else:
    if int(t[1])==1:
      s=[t[2]]+s
    else:
      s=s+[t[2]]
print(''.join(s))


### FIXED CODE ###

s=list(input())
q=int(input())
t1,t2=[],[]
cnt=0
for _ in range(q):
  t=list(input().split())
  if len(t)==1:
    cnt+=1
    t1,t2=t2,t1
  else:
    if int(t[1])==1:
      t1+=[t[2]]
    else:
      t2+=[t[2]]
if cnt%2==1:
  s=s[::-1]
u=t1[::-1]+s+t2
print(''.join(u))
### BUGGY CODE ###

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

a.sort(reverse=True)

print(sum(a[:n]))

### FIXED CODE ###

n, m = map(int, input().split())
a = [(int(i), 1) for i in input().split()]
for i in range(m):
    b, c = map(int, input().split())
    a += [(c, b)]

a.sort(reverse=True)

ans = 0
i = 0
j = 0
while True:
    ans += a[i][0] * min(a[i][1], n-j)
    j += a[i][1]
    i += 1
    if j >= n:
        print(ans)
        break
### BUGGY CODE ###

from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
ab = [[int(x) - 1 for x in stdin.readline().rstrip().split()] for _ in range(N - 1)]
inf = 1000000007

graph = [[] for _ in range(N)]
for n in range(N - 1):
    graph[ab[n][0]].append(ab[n][1])
    graph[ab[n][1]].append(ab[n][0])

stack = [0]
ans = 1
done = [False for _ in range(N)]
cnt = 0
parent = -1
while len(stack) > 0:
    now = stack.pop(0)
    done[now] = True
    cnt = 0
    for x in graph[now]:
        if not done[x]:
            cnt += 1
            stack.append(x)
    if now == 0:
        temp = 1
        for i in range(cnt):
            ans = (K - 1 - i) * ans % inf
    else:
        temp = 1
        for i in range(cnt):
            ans = (K - 2 - i) * ans % inf
print(ans * K % inf)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8

import sys

N, M = map(int, sys.stdin.readline().split(" ", 2))

L = []
R = []

ans = [0] * N
for line in sys.stdin:
    l, r = map(int, line.split(" ", 2))
    for i in range(l, r+1):
        ans[i-1] += 1
print(sum(1 for a in ans if a == M))


### FIXED CODE ###

# coding: utf-8

import sys
import numpy as np

N, M = map(int, sys.stdin.readline().split(" ", 2))

L = 0
R = M + N
for line in sys.stdin:
    l, r = map(int, line.split(" ", 2))
    if l > L:
        L = l
    if r < R:
        R = r
print(max(0, R - L + 1))
    # L.append(l)
    # R.append(r)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
power = 0
for i in range(len(l)//3):
    power += l[-2]
    l = l[1:-2]
print(power)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
power = 0
for i in range(1,len(l)//3+1):
    power += l[-2*i]
print(power)
### BUGGY CODE ###

def cycle(x):
    result = 0
    for y in range(int(x), 0, -1):
        result += y - 1
    return result


def main():
    N = int(input())
    a_list = list(map(int, input().split()))
    dict_a_list = dict()
    for a in a_list:
        if a in dict_a_list:
            dict_a_list[a] += 1
            continue
        dict_a_list[a] = 1
    for a in a_list:
        result = 0
        dict_a_list[a] -= 1
        for v in dict_a_list.values():
            result += cycle(v)
        print(result)
        dict_a_list[a] += 1


if __name__ == '__main__':
    main()


### FIXED CODE ###

def cycle(x):
    result = 0
    for y in range(int(x), 0, -1):
        result += y - 1
    return result


def main():
    input()
    a_list = list(map(int, input().split(' ')))
    dict_a_list = dict()
    dict_result = dict()
    for a in a_list:
        if a in dict_a_list:
            dict_a_list[a] += 1
            continue
        dict_a_list[a] = 1
    for a in a_list:
        result = 0
        if dict_a_list[a] in dict_result:
            print(dict_result[dict_a_list[a]])
            continue
        dict_a_list[a] -= 1
        for v in dict_a_list.values():
            result += cycle(v)
        print(result)
        dict_a_list[a] += 1
        dict_result[dict_a_list[a]] = result


if __name__ == '__main__':
    main()