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

from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

N = input()
A = list(map(int, input().split()))
ps = primes(10**6+1)
for p in ps:
    cnt = 0
    for a in A:
        if a % p == 0:
            cnt += 1
    if cnt > 1:
        break
else:
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

N = input()
A = list(map(int, input().split()))
M = 10**6+1
spf = [i for i in range(M)]
for i in range(2, M):
    if spf[i] == i:
        for j in range(i+i, M, i):
            spf[j] = i
cnt = defaultdict(int)
for a in A:
    ps = set()
    while a != 1:
        ps.add(spf[a])
        a = a // spf[a]
    for p in ps:
        cnt[p] += 1
if all([x < 2 for x in cnt.values()]):
    print("pairwise coprime")
    exit()
gcd = lambda x, y : x if y == 0 else gcd(y, x % y)
x = A[0]
for a in A[1:]:
    x = gcd(x, a)
if x == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def f(sx, sy):
    q = collections.deque()
    q.append((sx, sy))
    dist = [[float("inf") for w in range(W)] for h in range(H)]
    dist[sx][sy] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < W and w2 >= 0 and w2 < H:
                if S[h2][w2] == "." and dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
                if S[h2][w2] == '#':
                    return d + 1
    return 0
ans = 0
for i in range(H):
    for k in range(W):
        if S[i][k] == '.':
            ans = max(ans,f(k,i))
print(ans)

### FIXED CODE ###

import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def f():
    q = collections.deque()
    dist = [[float("inf")] * W for _ in range(H)]
    for i in range(H):
        for k in range(W):
            if S[i][k] == '#':
                q.append((i,k))
                dist[i][k] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist
ans = 0
dist = f()
for i in range(H):
    for k in range(W):
        ans = max(ans,dist[i][k])
print(ans)
### BUGGY CODE ###

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

train=[]
Query=[]
for i in range(M):
  train.append(list(map(int,input().split())))
for i in range(Q):
  answer=0
  Query=list(map(int,input().split()))
  for j in range(M):
    if train[j][0]>=Query[0] and train[j][1]<=Query[1]:
      answer+=1
  print(answer)
  

### FIXED CODE ###

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


Query=[]
answer=[[0]*N for i in range(N)]
for i in range(M):
  L,R=map(int,input().split())
  answer[N-L][R-1]+=1

for i in range(1,N):
  answer[0][i]+=answer[0][i-1]
  answer[i][0]+=answer[i-1][0]
  
for i in range(1,N):
  for j in range(1,N):
    answer[i][j]+=answer[i-1][j]
    answer[i][j]+=answer[i][j-1]
    answer[i][j]-=answer[i-1][j-1]
for i in range(Q):
  p,q=map(int,input().split())
  print(answer[N-p][q-1])
'''
for i in range(Q):
  answer=0
  Query=list(map(int,input().split()))
  for j in range(M):
    if train[j][0]>=Query[0] and train[j][1]<=Query[1]:
      answer+=1
  print(answer)
'''
### BUGGY CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	A[x].append(y)
	A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost += 1
		q.append(i)
		for _ in range(N):
			if len(q) == 0:
				break
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)


### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	A[x].append(y)
	A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost += 1
		q.append(i)
		while len(q):
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)
### BUGGY CODE ###

N=int(input())
h_list=[int(x) for x in input().split()]
flag=True
for i in range(len(h_list)-1):   
    if sorted(h_list)==h_list:
        flag=True
        break
        
    tmp=h_list[i:]
    if tmp[0]-min(tmp[1:])>=2:
        flag=False
        break
        
if flag:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N=int(input())
h_list=[int(x) for x in input().split()]

flag=True

m=h_list[0]
for j in range(len(h_list)-1):
    if m<h_list[j]:
        m=h_list[j]
    if m-h_list[j+1]>=2:
        flag=False
        break        
    
if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    query= list(input().split()) 
    if query[0] == '1':
        S = S[::-1]
    elif query[0] == '2':
        if query[1] == '1':
            S = ''.join([query[2],S])
        elif query[1] == '2':
            S = ''.join([S,query[2]])

print(S)

### FIXED CODE ###

