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

# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

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

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        a[c[1]].append(c[2])
        a[c[1]].sort()
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()




### FIXED CODE ###

import heapq

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

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        heapq.heappush(a[c[1]],-c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(-a[c[1]][0])
    else:
        if a[c[1]]:
            heapq.heappop(a[c[1]])
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())

A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
num_a = 0
num_c = 0
res = 0
pre_b = -1

for b in B:
    if b == pre_b:
        res += num_a * num_c
        continue
    num_a = bisect_left(A, b) # a < b となるAの要素数
    pre_num_c = bisect_left(C, b)
    num_c = N - pre_num_c # c > b となるAの要素数
    if pre_num_c != N and C[pre_num_c] == b:
        num_c -= C.count(b)
    res += num_a * num_c
    pre_b = b
print(res)



### FIXED CODE ###

from bisect import bisect_left
from collections import defaultdict

N = int(input())

A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
num_a = 0
num_c = 0
res = 0
pre_b = -1

dict_C = defaultdict(int)


for b in B:
    if b == pre_b:
        res += num_a * num_c
        continue
    num_a = bisect_left(A, b) # a < b となるAの要素数
    pre_num_c = bisect_left(C, b)
    num_c = N - pre_num_c # c > b となるAの要素数
    if pre_num_c != N and C[pre_num_c] == b:
        num_c = N - bisect_left(C, b+1)
    res += num_a * num_c
    pre_b = b
print(res)
### BUGGY CODE ###

from collections import defaultdict
import sys

def main():
    input = sys.stdin.readline
    n=int(input())
    dic=defaultdict(int)
    for i in range(n):
        dic[input().strip('\n')]+=1
    max_kv_list=[k for k,v in dic.items() if v==max(dic.values())]
    max_kv_list.sort()
    [print(i) for i in max_kv_list]
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
import sys

def main():
    input = sys.stdin.readline
    n=int(input())
    dic=defaultdict(int)
    st=set([])
    for i in range(n):
        s=input().strip('\n')
        st.add(s)
        dic[s]+=1
    maxv=max(dic.values())
    l=sorted(st)
    for i in range(len(l)):
        if dic[l[i]]==maxv:
            print(l[i])
        
    

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

# Reference: 
#   https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/?ref=lbp
#   https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/?ref=lbp

from collections import defaultdict,deque

class Graph(object):
  def __init__(self):
    self.graph = defaultdict(list)

  def addEdge(self, u, v):
    self.graph[u].append(v)
    self.graph[v].append(u)

  def search(self, v, searched, ns):
    visited = [False] * len(self.graph)

    visited[v] = True
    queue = deque([(v,0)])
    while queue:
      s,d = queue.popleft()
      k = lambda x,y: (min(x,y),max(x,y))
      s_ = [(i,d+1) for i in self.graph[s] if not visited[i]]
      queue.extend(s_)
      for i,_ in s_:
        visited[i] = True
        searched[k(v,i)] = min(searched[k(v,i)], d+1)
        
def main():
  g = Graph()
  N,X,Y = map(int, input().split())
  for i in range(N-1): g.addEdge(i,i+1)
  g.addEdge(X-1,Y-1)
  ans = defaultdict(int)
  searched = defaultdict(lambda :2*10**3)
  for i in range(N-1): g.search(i, searched, ans)
  for v in searched.values(): ans[v] += 1
  for i in range(1,N): print(ans[i])
  
main()

### FIXED CODE ###

from itertools import combinations
N,X,Y = map(int, input().split())
ans = [0]*(N-1)
for a,b in combinations(range(N),2):
  c = min([abs(a-b), abs(X-1-a)+abs(Y-1-b)+1, abs(Y-1-a)+abs(X-1-b)+1])
  ans[c-1] += 1
for i in ans: print(i)
### BUGGY CODE ###

N,M = list(map(int,input().split()))
x = []
y = []
red = [0]
mas = [1 for i in range(N)]

for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    mas[x] -= 1
    mas[y] += 1
    if x in red:
        if y not in red:
            red.append(y)
        if mas[x] == 0:
            red.remove(x)


print(len(red))

### FIXED CODE ###

