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

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

# (d, x, 0 or 1) のリスト
events = []

for xi, [s, t, x] in enumerate(STX):
    # [lo, hi) に出発した人は x で止まる
    lo = s - x
    hi = t - x
    events.append((lo, x, 1))  # 追加
    events.append((hi, x, 0))  # 削除

events.sort()
ev = 0
closes = set()
for d in D:
    while ev < len(events) and events[ev][0] <= d:
        t, x, op = events[ev]
        if op == 1:
            closes.add(x)
        else:
            closes.remove(x)
        ev += 1
    if closes:
        print(min(closes))
    else:
        print(-1)


### FIXED CODE ###

import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

ans = [-1 for _ in range(Q)]
nexts = [-1 for _ in range(Q)]

for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = max(0, bisect.bisect_left(D, s - x))
    hi = min(len(D), bisect.bisect_left(D, t - x))

    p = lo
    while p < hi:
        if nexts[p] == -1:
            ans[p] = x
            nexts[p] = hi
            p += 1
        else:
            prev = p
            p = nexts[p]
            nexts[prev] = hi

for a in ans:
    print(int(a))
### BUGGY CODE ###

import numpy as np

ans = 0

N=int(input())
A=list(map(int,input().split()))
npA=np.array(A)

uniqA, counts = np.unique(npA, return_counts=True)
ans = np.sum(npA)

Q=int(input())

for q in range(Q):
	diff = 0
	B,C = map(int,input().split())

	if B in uniqA:
		srcIndex = np.where(uniqA == B)[0]
		srcCount = int(counts[srcIndex])
		diff = ( C - int(uniqA[srcIndex]) ) * srcCount
		counts[srcIndex] = 0
		if C in uniqA:
			counts[np.where(uniqA == C)[0]] += srcCount
		else:
			uniqA = np.append(uniqA, C)
			counts = np.append(counts, srcCount)

	ans += diff
	print(ans)



### FIXED CODE ###

import numpy as np

ans = 0

N=int(input())
A=list(map(int,input().split()))
npA=np.array(A)

counts = [0] * (10**5 + 1)

for a in npA:
	counts[a]+=1

ans = np.sum(npA)

Q=int(input())

for q in range(Q):
	diff = 0
	B,C = map(int,input().split())

	if 0 < counts[B]:
		diff = ( C - B ) * counts[B]
		counts[C] += counts[B]
		counts[B] = 0

	ans += diff
	print(ans)
### BUGGY CODE ###

import sys
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=list(map(int,sys.stdin))
danger.append(0)
if 1 in danger:
  arr[0]=0
  arr[1]=1
for i in range(n):
  if i+1 in danger:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))


### FIXED CODE ###

import sys
n,m = map(int,input().split())
a = list(map(int,sys.stdin))
a.append(0)
prev=0
cur=1
m=0
for i in range(1,n+1):
  if a[m]==i:
    prev,cur = cur,0
    m += 1
  else:
    prev,cur = cur,(cur+prev)%1000000007
print(cur)
### BUGGY CODE ###

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

ans = -1
for i in range(N-K+1):
    sum = 0
    for j in range(K):
        tmp = P[i+j]
        sum += tmp - 0.5*(tmp-1)
    
    ans = max(ans, sum)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
memo = sum(P[:K])
ans = memo

for i in range(K, N):
    memo = memo - P[i-K] + P[i]
    ans = max(ans, memo)

print(K-1+((ans-K+1) - 0.5*((ans-K+1)-1)))
### BUGGY CODE ###

from collections import deque
def f(n):
    arr = deque()
    tmp = n
    for i in range(2,n//1 + 1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            arr.append(i)
    if tmp != 1:
        arr.append(tmp)
    if arr == []:
        arr.append(n)
    return arr

A, B = map(int, input().split())
arrA = f(A)
arrB = f(B)
if len(arrA )> len(arrB):
    arrA, arrB = arrB, arrA

cnt = 1
for i in range(len(arrA)):
    if arrA[i] in arrB:
        cnt += 1
print(cnt)

### FIXED CODE ###

from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    i = 2
    while i <= n**0.5 + 1:
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
        i += 1
    if tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)
### BUGGY CODE ###

from collections import deque
n,m = [int(i) for i in input().split()]
F = [{} for i in range(n)]
for _ in range(m):
    i,j = [int(i) for i in input().split()]
    F[i][j] = 1
    F[j][i] = 1