def main():

    S = input()
    Q = int(input())

    reverse = False
    head = ''
    tail = ''

    for _ in range(Q):
        query= input()
        if query == '1':
            reverse = not reverse
            head, tail = tail, head
        else:
            _, f, c = query.split()
            if f == '1':
                head = ''.join([head,c])
            else:
                tail = ''.join([tail,c])

    if reverse:
        S = S[::-1]

    print(''.join([head[::-1], S, tail]))

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

import heapq
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append([c, b - 1])
    G[b - 1].append([c, a - 1])
Q, K = map(int, input().split())

def dijkstra(s, N, G, x, y):
    d = [20 ** 9] * N
    d[s] = 0
    hq = [[0, s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        v, i = heapq.heappop(hq)
        if d[i] < v:
            continue
        for c, j in G[i]:
            if d[j] > d[i] + c:
                d[j] = d[i] + c
                heapq.heappush(hq, [d[j], j])
    return d[x] + d[y]

dist = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    dist[i] = dijkstra(K - 1, N, G, x - 1, y - 1)

for d in dist:
    print(d)

### FIXED CODE ###

import heapq
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append([c, b - 1])
    G[b - 1].append([c, a - 1])
Q, K = map(int, input().split())

def dijkstra(s, N, G):
    d = [float('inf')] * N
    d[s] = 0
    hq = [[0, s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        v, i = heapq.heappop(hq)
        if d[i] < v:
            continue
        for c, j in G[i]:
            if d[j] > d[i] + c:
                d[j] = d[i] + c
                heapq.heappush(hq, [d[j], j])
    return d

D = dijkstra(K - 1, N, G)

dist = [0] * Q
for i in range(Q):
    x, y = map(int, input().split())
    dist[i] = D[x - 1] + D[y - 1]

for d in dist:
    print(d)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
point = [K for _ in range(N)]
for i in range(Q):
  A = int(input())
  point = list(map(lambda x: x - 1, point))
  point[A-1] += 1
for i in point:
  if i > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k,q=map(int,input().split());a=[k-q for i in range(n)]
for _ in range(q): a[int(input())-1]+=1
print(*['Yes' if i>0 else 'No' for i in a],sep='\n')
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())
x = input()
o = int(x, 2)
for i in reversed(range(n)):
    if o >> i & 1:
        t = o - 2**i
    else:
        t = o + 2**i
    count = 0
    while t > 0:
        t %= bin(t).count("1")
        count += 1
    print(count)


### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
x = input()
c = x.count("1")
m = 0
m2 = 0
for i in range(n):
    if x[i] == "1":
        m += pow(2, (n - i - 1), c + 1)
        m %= c + 1
m2 = 0
if c!=1:
    for i in range(n):
        if x[i] == "1":
            m2 += pow(2, (n - i - 1), c - 1)
            m2 %= c - 1

for i in range(n):
    if x[i] == "1":
        if c != 1:
            t = m2 - pow(2, (n - i - 1), c - 1)
            t %= c - 1
            count = 1
        else:
            t = 0
            count = 0
    else:
        t = m + pow(2, (n - i - 1), c + 1)
        t %= c + 1
        count = 1
    while t > 0:
        t %= bin(t).count("1")
        count += 1
    print(count)
### BUGGY CODE ###

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

# なんこか入力
n,m = map(int, input().split())


# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(n)] 

x = sorted(x, key=lambda x: x[0])
x = sorted(x, key=lambda x: -x[1])
y = [0]*m
#print(x)


for i in range(n):
    for j in range(x[i][0]-1,m):
        if y[j] == 0:
            y[j] = x[i][1]
            break
#    print(y)

answer=0
for i in range(m):
    answer += y[i]
print(answer)






### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import heapq
from operator import itemgetter

# なんこか入力
n,m = map(int, input().split())

# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(n)] 

x = sorted(x,key=itemgetter(1),reverse = True)
x = sorted(x,key=itemgetter(0))

work = []
j = 0
answer = 0
for i in range(1,m+1,1):
    while j < n and x[j][0] == i:
        heapq.heappush(work,-x[j][1])
#        print(work)
        j += 1
    if work:
        answer -= heapq.heappop(work)

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

from collections import deque
s=list(str(input()))
s=deque(s)
q=int(input())
cnt=0
for i in range(q):
    que=list(input().split())
    if len(que)==1:
        cnt+=1
    else:
        if cnt%2!=0:
            s.reverse()
        if int(que[1])==1:
            s=deque(s)
            s.appendleft(que[2])
            cnt=0
        elif int(que[1])==2:
            s=deque(s)
            s.append(que[2])
            cnt=0
if cnt%2!=0:
    s.reverse()
print(''.join(s)) 

### FIXED CODE ###

from collections import deque
s=list(str(input()))
s=deque(s)
q=int(input())
cnt=0
for i in range(q):
    que=list(input().split())
    if len(que)==1:
        cnt+=1
    if len(que)!=1 and cnt%2==0:
        if int(que[1])==1:
            s.appendleft(que[2])
        elif int(que[1])==2:
            s.append(que[2])
    if len(que)!=1 and cnt%2!=0:
        if int(que[1])==1:
            s.append(que[2])
        elif int(que[1])==2:
            s.appendleft(que[2])
if cnt%2!=0:
    s.reverse()
print(''.join(s))
### BUGGY CODE ###

import math
import collections
def main():

    N = int(input())
    d = collections.defaultdict(int)
    for i in range(1, N+1):
        d[i] = 2
    d[1] = 1

    ans = 0
    for i in range(2, N//2+1):
        p = i + i
        while p <= N:
            d[p] += 1
            # if p // i > int(math.sqrt(N)):
                # d[p] += 1
            p += i

    for i in range(1, N+1):
        ans += i * d[i]

    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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

N, K = map(int, input().split())
people = list(input())
lst = []
count = 0
flag = people[0]
for i in range(len(people)):
	if i == len(people) - 1:
		lst.append(count + 1) if flag == '1' else lst.append(count * -1 - 1)
	elif people[i] == flag and people[i+1] != flag:
		lst.append(count + 1) if flag == '1' else lst.append(count * -1 - 1)
		count = 0
		flag = people[i + 1]
	else:
		count += 1

maximum = 0
for i in range(len(lst)):
	if lst[i] < 0:
		if i != 0:
			temp = list(map(abs, lst[i-1:i+2*K]))
		else:
			temp = list(map(abs, lst[i:i+2*K]))
		maximum = max(maximum, sum(temp))
	else:
		temp = list(map(abs, lst[i:2*K+1]))
		maximum = max(maximum, sum(temp))
print(maximum)


### FIXED CODE ###

N, K = map(int, input().split())
people = list(input())
lst = []
count = 0
flag = people[0]
if flag == '1':
	lst.append(0)
for i in range(len(people)):
	if i == len(people) - 1:
		lst.append(count + 1)
	elif people[i] == flag and people[i+1] != flag:
		lst.append(count + 1)
		count = 0
		flag = people[i + 1]
	else:
		count += 1

maximum = 0
l = len(lst)
temp = sum(lst[0:2*K])
maximum = max(maximum, temp)
for i in range(2, l, 2):
	end = i+2*K
	temp = temp - lst[i-2] + sum(lst[end-2:end])
	if i != 2:
		temp -= lst[i-3]
	maximum = max(maximum, temp)

print(maximum)
### BUGGY CODE ###

import math
n = int(input())
prime = []
insu = {}
for i in range(2, math.ceil(math.sqrt(n))):
    if i > n:
        break
    flag = 0
    for p in prime:
        if i%p == 0:
            flag = 1
            break
    if flag == 0:
        prime.append(i)
        while n%i == 0:
            if i in insu:
                insu[i] += 1
            else:
                insu[i] = 1
            n //= i

if n != 1 and len(insu)==0:
    insu[n] = 1

count = 0
for v in insu.values():
    i = 1
    while v >= i:
        v -= i
        i += 1
        count += 1

print(count)

### FIXED CODE ###

import math
n = int(input())
prime = []
insu = {}
max_itr = math.ceil(math.sqrt(n))+1
try_range = [2] + list(range(3, max_itr, 2))
for i in try_range:
    if i > max_itr:
        break
    if n%i == 0:
        flag = 0
        for p in prime:
            if i%p == 0:
                flag = 1
                break
        if flag == 0:
            prime.append(i)
            while n%i == 0:
                if i in insu:
                    insu[i] += 1
                else:
                    insu[i] = 1
                n //= i
            if n < max_itr:
                max_itr = n

if n != 1:
    insu[n] = 1
# print(insu)

count = 0
for v in insu.values():
    i = 1
    while v >= i:
        v -= i
        i += 1
        count += 1

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

from sys import stdin
S = (stdin.readline().rstrip())
dp = [[0]*13 for i in range(len(S)+1)]
MOD = 10**9+7

a = [0] + [(10**i) % 13 for i in range(len(S))]
dp[0][0] = 1

cnt = 1
for i, c in enumerate(S[::-1], 1):
    for j in range(13):
        if c == "?":
            for k in range(10):
                nj = (k*a[i]+j) % 13
                dp[i][nj] = dp[i][nj] + dp[i-1][j]
                dp[i][nj] %= MOD
        else:
            nj = (int(c)*a[i]+j) % 13
            dp[i][nj] = dp[i][nj] + dp[i-1][j]
            dp[i][nj] %= MOD
print(dp[-1][5])

### FIXED CODE ###

from sys import stdin
S = (stdin.readline().rstrip())
dp = [[0]*13 for i in range(len(S)+1)]
MOD = 10**9+7
 
S = list(reversed(S))
dp[0][0] = 1
 
t = 1
for i, c in enumerate(S, 1):
    for j in range(13):
        if c == "?":
            for k in range(10):
                nj = (k*t+j) % 13
                dp[i][nj] = dp[i][nj] + dp[i-1][j]
                dp[i][nj] %= MOD
        else:
            nj = (int(c)*t+j) % 13
            dp[i][nj] = dp[i][nj] + dp[i-1][j]
            dp[i][nj] %= MOD
    t = (t*10)%13
print(dp[-1][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
bn = (n-1).bit_length()
b_num = 2**bn
mx = 10**9
segl=[mx]*2*b_num 

if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x,0,x,i), (t-x,1,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2,0,0))
    xs.sort()
    ys = set()
    for x in xs:
        if x[1]==2:
            for _ in range(bn):
                nys = set()
                for k in ys:
                    segl[k] = min(segl[k*2+1],segl[k*2+2])
                    nys.add((k-1)//2)
                ys = nys
            print(segl[0] if segl[0]!= mx else -1)
            ys = set()
            continue
        segl[x[3]+b_num-1] = mx if x[1] else x[2]
        ys.add((x[3]+b_num-2)//2)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

n,k = map(int,input().split())
p_ = list(map(int,input().split()))
for i in range(n):
    p_[i] = p_[i]/2 +0.5

cnt,res =0,[]
for i in range(n-k+1):
    cnt = sum(p_[:i+k]) - sum(p_[:i])
    res.append(cnt)

print(max(res))


### FIXED CODE ###

n,k = map(int,input().split())
p_ = list(map(int,input().split()))

def calc_ex(x):
    return  x/2 + 0.5
p_ = list(map(calc_ex,p_))

res = sum(p_[:k])
cnt = sum(p_[:k])
for i in range(1,n-k+1):
    cnt = cnt - p_[i-1] + p_[i+k-1]
    res = max(res,cnt)
print(res)
### BUGGY CODE ###

n,q = map(int,input().split())
s = str(input().split())

q_con = []
for i in range(q) :
    q_con.append(list(map(int,input().split())))



count = [0 for i in range(q)]
for i in range(q) :
    a = q_con[i][0] + 1
    b = q_con[i][1] + 1
    for j in range(a,b) :
        if s[j] == "A" and s[j+1] == "C" :
            count[i] += 1
        else : pass 

for i in count :
    print(i)


### FIXED CODE ###

N, Q = map(int,input().split())
S = list(input())

dp = [float("inf") for i in range(N)]
dp[0] = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C" :
        dp[i] = dp[i-1] + 1
    else :
        dp[i] = dp[i-1]
val = [[] for i in range(Q)]
for i in range(Q) :
    a,b = map(int,input().split())
    val[i] = [a-1,b-1]
for i in range(Q):
    print("{}".format(dp[val[i][1]]-dp[val[i][0]]))
### BUGGY CODE ###

S = input()
Q = int(input())
S = list(S)

for i in range(Q):
    k = input()
    if k == "1":
        S = list(reversed(S))
    else:
        if k[2] == "1":
            S = [k[4]] + S
        else:
            S = S + [k[4]]

print(*S, sep="")

### FIXED CODE ###

S = input()
Q = int(input())
 
A = ""
B = ""
count = 0

Que = []
ope = []

def rev(s):
    re = ""
    for i in range(len(s)):
        re = re + s[len(s) - 1 - i]
    return re
 
for i in range(Q):
    k = input()
    if k == "1":
        count += 1
        Que.append("1")
        ope.append("0")
    else:
        Que.append("2")
        ope.append([k[2],k[4]])
 
cou = 0
 
if count % 2 == 0:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = ope[i][1] + A
            else:
                B = B + ope[i][1]
else:
    for i in range(Q):
        if Que[i] == "1":
            cou += 1
        else:
            if (int(ope[i][0]) + cou) % 2 == 1:
                A = A + ope[i][1]
            else:
                B = ope[i][1] + B
 
if count % 2 == 0:
    S = A + S + B
else:
    S = rev(S)
    S = B + S + A
 
print(S)
### BUGGY CODE ###

def do(s, query, isReverse):
    if(query[0] == "1"):
        isReverse *= -1
    else:
        if(query[1] == "1"):
            if(isReverse == 1):
                s += query[2]
            else:
                s = query[2] + s
        else:
            if(isReverse == 1):
                s = query[2] + s
            else:
                s += query[2]
    return s, isReverse

s = input()
q = int(input())
isReverse = -1
for i in range(q):
    query = input().split()
    s, isReverse = do(s, query, isReverse)
if(isReverse == -1):
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s = input()
q = int(input())

ans = [" " for n in range(2*q + 1)]
ans[q] = s
frontIndex = q - 1
endIndex = q + 1
isReverse = -1

for i in range(q):
    query = input().split()
    if(query[0] == "1"):
        isReverse *= -1
    else:
        if(query[1] == "1"):
            if(isReverse == 1):
                ans[endIndex] = query[2]  
                endIndex += 1
            else:
                ans[frontIndex] = query[2]
                frontIndex -= 1
        else:
            if(isReverse == 1):
                ans[frontIndex] = query[2] 
                frontIndex -= 1
            else:
                ans[endIndex] = query[2]
                endIndex += 1
ans = "".join(ans).strip()
if(isReverse == -1):
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
def c(k):
    s = 0
    for i in range(N):
        if A[i] == k:
            s += 1
    return s
x = 0
for i in range(1,N+1):
    x += c(i)*(c(i)-1)//2
for i in range(N):
    print(x+1-c(A[i]))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
c = {}
for k in range(N):
    if c.get(A[k]) is None:
        c[A[k]] = 1
    else:
        c[A[k]] += 1

x = 0
for i in c:
    x += c[i]*(c[i]-1)//2
for i in range(N):
    print(x+1-c[A[i]])
### BUGGY CODE ###

import sys


def bisect(ls, value):
    l, r = -1, len(ls)
    while r-l>1:
        mid = (l+r)//2
        if ls[mid] <= value:
            l = mid
        else:
            r = mid
    return r


def main():
    n, K, L, R = map(int, sys.stdin.readline().split())
    a = tuple(map(int, sys.stdin.readline().split()))
    m = n // 2
    ls = [[] for _ in range(m + 1)]
    for i in range(1 << m):
        cnt = 0
        val = 0
        for j in range(m):
            if i >> j & 1:
                cnt += 1
                val += a[j]
        ls[cnt].append(val)
    for i in range(m + 1):
        ls[i].sort()
    ans = 0
    for i in range(1 << n - m):
        cnt = 0
        val = 0
        for j in range(n - m):
            if i >> j & 1:
                cnt += 1
                val += a[m + j]
        if K - m <= cnt <= K:
            ans += bisect(ls[K - cnt], R - val) - bisect(ls[K - cnt], L - val - 1)
    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
import bisect


def main():
    n, K, L, R = map(int, sys.stdin.readline().split())
    a = tuple(map(int, sys.stdin.readline().split()))
    m = (n-1)//2
    ls = [[] for _ in range(m+1)]
    for i in range(1 << m):
        cnt = 0
        val = 0
        for j in range(m):
            if i >> j & 1:
                cnt += 1
                val += a[j]
        ls[cnt].append(val)
    for i in range(m+1):
        ls[i].sort()
    ans = 0
    for i in range(1 << n-m):
        cnt = 0
        val = 0
        for j in range(n-m):
            if i >> j & 1:
                cnt += 1
                val += a[m+j]
        if K-m <= cnt <= K:
            ans += bisect.bisect_right(ls[K-cnt], R-val) - bisect.bisect_right(ls[K-cnt], L-val-1)
    print(ans)


if __name__ == '__main__':
    main()