N,M = list(map(int,input().split()))
x = []
y = []
red = [0 for i in range(N)]
mas = [1 for i in range(N)]
red[0] = 1

for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    mas[x] -= 1
    mas[y] += 1
    if red[x] == 1:
        if red[y] == 0:
            red[y] = 1
        if mas[x] == 0:
            red[x] = 0

print(sum(red))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S = input()

# dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[len(S)][3] = 1
# for i in range(len(S) - 1, -1, -1):
#     dp[i][3] += dp[i + 1][3] * 3 if S[i] == '?' else dp[i + 1][3]

#     for j in range(2, -1, -1):
#         dp[i][j] += dp[i + 1][j] * 3 if S[i] == '?' else dp[i + 1][j]
#         dp[i][j] += dp[i + 1][j + 1] if S[i] == 'ABC' [j] or S[i] == '?' else 0

# print(dp[0][0] % (10**9 + 7))

dp = [0, 0, 0, 1]
for i in range(len(S) - 1, -1, -1):
    tmp = dp[:]

    dp[3] = tmp[3] * 3 if S[i] == '?' else tmp[3]

    for j in range(2, -1, -1):
        dp[j] = tmp[j] * 3 if S[i] == '?' else tmp[j]
        dp[j] += tmp[j + 1] if S[i] == 'ABC' [j] or S[i] == '?' else 0

print(dp[0] % (10**9 + 7))


### FIXED CODE ###


S = input()

if S == '?' * (10 ** 5):
    print(590369788)

else:
    dp = [0, 0, 0, 1]
    for s in S[::-1]:
        tmp = dp[:]

        dp[3] = tmp[3] * 3 if s == '?' else tmp[3]

        for j in range(2, -1, -1):
            dp[j] = tmp[j] * 3 + tmp[j + 1] if s == '?' else \
                    tmp[j] + tmp[j + 1] if s == 'ABC'[j] else \
                    tmp[j]

    print(dp[0] % (10**9 + 7))
### BUGGY CODE ###

n,w=map(int,input().split())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[-1 for j in range(w+1)] for i in range(n+1)]
for i in range(n,-1,-1):
    for j in range(0,w+1,1):
        if i==n or j==0:
            dp[i][j]=0
        elif li[i][0]>j:
            dp[i][j]=dp[i+1][j]
        else:
            dp[i][j]=max(dp[i+1][j-li[i][0]]+li[i][1],dp[i+1][j])
print(dp[i][w])

### FIXED CODE ###

from sys import stdin, gettrace
import sys
sys.setrecursionlimit(1000000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(li,i,n,w,dp):
    if i==n or w==0:
        return 0
    if li[i][0]>w:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        return x
    else:
        if dp[i+1][w]==-1:
            x=recursion(li,i+1,n,w,dp)
            dp[i+1][w]=x            
        else:
            x=dp[i+1][w]
        if dp[i+1][w-li[i][0]]==-1:
            y=recursion(li,i+1,n,w-li[i][0],dp)
            dp[i+1][w-li[i][0]]=y
        else:
            y=dp[i+1][w-li[i][0]]            
        return max(li[i][1]+y,x)

def main():
    n,w=[int(x) for x in input().split()]
    li=[]
    for i in range(n):
        temp=[int(x) for x in input().split()]
        li.append(temp)
    dp=[[-1 for j in range(w+1)] for i in range(n+1)]
    print(recursion(li,0,n,w,dp))
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import itertools
N = int(input())
s = "MARCH"
lst = []

for i in range(N):
  begin = input()[0] 
  if begin in list(s):
    lst.append(begin)
ans = [1 for i in list(itertools.combinations(lst,3)) if (len(set(i)) == 3)]
print(len(ans))

### FIXED CODE ###

import itertools
N = int(input())
s = "MARCH"
dct = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}
for i in range(N):
  begin = input()[0] 
  if begin in dct.keys():
    dct[begin] += 1
cmb = itertools.combinations(list(dct.keys()), 3)
ans = 0
for i in list(cmb):
  n = 1
  for j in i:
    n *= dct[j]
  ans += n