q = int(input())
for i in range(q):
    DP = [0]*n
    d = deque()
    s,t = [int(i) for i in input().split()]
    d.append(s)
    flag = False
    while(len(d)>0):
        tmp = d.pop()
        DP[tmp] = 1
        if tmp == t:
            flag = True
            break
        else:
            for i in F[tmp]:
                if not DP[i]:
                    d.append(i)
    if flag:
        print("yes")
    else:
        print("no")


### FIXED CODE ###

from collections import deque
n,m = [int(i) for i in input().split()]
F = [{} for i in range(n)]
for _ in range(m):
    i,j = [int(i) for i in input().split()]
    F[i][j] = 1
    F[j][i] = 1
q = int(input())
DP = [0 for i in range(n)]
c = 1
d = deque()
for i in range(n):
    if DP[i]:
        continue
    else:
        d.append(i)
    while(len(d)>0):
        tmp = d.pop()
        DP[tmp] = c
        for i in F[tmp]:
            if not DP[i]:
                d.append(i)
    c+=1

for i in range(q):
    s,t = [int(i) for i in input().split()]
    if DP[s] == DP[t]:
        print("yes")
    else:
        print("no")
### BUGGY CODE ###

n, m = map(int, input().split())
a, b = map(int, input().split())
d = list(range(a, b+1))
for i in range(m-1):
    a, b = map(int, input().split())
    src_set = set(d)
    tag_set = set(list(range(a, b+1)))
    d = list(src_set & tag_set)
print(len(d))

### FIXED CODE ###

n,m=map(int,input().split())
max_ = 0
min_ = n+1
for i in range(m):
  a,b=map(int, input().split())
  max_ = max(max_, a)
  min_ = min(min_, b)
#print(max_, min_)
if(min_ < max_):print(0)
else:print(min_-max_+1)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split(" ")))
for i in range(1,n+1):
  print(l.count(i))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split(" ")))
s=[0]*n
for i in range(len(l)):
    s[l.pop()-1]+=1
    
for i in range(n):
    print(s[i])
### BUGGY CODE ###

s = input()
q = int(input())
rev = 0

for i in range(q):
    a = input()
    
    if a[0] == '1':
        rev += 1
    else:
        if (int(a[2]) + rev) % 2 == 1:
            s = a[4] + s
        else:
            s += a[4]
    
if rev%2 == 0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s = input()
q = int(input())
rev = 0
mae = []
usiro = []

for i in range(q):
    a = input()
    
    if a[0] == '1':
        rev += 1
    else:
        if (int(a[2]) + rev) % 2 == 1:
            mae.append(a[4])
        else:
            usiro.append(a[4])
            
mae = mae[::-1]
mae2 = "".join(mae)
usiro2 = "".join(usiro)
if rev%2 == 0:
    print(mae2 + s + usiro2)
else:
    ans = mae2 + s + usiro2
    print(ans[::-1])
### BUGGY CODE ###

import numpy as np
h,w,a,b = map(int,input().split())
x = np.ones((w), int)
x[a:] = -1
y = np.ones(h, int)
y[b:] = -1
#x = np.array([1]*a + [-1]*(w-a), int)
#y = np.array([1]*b + [-1]*(h-b), int).reshape(-1,1)
m = x * y.reshape(-1,1)
#print(m)
m *= m > 0
#print(m)
for row in m:
  print(*row, sep='')

### FIXED CODE ###

h,w,a,b = map(int,input().split())
x = '1'*a + '0'*(w-a)
xinv = '0'*a + '1'*(w-a)
for i in range(h):
  row = x if i < b else xinv
  print(row)
### BUGGY CODE ###

import copy
s=input().split()
num=[int(i) for i in s[:3]]
K=int(s[3])
num_=[0,0,0]
for i in range(K):
	for j in range(3):
		num_[j]=num[(j+1)%3]+num[(j+2)%3]
	num=copy.deepcopy(num_)
	if i%10000==0:
		if abs(num[0]-num[1])>10**18:
			print("Unfair")
			break
else:
	print(num[0]-num[1])


### FIXED CODE ###

s=input().split()
ans=int(s[0])-int(s[1])
if abs(ans)>10**18:
  print("Unfair")