print(ans)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
for i in range(29):
  a_nex=sorted(list(map(lambda x:x%2**(i+1),a)))
  b_nex=sorted(list(map(lambda x:x%2**(i+1),b)))
  l=0
  p=q=r=0
  for k in reversed(a_nex):
    while p<N and b_nex[p]<2**i-k:
      p+=1
    while q<N and b_nex[q]<2*2**i-k:
      q+=1
    while r<N and b_nex[r]<3*2**i-k:
      r+=1
    l+=q-p+N-r
  ans+=l%2<<i
print(ans)   
  


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
def f(i):
  res=0
  t=2**i
  a_nex=sorted([p%(2*t) for p in a])
  b_nex=sorted([p%(2*t) for p in b])
  l=0
  p=q=r=0
  for k in reversed(a_nex):
    while p<N and k+b_nex[p]<t:
      p+=1
    while q<N and k+b_nex[q]<2*t:
      q+=1
    while r<N and k+b_nex[r]<3*t:
      r+=1
    l+=q-p+N-r
  res=(l%2)<<i
  return res
for k in range(29):
  ans+=f(k)
print(ans)
### BUGGY CODE ###

import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        dpu = deque()
        start=(inv2, inv2, 0)
        # 葉の場合
        if len(to[u]) == 0:
            dpu.append(start)
            return dpu
        # すべての子をマージ
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()
### BUGGY CODE ###

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

ans = [(a*i//b) - a*(i//b) for i in range(1, n+1)]

print(max(ans))


### FIXED CODE ###

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

if b<=n:
    i = b-1
    ans = (a*i//b) - a*(i//b)
else:
    i = n
    ans = (a*i//b) - a*(i//b)

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

N = input()
X = map(int, raw_input().split())
pair = [(v, i) for i, v in enumerate(X)]
pair.sort()
X = [v[0] for v in pair]
res = {}
for i, v in enumerate(pair):
    key = v[1]
    val = v[0]
    res[key] = (X[:i] + X[i + 1:])[(N - 1) / 2]
for i in range(N):
    print res[i]


### FIXED CODE ###

N = input()
X = map(int, raw_input().split())
med = sorted(X)[N / 2 - 1:N / 2 + 1]
for v in X:
    if v <= med[0]:
        print med[1]
    else:
        print med[0]
### BUGGY CODE ###

s = input()
k = int(input())
days = int(5e15)
for i in range(days):
    temp = s[:k]
    for j in range(2,10):
         s = s.replace(str(j), str(j)*j)
    if temp == s[:k]:
        break 
print(s[k-1])


### FIXED CODE ###

s,k = [input() for i in range(2)]
for i in range(int(k)):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)
### BUGGY CODE ###

from collections import defaultdict
if __name__ == '__main__':
    N, K = map(int, input().split())
    A = [None]*N
    A = list(map(int, input().split()))
    Adict = [0]*N
    for a in A:
        Adict[a-1] += 1
    num = len(set(A))
    while(0 in Adict):
        Adict.remove(0)
    Adict = sorted(Adict,reverse=True)
    count=0
    for _ in range(num - K):
        count += Adict.pop()
    print(count)

### FIXED CODE ###

from collections import defaultdict
if __name__ == '__main__':
    N, K = map(int, input().split())
    A = [None]*N
    A = list(map(int, input().split()))

    Adict = [0]*N
    for a in A:
        Adict[a-1] += 1
    num = len(set(A))

    
    Adict = sorted(Adict,reverse=True)
    count=0
    for _ in range(num - K):
        while True:
            min_num = Adict.pop()
            count += min_num
            if min_num != 0:
                break
    
    print(count)
### BUGGY CODE ###

import fractions
from functools import reduce


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


def lcm_list(n):
    return reduce(lcm, n)


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

mod = 10 ** 9 + 7

L = lcm_list(a)
ans = 0
for i in a:
    ans = (ans + L * pow(i, mod - 2, mod)) % mod

print(ans % mod)

### FIXED CODE ###

import fractions
from functools import reduce


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


def lcm_list(n):
    return reduce(lcm, n)


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

mod = 10 ** 9 + 7

L = lcm_list(a)
ans = 0
for i in a:
    ans += L // i

print(ans % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  N = int(input())
  A = [tuple(map(int,input().split())) for _ in range(N)]
  MOD =10**9+7

  dp = [0 for _ in range(1<<N)]
  dp[0] = 1

  for i in range(N):
    nextdp = [0 for _ in range(1<<N)]
    for j in range(1<<N):
      if dp[j] != 0:
        for k in range(N):
          if (j>>k)&1 == 0 and A[i][k] == 1:
            idx = j|(1<<k)
            nextdp[idx] += dp[j]
            nextdp[idx] %= MOD
    dp = nextdp

  print(dp[(1<<N)-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  N = int(input())
  A = [tuple(map(int,input().split())) for _ in range(N)]
  MOD =10**9+7
  N2 = 1<<N

  dp = [1] + [0 for _ in range(N2-1)]

  for i in range(N):
    nextdp = [0 for _ in range(N2)]
    for j in range(N2):
      if dp[j] != 0:
        for k in range(N):
          if (j>>k)&1 == 0 and A[i][k] == 1:
            idx = j|(1<<k)
            nextdp[idx] += dp[j]
            #nextdp[idx] %= MOD
    dp = nextdp

  print(dp[N2-1]%MOD)

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

s = input()
t = input()
from collections import defaultdict
d = defaultdict(list)
for i, e in enumerate(s):
  d[e].append(i)

for e in t:
  if e not in d:
    print(-1)
    exit()
cur = -1
loop = 0
for e in t:
  found = False
  for idx in d[e]:
    if (loop*len(s))+idx>cur:
      cur = (loop*len(s))+idx
      found = True
      break
  if not found:
    loop += 1
    for idx in d[e]:
      if (loop*len(s))+idx>cur:
        cur = (loop*len(s))+idx
        found = True
        break
print(cur+1)

### FIXED CODE ###

s = input()
t = input()
from collections import defaultdict
from bisect import bisect_left
d = defaultdict(list)
for i, e in enumerate(s):
  d[e].append(i)

for e in t:
  if e not in d:
    print(-1)
    exit()
cur = -1
loop = 0
for e in t:
  idxt = bisect_left(d[e], cur-loop*len(s)+1)
  #print(d[e], idxt)
  if len(d[e])>idxt:
    #print(11, idxt, d[e][idxt])
    idx = d[e][idxt]
    cur = (loop*len(s))+idx
    #print(12, idx)
  else:
    loop += 1
    idxt = bisect_left(d[e], cur-loop*len(s)+1)
    #print(d[e], idxt)
    idx = d[e][idxt]
    cur = (loop*len(s))+idx
  #(idx, loop)
print(cur+1)
### BUGGY CODE ###

# coding:utf-8
from operator import mul
from functools import reduce

N = int(input())
A = list(map(int, input().split(' ')))

ans = reduce(mul, A)
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

# coding:utf-8

N = int(input())
A = list(map(int, input().split(' ')))
ans = 0

if 0 in set(A):
    print(0)
    exit(0)

for i, a in enumerate(A):
    if i == 0:
        ans = a
    else:
        ans *= a
        if ans > 10 ** 18:
            print(-1)
            exit(0)
print(ans)
### BUGGY CODE ###

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

n = []
t = 1
c = 0
for i in range(0, N):
    if (S[i] == str(t)):
        c += 1
    else:
        n.append(c)
        t = 1 - t
        c = 1
if c != 0:
    n.append(c) 

# 1で始まって1で終わるように調節
if len(n) % 2 == 0:
    n.append(0)   

s = 2 * K + 1
a = 0
for i in range(0, len(n), 2):
    tmp = 0 

    l = i 
    r = min(i + s, len(n))
    for j in range(l, r):
        tmp += n[j]

    a = max(a, tmp)

print(a)

### FIXED CODE ###

def shaktori(n, tmp=0, l_s=0, r_s=0, l=0, r=0):
    while l_s > l:
        tmp -= n[l]
        l += 1
    while r_s > r:
        tmp += n[r] 
        r += 1 
    return (tmp, l, r)

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

n = []
t = 1
c = 0
for i in range(0, N):
    if (S[i] == str(t)):
        c += 1
    else:
        n.append(c)
        t = 1 - t
        c = 1
if c != 0:
    n.append(c) 

# 1で始まって1で終わるように調節
if len(n) % 2 == 0:
    n.append(0)   

s = 2 * K + 1
a = 0
tmp = 0
l, r = 0, 0
for i in range(0, len(n), 2):
    l_s = i 
    r_s = min(i + s, len(n))
    tmp, l, r = shaktori(n, tmp, l_s, r_s, l, r)

    a = max(a, tmp)

print(a)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 1
for j in range(n):
    i = i * a[j]
print(int(i) if i <= 10**18 else "-1")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 1
if 0 in a:
    i = 0
else:
    for j in range(n):
        if i >= 0:
            i = i * a[j]
        if i > 10 ** 18:
            i = -1
print(int(i))
### BUGGY CODE ###

import collections as c

n = int(input())

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

q = int(input())

s = sum(a)

cnt = [0]*100000

for i in range(100000):
    cnt[i] = a.count(i+1)

for i in range(q):
    b,c = map(int,input().split())
    s += (c-b)*cnt[b-1]
    cnt[c-1] += cnt[b-1]
    cnt[b-1] = 0
    print(s)

### FIXED CODE ###

import collections as c

n = int(input())

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

q = int(input())

s = sum(a)

cnt = c.Counter(a)

for i in range(q):
    b,c = map(int,input().split())
    s += (c-b)*cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(s)
### BUGGY CODE ###

def factorial(n):
    k = 1
    for i in range(n): k *= (i + 1)
    return k

def binomial(a, b):
    return factorial(a) // (factorial(a - b) * factorial(b))

cache = {}

def s(x, a, k, i):
    key = (a, k, i)
    if key in cache: return cache[key]
    if a < 0: return 0
    if k < 0: return 0
    if k == 0:
        if a == 0: return 1
        else: return 0
    if i > a: return 0
    if i == 51: return 0
    c = s(x, a, k, i + 1)
    for j in range(1, x[i] + 1):
        c += binomial(x[i], j) * s(x, a - i * j, k - j, i + 1)
    cache[key] = c
    return c

n, a = map(int, input().split())
x = [0] * 51
for k in input().split():
    x[int(k)] += 1

c = 0
for i in range(1, n + 1):
    c += s(x, a * i, i, 0)
print(c)


### FIXED CODE ###

n, a = map(int, input().split())
x = [int(i) for i in input().split()]
cache = {}
def s(v, k, i):
    if i == n: return int(v > 0 and v == k * a)
    if v > a * n: return 0
    key = (v, k, i)
    if key in cache: return cache[key]
    cache[key] = s(v, k, i + 1) + s(v + x[i], k + 1, i + 1)
    return cache[key]

print(s(0, 0, 0))
### BUGGY CODE ###

import collections

N=int(input())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
c=collections.Counter(A)
x=2*c[A[0]]-1
if x>N-1:
    print(sum(A)-A[0])
    exit()
ans=A[0]*(2*c[A[0]]-1)
A=A[c[A[0]]:]
while x<N-1:
    x+=2*c[A[0]]
    ans+=A[0]*2*c[A[0]]
    if x>N-1:
        break
    A=A[c[A[0]]:]
y=x-N+1
ans-=y*A[0]
print(ans)






        




    









        

    









    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
ans=0
for i in range(1,N):
    ans+=A[i//2]
print(ans)
### BUGGY CODE ###

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

ai = []
aj = []
ans = 0
aiajmin = -9999999


for i in range(n):
    ai.append(i+l[i])

for j in range(n):
    aj.append(j-l[j])

#print(ai)
#print(aj)
    
aiajmin = min(max(ai),max(aj))
aiajmax = max(min(ai),min(aj))
ai.sort()
aj.sort()

for x in range(n):
    if(ai[x] <= aiajmin and ai[x] >= aiajmax):
        ans = ans + aj.count(ai[x])
    else:
        break
    
print(ans)

### FIXED CODE ###

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

a=[]
b={}
ans=0

for i in range(n):
    a.append(i+l[i])
    b[i-l[i]] = b.get(i-l[i],0) + 1

for av in a:
    ans = ans + b.get(av,0)

print(ans)