elif int(s[3])%2==0:
  print(int(s[0])-int(s[1]))
else:
  print(-1*(int(s[0])-int(s[1])))
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
s,e = 1,k+1
temp = sum(a[:k])
for i in range(n-k):
    score = sum(a[s:e])
    print("Yes" if score>temp else "No")
    temp = score
    s+=1
    e+=1

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
temp,i = sum(a[:k]),k
for _ in range(n-k):
    score = temp+a[i]-a[i-k]
    print("Yes" if score>temp else "No")
    temp = score
    i+=1
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
cost = [[0] * (N + 2) for i in range(N + 2)]
D = []
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xs, ys, 0))
D.append((xt, yt, 0))

for i in range(len(D)):
    for j in range(i + 1, len(D)):
        k = max(0, ((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) ** 0.5 - (D[i][2] + D[j][2]))
        cost[i][j] = k
        cost[j][i] = k
INF = float('inf')
d = [INF] * (N + 2)
d[N] = 0
que = [(N, 0.0)]
while que:
    v, dist = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[N + 1])
        exit()
    for w in range(N + 2):
        if d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (w, d[w]))


### FIXED CODE ###

import sys
from math import sqrt
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
INF = float('inf')
cost = [[INF] * (N + 2) for i in range(N + 2)]
D = [(xs, ys, 0)]
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xt, yt, 0))

for i in range(N + 2):
    for j in range(i + 1, N + 2):
        k = max(0, sqrt((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) - D[i][2] - D[j][2])
        cost[i][j] = k
        cost[j][i] = k

visit = [0] * (N + 2)
visit[0] = 1
d = [INF] * (N + 2)
d[0] = 0
que = [(0, 0)]
while que:
    dist, v = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[v])
        exit()
    visit[v] = 1
    for w in range(N + 2):
        if visit[w] == 0 and w != v and d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (d[w], w))
### BUGGY CODE ###

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

DIV = 10**9+7

def comb(l, r):
    if l == 0:
        return 1
    val = 1
    for i in range(r, r-l, -1):
        val *= i
    for i in range(l, 0, -1):
        val //= i
    return val

def calc_rec_num(N, M, xi, xj, yi, yj):
    cnt = 1
    cnt *= N - yi
    cnt *= M - yj
    # rotate
    if xi != yi and xj != yj:
        cnt *= 2
    return cnt


p = comb(K-2, N*M-2)
#print(K-2, N*M-2, p)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        ans += d * calc_rec_num(N, M, 0, 0, i, j) * p
        if ans > DIV:
            ans %= DIV
        #print(ans)

print(ans)


### FIXED CODE ###

from math import factorial
N, M, K = map(int, input().split())

MOD = 10**9+7

fact = [1] * (N*M+1)
for i in range(2, N*M+1):
    fact[i] = fact[i-1] * i % MOD

def comb(n, r):
    r = n-r if n-r < r else r
    return fact[n] * pow(fact[r], MOD-2, MOD) * pow(fact[n-r], MOD-2, MOD) % MOD

p = comb(N*M-2, K-2)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt % MOD
ans = ans * p % MOD

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

A,B,C,N=map(int, input().split())
count=0
for x in range(N+1):
    for y in range(N+1):
        for z in range(N+1):
            if N==x*A+y*B+z*C:
                count+=1
                
print(count)

### FIXED CODE ###

A,B,C,N=map(int, input().split())
count=0
for x in range(N+1):
  for y in range(N-x*A+1):
    b=(N-x*A-y*B)
    if b>=0 and b%C==0:
      count+=1
                
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
remain = [0 for i in range(max(a) + 1)]
for ai in a:
    remain[ai] += 1
res = 0
for i in range(1, max(a) + 1):
    if remain[i] == 1:
        res += 1
    if remain[i]:
        for j in range(i * 2, max(a) + 1, i):
            remain[j] = 0
print(res)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
remain = [0 for i in range(max(a) + 1)]
for ai in a:
    remain[ai] += 1
res = 0
max_a = max(a)
for i in range(1, max_a + 1):
    if remain[i] == 1:
        res += 1
    if remain[i]:
        for j in range(i * 2, max_a + 1, i):
            remain[j] = 0
print(res)
### BUGGY CODE ###

from collections import deque

S = deque(input())
Q = int(input())
query = [input().split() for _ in range(Q)]
for q in query:
    if q[0] == '1':
        S.reverse()
    else:
        if q[1] == '1':
            S.appendleft(q[2])
        else:
            S.append(q[2])

print(''.join(S))


### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
query = [input().split() for _ in range(Q)]
reverse = False
for q in query:
    if q[0] == '1':
        reverse = not reverse
    else:
        if q[1] == '1':
            if not reverse:
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if not reverse:
                S.append(q[2])
            else:
                S.appendleft(q[2])
if reverse:
    S.reverse()
print(''.join(S))
### BUGGY CODE ###

import math
#! //Users/daigofujiwara/anaconda3/bin python3

#h行で列和がyかy+1であるかどうかとサンプルを出力

input1=input()

input2=input()

x,y=input1.split(" ")
N,M=int(x),int(y)

A=input2.split(" ")

A=[int(a) for a in A ]

B=[]
for a in A:
    B.append(a//2)

gmp=None

for i in range(1,M+1):
    T=1
    for b in B:
        if not ((i//b)%2==1 and i%b==0):
            T=0
    if T==1:
        gmp=i
        break

if gmp is None:
    print(0)
else:
    print(int(math.floor(M/gmp+1.0)/2.0))




### FIXED CODE ###

import math
from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
#! //Users/daigofujiwara/anaconda3/bin python3

#h行で列和がyかy+1であるかどうかとサンプルを出力

input1=input()

input2=input()

x,y=input1.split(" ")
N,M=int(x),int(y)

A=input2.split(" ")

A=[int(a) for a in A ]

B=[]
for a in A:
    B.append(a//2)


Mb=lcm_list(B)
gmp=None


T=1
for b in B:
    if not (Mb//b)%2==1:
        T=0
if T==1:
    gmp=Mb




if gmp is None:
    print(0)
else:
    print(int(math.floor(M/gmp+1.0)/2.0))
### BUGGY CODE ###

import numpy as np

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

ans = ""

list(enumerate(Ai))
Aians = sorted(enumerate(Ai), key = lambda x: x[-1])

for ansNum in Aians:
    ans = ans + str(ansNum[0] + 1) + " "

print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
Ai = list(map(int, input().split()))

#Aians = np.argsort(Ai) + 1
print(' '.join(map(str, np.argsort(Ai) + 1)))
### BUGGY CODE ###

from collections import deque
n=int(input())
al=[deque(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].popleft()
                    tn[t]-=1
                    ts.add(t)
                    al[j].popleft()
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print(i+1)
        exit()
    if flg:
        print(-1)
        exit()

### FIXED CODE ###

import time
n=int(input())
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
start=time.time()
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print(i+1)
        exit()
    if flg:
        print(-1)
        exit()
    now=time.time()
    if (now-start)>1.6:
        print(m)
        exit()
### BUGGY CODE ###

N = int(input())
T = [ int(input()) for i in range(N) ]

m = max(T)
mm = m
flg = False
while True:
    for i in T:
        if m % i != 0:
            flg =True

    if flg == False:
        break
    flg = False
    m += mm

print(m)


### FIXED CODE ###

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a


def lcm(a,b):
    return (a*b) // gcd(a,b)


N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

t = T[0]
for i in range(N - 1):
    t = lcm(t,T[i+1])
print(t)
### BUGGY CODE ###

n=int(input())
s=list(map(ord,list(input())))
for i in range(n):s[i]-=97

from random import randint
roli_mod=1370757747362922367
roli_r=randint(2,roli_mod-2)
roli=[0]
roli_rr=1
for i in range(n):
  roli.append((roli[-1]+roli_rr*s[i])%roli_mod)
  roli_rr*=roli_r
  roli_rr%=roli_mod
def roli_hash(i,j):return ((roli[j+1]-roli[i]+roli_mod)%roli_mod)*pow(roli_r,roli_mod-1-i,roli_mod)%roli_mod
def roli_check(i1,j1,i2,j2):return roli_hash(i1,j1)==roli_hash(i2,j2)

ans=0
for i in range(1,n+1):
  d={}
  for j in range(n-i+1):
    h=roli_hash(j,j+i-1)
    if h in d:
      if j-d[h]>=i:
        ans=i
        break
    else:d[h]=j
print(ans)

### FIXED CODE ###

n=int(input())
s=list(map(ord,list(input())))
dp=[n*[0]for _ in range(n)]
for i in range(n):
  if s[i]==s[0]:
    dp[i][0]=dp[0][i]=1
for i in range(1,n):
  for j in range(1,n):
    if s[i]==s[j]:
      dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if i<j-dp[i][j]+1:ans=max(ans,dp[i][j])
print(ans)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

S = input()

def solve(S):
    L = len(S)
    if L == 0 or int(S) == 0:
        return 1

    tmp = 0
    tmpS = ''
    for i in range(L):
        if S[i] == '1':
            tmpS = S[i+1:]
            tmp =  L - 1 - i
            break


    return (2*solve(tmpS) + solve_bin(tmp))%mod

def solve_bin(b):
    return pow(3,b,mod)

print(solve(S)%mod)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7

def solve(l):
    tmp = 0
    tmpS = ''
    for i in range(l,L):
        if S[i] == '1':
            return (2*solve(i+1) + pow(3,L-1-i,mod))%mod
    else:
        return 1

S = input()
L = len(S)
print(solve(0)%mod)
### BUGGY CODE ###

N = int(input())
Ss = []
c = []
for i in range(N):
  s = input()
  if s in Ss:
    c[Ss.index(s)] += 1
  else:
    Ss.append(s)
    c.append(1)
mostPoll = max(c)
winners = []
for i in range(len(c)):
  if c[i] == mostPoll:
    winners.append(Ss[i])
winners.sort()
for s in winners:
  print(s)

### FIXED CODE ###

n = int(input())
d = {}
for _ in range(n) :
    s = input()
    if s in d :
        d[s] += 1
    else :
        d[s] = 1

mx = max(d.values())
for s in sorted(k for k in d if d[k] == mx) :
    print(s)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


n = int(input())
a = list(map(int, input().split()))
cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

ret = 0

for val in a:
    is_ok = True
    if val in dup:
        continue
    divs = make_divisors(val)
    for item in divs:
        if item == val:
            continue
        elif item in cand:
            is_ok = False
            break
    if is_ok:
        ret += 1

print(ret)


### FIXED CODE ###

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

cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

dame_set = set()

a.sort()
ret = 0

for val in a:
    if val in dup:
        if val in dame_set:
            continue
        else:
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                tmp = i * val
                if tmp in cand:
                    dame_set.add(tmp)
                i += 1
    else:
        if val in dame_set:
            continue
        else:
            ret += 1
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                tmp = i * val
                if tmp in cand:
                    dame_set.add(tmp)
                i += 1

print(ret)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

total = sum(A)
# dp[i][j][k] := i枚目までからj枚取って、合計をkにする通り数
dp = list3d(N+1, N+1, total+1, 0)
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(N+1):
        for k in range(total+1):
            dp[i+1][j][k] += dp[i][j][k]
            if j+1 <= N and k+a <= total:
                dp[i+1][j+1][k+a] += dp[i][j][k]
ans = 0
for j in range(1, N+1):
    if j*K <= total:
        # 1枚以上取った時の、平均がKになる所 → j枚取って合計がj*Kの所 を合計する
        ans += dp[N][j][j*K]
print(ans)


### FIXED CODE ###

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

""" 3次元DP """

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

# i(=xNリストからどこまでを選べる範囲とするか)からj(=0～N)枚選んで、選んだ値の合計をkにするような選び方の総数
dp = [[[0] * (N*X+1) for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 1

ans = 0
for i in range(1,N+1):
    for j in range(N+1):
        for k in range(N*X+1):
            # 求めたい合計(k)が、この周回で増えた選択肢(xN[i-1])より小さい場合、
            # 選び方の総数は増える見込みがないので前回の値をそのまま使用
            if k < xN[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            # 合計kが大きければ、増やせるかもしれないので、選んだ数と合計を減らしたところを見に行く
            # 選べる数j=0は論外だし、添え字[j-1]に良くないので条件で除外する
            elif k >= xN[i-1] and j > 0:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-xN[i-1]]
            # 選んだ数と合計から判断して、平均が条件に合うものなら答えに足す
            if i == N and j > 0 and k == j*A:
                ans += dp[i][j][k]

# ans = 0
# for k in range(1,N+1):
#     ans += dp[N][k][k*A]
        
print(ans)